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.

Copyright © 1995-2015 C.B. Barber

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

### Index to qset.c and qset.h

- Data types and constants
- FOREACH macros
- access and size macros
- internal macros
- address macros

- Allocation and deallocation functions
- Access and predicate functions
- Add functions
- Check and print functions
- Copy, compact, and zero functions
- Delete functions
- Temporary set functions

### » 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)

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

The Geometry Center Home Page

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