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

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

/*  $RCSfile: ValueSet.c,v $
    $Log: ValueSet.c,v $
 * Revision 1.22.1.1  1994/12/08  14:47:56  thoth
 * Comparison rework to centralize computation.
 *
 * Revision 1.22  1994/10/06  18:41:05  gmt
 * Fixed typo
 *
 * Revision 1.21  1994/10/06  18:37:05  gmt
 * temporary hack to make this compile with SC++ without proper bsearch
 * and qsort routines.
 *
 * Revision 1.20  1994/10/04  21:00:18  gmt
 * Changed ValueType to T since the ValueSet.c and ValueSet.h did not match.
 *
 * Revision 1.19  1994/10/04  05:59:09  gmt
 * Fixed SC++ problem with nested enums for IA::LatticeRelation
 *
 * Revision 1.18  1994/10/03  17:54:28  thoth
 * Added iterators.
 * changed ValueType to T.
 * removed the binary ops between Sets and scalars since they were
 * inaccessible to users and unused by the IA_Set class.
 *
 * Revision 1.17  1994/09/27  04:41:19  gmt
 * Changed IA::LatticeRelation to IA_LatticeRelation since the mac
 * doesn't deal with enums defined inside of templated classes.  Not
 * that IA_LatticeRelation is #defined to IA::LatticeRelation in
 * ia.h . . .
 *
 * Revision 1.16  1994/09/20  17:28:38  thoth
 * Handle some difficulties with G++ instantiation of static data members.
 *
 * Revision 1.15  1994/08/22  15:10:18  thoth
 * fix to operator<.  All this code needs a review.
 *
 * Revision 1.14  1994/08/09  18:41:41  thoth
 * Logic errors in < partly fixed.
 *
 * Revision 1.13  1994/03/14  15:34:56  thoth
 * Work around bug in CFront float formal parameters.
 * Need dummy for type().
 *
 * Revision 1.12  1993/11/17  17:57:17  thoth
 * use value_type_compare any place you need a comparison
 * of values.
 *
 * Revision 1.11  1993/06/10  17:08:50  thoth
 * Fix array constructor.
 *
 * Revision 1.10  93/05/26  16:32:04  thoth
 * Copyright Notices
 * 
 * Revision 1.9  93/05/26  13:49:20  thoth
 * move the special functions into another module
 * 
 * Revision 1.8  93/02/20  15:25:02  thoth
 * The LatticeRelation that was causing a compiler bug is now
 * used from IA instead of IA_ValueSet<T>.
 * 
 * Revision 1.7  93/02/08  19:56:57  thoth
 * added output method for testing.
 * Also added ifdefs since template implementation file are really
 * "headers".  We were having problems with multiple inclusion.
 * 
 * Revision 1.6  92/12/14  16:18:50  jm
 *  Renamed class ValueSet to IA_ValueSet
 * 
 * Revision 1.5  92/10/22  14:04:47  jm
 * fixed operator "<=" on two value sets
 * 
 * Revision 1.4  92/09/29  15:27:24  jm
 * *** empty log message ***
 * 
 * Revision 1.3  92/09/16  16:41:30  jm
 * added comments to remove_dup and count_dup functions.
 * changed NULL to 0.
 * 
 * Revision 1.2  92/09/16  14:47:23  jm
 * Included value_range function as an independent function
 * function contains() now returns 1 or 0
 * added keyword 'const' to function count_dup
 * added keyword 'const' to all member operators
 * added definition for operators '>' and '<'
 * added definition for function compare
 * 
 * Revision 1.1  92/09/16  14:46:28  jm
 * Initial revision
 * 
Revision 1.6  92/09/09  14:36:35  jm
cleaned up use of dynamic memory in operator.

Revision 1.5  92/09/08  14:37:44  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.4  92/09/01  13:59:36  jm
added friend functions for operators between elements and ValueSets.
Added a guard for the "bsearch" function
templatized ValueSet
changed the "-" operator to the "/" operator

Revision 1.3  92/08/28  10:01:36  jm
added RCS keywords "RCSfile" and "Log"

*/

#ifndef ValueSet_c_
#define ValueSet_c_

#include <iostream.h>
#include <stdlib.h>
#include "ValueSet.h"
#include "VSIter.h"

