src/libqhull/qset.c

/*<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 */