Mercurial > repos > siyuan > prada

comparison pyPRADA_1.2/tools/bwa-0.5.7-mh/ksort.h @ 0:acc2ca1a3ba4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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