/*  $RCSfile: ValueSet.C,v $
    $Log: ValueSet.C,v $
Revision 1.7  1992/09/16  17:18:24  jm
last version of .C -> moved to .c

 * 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"

*/

#include <stream.h>
#include "ValueSet.h"

ValueSet<int> value_range(int v0, int v1) {
    ValueSet<int> vs;
    int sz = v1 - v0;
    
    if (sz < 0)
	return ValueSet<int>();
    if (sz == 0)
	return ValueSet<int>(v0);
    int *ret_array = new int[++sz];
    for (int i = 0; i < sz; i++)
	ret_array[i] = v0+i;
    return ValueSet<int>(ret_array, sz);
}

template <class ValueType>
int ValueSet<ValueType>::contains(ValueType e) const {
    
    if (this->size == 0) return 0;
	
    return ((int) bsearch((ValueType *)(&e), 
			 (ValueType *)this->value_array,
			 this->size, sizeof(ValueType),
			 this->value_type_compare) == 0 ? 0 : 1);
}    
    
template <class ValueType>
int ValueSetComparator<ValueType>::value_type_compare(
    const void *t1, const void *t2) {
    if (*(ValueType *)t1 > *(ValueType *)t2)
	return 1;
    
    if (*(ValueType *)t1 < *(ValueType *)t2)
	return -1;
    return 0;
}

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

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

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

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

