• Main Page
  • Related Pages
  • Modules
  • Namespaces
  • Classes
  • Files
  • Examples
  • File List

intksort.h

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 <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     // reset buckets
00029     std::fill(bucket, bucket + K, 0);
00030 
00031     // count occupancies
00032     for (type_key * p = a; p < aEnd; p++)
00033     {
00034         int_type i = (p->key - offset) >> shift;
00035         /*
00036         if (!(i < K && i >= 0))
00037         {
00038             STXXL_ERRMSG("i: " << i);
00039             abort();
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 // distribute input a to output b using bucket for the starting indices
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         {                       // b , c < a
00092             if (b < c)
00093             {                   // b < c < a
00094                 temp = a;
00095                 a = b;
00096                 b = c;
00097                 c = temp;
00098             }
00099             else
00100             {                   // c <=b < a
00101                 std::swap(c, a);
00102             }
00103         }
00104         else
00105         {                       // b < a <=c
00106             std::swap(a, b);
00107         }
00108     }
00109     else
00110     {                           // a <=b
00111         if (c < a)
00112         {                       // c < a <=b
00113             temp = a;
00114             a = c;
00115             c = b;
00116             b = temp;
00117         }
00118         else
00119         {                       // a <=b , c
00120             if (c < b)
00121             {                   // a <=c < b
00122                 std::swap(b, c);
00123             }
00124         }
00125     }
00126     // Assert1 (!(b < a) && !(c < b));
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);                // a < b ; c < d
00136     if (c < a)
00137     {                           // c minimal, a < b
00138         if (d < a)
00139         {                       // c < d < a < b
00140             std::swap(a, c);
00141             std::swap(b, d);
00142         }
00143         else
00144         {                       // c < a < {db}
00145             if (d < b)
00146             {                   // c < a < d < b
00147                 T temp = a;
00148                 a = c;
00149                 c = d;
00150                 d = b;
00151                 b = temp;
00152             }
00153             else
00154             {                   // c < a < b < d
00155                 T temp = a;
00156                 a = c;
00157                 c = b;
00158                 b = temp;
00159             }
00160         }
00161     }
00162     else
00163     {                           // a minimal ; c < d
00164         if (c < b)
00165         {                       // c < (bd)
00166             if (d < b)
00167             {                   // c < d < b
00168                 T temp = b;
00169                 b = c;
00170                 c = d;
00171                 d = temp;
00172             }
00173             else
00174             {                   // a < c < b < d
00175                 std::swap(b, c);
00176             }
00177         }                       // else sorted
00178     }
00179     //Assert1 (!(b < a) && !(c < b) & !(d < c));
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     }                           // a < d < e, a < b
00194     if (d < c)
00195     {
00196         std::swap(c, d);        // a minimal, c < {de}
00197         sort2(d, e);
00198     }
00199     else
00200     {                           // a<b, a<d<e, c<d<e
00201         sort2(a, c);
00202     }                           // a min, c < d < e
00203     // insert b int cde by binary search
00204     if (d < b)
00205     {                           // c < d < {be}
00206         if (e < b)
00207         {                       // c < d < e < b
00208             T temp = b;
00209             b = c;
00210             c = d;
00211             d = e;
00212             e = temp;
00213         }
00214         else
00215         {                       // c < d < b < e
00216             T temp = b;
00217             b = c;
00218             c = d;
00219             d = temp;
00220         }
00221     }
00222     else
00223     {                           // {cb} <=d < e
00224         sort2(b, c);
00225     }
00226     //Assert1 (!(b < a) && !(c < b) & !(d < c) & !(e < d));
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         // Invariant a..p-1 is sorted;
00238         T t = *p;
00239         if (t < *a)
00240         {   // new minimum
00241             // move stuff to the right
00242             for (pp = p; pp != a; pp--)
00243             {
00244                 *pp = *(pp - 1);
00245             }
00246             *pp = t;
00247         }
00248         else
00249         {
00250             // now we can use *a as a sentinel
00251             for (pp = p; t < *(pp - 1); pp--)
00252             {
00253                 *pp = *(pp - 1);
00254             }
00255             *pp = t;
00256         }
00257     }
00258 }
00259 
00260 // sort each bucket
00261 // bucket[i] is an index one off to the right from
00262 // the end of the i-th bucket
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 // do a single level MDS radix sort
00312 // using bucket[0..K-1] as a counter array
00313 // and using (key(x) - offset) >> shift to index buckets.
00314 // and using (key(x) - offset) >> shift to index buckets.
00315 // the input comes from a..aEnd-1
00316 // the output goes to b
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++) // count & create references
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++) // count & create references
00349     {
00350         out->ptr = p;
00351         typename type::key_type key = keyobj(*p);
00352         int_type ibucket = (key - offset) >> shift;
00353         /*
00354         if (!(ibucket < K && ibucket >= 0))
00355         {
00356             STXXL_ERRMSG("ibucket: " << ibucket << " K:" << K);
00357             abort();
00358         }
00359         */
00360         out->key = key;
00361         bucket[ibucket]++;
00362     }
00363 }
00364 
00365 __STXXL_END_NAMESPACE
00366 
00367 #endif // !STXXL_INTKSORT_HEADER

Generated on Sun Oct 17 2010 06:13:43 for Stxxl by  doxygen 1.7.1