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