Stxxl  1.2.1
intksort.h
1 /***************************************************************************
2  * include/stxxl/bits/algo/intksort.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002 Peter Sanders <sanders@mpi-sb.mpg.de>
7  *
8  * Distributed under the Boost Software License, Version 1.0.
9  * (See accompanying file LICENSE_1_0.txt or copy at
10  * http://www.boost.org/LICENSE_1_0.txt)
11  **************************************************************************/
12 
13 #ifndef STXXL_INTKSORT_HEADER
14 #define STXXL_INTKSORT_HEADER
15 
16 #include <stxxl/bits/common/utils.h>
17 
18 
19 __STXXL_BEGIN_NAMESPACE
20 
21 template <typename type_key>
22 static void
23 count(type_key * a, type_key * aEnd, int_type * bucket, int_type K, typename type_key::key_type offset,
24  unsigned shift)
25 {
26  // reset buckets
27  std::fill(bucket, bucket + K, 0);
28 
29  // count occupancies
30  for (type_key * p = a; p < aEnd; p++)
31  {
32  int_type i = (p->key - offset) >> shift;
33  /*
34  if (!(i < K && i >= 0))
35  {
36  STXXL_ERRMSG("i: " << i);
37  abort();
38  }
39  */
40  bucket[i]++;
41  }
42 }
43 
44 
45 static void
46 exclusive_prefix_sum(int_type * bucket, int_type K)
47 {
48  int_type sum = 0;
49  for (int_type i = 0; i < K; i++)
50  {
51  int_type current = bucket[i];
52  bucket[i] = sum;
53  sum += current;
54  }
55 }
56 
57 
58 // distribute input a to output b using bucket for the starting indices
59 template <typename type_key>
60 static void
61 classify(type_key * a, type_key * aEnd, type_key * b, int_type * bucket, typename type_key::key_type offset, unsigned shift)
62 {
63  for (type_key * p = a; p < aEnd; p++)
64  {
65  int_type i = (p->key - offset) >> shift;
66  int_type bi = bucket[i];
67  b[bi] = *p;
68  bucket[i] = bi + 1;
69  }
70 }
71 
72 
73 template <class T>
74 inline void
75 sort2(T & a, T & b)
76 {
77  if (b < a)
78  std::swap(a, b);
79 }
80 
81 template <class T>
82 inline void
83 sort3(T & a, T & b, T & c)
84 {
85  T temp;
86  if (b < a)
87  {
88  if (c < a)
89  { // b , c < a
90  if (b < c)
91  { // b < c < a
92  temp = a;
93  a = b;
94  b = c;
95  c = temp;
96  }
97  else
98  { // c <=b < a
99  std::swap(c, a);
100  }
101  }
102  else
103  { // b < a <=c
104  std::swap(a, b);
105  }
106  }
107  else
108  { // a <=b
109  if (c < a)
110  { // c < a <=b
111  temp = a;
112  a = c;
113  c = b;
114  b = temp;
115  }
116  else
117  { // a <=b , c
118  if (c < b)
119  { // a <=c < b
120  std::swap(b, c);
121  }
122  }
123  }
124  // Assert1 (!(b < a) && !(c < b));
125 }
126 
127 
128 template <class T>
129 inline void
130 sort4(T & a, T & b, T & c, T & d)
131 {
132  sort2(a, b);
133  sort2(c, d); // a < b ; c < d
134  if (c < a)
135  { // c minimal, a < b
136  if (d < a)
137  { // c < d < a < b
138  std::swap(a, c);
139  std::swap(b, d);
140  }
141  else
142  { // c < a < {db}
143  if (d < b)
144  { // c < a < d < b
145  T temp = a;
146  a = c;
147  c = d;
148  d = b;
149  b = temp;
150  }
151  else
152  { // c < a < b < d
153  T temp = a;
154  a = c;
155  c = b;
156  b = temp;
157  }
158  }
159  }
160  else
161  { // a minimal ; c < d
162  if (c < b)
163  { // c < (bd)
164  if (d < b)
165  { // c < d < b
166  T temp = b;
167  b = c;
168  c = d;
169  d = temp;
170  }
171  else
172  { // a < c < b < d
173  std::swap(b, c);
174  }
175  } // else sorted
176  }
177  //Assert1 (!(b < a) && !(c < b) & !(d < c));
178 }
179 
180 
181 template <class T>
182 inline void
183 sort5(T & a, T & b, T & c, T & d, T & e)
184 {
185  sort2(a, b);
186  sort2(d, e);
187  if (d < a)
188  {
189  std::swap(a, d);
190  std::swap(b, e);
191  } // a < d < e, a < b
192  if (d < c)
193  {
194  std::swap(c, d); // a minimal, c < {de}
195  sort2(d, e);
196  }
197  else
198  { // a<b, a<d<e, c<d<e
199  sort2(a, c);
200  } // a min, c < d < e
201  // insert b int cde by binary search
202  if (d < b)
203  { // c < d < {be}
204  if (e < b)
205  { // c < d < e < b
206  T temp = b;
207  b = c;
208  c = d;
209  d = e;
210  e = temp;
211  }
212  else
213  { // c < d < b < e
214  T temp = b;
215  b = c;
216  c = d;
217  d = temp;
218  }
219  }
220  else
221  { // {cb} <=d < e
222  sort2(b, c);
223  }
224  //Assert1 (!(b < a) && !(c < b) & !(d < c) & !(e < d));
225 }
226 
227 
228 template <class T>
229 inline void
230 insertion_sort(T * a, T * aEnd)
231 {
232  T * pp;
233  for (T * p = a + 1; p < aEnd; p++)
234  {
235  // Invariant a..p-1 is sorted;
236  T t = *p;
237  if (t < *a)
238  { // new minimum
239  // move stuff to the right
240  for (pp = p; pp != a; pp--)
241  {
242  *pp = *(pp - 1);
243  }
244  *pp = t;
245  }
246  else
247  {
248  // now we can use *a as a sentinel
249  for (pp = p; t < *(pp - 1); pp--)
250  {
251  *pp = *(pp - 1);
252  }
253  *pp = t;
254  }
255  }
256 }
257 
258 // sort each bucket
259 // bucket[i] is an index one off to the right from
260 // the end of the i-th bucket
261 template <class T>
262 static void
263 cleanup(T * b, int_type * bucket, int_type K)
264 {
265  T * c = b;
266  for (int_type i = 0; i < K; i++)
267  {
268  T * cEnd = b + bucket[i];
269  switch (cEnd - c)
270  {
271  case 0:
272  break;
273  case 1:
274  break;
275  case 2:
276  sort2(c[0], c[1]);
277  break;
278  case 3:
279  sort3(c[0], c[1], c[2]);
280  break;
281  case 4:
282  sort4(c[0], c[1], c[2], c[3]);
283  break;
284  case 5:
285  //sort5(c[0], c[1], c[2], c[3], c[4]); break;
286  case 6:
287  case 7:
288  case 8:
289  case 9:
290  case 10:
291  case 11:
292  case 12:
293  case 13:
294  case 14:
295  case 15:
296  case 16:
297  insertion_sort(c, cEnd);
298  break;
299  default:
300  std::sort(c, cEnd);
301  }
302  c = cEnd;
303  }
304 }
305 
306 // do a single level MDS radix sort
307 // using bucket[0..K-1] as a counter array
308 // and using (key(x) - offset) >> shift to index buckets.
309 // and using (key(x) - offset) >> shift to index buckets.
310 // the input comes from a..aEnd-1
311 // the output goes to b
312 template <typename type_key>
313 void
314 l1sort(type_key * a,
315  type_key * aEnd,
316  type_key * b, int_type * bucket, int_type K, typename type_key::key_type offset, int shift)
317 {
318  count(a, aEnd, bucket, K, offset, shift);
319  exclusive_prefix_sum(bucket, K);
320  classify(a, aEnd, b, bucket, offset, shift);
321  cleanup(b, bucket, K);
322 }
323 
324 template <typename type, typename type_key, typename key_extractor>
325 void classify_block(type * begin, type * end, type_key * & out,
326  int_type * bucket, typename key_extractor::key_type offset, unsigned shift, key_extractor keyobj)
327 {
328  assert(shift < (sizeof(typename key_extractor::key_type) * 8 + 1));
329  for (type * p = begin; p < end; p++, out++) // count & create references
330  {
331  out->ptr = p;
332  typename key_extractor::key_type key = keyobj(*p);
333  int_type ibucket = (key - offset) >> shift;
334  out->key = key;
335  bucket[ibucket]++;
336  }
337 }
338 template <typename type, typename type_key, typename key_extractor>
339 void classify_block(type * begin, type * end, type_key * & out, int_type * bucket, typename type::key_type offset, unsigned shift,
340  const int_type K, key_extractor keyobj)
341 {
342  assert(shift < (sizeof(typename type::key_type) * 8 + 1));
343  for (type * p = begin; p < end; p++, out++) // count & create references
344  {
345  out->ptr = p;
346  typename type::key_type key = keyobj(*p);
347  int_type ibucket = (key - offset) >> shift;
348  /*
349  if (!(ibucket < K && ibucket >= 0))
350  {
351  STXXL_ERRMSG("ibucket: " << ibucket << " K:" << K);
352  abort();
353  }
354  */
355  out->key = key;
356  bucket[ibucket]++;
357  }
358 }
359 
360 __STXXL_END_NAMESPACE
361 
362 #endif // !STXXL_INTKSORT_HEADER