00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #ifndef STXXL_INTKSORT_HEADER
00014 #define STXXL_INTKSORT_HEADER
00015
00016 #include <algorithm>
00017 #include <cassert>
00018 #include <stxxl/bits/common/types.h>
00019
00020
00021 __STXXL_BEGIN_NAMESPACE
00022
00023 template <typename type_key>
00024 static void
00025 count(type_key * a, type_key * aEnd, int_type * bucket, int_type K, typename type_key::key_type offset,
00026 unsigned shift)
00027 {
00028
00029 std::fill(bucket, bucket + K, 0);
00030
00031
00032 for (type_key * p = a; p < aEnd; p++)
00033 {
00034 int_type i = (p->key - offset) >> shift;
00035
00036
00037
00038
00039
00040
00041
00042 bucket[i]++;
00043 }
00044 }
00045
00046
00047 static void
00048 exclusive_prefix_sum(int_type * bucket, int_type K)
00049 {
00050 int_type sum = 0;
00051 for (int_type i = 0; i < K; i++)
00052 {
00053 int_type current = bucket[i];
00054 bucket[i] = sum;
00055 sum += current;
00056 }
00057 }
00058
00059
00060
00061 template <typename type_key>
00062 static void
00063 classify(type_key * a, type_key * aEnd, type_key * b, int_type * bucket, typename type_key::key_type offset, unsigned shift)
00064 {
00065 for (type_key * p = a; p < aEnd; p++)
00066 {
00067 int_type i = (p->key - offset) >> shift;
00068 int_type bi = bucket[i];
00069 b[bi] = *p;
00070 bucket[i] = bi + 1;
00071 }
00072 }
00073
00074
00075 template <class T>
00076 inline void
00077 sort2(T & a, T & b)
00078 {
00079 if (b < a)
00080 std::swap(a, b);
00081 }
00082
00083 template <class T>
00084 inline void
00085 sort3(T & a, T & b, T & c)
00086 {
00087 T temp;
00088 if (b < a)
00089 {
00090 if (c < a)
00091 {
00092 if (b < c)
00093 {
00094 temp = a;
00095 a = b;
00096 b = c;
00097 c = temp;
00098 }
00099 else
00100 {
00101 std::swap(c, a);
00102 }
00103 }
00104 else
00105 {
00106 std::swap(a, b);
00107 }
00108 }
00109 else
00110 {
00111 if (c < a)
00112 {
00113 temp = a;
00114 a = c;
00115 c = b;
00116 b = temp;
00117 }
00118 else
00119 {
00120 if (c < b)
00121 {
00122 std::swap(b, c);
00123 }
00124 }
00125 }
00126
00127 }
00128
00129
00130 template <class T>
00131 inline void
00132 sort4(T & a, T & b, T & c, T & d)
00133 {
00134 sort2(a, b);
00135 sort2(c, d);
00136 if (c < a)
00137 {
00138 if (d < a)
00139 {
00140 std::swap(a, c);
00141 std::swap(b, d);
00142 }
00143 else
00144 {
00145 if (d < b)
00146 {
00147 T temp = a;
00148 a = c;
00149 c = d;
00150 d = b;
00151 b = temp;
00152 }
00153 else
00154 {
00155 T temp = a;
00156 a = c;
00157 c = b;
00158 b = temp;
00159 }
00160 }
00161 }
00162 else
00163 {
00164 if (c < b)
00165 {
00166 if (d < b)
00167 {
00168 T temp = b;
00169 b = c;
00170 c = d;
00171 d = temp;
00172 }
00173 else
00174 {
00175 std::swap(b, c);
00176 }
00177 }
00178 }
00179
00180 }
00181
00182
00183 template <class T>
00184 inline void
00185 sort5(T & a, T & b, T & c, T & d, T & e)
00186 {
00187 sort2(a, b);
00188 sort2(d, e);
00189 if (d < a)
00190 {
00191 std::swap(a, d);
00192 std::swap(b, e);
00193 }
00194 if (d < c)
00195 {
00196 std::swap(c, d);
00197 sort2(d, e);
00198 }
00199 else
00200 {
00201 sort2(a, c);
00202 }
00203
00204 if (d < b)
00205 {
00206 if (e < b)
00207 {
00208 T temp = b;
00209 b = c;
00210 c = d;
00211 d = e;
00212 e = temp;
00213 }
00214 else
00215 {
00216 T temp = b;
00217 b = c;
00218 c = d;
00219 d = temp;
00220 }
00221 }
00222 else
00223 {
00224 sort2(b, c);
00225 }
00226
00227 }
00228
00229
00230 template <class T>
00231 inline void
00232 insertion_sort(T * a, T * aEnd)
00233 {
00234 T * pp;
00235 for (T * p = a + 1; p < aEnd; p++)
00236 {
00237
00238 T t = *p;
00239 if (t < *a)
00240 {
00241
00242 for (pp = p; pp != a; pp--)
00243 {
00244 *pp = *(pp - 1);
00245 }
00246 *pp = t;
00247 }
00248 else
00249 {
00250
00251 for (pp = p; t < *(pp - 1); pp--)
00252 {
00253 *pp = *(pp - 1);
00254 }
00255 *pp = t;
00256 }
00257 }
00258 }
00259
00260
00261
00262
00263 template <class T>
00264 static void
00265 cleanup(T * b, int_type * bucket, int_type K)
00266 {
00267 T * c = b;
00268 for (int_type i = 0; i < K; i++)
00269 {
00270 T * cEnd = b + bucket[i];
00271 switch (cEnd - c)
00272 {
00273 case 0:
00274 break;
00275 case 1:
00276 break;
00277 case 2:
00278 sort2(c[0], c[1]);
00279 break;
00280 case 3:
00281 sort3(c[0], c[1], c[2]);
00282 break;
00283 case 4:
00284 sort4(c[0], c[1], c[2], c[3]);
00285 break;
00286 case 5:
00287 #if 0
00288 sort5(c[0], c[1], c[2], c[3], c[4]);
00289 break;
00290 #endif
00291 case 6:
00292 case 7:
00293 case 8:
00294 case 9:
00295 case 10:
00296 case 11:
00297 case 12:
00298 case 13:
00299 case 14:
00300 case 15:
00301 case 16:
00302 insertion_sort(c, cEnd);
00303 break;
00304 default:
00305 std::sort(c, cEnd);
00306 }
00307 c = cEnd;
00308 }
00309 }
00310
00311
00312
00313
00314
00315
00316
00317 template <typename type_key>
00318 void
00319 l1sort(type_key * a,
00320 type_key * aEnd,
00321 type_key * b, int_type * bucket, int_type K, typename type_key::key_type offset, int shift)
00322 {
00323 count(a, aEnd, bucket, K, offset, shift);
00324 exclusive_prefix_sum(bucket, K);
00325 classify(a, aEnd, b, bucket, offset, shift);
00326 cleanup(b, bucket, K);
00327 }
00328
00329 template <typename type, typename type_key, typename key_extractor>
00330 void classify_block(type * begin, type * end, type_key * & out,
00331 int_type * bucket, typename key_extractor::key_type offset, unsigned shift, key_extractor keyobj)
00332 {
00333 assert(shift < (sizeof(typename key_extractor::key_type) * 8 + 1));
00334 for (type * p = begin; p < end; p++, out++)
00335 {
00336 out->ptr = p;
00337 typename key_extractor::key_type key = keyobj(*p);
00338 int_type ibucket = (key - offset) >> shift;
00339 out->key = key;
00340 bucket[ibucket]++;
00341 }
00342 }
00343 template <typename type, typename type_key, typename key_extractor>
00344 void classify_block(type * begin, type * end, type_key * & out, int_type * bucket, typename type::key_type offset, unsigned shift,
00345 const int_type K, key_extractor keyobj)
00346 {
00347 assert(shift < (sizeof(typename type::key_type) * 8 + 1));
00348 for (type * p = begin; p < end; p++, out++)
00349 {
00350 out->ptr = p;
00351 typename type::key_type key = keyobj(*p);
00352 int_type ibucket = (key - offset) >> shift;
00353
00354
00355
00356
00357
00358
00359
00360 out->key = key;
00361 bucket[ibucket]++;
00362 }
00363 }
00364
00365 __STXXL_END_NAMESPACE
00366
00367 #endif // !STXXL_INTKSORT_HEADER