| 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-2003, 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 |
please 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 |
please 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 |
please 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 |
please 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; \ |
| 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 */ |
