// File: Set_ADT.cpp
// Implementations for set of objects ADT

#include "Set_ADT.h"

 // Initialize Set to Empty
 template <typename eltType> SetADT<eltType>::SetADT()
 {Elts=0; ListOfElts=NULL;}

 // Add Item to Set
 // Pre: None
 // Post: If Elt already in set, size of set unchanged, otherwise
 //	set has cardinality increase by 1
 // Returns: 0=> Elt already in Set   1=> Elt added to Set
 template <typename eltType> int SetADT<eltType>::addElt(eltType Elt)
 {if (orderedSearch(ListOfElts,Elts,Elt)>=0)
   return(0);
  if (!Elts)
   ListOfElts=new eltType[1];
  else
   ListOfElts=(eltType *)realloc(ListOfElts,(Elts+1)*sizeof(eltType));
  ListOfElts[Elts++]=Elt;
  selSort(ListOfElts,Elts);
  return(1);
 }

 // Remove Item From Set
 // Pre: None
 // Post: If Elt not in set, size of set unchanged, otherwise
 //	set has cardinality decrease by 1
 // Returns: 0=> Elt not in Set   1=> Elt Removed From Set
 template <typename eltType> int SetADT<eltType>::removeElt(eltType Elt)
 {int Index;
  if ((Index=orderedSearch(ListOfElts,Elts,Elt))<0) return(0);
  ListOfElts[Index]=ListOfElts[Elts-1];
  if (!(--Elts)) {
   delete ListOfElts;
   ListOfElts=NULL;
  }
  else ListOfElts=(eltType *)realloc(ListOfElts,Elts*sizeof(eltType));
  selSort(ListOfElts,Elts);
  return(1);
 }

 // Return # Elts in Set
 // Pre: None
 // Post: Set Unchanged
 // Returns: Cardinality of Set
 template <typename eltType> int SetADT<eltType>::cardinality() const
 {return Elts;}


 // Determine if an element is a member of the set
 // Pre: None
 // Post: Set Unchanged. Result dependent on argument membership
 // Returns: 0=> Elt not in Set   1=> Elt in Set
 template <typename eltType> 
	 int SetADT<eltType>::operator >(eltType Elt)
 {if (orderedSearch(ListOfElts,Elts,Elt)<0) return(0);
  return(1);
 }

 // Friends that perform normal set operations

 // Return Union of 2 Sets
 // Pre: None
 // Post: Returns union of argument SetADTs with no repitition of elements
 // Resulting set is ordered
 template <typename eltType> 
	 SetADT<eltType>  SetADT<eltType>::operator+(SetADT<eltType> right)
 {SetADT<eltType> Result;
  int Index;
  for (Index=0;Index<cardinality();Index++) {
   if (right>ListOfElts[Index])
    right.removeElt(ListOfElts[Index]);
   Result.addElt(ListOfElts[Index]);
  }
  for (Index=0;Index<right.cardinality();Index++) {
   Result.addElt(right.ListOfElts[Index]);
  }
  selSort(Result.ListOfElts,Result.cardinality());
  return(Result);
 }


 // Return Intersection of 2 Sets
 // Pre: None
 // Post: Returns intersect of argument SetADTs
 template <typename eltType> 
	 SetADT<eltType>  SetADT<eltType>::operator *(SetADT<eltType> right)
 {SetADT<eltType> Result;
  int Index;
  for (Index=0;Index<cardinality();Index++)
   if (right>ListOfElts[Index])
    Result.addElt(ListOfElts[Index]);
  selSort(Result.ListOfElts,Result.cardinality());
  return(Result);
 }


 // Return Set Difference - Elts that are in 1st Set but not 2nd
 // Pre: None
 // Post: Returns difference of argument SetADTs
 template <typename eltType> 
	 SetADT<eltType> SetADT<eltType>::operator-(SetADT<eltType> right)
 {SetADT<eltType> Result;
  int Index;
  for (Index=0;Index<cardinality();Index++)
   if (!(right>ListOfElts[Index]))
    Result.addElt(ListOfElts[Index]);
  selSort(Result.ListOfElts,Result.cardinality());
  return(Result);
 }


 // Print the set
 // Pre:None
 // Post:None
 template <typename eltType> 
	 ostream &operator<<(ostream &out,SetADT<eltType> Set)
 {out << "Elements in the set are:\n";
  for (int i=0;i<Set.cardinality();i++)
   out << Set.ListOfElts[i] << endl;
  return(out);
 }

// Need to explicitly instantiate for our application...
template class SetADT<int>;
template ostream &operator<<(ostream &out,SetADT<int> Set);