Mercurial > repos > lsong10 > psiclass

comparison PsiCLASS-1.0.2/samtools-0.1.19/ksort.h @ 0:903fc43d6227 draft default tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Uploaded
author lsong10
date Fri, 26 Mar 2021 16:52:45 +0000
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:903fc43d6227
1 /* The MIT License
2
3 Copyright (c) 2008 Genome Research Ltd (GRL).
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 /* Contact: Heng Li <lh3@sanger.ac.uk> */
27
28 /*
29 2012-12-11 (0.1.4):
30
31 * Defined __ks_insertsort_##name as static to compile with C99.
32
33 2008-11-16 (0.1.4):
34
35 * Fixed a bug in introsort() that happens in rare cases.
36
37 2008-11-05 (0.1.3):
38
39 * Fixed a bug in introsort() for complex comparisons.
40
41 * Fixed a bug in mergesort(). The previous version is not stable.
42
43 2008-09-15 (0.1.2):
44
45 * Accelerated introsort. On my Mac (not on another Linux machine),
46 my implementation is as fast as std::sort on random input.
47
48 * Added combsort and in introsort, switch to combsort if the
49 recursion is too deep.
50
51 2008-09-13 (0.1.1):
52
53 * Added k-small algorithm
54
55 2008-09-05 (0.1.0):
56
57 * Initial version
58
59 */
60
61 #ifndef AC_KSORT_H
62 #define AC_KSORT_H
63
64 #include <stdlib.h>
65 #include <string.h>
66
67 typedef struct {
68 void *left, *right;
69 int depth;
70 } ks_isort_stack_t;
71
72 #define KSORT_SWAP(type_t, a, b) { register type_t t=(a); (a)=(b); (b)=t; }
73
74 #define KSORT_INIT(name, type_t, __sort_lt) \
75 void ks_mergesort_##name(size_t n, type_t array[], type_t temp[]) \
76 { \
77 type_t *a2[2], *a, *b; \
78 int curr, shift; \
79 \
80 a2[0] = array; \
81 a2[1] = temp? temp : (type_t*)malloc(sizeof(type_t) * n); \
82 for (curr = 0, shift = 0; (1ul<<shift) < n; ++shift) { \
83 a = a2[curr]; b = a2[1-curr]; \
84 if (shift == 0) { \
85 type_t *p = b, *i, *eb = a + n; \
86 for (i = a; i < eb; i += 2) { \
87 if (i == eb - 1) *p++ = *i; \
88 else { \
89 if (__sort_lt(*(i+1), *i)) { \
90 *p++ = *(i+1); *p++ = *i; \
91 } else { \
92 *p++ = *i; *p++ = *(i+1); \
93 } \
94 } \
95 } \
96 } else { \
97 size_t i, step = 1ul<<shift; \
98 for (i = 0; i < n; i += step<<1) { \
99 type_t *p, *j, *k, *ea, *eb; \
100 if (n < i + step) { \
101 ea = a + n; eb = a; \
102 } else { \
103 ea = a + i + step; \
104 eb = a + (n < i + (step<<1)? n : i + (step<<1)); \
105 } \
106 j = a + i; k = a + i + step; p = b + i; \
107 while (j < ea && k < eb) { \
108 if (__sort_lt(*k, *j)) *p++ = *k++; \
109 else *p++ = *j++; \
110 } \
111 while (j < ea) *p++ = *j++; \
112 while (k < eb) *p++ = *k++; \
113 } \
114 } \
115 curr = 1 - curr; \
116 } \
117 if (curr == 1) { \
118 type_t *p = a2[0], *i = a2[1], *eb = array + n; \
119 for (; p < eb; ++i) *p++ = *i; \
120 } \
121 if (temp == 0) free(a2[1]); \
122 } \
123 void ks_heapadjust_##name(size_t i, size_t n, type_t l[]) \
124 { \
125 size_t k = i; \
126 type_t tmp = l[i]; \
127 while ((k = (k << 1) + 1) < n) { \
128 if (k != n - 1 && __sort_lt(l[k], l[k+1])) ++k; \
129 if (__sort_lt(l[k], tmp)) break; \
130 l[i] = l[k]; i = k; \
131 } \
132 l[i] = tmp; \
133 } \
134 void ks_heapmake_##name(size_t lsize, type_t l[]) \
135 { \
136 size_t i; \
137 for (i = (lsize >> 1) - 1; i != (size_t)(-1); --i) \
138 ks_heapadjust_##name(i, lsize, l); \
139 } \
140 void ks_heapsort_##name(size_t lsize, type_t l[]) \
141 { \
142 size_t i; \
143 for (i = lsize - 1; i > 0; --i) { \
144 type_t tmp; \
145 tmp = *l; *l = l[i]; l[i] = tmp; ks_heapadjust_##name(0, i, l); \
146 } \
147 } \
148 static inline void __ks_insertsort_##name(type_t *s, type_t *t) \
149 { \
150 type_t *i, *j, swap_tmp; \
151 for (i = s + 1; i < t; ++i) \
152 for (j = i; j > s && __sort_lt(*j, *(j-1)); --j) { \
153 swap_tmp = *j; *j = *(j-1); *(j-1) = swap_tmp; \
154 } \
155 } \
156 void ks_combsort_##name(size_t n, type_t a[]) \
157 { \
158 const double shrink_factor = 1.2473309501039786540366528676643; \
159 int do_swap; \
160 size_t gap = n; \
161 type_t tmp, *i, *j; \
162 do { \
163 if (gap > 2) { \
164 gap = (size_t)(gap / shrink_factor); \
165 if (gap == 9 || gap == 10) gap = 11; \
166 } \
167 do_swap = 0; \
168 for (i = a; i < a + n - gap; ++i) { \
169 j = i + gap; \
170 if (__sort_lt(*j, *i)) { \
171 tmp = *i; *i = *j; *j = tmp; \
172 do_swap = 1; \
173 } \
174 } \
175 } while (do_swap || gap > 2); \
176 if (gap != 1) __ks_insertsort_##name(a, a + n); \
177 } \
178 void ks_introsort_##name(size_t n, type_t a[]) \
179 { \
180 int d; \
181 ks_isort_stack_t *top, *stack; \
182 type_t rp, swap_tmp; \
183 type_t *s, *t, *i, *j, *k; \
184 \
185 if (n < 1) return; \
186 else if (n == 2) { \
187 if (__sort_lt(a[1], a[0])) { swap_tmp = a[0]; a[0] = a[1]; a[1] = swap_tmp; } \
188 return; \
189 } \
190 for (d = 2; 1ul<<d < n; ++d); \
191 stack = (ks_isort_stack_t*)malloc(sizeof(ks_isort_stack_t) * ((sizeof(size_t)*d)+2)); \
192 top = stack; s = a; t = a + (n-1); d <<= 1; \
193 while (1) { \
194 if (s < t) { \
195 if (--d == 0) { \
196 ks_combsort_##name(t - s + 1, s); \
197 t = s; \
198 continue; \
199 } \
200 i = s; j = t; k = i + ((j-i)>>1) + 1; \
201 if (__sort_lt(*k, *i)) { \
202 if (__sort_lt(*k, *j)) k = j; \
203 } else k = __sort_lt(*j, *i)? i : j; \
204 rp = *k; \
205 if (k != t) { swap_tmp = *k; *k = *t; *t = swap_tmp; } \
206 for (;;) { \
207 do ++i; while (__sort_lt(*i, rp)); \
208 do --j; while (i <= j && __sort_lt(rp, *j)); \
209 if (j <= i) break; \
210 swap_tmp = *i; *i = *j; *j = swap_tmp; \
211 } \
212 swap_tmp = *i; *i = *t; *t = swap_tmp; \
213 if (i-s > t-i) { \
214 if (i-s > 16) { top->left = s; top->right = i-1; top->depth = d; ++top; } \
215 s = t-i > 16? i+1 : t; \
216 } else { \
217 if (t-i > 16) { top->left = i+1; top->right = t; top->depth = d; ++top; } \
218 t = i-s > 16? i-1 : s; \
219 } \
220 } else { \
221 if (top == stack) { \
222 free(stack); \
223 __ks_insertsort_##name(a, a+n); \
224 return; \
225 } else { --top; s = (type_t*)top->left; t = (type_t*)top->right; d = top->depth; } \
226 } \
227 } \
228 } \
229 /* This function is adapted from: http://ndevilla.free.fr/median/ */ \
230 /* 0 <= kk < n */ \
231 type_t ks_ksmall_##name(size_t n, type_t arr[], size_t kk) \
232 { \
233 type_t *low, *high, *k, *ll, *hh, *mid; \
234 low = arr; high = arr + n - 1; k = arr + kk; \
235 for (;;) { \
236 if (high <= low) return *k; \
237 if (high == low + 1) { \
238 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \
239 return *k; \
240 } \
241 mid = low + (high - low) / 2; \
242 if (__sort_lt(*high, *mid)) KSORT_SWAP(type_t, *mid, *high); \
243 if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \
244 if (__sort_lt(*low, *mid)) KSORT_SWAP(type_t, *mid, *low); \
245 KSORT_SWAP(type_t, *mid, *(low+1)); \
246 ll = low + 1; hh = high; \
247 for (;;) { \
248 do ++ll; while (__sort_lt(*ll, *low)); \
249 do --hh; while (__sort_lt(*low, *hh)); \
250 if (hh < ll) break; \
251 KSORT_SWAP(type_t, *ll, *hh); \
252 } \
253 KSORT_SWAP(type_t, *low, *hh); \
254 if (hh <= k) low = ll; \
255 if (hh >= k) high = hh - 1; \
256 } \
257 } \
258 void ks_shuffle_##name(size_t n, type_t a[]) \
259 { \
260 int i, j; \
261 for (i = n; i > 1; --i) { \
262 type_t tmp; \
263 j = (int)(drand48() * i); \
264 tmp = a[j]; a[j] = a[i-1]; a[i-1] = tmp; \
265 } \
266 }
267
268 #define ks_mergesort(name, n, a, t) ks_mergesort_##name(n, a, t)
269 #define ks_introsort(name, n, a) ks_introsort_##name(n, a)
270 #define ks_combsort(name, n, a) ks_combsort_##name(n, a)
271 #define ks_heapsort(name, n, a) ks_heapsort_##name(n, a)
272 #define ks_heapmake(name, n, a) ks_heapmake_##name(n, a)
273 #define ks_heapadjust(name, i, n, a) ks_heapadjust_##name(i, n, a)
274 #define ks_ksmall(name, n, a, k) ks_ksmall_##name(n, a, k)
275 #define ks_shuffle(name, n, a) ks_shuffle_##name(n, a)
276
277 #define ks_lt_generic(a, b) ((a) < (b))
278 #define ks_lt_str(a, b) (strcmp((a), (b)) < 0)
279
280 typedef const char *ksstr_t;
281
282 #define KSORT_INIT_GENERIC(type_t) KSORT_INIT(type_t, type_t, ks_lt_generic)
283 #define KSORT_INIT_STR KSORT_INIT(str, ksstr_t, ks_lt_str)
284
285 #endif