// Set.H

// Developed from intSet.h (JR 7/2/95).

// 10/25/95  Noticed problem that when card is changed,
//    an iterator or browsers don't get the news!
//    Rewrote iterator and browser to use a ref
//    to the Set instead of their own copies of Set info.
// 12/08/95  Added contains(),clear().
// 1/1/96   Made cardinality() and isEmpty() const.
// 3/5/96    Found only declaration of contains(),
//    not implementation. Implemented it.
//    clear() is not even declared! Hmmm.
//    Added operators == and !=.
//      3/7/96 When we call add() etc., do we expect the reference
//             we pass as an argument to be valid after the call? And will it
//             be, necessarily? Answer is no! (Add may cause reallocation.)
// 3/28/96   Added removeOne().
//           Added clear().
//    In remove(T& t), should put in check for case that t
//    is not a reference to the thing being removed. 
// 4/7/96   Added istream& operator>> .

#ifndef SET_H
#define SET_H

#include <assert.h>
//#include <iostream.h>
#include <iostream>
using namespace std;

template <class T>
class SetBrowser;
template <class T>
class SetIterator;


//const default_block_size=5;
const int default_block_size=5;    // Dec 15, 2002  (How did I get away with that previously??


// 2006_02_22 ///////////////////////////////////////////////////
// Added to allow compilation with g++ version 3.4.4
template <class T>
class Set;
template <class T>
ostream& operator << (ostream& out, const Set<T>& s);
template <class T>
istream& operator>>(istream& in,Set<T>& L);
// 2006_02_22 //////////////////////////////////////////////////


template <class T>
class Set
{

   friend class SetBrowser<T>;
   friend class SetIterator<T>;

   public:
      Set()
      {   alloc_block_size=default_block_size;
          array = new T [alloc_block_size];
          current_size=alloc_block_size;
          card=0;
      }
      Set(const Set<T>& s);
      Set(const T& t)
      {   alloc_block_size=default_block_size;
          array = new T [alloc_block_size];
          current_size=alloc_block_size;
          array[0]=t;
          card=1;
      }
      Set(const T* inputarray, const int& n);
     ~Set()
      {
         delete[] array;
      }
      Set<T>& operator=(const Set<T>& s);
      int add(const T& t);
      int remove(const T& t);
      T   removeOne();
      int has(const T& t) const;
      int setBlockSize(int b);
      int cardinality() const
      {   return card; }
      int isEmpty() const
      {   return card==0; }
      friend ostream& operator << <> (ostream& out, const Set<T>& s);
      friend istream& operator>> <> (istream& in,Set<T>& s);	

      Set<T>& operator-=(const Set<T>& s);
      Set<T>& operator+=(const Set<T>& s);

      int intersects(const Set<T>& s) const;
      Set<T> intersection(const Set<T>& s) const;
      Set<T> setunion(const Set<T>& s) const;
      int contains(const Set<T>& s) const;
      int operator==(const Set<T>& s) const;
      int operator!=(const Set<T>& s) const;

      void clear()
      {
	  delete[] array;
          array = new T [alloc_block_size];
          current_size=alloc_block_size;
          card=0;
      }

   private:
      T* array;
      int card;
      int current_size;
      int alloc_block_size;

};


template <class T>
class SetBrowser
{
   private:
	const Set<T>& set;
	int  offset;

   public:
//	SetBrowser()
//	{
//	}
	SetBrowser(const Set<T>& s)
	: set(s), offset(0)
	{}
       ~SetBrowser()
	{}
	void init()
	{	
		offset=0;
	}
	int ok()
	{
		return offset<set.card;
	}
	void advance()
	{	
		offset++;
	}
	const T& current() const;

};


template <class T>
class SetIterator	// Differs from Browser only in the non-const
			// reference returned by current().
{
   private:
	Set<T>& set;
	int  offset;

   public:
	SetIterator(Set<T>& s)
	: set(s), offset(0)
	{}
       ~SetIterator()
	{}
	void init()
	{	
		offset=0;
	}
	int ok()
	{
		return offset<set.card;
	}
	void advance()
	{	
		offset++;
	}
	T& current();

};




// Set.C

// JR 7/2/95


