// Emacs -*- C++ -*-

//
//	Copyright 1993, Center for Computer Vision and Visualization,
//	University of Florida.  All rights reserved.
//

/* $RCSfile: ValueSet.h,v $
   $Log: ValueSet.h,v $
 * Revision 1.23  1994/01/31  16:34:30  thoth
 * added the ability to reset a ValueSetIter.
 *
 * Revision 1.22  1993/11/17  17:57:51  thoth
 * added choice() member to valueset.
 *
 * Revision 1.21  1993/06/10  17:09:49  thoth
 * Fix array constructor.
 *
 * Revision 1.20  93/05/26  16:32:07  thoth
 * Copyright Notices
 * 
 * Revision 1.19  93/02/20  15:23:13  thoth
 * The LatticeRelation that was causing a compiler bug is now
 * used from IA instead of IA_ValueSet<T>.
 * 
 * Revision 1.18  93/02/08  19:57:51  thoth
 * added output method for testing.
 * added workaround for 3.0.2 bug.
 * 
 * Revision 1.17  92/12/14  16:18:10  jm
 * Renamed class ValueSet to IA_ValueSet
 * 
 * Revision 1.16  92/10/22  14:05:13  jm
 * *** empty log message ***
 * 
 * Revision 1.15  92/09/29  15:26:54  jm
 * *** empty log message ***
 * 
 * Revision 1.14  92/09/25  14:47:01  jm
 * *** empty log message ***
 * 
 * Revision 1.13  92/09/16  17:06:33  jm
 * added spec for value_range function
 * 
 * Revision 1.12  92/09/16  16:36:33  jm
 * Added commnet to compare function
 * changed NULL to 0.
 * 
 * Revision 1.11  92/09/16  14:38:59  jm
 * Added the class ValueSetIter to provide an iterator for ValueSet
 * Rearranged the different operators for esthetic purposes
 * Added keyword 'const' to all member operators
 * Added LatticeRelation enum type, used by the compare function
 * Added declaration for compare function
 * added operators '>' and '<' for proper superset and proper subset
 * added keyword 'const' to private function count_dup
 * Moved function value_range outside the class as an independent function
 *   that takes only integer parameters
 * 
 * Revision 1.10  92/09/08  14:37:04  jm
 * removed code that had been commented out before.
 * 
 * Revision 1.9  92/09/08  14:30:47  jm
 * the operators have been redefined to be class members in the case of
 * valueset op element, and valueset op valueset. The combination 
 * element op valueset remains as a friend.
 * the function make_set does not take parameters anymore. It operates on
 * the internal value_array and size.
 * function value_range has been changed from class member to independent. It
 * will only work with integer arguments.
 * predicate operators now return an int instead of a char, in order to be
 * able to print the result.
 * 
Revision 1.1  92/09/01  14:02:25  jm
Initial revision

*/

#ifndef ValueSet_h_
#define ValueSet_h_

#include <search.h>
#include <stream.h>
#include <assert.h>
#include "ia.h"

// This class is created to provide a "default" comparator function
// for ValueType. If the user of ValueSet does not like this comparator,
// a new one can be provided.
// Notice the use of void parameters; this is because the return type and
// the argument types must match exactly to the specification needed by
// the "bsearch" and "qsort" routines used in the "contains" and "make_set"
// functions, respectively.

template <class ValueType>
class IA_ValueSetComparator {
public:
    static int value_type_compare(const void *, const void *); 
};

template <class ValueType> class IA_ValueSetIter;
template <class ValueType> class IA_ValueSet;

template <class T> ostream& operator<< (ostream&, const IA_ValueSet<T>&);

template <class ValueType>
class IA_ValueSet: public IA_ValueSetComparator<ValueType> {
  private:
    unsigned int size;
    ValueType *value_array;
  public:
    IA_ValueSet() {size = 0; value_array = 0;}
    IA_ValueSet(const IA_ValueSet&);
    IA_ValueSet& operator= (const IA_ValueSet&);
    ~IA_ValueSet() {if (this->value_array != 0) delete [] value_array;}
    
    IA_ValueSet(ValueType);
    IA_ValueSet(ValueType, ValueType);
    IA_ValueSet(ValueType, ValueType, ValueType);
    IA_ValueSet(ValueType, ValueType, ValueType, ValueType);
    IA_ValueSet(ValueType, ValueType, ValueType, ValueType, ValueType);
    IA_ValueSet( const ValueType*, unsigned int);
    
    // card: cardinality, number of elements in the set
    
    unsigned int card() const {return this->size;}
    
