CS 201 - 11/11/14

Sets as a data structure
  - could store in a dynamic array, linked list,
       or in a hash table.

  most often an application using sets needs multiple
     set to be maintained.


  a data item may need to know to which set it belongs.
   to complicate matters, a data item may belong to 
   multiple sets

   when two sets overlap, what is the best way to 
      represent that data?

   A single data item may exist multiple times in
      our "set space".


   We may implement, a list of sets that each item
     is a member of.

   Each set normally allows the following operations
     - isEmpty()
     - add()
     - remove()
     - isMemberOf()
     - access()
     - update()  ???   more an operation on the data item
                         and not on the set itself
     - clear()
     - listAll()

   What operations might be performs on the entire set
      or on multiple sets?

      - union()
      - intersection()
      - setDifference()
      - inverseOfASet()
      - isSubSetOf()
      - isSupersetOf()

  Set  intersection (Set a, Set b)
     {
       Set c;
       clear (c);

       forAll ( dataItem in a)
          if ( memberOf( dataItem, b) == true)
             add (dataItem,  c);

       return c;
    }

   The "Set" would be made up of multiple dataItems
       of the same "type"

   Sometimes we may need to implement a "partial set"
      - particularly when we are working with
         infinite sets (i.e. set of prime numbers)

      - while partial may contain a list of data
          items, they may also contain functions
          that calculate a memberOf operation.
---------------------------------------------

Let us assume we have a linked list structure
    that maintains a single list of data items.

struct Node
  {
    int data;
    /* other data items */
    struct Node* next;
  }

A pointer to struct Node would be the head of the
    list of data items, i.e:
 
        struct Node* head;


How do we create a collection of lists?

  - each list needs to be identifiable 


   We can create a linked list of "identifiable header
      pointers"


struct  SetData
  {
    char name[40];
    struct Node* head;
    struct SetData* nextSD;
  };


typedef structSetData sdtype;

int main()
{
   sdtype* setLists;