text: /*<html><pre>  -<a                             href="qh-set.htm"
    >-------------------------------</a><a name="TOP">-</a>
  
     qset.c
     implements set manipulations needed for quickhull
  
     see qh-set.htm and qset.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/qset.c#3 $$Change: 2062 $
     $DateTime: 2016/01/17 13:13:18 $$Author: bbarber $
  */
  
  #include "user.h" /* for QHULL_CRTDBG */
  #include "qset.h"
  #include "mem.h"
  #include <stdio.h>
  #include <string.h>
  /*** uncomment here and qhull_a.h
       if string.h does not define memcpy()
  #include <memory.h>
  */
  
  #ifndef qhDEFlibqhull
  typedef struct ridgeT ridgeT;
  typedef struct facetT facetT;
  
  void qh_errexit(int exitcode, facetT *, ridgeT *);
  
  void qh_fprintf(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.htm#TOC"
    >--------------------------------<a name="setaddnth">-</a>
  
    qh_setaddnth( 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(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(setp);
          sizep = SETsizeaddr_(*setp);
      }
      oldsize = sizep->i - 1;
      if (nth < 0 || nth > oldsize) {
          qh_fprintf(qhmem.ferr, 6171, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
          qh_setprint(qhmem.ferr, "", *setp);
          qh_errexit(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.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(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(setp, newindex, newelem);
  } /* setaddsorted */
  
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="setappend">-</a>
  
    qh_setappend( 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(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(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.htm#TOC"
    >-------------------------------<a name="setappend_set">-</a>
  
    qh_setappend_set( 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(setT **setp, setT *setA) {
      int sizeA, size;
      setT *oldset;
      setelemT *sizep;
  
      if (!setA)
          return;
      SETreturnsize_(setA, sizeA);
      if (!*setp)
          *setp = qh_setnew(sizeA);
      sizep = SETsizeaddr_(*setp);
      if (!(size = sizep->i))
          size = (*setp)->maxsize;
      else
          size--;
      if (size + sizeA > (*setp)->maxsize) {
          oldset = *setp;
          *setp = qh_setcopy(oldset, sizeA);
          qh_setfree(&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.htm#TOC"
    >-------------------------------<a name="setappend2ndlast">-</a>
  
    qh_setappend2ndlast( 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(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(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.htm#TOC"
    >-------------------------------<a name="setcheck">-</a>
  
    qh_setcheck( 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(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(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(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(qhmem.ferr, "ERRONEOUS", set);
          qh_errexit(qhmem_ERRqhull, NULL, NULL);
      }
  } /* setcheck */
  
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="setcompact">-</a>
  
    qh_setcompact( 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(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(set, (int) (destp - firstp));   /* WARN64 */
  } /* setcompact */
  
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="setcopy">-</a>
  
    qh_setcopy( 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(setT *set, int extra) {
      setT *newset;
      int size;
  
      if (extra < 0)
          extra = 0;
      SETreturnsize_(set, size);
      newset = qh_setnew(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.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.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.htm#TOC"
    >-------------------------------<a name="setdelnth">-</a>
  
    qh_setdelnth( 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(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(qhmem.ferr, 6174, "qhull internal error (qh_setdelnth): nth %d is out-of-bounds for set:\n", nth);
          qh_setprint(qhmem.ferr, "", set);
          qh_errexit(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.htm#TOC"
    >-------------------------------<a name="setdelnthsorted">-</a>
  
    qh_setdelnthsorted( 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(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(qhmem.ferr, 6175, "qhull internal error (qh_setdelnthsorted): nth %d is out-of-bounds for set:\n",
                     nth);
          qh_setprint(qhmem.ferr, "", set);
          qh_errexit(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.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.htm#TOC"
    >-------------------------------<a name="setduplicate">-</a>
  
    qh_setduplicate( 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(setT *set, int elemsize) {
      void *elem, **elemp, *newElem;
      setT *newSet;
      int size;
  
      if (!(size = qh_setsize(set)))
          return NULL;
      newSet = qh_setnew(size);
      FOREACHelem_(set) {
              newElem = qh_memalloc(elemsize);
              memcpy(newElem, elem, (size_t) elemsize);
              qh_setappend(&newSet, newElem);
          }
      return newSet;
  } /* setduplicate */
  
  
  /*-<a                             href="qh-set.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.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.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.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.htm#TOC"
    >-------------------------------<a name="setfree">-</a>
  
    qh_setfree( 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(setT **setp) {
      int size;
      void **freelistp;  /* used if !qh_NOmem by qh_memfree_() */
  
      if (*setp) {
          size = sizeof(setT) + ((*setp)->maxsize) * SETelemsize;
          if (size <= qhmem.LASTsize) {
              qh_memfree_(*setp, size, freelistp);
          } else
              qh_memfree(*setp, size);
          *setp = NULL;
      }
  } /* setfree */
  
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="setfree2">-</a>
  
    qh_setfree2( 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(setT **setp, int elemsize) {
      void *elem, **elemp;
  
      FOREACHelem_(*setp)qh_memfree(elem, elemsize);
      qh_setfree(setp);
  } /* setfree2 */
  
  
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="setfreelong">-</a>
  
    qh_setfreelong( 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(setT **setp) {
      int size;
  
      if (*setp) {
          size = sizeof(setT) + ((*setp)->maxsize) * SETelemsize;
          if (size > qhmem.LASTsize) {
              qh_memfree(*setp, size);
              *setp = NULL;
          }
      }
  } /* setfreelong */
  
  
  /*-<a                             href="qh-set.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.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.htm#TOC"
    >-------------------------------<a name="setlarger">-</a>
  
    qh_setlarger( oldsetp )
      returns a larger set that contains all elements of *oldsetp
  
    notes:
      the set is at least twice as large
      if temp set, updates 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(setT **oldsetp) {
      int size = 1;
      setT *newset, *set, **setp, *oldset;
      setelemT *sizep;
      setelemT *newp, *oldp;
  
      if (*oldsetp) {
          oldset = *oldsetp;
          SETreturnsize_(oldset, size);
          qhmem.cntlarger++;
          qhmem.totlarger += size + 1;
          newset = qh_setnew(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 *) qhmem.tempstack) {
                  if (set == oldset)
                      *(setp - 1) = newset;
              }
          qh_setfree(oldsetp);
      } else
          newset = qh_setnew(3);
      *oldsetp = newset;
  } /* setlarger */
  
  
  /*-<a                             href="qh-set.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.htm#TOC"
    >-------------------------------<a name="setnew">-</a>
  
    qh_setnew( 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(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 <= qhmem.LASTsize) {
          qh_memalloc_(size, freelistp, set, setT);
  #ifndef qh_NOmem
          sizereceived = qhmem.sizetable[qhmem.indextable[size]];
          if (sizereceived > size)
              setsize += (sizereceived - size) / SETelemsize;
  #endif
      } else
          set = (setT *) qh_memalloc(size);
      set->maxsize = setsize;
      set->e[setsize].i = 1;
      set->e[0].p = NULL;
      return (set);
  } /* setnew */
  
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="setnew_delnthsorted">-</a>
  
    qh_setnew_delnthsorted( 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(setT *set, int size, int nth, int prepend) {
      setT *newset;
      void **oldp, **newp;
      int tailsize = size - nth - 1, newsize;
  
      if (tailsize < 0) {
          qh_fprintf(qhmem.ferr, 6176,
                     "qhull internal error (qh_setnew_delnthsorted): nth %d is out-of-bounds for set:\n", nth);
          qh_setprint(qhmem.ferr, "", set);
          qh_errexit(qhmem_ERRqhull, NULL, NULL);
      }
      newsize = size - 1 + prepend;
      newset = qh_setnew(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.htm#TOC"
    >-------------------------------<a name="setprint">-</a>
  
    qh_setprint( fp, string, set )
      print set elements to fp with identifying string
  
    notes:
      never errors
  */
  void qh_setprint(FILE *fp, const char *string, setT *set) {
      int size, k;
  
      if (!set)
          qh_fprintf(fp, 9346, "%s set is null\n", string);
      else {
          SETreturnsize_(set, size);
          qh_fprintf(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(fp, 9348, " %p", set->e[k].p);
          qh_fprintf(fp, 9349, "\n");
      }
  } /* setprint */
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="setreplace">-</a>
  
    qh_setreplace( 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(setT *set, void *oldelem, void *newelem) {
      void **elemp;
  
      elemp = SETaddr_(set, void);
      while (*elemp != oldelem && *elemp)
          elemp++;
      if (*elemp)
          *elemp = newelem;
      else {
          qh_fprintf(qhmem.ferr, 6177, "qhull internal error (qh_setreplace): elem %p not found in set\n",
                     oldelem);
          qh_setprint(qhmem.ferr, "", set);
          qh_errexit(qhmem_ERRqhull, NULL, NULL);
      }
  } /* setreplace */
  
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="setsize">-</a>
  
    qh_setsize( 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.c] and QhullSetBase::count
  
    design:
      determine actual size of set from maxsize
  */
  int qh_setsize(setT *set) {
      int size;
      setelemT *sizep;
  
      if (!set)
          return (0);
      sizep = SETsizeaddr_(set);
      if ((size = sizep->i)) {
          size--;
          if (size > set->maxsize) {
              qh_fprintf(qhmem.ferr, 6178,
                         "qhull internal error (qh_setsize): current set size %d is greater than maximum size %d\n",
                         size, set->maxsize);
              qh_setprint(qhmem.ferr, "set: ", set);
              qh_errexit(qhmem_ERRqhull, NULL, NULL);
          }
      } else
          size = set->maxsize;
      return size;
  } /* setsize */
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="settemp">-</a>
  
    qh_settemp( setsize )
      return a stacked, temporary set of upto setsize elements
  
    notes:
      use settempfree or settempfree_all to release from qhmem.tempstack
      see also qh_setnew
  
    design:
      allocate set
      append to qhmem.tempstack
  
  */
  setT *qh_settemp(int setsize) {
      setT *newset;
  
      newset = qh_setnew(setsize);
      qh_setappend(&qhmem.tempstack, newset);
      if (qhmem.IStracing >= 5)
          qh_fprintf(qhmem.ferr, 8123, "qh_settemp: temp set %p of %d elements, depth %d\n",
                     newset, newset->maxsize, qh_setsize(qhmem.tempstack));
      return newset;
  } /* settemp */
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="settempfree">-</a>
  
    qh_settempfree( set )
      free temporary set at top of 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 qhmem.tempstack
      free it
  */
  void qh_settempfree(setT **set) {
      setT *stackedset;
  
      if (!*set)
          return;
      stackedset = qh_settemppop();
      if (stackedset != *set) {
          qh_settemppush(stackedset);
          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",
                     *set, qh_setsize(*set), qh_setsize(qhmem.tempstack) + 1,
                     stackedset, qh_setsize(stackedset));
          qh_errexit(qhmem_ERRqhull, NULL, NULL);
      }
      qh_setfree(set);
  } /* settempfree */
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="settempfree_all">-</a>
  
    qh_settempfree_all(  )
      free all temporary sets in qhmem.tempstack
  
    design:
      for each set in tempstack
        free set
      free qhmem.tempstack
  */
  void qh_settempfree_all(void) {
      setT *set, **setp;
  
      FOREACHset_(qhmem.tempstack)qh_setfree(&set);
      qh_setfree(&qhmem.tempstack);
  } /* settempfree_all */
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="settemppop">-</a>
  
    qh_settemppop(  )
      pop and return temporary set from qhmem.tempstack
  
    notes:
      the returned set is permanent
  
    design:
      pop and check top of qhmem.tempstack
  */
  setT *qh_settemppop(void) {
      setT *stackedset;
  
      stackedset = (setT *) qh_setdellast(qhmem.tempstack);
      if (!stackedset) {
          qh_fprintf(qhmem.ferr, 6180, "qhull internal error (qh_settemppop): pop from empty temporary stack\n");
          qh_errexit(qhmem_ERRqhull, NULL, NULL);
      }
      if (qhmem.IStracing >= 5)
          qh_fprintf(qhmem.ferr, 8124, "qh_settemppop: depth %d temp set %p of %d elements\n",
                     qh_setsize(qhmem.tempstack) + 1, stackedset, qh_setsize(stackedset));
      return stackedset;
  } /* settemppop */
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="settemppush">-</a>
  
    qh_settemppush( set )
      push temporary set unto qhmem.tempstack (makes it temporary)
  
    notes:
      duplicates settemp() for tracing
  
    design:
      append set to tempstack
  */
  void qh_settemppush(setT *set) {
      if (!set) {
          qh_fprintf(qhmem.ferr, 6267, "qhull error (qh_settemppush): can not push a NULL temp\n");
          qh_errexit(qhmem_ERRqhull, NULL, NULL);
      }
      qh_setappend(&qhmem.tempstack, set);
      if (qhmem.IStracing >= 5)
          qh_fprintf(qhmem.ferr, 8125, "qh_settemppush: depth %d temp set %p of %d elements\n",
                     qh_setsize(qhmem.tempstack), set, qh_setsize(set));
  } /* settemppush */
  
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="settruncate">-</a>
  
    qh_settruncate( 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(setT *set, int size) {
  
      if (size < 0 || size > set->maxsize) {
          qh_fprintf(qhmem.ferr, 6181, "qhull internal error (qh_settruncate): size %d out of bounds for set:\n", size);
          qh_setprint(qhmem.ferr, "", set);
          qh_errexit(qhmem_ERRqhull, NULL, NULL);
      }
      set->e[set->maxsize].i = size + 1;   /* maybe overwritten */
      set->e[size].p = NULL;
  } /* settruncate */
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="setunique">-</a>
  
    qh_setunique( 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(setT **set, void *elem) {
  
      if (!qh_setin(*set, elem)) {
          qh_setappend(set, elem);
          return 1;
      }
      return 0;
  } /* setunique */
  
  /*-<a                             href="qh-set.htm#TOC"
    >-------------------------------<a name="setzero">-</a>
  
    qh_setzero( 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(setT *set, int idx, int size) {
      int count;
  
      if (idx < 0 || idx >= size || size > set->maxsize) {
          qh_fprintf(qhmem.ferr, 6182, "qhull internal error (qh_setzero): index %d or size %d out of bounds for set:\n",
                     idx, size);
          qh_setprint(qhmem.ferr, "", set);
          qh_errexit(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 */
  
  
  