// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): SUNY Stony Brook students, Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#define Subset_CC

#include <stdlib.h>
#include <math.h>

template<class Item>
SubSet<Item>::SubSet()		// this is a dummy routine to
{				// satisfy the List class, which
  original= new Set<Item>();	// defines  static T it;
				// (T can be SubSet<int>, e.g.)
  subset=new Bool[DEFAULT_SUBSET_SIZE]; 
}

/*  Nonsense   - JWB
template<class Item>
SubSet<Item>::SubSet( int size )
{ if (size<=0)
    { warning("Wrong argument, size must be > 0,now size=1\n");
       size=1;
    }
  original= new Set<Item>();
  subset=new Bool[size]; 
  for ( int i=size-1; i>=0; i--)
      { 
        original->insert(i+1);  // arg mismatch -- JWB
        subset[i]=0;
       }
}
*/

template<class Item>
SubSet<Item>::SubSet(const Set<Item>& s)
{ 
  original= new Set<Item>(s);
  int size=s.size();
  subset=new Bool[size];
  for ( int i=0; i<size; i++) subset[i]=0;
}

template<class Item>
SubSet<Item>::SubSet(const SubSet<Item>& s)
{ 
  original = new Set<Item>(*(s.original));
  subset=new Bool[s.order()]; 
  for ( int i=s.order()-1; i>=0; i--) {
	if (s.subset[i])  
        	subset[i]=1;
	else
        	subset[i]=0;
  }
}

template<class Item>
SubSet<Item>::~SubSet()
{
	delete original; 
	delete [] subset;
}

template<class Item>
Set<Item>
SubSet<Item>::makeSet() const
{ Set<Item>  result;
  int i=0;
  Iterator<Item> get_next1(original);
  Item item;
  while( get_next1(item) ) { 
	if ( subset[i]) 
		result.insert(item); 
	i++;
  } 
  return result;
}

template<class Item>
ostream&
SubSet<Item>::display(ostream& os) const
{ Set<Item> sub_set;
  sub_set=makeSet();
  sub_set.display(os);
  return os;
}


template<class Item>
int
SubSet<Item>::size() const
{ int size=0;
  for ( int i=0; i<original->size(); i++)
  if ( subset[i] ) size++; 
  return size;
}

//random() subset make from ainary array subset by those
//way. If element is presented - remove it, if element
//is absent - insert it.
template<class Item>
SubSet<Item>&
SubSet<Item>::random()		// This is not random; it's complement!  JWB
{ int size=original->size();
  for ( int i=0; i<size; i++ )
      if ( !subset[i] ) subset[i]=1;
      else subset[i]=0;
  return *this;
} 


//first subset is empty set
template <class Item>
void
SubSet<Item>::clear()
{ int size=original->size();
  for ( int i=0; i<size; i++ ) subset[i]=0;
}

	
//last subset is original set
template <class Item>
void
SubSet<Item>::fill()
{ int size=original->size();
  for ( int i=0; i<size; i++ ) subset[i]=1;
}



//rank of subset is integer which culculate from binary
//array, as binary numerous convert into integer.
template<class Item>
int
SubSet<Item>::rank() const
{ int rank=0;
  int size=original->size();
  for ( int i=0; i< size; i++)
         if ( subset[i] ) rank+=1<<i;
//it is the formula for(i=0;i<size;i++) 
//   rank=rank+ bin[i]*(2^i) - using "shift  left" 
  return rank;
}

//unrank culculate by converting integer in binary
//form and assing it to binary array
template <class Item>
SubSet<Item>&
SubSet<Item>::unrank( int rank )
{ int r;
  int size=original->size(); 
  if ( (rank<0) || ( rank>=(1<<size)) ) 
     error("Rank is out of range");
  else r=rank;
  for ( int i=0; i<size; i++ )
  {  if ( (r % 2) == 1 )  subset[i]=1; else subset[i]=0;
     r=r>>1;  //this means r/2.
  }
  return *this;
}

//next() is binary numerius  +1. Next for the last is first
template<class Item>
SubSet<Item>&
SubSet<Item>::next()
{ int i=0;
  int size=original->size();
  while( (i<size) && ( subset[i] ) )
       { subset[i]=0; i++ ; }
  if ( i<size ) subset[i]=1;
  return *this;
}


//previous() is binary numerous -1. Previous for the first
//is last.
template<class Item>
SubSet<Item>&
SubSet<Item>::previous()
{ int i=0;
  int size=original->size();
  while( (i<size) && ( !subset[i] ) )
       { subset[i]=1; i++ ; }
  if ( i<size ) subset[i]=0;
  return *this;
}

//make set which is the unions of two subset, which has
//equal original sets.
template<class Item>
SubSet<Item>
SubSet<Item>::unions( SubSet<Item>& sb) const
{  
	if (*original == *(sb.original)) { 
   		SubSet<Item> result(*this);
   		int size=original->size();
   		for(  int i=0; i<size; i++) {
       			if ( subset[i] || sb.subset[i] ) 
				result[i]=1;
       			else  
				result[i]=0;
		}
   		return result;
   	} else 
		error("Subsets must have equal original sets");
}


