Point Cloud Library (PCL) 1.13.0
Loading...
Searching...
No Matches
opennurbs_hsort_template.h
1#if !defined(ON_COMPILING_OPENNURBS_HSORT_FUNCTIONS)
2/*
3See opennurbs_sort.cpp for examples of using openurbs_hsort_template.c
4to define type specific heap sort functions.
5*/
6#error Do not compile openurbs_hsort_template.c directly.
7#endif
8
9// ON_SORT_TEMPLATE_TYPE -> double, int, ....
10#if !defined(ON_SORT_TEMPLATE_TYPE)
11#error Define ON_SORT_TEMPLATE_TYPE macro before including opennurbs_qsort_template.c
12#endif
13
14#if !defined(ON_HSORT_FNAME)
15#error Define ON_HSORT_FNAME macro before including opennurbs_qsort_template.c
16#endif
17
18#if defined(ON_SORT_TEMPLATE_COMPARE)
19// use a compare function like strcmp for char* strings
20#define ON_HSORT_GT(A,B) ON_SORT_TEMPLATE_COMPARE(A,B) > 0
21#define ON_HSORT_GT_TMP(A) ON_SORT_TEMPLATE_COMPARE(A,&tmp) > 0
22#else
23// use type compares
24#define ON_HSORT_GT(A,B) *A > *B
25#define ON_HSORT_GT_TMP(A) *A > tmp
26#endif
27
28#if defined(ON_SORT_TEMPLATE_USE_MEMCPY)
29#define ON_HSORT_TO_TMP(A) memcpy(&tmp,A,sizeof(tmp))
30#define ON_HSORT_FROM_TMP(A) memcpy(A,&tmp,sizeof(tmp))
31#define ON_HSORT_COPY(dst,src) memcpy(dst,src,sizeof(tmp))
32#else
33#define ON_HSORT_TO_TMP(A) tmp = *A
34#define ON_HSORT_FROM_TMP(A) *A = tmp
35#define ON_HSORT_COPY(dst,src) *dst = *src
36#endif
37
38#if defined(ON_SORT_TEMPLATE_STATIC_FUNCTION)
39static
40#endif
41void
42ON_HSORT_FNAME( ON_SORT_TEMPLATE_TYPE* base, std::size_t nel )
43{
44 std::size_t i_end,k,i,j;
45 ON_SORT_TEMPLATE_TYPE* e_end;
46 ON_SORT_TEMPLATE_TYPE* e_i;
47 ON_SORT_TEMPLATE_TYPE* e_j;
48 ON_SORT_TEMPLATE_TYPE tmp;
49
50 if (0 == base || nel < 2)
51 return;
52
53 k = nel >> 1;
54 i_end = nel-1;
55 e_end = base + i_end;
56 for (;;)
57 {
58 if (k)
59 {
60 --k;
61 ON_HSORT_TO_TMP((base+k)); /* e_tmp = e[k]; */
62 }
63 else
64 {
65 ON_HSORT_TO_TMP(e_end); /* e_tmp = e[i_end]; */
66 ON_HSORT_COPY(e_end,base); /* e[i_end] = e[0]; */
67 if (!(--i_end))
68 {
69 ON_HSORT_FROM_TMP(base); /* e[0] = e_tmp; */
70 break;
71 }
72 e_end--;
73 }
74
75 i = k;
76 j = (k<<1) + 1;
77 e_i = base + i;
78 while (j <= i_end)
79 {
80 e_j = base + j;
81 if (j < i_end && ON_HSORT_GT((e_j+1),e_j) /*e[j] < e[j + 1] */)
82 {
83 j++;
84 e_j++;
85 }
86 if (ON_HSORT_GT_TMP(e_j) /* tmp < e[j] */)
87 {
88 ON_HSORT_COPY(e_i,e_j); /* e[i] = e[j]; */
89 i = j;
90 e_i = e_j;
91 j = (j<<1) + 1;
92 }
93 else
94 j = i_end + 1;
95 }
96
97 ON_HSORT_FROM_TMP(e_i); /* e[i] = e_tmp; */
98 }
99}
100
101#undef ON_HSORT_GT
102#undef ON_HSORT_GT_TMP
103#undef ON_HSORT_TO_TMP
104#undef ON_HSORT_FROM_TMP
105#undef ON_HSORT_COPY
106#undef ON_HSORT_FROM_TMP