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