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 <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

Generated on Thu Jun 4 10:30:00 2009 for Stxxl by  doxygen 1.4.7