/*    SsetLib.c    */
/*  Impliments the set library with no
    dynamic allocation.                */


#include <stdio.h>
#include "SsetLib.h"


int look[256] = 
   {
     0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
     1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
     2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
     3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
    };

/* ******** Initialization ******** */

void SetEmpty (set S)
/* postcondition: S={} */
{
  int i;
  for (i=0; i<WORDS; i++)
    S[i] = (unsigned int) 0;
}

/* ********* Input/Output ********* */

void SetToScreen (set S)
{
  int i;
  for (i=0; i<WORDSIZE*WORDS; i++)
  {
    if (MemberOfSet(i,S))
      printf(" %d ",i);
  }
  printf("\n \n");
}

/* ************ Tests ************* */

int MemberOfSet (int u, set S)
{
  int i;
  unsigned int j;
  j = WORDSIZE - 1 - (u % WORDSIZE);
  i = u/WORDSIZE;
  if (S[i] & ((unsigned int)1<<j))
  {
    return 1;
  }
  else
  {
    return 0;
  }
}

int SetOrder (set S)
{
  int i;
  int order;
  unsigned int x;
  order = 0;
  for (i=0; i<WORDS; i++)
  {
    x = S[i];
    while (x)
    {
	order += look[x & (unsigned int)0377];
	x >>= (unsigned int) 8;
    }
  }
  return (order);
}

int IntersectTest(set S, set T)
/* returns true (1) if the intersection of
S and T is nonempty, otherwise returns false (0) */
{
  int i;
  for (i=0; i<WORDS; i++)
    if (S[i] & T[i])
      return (1);
  return (0);
}

/* ********** Operations ********** */

void SetInsert (int u, set S)
{
  int i;
  unsigned int j;
  j = WORDSIZE - 1 - (u % WORDSIZE);
  i = u/WORDSIZE;
  S[i] = S[i] | ((unsigned int) 1<<j);
}

void SetDelete (int u, set S)
/* postcondition:  element u is deleted from S */
{
  int i;
  unsigned int j;
  j = WORDSIZE - 1 - (u % WORDSIZE);
  i = u/WORDSIZE;
  S[i] = S[i] & ~((unsigned int) 1<<j);
}

void SetUnion (set S, set T, set A)
/* postcondition: A contains S union T */
{
  int i;
  for (i=0; i<WORDS; i++)
    A[i] = S[i] | T[i];
}

void SetIntersection (set S, set T, set A)
{
  int i;
  for (i=0; i<WORDS; i++)
    A[i] = S[i] & T[i];
}

void GetSet (set S, set T)
/* postcondition:  S contains T */
{
  int i;
  for (i=0; i<WORDS; i++)
  {
    S[i] = T[i];
  }
}