HOOPS/3dGS I.M. Interface

     << Back      Full Index      Forward >>


hqsort.h

00001 /*
00002  * Copyright (c) 1998 by Tech Soft 3D, LLC.
00003  * The information contained herein is confidential and proprietary to
00004  * Tech Soft 3D, LLC., and considered a trade secret as defined under
00005  * civil and criminal statutes.  Tech Soft 3D shall pursue its civil
00006  * and criminal remedies in the event of unauthorized use or misappropriation
00007  * of its trade secrets.  Use of this information by anyone other than
00008  * authorized employees of Tech Soft 3D, LLC. is granted only under a
00009  * written non-disclosure agreement, expressly prescribing the scope and
00010  * manner of such use.
00011  *
00012  * $Id: hqsort_8h-source.html,v 1.29 2008-03-10 07:09:28 stage Exp $
00013  */
00014 
00015 
00016 #if 0  
00017 /* the usage from the C file would look something like this (taken from generate_curve_polyline) */
00018 #define QS_TYPE             LineHeap *              /* the type of object or array that contains all values */
00019 #define QS_VAL(thing,a)     (thing->h[a].u_left)    /* returns the value of an item with index a */
00020 #define QS_COMPARE(f1,f2)   (f1>f2)                 /* use ">" to sort ascending, "<" to sort descending */
00021 #define QS_SWAP(thing,a,b)  swaph(thing, a, b)      /* swaps two values */
00022 #include "hqsort.h"
00023 /* and the function calls... */
00024 quick_sort(&heap, 0, heap.used - 1);
00025 ASSERT (issorted (&heap, heap.used));
00026 #endif
00027 
00028 /* define QS_RESET and include to get rid of all defs */
00029 /* must define QS_NAME for second include */
00030 #ifdef QS_RESET
00031 
00032 #undef QS_TYPE          
00033 #undef QS_VAL
00034 #undef QS_COMPARE
00035 #undef QS_SWAP
00036 #undef QS_MEDIANOF3INDEX
00037 #undef QS_COMPARETYPE
00038 #undef QS_COMPLEX_COMPARE
00039 #undef QS_EQUAL
00040 #undef QS_EQUAL_NOT_POSSIBLE
00041 #undef QS_COMPLEX_COMPARE
00042 #undef QS_PIVOT_VAL
00043 #undef QS_USE_SYSTEM_RAND
00044 #undef QS_PRESORTED_CHECK
00045 #undef QS_NEED_ISSORTED
00046 #undef quick_sort
00047 #undef QS_BUBBLE_SORT           
00048 #undef QS_QUICK_SORT_RECURSIVE  
00049 #undef QS_ISSORTED
00050 #undef QS_RESET
00051 
00052 #else           
00053 /*
00054   motivation:
00055     we want to avoid the function call per comparison, which rules out "void *" based algorithms.
00056  
00057   restrictions: 
00058     1) value to compare must resolve to a single value
00059     2) items must be identifiable by integer 
00060     3) whatever type QS_TYPE is defined as must be fully defined at the time of the include
00061 */
00062 
00063 #if !defined(QS_TYPE) || !defined(QS_VAL) || (!defined(QS_COMPARE)&&!defined(QS_COMPLEX_COMPARE)) || !defined(QS_SWAP)
00064 #    error "source file must define QS_TYPE, QS_VAL, QS_COMPARE and QS_SWAP before including this header"
00065 #endif
00066 
00067 
00068 #define QS_MEDIANOF3INDEX(a,b,c) (((a)>(b))?(((b)>(c))?(1):(((a)>(c))?(2):(0))):(((a)>(c))?(0):((b)>(c))?(2):(1)))
00069 #ifndef QS_COMPARETYPE
00070 #  define QS_COMPARETYPE float
00071 #endif
00072 
00073 /* this optional definition is used for when the comparison has to be multi-tiered */
00074 #ifdef QS_COMPLEX_COMPARE
00075 #  ifndef QS_EQUAL
00076 #    define QS_EQUAL_NOT_POSSIBLE
00077 #  endif
00078 #else
00079 #  define QS_COMPLEX_COMPARE(thing,i1,i2) QS_COMPARE (QS_VAL (thing,i1), QS_VAL (thing,i2))
00080 #  define QS_PIVOT_VAL(thing,i1) QS_VAL(thing,i1)
00081 #endif
00082 
00083 
00084 #ifndef QS_BUBBLE_SORT
00085 #define QS_BUBBLE_SORT              bubble_sort 
00086 #endif
00087 
00088 #ifndef QS_QUICK_SORT_RECURSIVE
00089 #define QS_QUICK_SORT_RECURSIVE     quick_sort_recursive
00090 #define quick_sort(thing,left,right) quick_sort_recursive(thing,left,right,1024);
00091 #endif
00092 
00093 #ifndef QS_ISSORTED
00094 #define QS_ISSORTED                 issorted
00095 #endif
00096 
00097 
00098 local void QS_BUBBLE_SORT(QS_TYPE thing, int left, int right) 
00099 {
00100     int i, j;
00101 
00102     for (i = left; i <= right; i++) {
00103         for (j = i+1; j <= right; j++) {
00104             if (QS_COMPLEX_COMPARE (thing,i,j))
00105                     QS_SWAP (thing, j, i);
00106         }
00107     }
00108 }
00109 
00110 /* hqsort.h can be used from outside of HOOPS, but you will get an error,
00111  * "unresolved external symbol __HOOPS" if you don't define QS_USE_SYSTEM_RAND */
00112 #ifdef QS_USE_SYSTEM_RAND
00113 #  undef URANDOM
00114 #  include <stdlib.h>
00115 #  define URANDOM() (unsigned int)rand()
00116 #endif
00117 
00118 /* the following implementation of quick sort is a variant that merges all values
00119  * that are exactly equal to the pivot as a single block in the middle, so that they can
00120  * be skipped when we recurse down to lower levels.  It has a hardcoded limit to the depth
00121  * of the recursion so that we avoid trashing the stack, but in our tests, we have never
00122  * been able to make it get anywhere near that limit. */
00123 
00124 local void QS_QUICK_SORT_RECURSIVE (QS_TYPE thing, int left, int right, int recursion_limit) 
00125 {
00126     int i, j, k, lower, upper, count;
00127     int pivot; /* index of the item to be used as a pivot */
00128 
00129 #if defined(HI_PROTO_DEFINED)
00130     if (recursion_limit == 0) {
00131         HI_Warning (2 /* HEC_INTERNAL_ERROR */, 288 /* HES_OUT_OF_RANGE */, "Quick sort recursion depth limit reached");
00132     }
00133 #endif
00134 
00135     if (recursion_limit == 0 || (right - left) <= 32) {
00136         QS_BUBBLE_SORT(thing, left, right);
00137         return;
00138     }
00139     
00140 
00141     if (right - left <= 1) {
00142         if (right <= left) 
00143             return;
00144         /* under most circumstances, the following comparison resolves to
00145             QS_COMPARE (QS_VAL (thing,left), QS_VAL (thing,right)) */
00146         if (QS_COMPLEX_COMPARE(thing,left,right))
00147             QS_SWAP (thing, right, left);
00148         return;
00149     }
00150 
00151 #ifdef QS_PRESORTED_CHECK
00152     for (i = left; i <right; i++) {
00153         if (QS_COMPLEX_COMPARE(thing,i,i+1))
00154             break;
00155     }
00156     if (i >= right)
00157         return;
00158 #endif
00159 
00160     i=left;
00161     j=right-1;
00162     lower=left;
00163     upper=right-1;
00164 
00165     count = right - left + 1;
00166     if (count > 8) {
00167         int sample1, sample2, sample3;  
00168   
00169         sample1 = left + (URANDOM() % count);
00170         sample2 = left + (URANDOM() % count);
00171         sample3 = left + (URANDOM() % count);
00172         /* these next few statements calculate the median and move it to the rightmost position */
00173         switch (QS_MEDIANOF3INDEX(QS_VAL (thing,sample1), QS_VAL (thing,sample2), QS_VAL (thing,sample3))) {
00174             case 0:
00175                 if (sample1 != right)
00176                     QS_SWAP (thing, sample1, right);
00177                 break;
00178             case 1:
00179                 if (sample2 != right)
00180                     QS_SWAP (thing, sample2, right);
00181                 break;
00182             case 2:
00183                 if (sample3 != right)
00184                     QS_SWAP (thing, sample3, right);
00185                 break;
00186         }
00187     }
00188     else {
00189         int sample1 = left + (URANDOM() % count);
00190         if (sample1 != right)
00191             QS_SWAP (thing, sample1, right);
00192     }
00193     pivot=right;
00194 
00195     while (1) {
00196         /* under most circumstances, the following comparison resolves to 
00197             QS_COMPARE (pivot,QS_VAL (thing,i)) */
00198         while (QS_COMPLEX_COMPARE(thing,pivot,i))  {
00199             i++;
00200             if (i == right)
00201                 break;
00202         }
00203         while (QS_COMPLEX_COMPARE(thing,j,pivot))  {
00204             j--;
00205             if (j == left) 
00206                 break;
00207         }
00208         if (i >= j) 
00209             break;
00210         QS_SWAP (thing, i, j);
00211 
00212 /* if the caller provided a macro to test for equality, use it.  otherwise, compare QS_VAL's */
00213 #ifndef QS_EQUAL_NOT_POSSIBLE
00214 #  ifdef QS_EQUAL
00215         if (QS_EQUAL (thing,i,pivot)) { 
00216             if (lower != i)
00217                 QS_SWAP (thing, lower, i); 
00218             lower++; 
00219             i++;
00220         }
00221         if (QS_EQUAL (thing,pivot,j)) { 
00222             if (j != upper)
00223                 QS_SWAP (thing, j, upper); 
00224             upper--; 
00225             j--;
00226         }
00227 #  else
00228         if (QS_VAL (thing,i) == QS_VAL (thing,pivot)) { 
00229             if (lower != i)
00230                 QS_SWAP (thing, lower, i); 
00231             lower++; 
00232             i++;
00233         }
00234         if (QS_VAL (thing,pivot) == QS_VAL (thing,j)) { 
00235             if (j != upper)
00236                 QS_SWAP (thing, j, upper); 
00237             upper--; 
00238             j--;
00239         }
00240 #  endif
00241 #endif
00242     }
00243     if (i != right)
00244         QS_SWAP (thing, i, right); 
00245     j = i-1;
00246     for (k=left; k<lower; k++, j--)
00247         if (k != j)
00248             QS_SWAP (thing, k, j);
00249     i++;
00250     for (k=right-1; k>upper; k--, i++) 
00251         if (i != k)
00252             QS_SWAP (thing, i, k);
00253 
00254     QS_QUICK_SORT_RECURSIVE (thing, left, j, recursion_limit - 1);
00255     QS_QUICK_SORT_RECURSIVE (thing, i, right, recursion_limit - 1);
00256 }
00257 
00258 
00259 #ifdef _DEBUG
00260 /* for debugging only */
00261 #ifdef QS_NEED_ISSORTED
00262 local bool QS_ISSORTED (
00263         QS_TYPE thing,
00264         int count) 
00265 {
00266     int i;
00267 
00268     for (i = 1; i < count; i++) {
00269         if (QS_VAL(thing,i-1) != QS_VAL(thing,i) &&
00270             QS_COMPARE(QS_VAL(thing,i-1),QS_VAL(thing,i)))
00271             return false;
00272     }
00273     return true;
00274 }
00275 #endif
00276 #endif
00277 
00278 /* QS_RESET */
00279 #endif
00280 
00281 
00282 
Main Index
HOOPS/3dGS I.M. Interface

     << Back      Full Index      Forward >>