//make set which is the intersection of two subset,which has
//equal original sets.
template<class Item>
SubSet<Item>
SubSet<Item>::intersection(  SubSet<Item>& sb) const
{  
	if (*original == *(sb.original)) { 
		SubSet<Item> result(*this);
     		int size=original->size();
     		for( int i=0; i<size; i++) {
       			if ( subset[i] && sb.subset[i] ) 
				result[i]=1;
       			else 
				result[i]=0;
		}
		return result;
	} else 
		error("Subsets must have equal original sets");
}

//make set which is the difference of two subset, which has
//equal original sets.
template<class Item>
SubSet<Item>
SubSet<Item>::difference(  SubSet<Item>& sb ) const
{  
	if (*original == *(sb.original)) {  
		SubSet<Item> result(*this);
      		int size=original->size();
      		for( int i=0; i<size; i++) {
       			if ( subset[i] && !sb.subset[i] ) 
				result[i]=1;
       			else 
				result[i]=0;
		}
      		return result;
   	} else 
		error("Subsets must have equal original sets");
}

//operator + is unions
template<class Item>
SubSet<Item>
SubSet<Item>::operator+(  SubSet<Item>& sb ) const
{ return( unions(sb));  }

//operator ^ is intersection
template<class Item>
SubSet<Item>
SubSet<Item>::operator^(  SubSet<Item>& sb ) const
{ return( intersection(sb));  }

//operator - is difference
template<class Item>
SubSet<Item>
SubSet<Item>::operator-(  SubSet<Item>& sb ) const
{ return( difference(sb));  }


//order is the size of the original set.
template<class Item>
int
SubSet<Item>::order() const
{ return( original->size() ); }


template<class Item>
SubSet<Item>&
SubSet<Item>::operator=( const SubSet<Item>& sb)
{ delete original; delete [] subset;
  original = new Set<Item>(*(sb.original));
  int size=sb.order();
  subset=new Bool[size];
  for ( int i=0; i<size; i++)
      subset[i]=sb.subset[i];
  return *this;
}

template <class Item>
Bool
SubSet<Item>::operator==(const SubSet<Item>& sb) const
{ if (*original ==  *(sb.original))
   { int i=this->order()-1; //bigin from the end
 //    cout<<"size="<<i<<endl;
     while( (subset[i]==sb.subset[i]) && (i>=0) ) i--;
     if ( i<0) return TRUE;
     else return FALSE;
    }
   else 
    {  warning("Subsets must have equal original sets");
       return FALSE;
    }
}


template <class Item>
Bool
SubSet<Item>::operator!=(const SubSet<Item>& sb) const
//{ return !operator==(sb); }
{ if ( *this == sb ) return FALSE;else return TRUE; }

template <class Item>
Bool
SubSet<Item>::operator>(const SubSet<Item>& sb) const
{  if (*original ==  *(sb.original))
   { int i=this->order()-1; //bigin from the end
     while( (subset[i]==sb.subset[i]) && (i>=0) ) i--;
     if ( i<0) return FALSE;
     else
     { if ( subset[i]>sb.subset[i]) return TRUE;
       else return FALSE;
     }
   }
   else 
    { warning("Subsets must have equal original sets");
      return FALSE;
    }
}


template <class Item>
Bool
SubSet<Item>::operator<=(const SubSet<Item>& sb) const
{ return !operator>(sb) ; }
//{ if ( *this > sb ) return FALSE; else return TRUE; }

template <class Item>
Bool
SubSet<Item>::operator<(const SubSet<Item>& sb) const
{  if (*original == *(sb.original))
   { int i=this->order()-1; //bigin from the end
     while( (subset[i]==sb.subset[i]) && (i>=0) ) i--;
     if ( i<0) return FALSE;
     else
     { if ( subset[i]<sb.subset[i]) return TRUE;
       else return FALSE;
     }
   }
   else 
    { warning("Subsets must have equal original sets");
      return FALSE;
    }
}

template <class Item>
Bool
SubSet<Item>::operator>=(const SubSet<Item>& sb) const
{ return !operator<(sb); }
//{ if (*this<sb) return FALSE; else return TRUE; }

template<class Item>
Bool
SubSet<Item>::subsetQ( SubSet<Item>& sb )
{
 return TRUE;
}


template<class Item>
Bool
SubSet<Item>::properSubsetQ( SubSet<Item>& sb )
{
 return TRUE;
}


template<class Item>
Bool&
SubSet<Item>::operator[]( int index ) const
{ if ( (index<=0) || (index>this->order()) ) {
  	warning("Index is out of the range");
	static Bool b;
	return b;
  }
  return subset[index];
}



template <class Item>
Set<Set<Item> >
SubSet<Item>::powerSet()
{
	int i;
	Set<Set<Item> > res;
	int max_rank = (int) pow(2, original->size());
        clear();
        for (i=0; i < max_rank; i++) {
		Set<Item> ms = makeSet();
		//cout << ms << endl;
		res.insert(ms);
		next();
	}
	return res;
}

template <class Item>
Set<Set<Item> >
SubSet<Item>::choose(int k)
{
	return SetFuncs<Item>::choose(*original, k);
}



template <class Item> ostream& operator<<(ostream& os, const SubSet<Item>&ss)
{ 
	ss.display(os); return os; 
}