📄 qset.c
字号:
/*<html><pre> -<a href="qh-c.htm#set"
>-------------------------------</a><a name="TOP">-</a>
qset.c
implements set manipulations needed for quickhull
see qh-c.htm and qset.h
copyright (c) 1993-1999 The Geometry Center
*/
#include <stdio.h>
#include <string.h>
/*** uncomment here and qhull_a.h
if string.h does not define memcpy()
#include <memory.h>
*/
#include "qset.h"
#include "mem.h"
#ifndef qhDEFqhull
typedef struct ridgeT ridgeT;
typedef struct facetT facetT;
void qh_errexit(int exitcode, facetT *, ridgeT *);
#endif
/*=============== internal macros ===========================*/
/*-<a href="qh-c.htm#set"
>-------------------------------<a name="SETsizeaddr_">-</a>
SETsizeaddr_(set)
return pointer to actual size+1 of set (set CANNOT be NULL!!)
notes:
*SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL
*/
#define SETsizeaddr_(set) (&((set)->e[(set)->maxsize].i))
/*============ functions in alphabetical order ===================*/
/*-<a href="qh-c.htm#set"
>--------------------------------<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 *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 */
/*-<a href="qh-c.htm#set"
>--------------------------------<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-c.htm#set"
>-------------------------------<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) {
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 */
/*-<a href="qh-c.htm#set"
>-------------------------------<a name="setappend_set">-</a>
qh_setappend_set( setp, setA)
appends setA to *setp
notes:
*setp and setA may be NULL
*setp can not be a temp set
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 *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 */
/*-<a href="qh-c.htm#set"
>-------------------------------<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) {
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 */
/*-<a href="qh-c.htm#set"
>-------------------------------<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, char *tname, 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, tname, 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",
tname, id, maxsize, size-1);
waserr= 1;
}
if (waserr) {
qh_setprint (qhmem.ferr, "ERRONEOUS", set);
qh_errexit (qhmem_ERRqhull, NULL, NULL);
}
} /* setcheck */
/*-<a href="qh-c.htm#set"
>-------------------------------<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, destp-firstp);
} /* setcompact */
/*-<a href="qh-c.htm#set"
>-------------------------------<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)= size+1; /* memcpy may overwrite */
memcpy((char *)&(newset->e[0].p), (char *)&(set->e[0].p), SETelemsize *(size+1));
return (newset);
} /* setcopy */
/*-<a href="qh-c.htm#set"
>-------------------------------<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) {
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 */
/*-<a href="qh-c.htm#set"
>-------------------------------<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;
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 */
/*-<a href="qh-c.htm#set"
>-------------------------------<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 **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 */
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -