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