Sets in C (like Pascal)

[Rhys Weatherley]

gwyn at smoke.BRL.MIL (Doug Gwyn) writes:

>In article <1990Jun26.144523.8804 at cs.utk.edu> wozniak at utkux1.utk.edu (Bryon Lape) writes:
>>	I know that the enum type is simliar to sets, but is there
>>anyway to have sets in C like there is in Pascal?

>Yes, roll your own.  It's not hard.

>>What of the set operators (+,-,*,/)?

>These are set operators?

Yep, In Pascal they are respectively union, difference, intersection, and ...
something else I can't remember :-).

I replied to Bryon myself, but I'll also post an excerpt from my reply here
as well to belay more unnecessary bandwidth wasting discussion on the topic:

The easiest way to get a set is to use an 'int' or 'long' to represent it,
and deal with bit fields.  e.g. the following macros, defs, etc:

/* The set type for elements 0..n */
typedef	int	SetType;

/* OR... */
typedef	long	SetType;

/* Convert an element (0..n) into a set */
#define	SET_ELEM(x)	(1 << (x))

/* Get the union of two sets */
#define	UNION(x,y)	((x) | (y))

/* Get the intersection of two sets */
#define	INTERSECT(x,y)	((x) & (y))

/* Diference operator */
#define	DIFFERENCE(x,y)	((x) & ~(y))

/* See if something (x) is a member of a set (y) */
#define	MEMBER(x,y)	(SET_ELEM(x) & (y))

/* See if something (x) is a subset of a set (y) */
#define	SUBSET(x,y)	(((y) & (x)) == (x))

/* See if something (x) is a proper subset of a set (y) */
#define	PROPER(x,y)	(SUBSET(x,y) && !((x) == (y)))

/* .... etc .... */

Be careful of side effects when using the last two (SUBSET and PROPER).

If you pull apart the generated code from most Pascal compilers, you
usually find it is implemented this way anyway!  If you need more arbitrary
sets, i.e. elements in the range 100..110, etc, you just need to
change SET_ELEM, and away you go.  e.g:

#define	SET_ELEM(x)	(1 << ((x) - 100))

Also, by having a different SET_ELEM for each set type you want, you can 
still use all the other operators with no worries. For "niceness" use the 
type 'SetType' or an equivalent always, as this makes it clearer as to 
what you are doing.

Totally arbitrary sets are a different matter, and are best implemented
with linked lists, binary trees, and other such structures, but for the
run-of-the-mill Pascal type sets, this method is adequate.

Rhys.

+===============================+==============================+
||  Rhys Weatherley             |  University of Queensland,  ||
||  rhys at batserver.cs.uq.oz.au  |  Australia.  G'day!!        ||
+===============================+==============================+