Reverted incorrect merge (missing files)
[blender.git] / extern / qhull / src / qset.c
1 /*<html><pre>  -<a                             href="qh-set.htm"
2   >-------------------------------</a><a name="TOP">-</a>
3
4    qset.c 
5    implements set manipulations needed for quickhull 
6
7    see qh-set.htm and qset.h
8
9    copyright (c) 1993-2002 The Geometry Center        
10 */
11
12 #include <stdio.h>
13 #include <string.h>
14 /*** uncomment here and qhull_a.h 
15      if string.h does not define memcpy()
16 #include <memory.h>
17 */
18 #include "qset.h"
19 #include "mem.h"
20
21 #ifndef qhDEFqhull
22 typedef struct ridgeT ridgeT;
23 typedef struct facetT facetT;
24 void    qh_errexit(int exitcode, facetT *, ridgeT *);
25 #endif
26
27 /*=============== internal macros ===========================*/
28
29 /*-<a                             href="qh-set.htm#TOC"
30   >-------------------------------<a name="SETsizeaddr_">-</a>
31    
32   SETsizeaddr_(set) 
33     return pointer to actual size+1 of set (set CANNOT be NULL!!)
34       
35   notes:
36     *SETsizeaddr==NULL or e[*SETsizeaddr-1].p==NULL
37 */
38 #define SETsizeaddr_(set) (&((set)->e[(set)->maxsize].i))
39
40 /*============ functions in alphabetical order ===================*/
41   
42 /*-<a                             href="qh-set.htm#TOC"
43   >--------------------------------<a name="setaddnth">-</a>
44    
45   qh_setaddnth( setp, nth, newelem)
46     adds newelem as n'th element of sorted or unsorted *setp
47       
48   notes:
49     *setp and newelem must be defined
50     *setp may be a temp set
51     nth=0 is first element
52     errors if nth is out of bounds
53    
54   design:
55     expand *setp if empty or full
56     move tail of *setp up one
57     insert newelem
58 */
59 void qh_setaddnth(setT **setp, int nth, void *newelem) {
60   int *sizep, oldsize, i;
61   void **oldp, **newp;
62
63   if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
64     qh_setlarger(setp);
65     sizep= SETsizeaddr_(*setp);
66   }
67   oldsize= *sizep - 1;
68   if (nth < 0 || nth > oldsize) {
69     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
70     qh_setprint (qhmem.ferr, "", *setp);
71     qh_errexit (qhmem_ERRqhull, NULL, NULL);
72   }
73   (*sizep)++;
74   oldp= SETelemaddr_(*setp, oldsize, void);   /* NULL */
75   newp= oldp+1;
76   for (i= oldsize-nth+1; i--; )  /* move at least NULL  */
77     *(newp--)= *(oldp--);       /* may overwrite *sizep */
78   *newp= newelem;
79 } /* setaddnth */
80
81
82 /*-<a                              href="qh-set.htm#TOC"
83   >--------------------------------<a name="setaddsorted">-</a>
84    
85   setaddsorted( setp, newelem )
86     adds an newelem into sorted *setp
87       
88   notes:
89     *setp and newelem must be defined
90     *setp may be a temp set
91     nop if newelem already in set
92   
93   design:
94     find newelem's position in *setp
95     insert newelem
96 */
97 void qh_setaddsorted(setT **setp, void *newelem) {
98   int newindex=0;
99   void *elem, **elemp;
100
101   FOREACHelem_(*setp) {          /* could use binary search instead */
102     if (elem < newelem)
103       newindex++;
104     else if (elem == newelem)
105       return;
106     else
107       break;
108   }
109   qh_setaddnth(setp, newindex, newelem);
110 } /* setaddsorted */
111
112
113 /*-<a                             href="qh-set.htm#TOC"
114   >-------------------------------<a name="setappend">-</a>
115   
116   qh_setappend( setp, newelem)
117     append newelem to *setp
118
119   notes:
120     *setp may be a temp set
121     *setp and newelem may be NULL
122
123   design:
124     expand *setp if empty or full
125     append newelem to *setp
126     
127 */
128 void qh_setappend(setT **setp, void *newelem) {
129   int *sizep;
130   void **endp;
131
132   if (!newelem)
133     return;
134   if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
135     qh_setlarger(setp);
136     sizep= SETsizeaddr_(*setp);
137   }
138   *(endp= &((*setp)->e[(*sizep)++ - 1].p))= newelem;
139   *(++endp)= NULL;
140 } /* setappend */
141
142 /*-<a                             href="qh-set.htm#TOC"
143   >-------------------------------<a name="setappend_set">-</a>
144   
145   qh_setappend_set( setp, setA) 
146     appends setA to *setp
147
148   notes:
149     *setp can not be a temp set
150     *setp and setA may be NULL
151
152   design:
153     setup for copy
154     expand *setp if it is too small
155     append all elements of setA to *setp 
156 */
157 void qh_setappend_set(setT **setp, setT *setA) {
158   int *sizep, sizeA, size;
159   setT *oldset;
160
161   if (!setA)
162     return;
163   SETreturnsize_(setA, sizeA);
164   if (!*setp)
165     *setp= qh_setnew (sizeA);
166   sizep= SETsizeaddr_(*setp);
167   if (!(size= *sizep))
168     size= (*setp)->maxsize;
169   else
170     size--;
171   if (size + sizeA > (*setp)->maxsize) {
172     oldset= *setp;
173     *setp= qh_setcopy (oldset, sizeA);
174     qh_setfree (&oldset);
175     sizep= SETsizeaddr_(*setp);
176   }
177   *sizep= size+sizeA+1;   /* memcpy may overwrite */
178   if (sizeA > 0) 
179     memcpy((char *)&((*setp)->e[size].p), (char *)&(setA->e[0].p), SETelemsize *(sizeA+1));
180 } /* setappend_set */
181
182
183 /*-<a                             href="qh-set.htm#TOC"
184   >-------------------------------<a name="setappend2ndlast">-</a>
185   
186   qh_setappend2ndlast( setp, newelem )
187     makes newelem the next to the last element in *setp
188
189   notes:
190     *setp must have at least one element
191     newelem must be defined
192     *setp may be a temp set
193
194   design:
195     expand *setp if empty or full
196     move last element of *setp up one
197     insert newelem
198 */
199 void qh_setappend2ndlast(setT **setp, void *newelem) {
200   int *sizep;
201   void **endp, **lastp;
202   
203   if (!*setp || !*(sizep= SETsizeaddr_(*setp))) {
204     qh_setlarger(setp);
205     sizep= SETsizeaddr_(*setp);
206   }
207   endp= SETelemaddr_(*setp, (*sizep)++ -1, void); /* NULL */
208   lastp= endp-1;
209   *(endp++)= *lastp;
210   *endp= NULL;    /* may overwrite *sizep */
211   *lastp= newelem;
212 } /* setappend2ndlast */
213
214
215 /*-<a                             href="qh-set.htm#TOC"
216   >-------------------------------<a name="setcheck">-</a>
217   
218   qh_setcheck( set, typename, id ) 
219     check set for validity
220     report errors with typename and id
221
222   design:
223     checks that maxsize, actual size, and NULL terminator agree
224 */
225 void qh_setcheck(setT *set, char *tname, int id) {
226   int maxsize, size;
227   int waserr= 0;
228
229   if (!set)
230     return;
231   SETreturnsize_(set, size);
232   maxsize= set->maxsize;
233   if (size > maxsize || !maxsize) {
234     fprintf (qhmem.ferr, "qhull internal error (qh_setcheck): actual size %d of %s%d is greater than max size %d\n",
235              size, tname, id, maxsize);
236     waserr= 1;
237   }else if (set->e[size].p) {
238     fprintf (qhmem.ferr, "qhull internal error (qh_setcheck): %s%d (size %d max %d) is not null terminated.\n",
239              tname, id, maxsize, size-1);
240     waserr= 1;
241   }
242   if (waserr) {
243     qh_setprint (qhmem.ferr, "ERRONEOUS", set);
244     qh_errexit (qhmem_ERRqhull, NULL, NULL);
245   }
246 } /* setcheck */
247
248
249 /*-<a                             href="qh-set.htm#TOC"
250   >-------------------------------<a name="setcompact">-</a>
251   
252   qh_setcompact( set )
253     remove internal NULLs from an unsorted set
254
255   returns:
256     updated set
257
258   notes:
259     set may be NULL
260     it would be faster to swap tail of set into holes, like qh_setdel
261
262   design:
263     setup pointers into set
264     skip NULLs while copying elements to start of set 
265     update the actual size
266 */
267 void qh_setcompact(setT *set) {
268   int size;
269   void **destp, **elemp, **endp, **firstp;
270
271   if (!set)
272     return;
273   SETreturnsize_(set, size);
274   destp= elemp= firstp= SETaddr_(set, void);
275   endp= destp + size;
276   while (1) {
277     if (!(*destp++ = *elemp++)) {
278       destp--;
279       if (elemp > endp)
280         break;
281     }
282   }
283   qh_settruncate (set, destp-firstp);
284 } /* setcompact */
285
286
287 /*-<a                             href="qh-set.htm#TOC"
288   >-------------------------------<a name="setcopy">-</a>
289   
290   qh_setcopy( set, extra )
291     make a copy of a sorted or unsorted set with extra slots
292
293   returns:
294     new set
295
296   design:
297     create a newset with extra slots
298     copy the elements to the newset
299     
300 */
301 setT *qh_setcopy(setT *set, int extra) {
302   setT *newset;
303   int size;
304
305   if (extra < 0)
306     extra= 0;
307   SETreturnsize_(set, size);
308   newset= qh_setnew(size+extra);
309   *SETsizeaddr_(newset)= size+1;    /* memcpy may overwrite */
310   memcpy((char *)&(newset->e[0].p), (char *)&(set->e[0].p), SETelemsize *(size+1));
311   return (newset);
312 } /* setcopy */
313
314
315 /*-<a                             href="qh-set.htm#TOC"
316   >-------------------------------<a name="setdel">-</a>
317   
318   qh_setdel( set, oldelem )
319     delete oldelem from an unsorted set
320
321   returns:
322     returns oldelem if found
323     returns NULL otherwise
324     
325   notes:
326     set may be NULL
327     oldelem must not be NULL;
328     only deletes one copy of oldelem in set
329      
330   design:
331     locate oldelem
332     update actual size if it was full
333     move the last element to the oldelem's location
334 */
335 void *qh_setdel(setT *set, void *oldelem) {
336   void **elemp, **lastp;
337   int *sizep;
338
339   if (!set)
340     return NULL;
341   elemp= SETaddr_(set, void);
342   while (*elemp != oldelem && *elemp)
343     elemp++;
344   if (*elemp) {
345     sizep= SETsizeaddr_(set);
346     if (!(*sizep)--)         /*  if was a full set */
347       *sizep= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */
348     lastp= SETelemaddr_(set, *sizep-1, void);
349     *elemp= *lastp;      /* may overwrite itself */
350     *lastp= NULL;
351     return oldelem;
352   }
353   return NULL;
354 } /* setdel */
355
356
357 /*-<a                             href="qh-set.htm#TOC"
358   >-------------------------------<a name="setdellast">-</a>
359   
360   qh_setdellast( set) 
361     return last element of set or NULL
362
363   notes:
364     deletes element from set
365     set may be NULL
366
367   design:
368     return NULL if empty
369     if full set
370       delete last element and set actual size
371     else
372       delete last element and update actual size 
373 */
374 void *qh_setdellast(setT *set) {
375   int setsize;  /* actually, actual_size + 1 */
376   int maxsize;
377   int *sizep;
378   void *returnvalue;
379   
380   if (!set || !(set->e[0].p))
381     return NULL;
382   sizep= SETsizeaddr_(set);
383   if ((setsize= *sizep)) {
384     returnvalue= set->e[setsize - 2].p;
385     set->e[setsize - 2].p= NULL;
386     (*sizep)--;
387   }else {
388     maxsize= set->maxsize;
389     returnvalue= set->e[maxsize - 1].p;
390     set->e[maxsize - 1].p= NULL;
391     *sizep= maxsize;
392   }
393   return returnvalue;
394 } /* setdellast */
395
396
397 /*-<a                             href="qh-set.htm#TOC"
398   >-------------------------------<a name="setdelnth">-</a>
399   
400   qh_setdelnth( set, nth )
401     deletes nth element from unsorted set 
402     0 is first element
403
404   returns:
405     returns the element (needs type conversion)
406
407   notes:
408     errors if nth invalid
409
410   design:
411     setup points and check nth
412     delete nth element and overwrite with last element
413 */
414 void *qh_setdelnth(setT *set, int nth) {
415   void **elemp, **lastp, *elem;
416   int *sizep;
417
418
419   elemp= SETelemaddr_(set, nth, void);
420   sizep= SETsizeaddr_(set);
421   if (!(*sizep)--)         /*  if was a full set */
422     *sizep= set->maxsize;  /*     *sizep= (maxsize-1)+ 1 */
423   if (nth < 0 || nth >= *sizep) {
424     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
425     qh_setprint (qhmem.ferr, "", set);
426     qh_errexit (qhmem_ERRqhull, NULL, NULL);
427   }
428   lastp= SETelemaddr_(set, *sizep-1, void);
429   elem= *elemp;
430   *elemp= *lastp;      /* may overwrite itself */
431   *lastp= NULL;
432   return elem;
433 } /* setdelnth */
434
435 /*-<a                             href="qh-set.htm#TOC"
436   >-------------------------------<a name="setdelnthsorted">-</a>
437   
438   qh_setdelnthsorted( set, nth )
439     deletes nth element from sorted set
440
441   returns:
442     returns the element (use type conversion)
443   
444   notes:
445     errors if nth invalid
446     
447   see also: 
448     setnew_delnthsorted
449
450   design:
451     setup points and check nth
452     copy remaining elements down one
453     update actual size  
454 */
455 void *qh_setdelnthsorted(setT *set, int nth) {
456   void **newp, **oldp, *elem;
457   int *sizep;
458
459   sizep= SETsizeaddr_(set);
460   if (nth < 0 || (*sizep && nth >= *sizep-1) || nth >= set->maxsize) {
461     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
462     qh_setprint (qhmem.ferr, "", set);
463     qh_errexit (qhmem_ERRqhull, NULL, NULL);
464   }
465   newp= SETelemaddr_(set, nth, void);
466   elem= *newp;
467   oldp= newp+1;
468   while ((*(newp++)= *(oldp++)))
469     ; /* copy remaining elements and NULL */
470   if (!(*sizep)--)         /*  if was a full set */
471     *sizep= set->maxsize;  /*     *sizep= (max size-1)+ 1 */
472   return elem;
473 } /* setdelnthsorted */
474
475
476 /*-<a                             href="qh-set.htm#TOC"
477   >-------------------------------<a name="setdelsorted">-</a>
478   
479   qh_setdelsorted( set, oldelem )
480     deletes oldelem from sorted set
481
482   returns:
483     returns oldelem if it was deleted
484   
485   notes:
486     set may be NULL
487
488   design:
489     locate oldelem in set
490     copy remaining elements down one
491     update actual size  
492 */
493 void *qh_setdelsorted(setT *set, void *oldelem) {
494   void **newp, **oldp;
495   int *sizep;
496
497   if (!set)
498     return NULL;
499   newp= SETaddr_(set, void);
500   while(*newp != oldelem && *newp)
501     newp++;
502   if (*newp) {
503     oldp= newp+1;
504     while ((*(newp++)= *(oldp++)))
505       ; /* copy remaining elements */
506     sizep= SETsizeaddr_(set);
507     if (!(*sizep)--)    /*  if was a full set */
508       *sizep= set->maxsize;  /*     *sizep= (max size-1)+ 1 */
509     return oldelem;
510   }
511   return NULL;
512 } /* setdelsorted */
513
514
515 /*-<a                             href="qh-set.htm#TOC"
516   >-------------------------------<a name="setduplicate">-</a>
517   
518   qh_setduplicate( set, elemsize )
519     duplicate a set of elemsize elements
520
521   notes:
522     use setcopy if retaining old elements
523
524   design:
525     create a new set
526     for each elem of the old set
527       create a newelem
528       append newelem to newset
529 */
530 setT *qh_setduplicate (setT *set, int elemsize) {
531   void          *elem, **elemp, *newElem;
532   setT          *newSet;
533   int           size;
534   
535   if (!(size= qh_setsize (set)))
536     return NULL;
537   newSet= qh_setnew (size);
538   FOREACHelem_(set) {
539     newElem= qh_memalloc (elemsize);
540     memcpy (newElem, elem, elemsize);
541     qh_setappend (&newSet, newElem);
542   }
543   return newSet;
544 } /* setduplicate */
545
546
547 /*-<a                             href="qh-set.htm#TOC"
548   >-------------------------------<a name="setequal">-</a>
549   
550   qh_setequal(  )
551     returns 1 if two sorted sets are equal, otherwise returns 0
552
553   notes:
554     either set may be NULL
555
556   design:
557     check size of each set
558     setup pointers
559     compare elements of each set
560 */
561 int qh_setequal(setT *setA, setT *setB) {
562   void **elemAp, **elemBp;
563   int sizeA, sizeB;
564   
565   SETreturnsize_(setA, sizeA);
566   SETreturnsize_(setB, sizeB);
567   if (sizeA != sizeB)
568     return 0;
569   if (!sizeA)
570     return 1;
571   elemAp= SETaddr_(setA, void);
572   elemBp= SETaddr_(setB, void);
573   if (!memcmp((char *)elemAp, (char *)elemBp, sizeA*SETelemsize))
574     return 1;
575   return 0;
576 } /* setequal */
577
578
579 /*-<a                             href="qh-set.htm#TOC"
580   >-------------------------------<a name="setequal_except">-</a>
581   
582   qh_setequal_except( setA, skipelemA, setB, skipelemB )
583     returns 1 if sorted setA and setB are equal except for skipelemA & B
584
585   returns:
586     false if either skipelemA or skipelemB are missing
587   
588   notes:
589     neither set may be NULL
590
591     if skipelemB is NULL, 
592       can skip any one element of setB
593
594   design:
595     setup pointers
596     search for skipelemA, skipelemB, and mismatches
597     check results
598 */
599 int qh_setequal_except (setT *setA, void *skipelemA, setT *setB, void *skipelemB) {
600   void **elemA, **elemB;
601   int skip=0;
602
603   elemA= SETaddr_(setA, void);
604   elemB= SETaddr_(setB, void);
605   while (1) {
606     if (*elemA == skipelemA) {
607       skip++;
608       elemA++;
609     }
610     if (skipelemB) {
611       if (*elemB == skipelemB) {
612         skip++;
613         elemB++;
614       }
615     }else if (*elemA != *elemB) {
616       skip++;
617       if (!(skipelemB= *elemB++))
618         return 0;
619     }
620     if (!*elemA)
621       break;
622     if (*elemA++ != *elemB++) 
623       return 0;
624   }
625   if (skip != 2 || *elemB)
626     return 0;
627   return 1;
628 } /* setequal_except */
629   
630
631 /*-<a                             href="qh-set.htm#TOC"
632   >-------------------------------<a name="setequal_skip">-</a>
633   
634   qh_setequal_skip( setA, skipA, setB, skipB )
635     returns 1 if sorted setA and setB are equal except for elements skipA & B
636
637   returns:
638     false if different size
639
640   notes:
641     neither set may be NULL
642
643   design:
644     setup pointers
645     search for mismatches while skipping skipA and skipB
646 */
647 int qh_setequal_skip (setT *setA, int skipA, setT *setB, int skipB) {
648   void **elemA, **elemB, **skipAp, **skipBp;
649
650   elemA= SETaddr_(setA, void);
651   elemB= SETaddr_(setB, void);
652   skipAp= SETelemaddr_(setA, skipA, void);
653   skipBp= SETelemaddr_(setB, skipB, void);
654   while (1) {
655     if (elemA == skipAp)
656       elemA++;
657     if (elemB == skipBp)
658       elemB++;
659     if (!*elemA)
660       break;
661     if (*elemA++ != *elemB++) 
662       return 0;
663   }
664   if (*elemB)
665     return 0;
666   return 1;
667 } /* setequal_skip */
668   
669
670 /*-<a                             href="qh-set.htm#TOC"
671   >-------------------------------<a name="setfree">-</a>
672   
673   qh_setfree( setp )
674     frees the space occupied by a sorted or unsorted set
675
676   returns:
677     sets setp to NULL
678     
679   notes:
680     set may be NULL
681
682   design:
683     free array
684     free set
685 */
686 void qh_setfree(setT **setp) {
687   int size;
688   void **freelistp;  /* used !qh_NOmem */
689   
690   if (*setp) {
691     size= sizeof(setT) + ((*setp)->maxsize)*SETelemsize; 
692     if (size <= qhmem.LASTsize) {
693       qh_memfree_(*setp, size, freelistp);
694     }else
695       qh_memfree (*setp, size);
696     *setp= NULL;
697   }
698 } /* setfree */
699
700
701 /*-<a                             href="qh-set.htm#TOC"
702   >-------------------------------<a name="setfree2">-</a>
703   
704   qh_setfree2( setp, elemsize )
705     frees the space occupied by a set and its elements
706
707   notes:
708     set may be NULL
709
710   design:
711     free each element
712     free set 
713 */
714 void qh_setfree2 (setT **setp, int elemsize) {
715   void          *elem, **elemp;
716   
717   FOREACHelem_(*setp)
718     qh_memfree (elem, elemsize);
719   qh_setfree (setp);
720 } /* setfree2 */
721
722
723       
724 /*-<a                             href="qh-set.htm#TOC"
725   >-------------------------------<a name="setfreelong">-</a>
726   
727   qh_setfreelong( setp )
728     frees a set only if it's in long memory
729
730   returns:
731     sets setp to NULL if it is freed
732     
733   notes:
734     set may be NULL
735
736   design:
737     if set is large
738       free it    
739 */
740 void qh_setfreelong(setT **setp) {
741   int size;
742   
743   if (*setp) {
744     size= sizeof(setT) + ((*setp)->maxsize)*SETelemsize; 
745     if (size > qhmem.LASTsize) {
746       qh_memfree (*setp, size);
747       *setp= NULL;
748     }
749   }
750 } /* setfreelong */
751
752
753 /*-<a                             href="qh-set.htm#TOC"
754   >-------------------------------<a name="setin">-</a>
755   
756   qh_setin( set, setelem )
757     returns 1 if setelem is in a set, 0 otherwise
758
759   notes:
760     set may be NULL or unsorted
761
762   design:
763     scans set for setelem
764 */
765 int qh_setin(setT *set, void *setelem) {
766   void *elem, **elemp;
767
768   FOREACHelem_(set) {
769     if (elem == setelem)
770       return 1;
771   }
772   return 0;
773 } /* setin */
774
775
776 /*-<a                             href="qh-set.htm#TOC"
777   >-------------------------------<a name="setindex">-</a>
778   
779   qh_setindex( set, atelem )
780     returns the index of atelem in set.   
781     returns -1, if not in set or maxsize wrong
782
783   notes:
784     set may be NULL and may contain nulls.
785
786   design:
787     checks maxsize
788     scans set for atelem
789 */
790 int qh_setindex(setT *set, void *atelem) {
791   void **elem;
792   int size, i;
793
794   SETreturnsize_(set, size);
795   if (size > set->maxsize)
796     return -1;
797   elem= SETaddr_(set, void);
798   for (i=0; i < size; i++) {
799     if (*elem++ == atelem)
800       return i;
801   }
802   return -1;
803 } /* setindex */
804
805
806 /*-<a                             href="qh-set.htm#TOC"
807   >-------------------------------<a name="setlarger">-</a>
808   
809   qh_setlarger( oldsetp )
810     returns a larger set that contains all elements of *oldsetp
811
812   notes:
813     the set is at least twice as large
814     if temp set, updates qhmem.tempstack
815
816   design:
817     creates a new set
818     copies the old set to the new set
819     updates pointers in tempstack
820     deletes the old set
821 */
822 void qh_setlarger(setT **oldsetp) {
823   int size= 1, *sizep;
824   setT *newset, *set, **setp, *oldset;
825   void **oldp, **newp;
826
827   if (*oldsetp) {
828     oldset= *oldsetp;
829     SETreturnsize_(oldset, size);
830     qhmem.cntlarger++;
831     qhmem.totlarger += size+1;
832     newset= qh_setnew(2 * size);
833     oldp= SETaddr_(oldset, void);
834     newp= SETaddr_(newset, void);
835     memcpy((char *)newp, (char *)oldp, (size+1) * SETelemsize);
836     sizep= SETsizeaddr_(newset);
837     *sizep= size+1;
838     FOREACHset_((setT *)qhmem.tempstack) {
839       if (set == oldset)
840         *(setp-1)= newset;
841     }
842     qh_setfree(oldsetp);
843   }else 
844     newset= qh_setnew(3);
845   *oldsetp= newset;
846 } /* setlarger */
847
848
849 /*-<a                             href="qh-set.htm#TOC"
850   >-------------------------------<a name="setlast">-</a>
851   
852   qh_setlast(  )
853     return last element of set or NULL (use type conversion)
854
855   notes:
856     set may be NULL
857
858   design:
859     return last element  
860 */
861 void *qh_setlast(setT *set) {
862   int size;
863
864   if (set) {
865     size= *SETsizeaddr_(set);
866     if (!size) 
867       return SETelem_(set, set->maxsize - 1);
868     else if (size > 1)
869       return SETelem_(set, size - 2);
870   }
871   return NULL;
872 } /* setlast */
873
874
875 /*-<a                             href="qh-set.htm#TOC"
876   >-------------------------------<a name="setnew">-</a>
877   
878   qh_setnew( setsize )
879     creates and allocates space for a set
880
881   notes:
882     setsize means the number of elements (NOT including the NULL terminator)
883     use qh_settemp/qh_setfreetemp if set is temporary
884
885   design:
886     allocate memory for set
887     roundup memory if small set
888     initialize as empty set
889 */
890 setT *qh_setnew(int setsize) {
891   setT *set;
892   int sizereceived; /* used !qh_NOmem */
893   int size;
894   void **freelistp; /* used !qh_NOmem */
895
896   if (!setsize)
897     setsize++;
898   size= sizeof(setT) + setsize * SETelemsize;
899   if ((unsigned) size <= (unsigned) qhmem.LASTsize) {
900     qh_memalloc_(size, freelistp, set, setT);
901 #ifndef qh_NOmem
902     sizereceived= qhmem.sizetable[ qhmem.indextable[size]];
903     if (sizereceived > size) 
904       setsize += (sizereceived - size)/SETelemsize;
905 #endif
906   }else
907     set= (setT*)qh_memalloc (size);
908   set->maxsize= setsize;
909   set->e[setsize].i= 1;
910   set->e[0].p= NULL;
911   return (set);
912 } /* setnew */
913
914
915 /*-<a                             href="qh-set.htm#TOC"
916   >-------------------------------<a name="setnew_delnthsorted">-</a>
917   
918   qh_setnew_delnthsorted( set, size, nth, prepend )
919     creates a sorted set not containing nth element
920     if prepend, the first prepend elements are undefined
921
922   notes:
923     set must be defined
924     checks nth
925     see also: setdelnthsorted
926
927   design:
928     create new set
929     setup pointers and allocate room for prepend'ed entries
930     append head of old set to new set
931     append tail of old set to new set
932 */
933 setT *qh_setnew_delnthsorted(setT *set, int size, int nth, int prepend) {
934   setT *newset;
935   void **oldp, **newp;
936   int tailsize= size - nth -1, newsize;
937
938   if (tailsize < 0) {
939     fprintf (qhmem.ferr, "qhull internal error (qh_setaddnth): nth %d is out-of-bounds for set:\n", nth);
940     qh_setprint (qhmem.ferr, "", set);
941     qh_errexit (qhmem_ERRqhull, NULL, NULL);
942   }
943   newsize= size-1 + prepend;
944   newset= qh_setnew(newsize);
945   newset->e[newset->maxsize].i= newsize+1;  /* may be overwritten */
946   oldp= SETaddr_(set, void);
947   newp= SETaddr_(newset, void) + prepend;
948   switch (nth) {
949   case 0:
950     break;
951   case 1:
952     *(newp++)= *oldp++;
953     break;
954   case 2:
955     *(newp++)= *oldp++;
956     *(newp++)= *oldp++;
957     break;
958   case 3:
959     *(newp++)= *oldp++;
960     *(newp++)= *oldp++;
961     *(newp++)= *oldp++;
962     break;
963   case 4:
964     *(newp++)= *oldp++;
965     *(newp++)= *oldp++;
966     *(newp++)= *oldp++;
967     *(newp++)= *oldp++;
968     break;
969   default:
970     memcpy((char *)newp, (char *)oldp, nth * SETelemsize);
971     newp += nth;
972     oldp += nth;
973     break;
974   }
975   oldp++;
976   switch (tailsize) {
977   case 0:
978     break;
979   case 1:
980     *(newp++)= *oldp++;
981     break;
982   case 2:
983     *(newp++)= *oldp++;
984     *(newp++)= *oldp++;
985     break;
986   case 3:
987     *(newp++)= *oldp++;
988     *(newp++)= *oldp++;
989     *(newp++)= *oldp++;
990     break;
991   case 4:
992     *(newp++)= *oldp++;
993     *(newp++)= *oldp++;
994     *(newp++)= *oldp++;
995     *(newp++)= *oldp++;
996     break;
997   default:
998     memcpy((char *)newp, (char *)oldp, tailsize * SETelemsize);
999     newp += tailsize;
1000   }
1001   *newp= NULL;
1002   return(newset);
1003 } /* setnew_delnthsorted */
1004
1005
1006 /*-<a                             href="qh-set.htm#TOC"
1007   >-------------------------------<a name="setprint">-</a>
1008   
1009   qh_setprint( fp, string, set )
1010     print set elements to fp with identifying string
1011
1012   notes:
1013     never errors
1014 */
1015 void qh_setprint(FILE *fp, char* string, setT *set) {
1016   int size, k;
1017
1018   if (!set)
1019     fprintf (fp, "%s set is null\n", string);
1020   else {
1021     SETreturnsize_(set, size);
1022     fprintf (fp, "%s set=%p maxsize=%d size=%d elems=",
1023              string, set, set->maxsize, size);
1024     if (size > set->maxsize)
1025       size= set->maxsize+1;
1026     for (k=0; k < size; k++)
1027       fprintf(fp, " %p", set->e[k].p);
1028     fprintf(fp, "\n");
1029   }
1030 } /* setprint */
1031
1032 /*-<a                             href="qh-set.htm#TOC"
1033   >-------------------------------<a name="setreplace">-</a>
1034   
1035   qh_setreplace( set, oldelem, newelem )
1036     replaces oldelem in set with newelem
1037
1038   notes:
1039     errors if oldelem not in the set
1040     newelem may be NULL, but it turns the set into an indexed set (no FOREACH)
1041
1042   design:
1043     find oldelem
1044     replace with newelem
1045 */
1046 void qh_setreplace(setT *set, void *oldelem, void *newelem) {
1047   void **elemp;
1048   
1049   elemp= SETaddr_(set, void);
1050   while(*elemp != oldelem && *elemp)
1051     elemp++;
1052   if (*elemp)
1053     *elemp= newelem;
1054   else {
1055     fprintf (qhmem.ferr, "qhull internal error (qh_setreplace): elem %p not found in set\n",
1056        oldelem);
1057     qh_setprint (qhmem.ferr, "", set);
1058     qh_errexit (qhmem_ERRqhull, NULL, NULL);
1059   }
1060 } /* setreplace */
1061
1062
1063 /*-<a                             href="qh-set.htm#TOC"
1064   >-------------------------------<a name="setsize">-</a>
1065   
1066   qh_setsize( set )
1067     returns the size of a set
1068
1069   notes:
1070     errors if set's maxsize is incorrect
1071     same as SETreturnsize_(set)
1072
1073   design:
1074     determine actual size of set from maxsize
1075 */
1076 int qh_setsize(setT *set) {
1077   int size, *sizep;
1078   
1079   if (!set)
1080     return (0);
1081   sizep= SETsizeaddr_(set);
1082   if ((size= *sizep)) {
1083     size--;
1084     if (size > set->maxsize) {
1085       fprintf (qhmem.ferr, "qhull internal error (qh_setsize): current set size %d is greater than maximum size %d\n",
1086                size, set->maxsize);
1087       qh_setprint (qhmem.ferr, "set: ", set);
1088       qh_errexit (qhmem_ERRqhull, NULL, NULL);
1089     }
1090   }else
1091     size= set->maxsize;
1092   return size;
1093 } /* setsize */
1094
1095 /*-<a                             href="qh-set.htm#TOC"
1096   >-------------------------------<a name="settemp">-</a>
1097   
1098   qh_settemp( setsize )
1099     return a stacked, temporary set of upto setsize elements
1100
1101   notes:
1102     use settempfree or settempfree_all to release from qhmem.tempstack
1103     see also qh_setnew
1104
1105   design:
1106     allocate set
1107     append to qhmem.tempstack
1108     
1109 */
1110 setT *qh_settemp(int setsize) {
1111   setT *newset;
1112   
1113   newset= qh_setnew (setsize);
1114   qh_setappend ((setT **)&qhmem.tempstack, newset);
1115   if (qhmem.IStracing >= 5)
1116     fprintf (qhmem.ferr, "qh_settemp: temp set %p of %d elements, depth %d\n",
1117        newset, newset->maxsize, qh_setsize ((setT*)qhmem.tempstack));
1118   return newset;
1119 } /* settemp */
1120
1121 /*-<a                             href="qh-set.htm#TOC"
1122   >-------------------------------<a name="settempfree">-</a>
1123   
1124   qh_settempfree( set )
1125     free temporary set at top of qhmem.tempstack
1126
1127   notes:
1128     nop if set is NULL
1129     errors if set not from previous   qh_settemp
1130   
1131   to locate errors:
1132     use 'T2' to find source and then find mis-matching qh_settemp
1133
1134   design:
1135     check top of qhmem.tempstack
1136     free it
1137 */
1138 void qh_settempfree(setT **set) {
1139   setT *stackedset;
1140
1141   if (!*set)
1142     return;
1143   stackedset= qh_settemppop ();
1144   if (stackedset != *set) {
1145     qh_settemppush(stackedset);
1146     fprintf (qhmem.ferr, "qhull internal error (qh_settempfree): set %p (size %d) was not last temporary allocated (depth %d, set %p, size %d)\n",
1147              *set, qh_setsize(*set), qh_setsize((setT*)qhmem.tempstack)+1,
1148              stackedset, qh_setsize(stackedset));
1149     qh_errexit (qhmem_ERRqhull, NULL, NULL);
1150   }
1151   qh_setfree (set);
1152 } /* settempfree */
1153
1154 /*-<a                             href="qh-set.htm#TOC"
1155   >-------------------------------<a name="settempfree_all">-</a>
1156   
1157   qh_settempfree_all(  )
1158     free all temporary sets in qhmem.tempstack
1159
1160   design:
1161     for each set in tempstack
1162       free set
1163     free qhmem.tempstack
1164 */
1165 void qh_settempfree_all(void) {
1166   setT *set, **setp;
1167
1168   FOREACHset_((setT *)qhmem.tempstack) 
1169     qh_setfree(&set);
1170   qh_setfree((setT **)&qhmem.tempstack);
1171 } /* settempfree_all */
1172
1173 /*-<a                             href="qh-set.htm#TOC"
1174   >-------------------------------<a name="settemppop">-</a>
1175   
1176   qh_settemppop(  )
1177     pop and return temporary set from qhmem.tempstack 
1178
1179   notes:
1180     the returned set is permanent
1181     
1182   design:
1183     pop and check top of qhmem.tempstack
1184 */
1185 setT *qh_settemppop(void) {
1186   setT *stackedset;
1187   
1188   stackedset= (setT*)qh_setdellast((setT *)qhmem.tempstack);
1189   if (!stackedset) {
1190     fprintf (qhmem.ferr, "qhull internal error (qh_settemppop): pop from empty temporary stack\n");
1191     qh_errexit (qhmem_ERRqhull, NULL, NULL);
1192   }
1193   if (qhmem.IStracing >= 5)
1194     fprintf (qhmem.ferr, "qh_settemppop: depth %d temp set %p of %d elements\n",
1195        qh_setsize((setT*)qhmem.tempstack)+1, stackedset, qh_setsize(stackedset));
1196   return stackedset;
1197 } /* settemppop */
1198
1199 /*-<a                             href="qh-set.htm#TOC"
1200   >-------------------------------<a name="settemppush">-</a>
1201   
1202   qh_settemppush( set )
1203     push temporary set unto qhmem.tempstack (makes it temporary)
1204
1205   notes:
1206     duplicates settemp() for tracing
1207
1208   design:
1209     append set to tempstack  
1210 */
1211 void qh_settemppush(setT *set) {
1212   
1213   qh_setappend ((setT**)&qhmem.tempstack, set);
1214   if (qhmem.IStracing >= 5)
1215     fprintf (qhmem.ferr, "qh_settemppush: depth %d temp set %p of %d elements\n",
1216     qh_setsize((setT*)qhmem.tempstack), set, qh_setsize(set));
1217 } /* settemppush */
1218
1219  
1220 /*-<a                             href="qh-set.htm#TOC"
1221   >-------------------------------<a name="settruncate">-</a>
1222   
1223   qh_settruncate( set, size )
1224     truncate set to size elements
1225
1226   notes:
1227     set must be defined
1228   
1229   see:
1230     SETtruncate_
1231
1232   design:
1233     check size
1234     update actual size of set
1235 */
1236 void qh_settruncate (setT *set, int size) {
1237
1238   if (size < 0 || size > set->maxsize) {
1239     fprintf (qhmem.ferr, "qhull internal error (qh_settruncate): size %d out of bounds for set:\n", size);
1240     qh_setprint (qhmem.ferr, "", set);
1241     qh_errexit (qhmem_ERRqhull, NULL, NULL);
1242   }
1243   set->e[set->maxsize].i= size+1;   /* maybe overwritten */
1244   set->e[size].p= NULL;
1245 } /* settruncate */
1246     
1247 /*-<a                             href="qh-set.htm#TOC"
1248   >-------------------------------<a name="setunique">-</a>
1249   
1250   qh_setunique( set, elem )
1251     add elem to unsorted set unless it is already in set
1252
1253   notes:
1254     returns 1 if it is appended
1255
1256   design:
1257     if elem not in set
1258       append elem to set
1259 */
1260 int qh_setunique (setT **set, void *elem) {
1261
1262   if (!qh_setin (*set, elem)) {
1263     qh_setappend (set, elem);
1264     return 1;
1265   }
1266   return 0;
1267 } /* setunique */
1268     
1269 /*-<a                             href="qh-set.htm#TOC"
1270   >-------------------------------<a name="setzero">-</a>
1271   
1272   qh_setzero( set, index, size )
1273     zero elements from index on
1274     set actual size of set to size
1275
1276   notes:
1277     set must be defined
1278     the set becomes an indexed set (can not use FOREACH...)
1279   
1280   see also:
1281     qh_settruncate
1282     
1283   design:
1284     check index and size
1285     update actual size
1286     zero elements starting at e[index]   
1287 */
1288 void qh_setzero (setT *set, int index, int size) {
1289   int count;
1290
1291   if (index < 0 || index >= size || size > set->maxsize) {
1292     fprintf (qhmem.ferr, "qhull internal error (qh_setzero): index %d or size %d out of bounds for set:\n", index, size);
1293     qh_setprint (qhmem.ferr, "", set);
1294     qh_errexit (qhmem_ERRqhull, NULL, NULL);
1295   }
1296   set->e[set->maxsize].i=  size+1;  /* may be overwritten */
1297   count= size - index + 1;   /* +1 for NULL terminator */
1298   memset ((char *)SETelemaddr_(set, index, void), 0, count * SETelemsize);
1299 } /* setzero */
1300
1301