/* 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
/*
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);
}
}