graspit: qset.c Source File

00001 /*<html><pre>  -<a                             href="qh-set.htm"
00002   >-------------------------------</a><a name="TOP">-</a>
00003 
00004    qset.c
00005    implements set manipulations needed for quickhull
00006 
00007    see qh-set.htm and qset.h
00008 
00009    Be careful of strict aliasing (two pointers of different types
00010    that reference the same location).  The last slot of a set is
00011    either the actual size of the set plus 1, or the NULL terminator
00012    of the set (i.e., setelemT).
00013 
00014    Copyright (c) 1993-2012 The Geometry Center.
00015    $Id: //main/2011/qhull/src/libqhull/qset.c#6 $$Change: 1475 $
00016    $DateTime: 2012/01/27 22:32:16 $$Author: bbarber $
00017 */
00018 
00019 #include "qset.h"
00020 #include "mem.h"
00021 #include <stdio.h>
00022 #include <string.h>
00023 /*** uncomment here and qhull_a.h
00024      if string.h does not define memcpy()
00025 #include <memory.h>
00026 */
00027 
00028 #ifndef qhDEFlibqhull
00029 typedef struct ridgeT ridgeT;
00030 typedef struct facetT facetT;
00031 void    qh_errexit(int exitcode, facetT *, ridgeT *);
00032 void    qh_fprintf(FILE *fp, int msgcode, const char *fmt, ... );
00033 #  ifdef _MSC_VER  /* Microsoft Visual C++ -- warning level 4 */
00034 #  pragma warning( disable : 4127)  /* conditional expression is constant */
00035 #  pragma warning( disable : 4706)  /* assignment within conditional function */
00036 #  endif
00037 #endif
00038 
00039 /*=============== internal macros ===========================*/
00040 
00041 /*============ functions in alphabetical order ===================*/
00042 
00043 /*-<a                             href="qh-set.htm#TOC"
00044   >--------------------------------<a name="setaddnth">-</a>
00045 
00046   qh_setaddnth( setp, nth, newelem)
00047     adds newelem as n'th element of sorted or unsorted *setp
00048 
00049   notes:
00050     *setp and newelem must be defined
00051     *setp may be a temp set
00052     nth=0 is first element
00053     errors if nth is out of bounds
00054 
00055   design:
00056     expand *setp if empty or full
00057     move tail of *setp up one
00058     insert newelem
00059 */
00060 void qh_setaddnth(setT **setp, int nth, void *newelem) {
00061   int oldsize, i;
00062   setelemT *sizep;          /* avoid strict aliasing */
00063   setelemT *oldp, *newp;
00064 
00065   if (!*setp || (sizep= SETsizeaddr_(*setp))->i==0) {
00066     qh_setlarger(setp);
00067     sizep= SETsizeaddr_(*setp);
00068   }
00069   oldsize= sizep->i - 1;
00070   if (nth < 0 || nth > oldsize) {
00071     qh_fprintf(qhmem.ferr, 6171, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
00072     qh_setprint(qhmem.ferr, "", *setp);
00073     qh_errexit(qhmem_ERRqhull, NULL, NULL);
00074   }
00075   sizep->i++;
00076   oldp= (setelemT *)SETelemaddr_(*setp, oldsize, void);   /* NULL */
00077   newp= oldp+1;
00078   for (i=oldsize-nth+1; i--; )  /* move at least NULL  */
00079     (newp--)->p= (oldp--)->p;       /* may overwrite *sizep */
00080   newp->p= newelem;
00081 } /* setaddnth */
00082 
00083 
00084 /*-<a                              href="qh-set.htm#TOC"
00085   >--------------------------------<a name="setaddsorted">-</a>
00086 
00087   setaddsorted( setp, newelem )
00088     adds an newelem into sorted *setp
00089 
00090   notes:
00091     *setp and newelem must be defined
00092     *setp may be a temp set
00093     nop if newelem already in set
00094 
00095   design:
00096     find newelem's position in *setp
00097     insert newelem
00098 */
00099 void qh_setaddsorted(setT **setp, void *newelem) {
00100   int newindex=0;
00101   void *elem, **elemp;
00102 
00103   FOREACHelem_(*setp) {          /* could use binary search instead */
00104     if (elem < newelem)
00105       newindex++;
00106     else if (elem == newelem)
00107       return;
00108     else
00109       break;
00110   }
00111   qh_setaddnth(setp, newindex, newelem);
00112 } /* setaddsorted */
00113 
00114 
00115 /*-<a                             href="qh-set.htm#TOC"
00116   >-------------------------------<a name="setappend">-</a>
00117 
00118   qh_setappend( setp, newelem)
00119     append newelem to *setp
00120 
00121   notes:
00122     *setp may be a temp set
00123     *setp and newelem may be NULL
00124 
00125   design:
00126     expand *setp if empty or full
00127     append newelem to *setp
00128 
00129 */
00130 void qh_setappend(setT **setp, void *newelem) {
00131   setelemT *sizep;  /* Avoid strict aliasing.  Writing to *endp may overwrite *sizep */
00132   setelemT *endp;
00133   int count;
00134 
00135   if (!newelem)
00136     return;
00137   if (!*setp || (sizep= SETsizeaddr_(*setp))->i==0) {
00138     qh_setlarger(setp);
00139     sizep= SETsizeaddr_(*setp);
00140   }
00141   count= (sizep->i)++ - 1;
00142   endp= (setelemT *)SETelemaddr_(*setp, count, void);
00143   (endp++)->p= newelem;
00144   endp->p= NULL;
00145 } /* setappend */
00146 
00147 /*-<a                             href="qh-set.htm#TOC"
00148   >-------------------------------<a name="setappend_set">-</a>
00149 
00150   qh_setappend_set( setp, setA)
00151     appends setA to *setp
00152 
00153   notes:
00154     *setp can not be a temp set
00155     *setp and setA may be NULL
00156 
00157   design:
00158     setup for copy
00159     expand *setp if it is too small
00160     append all elements of setA to *setp
00161 */
00162 void qh_setappend_set(setT **setp, setT *setA) {
00163   int sizeA, size;
00164   setT *oldset;
00165   setelemT *sizep;
00166 
00167   if (!setA)
00168     return;
00169   SETreturnsize_(setA, sizeA);
00170   if (!*setp)
00171     *setp= qh_setnew(sizeA);
00172   sizep= SETsizeaddr_(*setp);
00173   if (!(size= sizep->i))
00174     size= (*setp)->maxsize;
00175   else
00176     size--;
00177   if (size + sizeA > (*setp)->maxsize) {
00178     oldset= *setp;
00179     *setp= qh_setcopy(oldset, sizeA);
00180     qh_setfree(&oldset);
00181     sizep= SETsizeaddr_(*setp);
00182   }
00183   if (sizeA > 0) {
00184     sizep->i= size+sizeA+1;   /* memcpy may overwrite */
00185     memcpy((char *)&((*setp)->e[size].p), (char *)&(setA->e[0].p), (size_t)(sizeA+1) * SETelemsize);
00186   }
00187 } /* setappend_set */
00188 
00189 
00190 /*-<a                             href="qh-set.htm#TOC"
00191   >-------------------------------<a name="setappend2ndlast">-</a>
00192 
00193   qh_setappend2ndlast( setp, newelem )
00194     makes newelem the next to the last element in *setp
00195 
00196   notes:
00197     *setp must have at least one element
00198     newelem must be defined
00199     *setp may be a temp set
00200 
00201   design:
00202     expand *setp if empty or full
00203     move last element of *setp up one
00204     insert newelem
00205 */
00206 void qh_setappend2ndlast(setT **setp, void *newelem) {
00207     setelemT *sizep;  /* Avoid strict aliasing.  Writing to *endp may overwrite *sizep */
00208     setelemT *endp, *lastp;
00209     int count;
00210 
00211     if (!*setp || (sizep= SETsizeaddr_(*setp))->i==0) {
00212         qh_setlarger(setp);
00213         sizep= SETsizeaddr_(*setp);
00214     }
00215     count= (sizep->i)++ - 1;
00216     endp= (setelemT *)SETelemaddr_(*setp, count, void); /* NULL */
00217     lastp= endp-1;
00218     *(endp++)= *lastp;
00219     endp->p= NULL;    /* may overwrite *sizep */
00220     lastp->p= newelem;
00221 } /* setappend2ndlast */
00222 
00223 /*-<a                             href="qh-set.htm#TOC"
00224   >-------------------------------<a name="setcheck">-</a>
00225 
00226   qh_setcheck( set, typename, id )
00227     check set for validity
00228     report errors with typename and id
00229 
00230   design:
00231     checks that maxsize, actual size, and NULL terminator agree
00232 */
00233 void qh_setcheck(setT *set, const char *tname, unsigned id) {
00234   int maxsize, size;
00235   int waserr= 0;
00236 
00237   if (!set)
00238     return;
00239   SETreturnsize_(set, size);
00240   maxsize= set->maxsize;
00241   if (size > maxsize || !maxsize) {
00242     qh_fprintf(qhmem.ferr, 6172, "qhull internal error (qh_setcheck): actual size %d of %s%d is greater than max size %d\n",
00243              size, tname, id, maxsize);
00244     waserr= 1;
00245   }else if (set->e[size].p) {
00246     qh_fprintf(qhmem.ferr, 6173, "qhull internal error (qh_setcheck): %s%d(size %d max %d) is not null terminated.\n",
00247              tname, id, size-1, maxsize);
00248     waserr= 1;
00249   }
00250   if (waserr) {
00251     qh_setprint(qhmem.ferr, "ERRONEOUS", set);
00252     qh_errexit(qhmem_ERRqhull, NULL, NULL);
00253   }
00254 } /* setcheck */
00255 
00256 
00257 /*-<a                             href="qh-set.htm#TOC"
00258   >-------------------------------<a name="setcompact">-</a>
00259 
00260   qh_setcompact( set )
00261     remove internal NULLs from an unsorted set
00262 
00263   returns:
00264     updated set
00265 
00266   notes:
00267     set may be NULL
00268     it would be faster to swap tail of set into holes, like qh_setdel
00269 
00270   design:
00271     setup pointers into set
00272     skip NULLs while copying elements to start of set
00273     update the actual size
00274 */
00275 void qh_setcompact(setT *set) {
00276   int size;
00277   void **destp, **elemp, **endp, **firstp;
00278 
00279   if (!set)
00280     return;
00281   SETreturnsize_(set, size);
00282   destp= elemp= firstp= SETaddr_(set, void);
00283   endp= destp + size;
00284   while (1) {
00285     if (!(*destp++ = *elemp++)) {
00286       destp--;
00287       if (elemp > endp)
00288         break;
00289     }
00290   }
00291   qh_settruncate(set, (int)(destp-firstp));   /* WARN64 */
00292 } /* setcompact */
00293 
00294 
00295 /*-<a                             href="qh-set.htm#TOC"
00296   >-------------------------------<a name="setcopy">-</a>
00297 
00298   qh_setcopy( set, extra )
00299     make a copy of a sorted or unsorted set with extra slots
00300 
00301   returns:
00302     new set
00303 
00304   design:
00305     create a newset with extra slots
00306     copy the elements to the newset
00307 
00308 */
00309 setT *qh_setcopy(setT *set, int extra) {
00310   setT *newset;
00311   int size;
00312 
00313   if (extra < 0)
00314     extra= 0;
00315   SETreturnsize_(set, size);
00316   newset= qh_setnew(size+extra);
00317   SETsizeaddr_(newset)->i= size+1;    /* memcpy may overwrite */
00318   memcpy((char *)&(newset->e[0].p), (char *)&(set->e[0].p), (size_t)(size+1) * SETelemsize);
00319   return(newset);
00320 } /* setcopy */
00321 
00322 
00323 /*-<a                             href="qh-set.htm#TOC"
00324   >-------------------------------<a name="setdel">-</a>
00325 
00326   qh_setdel( set, oldelem )
00327     delete oldelem from an unsorted set
00328 
00329   returns:
00330     returns oldelem if found
00331     returns NULL otherwise
00332 
00333   notes:
00334     set may be NULL
00335     oldelem must not be NULL;
00336     only deletes one copy of oldelem in set
00337 
00338   design:
00339     locate oldelem
00340     update actual size if it was full
00341     move the last element to the oldelem's location
00342 */
00343 void *qh_setdel(setT *set, void *oldelem) {
00344   setelemT *sizep;
00345   setelemT *elemp;
00346   setelemT *lastp;
00347 
00348   if (!set)
00349     return NULL;
00350   elemp= (setelemT *)SETaddr_(set, void);
00351   while (elemp->p != oldelem && elemp->p)
00352     elemp++;
00353   if (elemp->p) {
00354     sizep= SETsizeaddr_(set);
00355     if (!(sizep->i)--)         /*  if was a full set */
00356       sizep->i= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */
00357     lastp= (setelemT *)SETelemaddr_(set, sizep->i-1, void);
00358     elemp->p= lastp->p;      /* may overwrite itself */
00359     lastp->p= NULL;
00360     return oldelem;
00361   }
00362   return NULL;
00363 } /* setdel */
00364 
00365 
00366 /*-<a                             href="qh-set.htm#TOC"
00367   >-------------------------------<a name="setdellast">-</a>
00368 
00369   qh_setdellast( set)
00370     return last element of set or NULL
00371 
00372   notes:
00373     deletes element from set
00374     set may be NULL
00375 
00376   design:
00377     return NULL if empty
00378     if full set
00379       delete last element and set actual size
00380     else
00381       delete last element and update actual size
00382 */
00383 void *qh_setdellast(setT *set) {
00384   int setsize;  /* actually, actual_size + 1 */
00385   int maxsize;
00386   setelemT *sizep;
00387   void *returnvalue;
00388 
00389   if (!set || !(set->e[0].p))
00390     return NULL;
00391   sizep= SETsizeaddr_(set);
00392   if ((setsize= sizep->i)) {
00393     returnvalue= set->e[setsize - 2].p;
00394     set->e[setsize - 2].p= NULL;
00395     sizep->i--;
00396   }else {
00397     maxsize= set->maxsize;
00398     returnvalue= set->e[maxsize - 1].p;
00399     set->e[maxsize - 1].p= NULL;
00400     sizep->i= maxsize;
00401   }
00402   return returnvalue;
00403 } /* setdellast */
00404 
00405 
00406 /*-<a                             href="qh-set.htm#TOC"
00407   >-------------------------------<a name="setdelnth">-</a>
00408 
00409   qh_setdelnth( set, nth )
00410     deletes nth element from unsorted set
00411     0 is first element
00412 
00413   returns:
00414     returns the element (needs type conversion)
00415 
00416   notes:
00417     errors if nth invalid
00418 
00419   design:
00420     setup points and check nth
00421     delete nth element and overwrite with last element
00422 */
00423 void *qh_setdelnth(setT *set, int nth) {
00424   void *elem;
00425   setelemT *sizep;
00426   setelemT *elemp, *lastp;
00427 
00428   elemp= (setelemT *)SETelemaddr_(set, nth, void);
00429   sizep= SETsizeaddr_(set);
00430   if ((sizep->i--)==0)         /*  if was a full set */
00431     sizep->i= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */
00432   if (nth < 0 || nth >= sizep->i) {
00433     qh_fprintf(qhmem.ferr, 6174, "qhull internal error (qh_setdelnth): nth %d is out-of-bounds for set:\n", nth);
00434     qh_setprint(qhmem.ferr, "", set);
00435     qh_errexit(qhmem_ERRqhull, NULL, NULL);
00436   }
00437   lastp= (setelemT *)SETelemaddr_(set, sizep->i-1, void);
00438   elem= elemp->p;
00439   elemp->p= lastp->p;      /* may overwrite itself */
00440   lastp->p= NULL;
00441   return elem;
00442 } /* setdelnth */
00443 
00444 /*-<a                             href="qh-set.htm#TOC"
00445   >-------------------------------<a name="setdelnthsorted">-</a>
00446 
00447   qh_setdelnthsorted( set, nth )
00448     deletes nth element from sorted set
00449 
00450   returns:
00451     returns the element (use type conversion)
00452 
00453   notes:
00454     errors if nth invalid
00455 
00456   see also:
00457     setnew_delnthsorted
00458 
00459   design:
00460     setup points and check nth
00461     copy remaining elements down one
00462     update actual size
00463 */
00464 void *qh_setdelnthsorted(setT *set, int nth) {
00465   void *elem;
00466   setelemT *sizep;
00467   setelemT *newp, *oldp;
00468 
00469   sizep= SETsizeaddr_(set);
00470   if (nth < 0 || (sizep->i && nth >= sizep->i-1) || nth >= set->maxsize) {
00471     qh_fprintf(qhmem.ferr, 6175, "qhull internal error (qh_setdelnthsorted): nth %d is out-of-bounds for set:\n", nth);
00472     qh_setprint(qhmem.ferr, "", set);
00473     qh_errexit(qhmem_ERRqhull, NULL, NULL);
00474   }
00475   newp= (setelemT *)SETelemaddr_(set, nth, void);
00476   elem= newp->p;
00477   oldp= newp+1;
00478   while (((newp++)->p= (oldp++)->p))
00479     ; /* copy remaining elements and NULL */
00480   if ((sizep->i--)==0)         /*  if was a full set */
00481     sizep->i= set->maxsize;  /*     *sizep= (max size-1)+ 1 */
00482   return elem;
00483 } /* setdelnthsorted */
00484 
00485 
00486 /*-<a                             href="qh-set.htm#TOC"
00487   >-------------------------------<a name="setdelsorted">-</a>
00488 
00489   qh_setdelsorted( set, oldelem )
00490     deletes oldelem from sorted set
00491 
00492   returns:
00493     returns oldelem if it was deleted
00494 
00495   notes:
00496     set may be NULL
00497 
00498   design:
00499     locate oldelem in set
00500     copy remaining elements down one
00501     update actual size
00502 */
00503 void *qh_setdelsorted(setT *set, void *oldelem) {
00504   setelemT *sizep;
00505   setelemT *newp, *oldp;
00506 
00507   if (!set)
00508     return NULL;
00509   newp= (setelemT *)SETaddr_(set, void);
00510   while(newp->p != oldelem && newp->p)
00511     newp++;
00512   if (newp->p) {
00513     oldp= newp+1;
00514     while (((newp++)->p= (oldp++)->p))
00515       ; /* copy remaining elements */
00516     sizep= SETsizeaddr_(set);
00517     if ((sizep->i--)==0)    /*  if was a full set */
00518       sizep->i= set->maxsize;  /*     *sizep= (max size-1)+ 1 */
00519     return oldelem;
00520   }
00521   return NULL;
00522 } /* setdelsorted */
00523 
00524 
00525 /*-<a                             href="qh-set.htm#TOC"
00526   >-------------------------------<a name="setduplicate">-</a>
00527 
00528   qh_setduplicate( set, elemsize )
00529     duplicate a set of elemsize elements
00530 
00531   notes:
00532     use setcopy if retaining old elements
00533 
00534   design:
00535     create a new set
00536     for each elem of the old set
00537       create a newelem
00538       append newelem to newset
00539 */
00540 setT *qh_setduplicate(setT *set, int elemsize) {
00541   void          *elem, **elemp, *newElem;
00542   setT          *newSet;
00543   int           size;
00544 
00545   if (!(size= qh_setsize(set)))
00546     return NULL;
00547   newSet= qh_setnew(size);
00548   FOREACHelem_(set) {
00549     newElem= qh_memalloc(elemsize);
00550     memcpy(newElem, elem, (size_t)elemsize);
00551     qh_setappend(&newSet, newElem);
00552   }
00553   return newSet;
00554 } /* setduplicate */
00555 
00556 
00557 /*-<a                             href="qh-set.htm#TOC"
00558   >-------------------------------<a name="setendpointer">-</a>
00559 
00560   qh_setendpointer( set )
00561     Returns pointer to NULL terminator of a set's elements
00562     set can not be NULL
00563 
00564 */
00565 void **qh_setendpointer(setT *set) {
00566 
00567   setelemT *sizep= SETsizeaddr_(set);
00568   int n= sizep->i;
00569   return (n ? &set->e[n-1].p : &sizep->p);
00570 } /* qh_setendpointer */
00571 
00572 /*-<a                             href="qh-set.htm#TOC"
00573   >-------------------------------<a name="setequal">-</a>
00574 
00575   qh_setequal(  )
00576     returns 1 if two sorted sets are equal, otherwise returns 0
00577 
00578   notes:
00579     either set may be NULL
00580 
00581   design:
00582     check size of each set
00583     setup pointers
00584     compare elements of each set
00585 */
00586 int qh_setequal(setT *setA, setT *setB) {
00587   void **elemAp, **elemBp;
00588   int sizeA= 0, sizeB= 0;
00589 
00590   if (setA) {
00591     SETreturnsize_(setA, sizeA);
00592   }
00593   if (setB) {
00594     SETreturnsize_(setB, sizeB);
00595   }
00596   if (sizeA != sizeB)
00597     return 0;
00598   if (!sizeA)
00599     return 1;
00600   elemAp= SETaddr_(setA, void);
00601   elemBp= SETaddr_(setB, void);
00602   if (!memcmp((char *)elemAp, (char *)elemBp, sizeA*SETelemsize))
00603     return 1;
00604   return 0;
00605 } /* setequal */
00606 
00607 
00608 /*-<a                             href="qh-set.htm#TOC"
00609   >-------------------------------<a name="setequal_except">-</a>
00610 
00611   qh_setequal_except( setA, skipelemA, setB, skipelemB )
00612     returns 1 if sorted setA and setB are equal except for skipelemA & B
00613 
00614   returns:
00615     false if either skipelemA or skipelemB are missing
00616 
00617   notes:
00618     neither set may be NULL
00619 
00620     if skipelemB is NULL,
00621       can skip any one element of setB
00622 
00623   design:
00624     setup pointers
00625     search for skipelemA, skipelemB, and mismatches
00626     check results
00627 */
00628 int qh_setequal_except(setT *setA, void *skipelemA, setT *setB, void *skipelemB) {
00629   void **elemA, **elemB;
00630   int skip=0;
00631 
00632   elemA= SETaddr_(setA, void);
00633   elemB= SETaddr_(setB, void);
00634   while (1) {
00635     if (*elemA == skipelemA) {
00636       skip++;
00637       elemA++;
00638     }
00639     if (skipelemB) {
00640       if (*elemB == skipelemB) {
00641         skip++;
00642         elemB++;
00643       }
00644     }else if (*elemA != *elemB) {
00645       skip++;
00646       if (!(skipelemB= *elemB++))
00647         return 0;
00648     }
00649     if (!*elemA)
00650       break;
00651     if (*elemA++ != *elemB++)
00652       return 0;
00653   }
00654   if (skip != 2 || *elemB)
00655     return 0;
00656   return 1;
00657 } /* setequal_except */
00658 
00659 
00660 /*-<a                             href="qh-set.htm#TOC"
00661   >-------------------------------<a name="setequal_skip">-</a>
00662 
00663   qh_setequal_skip( setA, skipA, setB, skipB )
00664     returns 1 if sorted setA and setB are equal except for elements skipA & B
00665 
00666   returns:
00667     false if different size
00668 
00669   notes:
00670     neither set may be NULL
00671 
00672   design:
00673     setup pointers
00674     search for mismatches while skipping skipA and skipB
00675 */
00676 int qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB) {
00677   void **elemA, **elemB, **skipAp, **skipBp;
00678 
00679   elemA= SETaddr_(setA, void);
00680   elemB= SETaddr_(setB, void);
00681   skipAp= SETelemaddr_(setA, skipA, void);
00682   skipBp= SETelemaddr_(setB, skipB, void);
00683   while (1) {
00684     if (elemA == skipAp)
00685       elemA++;
00686     if (elemB == skipBp)
00687       elemB++;
00688     if (!*elemA)
00689       break;
00690     if (*elemA++ != *elemB++)
00691       return 0;
00692   }
00693   if (*elemB)
00694     return 0;
00695   return 1;
00696 } /* setequal_skip */
00697 
00698 
00699 /*-<a                             href="qh-set.htm#TOC"
00700   >-------------------------------<a name="setfree">-</a>
00701 
00702   qh_setfree( setp )
00703     frees the space occupied by a sorted or unsorted set
00704 
00705   returns:
00706     sets setp to NULL
00707 
00708   notes:
00709     set may be NULL
00710 
00711   design:
00712     free array
00713     free set
00714 */
00715 void qh_setfree(setT **setp) {
00716   int size;
00717   void **freelistp;  /* used !qh_NOmem */
00718 
00719   if (*setp) {
00720     size= sizeof(setT) + ((*setp)->maxsize)*SETelemsize;
00721     if (size <= qhmem.LASTsize) {
00722       qh_memfree_(*setp, size, freelistp);
00723     }else
00724       qh_memfree(*setp, size);
00725     *setp= NULL;
00726   }
00727 } /* setfree */
00728 
00729 
00730 /*-<a                             href="qh-set.htm#TOC"
00731   >-------------------------------<a name="setfree2">-</a>
00732 
00733   qh_setfree2( setp, elemsize )
00734     frees the space occupied by a set and its elements
00735 
00736   notes:
00737     set may be NULL
00738 
00739   design:
00740     free each element
00741     free set
00742 */
00743 void qh_setfree2 (setT **setp, int elemsize) {
00744   void          *elem, **elemp;
00745 
00746   FOREACHelem_(*setp)
00747     qh_memfree(elem, elemsize);
00748   qh_setfree(setp);
00749 } /* setfree2 */
00750 
00751 
00752 
00753 /*-<a                             href="qh-set.htm#TOC"
00754   >-------------------------------<a name="setfreelong">-</a>
00755 
00756   qh_setfreelong( setp )
00757     frees a set only if it's in long memory
00758 
00759   returns:
00760     sets setp to NULL if it is freed
00761 
00762   notes:
00763     set may be NULL
00764 
00765   design:
00766     if set is large
00767       free it
00768 */
00769 void qh_setfreelong(setT **setp) {
00770   int size;
00771 
00772   if (*setp) {
00773     size= sizeof(setT) + ((*setp)->maxsize)*SETelemsize;
00774     if (size > qhmem.LASTsize) {
00775       qh_memfree(*setp, size);
00776       *setp= NULL;
00777     }
00778   }
00779 } /* setfreelong */
00780 
00781 
00782 /*-<a                             href="qh-set.htm#TOC"
00783   >-------------------------------<a name="setin">-</a>
00784 
00785   qh_setin( set, setelem )
00786     returns 1 if setelem is in a set, 0 otherwise
00787 
00788   notes:
00789     set may be NULL or unsorted
00790 
00791   design:
00792     scans set for setelem
00793 */
00794 int qh_setin(setT *set, void *setelem) {
00795   void *elem, **elemp;
00796 
00797   FOREACHelem_(set) {
00798     if (elem == setelem)
00799       return 1;
00800   }
00801   return 0;
00802 } /* setin */
00803 
00804 
00805 /*-<a                             href="qh-set.htm#TOC"
00806   >-------------------------------<a name="setindex">-</a>
00807 
00808   qh_setindex( set, atelem )
00809     returns the index of atelem in set.
00810     returns -1, if not in set or maxsize wrong
00811 
00812   notes:
00813     set may be NULL and may contain nulls.
00814     NOerrors returned (qh_pointid, QhullPoint::id)
00815 
00816   design:
00817     checks maxsize
00818     scans set for atelem
00819 */
00820 int qh_setindex(setT *set, void *atelem) {
00821   void **elem;
00822   int size, i;
00823 
00824   if (!set)
00825     return -1;
00826   SETreturnsize_(set, size);
00827   if (size > set->maxsize)
00828     return -1;
00829   elem= SETaddr_(set, void);
00830   for (i=0; i < size; i++) {
00831     if (*elem++ == atelem)
00832       return i;
00833   }
00834   return -1;
00835 } /* setindex */
00836 
00837 
00838 /*-<a                             href="qh-set.htm#TOC"
00839   >-------------------------------<a name="setlarger">-</a>
00840 
00841   qh_setlarger( oldsetp )
00842     returns a larger set that contains all elements of *oldsetp
00843 
00844   notes:
00845     the set is at least twice as large
00846     if temp set, updates qhmem.tempstack
00847 
00848   design:
00849     creates a new set
00850     copies the old set to the new set
00851     updates pointers in tempstack
00852     deletes the old set
00853 */
00854 void qh_setlarger(setT **oldsetp) {
00855   int size= 1;
00856   setT *newset, *set, **setp, *oldset;
00857   setelemT *sizep;
00858   setelemT *newp, *oldp;
00859 
00860   if (*oldsetp) {
00861     oldset= *oldsetp;
00862     SETreturnsize_(oldset, size);
00863     qhmem.cntlarger++;
00864     qhmem.totlarger += size+1;
00865     newset= qh_setnew(2 * size);
00866     oldp= (setelemT *)SETaddr_(oldset, void);
00867     newp= (setelemT *)SETaddr_(newset, void);
00868     memcpy((char *)newp, (char *)oldp, (size_t)(size+1) * SETelemsize);
00869     sizep= SETsizeaddr_(newset);
00870     sizep->i= size+1;
00871     FOREACHset_((setT *)qhmem.tempstack) {
00872       if (set == oldset)
00873         *(setp-1)= newset;
00874     }
00875     qh_setfree(oldsetp);
00876   }else
00877     newset= qh_setnew(3);
00878   *oldsetp= newset;
00879 } /* setlarger */
00880 
00881 
00882 /*-<a                             href="qh-set.htm#TOC"
00883   >-------------------------------<a name="setlast">-</a>
00884 
00885   qh_setlast(  )
00886     return last element of set or NULL (use type conversion)
00887 
00888   notes:
00889     set may be NULL
00890 
00891   design:
00892     return last element
00893 */
00894 void *qh_setlast(setT *set) {
00895   int size;
00896 
00897   if (set) {
00898     size= SETsizeaddr_(set)->i;
00899     if (!size)
00900       return SETelem_(set, set->maxsize - 1);
00901     else if (size > 1)
00902       return SETelem_(set, size - 2);
00903   }
00904   return NULL;
00905 } /* setlast */
00906 
00907 
00908 /*-<a                             href="qh-set.htm#TOC"
00909   >-------------------------------<a name="setnew">-</a>
00910 
00911   qh_setnew( setsize )
00912     creates and allocates space for a set
00913 
00914   notes:
00915     setsize means the number of elements (!including the NULL terminator)
00916     use qh_settemp/qh_setfreetemp if set is temporary
00917 
00918   design:
00919     allocate memory for set
00920     roundup memory if small set
00921     initialize as empty set
00922 */
00923 setT *qh_setnew(int setsize) {
00924   setT *set;
00925   int sizereceived; /* used !qh_NOmem */
00926   int size;
00927   void **freelistp; /* used !qh_NOmem */
00928 
00929   if (!setsize)
00930     setsize++;
00931   size= sizeof(setT) + setsize * SETelemsize;
00932   if (size>0 && size <= qhmem.LASTsize) {
00933     qh_memalloc_(size, freelistp, set, setT);
00934 #ifndef qh_NOmem
00935     sizereceived= qhmem.sizetable[ qhmem.indextable[size]];
00936     if (sizereceived > size)
00937       setsize += (sizereceived - size)/SETelemsize;
00938 #endif
00939   }else
00940     set= (setT*)qh_memalloc(size);
00941   set->maxsize= setsize;
00942   set->e[setsize].i= 1;
00943   set->e[0].p= NULL;
00944   return(set);
00945 } /* setnew */
00946 
00947 
00948 /*-<a                             href="qh-set.htm#TOC"
00949   >-------------------------------<a name="setnew_delnthsorted">-</a>
00950 
00951   qh_setnew_delnthsorted( set, size, nth, prepend )
00952     creates a sorted set not containing nth element
00953     if prepend, the first prepend elements are undefined
00954 
00955   notes:
00956     set must be defined
00957     checks nth
00958     see also: setdelnthsorted
00959 
00960   design:
00961     create new set
00962     setup pointers and allocate room for prepend'ed entries
00963     append head of old set to new set
00964     append tail of old set to new set
00965 */
00966 setT *qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend) {
00967   setT *newset;
00968   void **oldp, **newp;
00969   int tailsize= size - nth -1, newsize;
00970 
00971   if (tailsize < 0) {
00972     qh_fprintf(qhmem.ferr, 6176, "qhull internal error (qh_setnew_delnthsorted): nth %d is out-of-bounds for set:\n", nth);
00973     qh_setprint(qhmem.ferr, "", set);
00974     qh_errexit(qhmem_ERRqhull, NULL, NULL);
00975   }
00976   newsize= size-1 + prepend;
00977   newset= qh_setnew(newsize);
00978   newset->e[newset->maxsize].i= newsize+1;  /* may be overwritten */
00979   oldp= SETaddr_(set, void);
00980   newp= SETaddr_(newset, void) + prepend;
00981   switch (nth) {
00982   case 0:
00983     break;
00984   case 1:
00985     *(newp++)= *oldp++;
00986     break;
00987   case 2:
00988     *(newp++)= *oldp++;
00989     *(newp++)= *oldp++;
00990     break;
00991   case 3:
00992     *(newp++)= *oldp++;
00993     *(newp++)= *oldp++;
00994     *(newp++)= *oldp++;
00995     break;
00996   case 4:
00997     *(newp++)= *oldp++;
00998     *(newp++)= *oldp++;
00999     *(newp++)= *oldp++;
01000     *(newp++)= *oldp++;
01001     break;
01002   default:
01003     memcpy((char *)newp, (char *)oldp, (size_t)nth * SETelemsize);
01004     newp += nth;
01005     oldp += nth;
01006     break;
01007   }
01008   oldp++;
01009   switch (tailsize) {
01010   case 0:
01011     break;
01012   case 1:
01013     *(newp++)= *oldp++;
01014     break;
01015   case 2:
01016     *(newp++)= *oldp++;
01017     *(newp++)= *oldp++;
01018     break;
01019   case 3:
01020     *(newp++)= *oldp++;
01021     *(newp++)= *oldp++;
01022     *(newp++)= *oldp++;
01023     break;
01024   case 4:
01025     *(newp++)= *oldp++;
01026     *(newp++)= *oldp++;
01027     *(newp++)= *oldp++;
01028     *(newp++)= *oldp++;
01029     break;
01030   default:
01031     memcpy((char *)newp, (char *)oldp, (size_t)tailsize * SETelemsize);
01032     newp += tailsize;
01033   }
01034   *newp= NULL;
01035   return(newset);
01036 } /* setnew_delnthsorted */
01037 
01038 
01039 /*-<a                             href="qh-set.htm#TOC"
01040   >-------------------------------<a name="setprint">-</a>
01041 
01042   qh_setprint( fp, string, set )
01043     print set elements to fp with identifying string
01044 
01045   notes:
01046     never errors
01047 */
01048 void qh_setprint(FILE *fp, const char* string, setT *set) {
01049   int size, k;
01050 
01051   if (!set)
01052     qh_fprintf(fp, 9346, "%s set is null\n", string);
01053   else {
01054     SETreturnsize_(set, size);
01055     qh_fprintf(fp, 9347, "%s set=%p maxsize=%d size=%d elems=",
01056              string, set, set->maxsize, size);
01057     if (size > set->maxsize)
01058       size= set->maxsize+1;
01059     for (k=0; k < size; k++)
01060       qh_fprintf(fp, 9348, " %p", set->e[k].p);
01061     qh_fprintf(fp, 9349, "\n");
01062   }
01063 } /* setprint */
01064 
01065 /*-<a                             href="qh-set.htm#TOC"
01066   >-------------------------------<a name="setreplace">-</a>
01067 
01068   qh_setreplace( set, oldelem, newelem )
01069     replaces oldelem in set with newelem
01070 
01071   notes:
01072     errors if oldelem not in the set
01073     newelem may be NULL, but it turns the set into an indexed set (no FOREACH)
01074 
01075   design:
01076     find oldelem
01077     replace with newelem
01078 */
01079 void qh_setreplace(setT *set, void *oldelem, void *newelem) {
01080   void **elemp;
01081 
01082   elemp= SETaddr_(set, void);
01083   while (*elemp != oldelem && *elemp)
01084     elemp++;
01085   if (*elemp)
01086     *elemp= newelem;
01087   else {
01088     qh_fprintf(qhmem.ferr, 6177, "qhull internal error (qh_setreplace): elem %p not found in set\n",
01089        oldelem);
01090     qh_setprint(qhmem.ferr, "", set);
01091     qh_errexit(qhmem_ERRqhull, NULL, NULL);
01092   }
01093 } /* setreplace */
01094 
01095 
01096 /*-<a                             href="qh-set.htm#TOC"
01097   >-------------------------------<a name="setsize">-</a>
01098 
01099   qh_setsize( set )
01100     returns the size of a set
01101 
01102   notes:
01103     errors if set's maxsize is incorrect
01104     same as SETreturnsize_(set)
01105     same code for qh_setsize [qset.c] and QhullSetBase::count
01106 
01107   design:
01108     determine actual size of set from maxsize
01109 */
01110 int qh_setsize(setT *set) {
01111   int size;
01112   setelemT *sizep;
01113 
01114   if (!set)
01115     return(0);
01116   sizep= SETsizeaddr_(set);
01117   if ((size= sizep->i)) {
01118     size--;
01119     if (size > set->maxsize) {
01120       qh_fprintf(qhmem.ferr, 6178, "qhull internal error (qh_setsize): current set size %d is greater than maximum size %d\n",
01121                size, set->maxsize);
01122       qh_setprint(qhmem.ferr, "set: ", set);
01123       qh_errexit(qhmem_ERRqhull, NULL, NULL);
01124     }
01125   }else
01126     size= set->maxsize;
01127   return size;
01128 } /* setsize */
01129 
01130 /*-<a                             href="qh-set.htm#TOC"
01131   >-------------------------------<a name="settemp">-</a>
01132 
01133   qh_settemp( setsize )
01134     return a stacked, temporary set of upto setsize elements
01135 
01136   notes:
01137     use settempfree or settempfree_all to release from qhmem.tempstack
01138     see also qh_setnew
01139 
01140   design:
01141     allocate set
01142     append to qhmem.tempstack
01143 
01144 */
01145 setT *qh_settemp(int setsize) {
01146   setT *newset;
01147 
01148   newset= qh_setnew(setsize);
01149   qh_setappend(&qhmem.tempstack, newset);
01150   if (qhmem.IStracing >= 5)
01151     qh_fprintf(qhmem.ferr, 8123, "qh_settemp: temp set %p of %d elements, depth %d\n",
01152        newset, newset->maxsize, qh_setsize(qhmem.tempstack));
01153   return newset;
01154 } /* settemp */
01155 
01156 /*-<a                             href="qh-set.htm#TOC"
01157   >-------------------------------<a name="settempfree">-</a>
01158 
01159   qh_settempfree( set )
01160     free temporary set at top of qhmem.tempstack
01161 
01162   notes:
01163     nop if set is NULL
01164     errors if set not from previous   qh_settemp
01165 
01166   to locate errors:
01167     use 'T2' to find source and then find mis-matching qh_settemp
01168 
01169   design:
01170     check top of qhmem.tempstack
01171     free it
01172 */
01173 void qh_settempfree(setT **set) {
01174   setT *stackedset;
01175 
01176   if (!*set)
01177     return;
01178   stackedset= qh_settemppop();
01179   if (stackedset != *set) {
01180     qh_settemppush(stackedset);
01181     qh_fprintf(qhmem.ferr, 6179, "qhull internal error (qh_settempfree): set %p(size %d) was not last temporary allocated(depth %d, set %p, size %d)\n",
01182              *set, qh_setsize(*set), qh_setsize(qhmem.tempstack)+1,
01183              stackedset, qh_setsize(stackedset));
01184     qh_errexit(qhmem_ERRqhull, NULL, NULL);
01185   }
01186   qh_setfree(set);
01187 } /* settempfree */
01188 
01189 /*-<a                             href="qh-set.htm#TOC"
01190   >-------------------------------<a name="settempfree_all">-</a>
01191 
01192   qh_settempfree_all(  )
01193     free all temporary sets in qhmem.tempstack
01194 
01195   design:
01196     for each set in tempstack
01197       free set
01198     free qhmem.tempstack
01199 */
01200 void qh_settempfree_all(void) {
01201   setT *set, **setp;
01202 
01203   FOREACHset_(qhmem.tempstack)
01204     qh_setfree(&set);
01205   qh_setfree(&qhmem.tempstack);
01206 } /* settempfree_all */
01207 
01208 /*-<a                             href="qh-set.htm#TOC"
01209   >-------------------------------<a name="settemppop">-</a>
01210 
01211   qh_settemppop(  )
01212     pop and return temporary set from qhmem.tempstack
01213 
01214   notes:
01215     the returned set is permanent
01216 
01217   design:
01218     pop and check top of qhmem.tempstack
01219 */
01220 setT *qh_settemppop(void) {
01221   setT *stackedset;
01222 
01223   stackedset= (setT*)qh_setdellast(qhmem.tempstack);
01224   if (!stackedset) {
01225     qh_fprintf(qhmem.ferr, 6180, "qhull internal error (qh_settemppop): pop from empty temporary stack\n");
01226     qh_errexit(qhmem_ERRqhull, NULL, NULL);
01227   }
01228   if (qhmem.IStracing >= 5)
01229     qh_fprintf(qhmem.ferr, 8124, "qh_settemppop: depth %d temp set %p of %d elements\n",
01230        qh_setsize(qhmem.tempstack)+1, stackedset, qh_setsize(stackedset));
01231   return stackedset;
01232 } /* settemppop */
01233 
01234 /*-<a                             href="qh-set.htm#TOC"
01235   >-------------------------------<a name="settemppush">-</a>
01236 
01237   qh_settemppush( set )
01238     push temporary set unto qhmem.tempstack (makes it temporary)
01239 
01240   notes:
01241     duplicates settemp() for tracing
01242 
01243   design:
01244     append set to tempstack
01245 */
01246 void qh_settemppush(setT *set) {
01247     if (!set) {
01248         fprintf (qhmem.ferr, "qhull error (qh_settemppush): can not push a NULL temp\n");
01249         qh_errexit (qhmem_ERRqhull, NULL, NULL);
01250     }
01251   qh_setappend(&qhmem.tempstack, set);
01252   if (qhmem.IStracing >= 5)
01253     qh_fprintf(qhmem.ferr, 8125, "qh_settemppush: depth %d temp set %p of %d elements\n",
01254       qh_setsize(qhmem.tempstack), set, qh_setsize(set));
01255 } /* settemppush */
01256 
01257 
01258 /*-<a                             href="qh-set.htm#TOC"
01259   >-------------------------------<a name="settruncate">-</a>
01260 
01261   qh_settruncate( set, size )
01262     truncate set to size elements
01263 
01264   notes:
01265     set must be defined
01266 
01267   see:
01268     SETtruncate_
01269 
01270   design:
01271     check size
01272     update actual size of set
01273 */
01274 void qh_settruncate(setT *set, int size) {
01275 
01276   if (size < 0 || size > set->maxsize) {
01277     qh_fprintf(qhmem.ferr, 6181, "qhull internal error (qh_settruncate): size %d out of bounds for set:\n", size);
01278     qh_setprint(qhmem.ferr, "", set);
01279     qh_errexit(qhmem_ERRqhull, NULL, NULL);
01280   }
01281   set->e[set->maxsize].i= size+1;   /* maybe overwritten */
01282   set->e[size].p= NULL;
01283 } /* settruncate */
01284 
01285 /*-<a                             href="qh-set.htm#TOC"
01286   >-------------------------------<a name="setunique">-</a>
01287 
01288   qh_setunique( set, elem )
01289     add elem to unsorted set unless it is already in set
01290 
01291   notes:
01292     returns 1 if it is appended
01293 
01294   design:
01295     if elem not in set
01296       append elem to set
01297 */
01298 int qh_setunique(setT **set, void *elem) {
01299 
01300   if (!qh_setin(*set, elem)) {
01301     qh_setappend(set, elem);
01302     return 1;
01303   }
01304   return 0;
01305 } /* setunique */
01306 
01307 /*-<a                             href="qh-set.htm#TOC"
01308   >-------------------------------<a name="setzero">-</a>
01309 
01310   qh_setzero( set, index, size )
01311     zero elements from index on
01312     set actual size of set to size
01313 
01314   notes:
01315     set must be defined
01316     the set becomes an indexed set (can not use FOREACH...)
01317 
01318   see also:
01319     qh_settruncate
01320 
01321   design:
01322     check index and size
01323     update actual size
01324     zero elements starting at e[index]
01325 */
01326 void qh_setzero(setT *set, int idx, int size) {
01327   int count;
01328 
01329   if (idx < 0 || idx >= size || size > set->maxsize) {
01330     qh_fprintf(qhmem.ferr, 6182, "qhull internal error (qh_setzero): index %d or size %d out of bounds for set:\n", idx, size);
01331     qh_setprint(qhmem.ferr, "", set);
01332     qh_errexit(qhmem_ERRqhull, NULL, NULL);
01333   }
01334   set->e[set->maxsize].i=  size+1;  /* may be overwritten */
01335   count= size - idx + 1;   /* +1 for NULL terminator */
01336   memset((char *)SETelemaddr_(set, idx, void), 0, (size_t)count * SETelemsize);
01337 } /* setzero */
01338 
01339