1 /*
2 * Copyright (c) 2000, 2001 Peter Bozarov.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by Peter Bozarov.
16 * 4. The name of the author may not be used to endorse or promote products
17 * derived from this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
23 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
24 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
27 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
28 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
29 * POSSIBILITY OF SUCH DAMAGE.
30 */
31
32 /*
33 * Implementation of sets and bags.
34 * A Set is a data structure that holds any number of unique elements ---
35 * i.e. no duplicates are allowed. A Bag can hold any number of elements,
36 * including duplicates.
37 *
38 * This particular implementation uses a QUEUE to represent sets.
39 *
40 * Created: Mon Jan 7 10:38:41 EST 2002
41 * Updates: Sat Jun 22 12:29:23 EST 2002
42 */
43
44 # include "local.h"
45
46 struct _set
47 {
48 int ord; /* Elements have an order flag */
49 int ed; /* Ensure disjoint flag */
50 union {
51 QUEUE un_qelts;
52 AVLTREE un_telts;
53 } un_data;
54 SETCMPFUN cmp;
55 };
56
57 # define SET_IsSET(s) ( (s)->ed != 0 )
58 # define SET_IsBAG(s) ( (s)->ed == 0 )
59
60 # define SET_Ord(s) ( (s)->ord != 0 )
61
62 # define qelts un_data.un_qelts
63 # define telts un_data.un_telts
64
65 SET
setMake(void)66 setMake(void)
67 {
68 return setNew(NULL,0,0);
69 }
70
71 SET
setNew(SETCMPFUN f,int ensure_disjoint,int ord)72 setNew(SETCMPFUN f,int ensure_disjoint,int ord)
73 {
74 Set * set;
75
76 STDMALLOC(set,sizeof(Set),NULL);
77
78 set->ed = ensure_disjoint != 0;
79
80 if (ensure_disjoint && ord)
81 {
82 /* Elements can be ordered, this means, use more efficient AVL tree */
83 set->telts = avlNewTree(f,0,0);
84 set->ord = 1;
85 }
86 else
87 {
88 /* Elements cannot be ordered, use conventional QUEUE */
89 set->qelts= qMake();
90 set->ord = 0;
91 }
92 set->cmp = f;
93
94 return set;
95 }
96 void
setClose(SET set)97 setClose(SET set)
98 {
99 if (SET_Ord(set))
100 avlClose(set->telts);
101 else
102 qClose(set->qelts);
103
104 STDFREE(set);
105 }
106 void
setCloseWithFunction(SET set,void (* fun)(void *))107 setCloseWithFunction(SET set,void (*fun)(void*))
108 {
109 if (SET_Ord(set))
110 avlCloseWithFunction(set->telts,fun);
111 else
112 qCloseWithFunction(set->qelts,fun);
113 STDFREE(set);
114 }
115 /*----------------------------------------------------------------------*
116 * Add/Remove *
117 *----------------------------------------------------------------------*/
118 int
setAdd(SET set,void * data)119 setAdd(SET set,void *data)
120 {
121 /* An ordered set uses the avl tree routines. */
122 if (SET_Ord(set))
123 return avlInsert(set->telts,data,data);
124
125 /* A non-ordered set uses the disjoint flag to check if it needs to
126 * exclude double elements */
127 if (SET_IsSET(set) && setContains(set,data))
128 return -1;
129
130 /* Else, or if BAG, add the element to the queue */
131 return - !qAdd(set->qelts,data);
132 }
133 void*
setRemove(SET set,void * key)134 setRemove(SET set,void * key)
135 {
136 void *e;
137
138 if (SET_Ord(set))
139 return avlRemove(set->telts,key);
140
141 for (e = qFirst(set->qelts); e; e = qNext(set->qelts))
142 {
143 if (set->cmp ? set->cmp(e,key) == 0 : e == key)
144 {
145 qElemRemove(set->qelts,qElemCurr(set->qelts));
146 return e;
147 }
148 }
149
150 return NULL;
151 }
152 void*
setFirst(SET set)153 setFirst(SET set)
154 {
155 if (SET_Ord(set))
156 return avlFirst(set->telts);
157
158 return qFirst(set->qelts);
159 }
160 void*
setNext(SET set)161 setNext(SET set)
162 {
163 if (SET_Ord(set))
164 return avlNext(set->telts);
165
166 return qNext(set->qelts);
167 }
168
169 int
setSize(SET set)170 setSize(SET set)
171 {
172 if (SET_Ord(set))
173 return avlSize(set->telts);
174
175 return qSize(set->qelts);
176 }
177 int
setEmpty(SET set)178 setEmpty(SET set)
179 {
180 return setSize(set) == 0;
181 }
182 int
setContains(SET set,void * elt)183 setContains(SET set,void *elt)
184 {
185 return setFind(set,elt) != NULL;
186 }
187 /*----------------------------------------------------------------------*/
188 /* Search for an element in a SET/BAG. If a set is passed, we simply */
189 /* use the avltree find routines to locate it. If a BAG is passed, we need*/
190 /* to inspect all elements prior to locating the one we are looking for.*/
191 /* If no compare routine is given, we resort to comparing pointers. What*/
192 /* else? */
193 /*----------------------------------------------------------------------*/
194 void*
setFind(SET set,void * elt)195 setFind(SET set,void *elt)
196 {
197 void *e;
198
199 /* A orderable SET: fetch element trough avlTree routines. */
200 if (SET_Ord(set))
201 return avlFind(set->telts,elt);
202
203 for (e = qFirst(set->qelts); e; e = qNext(set->qelts))
204 {
205 if (set->cmp ? set->cmp(e,elt) == 0 : e == elt)
206 return e;
207 }
208
209 return NULL;
210 }
211
212 /*----------------------------------------------------------------------*/
213 /* Unions and Intersections of SETs and BAGs */
214 /*----------------------------------------------------------------------*/
215
216 /*----------------------------------------------------------------------*/
217 /* setUnion(set1,set2): elements of set2 are simply added to set1. Set2 */
218 /* remains unchanged. set1 is modified. */
219 /* Return value is the new version of set1. */
220 /*----------------------------------------------------------------------*/
221
222 SET
setUnion(SET set1,SET set2)223 setUnion(SET set1,SET set2)
224 {
225 void *e;
226
227 /* Add all elements of set2 onto set1 */
228 for (e = setFirst(set2); e; e = setNext(set2))
229 setAdd(set1,e);
230
231 return set1;
232 }
233
234 /*----------------------------------------------------------------------*/
235 /* setUnion1(set1,set2): here, a completely new set is created, and the */
236 /* union of set1 and set2 is stored in it. set1 and set2 remain */
237 /* unmodified. */
238 /* Returns a new set that inherits all parameters of set1. */
239 /*----------------------------------------------------------------------*/
240
241 SET
setUnion1(SET s1,SET s2)242 setUnion1(SET s1,SET s2)
243 {
244 SET set;
245 void *e;
246
247 set = setNew(s1->cmp,s1->ed,s1->ord);
248
249 if (!set)
250 { XLOG(set); return NULL; }
251
252 for (e = setFirst(s1); e; e = setNext(s1))
253 setAdd(set,e); /* Blind copy of s1 */
254
255 for (e = setFirst(s2); e; e = setNext(s2))
256 setAdd(set,e); /* Call setAdd() to weed out duplicates */
257
258 return set;
259 }
260 /*----------------------------------------------------------------------*/
261 /* setIntersect(set1,set2): a new set is created that contains the */
262 /* intersection of the elements contained in set1 and set2. */
263 /* This measn A /\ B */
264 /*----------------------------------------------------------------------*/
265
266 SET
setIntersect(SET s1,SET s2)267 setIntersect(SET s1,SET s2)
268 {
269 SET set;
270 void *e;
271
272 /* At least one of the sets must have a compare function */
273 if ( ! (s1->cmp || s2->cmp) )
274 return NULL;
275
276 /* Create a disjoint set */
277 set = setNew(s1->cmp ? s1->cmp : s2->cmp,1,s1->ord);
278
279 if (!set)
280 { XLOG(set); return NULL; }
281
282 for (e = setFirst(s1); e; e = setNext(s1))
283 {
284 if (setContains(s2,e))
285 setAdd(set,e);
286 }
287
288 return set;
289 }
290 /*----------------------------------------------------------------------*/
291 /* The difference of two sets: the result of A - B is all elements that */
292 /* belong to A only. This means A - B = A /\ B - B */
293 /*----------------------------------------------------------------------*/
294
295 SET
setDifference(SET A,SET B)296 setDifference(SET A,SET B)
297 {
298 SET set;
299 void *e;
300
301 if ( ! B->cmp)
302 return NULL; /* B needs a compare function */
303
304 /* Create the resulting set */
305 set = setNew(A->cmp,A->ed,A->ord);
306
307 if (!set)
308 { XLOG(set); return NULL; }
309
310 for (e = setFirst(A); e; e = setNext(A))
311 if (!setContains(B,e))
312 setAdd(set,e);
313
314 return set;
315 }
316 /*----------------------------------------------------------------------*/
317 /* setXIntersect(set1,set2): a new set is created, containing those */
318 /* elements of set1 and set2 that are not contained in the intersection */
319 /* of set1 and set2. */
320 /* Note: mathematically, this is the difference A \/ B - A /\ B */
321 /*----------------------------------------------------------------------*/
322
323 SET
setXIntersect(SET A,SET B)324 setXIntersect(SET A,SET B)
325 {
326 SET set;
327 void *e;
328
329 if (! (A->cmp && B->cmp) )
330 return NULL; /* Both need a compare function */
331
332 /* Create new set */
333 if (! (set = setNew(A->cmp,A->ed,A->ord)))
334 { XLOG(set); return NULL; }
335
336 /* Add elements of A only */
337 for (e = setFirst(A); e; e = setNext(A))
338 if (!setContains(B,e))
339 setAdd(set,e);
340
341 /* Add elements of B only */
342 for (e = setFirst(B); e; e = setNext(B))
343 if (!setContains(A,e))
344 setAdd(set,e);
345
346 return set;
347 }
348