    // contains: predicate for testing membership of an element in a set
    
    int contains(ValueType) const;
    
    // min: minimum element of the set
    
    ValueType min() const {
	if (this->size == 0) 
	    ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);    
	return this->value_array[0];
    }
    
    // max: maximum element of the set
    
    ValueType max() const {
	if (this->size == 0) 
	    ia_throw(IA::INVALID_OPERATION, __FILE__, __LINE__);    
	return this->value_array[this->size-1];
    }

    // choice: some element from the set, we don't care which one
    ValueType choice() const {
	return max();		// how lame.
    }
    
    // empty: predicate for testing emptiness of a set 
    
    int empty() const {return (this->size == 0);}
    
    IA_ValueSet<ValueType> operator|  (const IA_ValueSet<ValueType>&) const;
    IA_ValueSet<ValueType> operator&  (const IA_ValueSet<ValueType>&) const;
    IA_ValueSet<ValueType> operator/  (const IA_ValueSet<ValueType>&) const;
    IA_ValueSet<ValueType> operator^  (const IA_ValueSet<ValueType>&) const;
    
    IA_ValueSet<ValueType> operator|  (const ValueType&) const;
    IA_ValueSet<ValueType> operator&  (const ValueType&) const;
    IA_ValueSet<ValueType> operator/  (const ValueType&) const;
    IA_ValueSet<ValueType> operator^  (const ValueType&) const;
    
    friend IA_ValueSet<ValueType>	
    operator|  (const ValueType&, const IA_ValueSet<ValueType>&);
    friend IA_ValueSet<ValueType>	
    operator&  (const ValueType&, const IA_ValueSet<ValueType>&);
    friend IA_ValueSet<ValueType>	
    operator/  (const ValueType&, const IA_ValueSet<ValueType>&);
    friend IA_ValueSet<ValueType>	
    operator^  (const ValueType&, const IA_ValueSet<ValueType>&);
    
    // The range of return values for this compare function does not include
    // all the enumerated values.
    
    int operator<= (const IA_ValueSet<ValueType>&) const;
    int operator>= (const IA_ValueSet<ValueType>&) const;
    int operator<  (const IA_ValueSet<ValueType>&) const;
    int operator>  (const IA_ValueSet<ValueType>&) const;
    int	operator== (const IA_ValueSet<ValueType>&) const;
    int	operator!= (const IA_ValueSet<ValueType>&) const;
    
    int operator<= (const ValueType&) const;
    int operator>= (const ValueType&) const;
    int operator<  (const ValueType&) const;
    int operator>  (const ValueType&) const;
    int	operator== (const ValueType&) const;
    int operator!= (const ValueType&) const;
    
    friend int operator<= (const ValueType&, const IA_ValueSet<ValueType>&);
    friend int operator>= (const ValueType&, const IA_ValueSet<ValueType>&);
    friend int operator<  (const ValueType&, const IA_ValueSet<ValueType>&);
    friend int operator>  (const ValueType&, const IA_ValueSet<ValueType>&);
    friend int operator== (const ValueType&, const IA_ValueSet<ValueType>&);
    friend int operator!= (const ValueType&, const IA_ValueSet<ValueType>&);

    friend IA::LatticeRelation
    compare(const IA_ValueSet<ValueType>&,
	    const IA_ValueSet<ValueType>&);
   
#ifndef WORKAROUND_CFRONT_FRIEND_MANGLING_BUG
    friend ostream& operator<< (ostream&, const IA_ValueSet<ValueType>&);
#endif
    friend class IA_ValueSetIter<ValueType>;
    
  private:
    
    // Set_Nth procedure, note:  indices start at 0
    void set_nth (unsigned int index, ValueType value) {
	if (index >= this->size)
	    ia_throw(IA::POINT_INDEX_MISMATCH, __FILE__, __LINE__);
	this->value_array[index] = value;
	// problem? need promotion to proper type?
    }
    
    int count_dup() const;
    void make_set();
    void remove_dup();
    
};

template <class ValueType>
class IA_ValueSetIter {
    const IA_ValueSet<ValueType>* vsp;
    int i;
public:
    IA_ValueSetIter(const IA_ValueSet<ValueType> &vs) { vsp = &vs; i = 0;}
    int operator()(ValueType& vt) {
	int ret = 1;
	if (i < vsp->size) vt = vsp->value_array[i++];
	else ret = 0;
	return ret;
    }
    void reset() {
	i=0;
    }
};

IA_ValueSet<int> value_range(int v0, int v1);

#endif

