Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Analysis.AlgorithmBehavior/qhull-2012.1/src/libqhull/qset.h @ 11303

Last change on this file since 11303 was 10207, checked in by ascheibe, 11 years ago

#1886 added a unit test for volume calculation and the qhull library
File size: 15.0 KB
Line 
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
33typedef 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
39setT
40  a set or list of pointers with maximum size and actual size.
41
42variations:
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
50structure 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*/
75typedef union setelemT setelemT;
76union setelemT {
77  void    *p;
78  int      i;         /* integer used for e[maxSize] */
79};
80
81struct 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
448void  qh_setaddsorted(setT **setp, void *elem);
449void  qh_setaddnth(setT **setp, int nth, void *newelem);
450void  qh_setappend(setT **setp, void *elem);
451void  qh_setappend_set(setT **setp, setT *setA);
452void  qh_setappend2ndlast(setT **setp, void *elem);
453void  qh_setcheck(setT *set, const char *tname, unsigned id);
454void  qh_setcompact(setT *set);
455setT *qh_setcopy(setT *set, int extra);
456void *qh_setdel(setT *set, void *elem);
457void *qh_setdellast(setT *set);
458void *qh_setdelnth(setT *set, int nth);
459void *qh_setdelnthsorted(setT *set, int nth);
460void *qh_setdelsorted(setT *set, void *newelem);
461setT *qh_setduplicate( setT *set, int elemsize);
462int   qh_setequal(setT *setA, setT *setB);
463int   qh_setequal_except(setT *setA, void *skipelemA, setT *setB, void *skipelemB);
464int   qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB);
465void **qh_setendpointer(setT *set);
466void  qh_setfree(setT **set);
467void  qh_setfree2( setT **setp, int elemsize);
468void  qh_setfreelong(setT **set);
469int   qh_setin(setT *set, void *setelem);
470int   qh_setindex(setT *set, void *setelem);
471void  qh_setlarger(setT **setp);
472void *qh_setlast(setT *set);
473setT *qh_setnew(int size);
474setT *qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend);
475void  qh_setprint(FILE *fp, const char* string, setT *set);
476void  qh_setreplace(setT *set, void *oldelem, void *newelem);
477int   qh_setsize(setT *set);
478setT *qh_settemp(int setsize);
479void  qh_settempfree(setT **set);
480void  qh_settempfree_all(void);
481setT *qh_settemppop(void);
482void  qh_settemppush(setT *set);
483void  qh_settruncate(setT *set, int size);
484int   qh_setunique(setT **set, void *elem);
485void  qh_setzero(setT *set, int idx, int size);
486
487
488#endif /* qhDEFset */
Note: See TracBrowser for help on using the repository browser.