tools/bwt/dcs-bwt/src/ternary_partition.h

   1 // Copyright 2007 Google Inc.
   2
   3 // This program is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU General Public License
   5 // as published by the Free Software Foundation; either version 2
   6 // of the License, or (at your option) any later version.
   7
   8 // This program is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 // GNU General Public License for more details.
  12
  13 // You should have received a copy of the GNU General Public License
  14 // along with this program; if not, write to the Free Software
  15 // Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  16
  17 // Ternary partition algorithm. Includes main functions:
  18 //   ChoosePivot()
  19 //   TernaryPartition()
  20 // and supporting code
  21 //   class RandomNumberGenerator
  22 //   function MedianOfThree()
  23 //
  24 // Genereric comparison is achieved using a functor that returns
  25 // the comparison key instead of a comparison functor.
  26
  27 #ifndef DCSBWT_TERNARY_PARTITION_H__
  28 #define DCSBWT_TERNARY_PARTITION_H__
  29
  30 #include "inttypes.h"
  31
  32 #include <utility>    // for pair, make_pair
  33 #include <algorithm>  // for swap
  34 #include <cstdlib>    // for drand48
  35
  36 namespace dcsbwt {
  37
  38 namespace ternary_partition {
  39
  40 // Currently implemented using drand48.
  41 // TODO: Switch to an implementation using Mersenne Twister or
  42 // to using directly TR1 random number generators.
  43 class RandomNumberGenerator {
  44  public:
  45   RandomNumberGenerator() { srand48_r(87989823L, &buffer_); }
  46   typedef uint32 result_type;
  47   static const result_type min = 0;
  48   static const result_type max = (1UL << 31) - 1;
  49   result_type operator()() {
  50     long int result = 0;
  51     lrand48_r(&buffer_, &result);
  52     return result;
  53   }
  54   result_type Uniform(uint32 range) {
  55     assert(range - 1 <= max);
  56     return operator()() % range;
  57   }
  58  private:
  59   drand48_data buffer_;
  60 };
  61
  62 template <typename Iterator, typename Key>
  63 Iterator MedianOfThree(Iterator a, Iterator b, Iterator c, Key key) {
  64   typename Key::result_type akey = key(*a);
  65   typename Key::result_type bkey = key(*b);
  66   typename Key::result_type ckey = key(*c);
  67   if (akey < bkey) {
  68     if (bkey < ckey) return b;
  69     else if (akey < ckey) return c;
  70     else return a;
  71   } else {
  72     if (akey < ckey) return a;
  73     else if (bkey < ckey) return c;
  74     else return b;
  75   }
  76 }
  77
  78 }  // namespace ternary_partition
  79
  80 // Choose a pivot for partitioning.
  81 // Returns an iterator to the chosen pivot.
  82 template <typename Iterator, typename Key>
  83 Iterator ChoosePivot(Iterator begin, Iterator end, Key key) {
  84   using ternary_partition::MedianOfThree;
  85   static ternary_partition::RandomNumberGenerator rng;
  86   int32 size = end - begin;
  87   if (size < 100) {
  88     return begin + rng.Uniform(size);
  89   //return begin + rng.Uniform(std::distance(begin,end));
  90   } else if (size < 1000) {
  91     return MedianOfThree(begin + rng.Uniform(size),
  92                          begin + rng.Uniform(size),
  93                          begin + rng.Uniform(size),
  94                          key);
  95   } else {
  96     // pseudo-median of nine
  97     return MedianOfThree(
  98         MedianOfThree(begin + rng.Uniform(size),
  99                       begin + rng.Uniform(size),
 100                       begin + rng.Uniform(size),
 101                       key),
 102         MedianOfThree(begin + rng.Uniform(size),
 103                       begin + rng.Uniform(size),
 104                       begin + rng.Uniform(size),
 105                       key),
 106         MedianOfThree(begin + rng.Uniform(size),
 107                       begin + rng.Uniform(size),
 108                       begin + rng.Uniform(size),
 109                       key),
 110         key);
 111   }
 112 }
 113
 114 // Permute the elements in [begin,end) so that elements smaller than
 115 // pivot are on the left, elements equal to pivot are in the middle,
 116 // and elements larger than pivot are on the right.
 117 // Returns a range identifying the equal part.
 118 template <typename Iterator, typename Key>
 119 std::pair<Iterator,Iterator> TernaryPartition(Iterator begin, Iterator end,
 120                                               Iterator pivot, Key key) {
 121   // The unqualified call of swap (i.e. without std::) ensures
 122   // that overloads of swap for user-defined types are found.
 123   // This using declaration ensures that the spezializations
 124   // for built-in types in std are found as well.
 125   using std::swap;
 126   typename Key::result_type pivot_key = key(*pivot);
 127   Iterator smaller_end = begin;
 128   Iterator larger_begin = end;
 129   Iterator current = begin;
 130   while (current != larger_begin) {
 131     typename Key::result_type current_key = key(*current);
 132     if (current_key < pivot_key) {
 133       swap(*current++, *smaller_end++);
 134     } else if (pivot_key < current_key) {
 135       swap(*current, *--larger_begin);
 136     } else {
 137       ++current;
 138     }
 139   }
 140   return std::make_pair(smaller_end, larger_begin);
 141 }
 142
 143 }  // namespace dcsbwt
 144
 145 #endif  // DCSBWT_TERNARY_PARTITION_H__