dcover/partition.hpp

   1 /*
   2  * partition.hpp
   3  *
   4  * Copyright 2003 Max-Planck-Institut fuer Informatik
   5  *
   6  */
   7
   8 //======================================================================
   9 // A collection of flexible, generic, STL-like algorithm components
  10 // for comparison-based distribution (i.e., quicksort-like) sorting.
  11 //======================================================================
  12
  13 #ifndef PARTITION_HPP
  14 #define PARTITION_HPP
  15
  16 #include <algorithm>
  17 #include <utility>
  18 #include <functional>
  19 #include <iterator>
  20 #include <cstdlib>   // for rand()
  21
  22 //======================================================================
  23 // Most of the algorithms here have three versions. For example a sort
  24 // function can have the following forms:
  25 //   sort(beg, end);
  26 //   sort(beg, end, less);
  27 //   sort(beg, end, less, key);
  28 // The first two forms are standard STL. The third form adds an
  29 // argument key, which is a unary function.  Where the second
  30 // form would compare two iterators i and j as less(*i, *j),
  31 // the third form does less(key(i), key(j)) instead. This allows
  32 // moving some of the computation related to the comparison from
  33 // less() into key().  When the same iterator is used in many
  34 // comparisons (for example the pivot), key() needs to be evaluated
  35 // only once.
  36 //
  37 // For example, to sort objects of type T with a member function
  38 // size() returning int into increasing order of size() do
  39 // (TODO: test/expand this, use vector of vectors)
  40 //
  41 //   sort(beg, end, std::less<unsigned>(), std::mem_fun(&T::size));
  42 //
  43 // key() may return a pointer or reference to (a member of) the object.
  44 // All the algorithms assume that the value returned by key() stays
  45 // valid only as long as the object is not moved.
  46 //
  47 // TYPE REQUIREMENTS
  48 // For example:
  49 // template <typename Iterator, typename Compare, typename KeyAccess>
  50 // void sort(Iterator, Iterator, Compare, KeyAccess);
  51 //  * KeyAccess is a model of Adaptable Unary Function
  52 //  * Iterator is convertible to KeyAccess::argument_type
  53 //  * KeyAccess::result_type is convertible to the argument type
  54 //    of Compare.
  55 //======================================================================
  56
  57 //----------------------------------------------------------------------
  58 // functor copy_dereference
  59 // functor const_dereference
  60 //
  61 // Default functors to be used as key().
  62 // (TODO: which one should be used as the default?)
  63 // (TODO: is const_dereference::result_type a problem?)
  64 //----------------------------------------------------------------------
  65 template <typename Iterator>
  66 class const_dereference
  67   : public std::unary_function<Iterator,
  68           const typename std::iterator_traits<Iterator>::value_type &>
  69 {
  70 public:
  71   const typename std::iterator_traits<Iterator>::value_type &
  72   operator() (Iterator i) const { return *i; }
  73 };
  74
  75 template <typename Iterator>
  76 class copy_dereference
  77   : public std::unary_function<Iterator,
  78                  typename std::iterator_traits<Iterator>::value_type>
  79 {
  80 public:
  81   typename std::iterator_traits<Iterator>::value_type
  82   operator() (Iterator i) const { return *i; }
  83 };
  84
  85 template <typename Iterator>
  86 class default_key : public copy_dereference<Iterator> {};
  87
  88
  89
  90 //======================================================================
  91 //
  92 // Pivot selection
  93 //
  94 // (TODO: non-randomized pivot selectors)
  95 //======================================================================
  96
  97 //----------------------------------------------------------------------
  98 // function iter_median3
  99 //
 100 // Median of three
 101 //----------------------------------------------------------------------
 102 template <typename Iterator, typename Compare, typename KeyAccess>
 103 Iterator
 104 iter_median3(Iterator a, Iterator b, Iterator c,
 105              Compare less, KeyAccess key) {
 106   typedef typename KeyAccess::result_type key_type;
 107   key_type ka = key(a), kb = key(b), kc = key(c);
 108   if (less(ka, kb))
 109     if (less(kb, kc)) return b;
 110     else if (less(ka, kc)) return c;
 111     else return a;
 112   else if (less(ka, kc)) return a;
 113   else if (less(kb, kc)) return c;
 114   else return b;
 115 }
 116 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 117
 118 template <typename Iterator, typename Compare>
 119 Iterator
 120 iter_median3(Iterator a, Iterator b, Iterator c, Compare less) {
 121   return iter_median3(a, b, c, less, default_key<Iterator>());
 122 }
 123
 124 template <typename Iterator>
 125 Iterator
 126 iter_median3(Iterator a, Iterator b, Iterator c) {
 127   typedef typename std::iterator_traits<Iterator>::value_type key_type;
 128   return iter_median3(a, b, c, std::less<key_type>(),
 129                       default_key<Iterator>());
 130 }
 131
 132
 133 //----------------------------------------------------------------------
 134 // function random_pivot
 135 //
 136 // Choose pivot of as a median of three random elements
 137 // (or as a single random element for small ranges)
 138 //
 139 // (TODO: better/faster random number generation?)
 140 //----------------------------------------------------------------------
 141 template <typename RandomAccessIterator, typename Compare,
 142           typename KeyAccess>
 143 RandomAccessIterator
 144 random_pivot (RandomAccessIterator beg, RandomAccessIterator end,
 145               Compare less, KeyAccess key)
 146 {
 147   static double scale_to_one = 1.0L/(RAND_MAX+1.0);
 148
 149   typedef typename std::iterator_traits<RandomAccessIterator>::difference_type
 150     difference_type;
 151   difference_type size = std::distance(beg, end);
 152   double scale_to_size = size * scale_to_one;
 153   RandomAccessIterator pivot;
 154   pivot = beg + static_cast<difference_type>(scale_to_size*std::rand());
 155   if (size > 50) {
 156     RandomAccessIterator pivot2, pivot3;
 157     pivot2 = beg + static_cast<difference_type>(scale_to_size*std::rand());
 158     pivot3 = beg + static_cast<difference_type>(scale_to_size*std::rand());
 159     pivot = iter_median3(pivot, pivot2, pivot3, less, key);
 160   }
 161   return pivot;
 162 }
 163 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 164
 165 template <typename RandomAccessIterator, typename Compare>
 166 RandomAccessIterator
 167 random_pivot(RandomAccessIterator beg, RandomAccessIterator end,
 168                     Compare less)
 169 {
 170   return random_pivot(beg, end, less,
 171                       default_key<RandomAccessIterator>());
 172 }
 173
 174 template <typename RandomAccessIterator>
 175 RandomAccessIterator
 176 random_pivot(RandomAccessIterator beg, RandomAccessIterator end)
 177 {
 178   typedef typename std::iterator_traits<RandomAccessIterator>::value_type
 179     key_type;
 180   return random_pivot(beg, end, std::less<key_type>(),
 181                       default_key<RandomAccessIterator>());
 182 }
 183
 184
 185
 186
 187 //======================================================================
 188 // Partitioning
 189 //======================================================================
 190
 191 //----------------------------------------------------------------------
 192 // function binary_partition
 193 //
 194 // Partitions the input range [beg,end) into two parts [beg,mid) and
 195 // [mid,end) with all elements smaller than pivot in [beg, mid) and
 196 // all elements larger than pivot in [mid,end). Equal elements may
 197 // be in either subrange. Returns mid.
 198 // PRECONDITION: pivot is in the range [beg,end)
 199 //----------------------------------------------------------------------
 200 template <typename RandomAccessIterator, typename Compare,
 201           typename KeyAccess>
 202 RandomAccessIterator
 203 binary_partition(RandomAccessIterator beg, RandomAccessIterator end,
 204                  RandomAccessIterator pivot, Compare less, KeyAccess key)
 205 {
 206   if (beg == --end) return beg;
 207
 208   // move the pivot to a safe place and setup sentinels
 209   std::swap(*beg, *pivot);
 210   if (less(key(end), key(beg))) {
 211     std::swap(*beg, *end);
 212     pivot = end;
 213   } else {
 214     pivot = beg;
 215   }
 216
 217   // now the pivot won't move anymore
 218   typename KeyAccess::result_type pivot_key = key(pivot);
 219
 220   while (true) {
 221     do { ++beg; } while (less(key(beg), pivot_key));
 222     do { --end; } while (less(pivot_key, key(end)));
 223     if (!(beg < end)) return beg;
 224     std::swap(*beg, *end);
 225   }
 226 }
 227 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 228
 229 template <typename RandomAccessIterator, typename Compare>
 230 RandomAccessIterator
 231 binary_partition(RandomAccessIterator beg, RandomAccessIterator end,
 232                  RandomAccessIterator pivot, Compare less)
 233 {
 234   return binary_partition(beg, end, pivot, less,
 235                           default_key<RandomAccessIterator>());
 236 }
 237
 238 template <typename RandomAccessIterator>
 239 RandomAccessIterator
 240 binary_partition(RandomAccessIterator beg, RandomAccessIterator end,
 241                  RandomAccessIterator pivot)
 242 {
 243   typedef typename std::iterator_traits<RandomAccessIterator>::value_type
 244     key_type;
 245   return binary_partition(beg, end, pivot, std::less<key_type>(),
 246                           default_key<RandomAccessIterator>());
 247 }
 248
 249
 250 //----------------------------------------------------------------------
 251 // function ternary_partition
 252 //
 253 // Partitions the input range [beg,end) into three parts according to
 254 // comparisons to the pivot:  | less | equal | greater |
 255 // Returns the middle (equal) range.
 256 // PRECONDITION: pivot is in the range [beg,end)
 257 //
 258 // METHOD
 259 // The algorithm maintains the following invariant:
 260 //
 261 // | equal  |  less  |  unknown  | greater | equal |
 262 //  ^        ^        ^         ^         ^         ^
 263 // beg  first_less   left     right  last_greater  end
 264 //
 265 //----------------------------------------------------------------------
 266 template <typename RandomAccessIterator, typename Compare,
 267           typename KeyAccess>
 268 std::pair<RandomAccessIterator,RandomAccessIterator>
 269 ternary_partition(RandomAccessIterator beg, RandomAccessIterator end,
 270                   RandomAccessIterator pivot, Compare less,
 271                   KeyAccess key)
 272 {
 273   RandomAccessIterator left = beg, right = end-1;
 274   RandomAccessIterator first_less = left, last_greater = right;
 275
 276   // first move pivot to a safe place and setup sentinels
 277   std::iter_swap(pivot, left);
 278   if (less(key(right), key(left))) {
 279     std::iter_swap(left, right);
 280     pivot = right;
 281     ++left; --right; --last_greater;
 282   } else {
 283     pivot = left;
 284     ++left; ++first_less;
 285   }
 286
 287   // now the pivot won't move anymore
 288   typename KeyAccess::result_type pivot_key = key(pivot);
 289
 290   while(true) {
 291     while(less(key(left), pivot_key)) ++left;
 292     while (!less(pivot_key, key(left)) && left < right) {
 293       std::iter_swap(left++, first_less++);
 294       while(less(key(left), pivot_key)) ++left;
 295     }
 296     while(less(pivot_key, key(right))) --right;
 297     while (!less(key(right), pivot_key) && left < right) {
 298       std::iter_swap(right--, last_greater--);
 299       while(less(pivot_key, key(right))) --right;
 300     }
 301     if (!(left < right)) break;
 302     std::iter_swap(left++, right--);
 303   }
 304
 305   // now the situation is this:
 306   //
 307   // | equal  |     less     |    greater   | equal |
 308   //  ^        ^            ^ ^            ^         ^
 309   // beg  first_less    right left    last_greater  end
 310   //
 311   // or this:
 312   //
 313   // | equal  |     less    |=|   greater   | equal |
 314   //  ^        ^             ^             ^         ^
 315   // beg  first_less       left       last_greater  end
 316   //                       right
 317   //
 318   // next: swap equal parts to the middle
 319
 320   typename std::iterator_traits<RandomAccessIterator>::difference_type size;
 321   size = std::min(first_less-beg, left-first_less);
 322   std::swap_ranges(beg, beg+size, left-size);
 323   size = std::min(end-1-last_greater, last_greater-right);
 324   std::swap_ranges(right+1, right+1+size, end-size);
 325   return std::make_pair(beg+(left-first_less), end-(last_greater-right));
 326 }
 327 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 328
 329 template <typename RandomAccessIterator, typename Compare>
 330 std::pair<RandomAccessIterator,RandomAccessIterator>
 331 ternary_partition(RandomAccessIterator beg, RandomAccessIterator end,
 332                   RandomAccessIterator pivot, Compare less)
 333 {
 334   return ternary_partition(beg, end, pivot, less,
 335                            default_key<RandomAccessIterator>());
 336 }
 337
 338 template <typename RandomAccessIterator>
 339 std::pair<RandomAccessIterator,RandomAccessIterator>
 340 ternary_partition(RandomAccessIterator beg, RandomAccessIterator end,
 341                   RandomAccessIterator pivot)
 342 {
 343   typedef typename std::iterator_traits<RandomAccessIterator>::value_type
 344     key_type;
 345   return ternary_partition(beg, end, pivot, std::less<key_type>(),
 346                            default_key<RandomAccessIterator>());
 347 }
 348
 349
 350 //======================================================================
 351 // Sorting
 352 //======================================================================
 353
 354 //----------------------------------------------------------------------
 355 // function insertion_sort
 356 //
 357 //----------------------------------------------------------------------
 358 template <typename RandomAccessIterator, typename Compare,
 359           typename KeyAccess>
 360 void
 361 insertion_sort(RandomAccessIterator beg, RandomAccessIterator end,
 362                Compare less, KeyAccess key)
 363 {
 364   if (end-beg <= 1) return;
 365   for (RandomAccessIterator i = beg+1; i != end; ++i) {
 366     typename KeyAccess::result_type i_key = key(i); // i is not moved ...
 367     RandomAccessIterator j = i-1;
 368     if (!less(i_key, key(j))) continue;
 369     for ( ; j != beg; --j) {
 370       if (!less(i_key, key(j-1))) break;
 371       std::swap(*(j-1), *j);
 372     }
 373     std::swap(*i, *j);                              // ... until here
 374   }
 375 }
 376 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 377
 378 template <typename RandomAccessIterator, typename Compare>
 379 void
 380 insertion_sort(RandomAccessIterator beg, RandomAccessIterator end,
 381                Compare less)
 382 {
 383   insertion_sort(beg, end, less, default_key<RandomAccessIterator>());
 384 }
 385
 386 template <typename RandomAccessIterator>
 387 void
 388 insertion_sort(RandomAccessIterator beg, RandomAccessIterator end)
 389 {
 390   typedef typename std::iterator_traits<RandomAccessIterator>::value_type
 391     key_type;
 392   insertion_sort(beg, end, std::less<key_type>(),
 393                  default_key<RandomAccessIterator>());
 394 }
 395
 396
 397 //----------------------------------------------------------------------
 398 // function quicksort
 399 //
 400 //----------------------------------------------------------------------
 401 template <typename RandomAccessIterator, typename Compare,
 402           typename KeyAccess>
 403 void
 404 quicksort(RandomAccessIterator beg, RandomAccessIterator end,
 405           Compare less, KeyAccess key)
 406 {
 407   while (end-beg > 15) {
 408     RandomAccessIterator pivot = random_pivot(beg, end, less, key);
 409     RandomAccessIterator mid = binary_partition(beg, end, pivot, less, key);
 410     quicksort(beg, mid, less, key);
 411     beg = mid;
 412   }
 413   insertion_sort(beg, end, less, key);
 414 }
 415 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
 416
 417 template <typename RandomAccessIterator, typename Compare>
 418 void
 419 quicksort(RandomAccessIterator beg, RandomAccessIterator end, Compare less)
 420 {
 421   quicksort(beg, end, less, default_key<RandomAccessIterator>());
 422 }
 423
 424 template <typename RandomAccessIterator>
 425 void
 426 quicksort(RandomAccessIterator beg, RandomAccessIterator end)
 427 {
 428   typedef typename std::iterator_traits<RandomAccessIterator>::value_type
 429     key_type;
 430   quicksort(beg, end, std::less<key_type>(),
 431             default_key<RandomAccessIterator>());
 432 }
 433
 434
 435 #endif // PARTITION_HPP