/* BigSet package, Copyright (C) 2002, Tim McLarnan

This program is free software; you can redistribute it and/or
modify it under the terms of the GNU General Public License
as published by the Free Software Foundation; either version 2
of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.

Do, please, let me hear from you if you use this package, or if you
have questions.

Tim McLarnan, Dept. of Mathematics, Earlham College, Richmond, IN 47374 USA
timm AT cs.earlham.edu

*/


/*
  BigSet package, Tim McLarnan, 12/28/1999,
  BigSetPlaceUnion and BigSetPlaceIntersection added 1/15/2000, TJMcL.
  modified 1/21/2000 to store sets as arrays of chars, not arrays of bits.
  modified 7/10/2000 so functions using malloc return ints to signal
  success or failure, and to eliminate functions unused in the
  weaving program.
 
  BigSets are structs modeling sets of arbitrary size.
  The set theoretic operations on BigSets assume that all the sets
  we are working with have a common universal set,
  {0, 1, 2, ... , universe-1}.
 
  A BigSet contains a long giving the size of the common universe,
  together with an array of chars in which element[k] is 1 or 0
  according as k is or is not a member of the set.

  The critical thing to know about this package is that it exists for
  reasons of efficiency, not portability.  8-bit bytes and 1-byte
  characters are assumed.  There's no error checking.  The only
  functions implemented are those needed for the weaving program.
  Deal with it.  On the other hand, it's fast enough for the weaving
  program to be efficient.
*/


#include "BigSet.h"
#include <stdlib.h>


/*
  BigSetDiff, Tim McLarnan, 1/21/2000
  pre: two BigSets a, b.
  WARNING: The two sets a and b must have the same size universe.
  For efficiency, this is not checked.
  Insuring it is a programmer responsibility.
  post: returns non-0 iff a and b are different.
*/
int BigSetDiff(const BigSet a, const BigSet b) {
  return(memcmp(a.element, b.element, a.universe));
}


/*
  BigSetMakeNull, Tim McLarnan, 1/21/2000
  pre: b is a pointer to a BigSet b,
  whose size (*b).universe must have been set
  and whose element-array (*b).element must have been allocated.
  post: b is an empty set of size (*b).universe.
*/
void BigSetMakeNull(BigSet *b) {
  memset((*b).element, 0, (*b).universe);
}


/*
  BigSetMake, Tim McLarnan, 1/21/2000
              Modified 7/10/2000 to return an int.
  pre: b is a pointer to a BigSet b, max_size is the number of
  elements in the universe for this set.
  post: b is an empty set with a universe of size max_size.
  returns: 1 on success; 0 if malloc fails.
*/
int BigSetMake(BigSet *b, long max_size) {
  (*b).universe = max_size;
  if (((*b).element = (unsigned char *) malloc(max_size))) {
    BigSetMakeNull(b);
    return(1);
  } else {
    return(0);
  }
}


/*
  BigSetFree, Tim McLarnan, 1/21/2000
  pre: b is a pointer to a BigSet
  whose element-array (*b).element must have been allocated.
  post: Frees the bit-array to prevent memory leaks, and sets the size
  of the set's universe to 0.
*/
void BigSetFree(BigSet * b) {
  free((*b).element);
  (*b).universe = 0;
}


/*
  BigSetAddElement, Tim McLarnan, 1/22/2000
  pre: b is a pointer to a BigSet,
  e is an element to be added to the set.
  post: Adds e to the set b.
  returns: 1 if e was not originally in b and has been added,
           0 if e was originally in b and has not been added.
*/
int BigSetAddElement(BigSet * b, long e) {
  if ((*b).element[e] == 0) {
    (*b).element[e] = 1;
    return(1);
  } else {
    return(0);
  }
}

/*
  BigSetRemoveElement, Tim McLarnan, 1/22/2000
  pre: b is a pointer to a BigSet,
  e is an element to be removed from the set.
  post: Removes e from the set b.
  returns: 1 if e was originally in b and has been removed,
           0 if e was not originally in b and has not been removed.
*/
int BigSetRemoveElement(BigSet * b, long e) {
  if ((*b).element[e] == 1) {
    (*b).element[e] = 0;
    return(1);
  } else {
    return(0);
  }
}


/*
  BigSetElementOf, Tim McLarnan, 1/21/2000
  pre: b is a BigSet; e is a possible element of b.
  post: returns non-0 iff e is an element of b.
*/
int BigSetElementOf(BigSet b, long e) {
  return (int) (b.element[e]);
}


/*
  BigSetPlaceUnion, Tim McLarnan, 1/21/2000
  pre: a and b are BigSets; un is a pointer to a BigSet *un.
  WARNING: The sets a, b and *un must have the same size universe.
  For efficiency, this is not checked.
  Insuring it is a programmer responsibility.
  post: *un contains a union b.
*/
void BigSetPlaceUnion(BigSet a, BigSet b, BigSet *un) {
  int k;
  BigSetMakeNull(un);
  for (k = 0; k < a.universe; k++) {
    if ((a.element)[k] || (b.element)[k]) {
      (*un).element[k] = 1;
    }
  }
}


/*
  BigSetPlaceIntersection, Tim McLarnan, 1/21/2000
  pre: a and b are BigSets; inter is a pointer to a BigSet *inter.
  WARNING: The sets a, b and *inter must have the same size universe.
  For efficiency, this is not checked.
  Insuring it is a programmer responsibility.
  post: *inter contains a intersect b.
*/
void BigSetPlaceIntersection(BigSet a, BigSet b, BigSet *inter) {
  int k;
  BigSetMakeNull(inter);
  for (k = 0; k < a.universe; k++) {
    if ((a.element)[k] && (b.element)[k]) {
      (*inter).element[k] = 1;
    }
  }
}


/*
  BigSetPrint, Tim McLarnan, 1/21/2000
  pre: b is a BigSet.
  post: prints b to stdout.
*/
void BigSetPrint(BigSet b) {
  long elt;
  int first_time = 1;
  printf("{");
  for (elt = 0; elt < b.universe; elt++) {
    if (BigSetElementOf(b, elt)) {
      if (first_time) {
	first_time = 0;
      } else {
	printf(", ");
      }
      printf("%ld", elt);
    }
  }
  printf("}");
}


/*
  BigSetCopy  Tim McLarnan, 1/10/2000.
              Modified 7/10/2000 to return an int.
  pre: source and *target are BigSets.
  post: target is a copy of source, not sharing the array source.element.
  returns: 1 on success; 0 if the malloc in BigSetMake fails.
*/
int BigSetCopy(BigSet source, BigSet *target) {
  if (BigSetMake(target, source.universe)) {
    memcpy((*target).element, source.element, source.universe);
    return(1);
  } else {
    return(0);
  }
}