#ifndef IA_NO_AUTOINST_OF_STATIC_DATA
template <class T>
char IA_ValueSet<T>::dummy;
#endif

template <class T>
int IA_ValueSet<T>::contains(T e) const
{
    if (this->size == 0) return 0;
    T	e_ = e;
#ifdef __SC__
	return 0;
#else
    return ((int) bsearch((T *)(&e_), 
			 (T *)this->value_array,
			 this->size, sizeof(T),
			 this->value_type_compare) == 0 ? 0 : 1);
#endif
}
    
template <class T>
int IA_ValueSetComparator<T>::value_type_compare(
    const void *t1, const void *t2) {
    if (*(T *)t1 > *(T *)t2)
	return 1;
    
    if (*(T *)t1 < *(T *)t2)
	return -1;
    return 0;
}

template <class T>
IA_ValueSet<T>::IA_ValueSet(const IA_ValueSet<T>& vs) {
    this->size = vs.size;
    if (this->size == 0)
	this->value_array = 0;
    else {
	this->value_array = new T[this->size];
	for (unsigned int i = 0; i < this->size; i++)
	    this->value_array[i] = vs.value_array[i];
    }
}

template <class T>
IA_ValueSet<T>::IA_ValueSet(T v0) {
    this->value_array = new T[this->size = 1];
    
    this->value_array[0] = v0;
}

template <class T>
IA_ValueSet<T>::IA_ValueSet(T v0, T v1) {
    
    this->value_array = new T[this->size = 2];

    this->value_array[0] = v0;
    this->value_array[1] = v1;
    make_set();
}

template <class T>
IA_ValueSet<T>::IA_ValueSet(T v0, T v1, T v2) {

    this->value_array = new T[this->size = 3];
    
    this->value_array[0] = v0;
    this->value_array[1] = v1;
    this->value_array[2] = v2;
    make_set();
}

template <class T>
IA_ValueSet<T>::IA_ValueSet(T v0, T v1,T v2, 
			      T v3) {
    this->value_array = new T[this->size = 4];
    
    this->value_array[0] = v0;
    this->value_array[1] = v1;
    this->value_array[2] = v2;
    this->value_array[3] = v3;
    make_set();

}

template <class T>
IA_ValueSet<T>::IA_ValueSet(T v0, T v1, T v2, 
			      T v3, T v4) {
    this->value_array = new T[this->size = 5];
    
    this->value_array[0] = v0;
    this->value_array[1] = v1;
    this->value_array[2] = v2;
    this->value_array[3] = v3;
    this->value_array[4] = v4;
    make_set();
}

template <class T>
IA_ValueSet<T>::IA_ValueSet(const T* ar, unsigned int sz) {
    if (sz == 0) {
	this->size = 0;
	this->value_array = 0;
    }
    else {
	this->value_array = new T[this->size = sz];
	for (unsigned int i=0; i < sz; i++)
	    this->value_array[i] = ar[i];
	make_set();
    }
}

// make_set: sorts the value_array and removes duplicates.

template <class T>
void IA_ValueSet<T>::make_set() {
    if (this->size == 0)
	this->value_array = 0;
    else {
#ifndef __SC__
	qsort(this->value_array, this->size, sizeof(T),
	      this->value_type_compare);
#endif
	remove_dup();
    }
}

// remove_dup is for the private use of make_set
// this->size must not be 0.

template <class T>
void IA_ValueSet<T>::remove_dup() {
    
    T *clean_array = new T[this->size - count_dup()];
    
    unsigned int di = 0;
    
    for (unsigned int i=0; i < this->size - 1; i++)
	if (this->value_array[i] != this->value_array[i+1])
	    clean_array[di++] = this->value_array[i];
    clean_array[di++] = this->value_array[this->size - 1];
    delete [] this->value_array;
    this->value_array = clean_array;
    this->size = di;
}

// count_dup is for the private use of make_set

template <class T>
int IA_ValueSet<T>::count_dup() const {
    int count = 0;
    for (unsigned int i=0; i < this->size - 1; i++)
	if (this->value_array[i] == this->value_array[i+1])
	    count++;
    return count;
}

