graspit: /opt/ros/diamondback/stacks/graspit_simulator/graspit/graspit

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