Stxxl 1.2.1
|
00001 /*************************************************************************** 00002 * include/stxxl/bits/algo/intksort.h 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2002 Peter Sanders <sanders@mpi-sb.mpg.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 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 // reset buckets 00027 std::fill(bucket, bucket + K, 0); 00028 00029 // count occupancies 00030 for (type_key * p = a; p < aEnd; p++) 00031 { 00032 int_type i = (p->key - offset) >> shift; 00033 /* 00034 if (!(i < K && i >= 0)) 00035 { 00036 STXXL_ERRMSG("i: " << i); 00037 abort(); 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 // distribute input a to output b using bucket for the starting indices 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 { // b , c < a 00090 if (b < c) 00091 { // b < c < a 00092 temp = a; 00093 a = b; 00094 b = c; 00095 c = temp; 00096 } 00097 else 00098 { // c <=b < a 00099 std::swap(c, a); 00100 } 00101 } 00102 else 00103 { // b < a <=c 00104 std::swap(a, b); 00105 } 00106 } 00107 else 00108 { // a <=b 00109 if (c < a) 00110 { // c < a <=b 00111 temp = a; 00112 a = c; 00113 c = b; 00114 b = temp; 00115 } 00116 else 00117 { // a <=b , c 00118 if (c < b) 00119 { // a <=c < b 00120 std::swap(b, c); 00121 } 00122 } 00123 } 00124 // Assert1 (!(b < a) && !(c < b)); 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); // a < b ; c < d 00134 if (c < a) 00135 { // c minimal, a < b 00136 if (d < a) 00137 { // c < d < a < b 00138 std::swap(a, c); 00139 std::swap(b, d); 00140 } 00141 else 00142 { // c < a < {db} 00143 if (d < b) 00144 { // c < a < d < b 00145 T temp = a; 00146 a = c; 00147 c = d; 00148 d = b; 00149 b = temp; 00150 } 00151 else 00152 { // c < a < b < d 00153 T temp = a; 00154 a = c; 00155 c = b; 00156 b = temp; 00157 } 00158 } 00159 } 00160 else 00161 { // a minimal ; c < d 00162 if (c < b) 00163 { // c < (bd) 00164 if (d < b) 00165 { // c < d < b 00166 T temp = b; 00167 b = c; 00168 c = d; 00169 d = temp; 00170 } 00171 else 00172 { // a < c < b < d 00173 std::swap(b, c); 00174 } 00175 } // else sorted 00176 } 00177 //Assert1 (!(b < a) && !(c < b) & !(d < c)); 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 } // a < d < e, a < b 00192 if (d < c) 00193 { 00194 std::swap(c, d); // a minimal, c < {de} 00195 sort2(d, e); 00196 } 00197 else 00198 { // a<b, a<d<e, c<d<e 00199 sort2(a, c); 00200 } // a min, c < d < e 00201 // insert b int cde by binary search 00202 if (d < b) 00203 { // c < d < {be} 00204 if (e < b) 00205 { // c < d < e < b 00206 T temp = b; 00207 b = c; 00208 c = d; 00209 d = e; 00210 e = temp; 00211 } 00212 else 00213 { // c < d < b < e 00214 T temp = b; 00215 b = c; 00216 c = d; 00217 d = temp; 00218 } 00219 } 00220 else 00221 { // {cb} <=d < e 00222 sort2(b, c); 00223 } 00224 //Assert1 (!(b < a) && !(c < b) & !(d < c) & !(e < d)); 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 // Invariant a..p-1 is sorted; 00236 T t = *p; 00237 if (t < *a) 00238 { // new minimum 00239 // move stuff to the right 00240 for (pp = p; pp != a; pp--) 00241 { 00242 *pp = *(pp - 1); 00243 } 00244 *pp = t; 00245 } 00246 else 00247 { 00248 // now we can use *a as a sentinel 00249 for (pp = p; t < *(pp - 1); pp--) 00250 { 00251 *pp = *(pp - 1); 00252 } 00253 *pp = t; 00254 } 00255 } 00256 } 00257 00258 // sort each bucket 00259 // bucket[i] is an index one off to the right from 00260 // the end of the i-th bucket 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 //sort5(c[0], c[1], c[2], c[3], c[4]); break; 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 // do a single level MDS radix sort 00307 // using bucket[0..K-1] as a counter array 00308 // and using (key(x) - offset) >> shift to index buckets. 00309 // and using (key(x) - offset) >> shift to index buckets. 00310 // the input comes from a..aEnd-1 00311 // the output goes to b 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++) // count & create references 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++) // count & create references 00344 { 00345 out->ptr = p; 00346 typename type::key_type key = keyobj(*p); 00347 int_type ibucket = (key - offset) >> shift; 00348 /* 00349 if (!(ibucket < K && ibucket >= 0)) 00350 { 00351 STXXL_ERRMSG("ibucket: " << ibucket << " K:" << K); 00352 abort(); 00353 } 00354 */ 00355 out->key = key; 00356 bucket[ibucket]++; 00357 } 00358 } 00359 00360 __STXXL_END_NAMESPACE 00361 00362 #endif // !STXXL_INTKSORT_HEADER