Point Cloud Library (PCL)
1.7.0
|
00001 #if !defined(ON_COMPILING_OPENNURBS_HSORT_FUNCTIONS) 00002 /* 00003 See opennurbs_sort.cpp for examples of using openurbs_hsort_template.c 00004 to define type specific heap sort functions. 00005 */ 00006 #error Do not compile openurbs_hsort_template.c directly. 00007 #endif 00008 00009 // ON_SORT_TEMPLATE_TYPE -> double, int, .... 00010 #if !defined(ON_SORT_TEMPLATE_TYPE) 00011 #error Define ON_SORT_TEMPLATE_TYPE macro before including opennurbs_qsort_template.c 00012 #endif 00013 00014 #if !defined(ON_HSORT_FNAME) 00015 #error Define ON_HSORT_FNAME macro before including opennurbs_qsort_template.c 00016 #endif 00017 00018 #if defined(ON_SORT_TEMPLATE_COMPARE) 00019 // use a compare function like strcmp for char* strings 00020 #define ON_HSORT_GT(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) > 0 00021 #define ON_HSORT_GT_TMP(A) ON_SORT_TEMPLATE_COMPARE(A,&tmp) > 0 00022 #else 00023 // use type compares 00024 #define ON_HSORT_GT(A,B) *A > *B 00025 #define ON_HSORT_GT_TMP(A) *A > tmp 00026 #endif 00027 00028 #if defined(ON_SORT_TEMPLATE_USE_MEMCPY) 00029 #define ON_HSORT_TO_TMP(A) memcpy(&tmp,A,sizeof(tmp)) 00030 #define ON_HSORT_FROM_TMP(A) memcpy(A,&tmp,sizeof(tmp)) 00031 #define ON_HSORT_COPY(dst,src) memcpy(dst,src,sizeof(tmp)) 00032 #else 00033 #define ON_HSORT_TO_TMP(A) tmp = *A 00034 #define ON_HSORT_FROM_TMP(A) *A = tmp 00035 #define ON_HSORT_COPY(dst,src) *dst = *src 00036 #endif 00037 00038 #if defined(ON_SORT_TEMPLATE_STATIC_FUNCTION) 00039 static 00040 #endif 00041 void 00042 ON_HSORT_FNAME( ON_SORT_TEMPLATE_TYPE* base, size_t nel ) 00043 { 00044 size_t i_end,k,i,j; 00045 ON_SORT_TEMPLATE_TYPE* e_end; 00046 ON_SORT_TEMPLATE_TYPE* e_i; 00047 ON_SORT_TEMPLATE_TYPE* e_j; 00048 ON_SORT_TEMPLATE_TYPE tmp; 00049 00050 if (0 == base || nel < 2) 00051 return; 00052 00053 k = nel >> 1; 00054 i_end = nel-1; 00055 e_end = base + i_end; 00056 for (;;) 00057 { 00058 if (k) 00059 { 00060 --k; 00061 ON_HSORT_TO_TMP((base+k)); /* e_tmp = e[k]; */ 00062 } 00063 else 00064 { 00065 ON_HSORT_TO_TMP(e_end); /* e_tmp = e[i_end]; */ 00066 ON_HSORT_COPY(e_end,base); /* e[i_end] = e[0]; */ 00067 if (!(--i_end)) 00068 { 00069 ON_HSORT_FROM_TMP(base); /* e[0] = e_tmp; */ 00070 break; 00071 } 00072 e_end--; 00073 } 00074 00075 i = k; 00076 j = (k<<1) + 1; 00077 e_i = base + i; 00078 while (j <= i_end) 00079 { 00080 e_j = base + j; 00081 if (j < i_end && ON_HSORT_GT((e_j+1),e_j) /*e[j] < e[j + 1] */) 00082 { 00083 j++; 00084 e_j++; 00085 } 00086 if (ON_HSORT_GT_TMP(e_j) /* tmp < e[j] */) 00087 { 00088 ON_HSORT_COPY(e_i,e_j); /* e[i] = e[j]; */ 00089 i = j; 00090 e_i = e_j; 00091 j = (j<<1) + 1; 00092 } 00093 else 00094 j = i_end + 1; 00095 } 00096 00097 ON_HSORT_FROM_TMP(e_i); /* e[i] = e_tmp; */ 00098 } 00099 } 00100 00101 #undef ON_HSORT_GT 00102 #undef ON_HSORT_GT_TMP 00103 #undef ON_HSORT_TO_TMP 00104 #undef ON_HSORT_FROM_TMP 00105 #undef ON_HSORT_COPY 00106 #undef ON_HSORT_FROM_TMP