set.c

Oversampling Delta-Sigma Data Converters

/* 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 qhDEFqhull
void    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 NULL
returns:
  updates set
notes:
  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 another
returns:
  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 elements
notes:
  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);