00001 /*<html><pre> -<a href="qh-set.htm" 00002 >-------------------------------</a><a name="TOP">-</a> 00003 00004 qset.h 00005 header file for qset.c that implements set 00006 00007 see qh-set.htm and qset.c 00008 00009 only uses mem.c, malloc/free 00010 00011 for error handling, writes message and calls 00012 qh_errexit (qhmem_ERRqhull, NULL, NULL); 00013 00014 set operations satisfy the following properties: 00015 - sets have a max size, the actual size (if different) is stored at the end 00016 - every set is NULL terminated 00017 - sets may be sorted or unsorted, the caller must distinguish this 00018 00019 copyright (c) 1993-2003, The Geometry Center 00020 */ 00021 00022 #ifndef qhDEFset 00023 #define qhDEFset 1 00024 00025 /*================= -structures- ===============*/ 00026 00027 #ifndef DEFsetT 00028 #define DEFsetT 1 00029 typedef struct setT setT; /* a set is a sorted or unsorted array of pointers */ 00030 #endif 00031 00032 /*-<a href="qh-set.htm#TOC" 00033 >----------------------------------------</a><a name="setT">-</a> 00034 00035 setT 00036 a set or list of pointers with maximum size and actual size. 00037 00038 variations: 00039 unsorted, unique -- a list of unique pointers with NULL terminator 00040 user guarantees uniqueness 00041 sorted -- a sorted list of unique pointers with NULL terminator 00042 qset.c guarantees uniqueness 00043 unsorted -- a list of pointers terminated with NULL 00044 indexed -- an array of pointers with NULL elements 00045 00046 structure for set of n elements: 00047 00048 -------------- 00049 | maxsize 00050 -------------- 00051 | e[0] - a pointer, may be NULL for indexed sets 00052 -------------- 00053 | e[1] 00054 00055 -------------- 00056 | ... 00057 -------------- 00058 | e[n-1] 00059 -------------- 00060 | e[n] = NULL 00061 -------------- 00062 | ... 00063 -------------- 00064 | e[maxsize] - n+1 or NULL (determines actual size of set) 00065 -------------- 00066 00067 */ 00068 00069 /*-- setelemT -- internal type to allow both pointers and indices 00070 */ 00071 typedef union setelemT setelemT; 00072 union setelemT { 00073 void *p; 00074 int i; /* integer used for e[maxSize] */ 00075 }; 00076 00077 struct setT { 00078 int maxsize; /* maximum number of elements (except NULL) */ 00079 setelemT e[1]; /* array of pointers, tail is NULL */ 00080 /* last slot (unless NULL) is actual size+1 00081 e[maxsize]==NULL or e[e[maxsize]-1]==NULL */ 00082 /* this may generate a warning since e[] contains 00083 maxsize elements */ 00084 }; 00085 00086 /*=========== -constants- =========================*/ 00087 00088 /*-<a href="qh-set.htm#TOC" 00089 >-----------------------------------</a><a name="SETelemsize">-</a> 00090 00091 SETelemsize 00092 size of a set element in bytes 00093 */ 00094 #define SETelemsize sizeof(setelemT) 00095 00096 00097 /*=========== -macros- =========================*/ 00098 00099 /*-<a href="qh-set.htm#TOC" 00100 >-----------------------------------</a><a name="FOREACHsetelement_">-</a> 00101 00102 FOREACHsetelement_(type, set, variable) 00103 define FOREACH iterator 00104 00105 declare: 00106 assumes *variable and **variablep are declared 00107 no space in "variable)" [DEC Alpha cc compiler] 00108 00109 each iteration: 00110 variable is set element 00111 variablep is one beyond variable. 00112 00113 to repeat an element: 00114 variablep--; / *repeat* / 00115 00116 at exit: 00117 variable is NULL at end of loop 00118 00119 example: 00120 #define FOREACHfacet_( facets ) FOREACHsetelement_( facetT, facets, facet ) 00121 00122 notes: 00123 use FOREACHsetelement_i_() if need index or include NULLs 00124 00125 WARNING: 00126 nested loops can't use the same variable (define another FOREACH) 00127 00128 needs braces if nested inside another FOREACH 00129 this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} ) 00130 */ 00131 #define FOREACHsetelement_(type, set, variable) \ 00132 if (((variable= NULL), set)) for(\ 00133 variable##p= (type **)&((set)->e[0].p); \ 00134 (variable= *variable##p++);) 00135 00136 /*-<a href="qh-set.htm#TOC" 00137 >----------------------------------------</a><a name="FOREACHsetelement_i_">-</a> 00138 00139 FOREACHsetelement_i_(type, set, variable) 00140 define indexed FOREACH iterator 00141 00142 declare: 00143 type *variable, variable_n, variable_i; 00144 00145 each iteration: 00146 variable is set element, may be NULL 00147 variable_i is index, variable_n is qh_setsize() 00148 00149 to repeat an element: 00150 variable_i--; variable_n-- repeats for deleted element 00151 00152 at exit: 00153 variable==NULL and variable_i==variable_n 00154 00155 example: 00156 #define FOREACHfacet_i_( facets ) FOREACHsetelement_i_( facetT, facets, facet ) 00157 00158 WARNING: 00159 nested loops can't use the same variable (define another FOREACH) 00160 00161 needs braces if nested inside another FOREACH 00162 this includes intervening blocks, e.g. FOREACH...{ if () FOREACH...} ) 00163 */ 00164 #define FOREACHsetelement_i_(type, set, variable) \ 00165 if (((variable= NULL), set)) for (\ 00166 variable##_i= 0, variable= (type *)((set)->e[0].p), \ 00167 variable##_n= qh_setsize(set);\ 00168 variable##_i < variable##_n;\ 00169 variable= (type *)((set)->e[++variable##_i].p) ) 00170 00171 /*-<a href="qh-set.htm#TOC" 00172 >--------------------------------------</a><a name="FOREACHsetelementreverse_">-</a> 00173 00174 FOREACHsetelementreverse_(type, set, variable)- 00175 define FOREACH iterator in reverse order 00176 00177 declare: 00178 assumes *variable and **variablep are declared 00179 also declare 'int variabletemp' 00180 00181 each iteration: 00182 variable is set element 00183 00184 to repeat an element: 00185 variabletemp++; / *repeat* / 00186 00187 at exit: 00188 variable is NULL 00189 00190 example: 00191 #define FOREACHvertexreverse_( vertices ) FOREACHsetelementreverse_( vertexT, vertices, vertex ) 00192 00193 notes: 00194 use FOREACHsetelementreverse12_() to reverse first two elements 00195 WARNING: needs braces if nested inside another FOREACH 00196 */ 00197 #define FOREACHsetelementreverse_(type, set, variable) \ 00198 if (((variable= NULL), set)) for(\ 00199 variable##temp= qh_setsize(set)-1, variable= qh_setlast(set);\ 00200 variable; variable= \ 00201 ((--variable##temp >= 0) ? SETelemt_(set, variable##temp, type) : NULL)) 00202 00203 /*-<a href="qh-set.htm#TOC" 00204 >-----------------------------------</a><a name="FOREACHsetelementreverse12_">-</a> 00205 00206 FOREACHsetelementreverse12_(type, set, variable)- 00207 define FOREACH iterator with e[1] and e[0] reversed 00208 00209 declare: 00210 assumes *variable and **variablep are declared 00211 00212 each iteration: 00213 variable is set element 00214 variablep is one after variable. 00215 00216 to repeat an element: 00217 variablep--; / *repeat* / 00218 00219 at exit: 00220 variable is NULL at end of loop 00221 00222 example 00223 #define FOREACHvertexreverse12_( vertices ) FOREACHsetelementreverse12_( vertexT, vertices, vertex ) 00224 00225 notes: 00226 WARNING: needs braces if nested inside another FOREACH 00227 */ 00228 #define FOREACHsetelementreverse12_(type, set, variable) \ 00229 if (((variable= NULL), set)) for(\ 00230 variable##p= (type **)&((set)->e[1].p); \ 00231 (variable= *variable##p); \ 00232 variable##p == ((type **)&((set)->e[0].p))?variable##p += 2: \ 00233 (variable##p == ((type **)&((set)->e[1].p))?variable##p--:variable##p++)) 00234 00235 /*-<a href="qh-set.htm#TOC" 00236 >-----------------------------------</a><a name="FOREACHelem_">-</a> 00237 00238 FOREACHelem_( set )- 00239 iterate elements in a set 00240 00241 declare: 00242 void *elem, *elemp; 00243 00244 each iteration: 00245 elem is set element 00246 elemp is one beyond 00247 00248 to repeat an element: 00249 elemp--; / *repeat* / 00250 00251 at exit: 00252 elem == NULL at end of loop 00253 00254 example: 00255 FOREACHelem_(set) { 00256 00257 notes: 00258 WARNING: needs braces if nested inside another FOREACH 00259 */ 00260 #define FOREACHelem_(set) FOREACHsetelement_(void, set, elem) 00261 00262 /*-<a href="qh-set.htm#TOC" 00263 >-----------------------------------</a><a name="FOREACHset_">-</a> 00264 00265 FOREACHset_( set )- 00266 iterate a set of sets 00267 00268 declare: 00269 setT *set, **setp; 00270 00271 each iteration: 00272 set is set element 00273 setp is one beyond 00274 00275 to repeat an element: 00276 setp--; / *repeat* / 00277 00278 at exit: 00279 set == NULL at end of loop 00280 00281 example 00282 FOREACHset_(sets) { 00283 00284 notes: 00285 WARNING: needs braces if nested inside another FOREACH 00286 */ 00287 #define FOREACHset_(sets) FOREACHsetelement_(setT, sets, set) 00288 00289 /*-<a href="qh-set.htm#TOC" 00290 >-----------------------------------------</a><a name="SETindex_">-</a> 00291 00292 SETindex_( set, elem ) 00293 return index of elem in set 00294 00295 notes: 00296 for use with FOREACH iteration 00297 00298 example: 00299 i= SETindex_(ridges, ridge) 00300 */ 00301 #define SETindex_(set, elem) ((void **)elem##p - (void **)&(set)->e[1].p) 00302 00303 /*-<a href="qh-set.htm#TOC" 00304 >---------------------------------------</a><a name="SETref_">-</a> 00305 00306 SETref_( elem ) 00307 l.h.s. for modifying the current element in a FOREACH iteration 00308 00309 example: 00310 SETref_(ridge)= anotherridge; 00311 */ 00312 #define SETref_(elem) (elem##p[-1]) 00313 00314 /*-<a href="qh-set.htm#TOC" 00315 >---------------------------------------</a><a name="SETelem_">-</a> 00316 00317 SETelem_(set, n) 00318 return the n'th element of set 00319 00320 notes: 00321 assumes that n is valid [0..size] and that set is defined 00322 use SETelemt_() for type cast 00323 */ 00324 #define SETelem_(set, n) ((set)->e[n].p) 00325 00326 /*-<a href="qh-set.htm#TOC" 00327 >---------------------------------------</a><a name="SETelemt_">-</a> 00328 00329 SETelemt_(set, n, type) 00330 return the n'th element of set as a type 00331 00332 notes: 00333 assumes that n is valid [0..size] and that set is defined 00334 */ 00335 #define SETelemt_(set, n, type) ((type*)((set)->e[n].p)) 00336 00337 /*-<a href="qh-set.htm#TOC" 00338 >---------------------------------------</a><a name="SETelemaddr_">-</a> 00339 00340 SETelemaddr_(set, n, type) 00341 return address of the n'th element of a set 00342 00343 notes: 00344 assumes that n is valid [0..size] and set is defined 00345 */ 00346 #define SETelemaddr_(set, n, type) ((type **)(&((set)->e[n].p))) 00347 00348 /*-<a href="qh-set.htm#TOC" 00349 >---------------------------------------</a><a name="SETfirst_">-</a> 00350 00351 SETfirst_(set) 00352 return first element of set 00353 00354 */ 00355 #define SETfirst_(set) ((set)->e[0].p) 00356 00357 /*-<a href="qh-set.htm#TOC" 00358 >---------------------------------------</a><a name="SETfirstt_">-</a> 00359 00360 SETfirstt_(set, type) 00361 return first element of set as a type 00362 00363 */ 00364 #define SETfirstt_(set, type) ((type*)((set)->e[0].p)) 00365 00366 /*-<a href="qh-set.htm#TOC" 00367 >---------------------------------------</a><a name="SETsecond_">-</a> 00368 00369 SETsecond_(set) 00370 return second element of set 00371 00372 */ 00373 #define SETsecond_(set) ((set)->e[1].p) 00374 00375 /*-<a href="qh-set.htm#TOC" 00376 >---------------------------------------</a><a name="SETsecondt_">-</a> 00377 00378 SETsecondt_(set, type) 00379 return second element of set as a type 00380 */ 00381 #define SETsecondt_(set, type) ((type*)((set)->e[1].p)) 00382 00383 /*-<a href="qh-set.htm#TOC" 00384 >---------------------------------------</a><a name="SETaddr_">-</a> 00385 00386 SETaddr_(set, type) 00387 return address of set's elements 00388 */ 00389 #define SETaddr_(set,type) ((type **)(&((set)->e[0].p))) 00390 00391 /*-<a href="qh-set.htm#TOC" 00392 >---------------------------------------</a><a name="SETreturnsize_">-</a> 00393 00394 SETreturnsize_(set, size) 00395 return size of a set 00396 00397 notes: 00398 set must be defined 00399 use qh_setsize(set) unless speed is critical 00400 */ 00401 #define SETreturnsize_(set, size) (((size)= ((set)->e[(set)->maxsize].i))?(--(size)):((size)= (set)->maxsize)) 00402 00403 /*-<a href="qh-set.htm#TOC" 00404 >---------------------------------------</a><a name="SETempty_">-</a> 00405 00406 SETempty_(set) 00407 return true (1) if set is empty 00408 00409 notes: 00410 set may be NULL 00411 */ 00412 #define SETempty_(set) (!set || (SETfirst_(set) ? 0:1)) 00413 00414 /*-<a href="qh-set.htm#TOC" 00415 >---------------------------------------</a><a name="SETtruncate_">-</a> 00416 00417 SETtruncate_(set) 00418 return first element of set 00419 00420 see: 00421 qh_settruncate() 00422 00423 */ 00424 #define SETtruncate_(set, size) {set->e[set->maxsize].i= size+1; /* maybe overwritten */ \ 00425 set->e[size].p= NULL;} 00426 00427 /*======= prototypes in alphabetical order ============*/ 00428 00429 void qh_setaddsorted(setT **setp, void *elem); 00430 void qh_setaddnth(setT **setp, int nth, void *newelem); 00431 void qh_setappend(setT **setp, void *elem); 00432 void qh_setappend_set(setT **setp, setT *setA); 00433 void qh_setappend2ndlast(setT **setp, void *elem); 00434 void qh_setcheck(setT *set, char *tname, int id); 00435 void qh_setcompact(setT *set); 00436 setT *qh_setcopy(setT *set, int extra); 00437 void *qh_setdel(setT *set, void *elem); 00438 void *qh_setdellast(setT *set); 00439 void *qh_setdelnth(setT *set, int nth); 00440 void *qh_setdelnthsorted(setT *set, int nth); 00441 void *qh_setdelsorted(setT *set, void *newelem); 00442 setT *qh_setduplicate( setT *set, int elemsize); 00443 int qh_setequal(setT *setA, setT *setB); 00444 int qh_setequal_except (setT *setA, void *skipelemA, setT *setB, void *skipelemB); 00445 int qh_setequal_skip (setT *setA, int skipA, setT *setB, int skipB); 00446 void qh_setfree(setT **set); 00447 void qh_setfree2( setT **setp, int elemsize); 00448 void qh_setfreelong(setT **set); 00449 int qh_setin(setT *set, void *setelem); 00450 int qh_setindex(setT *set, void *setelem); 00451 void qh_setlarger(setT **setp); 00452 void *qh_setlast(setT *set); 00453 setT *qh_setnew(int size); 00454 setT *qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend); 00455 void qh_setprint(FILE *fp, char* string, setT *set); 00456 void qh_setreplace(setT *set, void *oldelem, void *newelem); 00457 int qh_setsize(setT *set); 00458 setT *qh_settemp(int setsize); 00459 void qh_settempfree(setT **set); 00460 void qh_settempfree_all(void); 00461 setT *qh_settemppop(void); 00462 void qh_settemppush(setT *set); 00463 void qh_settruncate (setT *set, int size); 00464 int qh_setunique (setT **set, void *elem); 00465 void qh_setzero (setT *set, int index, int size); 00466 00467 00468 #endif /* qhDEFset */
1.7.1