Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Analysis.AlgorithmBehavior/qhull-2012.1/src/libqhull/qh-set.htm @ 10621

Last change on this file since 10621 was 10207, checked in by ascheibe, 11 years ago

#1886 added a unit test for volume calculation and the qhull library
File size: 13.1 KB
Line 
1<!-- Do not edit with Front Page, it adds too many spaces -->
2<html>
3<head>
4<meta http-equiv="Content-Type"
5content="text/html; charset=iso-8859-1">
6<title>qset.c -- set data type and operations</title>
7</head>
8
9<body>
10<!-- Navigation links -->
11<p><a name="TOP"><b>Up:</b></a> <a
12href="http://www.qhull.org">Home page</a> for Qhull<br>
13<b>Up:</b> <a href="../../html/index.htm#TOC">Qhull manual</a>: Table of Contents <br>
14<b>Up:</b> <a href="../../html/qh-quick.htm#programs">Programs</a>
15&#149; <a href="../../html/qh-quick.htm#options">Options</a>
16&#149; <a href="../../html/qh-opto.htm#output">Output</a>
17&#149; <a href="../../html/qh-optf.htm#format">Formats</a>
18&#149; <a href="../../html/qh-optg.htm#geomview">Geomview</a>
19&#149; <a href="../../html/qh-optp.htm#print">Print</a>
20&#149; <a href="../../html/qh-optq.htm#qhull">Qhull</a>
21&#149; <a href="../../html/qh-optc.htm#prec">Precision</a>
22&#149; <a href="../../html/qh-optt.htm#trace">Trace</a><br>
23<b>Up:</b> <a href="../../html/qh-code.htm#TOC">Qhull code: Table of Contents</a><br>
24<b>To:</b> <a href="index.htm">Qhull functions</a>, macros, and data structures<br>
25<b>To:</b> <a href="qh-geom.htm">Geom</a> &#149; <a href="qh-globa.htm">Global</a>
26&#149; <a href="qh-io.htm">Io</a> &#149; <a href="qh-mem.htm">Mem</a>
27&#149; <a href="qh-merge.htm">Merge</a> &#149; <a href="qh-poly.htm">Poly</a>
28&#149; <a href="qh-qhull.htm">Qhull</a> &#149; <a href="qh-set.htm#TOC">Set</a>
29&#149; <a href="qh-stat.htm">Stat</a> &#149; <a href="qh-user.htm">User</a>
30</p>
31<hr>
32
33<h2>qset.c -- set data type and operations</h2>
34<blockquote>
35<p>Qhull's data structures are constructed from sets. The
36functions and macros in qset.c construct, iterate, and
37modify these sets. They are the most frequently called
38functions in Qhull. For this reason, efficiency is the
39primary concern. </p>
40<p>In Qhull, a <i>set</i> is represented by an unordered
41array of pointers with a maximum size and a NULL
42terminator (<a href="qset.h#setT">setT</a>).
43Most sets correspond to mathematical sets
44(i.e., the pointers are unique). Some sets are sorted to
45enforce uniqueness. Some sets are ordered. For example,
46the order of vertices in a ridge determine the ridge's
47orientation. If you reverse the order of adjacent
48vertices, the orientation reverses. Some sets are not
49mathematical sets. They may be indexed as an array and
50they may include NULL pointers. </p>
51<p>The most common operation on a set is to iterate its
52members. This is done with a 'FOREACH...' macro. Each set
53has a custom macro. For example, 'FOREACHvertex_'
54iterates over a set of vertices. Each vertex is assigned
55to the variable 'vertex' from the pointer 'vertexp'. </p>
56<p>Most sets are constructed by appending elements to the
57set. The last element of a set is either NULL or the
58index of the terminating NULL for a partially full set.
59If a set is full, appending an element copies the set to
60a larger array. </p>
61
62</blockquote>
63<p><b>Copyright &copy; 1995-2012 C.B. Barber</b></p>
64<hr>
65<p><a href="#TOP">&#187;</a> <a href="qh-geom.htm#TOC">Geom</a>
66<a name="TOC">&#149;</a> <a href="qh-globa.htm#TOC">Global</a> &#149;
67<a href="qh-io.htm#TOC">Io</a> &#149; <a href="qh-mem.htm#TOC">Mem</a> &#149;
68<a href="qh-merge.htm#TOC">Merge</a> &#149; <a href="qh-poly.htm#TOC">Poly</a>
69&#149; <a href="qh-qhull.htm#TOC">Qhull</a> &#149; <b>Set</b>
70&#149; <a href="qh-stat.htm#TOC">Stat</a> &#149; <a href="qh-user.htm#TOC">User</a>
71</p>
72<h3>Index to <a href="qset.c">qset.c</a> and
73<a href="qset.h">qset.h</a></h3>
74<ul>
75<li><a href="#stype">Data types and constants</a> </li>
76<li><a href="#seach">FOREACH macros</a> </li>
77<li><a href="#saccess">access and size macros</a> </li>
78<li><a href="#sint">internal macros</a> </li>
79<li><a href="#saddr">address macros</a><p>&nbsp;</li>
80
81<li><a href="#snew">Allocation and deallocation functions</a> </li>
82<li><a href="#spred">Access and predicate functions</a>
83</li>
84<li><a href="#sadd">Add functions</a> </li>
85<li><a href="#scheck">Check and print functions</a></li>
86<li><a href="#scopy">Copy, compact, and zero functions</a></li>
87<li><a href="#sdel">Delete functions</a> </li>
88<li><a href="#stemp">Temporary set functions</a> </li>
89</ul>
90<h3><a href="qh-set.htm#TOC">&#187;</a><a name="stype">Data types and
91constants</a></h3>
92<ul>
93<li><a href="qset.h#SETelemsize">SETelemsize</a> size
94of a set element in bytes </li>
95<li><a href="qset.h#setT">setT</a> a set with a
96maximum size and a current size</li>
97<li><a href="libqhull.h#qh-set">qh global sets</a>
98global sets for temporary sets, etc. </li>
99</ul>
100<h3><a href="qh-set.htm#TOC">&#187;</a><a name="seach">FOREACH macros</a></h3>
101<ul>
102<li><a href="qset.h#FOREACHelem_">FOREACHelem_</a>
103assign 'elem' to each element in a set </li>
104<li><a href="qset.h#FOREACHset_">FOREACHset_</a>
105assign 'set' to each set in a set of sets </li>
106<li><a href="qset.h#FOREACHsetelement_">FOREACHsetelement_</a>
107define a FOREACH iterator </li>
108<li><a href="qset.h#FOREACHsetelement_i_">FOREACHsetelement_i_</a>
109define an indexed FOREACH iterator </li>
110<li><a href="qset.h#FOREACHsetelementreverse_">FOREACHsetelementreverse_</a>
111define a reversed FOREACH iterator </li>
112<li><a href="qset.h#FOREACHsetelementreverse12_">FOREACHsetelementreverse12_</a>
113define a FOREACH iterator with e[1] and e[0]
114reversed </li>
115</ul>
116<h3><a href="qh-set.htm#TOC">&#187;</a><a name="saccess">Access and
117size macros</a></h3>
118<ul>
119<li><a href="qset.h#SETelem_">SETelem_</a> return the
120n'th element of set </li>
121<li><a href="qset.h#SETelemt_">SETelemt_</a> return
122the n'th element of set as a type</li>
123<li><a href="qset.h#SETempty_">SETempty_</a> return
124true (1) if set is empty </li>
125<li><a href="qset.h#SETfirst_">SETfirst_</a> return
126first element of set </li>
127<li><a href="qset.h#SETfirstt_">SETfirstt_</a> return
128first element of set as a type</li>
129<li><a href="qset.h#SETindex_">SETindex_</a> return
130index of elem in set </li>
131<li><a href="qset.h#SETreturnsize_">SETreturnsize_</a>
132return size of a set (normally use <a href="qset.c#setsize">qh_setsize</a>) </li>
133<li><a href="qset.h#SETsecond_">SETsecond_</a> return
134second element of set </li>
135<li><a href="qset.h#SETsecondt_">SETsecondt_</a>
136return second element of set as a type</li>
137<li><a href="qset.h#SETtruncate_">SETtruncate_</a>
138truncate set to size, i.e., qh_settruncate()</li>
139</ul>
140<h3><a href="qh-set.htm#TOC">&#187;</a><a name="sint">Internal macros</a></h3>
141<ul>
142<li><a href="qset.c#SETsizeaddr_">SETsizeaddr_</a>
143return pointer to end element of a set (indicates
144current size) </li>
145</ul>
146
147<h3><a href="qh-set.htm#TOC">&#187;</a><a name="saddr">address macros</a></h3>
148<ul>
149<li><a href="qset.h#SETaddr_">SETaddr_</a> return
150address of a set's elements </li>
151<li><a href="qset.h#SETelemaddr_">SETelemaddr_</a>
152return address of the n'th element of a set </li>
153<li><a href="qset.h#SETref_">SETref_</a> l.h.s. for
154modifying the current element in a FOREACH
155iteration </li>
156</ul>
157
158<h3><a href="qh-set.htm#TOC">&#187;</a><a name="snew">Allocation and
159deallocation functions</a></h3>
160<ul>
161<li><a href="qset.c#setfree">qh_setfree</a> free the
162space occupied by a set </li>
163<li><a href="qset.c#setfree2">qh_setfree2</a> free a
164set and its elements </li>
165<li><a href="qset.c#setfreelong">qh_setfreelong</a>
166free a set only if it is in long memory </li>
167<li><a href="qset.c#setnew">qh_setnew</a> create a new
168set </li>
169</ul>
170
171<h3><a href="qh-set.htm#TOC">&#187;</a><a name="spred">Access and
172predicate functions </a></h3>
173<ul>
174<li><a href="qset.c#setendpointer">qh_setendpointer</a> return
175pointer to NULL terminator of a set</li>
176<li><a href="qset.c#setequal">qh_setequal</a> return 1
177if two sorted sets are equal </li>
178<li><a href="qset.c#setequal_except">qh_setequal_except</a>
179return 1 if two sorted sets are equal except for
180an element </li>
181<li><a href="qset.c#setequal_skip">qh_setequal_skip</a>
182return 1 if two sorted sets are equal except for
183a pair of skipped elements </li>
184<li><a href="qset.c#setequal_skip">qh_setequal_skip</a>
185return 1 if two sorted sets are equal except for
186a pair of skipped elements </li>
187<li><a href="qset.c#setin">qh_setin</a> return 1 if an
188element is in a set </li>
189<li><a href="qset.c#setindex">qh_setindex</a> return
190the index of an element in a set </li>
191<li><a href="qset.c#setlast">qh_setlast</a> return
192last element of a set</li>
193<li><a href="qset.c#setsize">qh_setsize</a> returns
194the size of a set </li>
195</ul>
196
197<h3><a href="qh-set.htm#TOC">&#187;</a><a name="sadd">Add functions</a></h3>
198<ul>
199<li><a href="qset.c#setaddnth">qh_setaddnth</a> add a
200element as n'th element of sorted or unsorted set
201</li>
202<li><a href="qset.c#setaddsorted">qh_setaddsorted</a>
203add an element to a sorted set </li>
204<li><a href="qset.c#setappend">qh_setappend</a> append
205an element to a set </li>
206<li><a href="qset.c#setappend_set">qh_setappend_set</a>
207append a set of elements to a set </li>
208<li><a href="qset.c#setappend2ndlast">qh_setappend2ndlast</a>
209add an element as the next to the last element in
210a set </li>
211<li><a href="qset.c#setlarger">qh_setlarger</a> return
212a larger set with the same elements</li>
213<li><a href="qset.c#setreplace">qh_setreplace</a>
214replace one element with another in a set</li>
215<li><a href="qset.c#setunique">qh_setunique</a> add an
216element if it is not already in a set </li>
217</ul>
218
219<h3><a href="qh-set.htm#TOC">&#187;</a><a name="scheck">Check and print functions</a></h3>
220<ul>
221<li><a href="qset.c#setcheck">qh_setcheck</a> check a
222set for validity </li>
223<li><a href="qset.c#setprint">qh_setprint</a> print a
224set's elements to fp </li>
225</ul>
226
227<h3><a href="qh-set.htm#TOC">&#187;</a><a name="scopy">Copy, compact, and zero functions</a></h3>
228<ul>
229<li><a href="qset.c#setcompact">qh_setcompact</a>
230compact NULLs from an unsorted set </li>
231<li><a href="qset.c#setcopy">qh_setcopy</a> make a
232copy of a sorted or unsorted set </li>
233<li><a href="qset.c#setduplicate">qh_setduplicate</a>
234duplicate a set and its elements </li>
235<li><a href="qset.c#settruncate">qh_settruncate</a>
236truncate a set to size elements </li>
237<li><a href="qset.c#setzero">qh_setzero</a> zero the
238remainder of a set </li>
239</ul>
240
241<h3><a href="qh-set.htm#TOC">&#187;</a><a name="sdel">Delete functions</a></h3>
242<ul>
243<li><a href="qset.c#setdel">qh_setdel</a> delete an
244element from an unsorted set. </li>
245<li><a href="qset.c#setdellast">qh_setdellast</a>
246delete and return last element from a set</li>
247<li><a href="qset.c#setdelnth">qh_setdelnth</a> delete
248and return nth element from an unsorted set </li>
249<li><a href="qset.c#setdelnthsorted">qh_setdelnthsorted</a>
250delete and return nth element from a sorted set </li>
251<li><a href="qset.c#setdelsorted">qh_setdelsorted</a>
252delete an element from a sorted set </li>
253<li><a href="qset.c#setnew_delnthsorted">qh_setnew_delnthsorted</a>
254create a sorted set not containing the nth
255element </li>
256</ul>
257
258<h3><a href="qh-set.htm#TOC">&#187;</a><a name="stemp">Temporary set functions</a></h3>
259<ul>
260<li><a href="qset.c#settemp">qh_settemp</a> return a
261temporary set and append it qhmem.tempstack</li>
262<li><a href="qset.c#settempfree">qh_settempfree</a>
263free and pop a set from qhmem.tempstack</li>
264<li><a href="qset.c#settempfree_all">qh_settempfree_all</a>
265free all sets in qhmem.tempstack </li>
266<li><a href="qset.c#settemppop">qh_settemppop</a> pop
267a set from qhmem.tempstack (makes it permanent) </li>
268<li><a href="qset.c#settemppush">qh_settemppush</a>
269push a set unto qhmem.tempstack (makes it
270temporary) </li>
271</ul>
272
273<p><!-- Navigation links --> </p>
274<hr>
275<p><b>Up:</b>
276<a href="http://www.qhull.org">Home page for
277Qhull</a> <br>
278<b>Up:</b> <a href="../../html/index.htm#TOC">Qhull manual: Table of Contents</a> <br>
279<b>Up:</b> <a href="../../html/qh-quick.htm#programs">Programs</a>
280&#149; <a href="../../html/qh-quick.htm#options">Options</a>
281&#149; <a href="../../html/qh-opto.htm#output">Output</a>
282&#149; <a href="../../html/qh-optf.htm#format">Formats</a>
283&#149; <a href="../../html/qh-optg.htm#geomview">Geomview</a>
284&#149; <a href="../../html/qh-optp.htm#print">Print</a>
285&#149; <a href="../../html/qh-optq.htm#qhull">Qhull</a>
286&#149; <a href="../../html/qh-optc.htm#prec">Precision</a>
287&#149; <a href="../../html/qh-optt.htm#trace">Trace</a><br>
288<b>Up:</b> <a href="../../html/qh-code.htm#TOC">Qhull code: Table of Contents</a> <br>
289<b>To:</b> <a href="index.htm">Qhull functions</a>, macros, and data structures<br>
290<b>To:</b> <a href="qh-geom.htm">Geom</a> &#149;
291<a href="qh-globa.htm">Global</a> &#149; <a href="qh-io.htm">Io</a>
292&#149; <a href="qh-mem.htm">Mem</a> &#149; <a href="qh-merge.htm">Merge</a>
293&#149; <a href="qh-poly.htm">Poly</a> &#149; <a href="qh-qhull.htm#TOC">Qhull</a>
294&#149; <a href="qh-set.htm">Set</a> &#149; <a href="qh-stat.htm">Stat</a>
295&#149; <a href="qh-user.htm">User</a><br>
296</p>
297<p><!-- GC common information --> </p>
298<hr>
299<p><a href="http://www.geom.uiuc.edu/"><img
300src="../../html/qh--geom.gif" align="middle" width="40" height="40"></a><i>The
301Geometry Center Home Page </i></p>
302<p>Comments to: <a href=mailto:qhull@qhull.org>qhull@qhull.org</a>
303</a><br>
304Created: May 2, 1997 --- <!-- hhmts start --> Last modified: see top <!-- hhmts end --> </p>
305</body>
306</html>
Note: See TracBrowser for help on using the repository browser.