dcover/dcsuffixsort.hpp

   1 /*
   2  * dcsuffixsort.hpp
   3  *
   4  * Copyright 2003 Max-Planck-Institut fuer Informatik
   5  * Copyright 2004 Juha Ka"rkka"inen <juha.karkkainen@cs.helsinki.fi>
   6  *
   7  */
   8
   9 #ifndef DCSUFFIXSORT_HPP
  10 #define DCSUFFIXSORT_HPP
  11
  12 #include "stringsort.hpp"
  13 #include "difference_cover.hpp"
  14 #include "partition.hpp"
  15 /*
  16 #include "doubling.hpp"
  17 #include "stringsort.hpp"
  18 #include "checker.hpp"
  19 #include "timing.hpp"
  20 */
  21
  22 #include <utility>
  23 #include <iterator>
  24 #include <stdexcept>
  25 #include <sstream>
  26 /*
  27 #include <algorithm>
  28 #include <vector>
  29 #include <string>
  30 #include <functional>
  31 */
  32
  33 //----------------------------------------------------------------------
  34 // dc_suffix_compare
  35 //
  36 // compare two suffixes using difference covers
  37 //----------------------------------------------------------------------
  38 template <typename RankIterator>
  39 class dc_suffix_compare {
  40 private:
  41   typedef typename std::iterator_traits<RankIterator>::value_type
  42           rank_type;
  43   const RankIterator sample_ranks;
  44   const dc_sampler<rank_type>& sample;
  45 public:
  46   dc_suffix_compare(RankIterator beg, const dc_sampler<rank_type>& s)
  47     : sample_ranks(beg), sample(s) {}
  48   template <typename StringPosType>
  49   bool operator() (StringPosType a, StringPosType b) const {
  50     std::pair<rank_type,rank_type> rep = sample.pair(a, b);
  51     return sample_ranks[rep.first] < sample_ranks[rep.second];
  52   }
  53 };
  54
  55
  56 //----------------------------------------------------------------------
  57 // functor mark_unsorted_group
  58 //
  59 // When string sorting leaves a group of suffixes unsorted,
  60 // it marks that group by calling this functor.
  61 //
  62 // The marking is done by one's complementing the first and last
  63 // entries of the group. Complemented values are assumed to become
  64 // negative. Complementing is used instead of negation to be able
  65 // mark the zero.
  66 //----------------------------------------------------------------------
  67 class mark_unsorted_group2 {
  68 public:
  69   template <typename SArrayIterator>
  70   void operator() (SArrayIterator beg, SArrayIterator end) const {
  71     *beg = ~*beg;
  72     --end;
  73     *end = ~*end;  // note: group of size one stays unmarked
  74   }
  75 };
  76
  77 /*
  78 //----------------------------------------------------------------------
  79 // functor do_nothing
  80 //
  81 // Replaces mark_unsorted_group when nothing needs to be done
  82 // to unsorted groups (this happens when doing stringsort only)
  83 //----------------------------------------------------------------------
  84 class do_nothing {
  85 public:
  86   template <typename Iterator>
  87   void operator() (Iterator, Iterator) {}
  88 };
  89 */
  90
  91
  92 //----------------------------------------------------------------------
  93 // function dc_sort_suffixes
  94 //
  95 // Sort a set of suffixes using a difference cover sample.
  96 //----------------------------------------------------------------------
  97 template <typename StringIterator, typename SArrayIterator,
  98           typename DCSampler, typename RankIterator>
  99 void
 100 dc_sort_suffixes(StringIterator str, StringIterator str_end,
 101               SArrayIterator sa, SArrayIterator sa_end,
 102               const DCSampler& sampler,
 103               RankIterator ranks, RankIterator ranks_end)
 104 {
 105   if (ranks_end-ranks != sampler.samplesize()) {
 106     std::ostringstream os;
 107     os << "dc_suffix_sort:"
 108        << " wrong range size";
 109     throw std::logic_error(os.str());
 110   }
 111
 112   suffix_mkqsort(str, str_end, sa, sa_end, sampler.period(),
 113                          mark_unsorted_group2());
 114
 115   SArrayIterator first = sa;
 116   while (true) {
 117     while (first != sa_end && *first >= 0) ++first;
 118     if (first == sa_end) break;
 119     *first = ~*first;
 120     SArrayIterator last = first + 1;
 121     while (*last >= 0) ++last;
 122     *last = ~*last;
 123     ++last;
 124     quicksort(first, last,
 125               dc_suffix_compare<RankIterator>(ranks, sampler));
 126     first = last;
 127   }
 128
 129 }
 130
 131 #endif // DCSUFFIXSORT_HPP