How to do sets?

[David Collier-Brown]

>From article <5080031 at hpfcdc.HP.COM>, by mike at hpfcdc.HP.COM (Mike McNelly):
quotes someone who says:
> Is there a way to do sets in C (like in Pascal)?  That is, check for set
> inclusion (char in ["0".."9"]), and perform unions and intersections. 

Sure, here's a procedural model in an ad-hoc specification language:

define
	create: size of set -> set | error
	assign: set x value -> set | error
	in: set x value -> YES | NO
	and: set x set -> set | error
	... other binary booleans ditto ...
	uncreate: set -> error trap
implement as if
	create(size) ::=
		malloc((size/BITSPERWORD)+2)[0] = signature
					    [1] = size - 2
	in(set,value) ::=
		if set[0] == signature 
			if value <= size
				set[2+value/BITSPERWORD][value%BITSPERWORD]
				(see note below, though)
			else
				NO
		else
			error
	and(set1,set2) ::=
		if set1[0] == set2[0] == signature 
		   && set1[1] == set2[1] 
			for i=0; i < size; i++
				set1[2+i] &= set2[2+i]
		else
			error
	uncreate(set) ::=
		if set[0] == signature
			set[0] = error
		else
			error
   As you can probably see from the shorthand above, a set is a
behavior, implementable as procedures acting on a sequence of
storage units which can be accessed by the bit, with a signature and
a length.
   The signature is just for run-time checking, and the length is
mostly for the "in" operation, so it doesn't lie when you fall off
the end.  In an implementation one could probably use a struct so as
to allow most sanity checks to be compiled to (constant-expression ==
variable)?  Dirty tricks with data encoding can also improve
performance. (eg: make the signature & length a float on one
particular machine: the sanity check becomes an exception mechanism
in the hardware)
  Constantly-varying lengths can be done easily with realloc, by
the way, so you can start with a size hint instead of a value.  The
extra overhead doesn't cost much unless you start using the
variability feature a lot.

Etc, etc, ad infinitum.  Indeed, ad nauseam.  C is a subtle
language, although by no means a sophisticated one.

--dave (a philosopher, not a sophist) c-b
   
-- 
 David Collier-Brown.  | yunexus!lethe!dave
 Interleaf Canada Inc. |
 1550 Enterprise Rd.   | He's so smart he's dumb.
 Mississauga, Ontario  |       --Joyce C-B