hpp-fcl: qset_r.c Source File

Go to the documentation of this file.
 /*<html><pre>  -<a                             href="qh-set_r.htm"
   >-------------------------------</a><a name="TOP">-</a>
  
    qset_r.c
    implements set manipulations needed for quickhull
  
    see qh-set_r.htm and qset_r.h
  
    Be careful of strict aliasing (two pointers of different types
    that reference the same location).  The last slot of a set is
    either the actual size of the set plus 1, or the NULL terminator
    of the set (i.e., setelemT).
  
    Copyright (c) 1993-2015 The Geometry Center.
    $Id: //main/2015/qhull/src/libqhull_r/qset_r.c#3 $$Change: 2062 $
    $DateTime: 2016/01/17 13:13:18 $$Author: bbarber $
 */
  
 #include "libqhull_r.h" /* for qhT and QHULL_CRTDBG */
 #include "qset_r.h"
 #include "mem_r.h"
 #include <stdio.h>
 #include <string.h>
 /*** uncomment here and qhull_ra.h
      if string.h does not define memcpy()
 #include <memory.h>
 */
  
 #ifndef qhDEFlibqhull
 typedef struct ridgeT ridgeT;
 typedef struct facetT facetT;
 void    qh_errexit(qhT *qh, int exitcode, facetT *, ridgeT *);
 void    qh_fprintf(qhT *qh, FILE *fp, int msgcode, const char *fmt, ... );
 #  ifdef _MSC_VER  /* Microsoft Visual C++ -- warning level 4 */
 #  pragma warning( disable : 4127)  /* conditional expression is constant */
 #  pragma warning( disable : 4706)  /* assignment within conditional function */
 #  endif
 #endif
  
 /*=============== internal macros ===========================*/
  
 /*============ functions in alphabetical order ===================*/
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >--------------------------------<a name="setaddnth">-</a>
  
   qh_setaddnth(qh, setp, nth, newelem)
     adds newelem as n'th element of sorted or unsorted *setp
  
   notes:
     *setp and newelem must be defined
     *setp may be a temp set
     nth=0 is first element
     errors if nth is out of bounds
  
   design:
     expand *setp if empty or full
     move tail of *setp up one
     insert newelem
 */
 void qh_setaddnth(qhT *qh, setT **setp, int nth, void *newelem) {
   int oldsize, i;
   setelemT *sizep;          /* avoid strict aliasing */
   setelemT *oldp, *newp;
  
   if (!*setp || (sizep= SETsizeaddr_(*setp))->i==0) {
     qh_setlarger(qh, setp);
     sizep= SETsizeaddr_(*setp);
   }
   oldsize= sizep->i - 1;
   if (nth < 0 || nth > oldsize) {
     qh_fprintf(qh, qh->qhmem.ferr, 6171, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
     qh_setprint(qh, qh->qhmem.ferr, "", *setp);
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
   sizep->i++;
   oldp= (setelemT *)SETelemaddr_(*setp, oldsize, void);   /* NULL */
   newp= oldp+1;
   for (i=oldsize-nth+1; i--; )  /* move at least NULL  */
     (newp--)->p= (oldp--)->p;       /* may overwrite *sizep */
   newp->p= newelem;
 } /* setaddnth */
  
  
 /*-<a                              href="qh-set_r.htm#TOC"
   >--------------------------------<a name="setaddsorted">-</a>
  
   setaddsorted( setp, newelem )
     adds an newelem into sorted *setp
  
   notes:
     *setp and newelem must be defined
     *setp may be a temp set
     nop if newelem already in set
  
   design:
     find newelem's position in *setp
     insert newelem
 */
 void qh_setaddsorted(qhT *qh, setT **setp, void *newelem) {
   int newindex=0;
   void *elem, **elemp;
  
   FOREACHelem_(*setp) {          /* could use binary search instead */
     if (elem < newelem)
       newindex++;
     else if (elem == newelem)
       return;
     else
       break;
   }
   qh_setaddnth(qh, setp, newindex, newelem);
 } /* setaddsorted */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setappend">-</a>
  
   qh_setappend(qh, setp, newelem)
     append newelem to *setp
  
   notes:
     *setp may be a temp set
     *setp and newelem may be NULL
  
   design:
     expand *setp if empty or full
     append newelem to *setp
  
 */
 void qh_setappend(qhT *qh, setT **setp, void *newelem) {
   setelemT *sizep;  /* Avoid strict aliasing.  Writing to *endp may overwrite *sizep */
   setelemT *endp;
   int count;
  
   if (!newelem)
     return;
   if (!*setp || (sizep= SETsizeaddr_(*setp))->i==0) {
     qh_setlarger(qh, setp);
     sizep= SETsizeaddr_(*setp);
   }
   count= (sizep->i)++ - 1;
   endp= (setelemT *)SETelemaddr_(*setp, count, void);
   (endp++)->p= newelem;
   endp->p= NULL;
 } /* setappend */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setappend_set">-</a>
  
   qh_setappend_set(qh, setp, setA)
     appends setA to *setp
  
   notes:
     *setp can not be a temp set
     *setp and setA may be NULL
  
   design:
     setup for copy
     expand *setp if it is too small
     append all elements of setA to *setp
 */
 void qh_setappend_set(qhT *qh, setT **setp, setT *setA) {
   int sizeA, size;
   setT *oldset;
   setelemT *sizep;
  
   if (!setA)
     return;
   SETreturnsize_(setA, sizeA);
   if (!*setp)
     *setp= qh_setnew(qh, sizeA);
   sizep= SETsizeaddr_(*setp);
   if (!(size= sizep->i))
     size= (*setp)->maxsize;
   else
     size--;
   if (size + sizeA > (*setp)->maxsize) {
     oldset= *setp;
     *setp= qh_setcopy(qh, oldset, sizeA);
     qh_setfree(qh, &oldset);
     sizep= SETsizeaddr_(*setp);
   }
   if (sizeA > 0) {
     sizep->i= size+sizeA+1;   /* memcpy may overwrite */
     memcpy((char *)&((*setp)->e[size].p), (char *)&(setA->e[0].p), (size_t)(sizeA+1) * SETelemsize);
   }
 } /* setappend_set */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setappend2ndlast">-</a>
  
   qh_setappend2ndlast(qh, setp, newelem )
     makes newelem the next to the last element in *setp
  
   notes:
     *setp must have at least one element
     newelem must be defined
     *setp may be a temp set
  
   design:
     expand *setp if empty or full
     move last element of *setp up one
     insert newelem
 */
 void qh_setappend2ndlast(qhT *qh, setT **setp, void *newelem) {
     setelemT *sizep;  /* Avoid strict aliasing.  Writing to *endp may overwrite *sizep */
     setelemT *endp, *lastp;
     int count;
  
     if (!*setp || (sizep= SETsizeaddr_(*setp))->i==0) {
         qh_setlarger(qh, setp);
         sizep= SETsizeaddr_(*setp);
     }
     count= (sizep->i)++ - 1;
     endp= (setelemT *)SETelemaddr_(*setp, count, void); /* NULL */
     lastp= endp-1;
     *(endp++)= *lastp;
     endp->p= NULL;    /* may overwrite *sizep */
     lastp->p= newelem;
 } /* setappend2ndlast */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setcheck">-</a>
  
   qh_setcheck(qh, set, typename, id )
     check set for validity
     report errors with typename and id
  
   design:
     checks that maxsize, actual size, and NULL terminator agree
 */
 void qh_setcheck(qhT *qh, setT *set, const char *tname, unsigned id) {
   int maxsize, size;
   int waserr= 0;
  
   if (!set)
     return;
   SETreturnsize_(set, size);
   maxsize= set->maxsize;
   if (size > maxsize || !maxsize) {
     qh_fprintf(qh, qh->qhmem.ferr, 6172, "qhull internal error (qh_setcheck): actual size %d of %s%d is greater than max size %d\n",
              size, tname, id, maxsize);
     waserr= 1;
   }else if (set->e[size].p) {
     qh_fprintf(qh, qh->qhmem.ferr, 6173, "qhull internal error (qh_setcheck): %s%d(size %d max %d) is not null terminated.\n",
              tname, id, size-1, maxsize);
     waserr= 1;
   }
   if (waserr) {
     qh_setprint(qh, qh->qhmem.ferr, "ERRONEOUS", set);
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
 } /* setcheck */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setcompact">-</a>
  
   qh_setcompact(qh, set )
     remove internal NULLs from an unsorted set
  
   returns:
     updated set
  
   notes:
     set may be NULL
     it would be faster to swap tail of set into holes, like qh_setdel
  
   design:
     setup pointers into set
     skip NULLs while copying elements to start of set
     update the actual size
 */
 void qh_setcompact(qhT *qh, setT *set) {
   int size;
   void **destp, **elemp, **endp, **firstp;
  
   if (!set)
     return;
   SETreturnsize_(set, size);
   destp= elemp= firstp= SETaddr_(set, void);
   endp= destp + size;
   while (1) {
     if (!(*destp++ = *elemp++)) {
       destp--;
       if (elemp > endp)
         break;
     }
   }
   qh_settruncate(qh, set, (int)(destp-firstp));   /* WARN64 */
 } /* setcompact */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setcopy">-</a>
  
   qh_setcopy(qh, set, extra )
     make a copy of a sorted or unsorted set with extra slots
  
   returns:
     new set
  
   design:
     create a newset with extra slots
     copy the elements to the newset
  
 */
 setT *qh_setcopy(qhT *qh, setT *set, int extra) {
   setT *newset;
   int size;
  
   if (extra < 0)
     extra= 0;
   SETreturnsize_(set, size);
   newset= qh_setnew(qh, size+extra);
   SETsizeaddr_(newset)->i= size+1;    /* memcpy may overwrite */
   memcpy((char *)&(newset->e[0].p), (char *)&(set->e[0].p), (size_t)(size+1) * SETelemsize);
   return(newset);
 } /* setcopy */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setdel">-</a>
  
   qh_setdel(set, oldelem )
     delete oldelem from an unsorted set
  
   returns:
     returns oldelem if found
     returns NULL otherwise
  
   notes:
     set may be NULL
     oldelem must not be NULL;
     only deletes one copy of oldelem in set
  
   design:
     locate oldelem
     update actual size if it was full
     move the last element to the oldelem's location
 */
 void *qh_setdel(setT *set, void *oldelem) {
   setelemT *sizep;
   setelemT *elemp;
   setelemT *lastp;
  
   if (!set)
     return NULL;
   elemp= (setelemT *)SETaddr_(set, void);
   while (elemp->p != oldelem && elemp->p)
     elemp++;
   if (elemp->p) {
     sizep= SETsizeaddr_(set);
     if (!(sizep->i)--)         /*  if was a full set */
       sizep->i= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */
     lastp= (setelemT *)SETelemaddr_(set, sizep->i-1, void);
     elemp->p= lastp->p;      /* may overwrite itself */
     lastp->p= NULL;
     return oldelem;
   }
   return NULL;
 } /* setdel */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setdellast">-</a>
  
   qh_setdellast(set)
     return last element of set or NULL
  
   notes:
     deletes element from set
     set may be NULL
  
   design:
     return NULL if empty
     if full set
       delete last element and set actual size
     else
       delete last element and update actual size
 */
 void *qh_setdellast(setT *set) {
   int setsize;  /* actually, actual_size + 1 */
   int maxsize;
   setelemT *sizep;
   void *returnvalue;
  
   if (!set || !(set->e[0].p))
     return NULL;
   sizep= SETsizeaddr_(set);
   if ((setsize= sizep->i)) {
     returnvalue= set->e[setsize - 2].p;
     set->e[setsize - 2].p= NULL;
     sizep->i--;
   }else {
     maxsize= set->maxsize;
     returnvalue= set->e[maxsize - 1].p;
     set->e[maxsize - 1].p= NULL;
     sizep->i= maxsize;
   }
   return returnvalue;
 } /* setdellast */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setdelnth">-</a>
  
   qh_setdelnth(qh, set, nth )
     deletes nth element from unsorted set
     0 is first element
  
   returns:
     returns the element (needs type conversion)
  
   notes:
     errors if nth invalid
  
   design:
     setup points and check nth
     delete nth element and overwrite with last element
 */
 void *qh_setdelnth(qhT *qh, setT *set, int nth) {
   void *elem;
   setelemT *sizep;
   setelemT *elemp, *lastp;
  
   sizep= SETsizeaddr_(set);
   if ((sizep->i--)==0)         /*  if was a full set */
     sizep->i= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */
   if (nth < 0 || nth >= sizep->i) {
     qh_fprintf(qh, qh->qhmem.ferr, 6174, "qhull internal error (qh_setdelnth): nth %d is out-of-bounds for set:\n", nth);
     qh_setprint(qh, qh->qhmem.ferr, "", set);
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
   elemp= (setelemT *)SETelemaddr_(set, nth, void); /* nth valid by QH6174 */
   lastp= (setelemT *)SETelemaddr_(set, sizep->i-1, void);
   elem= elemp->p;
   elemp->p= lastp->p;      /* may overwrite itself */
   lastp->p= NULL;
   return elem;
 } /* setdelnth */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setdelnthsorted">-</a>
  
   qh_setdelnthsorted(qh, set, nth )
     deletes nth element from sorted set
  
   returns:
     returns the element (use type conversion)
  
   notes:
     errors if nth invalid
  
   see also:
     setnew_delnthsorted
  
   design:
     setup points and check nth
     copy remaining elements down one
     update actual size
 */
 void *qh_setdelnthsorted(qhT *qh, setT *set, int nth) {
   void *elem;
   setelemT *sizep;
   setelemT *newp, *oldp;
  
   sizep= SETsizeaddr_(set);
   if (nth < 0 || (sizep->i && nth >= sizep->i-1) || nth >= set->maxsize) {
     qh_fprintf(qh, qh->qhmem.ferr, 6175, "qhull internal error (qh_setdelnthsorted): nth %d is out-of-bounds for set:\n", nth);
     qh_setprint(qh, qh->qhmem.ferr, "", set);
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
   newp= (setelemT *)SETelemaddr_(set, nth, void);
   elem= newp->p;
   oldp= newp+1;
   while (((newp++)->p= (oldp++)->p))
     ; /* copy remaining elements and NULL */
   if ((sizep->i--)==0)         /*  if was a full set */
     sizep->i= set->maxsize;  /*     *sizep= (max size-1)+ 1 */
   return elem;
 } /* setdelnthsorted */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setdelsorted">-</a>
  
   qh_setdelsorted(set, oldelem )
     deletes oldelem from sorted set
  
   returns:
     returns oldelem if it was deleted
  
   notes:
     set may be NULL
  
   design:
     locate oldelem in set
     copy remaining elements down one
     update actual size
 */
 void *qh_setdelsorted(setT *set, void *oldelem) {
   setelemT *sizep;
   setelemT *newp, *oldp;
  
   if (!set)
     return NULL;
   newp= (setelemT *)SETaddr_(set, void);
   while(newp->p != oldelem && newp->p)
     newp++;
   if (newp->p) {
     oldp= newp+1;
     while (((newp++)->p= (oldp++)->p))
       ; /* copy remaining elements */
     sizep= SETsizeaddr_(set);
     if ((sizep->i--)==0)    /*  if was a full set */
       sizep->i= set->maxsize;  /*     *sizep= (max size-1)+ 1 */
     return oldelem;
   }
   return NULL;
 } /* setdelsorted */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setduplicate">-</a>
  
   qh_setduplicate(qh, set, elemsize )
     duplicate a set of elemsize elements
  
   notes:
     use setcopy if retaining old elements
  
   design:
     create a new set
     for each elem of the old set
       create a newelem
       append newelem to newset
 */
 setT *qh_setduplicate(qhT *qh, setT *set, int elemsize) {
   void          *elem, **elemp, *newElem;
   setT          *newSet;
   int           size;
  
   if (!(size= qh_setsize(qh, set)))
     return NULL;
   newSet= qh_setnew(qh, size);
   FOREACHelem_(set) {
     newElem= qh_memalloc(qh, elemsize);
     memcpy(newElem, elem, (size_t)elemsize);
     qh_setappend(qh, &newSet, newElem);
   }
   return newSet;
 } /* setduplicate */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setendpointer">-</a>
  
   qh_setendpointer( set )
     Returns pointer to NULL terminator of a set's elements
     set can not be NULL
  
 */
 void **qh_setendpointer(setT *set) {
  
   setelemT *sizep= SETsizeaddr_(set);
   int n= sizep->i;
   return (n ? &set->e[n-1].p : &sizep->p);
 } /* qh_setendpointer */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setequal">-</a>
  
   qh_setequal( setA, setB )
     returns 1 if two sorted sets are equal, otherwise returns 0
  
   notes:
     either set may be NULL
  
   design:
     check size of each set
     setup pointers
     compare elements of each set
 */
 int qh_setequal(setT *setA, setT *setB) {
   void **elemAp, **elemBp;
   int sizeA= 0, sizeB= 0;
  
   if (setA) {
     SETreturnsize_(setA, sizeA);
   }
   if (setB) {
     SETreturnsize_(setB, sizeB);
   }
   if (sizeA != sizeB)
     return 0;
   if (!sizeA)
     return 1;
   elemAp= SETaddr_(setA, void);
   elemBp= SETaddr_(setB, void);
   if (!memcmp((char *)elemAp, (char *)elemBp, sizeA*SETelemsize))
     return 1;
   return 0;
 } /* setequal */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setequal_except">-</a>
  
   qh_setequal_except( setA, skipelemA, setB, skipelemB )
     returns 1 if sorted setA and setB are equal except for skipelemA & B
  
   returns:
     false if either skipelemA or skipelemB are missing
  
   notes:
     neither set may be NULL
  
     if skipelemB is NULL,
       can skip any one element of setB
  
   design:
     setup pointers
     search for skipelemA, skipelemB, and mismatches
     check results
 */
 int qh_setequal_except(setT *setA, void *skipelemA, setT *setB, void *skipelemB) {
   void **elemA, **elemB;
   int skip=0;
  
   elemA= SETaddr_(setA, void);
   elemB= SETaddr_(setB, void);
   while (1) {
     if (*elemA == skipelemA) {
       skip++;
       elemA++;
     }
     if (skipelemB) {
       if (*elemB == skipelemB) {
         skip++;
         elemB++;
       }
     }else if (*elemA != *elemB) {
       skip++;
       if (!(skipelemB= *elemB++))
         return 0;
     }
     if (!*elemA)
       break;
     if (*elemA++ != *elemB++)
       return 0;
   }
   if (skip != 2 || *elemB)
     return 0;
   return 1;
 } /* setequal_except */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setequal_skip">-</a>
  
   qh_setequal_skip( setA, skipA, setB, skipB )
     returns 1 if sorted setA and setB are equal except for elements skipA & B
  
   returns:
     false if different size
  
   notes:
     neither set may be NULL
  
   design:
     setup pointers
     search for mismatches while skipping skipA and skipB
 */
 int qh_setequal_skip(setT *setA, int skipA, setT *setB, int skipB) {
   void **elemA, **elemB, **skipAp, **skipBp;
  
   elemA= SETaddr_(setA, void);
   elemB= SETaddr_(setB, void);
   skipAp= SETelemaddr_(setA, skipA, void);
   skipBp= SETelemaddr_(setB, skipB, void);
   while (1) {
     if (elemA == skipAp)
       elemA++;
     if (elemB == skipBp)
       elemB++;
     if (!*elemA)
       break;
     if (*elemA++ != *elemB++)
       return 0;
   }
   if (*elemB)
     return 0;
   return 1;
 } /* setequal_skip */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setfree">-</a>
  
   qh_setfree(qh, setp )
     frees the space occupied by a sorted or unsorted set
  
   returns:
     sets setp to NULL
  
   notes:
     set may be NULL
  
   design:
     free array
     free set
 */
 void qh_setfree(qhT *qh, setT **setp) {
   int size;
   void **freelistp;  /* used if !qh_NOmem by qh_memfree_() */
  
   if (*setp) {
     size= sizeof(setT) + ((*setp)->maxsize)*SETelemsize;
     if (size <= qh->qhmem.LASTsize) {
       qh_memfree_(qh, *setp, size, freelistp);
     }else
       qh_memfree(qh, *setp, size);
     *setp= NULL;
   }
 } /* setfree */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setfree2">-</a>
  
   qh_setfree2(qh, setp, elemsize )
     frees the space occupied by a set and its elements
  
   notes:
     set may be NULL
  
   design:
     free each element
     free set
 */
 void qh_setfree2(qhT *qh, setT **setp, int elemsize) {
   void          *elem, **elemp;
  
   FOREACHelem_(*setp)
     qh_memfree(qh, elem, elemsize);
   qh_setfree(qh, setp);
 } /* setfree2 */
  
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setfreelong">-</a>
  
   qh_setfreelong(qh, setp )
     frees a set only if it's in long memory
  
   returns:
     sets setp to NULL if it is freed
  
   notes:
     set may be NULL
  
   design:
     if set is large
       free it
 */
 void qh_setfreelong(qhT *qh, setT **setp) {
   int size;
  
   if (*setp) {
     size= sizeof(setT) + ((*setp)->maxsize)*SETelemsize;
     if (size > qh->qhmem.LASTsize) {
       qh_memfree(qh, *setp, size);
       *setp= NULL;
     }
   }
 } /* setfreelong */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setin">-</a>
  
   qh_setin(set, setelem )
     returns 1 if setelem is in a set, 0 otherwise
  
   notes:
     set may be NULL or unsorted
  
   design:
     scans set for setelem
 */
 int qh_setin(setT *set, void *setelem) {
   void *elem, **elemp;
  
   FOREACHelem_(set) {
     if (elem == setelem)
       return 1;
   }
   return 0;
 } /* setin */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setindex">-</a>
  
   qh_setindex(set, atelem )
     returns the index of atelem in set.
     returns -1, if not in set or maxsize wrong
  
   notes:
     set may be NULL and may contain nulls.
     NOerrors returned (qh_pointid, QhullPoint::id)
  
   design:
     checks maxsize
     scans set for atelem
 */
 int qh_setindex(setT *set, void *atelem) {
   void **elem;
   int size, i;
  
   if (!set)
     return -1;
   SETreturnsize_(set, size);
   if (size > set->maxsize)
     return -1;
   elem= SETaddr_(set, void);
   for (i=0; i < size; i++) {
     if (*elem++ == atelem)
       return i;
   }
   return -1;
 } /* setindex */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setlarger">-</a>
  
   qh_setlarger(qh, oldsetp )
     returns a larger set that contains all elements of *oldsetp
  
   notes:
     the set is at least twice as large
     if temp set, updates qh->qhmem.tempstack
  
   design:
     creates a new set
     copies the old set to the new set
     updates pointers in tempstack
     deletes the old set
 */
 void qh_setlarger(qhT *qh, setT **oldsetp) {
   int size= 1;
   setT *newset, *set, **setp, *oldset;
   setelemT *sizep;
   setelemT *newp, *oldp;
  
   if (*oldsetp) {
     oldset= *oldsetp;
     SETreturnsize_(oldset, size);
     qh->qhmem.cntlarger++;
     qh->qhmem.totlarger += size+1;
     newset= qh_setnew(qh, 2 * size);
     oldp= (setelemT *)SETaddr_(oldset, void);
     newp= (setelemT *)SETaddr_(newset, void);
     memcpy((char *)newp, (char *)oldp, (size_t)(size+1) * SETelemsize);
     sizep= SETsizeaddr_(newset);
     sizep->i= size+1;
     FOREACHset_((setT *)qh->qhmem.tempstack) {
       if (set == oldset)
         *(setp-1)= newset;
     }
     qh_setfree(qh, oldsetp);
   }else
     newset= qh_setnew(qh, 3);
   *oldsetp= newset;
 } /* setlarger */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setlast">-</a>
  
   qh_setlast( set )
     return last element of set or NULL (use type conversion)
  
   notes:
     set may be NULL
  
   design:
     return last element
 */
 void *qh_setlast(setT *set) {
   int size;
  
   if (set) {
     size= SETsizeaddr_(set)->i;
     if (!size)
       return SETelem_(set, set->maxsize - 1);
     else if (size > 1)
       return SETelem_(set, size - 2);
   }
   return NULL;
 } /* setlast */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setnew">-</a>
  
   qh_setnew(qh, setsize )
     creates and allocates space for a set
  
   notes:
     setsize means the number of elements (!including the NULL terminator)
     use qh_settemp/qh_setfreetemp if set is temporary
  
   design:
     allocate memory for set
     roundup memory if small set
     initialize as empty set
 */
 setT *qh_setnew(qhT *qh, int setsize) {
   setT *set;
   int sizereceived; /* used if !qh_NOmem */
   int size;
   void **freelistp; /* used if !qh_NOmem by qh_memalloc_() */
  
   if (!setsize)
     setsize++;
   size= sizeof(setT) + setsize * SETelemsize;
   if (size>0 && size <= qh->qhmem.LASTsize) {
     qh_memalloc_(qh, size, freelistp, set, setT);
 #ifndef qh_NOmem
     sizereceived= qh->qhmem.sizetable[ qh->qhmem.indextable[size]];
     if (sizereceived > size)
       setsize += (sizereceived - size)/SETelemsize;
 #endif
   }else
     set= (setT*)qh_memalloc(qh, size);
   set->maxsize= setsize;
   set->e[setsize].i= 1;
   set->e[0].p= NULL;
   return(set);
 } /* setnew */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setnew_delnthsorted">-</a>
  
   qh_setnew_delnthsorted(qh, set, size, nth, prepend )
     creates a sorted set not containing nth element
     if prepend, the first prepend elements are undefined
  
   notes:
     set must be defined
     checks nth
     see also: setdelnthsorted
  
   design:
     create new set
     setup pointers and allocate room for prepend'ed entries
     append head of old set to new set
     append tail of old set to new set
 */
 setT *qh_setnew_delnthsorted(qhT *qh, setT *set, int size, int nth, int prepend) {
   setT *newset;
   void **oldp, **newp;
   int tailsize= size - nth -1, newsize;
  
   if (tailsize < 0) {
     qh_fprintf(qh, qh->qhmem.ferr, 6176, "qhull internal error (qh_setnew_delnthsorted): nth %d is out-of-bounds for set:\n", nth);
     qh_setprint(qh, qh->qhmem.ferr, "", set);
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
   newsize= size-1 + prepend;
   newset= qh_setnew(qh, newsize);
   newset->e[newset->maxsize].i= newsize+1;  /* may be overwritten */
   oldp= SETaddr_(set, void);
   newp= SETaddr_(newset, void) + prepend;
   switch (nth) {
   case 0:
     break;
   case 1:
     *(newp++)= *oldp++;
     break;
   case 2:
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     break;
   case 3:
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     break;
   case 4:
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     break;
   default:
     memcpy((char *)newp, (char *)oldp, (size_t)nth * SETelemsize);
     newp += nth;
     oldp += nth;
     break;
   }
   oldp++;
   switch (tailsize) {
   case 0:
     break;
   case 1:
     *(newp++)= *oldp++;
     break;
   case 2:
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     break;
   case 3:
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     break;
   case 4:
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     *(newp++)= *oldp++;
     break;
   default:
     memcpy((char *)newp, (char *)oldp, (size_t)tailsize * SETelemsize);
     newp += tailsize;
   }
   *newp= NULL;
   return(newset);
 } /* setnew_delnthsorted */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setprint">-</a>
  
   qh_setprint(qh, fp, string, set )
     print set elements to fp with identifying string
  
   notes:
     never errors
 */
 void qh_setprint(qhT *qh, FILE *fp, const char* string, setT *set) {
   int size, k;
  
   if (!set)
     qh_fprintf(qh, fp, 9346, "%s set is null\n", string);
   else {
     SETreturnsize_(set, size);
     qh_fprintf(qh, fp, 9347, "%s set=%p maxsize=%d size=%d elems=",
              string, set, set->maxsize, size);
     if (size > set->maxsize)
       size= set->maxsize+1;
     for (k=0; k < size; k++)
       qh_fprintf(qh, fp, 9348, " %p", set->e[k].p);
     qh_fprintf(qh, fp, 9349, "\n");
   }
 } /* setprint */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setreplace">-</a>
  
   qh_setreplace(qh, set, oldelem, newelem )
     replaces oldelem in set with newelem
  
   notes:
     errors if oldelem not in the set
     newelem may be NULL, but it turns the set into an indexed set (no FOREACH)
  
   design:
     find oldelem
     replace with newelem
 */
 void qh_setreplace(qhT *qh, setT *set, void *oldelem, void *newelem) {
   void **elemp;
  
   elemp= SETaddr_(set, void);
   while (*elemp != oldelem && *elemp)
     elemp++;
   if (*elemp)
     *elemp= newelem;
   else {
     qh_fprintf(qh, qh->qhmem.ferr, 6177, "qhull internal error (qh_setreplace): elem %p not found in set\n",
        oldelem);
     qh_setprint(qh, qh->qhmem.ferr, "", set);
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
 } /* setreplace */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setsize">-</a>
  
   qh_setsize(qh, set )
     returns the size of a set
  
   notes:
     errors if set's maxsize is incorrect
     same as SETreturnsize_(set)
     same code for qh_setsize [qset_r.c] and QhullSetBase::count
  
   design:
     determine actual size of set from maxsize
 */
 int qh_setsize(qhT *qh, setT *set) {
   int size;
   setelemT *sizep;
  
   if (!set)
     return(0);
   sizep= SETsizeaddr_(set);
   if ((size= sizep->i)) {
     size--;
     if (size > set->maxsize) {
       qh_fprintf(qh, qh->qhmem.ferr, 6178, "qhull internal error (qh_setsize): current set size %d is greater than maximum size %d\n",
                size, set->maxsize);
       qh_setprint(qh, qh->qhmem.ferr, "set: ", set);
       qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
     }
   }else
     size= set->maxsize;
   return size;
 } /* setsize */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="settemp">-</a>
  
   qh_settemp(qh, setsize )
     return a stacked, temporary set of upto setsize elements
  
   notes:
     use settempfree or settempfree_all to release from qh->qhmem.tempstack
     see also qh_setnew
  
   design:
     allocate set
     append to qh->qhmem.tempstack
  
 */
 setT *qh_settemp(qhT *qh, int setsize) {
   setT *newset;
  
   newset= qh_setnew(qh, setsize);
   qh_setappend(qh, &qh->qhmem.tempstack, newset);
   if (qh->qhmem.IStracing >= 5)
     qh_fprintf(qh, qh->qhmem.ferr, 8123, "qh_settemp: temp set %p of %d elements, depth %d\n",
        newset, newset->maxsize, qh_setsize(qh, qh->qhmem.tempstack));
   return newset;
 } /* settemp */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="settempfree">-</a>
  
   qh_settempfree(qh, set )
     free temporary set at top of qh->qhmem.tempstack
  
   notes:
     nop if set is NULL
     errors if set not from previous   qh_settemp
  
   to locate errors:
     use 'T2' to find source and then find mis-matching qh_settemp
  
   design:
     check top of qh->qhmem.tempstack
     free it
 */
 void qh_settempfree(qhT *qh, setT **set) {
   setT *stackedset;
  
   if (!*set)
     return;
   stackedset= qh_settemppop(qh);
   if (stackedset != *set) {
     qh_settemppush(qh, stackedset);
     qh_fprintf(qh, qh->qhmem.ferr, 6179, "qhull internal error (qh_settempfree): set %p(size %d) was not last temporary allocated(depth %d, set %p, size %d)\n",
              *set, qh_setsize(qh, *set), qh_setsize(qh, qh->qhmem.tempstack)+1,
              stackedset, qh_setsize(qh, stackedset));
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
   qh_setfree(qh, set);
 } /* settempfree */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="settempfree_all">-</a>
  
   qh_settempfree_all(qh)
     free all temporary sets in qh->qhmem.tempstack
  
   design:
     for each set in tempstack
       free set
     free qh->qhmem.tempstack
 */
 void qh_settempfree_all(qhT *qh) {
   setT *set, **setp;
  
   FOREACHset_(qh->qhmem.tempstack)
     qh_setfree(qh, &set);
   qh_setfree(qh, &qh->qhmem.tempstack);
 } /* settempfree_all */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="settemppop">-</a>
  
   qh_settemppop(qh)
     pop and return temporary set from qh->qhmem.tempstack
  
   notes:
     the returned set is permanent
  
   design:
     pop and check top of qh->qhmem.tempstack
 */
 setT *qh_settemppop(qhT *qh) {
   setT *stackedset;
  
   stackedset= (setT*)qh_setdellast(qh->qhmem.tempstack);
   if (!stackedset) {
     qh_fprintf(qh, qh->qhmem.ferr, 6180, "qhull internal error (qh_settemppop): pop from empty temporary stack\n");
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
   if (qh->qhmem.IStracing >= 5)
     qh_fprintf(qh, qh->qhmem.ferr, 8124, "qh_settemppop: depth %d temp set %p of %d elements\n",
        qh_setsize(qh, qh->qhmem.tempstack)+1, stackedset, qh_setsize(qh, stackedset));
   return stackedset;
 } /* settemppop */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="settemppush">-</a>
  
   qh_settemppush(qh, set )
     push temporary set unto qh->qhmem.tempstack (makes it temporary)
  
   notes:
     duplicates settemp() for tracing
  
   design:
     append set to tempstack
 */
 void qh_settemppush(qhT *qh, setT *set) {
   if (!set) {
     qh_fprintf(qh, qh->qhmem.ferr, 6267, "qhull error (qh_settemppush): can not push a NULL temp\n");
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
   qh_setappend(qh, &qh->qhmem.tempstack, set);
   if (qh->qhmem.IStracing >= 5)
     qh_fprintf(qh, qh->qhmem.ferr, 8125, "qh_settemppush: depth %d temp set %p of %d elements\n",
       qh_setsize(qh, qh->qhmem.tempstack), set, qh_setsize(qh, set));
 } /* settemppush */
  
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="settruncate">-</a>
  
   qh_settruncate(qh, set, size )
     truncate set to size elements
  
   notes:
     set must be defined
  
   see:
     SETtruncate_
  
   design:
     check size
     update actual size of set
 */
 void qh_settruncate(qhT *qh, setT *set, int size) {
  
   if (size < 0 || size > set->maxsize) {
     qh_fprintf(qh, qh->qhmem.ferr, 6181, "qhull internal error (qh_settruncate): size %d out of bounds for set:\n", size);
     qh_setprint(qh, qh->qhmem.ferr, "", set);
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
   set->e[set->maxsize].i= size+1;   /* maybe overwritten */
   set->e[size].p= NULL;
 } /* settruncate */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setunique">-</a>
  
   qh_setunique(qh, set, elem )
     add elem to unsorted set unless it is already in set
  
   notes:
     returns 1 if it is appended
  
   design:
     if elem not in set
       append elem to set
 */
 int qh_setunique(qhT *qh, setT **set, void *elem) {
  
   if (!qh_setin(*set, elem)) {
     qh_setappend(qh, set, elem);
     return 1;
   }
   return 0;
 } /* setunique */
  
 /*-<a                             href="qh-set_r.htm#TOC"
   >-------------------------------<a name="setzero">-</a>
  
   qh_setzero(qh, set, index, size )
     zero elements from index on
     set actual size of set to size
  
   notes:
     set must be defined
     the set becomes an indexed set (can not use FOREACH...)
  
   see also:
     qh_settruncate
  
   design:
     check index and size
     update actual size
     zero elements starting at e[index]
 */
 void qh_setzero(qhT *qh, setT *set, int idx, int size) {
   int count;
  
   if (idx < 0 || idx >= size || size > set->maxsize) {
     qh_fprintf(qh, qh->qhmem.ferr, 6182, "qhull internal error (qh_setzero): index %d or size %d out of bounds for set:\n", idx, size);
     qh_setprint(qh, qh->qhmem.ferr, "", set);
     qh_errexit(qh, qhmem_ERRqhull, NULL, NULL);
   }
   set->e[set->maxsize].i=  size+1;  /* may be overwritten */
   count= size - idx + 1;   /* +1 for NULL terminator */
   memset((char *)SETelemaddr_(set, idx, void), 0, (size_t)count * SETelemsize);
 } /* setzero */
  
  