template <class ValueType>
ValueSet<ValueType>::ValueSet(ValueType v0, ValueType v1, ValueType v2) {

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

template <class ValueType>
ValueSet<ValueType>::ValueSet(ValueType v0, ValueType v1,ValueType v2, 
			      ValueType v3) {
    this->value_array = new ValueType[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 ValueType>
ValueSet<ValueType>::ValueSet(ValueType v0, ValueType v1, ValueType v2, 
			      ValueType v3, ValueType v4) {
    this->value_array = new ValueType[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 ValueType>
ValueSet<ValueType>::ValueSet(ValueType* const ar, unsigned int sz) {
    if (sz == 0) {
	this->size = 0;
	this->value_array = 0;
    }
    else {
	this->value_array = new ValueType[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 ValueType>
void ValueSet<ValueType>::make_set() {
    if (this->size == 0)
	this->value_array = 0;
    else {
	qsort(this->value_array, this->size, sizeof(ValueType),
	      this->value_type_compare);
	remove_dup();
    }
}

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

template <class ValueType>
void ValueSet<ValueType>::remove_dup() {
    
    ValueType *clean_array = new ValueType[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 ValueType>
int ValueSet<ValueType>::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 ValueType>
ValueSet<ValueType>& 
ValueSet<ValueType>::operator=  (const ValueSet<ValueType>& 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 ValueType[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 ValueType>
ValueSet<ValueType> 
ValueSet<ValueType>::operator| (const ValueSet<ValueType> &right) const {
    unsigned int li = 0, ri = 0, ci = 0;

    if (this == &right) 
	return ValueSet<ValueType>(*this);

    ValueType* temp = new ValueType[this->size + right.size];
    while ((li < this->size) && (ri < right.size))
	if (this->value_array[li] < right.value_array[ri])
	    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 ValueSet<ValueType>(temp, ci);
}

template <class ValueType>
ValueSet<ValueType> 
ValueSet<ValueType>::operator| (const ValueType &right) const {
    return *this | ValueSet<ValueType>(right);
}

template <class ValueType>
ValueSet<ValueType> 
operator| (const ValueType &left, const ValueSet<ValueType> &right) {
    return ValueSet<ValueType>(left) | right;
}

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

    if ((this->empty()) || (right.empty()))
	return ValueSet<ValueType>();
    if ((this->max() < right.min()) || (this->min() > right.max()))
	return ValueSet<ValueType>();
    if (this == &right) 
	return ValueSet<ValueType>(*this);

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

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

template <class ValueType>
ValueSet<ValueType> 
ValueSet<ValueType>::operator& (const ValueType &right) const {
    if (this->contains(right))
	return ValueSet<ValueType>(right);
    else
	return ValueSet<ValueType>();
}

template <class ValueType>
ValueSet<ValueType> 
operator& (const ValueType &left, const ValueSet<ValueType> &right) {
    if (right.contains(left))
	return ValueSet<ValueType>(left);
    else
	return ValueSet<ValueType>();
}

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

    if (this->empty())
	return ValueSet<ValueType>();
    if (right.empty())
	return ValueSet<ValueType>(*this);
    if (this == &right) 
	return ValueSet<ValueType>();

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

template <class ValueType>
ValueSet<ValueType> 
ValueSet<ValueType>::operator/ (const ValueType &right) const {
    return *this / ValueSet<ValueType>(right);
}

template <class ValueType>
ValueSet<ValueType> 
operator/ (const ValueType &left, const ValueSet<ValueType> &right) {
    if (right.contains(left))
	return ValueSet<ValueType>();
    else
	return ValueSet<ValueType>(left);
}

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

    if (this->empty())
	return ValueSet<ValueType>(right);
    if (right.empty())
	return ValueSet<ValueType>(*this);
    if (this == &right) 
	return ValueSet<ValueType>();

    ValueType* temp = new ValueType[this->size + right.size];
    while ((li < this->size) && (ri < right.size)) 
	if (this->value_array[li] < right.value_array[ri])
	    temp[ci++] = this->value_array[li++];
	else
	    if (this->value_array[li] > right.value_array[ri])
		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 ValueSet<ValueType>(temp, ci);
}

template <class ValueType>
ValueSet<ValueType> 
ValueSet<ValueType>::operator^ (const ValueType &right) const {

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

template <class ValueType>
ValueSet<ValueType> 
operator^ (const ValueType &left, const ValueSet<ValueType> &right) {

    if (right.contains(left))
	return ValueSet<ValueType>(right / left);
    else
	return ValueSet<ValueType>(right | left);
}

template <class ValueType> 
int 
ValueSet<ValueType>::operator<= (const ValueSet<ValueType> &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)) {
	if (this->value_array[li] < right.value_array[ri])
	    return 0;
	if (this->value_array[li] == right.value_array[ri++])
	    li++;
    }
    return 1;
}

template <class ValueType> 
int 
ValueSet<ValueType>::operator<= (const ValueType &right) const {

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

template <class ValueType> 
int 
operator<= (const ValueType &left, const ValueSet<ValueType> &right){

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

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

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

template <class ValueType>
int 
operator>= (const ValueType &left, const ValueSet<ValueType> &right){
    return right <= left;
}

template <class ValueType> 
int 
ValueSet<ValueType>::operator< (const ValueSet<ValueType> &right) const {

    unsigned int li = 0, ri = 0;

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

    if (li == this->size)
	if (ri == right.size)
	    return 0;
	else
	    return 1;
    return 0;
}

template <class ValueType> 
int 
ValueSet<ValueType>::operator< (const ValueType &right) const {

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

template <class ValueType> 
int 
operator< (const ValueType &left, const ValueSet<ValueType> &right){

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

}

template <class ValueType>
int 
ValueSet<ValueType>::operator> (const ValueSet<ValueType> &right) const {

    return (right < *this);

}

template <class ValueType>
int 
ValueSet<ValueType>::operator> (const ValueType &right) const {
    return (right < *this);
}

template <class ValueType>
int 
operator> (const ValueType &left, const ValueSet<ValueType> &right){
    return (right < left);
}

template <class ValueType> 
int 
ValueSet<ValueType>::operator== (const ValueSet<ValueType> &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;
}

template <class ValueType> 
int 
ValueSet<ValueType>::operator== (const ValueType &right) const {

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

template <class ValueType> 
int 
operator== (const ValueType &left, const ValueSet<ValueType> &right){

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

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

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

template <class ValueType> 
int 
operator!= (const ValueType &left, const ValueSet<ValueType> &right){
    return !(left == right);
}

template <class ValueType>
ValueSet<ValueType>::LatticeRelation
compare(const ValueSet<ValueType> &lhs, const ValueSet<ValueType> &rhs) {

   if (lhs == rhs)
       return ValueSet<ValueType>::EQUAL;
   if (lhs < rhs)
       return ValueSet<ValueType>::P_SUBSET;
   if (lhs > rhs)
       return ValueSet<ValueType>::P_SUPERSET;
   return ValueSet<ValueType>::NO_REL;

}
