set.c

压缩包里面的都是精致的基本C语言小程序

#include <stdio.h>
#include <stdlib.h>
#include "hash.h"
#include "arrayList.h"
#include "tuple.h"
#include "nat.h"
#include "mystdlib.h"
#include "error.h"
#include "bitArray.h"
#include "str.h"
#include "error.h"
#include "set.h"

struct set
{
  hash localSet;  
};

static int counter = 0;
static hash universe = NULL;
static arrayList array = NULL;

set newSet ()
{    
  set s = checkedMalloc (sizeof (*s));
  s->localSet = newHash ();
  
  return s;
}

void setInitializeGlobal ()
{
  universe = newHash ();
  array = newArrayList ();
}

void universeStatus ()
{
  hashStatus (universe);
  return;
}

void setInsertUniverse (poly data)
{ 
  int i = counter++;
  nat n = newNat (i);
    
  hashInsert (universe, data, n);
    
  arrayListInsert(array, data, i);
  
  return;
}

void setInsert (set s, poly data)
{
  poly value = hashLookup (universe, data);
  
  if (!value)
  {
    exception ("value not found in universe: ");
    strOutput (getVft (data)->toString (data));
    printf ("\n");
  }
  else;
    
  hashInsert (s->localSet, data, value);
  return;
}

void setOutputUniverse ()
{  
  printf ("the set is:\n");
  
  for (int i=0; i<hashSize (universe); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (universe, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      strOutput (tupleToString (t));
      list1 = list1->next;
    }
  }  
  printf ("the array is:\n");
  
  arrayListOutput (array);
  
  return;
}

void setOutput (set s)
{  
  if (!s->localSet)
    exception ("empty local hash table\n");
    
  for (int i=0; i<hashSize (s->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s->localSet, i));

    while (list1)
    {
      tuple t = (tuple)(list1->data);
      strOutput (tupleToString (t));
      list1 = list1->next;
    }
  }

  return;
}

void setOutput2 (set s)
{
  if (!s->localSet)
    exception ("empty local hash table\n");
  
  printf ("{");
  
  for (int i=0; i<hashSize (s->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s->localSet, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      poly p = tupleFirst (t);
      strOutput (getVft (p)->toString (p));
      printf (", ");
      list1 = list1->next;
    }
  }
  printf ("}");
  
  return;
}

poly setLookup2 (set s, poly data)
{
  
  if (!s->localSet)
    exception ("empty local hash table\n");
    
  for (int i=0; i<hashSize (s->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s->localSet, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      poly p = tupleFirst (t);
      int flag = getVft (p)->equals (data, p);
      if (flag)
        return p;
        
      list1 = list1->next;
    }
  }
  
  return NULL;
}

set setUnion (set s1, set s2)
{
  int size = hashNumItems (universe);
  bitArray ba1 = newBitArray (size);
  bitArray ba2 = newBitArray (size);

  for (int i=0; i<hashSize (s1->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s1->localSet, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      int index = natToInt ((nat)(tupleSecond (t)));
      bitArrayChangeBit (ba1, index);
      list1 = list1->next;
    }
  }
  
  for (int i=0; i<hashSize (s2->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s2->localSet, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      int index = natToInt ((nat)(tupleSecond (t)));
      bitArrayChangeBit (ba2, index);
      list1 = list1->next;
    }
  }

  
  bitArrayOutput (ba1);
  printf("bitarray of set2");
  bitArrayOutput (ba2);
  printf("bitarray of set3");

  bitArray ba3 = bitArrayOr (ba1, ba2);
  bitArrayOutput (ba3);


  set s = newSet ();
  int i;

  for (i=0; i<size; i++)
  {
    if (bitArrayGetBit (ba3, i))
    {
      setInsert (s, arrayListLookup(array, i));
    }
  }
    
  bitArrayDestroy (ba1);
  bitArrayDestroy (ba2);
  bitArrayDestroy (ba3);
  
  return s;
}

set setIntersection (set s1, set s2)
{
  int size = hashNumItems (universe);
  bitArray ba1 = newBitArray (size);
  bitArray ba2 = newBitArray (size);
 
  for (int i=0; i<hashSize (s1->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s1->localSet, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      int index = natToInt ((nat)(tupleSecond (t)));
      bitArrayChangeBit (ba1, index);
      list1 = list1->next;
    }
  }
  
  for (int i=0; i<hashSize (s2->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s2->localSet, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      int index = natToInt ((nat)(tupleSecond (t)));
      bitArrayChangeBit (ba2, index);
      list1 = list1->next;
    }
  }
//  bitArrayOutput (ba1);
//  bitArrayOutput (ba2);
  
  bitArray ba3 = bitArrayAnd (ba1, ba2);
  
//  bitArrayOutput (ba3);
  
  set s = newSet ();
  int i;

  for (i=0; i<size; i++)
  {
    //printf ("i=%d\n", i);
    if (bitArrayGetBit (ba3, i))
    {
      setInsert (s, arrayListLookup(array, i));
    }
  }

  bitArrayDestroy (ba1);
  bitArrayDestroy (ba2);
  bitArrayDestroy (ba3);
  
  return s;
}

set setComplement (set s)
{
  int size = hashNumItems (universe);
  bitArray ba1 = newBitArray (size);
      
  for (int i=0; i<hashSize (s->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s->localSet, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      int index = natToInt ((nat)(tupleSecond (t)));
      bitArrayChangeBit (ba1, index);
      list1 = list1->next;
    }
  }
 
//  bitArrayOutput (ba);
  
  bitArray ba2 = bitArrayNegation (ba1);
  
//  bitArrayOutput (ba2);
  
  set sss = newSet ();
  int i;

  for (i=0; i<size; i++)
  {
    if (bitArrayGetBit (ba2, i))
    {
      setInsert (sss, arrayListLookup(array, i));
    }
  }
  
  bitArrayDestroy (ba1);
  bitArrayDestroy (ba2);

  return sss;
}

void setInsert2 (set s, poly data)
{
  poly value = NULL;
  
  if (setLookup2 (s, data))
    return;
    
  hashInsert (s->localSet, data, value);
  return;
}


set setUnion2 (set s1, set s2)
{
  set s = newSet ();
  
  for (int i=0; i<hashSize (s1->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s1->localSet, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      poly key = (tupleFirst (t));
      setInsert2 (s, key);
      list1 = list1->next;
    }
  }
  
  for (int i=0; i<hashSize (s2->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s2->localSet, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      poly key = (tupleFirst (t));
      setInsert2 (s, key);
      list1 = list1->next;
    }
  }
  
  return s;
}

int setSize (set s)
{
  return hashNumItems (s->localSet);
}

linkedList setToLinkedList2 (set s)
{
  linkedList l = newLinkedList ();
  
  for (int i=0; i<hashSize (s->localSet); i++)
  {
    linkedList list1 = linkedListGetFirst (hashChain (s->localSet, i));
    while (list1)
    {
      tuple t = (tuple)(list1->data);
      poly key = (tupleFirst (t));
      linkedListInsertHead (l, key);
      list1 = list1->next;
    }
  }
  
  return l;
}