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