/* This file contains the implementation for class Set.

-----------------------------------------------------------------*/

#include "Set.h"

#include <stdarg.h>

/* This function constructs a Set as the empty set.

   Precondition:  A Set has been defined with no arguments.
   Postcondition: That Set is initialized as an empty set.
--------------------------------------------------------------------*/

Set::Set(void)
{                                // initialize Array as an empty set
   for (int i = 0; i < Set::ArrayLength; i++)
      Array[i] = 0;
}

/* This function constructs a Set from a list of Set elements.

--------------------------------------------------------------------*/

Set::Set(unsigned Num, ...)
{
   if (Num == MaxElements)
   {
      for (int i = 0; i < Set::ArrayLength; i++)
         Array[i] = long(0xffffffff);
      return;
   }

   for (int i = 0; i < Set::ArrayLength; i++)
      Array[i] = 0;

   va_list args;
   va_start(args,Num);

   for (i = 0; i < Num; i++) {

      unsigned
         Elem = va_arg(args,unsigned);

      int
         Index = Elem / Set::BitsPerEntry;      // find index of Elem

      if (Index >= Set::ArrayLength)            // if it's invalid
      {                                         //   display error msg
         cerr << "\n*** Set: Set is too small to hold "
              << Elem << endl;
      }

      int
         BitPosition = Elem % Set::BitsPerEntry;// find the bit to set

      long
         Mask = 1;                              // 31 0s and a 1.

      Mask = Mask << BitPosition;               //   left-shift the mask

      Array[Index] |= Mask;                     // see if the bit is 1

      }

   va_end(args);
}

/* This function returns the union of two Set objects.

   Receive: S1 and S2, two Set objects
   Return:  The union of S1 and S2
----------------------------------------------------------*/

Set operator+(const Set& S1, const Set& S2)
{
   Set
      Result;

   for (int i = 0; i < Result.ArrayLength; i++)
      Result.Array[i] = S1.Array[i] | S2.Array[i];

   return Result;
}

/* This function returns the insersection of two Set objects.

   Receive: S1 and S2, two Set objects
   Return:  The intersection of S1 and S2
--------------------------------------------------------------*/

Set operator*(const Set& S1, const Set& S2)
{
   Set
      Result;

   for (int i = 0; i < Set::ArrayLength; i++)
      Result.Array[i] = S1.Array[i] & S2.Array[i];

   return Result;
}

/* This function returns the difference of two Set objects.

   Receive: S1 and S2, two Set objects
   Return:  The difference of S1 and S2
----------------------------------------------------------*/

Set operator-(const Set& S1, const Set& S2)
{
   Set
      Result = S1,
      CommonSet = S1 * S2;

   for (int i = 0; i < Set::ArrayLength; i++)
      Result.Array[i] ^= CommonSet.Array[i];

   return Result;
}

/* This function performs the set membership operation.

   Receive: Elem, an element.
   Return:  True if Elem is a member of the Set containing
              this function and False otherwise.
-----------------------------------------------------------*/

Boolean Set::Contains(unsigned Elem) const
{
   int
      Index = Elem / Set::BitsPerEntry;      // find index of Elem

   if (Index >= Set::ArrayLength)            // if it's invalid
   {                                         //   display error msg
      cerr << "\n*** Contains: Set is too small to hold "
           << Elem << endl;
      return False;                          // indicate failure
   }

   int
      BitPosition = Elem % Set::BitsPerEntry;// find the bit to set

   long
      Mask = 1;                              // 31 0s and a 1.

   Mask = Mask << BitPosition;               //   left-shift the mask

   return (Array[Index] & Mask) != 0;        // see if the bit is 1
}

/* This function inserts an element into a Set.

   Receive: Elem, a set element
   Return:  The Set containing this function, with Elem as a
              member
            True if successful and False otherwise
------------------------------------------------------------------*/

Boolean Set::Insert(unsigned Elem)
{
   int
      Index = Elem / Set::BitsPerEntry;       // find index for Elem

   if (Index >= Set::ArrayLength)             // if it's invalid
   {                                          //   display error msg
      cerr << "\n*** Insert: Set is too small to hold "
           << Elem << endl;
      return False;                           // indicate failure
   }

   int
      BitPosition = Elem % Set::BitsPerEntry;// find the bit to set

   long
      Mask = 1;                              // the mask to set it

   if (BitPosition > 0)                      // if not the first bit
      Mask <<= BitPosition;                  //   left-shift the mask

   Array[Index] |= Mask;                     // set the bit

   return True;                              // indicate success
}

/* This function removes an element from a Set.

   Receive: Elem, a set element
   Return:  The Set containing this function, without Elem as a
              member
            True if successful and False otherwise
------------------------------------------------------------------*/

Boolean Set::Delete(unsigned Elem)
{
   int
      Index = Elem / Set::BitsPerEntry;       // find index for Elem

   if (Index >= Set::ArrayLength)             // if it's invalid
   {                                          //   display error msg
      cerr << "\n*** Delete: Set is too small to hold "
           << Elem << endl;
      return False;                           // indicate failure
   }

   int
      BitPosition = Elem % Set::BitsPerEntry;// find the bit to set

   long
      Mask = 1;                              // the mask to set it

   if (BitPosition > 0)                      // if not the first bit
      Mask <<= BitPosition;                  //   left-shift the mask

   Array[Index] &= (~Mask);                  // clear the bit

   return True;                              // indicate success
}

/* This function provides stream output for a Set.

------------------------------------------------------------------*/

ostream& operator<<(ostream& Out, const Set& S)
{
   for (unsigned Elem = 0; Elem < Set::MaxElements; Elem++)
   {
      if (S.Contains(Elem))
         Out << Elem << ' ';
   }

   return Out;
}