Changeset View
Changeset View
Standalone View
Standalone View
extern/opennurbs/opennurbs_qsort_template.h
- This file was added.
| // NOTE: 14 April 2011 Dale Lear: | |||||
| // Replace this code with Mikko's "quacksort", once "quacksort" is fully debugged | |||||
| // This code is based ont the VC 2010 crt qsort.c file and must not be released | |||||
| // with public opennurbs. | |||||
| #if !defined(ON_COMPILING_OPENNURBS_QSORT_FUNCTIONS) | |||||
| /* | |||||
| See opennurbs_sort.cpp for examples of using openurbs_qsort_template.c | |||||
| to define type specific quick sort functions. | |||||
| */ | |||||
| #error Do not compile openurbs_qsort_template.c directly. | |||||
| #endif | |||||
| #define ON_QSORT_CUTOFF 8 /* testing shows that this is good value */ | |||||
| /* Note: the theoretical number of stack entries required is | |||||
| no more than 1 + log2(num). But we switch to insertion | |||||
| sort for CUTOFF elements or less, so we really only need | |||||
| 1 + log2(num) - log2(CUTOFF) stack entries. For a CUTOFF | |||||
| of 8, that means we need no more than 30 stack entries for | |||||
| 32 bit platforms, and 62 for 64-bit platforms. */ | |||||
| #define ON_QSORT_STKSIZ (8*sizeof(void*) - 2) | |||||
| // ON_SORT_TEMPLATE_TYPE -> double, int, .... | |||||
| #if !defined(ON_SORT_TEMPLATE_TYPE) | |||||
| #error Define ON_SORT_TEMPLATE_TYPE macro before including opennurbs_qsort_template.c | |||||
| #endif | |||||
| #if !defined(ON_QSORT_FNAME) | |||||
| #error Define ON_QSORT_FNAME macro before including opennurbs_qsort_template.c | |||||
| #endif | |||||
| #if !defined(ON_QSORT_GT) && !defined(ON_QSORT_LE) && !defined(ON_QSORT_EQ) | |||||
| #if defined(ON_SORT_TEMPLATE_COMPARE) | |||||
| // use a compare function like strcmp for char* strings | |||||
| #define ON_QSORT_GT(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) > 0 | |||||
| #define ON_QSORT_LE(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) <= 0 | |||||
| #define ON_QSORT_EQ(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) == 0 | |||||
| #else | |||||
| // use type compares | |||||
| #define ON_QSORT_GT(A,B) *A > *B | |||||
| #define ON_QSORT_LE(A,B) *A <= *B | |||||
| #define ON_QSORT_EQ(A,B) *A == *B | |||||
| #endif | |||||
| #endif | |||||
| #if defined(ON_SORT_TEMPLATE_SWAP) | |||||
| #define ON_QSORT_SWAP ON_SORT_TEMPLATE_SWAP | |||||
| #elif defined(ON_SORT_TEMPLATE_USE_MEMCPY) | |||||
| #define ON_QSORT_SWAP(A,B) memcpy(&tmp,A,sizeof(tmp));memcpy(A,B,sizeof(tmp));memcpy(B,&tmp,sizeof(tmp)) | |||||
| #else | |||||
| #define ON_QSORT_SWAP(A,B) tmp = *A; *A = *B; *B = tmp | |||||
| #endif | |||||
| // When opennurbs_qsort_template.h is included more than once | |||||
| // in the same file for sorting the same type with different | |||||
| // compare functions, then either | |||||
| // 1) After the first include, define ON_SORT_TEMPLATE_HAVE_SHORT_SORT | |||||
| // to prevent generation of an identical short-sort function | |||||
| // or | |||||
| // 2) Define different values of ON_QSORT_SHORT_SORT_FNAME to generate | |||||
| // different short-sort helper functions. | |||||
| #if !defined(ON_SORT_TEMPLATE_HAVE_SHORT_SORT) | |||||
| #if !defined(ON_QSORT_SHORT_SORT_FNAME) | |||||
| // The default name for the short sort helper function is ON__shortsort | |||||
| #define ON_QSORT_SHORT_SORT_FNAME ON__shortsort | |||||
| #endif | |||||
| static void ON_QSORT_SHORT_SORT_FNAME(ON_SORT_TEMPLATE_TYPE *, ON_SORT_TEMPLATE_TYPE *); | |||||
| static void ON_QSORT_SHORT_SORT_FNAME(ON_SORT_TEMPLATE_TYPE *lo, ON_SORT_TEMPLATE_TYPE *hi) | |||||
| { | |||||
| ON_SORT_TEMPLATE_TYPE *p; | |||||
| ON_SORT_TEMPLATE_TYPE *max; | |||||
| ON_SORT_TEMPLATE_TYPE tmp; | |||||
| /* Note: in assertions below, i and j are alway inside original bound of | |||||
| array to sort. */ | |||||
| while (hi > lo) | |||||
| { | |||||
| /* A[i] <= A[j] for i <= j, j > hi */ | |||||
| max = lo; | |||||
| for (p = lo+1; p <= hi; p++) | |||||
| { | |||||
| /* A[i] <= A[max] for lo <= i < p */ | |||||
| if ( ON_QSORT_GT(p,max) ) | |||||
| { | |||||
| max = p; | |||||
| } | |||||
| /* A[i] <= A[max] for lo <= i <= p */ | |||||
| } | |||||
| /* A[i] <= A[max] for lo <= i <= hi */ | |||||
| ON_QSORT_SWAP(max,hi); | |||||
| /* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */ | |||||
| hi--; | |||||
| /* A[i] <= A[j] for i <= j, j > hi, loop top condition established */ | |||||
| } | |||||
| /* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j, | |||||
| so array is sorted */ | |||||
| } | |||||
| #endif | |||||
| /* this parameter defines the cutoff between using quick sort and | |||||
| insertion sort for arrays; arrays with lengths shorter or equal to the | |||||
| below value use insertion sort */ | |||||
| #if defined(ON_SORT_TEMPLATE_STATIC_FUNCTION) | |||||
| static | |||||
| #endif | |||||
| void | |||||
| ON_QSORT_FNAME ( | |||||
| ON_SORT_TEMPLATE_TYPE *base, | |||||
| size_t num | |||||
| ) | |||||
| { | |||||
| ON_SORT_TEMPLATE_TYPE *lo; /* start of sub-array currently sorting */ | |||||
| ON_SORT_TEMPLATE_TYPE *hi; /* end of sub-array currently sorting */ | |||||
| ON_SORT_TEMPLATE_TYPE *mid; /* points to middle of subarray */ | |||||
| ON_SORT_TEMPLATE_TYPE *loguy; /* traveling pointers for partition step */ | |||||
| ON_SORT_TEMPLATE_TYPE *higuy; /* traveling pointers for partition step */ | |||||
| ON_SORT_TEMPLATE_TYPE *lostk[ON_QSORT_STKSIZ]; | |||||
| ON_SORT_TEMPLATE_TYPE *histk[ON_QSORT_STKSIZ]; | |||||
| size_t size; /* size of the sub-array */ | |||||
| int stkptr; /* stack for saving sub-array to be processed */ | |||||
| ON_SORT_TEMPLATE_TYPE tmp; | |||||
| if ( 0 == base || num < 2 ) | |||||
| return; | |||||
| stkptr = 0; /* initialize stack */ | |||||
| lo = base; | |||||
| hi = base + (num-1); /* initialize limits */ | |||||
| /* this entry point is for pseudo-recursion calling: setting | |||||
| lo and hi and jumping to here is like recursion, but stkptr is | |||||
| preserved, locals aren't, so we preserve stuff on the stack */ | |||||
| recurse: | |||||
| size = (hi - lo) + 1; /* number of el's to sort */ | |||||
| /* below a certain size, it is faster to use a O(n^2) sorting method */ | |||||
| if (size <= ON_QSORT_CUTOFF) | |||||
| { | |||||
| ON_QSORT_SHORT_SORT_FNAME(lo, hi); | |||||
| } | |||||
| else { | |||||
| /* First we pick a partitioning element. The efficiency of the | |||||
| algorithm demands that we find one that is approximately the median | |||||
| of the values, but also that we select one fast. We choose the | |||||
| median of the first, middle, and last elements, to avoid bad | |||||
| performance in the face of already sorted data, or data that is made | |||||
| up of multiple sorted runs appended together. Testing shows that a | |||||
| median-of-three algorithm provides better performance than simply | |||||
| picking the middle element for the latter case. */ | |||||
| mid = lo + (size / 2); /* find middle element */ | |||||
| /* Sort the first, middle, last elements into order */ | |||||
| if ( ON_QSORT_GT(lo,mid) ) {ON_QSORT_SWAP(lo,mid);} | |||||
| if ( ON_QSORT_GT(lo,hi) ) {ON_QSORT_SWAP(lo,hi);} | |||||
| if ( ON_QSORT_GT(mid,hi) ) {ON_QSORT_SWAP(mid,hi);} | |||||
| /* We now wish to partition the array into three pieces, one consisting | |||||
| of elements <= partition element, one of elements equal to the | |||||
| partition element, and one of elements > than it. This is done | |||||
| below; comments indicate conditions established at every step. */ | |||||
| loguy = lo; | |||||
| higuy = hi; | |||||
| /* Note that higuy decreases and loguy increases on every iteration, | |||||
| so loop must terminate. */ | |||||
| for (;;) | |||||
| { | |||||
| /* lo <= loguy < hi, lo < higuy <= hi, | |||||
| A[i] <= A[mid] for lo <= i <= loguy, | |||||
| A[i] > A[mid] for higuy <= i < hi, | |||||
| A[hi] >= A[mid] */ | |||||
| /* The doubled loop is to avoid calling comp(mid,mid), since some | |||||
| existing comparison funcs don't work when passed the same | |||||
| value for both pointers. */ | |||||
| if (mid > loguy) | |||||
| { | |||||
| do { | |||||
| loguy++; | |||||
| } while (loguy < mid && ON_QSORT_LE(loguy,mid)); | |||||
| } | |||||
| if (mid <= loguy) | |||||
| { | |||||
| do { | |||||
| loguy++; | |||||
| } while (loguy <= hi && ON_QSORT_LE(loguy,mid)); | |||||
| } | |||||
| /* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy, | |||||
| either loguy > hi or A[loguy] > A[mid] */ | |||||
| do { | |||||
| higuy--; | |||||
| } while (higuy > mid && ON_QSORT_GT(higuy,mid)); | |||||
| /* lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi, | |||||
| either higuy == lo or A[higuy] <= A[mid] */ | |||||
| if (higuy < loguy) | |||||
| break; | |||||
| /* if loguy > hi or higuy == lo, then we would have exited, so | |||||
| A[loguy] > A[mid], A[higuy] <= A[mid], | |||||
| loguy <= hi, higuy > lo */ | |||||
| ON_QSORT_SWAP(loguy,higuy); | |||||
| /* If the partition element was moved, follow it. Only need | |||||
| to check for mid == higuy, since before the swap, | |||||
| A[loguy] > A[mid] implies loguy != mid. */ | |||||
| if (mid == higuy) | |||||
| mid = loguy; | |||||
| /* A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top | |||||
| of loop is re-established */ | |||||
| } | |||||
| /* A[i] <= A[mid] for lo <= i < loguy, | |||||
| A[i] > A[mid] for higuy < i < hi, | |||||
| A[hi] >= A[mid] | |||||
| higuy < loguy | |||||
| implying: | |||||
| higuy == loguy-1 | |||||
| or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid] */ | |||||
| /* Find adjacent elements equal to the partition element. The | |||||
| doubled loop is to avoid calling comp(mid,mid), since some | |||||
| existing comparison funcs don't work when passed the same value | |||||
| for both pointers. */ | |||||
| higuy++; | |||||
| if (mid < higuy) { | |||||
| do { | |||||
| higuy--; | |||||
| } while (higuy > mid && ON_QSORT_EQ(higuy,mid)); | |||||
| } | |||||
| if (mid >= higuy) { | |||||
| do { | |||||
| higuy--; | |||||
| } while (higuy > lo && ON_QSORT_EQ(higuy,mid)); | |||||
| } | |||||
| /* OK, now we have the following: | |||||
| higuy < loguy | |||||
| lo <= higuy <= hi | |||||
| A[i] <= A[mid] for lo <= i <= higuy | |||||
| A[i] == A[mid] for higuy < i < loguy | |||||
| A[i] > A[mid] for loguy <= i < hi | |||||
| A[hi] >= A[mid] */ | |||||
| /* We've finished the partition, now we want to sort the subarrays | |||||
| [lo, higuy] and [loguy, hi]. | |||||
| We do the smaller one first to minimize stack usage. | |||||
| We only sort arrays of length 2 or more.*/ | |||||
| if ( higuy - lo >= hi - loguy ) { | |||||
| if (lo < higuy) { | |||||
| lostk[stkptr] = lo; | |||||
| histk[stkptr] = higuy; | |||||
| ++stkptr; | |||||
| } /* save big recursion for later */ | |||||
| if (loguy < hi) { | |||||
| lo = loguy; | |||||
| goto recurse; /* do small recursion */ | |||||
| } | |||||
| } | |||||
| else { | |||||
| if (loguy < hi) { | |||||
| lostk[stkptr] = loguy; | |||||
| histk[stkptr] = hi; | |||||
| ++stkptr; /* save big recursion for later */ | |||||
| } | |||||
| if (lo < higuy) { | |||||
| hi = higuy; | |||||
| goto recurse; /* do small recursion */ | |||||
| } | |||||
| } | |||||
| } | |||||
| /* We have sorted the array, except for any pending sorts on the stack. | |||||
| Check if there are any, and do them. */ | |||||
| --stkptr; | |||||
| if (stkptr >= 0) { | |||||
| lo = lostk[stkptr]; | |||||
| hi = histk[stkptr]; | |||||
| goto recurse; /* pop subarray from stack */ | |||||
| } | |||||
| else | |||||
| return; /* all subarrays done */ | |||||
| } | |||||
| #undef ON_QSORT_GT | |||||
| #undef ON_QSORT_LE | |||||
| #undef ON_QSORT_EQ | |||||
| #undef ON_QSORT_SWAP | |||||
| #undef ON_QSORT_CUTOFF | |||||
| #undef ON_QSORT_STKSIZ | |||||