pelqhull.cc

Gambit 是一个游戏库理论软件

/*----------------------------------------
-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]), (char *)&(set->e[0]), 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
*/
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
   delete element from set
   set may be NULL
*/
void *qh_setdellast(setT *set) {
  int setsize;
  void **last;
  void *returnvalue;
  
  if (!set || !(set->e[0]))
    return NULL;
  if ((setsize= (int)*(last= &(set->e[set->maxsize])))) {
    returnvalue= set->e[setsize - 2];
    set->e[setsize - 2]= NULL;
    *last= (void *)((int)*last - 1);
  }else {
    returnvalue= set->e[set->maxsize - 1];
    set->e[set->maxsize - 1]= NULL;
    *last= (void *)(set->maxsize);
  }
  return returnvalue;
} /* setdellast */


/*----------------------------------------
-setdelnth- deletes nth element from unsorted set 
  errors if nth invalid
  returns the element
*/
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) qhull_fatal(12);

  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
  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 >= (int)set->maxsize ) 
    qhull_fatal(13);

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


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

/*----------------------------------------
-setfree- frees the space occupied by a sorted or unsorted set
  set may be NULL
*/
void qh_setfree(setT **setp) {
  int size;
  void **freelistp;
  
  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 */


/*----------------------------------------
-setfreelong- frees a set only if it's in long memory
  set may be NULL
*/
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 */


/*----------------------------------------
-setin- returns 1 if setelem is in a set, 0 otherwise
  set may be NULL or unsorted
*/
int qh_setin(setT *set, void *setelem) {
  void *elem, **elemp;

  FOREACHelem_(set) {
    if (elem == setelem)
      return 1;
  }
  return 0;
} /* setin */


/*----------------------------------------
-setindex- returns the index of elem in set.   If none, returns -1
  set may be NULL and may contain nulls.
*/
int qh_setindex(setT *set, void *atelem) {
  void **elem;
  int size, i;

  SETreturnsize_(set, size);
  if (size > (int)set->maxsize)
    return -1;
  elem= SETaddr_(set, void);
  for (i=0; i<size; i++) {
    if (*elem++ == atelem)
      return i;
  }
  return -1;
} /* setindex */


/*----------------------------------------
-setlarger- returns a larger set that contains elements of *setp
  the set is at least twice as large
  updates qhmem.tempstack if needed
*/
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 */


/*----------------------------------------
-setlast- return last element of set or NULL
   set may be NULL
*/
void *qh_setlast(setT *set) {
  int size;

  if (set) {
    size= *SETsizeaddr_(set);
    if (!size) 
      return SETelem_(set, set->maxsize - 1);
    else if (size > 1)
      return SETelem_(set, size - 2);
  }
  return NULL;
} /* setlast */


/*----------------------------------------
-setnew- creates and allocates space for a set
    setsize means the number of elements (NOT including the NULL terminator)
    use qh_settemp/qh_setfreetemp if set is temporary
*/
setT *qh_setnew(int setsize) {
  setT *set;
  int sizereceived, size;
  void **freelistp;

  if (!setsize)
    setsize++;
  size= sizeof(setT) + setsize * SETelemsize;
  if ((unsigned) size <= (unsigned) qhmem.LASTsize) {
    qh_memalloc_(size, freelistp, set);
    sizereceived= qhmem.sizetable[ qhmem.indextable[size]];
    if (sizereceived > size) 
      setsize += (sizereceived - size)/SETelemsize;
  }else
    set= (setT *)qh_memalloc ((int)size);
  set->maxsize= setsize;
  set->e[setsize]= (void *) 1;
  set->e[0]= NULL;
  return (set);
} /* setnew */


/*----------------------------------------
-setnew_delnthsorted- creates a sorted set not containing nth element
  the new set may have prepended undefined entries
  set must be defined
  checks nth
  see also: setdelnthsorted
*/
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) qhull_fatal(14);

  newsize= size-1 + prepend;
  newset= qh_setnew(newsize);
  newset->e[newset->maxsize]= (void *)(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, 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, tailsize * SETelemsize);
    newp += tailsize;