1 /*<html><pre>  -<a                             href="qh-set.htm"
2   >-------------------------------</a><a name="TOP">-</a>
3 
4    qset.h
5      header file for qset.c that implements set
6 
7    see qh-set.htm and qset.c
8 
9    only uses mem.c, malloc/free
10 
11    for error handling, writes message and calls
12       qh_errexit(qhmem_ERRqhull, NULL, NULL);
13 
14    set operations satisfy the following properties:
15     - sets have a max size, the actual size (if different) is stored at the end
16     - every set is NULL terminated
17     - sets may be sorted or unsorted, the caller must distinguish this
18 
19    Copyright (c) 1993-2012 The Geometry Center.
20    $Id: //main/2011/qhull/src/libqhull/qset.h#4 $$Change: 1464 $
21    $DateTime: 2012/01/25 22:58:41 $$Author: bbarber $
22 */
23 
24 #ifndef qhDEFset
25 #define qhDEFset 1
26 
27 #include <stdio.h>
28 
29 /*================= -structures- ===============*/
30 
31 #ifndef DEFsetT
32 #define DEFsetT 1
33 typedef struct setT setT;   /* a set is a sorted or unsorted array of pointers */
34 #endif
35 
36 /*-<a                                      href="qh-set.htm#TOC"
37 >----------------------------------------</a><a name="setT">-</a>
38 
39 setT
40   a set or list of pointers with maximum size and actual size.
41 
42 variations:
43   unsorted, unique   -- a list of unique pointers with NULL terminator
44                            user guarantees uniqueness
45   sorted             -- a sorted list of unique pointers with NULL terminator
46                            qset.c guarantees uniqueness
47   unsorted           -- a list of pointers terminated with NULL
48   indexed            -- an array of pointers with NULL elements
49 
50 structure for set of n elements:
51 
52         --------------
53         |  maxsize
54         --------------
55         |  e[0] - a pointer, may be NULL for indexed sets
56         --------------
57         |  e[1]
58 
59         --------------
60         |  ...
61         --------------
62         |  e[n-1]
63         --------------
64         |  e[n] = NULL
65         --------------
66         |  ...
67         --------------
68         |  e[maxsize] - n+1 or NULL (determines actual size of set)
69         --------------
70 
71 */
72 
73 /*-- setelemT -- internal type to allow both pointers and indices
74 */
75 typedef union setelemT setelemT;
76 union setelemT {
77   void    *p;
78   int      i;         /* integer used for e[maxSize] */
79 };
80 
81 struct setT {
82   int maxsize;          /* maximum number of elements (except NULL) */
83   setelemT e[1];        /* array of pointers, tail is NULL */
84                         /* last slot (unless NULL) is actual size+1
85                            e[maxsize]==NULL or e[e[maxsize]-1]==NULL */
86                         /* this may generate a warning since e[] contains
87                            maxsize elements */
88 };
89 
90 /*=========== -constants- =========================*/
91 
92 /*-<a                                 href="qh-set.htm#TOC"
93   >-----------------------------------</a><a name="SETelemsize">-</a>
94 
95   SETelemsize
96     size of a set element in bytes
97 */
98 #define SETelemsize ((int)sizeof(setelemT))
99 
100 
101 /*=========== -macros- =========================*/
102 
103 /*-<a                                 href="qh-set.htm#TOC"
104   >-----------------------------------</a><a name="FOREACHsetelement_">-</a>
105 
106    FOREACHsetelement_(type, set, variable)
107      define FOREACH iterator
108 
109    declare:
110      assumes *variable and **variablep are declared
111      no space in "variable)" [DEC Alpha cc compiler]
112 
113    each iteration:
114      variable is set element
115      variablep is one beyond variable.
116 
117    to repeat an element:
118      variablep--; / *repeat* /
119 
120    at exit:
121      variable is NULL at end of loop
122 
123    example:
124      #define FOREACHfacet_( facets ) FOREACHsetelement_( facetT, facets, facet )
125 
126    notes:
127      use FOREACHsetelement_i_() if need index or include NULLs
128 
129    WARNING:
130      nested loops can't use the same variable (define another FOREACH)
131 
132      needs braces if nested inside another FOREACH
133      this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} )
134 */
135 #define FOREACHsetelement_(type, set, variable) \
136         if (((variable= NULL), set)) for (\
137           variable##p= (type **)&((set)->e[0].p); \
138           (variable= *variable##p++);)
139 
140 /*-<a                                      href="qh-set.htm#TOC"
141   >----------------------------------------</a><a name="FOREACHsetelement_i_">-</a>
142 
143    FOREACHsetelement_i_(type, set, variable)
144      define indexed FOREACH iterator
145 
146    declare:
147      type *variable, variable_n, variable_i;
148 
149    each iteration:
150      variable is set element, may be NULL
151      variable_i is index, variable_n is qh_setsize()
152 
153    to repeat an element:
154      variable_i--; variable_n-- repeats for deleted element
155 
156    at exit:
157      variable==NULL and variable_i==variable_n
158 
159    example:
160      #define FOREACHfacet_i_( facets ) FOREACHsetelement_i_( facetT, facets, facet )
161 
162    WARNING:
163      nested loops can't use the same variable (define another FOREACH)
164 
165      needs braces if nested inside another FOREACH
166      this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} )
167 */
168 #define FOREACHsetelement_i_(type, set, variable) \
169         if (((variable= NULL), set)) for (\
170           variable##_i= 0, variable= (type *)((set)->e[0].p), \
171                    variable##_n= qh_setsize(set);\
172           variable##_i < variable##_n;\
173           variable= (type *)((set)->e[++variable##_i].p) )
174 
175 /*-<a                                    href="qh-set.htm#TOC"
176   >--------------------------------------</a><a name="FOREACHsetelementreverse_">-</a>
177 
178    FOREACHsetelementreverse_(type, set, variable)-
179      define FOREACH iterator in reverse order
180 
181    declare:
182      assumes *variable and **variablep are declared
183      also declare 'int variabletemp'
184 
185    each iteration:
186      variable is set element
187 
188    to repeat an element:
189      variabletemp++; / *repeat* /
190 
191    at exit:
192      variable is NULL
193 
194    example:
195      #define FOREACHvertexreverse_( vertices ) FOREACHsetelementreverse_( vertexT, vertices, vertex )
196 
197    notes:
198      use FOREACHsetelementreverse12_() to reverse first two elements
199      WARNING: needs braces if nested inside another FOREACH
200 */
201 #define FOREACHsetelementreverse_(type, set, variable) \
202         if (((variable= NULL), set)) for (\
203            variable##temp= qh_setsize(set)-1, variable= qh_setlast(set);\
204            variable; variable= \
205            ((--variable##temp >= 0) ? SETelemt_(set, variable##temp, type) : NULL))
206 
207 /*-<a                                 href="qh-set.htm#TOC"
208   >-----------------------------------</a><a name="FOREACHsetelementreverse12_">-</a>
209 
210    FOREACHsetelementreverse12_(type, set, variable)-
211      define FOREACH iterator with e[1] and e[0] reversed
212 
213    declare:
214      assumes *variable and **variablep are declared
215 
216    each iteration:
217      variable is set element
218      variablep is one after variable.
219 
220    to repeat an element:
221      variablep--; / *repeat* /
222 
223    at exit:
224      variable is NULL at end of loop
225 
226    example
227      #define FOREACHvertexreverse12_( vertices ) FOREACHsetelementreverse12_( vertexT, vertices, vertex )
228 
229    notes:
230      WARNING: needs braces if nested inside another FOREACH
231 */
232 #define FOREACHsetelementreverse12_(type, set, variable) \
233         if (((variable= NULL), set)) for (\
234           variable##p= (type **)&((set)->e[1].p); \
235           (variable= *variable##p); \
236           variable##p == ((type **)&((set)->e[0].p))?variable##p += 2: \
237               (variable##p == ((type **)&((set)->e[1].p))?variable##p--:variable##p++))
238 
239 /*-<a                                 href="qh-set.htm#TOC"
240   >-----------------------------------</a><a name="FOREACHelem_">-</a>
241 
242    FOREACHelem_( set )-
243      iterate elements in a set
244 
245    declare:
246      void *elem, *elemp;
247 
248    each iteration:
249      elem is set element
250      elemp is one beyond
251 
252    to repeat an element:
253      elemp--; / *repeat* /
254 
255    at exit:
256      elem == NULL at end of loop
257 
258    example:
259      FOREACHelem_(set) {
260 
261    notes:
262      WARNING: needs braces if nested inside another FOREACH
263 */
264 #define FOREACHelem_(set) FOREACHsetelement_(void, set, elem)
265 
266 /*-<a                                 href="qh-set.htm#TOC"
267   >-----------------------------------</a><a name="FOREACHset_">-</a>
268 
269    FOREACHset_( set )-
270      iterate a set of sets
271 
272    declare:
273      setT *set, **setp;
274 
275    each iteration:
276      set is set element
277      setp is one beyond
278 
279    to repeat an element:
280      setp--; / *repeat* /
281 
282    at exit:
283      set == NULL at end of loop
284 
285    example
286      FOREACHset_(sets) {
287 
288    notes:
289      WARNING: needs braces if nested inside another FOREACH
290 */
291 #define FOREACHset_(sets) FOREACHsetelement_(setT, sets, set)
292 
293 /*-<a                                       href="qh-set.htm#TOC"
294   >-----------------------------------------</a><a name="SETindex_">-</a>
295 
296    SETindex_( set, elem )
297      return index of elem in set
298 
299    notes:
300      for use with FOREACH iteration
301      WARN64 -- Maximum set size is 2G
302 
303    example:
304      i= SETindex_(ridges, ridge)
305 */
306 #define SETindex_(set, elem) ((int)((void **)elem##p - (void **)&(set)->e[1].p))
307 
308 /*-<a                                     href="qh-set.htm#TOC"
309   >---------------------------------------</a><a name="SETref_">-</a>
310 
311    SETref_( elem )
312      l.h.s. for modifying the current element in a FOREACH iteration
313 
314    example:
315      SETref_(ridge)= anotherridge;
316 */
317 #define SETref_(elem) (elem##p[-1])
318 
319 /*-<a                                     href="qh-set.htm#TOC"
320   >---------------------------------------</a><a name="SETelem_">-</a>
321 
322    SETelem_(set, n)
323      return the n'th element of set
324 
325    notes:
326       assumes that n is valid [0..size] and that set is defined
327       use SETelemt_() for type cast
328 */
329 #define SETelem_(set, n)           ((set)->e[n].p)
330 
331 /*-<a                                     href="qh-set.htm#TOC"
332   >---------------------------------------</a><a name="SETelemt_">-</a>
333 
334    SETelemt_(set, n, type)
335      return the n'th element of set as a type
336 
337    notes:
338       assumes that n is valid [0..size] and that set is defined
339 */
340 #define SETelemt_(set, n, type)    ((type*)((set)->e[n].p))
341 
342 /*-<a                                     href="qh-set.htm#TOC"
343   >---------------------------------------</a><a name="SETelemaddr_">-</a>
344 
345    SETelemaddr_(set, n, type)
346      return address of the n'th element of a set
347 
348    notes:
349       assumes that n is valid [0..size] and set is defined
350 */
351 #define SETelemaddr_(set, n, type) ((type **)(&((set)->e[n].p)))
352 
353 /*-<a                                     href="qh-set.htm#TOC"
354   >---------------------------------------</a><a name="SETfirst_">-</a>
355 
356    SETfirst_(set)
357      return first element of set
358 
359 */
360 #define SETfirst_(set)             ((set)->e[0].p)
361 
362 /*-<a                                     href="qh-set.htm#TOC"
363   >---------------------------------------</a><a name="SETfirstt_">-</a>
364 
365    SETfirstt_(set, type)
366      return first element of set as a type
367 
368 */
369 #define SETfirstt_(set, type)      ((type*)((set)->e[0].p))
370 
371 /*-<a                                     href="qh-set.htm#TOC"
372   >---------------------------------------</a><a name="SETsecond_">-</a>
373 
374    SETsecond_(set)
375      return second element of set
376 
377 */
378 #define SETsecond_(set)            ((set)->e[1].p)
379 
380 /*-<a                                     href="qh-set.htm#TOC"
381   >---------------------------------------</a><a name="SETsecondt_">-</a>
382 
383    SETsecondt_(set, type)
384      return second element of set as a type
385 */
386 #define SETsecondt_(set, type)     ((type*)((set)->e[1].p))
387 
388 /*-<a                                     href="qh-set.htm#TOC"
389   >---------------------------------------</a><a name="SETaddr_">-</a>
390 
391    SETaddr_(set, type)
392        return address of set's elements
393 */
394 #define SETaddr_(set,type)         ((type **)(&((set)->e[0].p)))
395 
396 /*-<a                                     href="qh-set.htm#TOC"
397   >---------------------------------------</a><a name="SETreturnsize_">-</a>
398 
399    SETreturnsize_(set, size)
400      return size of a set
401 
402    notes:
403       set must be defined
404       use qh_setsize(set) unless speed is critical
405 */
406 #define SETreturnsize_(set, size) (((size)= ((set)->e[(set)->maxsize].i))?(--(size)):((size)= (set)->maxsize))
407 
408 /*-<a                                     href="qh-set.htm#TOC"
409   >---------------------------------------</a><a name="SETempty_">-</a>
410 
411    SETempty_(set)
412      return true(1) if set is empty
413 
414    notes:
415       set may be NULL
416 */
417 #define SETempty_(set)            (!set || (SETfirst_(set) ? 0 : 1))
418 
419 /*-<a                             href="qh-set.htm#TOC"
420   >-------------------------------<a name="SETsizeaddr_">-</a>
421 
422   SETsizeaddr_(set)
423     return pointer to 'actual size+1' of set (set CANNOT be NULL!!)
424     Its type is setelemT* for strict aliasing
425     All SETelemaddr_ must be cast to setelemT
426 
427 
428   notes:
429     *SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL
430 */
431 #define SETsizeaddr_(set) (&((set)->e[(set)->maxsize]))
432 
433 /*-<a                                     href="qh-set.htm#TOC"
434   >---------------------------------------</a><a name="SETtruncate_">-</a>
435 
436    SETtruncate_(set, size)
437      truncate set to size
438 
439    see:
440      qh_settruncate()
441 
442 */
443 #define SETtruncate_(set, size) {set->e[set->maxsize].i= size+1; /* maybe overwritten */ \
444       set->e[size].p= NULL;}
445 
446 /*======= prototypes in alphabetical order ============*/
447 
448 void  qh_setaddsorted(setT **setp, void *elem);
449 void  qh_setaddnth(setT **setp, int nth, void *newelem);
450 void  qh_setappend(setT **setp, void *elem);
451 void  qh_setappend_set(setT **setp, setT *setA);
452 void  qh_setappend2ndlast(setT **setp, void *elem);
453 void  qh_setcheck(setT *set, const char *tname, unsigned id);
454 void  qh_setcompact(setT *set);
455 setT *qh_setcopy(setT *set, int extra);
456 void *qh_setdel(setT *set, void *elem);
457 void *qh_setdellast(setT *set);
458 void *qh_setdelnth(setT *set, int nth);
459 void *qh_setdelnthsorted(setT *set, int nth);
460 void *qh_setdelsorted(setT *set, void *newelem);
461 setT *qh_setduplicate( setT *set, int elemsize);
462 int   qh_setequal(setT *setA, setT *setB);
463 int   qh_setequal_except(setT *setA, void *skipelemA, setT *setB, void *skipelemB);
464 int   qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB);
465 void **qh_setendpointer(setT *set);
466 void  qh_setfree(setT **set);
467 void  qh_setfree2( setT **setp, int elemsize);
468 void  qh_setfreelong(setT **set);
469 int   qh_setin(setT *set, void *setelem);
470 int   qh_setindex(setT *set, void *setelem);
471 void  qh_setlarger(setT **setp);
472 void *qh_setlast(setT *set);
473 setT *qh_setnew(int size);
474 setT *qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend);
475 void  qh_setprint(FILE *fp, const char* string, setT *set);
476 void  qh_setreplace(setT *set, void *oldelem, void *newelem);
477 int   qh_setsize(setT *set);
478 setT *qh_settemp(int setsize);
479 void  qh_settempfree(setT **set);
480 void  qh_settempfree_all(void);
481 setT *qh_settemppop(void);
482 void  qh_settemppush(setT *set);
483 void  qh_settruncate(setT *set, int size);
484 int   qh_setunique(setT **set, void *elem);
485 void  qh_setzero(setT *set, int idx, int size);
486 
487 
488 #endif /* qhDEFset */
489