#include <stdlib.h>
#include <stdio.h>


      template <class T>
      Set<T>::Set(const Set<T>& s)
      {   alloc_block_size=default_block_size;
          current_size=alloc_block_size*(s.card/alloc_block_size + 1);
          array = new T [current_size];
          for(int i=0;i<s.card;i++) array[i]=s.array[i];
          card = s.card;
      }
      template <class T>
      Set<T>::Set(const T* inputarray, const int& n)
      {   // New set initialized from array
          alloc_block_size=default_block_size;
          array = new T [n];
          current_size=n;
          for(int i=0;i<n;i++) array[i]=inputarray[i];
          card=n;
      }

      template <class T>
      Set<T>& Set<T>::operator=(const Set<T>& s)
      {   if(s.card>current_size)
          {   delete[] array;
              array = new T [current_size=s.current_size];
          }
          card=s.card;
          for(int i=0;i<s.card;i++) array[i]=s.array[i];
          return *this;
      }
      template <class T>
      int Set<T>::add(const T& t)
      {   int alreadyIn=0;
          for(int i=0;i<card;i++) if(array[i]==t) { alreadyIn=1; break; }
          if(alreadyIn) return 0;
          if(card==current_size) // more memory needed
          {   T* tmp = new T [current_size+alloc_block_size];
              for(int i=0;i<card;i++) tmp[i]=array[i];
              current_size+=alloc_block_size;
              delete[] array;
              array=tmp;
          }
          array[card++]=t;
          return 1;
      }
      template <class T>
      int Set<T>::remove(const T& t)
      {   int notIn=1;
          for(int i=0;i<card;i++) if(array[i]==t) { notIn=0; break; }
          if(notIn) return 0;
          // delete item at index i
          for(int j=i;j<card-1;j++) array[j]=array[j+1];
          card--;
          return 1;
      }
      template <class T>
      T Set<T>::removeOne()
      {   
	  assert(card!=0);
	  T tmp=array[card-1];
          card--;
          return tmp;
      }
      template <class T>
      int Set<T>::has(const T& t) const
      {   for(int i=0;i<card;i++) if(array[i]==t) return 1;
          return 0;
      }
      template <class T>
      int Set<T>::setBlockSize(int b)
      {   if(b<1) { cout << "Illegal blocksize:" << b << '\n'; return 0;}
          alloc_block_size=b;
          return 1;
      }
      template <class T>
      int Set<T>::intersects(const Set<T>& s) const
      {
          int i,j;
          for(i=0;i<card;i++)
             for(j=0;j<s.card;j++) if(array[i]==s.array[j]) return 1;
          return 0;
      }

      template <class T>
      Set<T>& Set<T>::operator-=(const Set<T>& s)
      {   // Regular algorithm won't work for "a-=a;"
	  if(array==s.array)
	  {	delete[] array;
		current_size=0;
		card=0;
		return *this;
	  }
	  // remove any elements that are also in s
          for(int i=0;i<s.card;i++) remove(s.array[i]);
          return *this;
      }
      template <class T>
      Set<T>& Set<T>::operator+=(const Set<T>& s)
      {   // add elements of s not already present
          for(int i=0;i<s.card;i++) add(s.array[i]);
          return *this;
      }


      template <class T>
      int Set<T>::contains(const Set<T>& s) const
      {	
	  SetBrowser<T> j(s);
	  for(j.init();j.ok();j.advance())
		if( ! has( j.current() ) ) return 0;
	  return 1;
      }

      template <class T>
      Set<T> Set<T>::intersection(const Set<T>& s) const
      {	  // return the intersection
          Set<T> tmp(s);
	  SetBrowser<T> j(s);
	  for(j.init();j.ok();j.advance())
		if( ! has( j.current() ) ) tmp.remove(j.current());
	  return tmp;
      }

      template <class T>
      Set<T> Set<T>::setunion(const Set<T>& s) const
      {	  // return the union
          Set<T> tmp(*this);
	  SetBrowser<T> j(s);
	  for(j.init();j.ok();j.advance()) tmp.add(j.current());
	  return tmp;
      }

      template <class T>
      int Set<T>::operator==(const Set<T>& s) const
      {
          return (((*this).contains(s)) && (s.contains(*this)));
      }

      template <class T>
      int Set<T>::operator!=(const Set<T>& s) const
      {
          return !(((*this).contains(s)) && (s.contains(*this)));
      }

      template <class T>
      ostream& operator << (ostream& out, const Set<T>& s)
      {   out << "{ ";
	  for(int i=0;i<s.card;i++) out << s.array[i] << " ";
          out << "}";
	  return out;
      }
	
	template <class T>
	istream& operator>>(istream& in,Set<T>& L)
	{
		L.clear();
  int c;
  T tmp;
  while ( (c=in.get()) != '{' )
  {}
  while(in)
  {
   while((c=in.get()) == ' ' || c==',' || c=='\n' )
   {}
   if(  c== '}' ) return in;
   in.putback(c);
   in >> tmp;
   L.add(tmp);
  }
 }

      template <class T>
      const T& SetBrowser<T>::current() const
      {
   if( offset>=0 && offset<set.card )
              return set.array[offset];

             cout << "Nonexistent element requested" << endl;
  cout << "   offset = " << offset << " , set.card = " << set.card << endl;
  assert(0);
      }

      template <class T>
      T& SetIterator<T>::current()
      {
   if( offset>=0 && offset<set.card )
              return set.array[offset];
          else
              cout << "Nonexistent element requested" << endl;
cout << "offset = " << offset << endl;
cout << "Set is " << set << endl;
   assert(0);
      }

#endif