qset.c

关于网格剖分的

/*-<a                             href="qh-c.htm#set"
  >-------------------------------<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 **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 */


/*-<a                             href="qh-c.htm#set"
  >-------------------------------<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) {
  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 */


/*-<a                             href="qh-c.htm#set"
  >-------------------------------<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, elemsize);
    qh_setappend (&newSet, newElem);
  }
  return newSet;
} /* setduplicate */


/*-<a                             href="qh-c.htm#set"
  >-------------------------------<a name="setequal">-</a>
  
  qh_setequal(  )
    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, 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 */


/*-<a                             href="qh-c.htm#set"
  >-------------------------------<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-c.htm#set"
  >-------------------------------<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-c.htm#set"
  >-------------------------------<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 !qh_NOmem */
  
  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-c.htm#set"
  >-------------------------------<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-c.htm#set"
  >-------------------------------<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-c.htm#set"
  >-------------------------------<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-c.htm#set"
  >-------------------------------<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.

  design:
    checks maxsize
    scans set for atelem
*/
int qh_setindex(setT *set, void *atelem) {
  void **elem;
  int size, i;

  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-c.htm#set"
  >-------------------------------<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, *sizep;
  setT *newset, *set, **setp, *oldset;
  void **oldp, **newp;

  if (*oldsetp) {
    oldset= *oldsetp;
    SETreturnsize_(oldset, size);
    qhmem.cntlarger++;
    qhmem.totlarger += size+1;
    newset= qh_setnew(2 * size);
    oldp= SETaddr_(oldset, void);
    newp= SETaddr_(newset, void);
    memcpy((char *)newp, (char *)oldp, (size+1) * SETelemsize);
    sizep= SETsizeaddr_(newset);
    *sizep= 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-c.htm#set"
  >-------------------------------<a name="setlast">-</a>
  
  qh_setlast(  )
    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);
    if (!size)