template <class T>
IA_ValueSet<T>& 
IA_ValueSet<T>::operator=  (const IA_ValueSet<T>& vs) {
    if (this == &vs) 
	return *this;

    // handle empty set possibility
    
    if (vs.size == 0) {
	delete[] this->value_array;  // OK even if value_array already 0
	this->value_array = 0; 
	this->size = 0;
	return *this;
    }
    
    // handle the typical case
    
    if (vs.size != this->size) {
	delete[] this->value_array;
	this->value_array = new T[vs.size];
	this->size = vs.size;
    }
    
    for (unsigned int i = 0; i < this->size; i++)
	this->value_array[i] = vs.value_array[i];
    
    return *this;
}


template <class T>
IA_BaseSetIter<T> *
IA_ValueSet<T> :: iterator() const
{
			// cast away const to allow frobbing of refcount
    return new IA_ValueSetIter<T>((IA_ValueSet<T>*)this);
}

//
//
//

template <class T>
IA_ValueSet<T> 
IA_ValueSet<T>::operator| (const IA_ValueSet<T> &right) const {
    unsigned int li = 0, ri = 0, ci = 0;

    if (this == &right) 
	return IA_ValueSet<T>(*this);

    T* temp = new T[this->size + right.size];
    while ((li < this->size) && (ri < right.size))
	if (value_type_compare(&this->value_array[li],&right.value_array[ri])<0)
	    temp[ci++] = this->value_array[li++];
	else {
	    temp[ci++] = right.value_array[ri];
	    if (this->value_array[li] == right.value_array[ri++])
		li++;
	}
    if (li == this->size)
	for (;ri < right.size;ri++)
	    temp[ci++] = right.value_array[ri];
    else
	for (;li < this->size;li++)
	    temp[ci++] = this->value_array[li];
    return IA_ValueSet<T>(temp, ci);
}

#if 0
template <class T>
IA_ValueSet<T> 
IA_ValueSet<T>::operator| (const T &right) const {
    return *this | IA_ValueSet<T>(right);
}

template <class T>
IA_ValueSet<T> 
operator| (const T &left, const IA_ValueSet<T> &right) {
    return IA_ValueSet<T>(left) | right;
}
#endif

//
//
//

template <class T>
IA_ValueSet<T> 
IA_ValueSet<T>::operator& (const IA_ValueSet<T> &right)  const {
    unsigned int li = 0, ri = 0, ci = 0;

    if ((this->empty()) || (right.empty()))
	return IA_ValueSet<T>();
    {
	T	lmax = this->max();
	T	lmin = this->min();
	T	rmax = right.max();
	T	rmin = right.min();
	if (value_type_compare(&lmax, &rmin)<0 ||
	    value_type_compare(&rmax, &lmin)<0)
	    return IA_ValueSet<T>();
    }
    if (this == &right) 
	return IA_ValueSet<T>(*this);

    T* temp = new T[this->card() < right.card() 
				    ? this->size : right.size];

    while ((li < this->size) && (ri < right.size))
	if (value_type_compare(&this->value_array[li],&right.value_array[ri])<0)
	    li++;
	else {
	    if (this->value_array[li] == right.value_array[ri]) {
		temp[ci++] = right.value_array[ri];
		li++;
	    }
	    ri++;
	}
    return IA_ValueSet<T>(temp, ci);
}

#if 0
template <class T>
IA_ValueSet<T> 
IA_ValueSet<T>::operator& (const T &right) const {
    if (this->contains(right))
	return IA_ValueSet<T>(right);
    else
	return IA_ValueSet<T>();
}

template <class T>
IA_ValueSet<T> 
operator& (const T &left, const IA_ValueSet<T> &right) {
    if (right.contains(left))
	return IA_ValueSet<T>(left);
    else
	return IA_ValueSet<T>();
}
#endif

//
//
//

template <class T>
IA_ValueSet<T> 
IA_ValueSet<T>::operator/ (const IA_ValueSet<T> &right) const {
    unsigned int li = 0, ri = 0, ci = 0;

    if (this->empty())
	return IA_ValueSet<T>();
    if (right.empty())
	return IA_ValueSet<T>(*this);
    if (this == &right) 
	return IA_ValueSet<T>();

    T* temp = new T[this->size];
    while ((li < this->size) && (ri < right.size)) {
	int cmp = value_type_compare(&this->value_array[li],
				     &right.value_array[ri]);
	if (cmp<0)
	    temp[ci++] = this->value_array[li++];
	else {
	    if (cmp==0)
		li++;
	    ri++;
	}
    }
    if (ri == right.size)
	for (;li<this->size;li++)
	    temp[ci++] = this->value_array[li];
    return IA_ValueSet<T>(temp, ci);
}

