Mercurial > repos > siyuan > prada
comparison pyPRADA_1.2/tools/bwa-0.5.7-mh/ksort.h @ 0:acc2ca1a3ba4
Uploaded
author | siyuan |
---|---|
date | Thu, 20 Feb 2014 00:44:58 -0500 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:acc2ca1a3ba4 |
---|---|
1 /* The MIT License | |
2 | |
3 Copyright (c) 2008, by Attractive Chaos <attractivechaos@aol.co.uk> | |
4 | |
5 Permission is hereby granted, free of charge, to any person obtaining | |
6 a copy of this software and associated documentation files (the | |
7 "Software"), to deal in the Software without restriction, including | |
8 without limitation the rights to use, copy, modify, merge, publish, | |
9 distribute, sublicense, and/or sell copies of the Software, and to | |
10 permit persons to whom the Software is furnished to do so, subject to | |
11 the following conditions: | |
12 | |
13 The above copyright notice and this permission notice shall be | |
14 included in all copies or substantial portions of the Software. | |
15 | |
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | |
17 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF | |
18 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND | |
19 NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS | |
20 BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN | |
21 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | |
22 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | |
23 SOFTWARE. | |
24 */ | |
25 | |
26 /* | |
27 2008-11-16 (0.1.4): | |
28 | |
29 * Fixed a bug in introsort() that happens in rare cases. | |
30 | |
31 2008-11-05 (0.1.3): | |
32 | |
33 * Fixed a bug in introsort() for complex comparisons. | |
34 | |
35 * Fixed a bug in mergesort(). The previous version is not stable. | |
36 | |
37 2008-09-15 (0.1.2): | |
38 | |
39 * Accelerated introsort. On my Mac (not on another Linux machine), | |
40 my implementation is as fast as std::sort on random input. | |
41 | |
42 * Added combsort and in introsort, switch to combsort if the | |
43 recursion is too deep. | |
44 | |
45 2008-09-13 (0.1.1): | |
46 | |
47 * Added k-small algorithm | |
48 | |
49 2008-09-05 (0.1.0): | |
50 | |
51 * Initial version | |
52 | |
53 */ | |
54 | |
55 #ifndef AC_KSORT_H | |
56 #define AC_KSORT_H | |
57 | |
58 #include <stdlib.h> | |
59 #include <string.h> | |
60 | |
61 typedef struct { | |
62 void *left, *right; | |
63 int depth; | |
64 } ks_isort_stack_t; | |
65 | |
66 #define KSORT_SWAP(type_t, a, b) { register type_t t=(a); (a)=(b); (b)=t; } | |
67 | |
68 #define KSORT_INIT(name, type_t, __sort_lt) \ | |
69 void ks_mergesort_##name(size_t n, type_t array[], type_t temp[]) \ | |
70 { \ | |
71 type_t *a2[2], *a, *b; \ | |
72 int curr, shift; \ | |
73 \ | |
74 a2[0] = array; \ | |
75 a2[1] = temp? temp : (type_t*)malloc(sizeof(type_t) * n); \ | |
76 for (curr = 0, shift = 0; (1ul<<shift) < n; ++shift) { \ | |
77 a = a2[curr]; b = a2[1-curr]; \ | |
78 if (shift == 0) { \ | |
79 type_t *p = b, *i, *eb = a + n; \ | |
80 for (i = a; i < eb; i += 2) { \ | |
81 if (i == eb - 1) *p++ = *i; \ | |
82 else { \ | |
83 if (__sort_lt(*(i+1), *i)) { \ | |
84 *p++ = *(i+1); *p++ = *i; \ | |
85 } else { \ | |
86 *p++ = *i; *p++ = *(i+1); \ | |
87 } \ | |
88 } \ | |
89 } \ | |
90 } else { \ | |
91 size_t i, step = 1ul<<shift; \ | |
92 for (i = 0; i < n; i += step<<1) { \ | |
93 type_t *p, *j, *k, *ea, *eb; \ | |
94 if (n < i + step) { \ | |
95 ea = a + n; eb = a; \ | |
96 } else { \ | |
97 ea = a + i + step; \ | |
98 eb = a + (n < i + (step<<1)? n : i + (step<<1)); \ | |
99 } \ | |
100 j = a + i; k = a + i + step; p = b + i; \ | |
101 while (j < ea && k < eb) { \ | |
102 if (__sort_lt(*k, *j)) *p++ = *k++; \ | |
103 else *p++ = *j++; \ | |
104 } \ | |
105 while (j < ea) *p++ = *j++; \ | |
106 while (k < eb) *p++ = *k++; \ | |
107 } \ | |
108 } \ | |
109 curr = 1 - curr; \ | |
110 } \ | |
111 if (curr == 1) { \ | |
112 type_t *p = a2[0], *i = a2[1], *eb = array + n; \ | |
113 for (; p < eb; ++i) *p++ = *i; \ | |
114 } \ | |
115 if (temp == 0) free(a2[1]); \ | |
116 } \ | |
117 void ks_heapadjust_##name(size_t i, size_t n, type_t l[]) \ | |
118 { \ | |
119 size_t k = i; \ | |
120 type_t tmp = l[i]; \ | |
121 while ((k = (k << 1) + 1) < n) { \ | |
122 if (k != n - 1 && __sort_lt(l[k], l[k+1])) ++k; \ | |
123 if (__sort_lt(l[k], tmp)) break; \ | |
124 l[i] = l[k]; i = k; \ | |
125 } \ | |
126 l[i] = tmp; \ | |
127 } \ | |
128 void ks_heapmake_##name(size_t lsize, type_t l[]) \ | |
129 { \ | |
130 size_t i; \ | |
131 for (i = (lsize >> 1) - 1; i != (size_t)(-1); --i) \ | |
132 ks_heapadjust_##name(i, lsize, l); \ | |
133 } \ | |
134 void ks_heapsort_##name(size_t lsize, type_t l[]) \ | |
135 { \ | |
136 size_t i; \ | |
137 for (i = lsize - 1; i > 0; --i) { \ | |
138 type_t tmp; \ | |
139 tmp = *l; *l = l[i]; l[i] = tmp; ks_heapadjust_##name(0, i, l); \ | |
140 } \ | |
141 } \ | |
142 inline void __ks_insertsort_##name(type_t *s, type_t *t) \ | |
143 { \ | |
144 type_t *i, *j, swap_tmp; \ | |
145 for (i = s + 1; i < t; ++i) \ | |
146 for (j = i; j > s && __sort_lt(*j, *(j-1)); --j) { \ | |
147 swap_tmp = *j; *j = *(j-1); *(j-1) = swap_tmp; \ | |
148 } \ | |
149 } \ | |
150 void ks_combsort_##name(size_t n, type_t a[]) \ | |
151 { \ | |
152 const double shrink_factor = 1.2473309501039786540366528676643; \ | |
153 int do_swap; \ | |
154 size_t gap = n; \ | |
155 type_t tmp, *i, *j; \ | |
156 do { \ | |
157 if (gap > 2) { \ | |
158 gap = (size_t)(gap / shrink_factor); \ | |
159 if (gap == 9 || gap == 10) gap = 11; \ | |
160 } \ | |
161 do_swap = 0; \ | |
162 for (i = a; i < a + n - gap; ++i) { \ | |
163 j = i + gap; \ | |
164 if (__sort_lt(*j, *i)) { \ | |
165 tmp = *i; *i = *j; *j = tmp; \ | |
166 do_swap = 1; \ | |
167 } \ | |
168 } \ | |
169 } while (do_swap || gap > 2); \ | |
170 if (gap != 1) __ks_insertsort_##name(a, a + n); \ | |
171 } \ | |
172 void ks_introsort_##name(size_t n, type_t a[]) \ | |
173 { \ | |
174 int d; \ | |
175 ks_isort_stack_t *top, *stack; \ | |
176 type_t rp, swap_tmp; \ | |
177 type_t *s, *t, *i, *j, *k; \ | |
178 \ | |
179 if (n < 1) return; \ | |
180 else if (n == 2) { \ | |
181 if (__sort_lt(a[1], a[0])) { swap_tmp = a[0]; a[0] = a[1]; a[1] = swap_tmp; } \ | |
182 return; \ | |
183 } \ | |
184 for (d = 2; 1ul<<d < n; ++d); \ | |
185 stack = (ks_isort_stack_t*)malloc(sizeof(ks_isort_stack_t) * ((sizeof(size_t)*d)+2)); \ | |
186 top = stack; s = a; t = a + (n-1); d <<= 1; \ | |
187 while (1) { \ | |
188 if (s < t) { \ | |
189 if (--d == 0) { \ | |
190 ks_combsort_##name(t - s + 1, s); \ | |
191 t = s; \ | |
192 continue; \ | |
193 } \ | |
194 i = s; j = t; k = i + ((j-i)>>1) + 1; \ | |
195 if (__sort_lt(*k, *i)) { \ | |
196 if (__sort_lt(*k, *j)) k = j; \ | |
197 } else k = __sort_lt(*j, *i)? i : j; \ | |
198 rp = *k; \ | |
199 if (k != t) { swap_tmp = *k; *k = *t; *t = swap_tmp; } \ | |
200 for (;;) { \ | |
201 do ++i; while (__sort_lt(*i, rp)); \ | |
202 do --j; while (i <= j && __sort_lt(rp, *j)); \ | |
203 if (j <= i) break; \ | |
204 swap_tmp = *i; *i = *j; *j = swap_tmp; \ | |
205 } \ | |
206 swap_tmp = *i; *i = *t; *t = swap_tmp; \ | |
207 if (i-s > t-i) { \ | |
208 if (i-s > 16) { top->left = s; top->right = i-1; top->depth = d; ++top; } \ | |
209 s = t-i > 16? i+1 : t; \ | |
210 } else { \ | |
211 if (t-i > 16) { top->left = i+1; top->right = t; top->depth = d; ++top; } \ | |
212 t = i-s > 16? i-1 : s; \ | |
213 } \ | |
214 } else { \ | |
215 if (top == stack) { \ | |
216 free(stack); \ | |
217 __ks_insertsort_##name(a, a+n); \ | |
218 return; \ | |
219 } else { --top; s = (type_t*)top->left; t = (type_t*)top->right; d = top->depth; } \ | |
220 } \ | |
221 } \ | |
222 } \ | |
223 /* This function is adapted from: http://ndevilla.free.fr/median/ */ \ | |
224 /* 0 <= kk < n */ \ | |
225 type_t ks_ksmall_##name(size_t n, type_t arr[], size_t kk) \ | |
226 { \ | |
227 type_t *low, *high, *k, *ll, *hh, *mid; \ | |
228 low = arr; high = arr + n - 1; k = arr + kk; \ | |
229 for (;;) { \ | |
230 if (high <= low) return *k; \ | |
231 if (high == low + 1) { \ | |
232 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \ | |
233 return *k; \ | |
234 } \ | |
235 mid = low + (high - low) / 2; \ | |
236 if (__sort_lt(*high, *mid)) KSORT_SWAP(type_t, *mid, *high); \ | |
237 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \ | |
238 if (__sort_lt(*low, *mid)) KSORT_SWAP(type_t, *mid, *low); \ | |
239 KSORT_SWAP(type_t, *mid, *(low+1)); \ | |
240 ll = low + 1; hh = high; \ | |
241 for (;;) { \ | |
242 do ++ll; while (__sort_lt(*ll, *low)); \ | |
243 do --hh; while (__sort_lt(*low, *hh)); \ | |
244 if (hh < ll) break; \ | |
245 KSORT_SWAP(type_t, *ll, *hh); \ | |
246 } \ | |
247 KSORT_SWAP(type_t, *low, *hh); \ | |
248 if (hh <= k) low = ll; \ | |
249 if (hh >= k) high = hh - 1; \ | |
250 } \ | |
251 } | |
252 | |
253 #define ks_mergesort(name, n, a, t) ks_mergesort_##name(n, a, t) | |
254 #define ks_introsort(name, n, a) ks_introsort_##name(n, a) | |
255 #define ks_combsort(name, n, a) ks_combsort_##name(n, a) | |
256 #define ks_heapsort(name, n, a) ks_heapsort_##name(n, a) | |
257 #define ks_heapmake(name, n, a) ks_heapmake_##name(n, a) | |
258 #define ks_heapadjust(name, i, n, a) ks_heapadjust_##name(i, n, a) | |
259 #define ks_ksmall(name, n, a, k) ks_ksmall_##name(n, a, k) | |
260 | |
261 #define ks_lt_generic(a, b) ((a) < (b)) | |
262 #define ks_lt_str(a, b) (strcmp((a), (b)) < 0) | |
263 | |
264 typedef const char *ksstr_t; | |
265 | |
266 #define KSORT_INIT_GENERIC(type_t) KSORT_INIT(type_t, type_t, ks_lt_generic) | |
267 #define KSORT_INIT_STR KSORT_INIT(str, ksstr_t, ks_lt_str) | |
268 | |
269 #endif |