merlyn@starfire.UUCP (08/14/87)
# Here are a couple of C include files to add the set type a la' Pascal. # A very small demo program is also included. Read the comments in # sets.h for edification. # # Merlyn Leroy (starfire!merlyn) : ---cut here--- : #!/bin/sh # This is a shell archive. Remove everything # above !/bin/sh and type 'sh this_sharfile' to unpack. # 'sharfile complete' should appear last. # Made by 'MVAX1!brianw' on Wed Aug 12 15:15:25 CDT 1987 export HOME || ( set cmd=`echo "$0"` ; echo " " ; \ echo "This is not /bin/sh - punting..." ; \ echo Do \"sh sharfile\", not \"csh \<sharfile\" "$cmd" | \ sed "s:^........................................*::" ; \ set cmd=`echo "$cmd/dev/null" | sed "s ^\(..*\).........$ \1 "` ; \ /bin/sh "$cmd" $* ; kill $$ ; ) umask 002 PATH="/bin:/usr/bin:$PATH" echo extracting: F='sets.h' echo $F if test -f $F then echo $F exists - not extracted >&2 else sed 's.^>..' << 'EOF' > $F > >/* sets.h - set pseudo-type for C > * > * to use, include ONE of "sets.h" or "setlib.h" > * setlib.h has the actual C routines, and must be included exactly once > * in a group of files, or made into a library and linked in. > * > * to declare a set type: > * set alphabet of('a','z'); > * set wands of(striking,polymorph); > * static set vowels of('a','z'); > * > * The element ranges must be known at compile time (constants or enums). > * The smaller element must be first. Set variables within functions and > * procedures must be declared static, or declared as: > * set digits ofsize('0','9'); > * and explicitly initialized with: > * first_element(digits) = '0'; > * last_element(digits) = '9'; > * > * You can also declare a pointer to a set, thus: > * set *p_set; > * Point it to a set variable (p_set=alphabet;), or use malloc() & initialize: > * p_set = (set *) malloc(sizeof(set ofsize('A','Z'))); > * first_element(p_set) = 'A'; > * last_element(p_set) = 'Z'; > * > * The special null set EMPTYSET is also defined. > * > * All operations on sets must be between sets of the same range > * (or EMPTYSET) except for setncpy(). > * > * functions: > * first_element(S) First legal element of set S > * last_element(S) Last legal element of set S > * set *emptyset(S) Make S the emptyset (returns EMPTYSET) > * > * These functions return S1 or EMPTYSET if result is null: > * > * set *setcpy(S1,S2) copy S2 into S1 > * set *setncpy(S1,S2) copy S2 into S1, even for different ranges > * e.g. set S1 of('A','L'), S2 of('H','Z'); > * set *setunion(S1,S2) S1 = S1 union S2 (S1 evaluated twice) > * set *set3union(S1,S2,S3) S1 = S2 union S3 > * set *setinter(S1,S2) S1 = S1 intersection S2 (S1 evaluated twice) > * set *set3inter(S1,S2,S3) S1 = S2 intersection S3 > * set *setdiff(S1,S2) S1 = S1 difference S2 (S1 evaluated twice) > * set *set3diff(S1,S2,S3) S1 = S2 difference S3 > * > * This allows: if (setinter(text,vowels) == EMPTYSET) puts("No vowels!"); > * > * setord(S) Returns number of elements in set S > * ismember(S,E) Returns 1 if E is a member of set S, else 0 > * > * These three functions return S if E is a legal element, EMPTYSET otherwise > * set *addmember(S,E) Add element E to set S > * set *submember(S,E) Subtract element E from set S > * set *xormember(S,E) Toggle element E in set S > * > * The next few functions take a list of elements. > * For sets whose first element is greater than one, a list is a > * null-terminated string; otherwise, a list is an integer (enum) pointer > * to a list terminated by first_element(S)-1. This allows: > * set alphabet of('A','z'); > * setlcpy(alphabet,"AEIOUaeiou"); > * or, for enums: > * enum colors { endcolor, red, blue, green}; > * enum colorlist[] = { green, blue, endcolor }; > * set spectrum of(red,green); > * setlcpy(spectrum, colorlist); > * > * The first four functions all return S > * set *setlcpy(S,L) Assign the list of elements L to set S > * set *addlmember(S,L) Adds list L to set S > * set *sublmember(S,L) Subtracts list L from set S > * set *xorlmember(S,L) Toggles list L in set S > * setlord(S,L) Returns count of elements in L found in set S > * > * Finally, there is setcmp(S1,S2) to compare sets. Values returned are: > * ERRORSET The sets are of different ranges > * SAMESET The sets are equal > * SUBSET Set S1 is a proper subset of S2 > * SUPERSET Set S1 is a proper superset of S2 > * DISJOINT Sets S1 and S2 have no elements in common > * DIFFSET None of the above; S1 and S2 have at least one > * element in common and at least one unique element. > * > * Also note that: > * setcmp(S1,S2) & SUBSET is true iff S1 is a subset of S2 > * (proper subset or sets are equal) > * setcmp(S1,S2) & SUPERSET is true iff S1 is a superset of S2 > * setcmp(S1,S2) & SAMESET is true iff S1 is a sub- or superset of S2 > * EMPTYSET is a subset of all other sets > * !setcmp(S1,S2) is NOT the same as (setcmp(S1,S2) == SAMESET) > * > */ > >/* What type to use for a set, the number of bits in it, and log2 of bits. */ >/* The first and last element of a set must fit into the type used for set. */ >/* For example, set years of(1900,1987) wouldn't work with an 8-bit set */ >/* type; a larger type would be needed. */ >#define set char >#define SET_BSIZE 8 /* must be power of two; use 8 if 9 bit chars, etc */ >#define SET_SSIZE 3 /* log2 of previous number */ > >#define of(a,z) [((SET_BSIZE-(int)(a)+(int)(z))>>SET_SSIZE)+2]={(set)a,(set)z} >#define ofsize(a,z) [((SET_BSIZE-(int)(a)+(int)(z))>>SET_SSIZE)+2] > >#define first_element(s) ((s)[0]) >#define last_element(s) ((s)[1]) > >#define EMPTYSET ((set *)0) > >/* setcmp return values */ >#define SUBSET 0x01 >#define SUPERSET 0x02 >#define SAMESET 0x03 >#define DIFFSET 0x00 >#define DISJOINT 0x04 >#define ERRORSET 0x80 /* sets have different element ranges */ > >#define addlmember(s,l) S_lmember(s,(char *)(l),addmember) >#define sublmember(s,l) S_lmember(s,(char *)(l),submember) >#define xorlmember(s,l) S_lmember(s,(char *)(l),xormember) > >#define setunion(s1,s2) set3union(s1,s1,s2) >#define setinter(s1,s2) set3inter(s1,s1,s2) >#define setdiff(s1,s2) set3diff(s1,s1,s2) > >#define setlcpy(s1,l) S_setlcpy(s1,(char *)(l)) >#define setlord(s,l) S_setlord(s,(char *)(l)) > >#ifndef _SETLIB_ >extern set *setcpy(), *setncpy(), *set3union(), *set3inter(), *set3diff(), > *addmember(), *submember(), *xormember(), > *S_lmember(), *S_setlcpy(), *emptyset(); >extern int ismember(), setord(), setcmp(), S_setlord(); >#endif /* _SETLIB_ */ EOF S=`wc -c < $F` if test 5477 != $S then echo $F: size is $S, should be 5477 >&2 fi fi F='setlib.h' echo $F if test -f $F then echo $F exists - not extracted >&2 else sed 's.^>..' << 'EOF' > $F > >/* setlib.h - set pseudo-type for C, library programs */ >/* see sets.h for usage */ > >#define _SETLIB_ >#include "sets.h" >#undef _SETLIB_ > >#define setsize(s) ((SET_BSIZE-(first_element(s)-last_element(s)))>>SET_SSIZE) > >set *emptyset(s) >register set *s; >{ > register int n; > > n = setsize(s); > s += 2; > while (n-- > 0) > *s++ = 0; > return (EMPTYSET); >} > >set *setcpy(s1,s2) >register set *s1,*s2; >{ > register short n; > register set nonnull = 0; > set *s = s1; > > if (s2 != EMPTYSET) { > n = setsize(s2); > *s1++ = *s2++; /* copy the element ranges too - can be different */ > *s1++ = *s2++; > while (n-- > 0) > nonnull |= (*s1++ = *s2++); > return (nonnull ? s : EMPTYSET); > } > else > return (emptyset(s1)); >} > >set *set3union(s1,s2,s3) >register set *s1,*s2,*s3; >{ > register short n; > register set nonnull = 0; > set *s = s1; > > if (s2 == EMPTYSET) > s2 = s3, s3 = EMPTYSET; > if (s2 == EMPTYSET) > return (emptyset(s1)); > n = setsize(s2); > *s1++ = *s2++; > *s1++ = *s2++; > if (s3 != EMPTYSET) { > s3 += 2; > while (n-- > 0) > nonnull |= (*s1++ = (*s2++ | *s3++)); > } > else { > while (n-- > 0) > nonnull |= (*s1++ = *s2++); > } > return (nonnull ? s : EMPTYSET); >} > >set *set3inter(s1,s2,s3) >register set *s1,*s2,*s3; >{ > register short n; > register set nonnull = 0; > set *s = s1; > > if (s2 == EMPTYSET) > s2 = s3, s3 = EMPTYSET; > if (s2 == EMPTYSET) > return (emptyset(s1)); > n = setsize(s2); > *s1++ = *s2++; > *s1++ = *s2++; > if (s3 != EMPTYSET) { > s3 += 2; > while (n-- > 0) > nonnull |= (*s1++ = (*s2++ & *s3++)); > return (nonnull ? s : EMPTYSET); > } > else > return (emptyset(s)); /* must use s, not (modified) s1 */ >} > >set *set3diff(s1,s2,s3) >register set *s1,*s2,*s3; >{ > register short n; > register set nonnull = 0; > set *s = s1; > > if (s2 == EMPTYSET) > return (emptyset(s1)); > n = setsize(s2); > *s1++ = *s2++; > *s1++ = *s2++; > if (s3 != EMPTYSET && s2 != EMPTYSET) { > s3 += 2; > while (n-- > 0) > nonnull |= (*s1++ = (*s2++ & ~*s3++)); > } > else { > while (n-- > 0) > nonnull |= (*s1++ = *s2++); > } > return (nonnull ? s : EMPTYSET); >} > >int setord(s) >register set *s; >{ > register short member, total = 0; > > if (s != EMPTYSET) { > for (member=first_element(s); member<=last_element(s); member++) { > if (ismember(s,member)) > total++; > } > } > return (total); >} > >int setcmp(s1,s2) >register set *s1,*s2; >{ > register short n; > register int result; > > if (s1 != EMPTYSET && s2 != EMPTYSET) { > if (first_element(s1) != first_element(s2) || > last_element(s1) != last_element(s2)) > return (ERRORSET); > n = setsize(s1); > s1 += 2; s2 += 2; > result = SAMESET | DISJOINT; > while (n-- > 0 && result) { > if (*s1 & ~*s2) > result &= ~SUBSET; > if (*s2 & ~*s1) > result &= ~SUPERSET; > if (*s1++ & *s2++) > result &= ~DISJOINT; > } > if (result != DISJOINT) > result &= ~DISJOINT; > return (result); > } > else if (s1 != EMPTYSET) { > n = setsize(s1); > s1 += 2; > while (n-- > 0) > if (*s1++) > return (SUPERSET); > } > else if (s2 != EMPTYSET) { > n = setsize(s2); > s2 += 2; > while (n-- > 0) > if (*s2++) > return (SUBSET); > } > return (SAMESET); >} > >int ismember(s,e) >register set *s; >int e; >{ > if (first_element(s) <= e && e <= last_element(s)) { > e -= first_element(s); > return ((s[(e>>SET_SSIZE)+2] & (1<<(e & (SET_BSIZE-1)))) != 0); > } > else > return (0); >} > >set *addmember(s,e) >register set *s; >int e; >{ > if (first_element(s) <= e && e <= last_element(s)) { > e -= first_element(s); > s[(e>>SET_SSIZE)+2] |= (1<<(e & (SET_BSIZE-1))); > return (s); > } > else > return (EMPTYSET); >} > >set *submember(s,e) >register set *s; >int e; >{ > if (first_element(s) <= e && e <= last_element(s)) { > e -= first_element(s); > s[(e>>SET_SSIZE)+2] &= ~(1<<(e & (SET_BSIZE-1))); > return (s); > } > else > return (EMPTYSET); >} > >set *xormember(s,e) >register set *s; >int e; >{ > if (first_element(s) <= e && e <= last_element(s)) { > e -= first_element(s); > s[(e>>SET_SSIZE)+2] ^= (1<<(e & (SET_BSIZE-1))); > return (s); > } > else > return (EMPTYSET); >} > >set *S_lmember(s,l,fn) >register set *s; >register char *l; >set *(*fn)(); >{ > register short base; > register int *ll; > > base = first_element(s); > if (base > 1) { > while (*l) > (fn)(s,*l++); > } > else { > ll = (int *)l; > while (*ll != base-1) > (fn)(s,*ll++); > } > return (s); >} > >int S_setlord(s,l) >register set *s; >register char *l; >{ > register short base, total = 0; > register int *ll; > > if (s == EMPTYSET) > return (0); > base = first_element(s); > if (base > 1) { > while (*l) > total += ismember(s,*l++); > } > else { > ll = (int *)l; > while (*ll != base-1) > total += ismember(s,*ll++); > } > return (total); >} > >set *S_setlcpy(s1,l) >set *s1; >char *l; >{ > emptyset(s1); > return (S_lmember(s1,l,addmember)); >} > >set *setncpy(s1,s2) >register set *s1, *s2; >{ > register short member; > set *result = EMPTYSET; > > emptyset(s1); > if (s2 != EMPTYSET) { > for (member=first_element(s2); member<=last_element(s2); member++) { > if (ismember(s2,member) && addmember(s1,member)) > result = s1; > } > } > return (result); >} > >#undef setsize EOF S=`wc -c < $F` if test 5224 != $S then echo $F: size is $S, should be 5224 >&2 fi fi F='setdemo.c' echo $F if test -f $F then echo $F exists - not extracted >&2 else sed 's.^>..' << 'EOF' > $F > >#include <stdio.h> >#include "setlib.h" > >set s1 of('a','z'), s2 of('a','z'); > >main() >{ > set *s3; > > s3 = s2; > setlcpy(s1,"aeiou"); > pr_set(s1); > emptyset(s3); > addlmember(s3,"asdfgh"); > pr_set(s3); > pr_set(setunion(s3,s1)); > pr_set(setdiff(s3,s1)); > pr_set(setdiff(s1,s1)); >} > >pr_set(s) >set *s; >{ > int i; > > if (s) > for (i=first_element(s); i<=last_element(s); i++) > putchar((ismember(s,i)) ? i : ' '); > else > printf("-emptyset pointer-"); > putchar('\n'); >} > EOF S=`wc -c < $F` if test 466 != $S then echo $F: size is $S, should be 466 >&2 fi fi F=Y echo Checking manifest.. for file in \ 'sets.h' \ 'setlib.h' \ 'setdemo.c' do if test ! -r $file then echo Error: $file not extracted. >&2 F= fi done echo sharfile complete if test "$F" then exit 0 else exit 2 fi