qset.c -- set data type and operations

Up: Home page for Qhull
Up: Qhull manual: Table of Contents
Up: Programs • Options • Output • Formats • Geomview • Print • Qhull • Precision • Trace • Functions
Up: Qhull code: Table of Contents
To: Qhull functions, macros, and data structures
To: Geom • Global • Io • Mem • Merge • Poly • Qhull • Set • Stat • User

qset.c -- set data type and operations

Qhull's data structures are constructed from sets. The functions and macros in qset.c construct, iterate, and modify these sets. They are the most frequently called functions in Qhull. For this reason, efficiency is the primary concern.

In Qhull, a set is represented by an unordered array of pointers with a maximum size and a NULL terminator (setT). Most sets correspond to mathematical sets (i.e., the pointers are unique). Some sets are sorted to enforce uniqueness. Some sets are ordered. For example, the order of vertices in a ridge determine the ridge's orientation. If you reverse the order of adjacent vertices, the orientation reverses. Some sets are not mathematical sets. They may be indexed as an array and they may include NULL pointers.

The most common operation on a set is to iterate its members. This is done with a 'FOREACH...' macro. Each set has a custom macro. For example, 'FOREACHvertex_' iterates over a set of vertices. Each vertex is assigned to the variable 'vertex' from the pointer 'vertexp'.

Most sets are constructed by appending elements to the set. The last element of a set is either NULL or the index of the terminating NULL for a partially full set. If a set is full, appending an element copies the set to a larger array.

» Geom • Global • Io • Mem • Merge • Poly • Qhull • Set • Stat • User

»Data types and constants

SETelemsize size of a set element in bytes
setT a set with a maximum size and a current size
qh global sets global sets for temporary sets, etc.

»FOREACH macros

FOREACHelem_ assign 'elem' to each element in a set
FOREACHset_ assign 'set' to each set in a set of sets
FOREACHsetelement_ define a FOREACH iterator
FOREACHsetelement_i_ define an indexed FOREACH iterator
FOREACHsetelementreverse_ define a reversed FOREACH iterator
FOREACHsetelementreverse12_ define a FOREACH iterator with e[1] and e[0] reversed

»Access and size macros

SETelem_ return the n'th element of set
SETelemt_ return the n'th element of set as a type
SETempty_ return true (1) if set is empty
SETfirst_ return first element of set
SETfirstt_ return first element of set as a type
SETindex_ return index of elem in set
SETreturnsize_ return size of a set (normally use qh_setsize)
SETsecond_ return second element of set
SETsecondt_ return second element of set as a type
SETtruncate_ truncate set to size, i.e., qh_settruncate()

»Internal macros

SETsizeaddr_ return pointer to end element of a set (indicates current size)

»address macros

SETaddr_ return address of a set's elements
SETelemaddr_ return address of the n'th element of a set
SETref_ l.h.s. for modifying the current element in a FOREACH iteration

»Allocation and deallocation functions

qh_setfree free the space occupied by a set
qh_setfree2 free a set and its elements
qh_setfreelong free a set only if it is in long memory
qh_setnew create a new set

»Access and predicate functions

qh_setendpointer return pointer to NULL terminator of a set
qh_setequal return 1 if two sorted sets are equal
qh_setequal_except return 1 if two sorted sets are equal except for an element
qh_setequal_skip return 1 if two sorted sets are equal except for a pair of skipped elements
qh_setequal_skip return 1 if two sorted sets are equal except for a pair of skipped elements
qh_setin return 1 if an element is in a set
qh_setindex return the index of an element in a set
qh_setlast return last element of a set
qh_setsize returns the size of a set

»Add functions

qh_setaddnth add a element as n'th element of sorted or unsorted set
qh_setaddsorted add an element to a sorted set
qh_setappend append an element to a set
qh_setappend_set append a set of elements to a set
qh_setappend2ndlast add an element as the next to the last element in a set
qh_setlarger return a larger set with the same elements
qh_setreplace replace one element with another in a set
qh_setunique add an element if it is not already in a set

»Check and print functions

qh_setcheck check a set for validity
qh_setprint print a set's elements to fp

»Copy, compact, and zero functions

qh_setcompact compact NULLs from an unsorted set
qh_setcopy make a copy of a sorted or unsorted set
qh_setduplicate duplicate a set and its elements
qh_settruncate truncate a set to size elements
qh_setzero zero the remainder of a set

»Delete functions

qh_setdel delete an element from an unsorted set.
qh_setdellast delete and return last element from a set
qh_setdelnth delete and return nth element from an unsorted set
qh_setdelnthsorted delete and return nth element from a sorted set
qh_setdelsorted delete an element from a sorted set
qh_setnew_delnthsorted create a sorted set not containing the nth element

»Temporary set functions

qh_settemp return a temporary set and append it qhmem.tempstack
qh_settempfree free and pop a set from qhmem.tempstack
qh_settempfree_all free all sets in qhmem.tempstack
qh_settemppop pop a set from qhmem.tempstack (makes it permanent)
qh_settemppush push a set unto qhmem.tempstack (makes it temporary)

The Geometry Center Home Page

Comments to: qhull@qhull.org
Created: May 2, 1997 --- Last modified: see top