#if 0
template <class T>
IA_ValueSet<T> 
IA_ValueSet<T>::operator/ (const T &right) const {
    return *this / IA_ValueSet<T>(right);
}

template <class T>
IA_ValueSet<T> 
operator/ (const T &left, const IA_ValueSet<T> &right) {
    if (right.contains(left))
	return IA_ValueSet<T>();
    else
	return IA_ValueSet<T>(left);
}
#endif

//
//
//

template <class T>
IA_ValueSet<T> 
IA_ValueSet<T>::operator^ (const IA_ValueSet<T> &right) const {
    unsigned int li = 0, ri = 0, ci = 0;

    if (this->empty())
	return IA_ValueSet<T>(right);
    if (right.empty())
	return IA_ValueSet<T>(*this);
    if (this == &right) 
	return IA_ValueSet<T>();

    T* temp = new T[this->size + right.size];
    while ((li < this->size) && (ri < right.size)) {
	int cmp = value_type_compare(&this->value_array[li],
				     &right.value_array[ri]);
	if (cmp<0)
	    temp[ci++] = this->value_array[li++];
	else if (cmp>0)
	    temp[ci++] = right.value_array[ri++];
	else { 
	    li++;
	    ri++;
	}
    }
    if (ri == right.size)
	for (;li<this->size;li++)
	    temp[ci++] = this->value_array[li];
    if (li == this->size)
	for (;ri<right.size;ri++)
	    temp[ci++] = right.value_array[ri];
    return IA_ValueSet<T>(temp, ci);
}
#if 0
template <class T>
IA_ValueSet<T> 
IA_ValueSet<T>::operator^ (const T &right) const {

    if (this->contains(right))
	return IA_ValueSet<T>(*this / right);
    else
	return IA_ValueSet<T>(*this | right);
}

template <class T>
IA_ValueSet<T> 
operator^ (const T &left, const IA_ValueSet<T> &right) {

    if (right.contains(left))
	return IA_ValueSet<T>(right / left);
    else
	return IA_ValueSet<T>(right | left);
}
#endif

//
//
//

#if 0				// Set.c will use the compare() function.

template <class T> 
int 
IA_ValueSet<T>::operator<= (const IA_ValueSet<T> &right) const {

    unsigned int li = 0, ri = 0;

    if (this->empty())
	return 1;
    if (right.empty())
	return 0;
    if (this == &right) return 1;
    while ((li < this->size) && (ri < right.size)) {
	int cmp = value_type_compare(&this->value_array[li],
				     &right.value_array[ri]);
	if (cmp<0)
	    return 0;
	else {
	    if (cmp==0)
		li++;
	    ri++;
	}
    }
    if (ri == right.size)
	if (li == this->size)
	    return 1;
	else
	    return 0;
    return 1;
}

#if 0
template <class T> 
int 
IA_ValueSet<T>::operator<= (const T &right) const {

    if (this->size == 0) 
	return 1;
    if (this->size == 1)
	return this->max() == right;
    return 0;
}

template <class T> 
int 
operator<= (const T &left, const IA_ValueSet<T> &right){

    if (right.contains(left)) 
	return 1;
    return 0;
}
#endif

//
//
//

template <class T>
int 
IA_ValueSet<T>::operator>= (const IA_ValueSet<T> &right) const {
    return right <= *this;
}

#if 0
template <class T>
int 
IA_ValueSet<T>::operator>= (const T &right) const {
    return right <= *this;
}

template <class T>
int 
operator>= (const T &left, const IA_ValueSet<T> &right){
    return right <= left;
}
#endif

//
//
//

template <class T> 
int 
IA_ValueSet<T>::operator< (const IA_ValueSet<T> &right) const {

    unsigned int li = 0, ri = 0;

    if (right.empty())
	return 0;
    if (this->empty())
	return 1;
    if (this->size >= right.size)
	return 0;		// short-circuits s<s

    while ((li < this->size) && (ri < right.size)) {
	int cmp = value_type_compare(&this->value_array[li],
				     &right.value_array[ri]);
	if (cmp<0)
	    return 0;
	else {
	    if (cmp==0)
		li++;
	    ri++;
	}
    }

    if (li == this->size)
	return 1;
    return 0;
}

#if 0
template <class T> 
int 
IA_ValueSet<T>::operator< (const T &) const {

    return (this->size == 0);
}

template <class T> 
int 
operator< (const T &left, const IA_ValueSet<T> &right){

    return (right.contains(left) && (right.size > 1));

}
#endif

//
//
//

template <class T>
int 
IA_ValueSet<T>::operator> (const IA_ValueSet<T> &right) const {

    return (right < *this);

}
#if 0
template <class T>
int 
IA_ValueSet<T>::operator> (const T &right) const {
    return (right < *this);
}

template <class T>
int 
operator> (const T &left, const IA_ValueSet<T> &right){
    return (right < left);
}
#endif

//
//
//

template <class T> 
int 
IA_ValueSet<T>::operator== (const IA_ValueSet<T> &right) const {

    if (this->size != right.size)
	return 0;
    for (unsigned int i = 0; i < this->size; i++)
       if (this->value_array[i] != right.value_array[i])
	   return 0;
    return 1;
}

#if 0
template <class T> 
int 
IA_ValueSet<T>::operator== (const T &right) const {

    if (this->size != 1)
	return 0;
    return this->max() == right;
}

template <class T> 
int 
operator== (const T &left, const IA_ValueSet<T> &right){

    if (right.size != 1)
	return 0;
    return right.max() == left;
}
#endif

//
//
//

template <class T> 
int 
IA_ValueSet<T>::operator!= (const IA_ValueSet<T> &right) const {
    return !(*this == right);
}

#if 0
template <class T> 
int 
IA_ValueSet<T>::operator!= (const T &right) const {
    return !(*this == right);
}

template <class T> 
int 
operator!= (const T &left, const IA_ValueSet<T> &right){
    return !(left == right);
}
#endif

#endif

//
//
//

template <class T>
#ifdef IA_NO_NESTED_ENUMS
IA_LatticeRelation
#else
IA::LatticeRelation
#endif
compare(const IA_ValueSet<T> &lhs, const IA_ValueSet<T> &rhs)
{
#ifdef IA_NO_NESTED_ENUMS
    IA_LatticeRelation
#else
	IA::LatticeRelation
#endif
	    rval=IA::EQUAL;

    int	li,ri;			// left and right indices

    li = ri = 0;

    while (li < lhs.size && ri < rhs.size) {
	int cmp = IA_ValueSet<T>::value_type_compare(&lhs.value_array[li],
						     &rhs.value_array[ri]);

	if (cmp<0) {
	    if (rval==IA::P_SUBSET) // Left was missing some from the right,
		return IA::NO_REL;  // now it has an extra.  No relation.
	    li++;
	    rval = IA::P_SUPERSET; // otherwise left is a superset so far
	} else if (cmp==0) {
	    li++;
	    ri++;
	} else /* cmp>0 */ {
	    if (rval==IA::P_SUPERSET) // Right was missing some from the left,
		return IA::NO_REL;    // now it has an extra.  No relation.
	    ri++;
	    rval = IA::P_SUBSET; // otherwise right is a superset so far
	}
    }
    if (li<lhs.size) {
	if (rval==IA::P_SUBSET)	// Left was missing some from the right,
	    return IA::NO_REL;  // now it has an extra.  No relation.
	return IA::P_SUPERSET; // otherwise left is a superset
    } else if (ri<rhs.size) {
	if (rval==IA::P_SUPERSET) // Right was missing some from the left,
	    return IA::NO_REL;  // now it has an extra.  No relation.
	return IA::P_SUBSET; // otherwise right is a superset
    } else {
	// ran out of items from both at the same time.  Whatever
	// we determined before is cool.
	return rval;
    }
}

template <class T>
ostream& operator<< (ostream& st, const IA_ValueSet<T>& vs) {
    int last_index = vs.size-1;
    st << "<"; 
    if (vs.size > 0) {
	for (int i=0; i < last_index; i++)
	    st << vs.value_array[i] << " ";
	if (vs.size > 0)
	    st << vs.value_array[last_index];
    }
    st << ">" << '\n';
    return st;
}

#endif // ValueSet_c_
