/* set.c -- implements set manipulations needed for quickhull    see README and set.h      copyright (c) 1993-1995 The Geometry Center        */#include <stdio.h>#include <memory.h>#include <string.h>#include "set.h"#include "mem.h"#ifndef qhDEFqhullvoid    qh_errexit(int exitcode, void *, void *);#endif/*----------- internal macros --------------------SETsizeaddr_(set) - return pointer to actual size+1 of set (set CANNOT be NULL!!)    *SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL*/#define SETsizeaddr_(set) (&((set)->e[(set)->maxsize].i))/*============ functions in alphabetical order ===================*/  /*-----------------------------------------setaddnth- adds newelem as n'th element of sorted or unsorted set  setp and newelem must be defined  set may be a temp set  nth=0 is first element  errors if nth is out of bounds*/void qh_setaddnth(setT **setp, int nth, void *newelem) {  int *sizep, oldsize, i;  void **oldp, **newp;  if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {    qh_setlarger(setp);    sizep= SETsizeaddr_(*setp);  }  oldsize= *sizep - 1;  if (nth < 0 || nth > oldsize) {    fprintf (qhmem.ferr, "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)++;  oldp= SETelemaddr_(*setp, oldsize, void);   /* NULL */  newp= oldp+1;  for (i= oldsize-nth+1; i--; )  /* move at least NULL  */    *(newp--)= *(oldp--);       /* may overwrite *sizep */  *newp= newelem;} /* setaddnth *//*-----------------------------------------setaddsorted- adds an element to a sorted set  setp and newelem must be defined  set may be a temp set  nop if newelem already in set*/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 *//*-----------------------------------------setappend- appends an element to a set  set may be a temp set  *setp and newelem may be NULL*/void qh_setappend(setT **setp, void *newelem) {  int *sizep;  void **endp;  if (!newelem)    return;  if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {    qh_setlarger(setp);    sizep= SETsizeaddr_(*setp);  }  *(endp= &((*setp)->e[(*sizep)++ - 1].p))= newelem;  *(++endp)= NULL;} /* setappend *//*-----------------------------------------setappend_set- appends a set to a set  *setp and set may be NULL  setp can not be a temp set*/void qh_setappend_set(setT **setp, setT *setA) {  int *sizep, sizeA, size;  setT *oldset;  if (!setA)    return;  SETreturnsize_(setA, sizeA);  if (!*setp)    *setp= qh_setnew (sizeA);  sizep= SETsizeaddr_(*setp);  if (!(size= *sizep))    size= (*setp)->maxsize;  else    size--;  if (size + sizeA > (*setp)->maxsize) {    oldset= *setp;    *setp= qh_setcopy (oldset, sizeA);    qh_setfree (&oldset);    sizep= SETsizeaddr_(*setp);  }  *sizep= size+sizeA+1;   /* memcpy may overwrite */  if (sizeA > 0)     memcpy((char *)&((*setp)->e[size].p), (char *)&(setA->e[0].p), SETelemsize *(sizeA+1));} /* setappend_set *//*-----------------------------------------setappend2ndlast- makes newelem the next to the last element in set  set must have at least one element, newelem must be defined  set may be a temp set*/void qh_setappend2ndlast(setT **setp, void *newelem) {  int *sizep;  void **endp, **lastp;    if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {    qh_setlarger(setp);    sizep= SETsizeaddr_(*setp);  }  endp= SETelemaddr_(*setp, (*sizep)++ -1, void); /* NULL */  lastp= endp-1;  *(endp++)= *lastp;  *endp= NULL;    /* may overwrite *sizep */  *lastp= newelem;} /* setappend2ndlast *//*-----------------------------------------setcheck- check set for validity*/void qh_setcheck(setT *set, char *typename, int id) {  int maxsize, size;  int waserr= 0;  if (!set)    return;  SETreturnsize_(set, size);  maxsize= set->maxsize;  if (size > maxsize || !maxsize) {    fprintf (qhmem.ferr, "qhull internal error (qh_setcheck): actual size %d of %s%d is greater than max size %d\n",	     size, typename, id, maxsize);    waserr= 1;  }else if (set->e[size].p) {    fprintf (qhmem.ferr, "qhull internal error (qh_setcheck): %s%d (size %d max %d) is not null terminated.\n",	     typename, id, maxsize, size-1);    waserr= 1;  }  if (waserr) {    qh_setprint (qhmem.ferr, "ERRONEOUS", set);    qh_errexit (qhmem_ERRqhull, NULL, NULL);  }} /* setcheck *//*-----------------------------------------setcompact- compact NULLs in an unsorted set  set may be NULLreturns:  updates setnotes:  is faster to swap tail of set into holes, like qh_setdel*/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, destp-firstp);} /* setcompact *//*-----------------------------------------setcopy- copies a sorted or unsorted set into anotherreturns:  new set is actual size of old set plus extra*/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)= size+1;    /* memcpy may overwrite */  memcpy((char *)&(newset->e[0].p), (char *)&(set->e[0].p), SETelemsize *(size+1));  return (newset);} /* setcopy *//*-----------------------------------------setdel- deletes oldelem from unsorted set.   if found, overwrites newlelem with lastelem   set may be NULL, oldelem must not be NULL;returns:  returns oldelem if it was deleted (use type conversion)notes:  only deletes one copy of oldelem in set*/void *qh_setdel(setT *set, void *oldelem) {  void **elemp, **lastp;  int *sizep;  if (!set)    return NULL;  elemp= SETaddr_(set, void);  while (*elemp != oldelem && *elemp)    elemp++;  if (*elemp) {    sizep= SETsizeaddr_(set);    if (!(*sizep)--)         /*  if was a full set */      *sizep= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */    lastp= SETelemaddr_(set, *sizep-1, void);    *elemp= *lastp;      /* may overwrite itself */    *lastp= NULL;    return oldelem;  }  return NULL;} /* setdel *//*-----------------------------------------setdellast- return last element of set or NULL (use type conversion)   delete element from set   set may be NULL*/void *qh_setdellast(setT *set) {  int setsize;  /* actually, actual_size + 1 */  int maxsize;  int *sizep;  void *returnvalue;    if (!set || !(set->e[0].p))    return NULL;  sizep= SETsizeaddr_(set);  if ((setsize= *sizep)) {    returnvalue= set->e[setsize - 2].p;    set->e[setsize - 2].p= NULL;    (*sizep)--;  }else {    maxsize= set->maxsize;    returnvalue= set->e[maxsize - 1].p;    set->e[maxsize - 1].p= NULL;    *sizep= maxsize;  }  return returnvalue;} /* setdellast *//*-----------------------------------------setdelnth- deletes nth element from unsorted set   errors if nth invalid  returns the element (use type conversion)*/void *qh_setdelnth(setT *set, int nth) {  void **elemp, **lastp, *elem;  int *sizep;  elemp= SETelemaddr_(set, nth, void);  sizep= SETsizeaddr_(set);  if (!(*sizep)--)         /*  if was a full set */    *sizep= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */  if (nth < 0 || nth >= *sizep) {    fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);    qh_setprint (qhmem.ferr, "", set);    qh_errexit (qhmem_ERRqhull, NULL, NULL);  }  lastp= SETelemaddr_(set, *sizep-1, void);  elem= *elemp;  *elemp= *lastp;      /* may overwrite itself */  *lastp= NULL;  return elem;} /* setdelnth *//*-----------------------------------------setdelnthsorted- deletes nth element from sorted set  sort order is undefined  errors if nth invalid  returns the element (use type conversion)  see also: setnew_delnthsorted*/void *qh_setdelnthsorted(setT *set, int nth) {  void **newp, **oldp, *elem;  int *sizep;  sizep= SETsizeaddr_(set);  if (nth < 0 || (*sizep && nth >= *sizep-1) || nth >= set->maxsize) {    fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);    qh_setprint (qhmem.ferr, "", set);    qh_errexit (qhmem_ERRqhull, NULL, NULL);  }  newp= SETelemaddr_(set, nth, void);  elem= *newp;  oldp= newp+1;  while ((*(newp++)= *(oldp++)))    ; /* copy remaining elements and NULL */  if (!(*sizep)--)         /*  if was a full set */    *sizep= set->maxsize;  /*     *sizep= (max size-1)+ 1 */  return elem;} /* setdelnthsorted *//*-----------------------------------------setdelsorted- deletes oldelem from sorted set  sort order is undefined  set may be NULL  returns oldelem if it was deleted*/void *qh_setdelsorted(setT *set, void *oldelem) {  void **newp, **oldp;  int *sizep;  if (!set)    return NULL;  newp= SETaddr_(set, void);  while(*newp != oldelem && *newp)    newp++;  if (*newp) {    oldp= newp+1;    while ((*(newp++)= *(oldp++)))      ; /* copy remaining elements */    sizep= SETsizeaddr_(set);    if (!(*sizep)--)    /*  if was a full set */      *sizep= set->maxsize;  /*     *sizep= (max size-1)+ 1 */    return oldelem;  }  return NULL;} /* setdelsorted *//*-----------------------------------------setduplicate- duplicate a set of elementsnotes:  use setcopy if retaining old elements*/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, elemsize);    qh_setappend (&newSet, newElem);  }  return newSet;} /* setduplicate *//*-----------------------------------------setequal- returns 1 if two sorted sets are equal, otherwise returns 0    either set may be NULL*/int qh_setequal(setT *setA, setT *setB) {  void **elemAp, **elemBp;  int sizeA, sizeB;    SETreturnsize_(setA, sizeA);  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 *//*-----------------------------------------setequal_except- returns 1 if two sorted sets are equal except for 2 elements  neither set may be NULL  false if either skip is missing  if second skip is NULL,      can skip any one element*/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 */  /*-----------------------------------------setequal_skip- returns 1 if two sorted sets are equal except for skips  neither set may be NULL  false if different size*/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);