dcover/dcsamplesort.hpp

   1 /*
   2  * dcsamplesort.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 DCSAMPLESORT_HPP
  10 #define DCSAMPLESORT_HPP
  11
  12 #include "difference_cover.hpp"
  13 #include "doubling.hpp"
  14 #include "stringsort.hpp"
  15 /*
  16 */
  17
  18 #include <sstream>
  19 #include <iostream>
  20 /*
  21 #include <algorithm>
  22 #include <iterator>
  23 */
  24
  25
  26 //----------------------------------------------------------------------
  27 // functor mark_unsorted_group
  28 //
  29 // When string sorting leaves a group of suffixes unsorted,
  30 // it marks that group by calling this functor.
  31 //
  32 // The marking is done by one's complementing the first and last
  33 // entries of the group. Complemented values are assumed to become
  34 // negative. Complementing is used instead of negation to be able
  35 // mark the zero.
  36 //----------------------------------------------------------------------
  37 class mark_unsorted_group {
  38 public:
  39   template <typename SArrayIterator>
  40   void operator() (SArrayIterator beg, SArrayIterator end) const {
  41     *beg = ~*beg;
  42     --end;
  43     *end = ~*end;  // note: group of size one stays unmarked
  44   }
  45 };
  46
  47
  48
  49
  50 template <class Sampler, class RandomAccessIterator1,
  51           class RandomAccessIterator2, class RandomAccessIterator3>
  52 void
  53 sort_dc_sample(Sampler sampler,
  54                RandomAccessIterator1 str, RandomAccessIterator1 str_end,
  55                RandomAccessIterator2 ranks, RandomAccessIterator2 ranks_end,
  56                RandomAccessIterator3 suffixes,
  57                RandomAccessIterator3 suffixes_end)
  58 {
  59   int size = sampler.samplesize();
  60   if ((ranks_end-ranks != size) || (suffixes_end-suffixes != size)) {
  61     std::ostringstream os;
  62     os << "sort_dc_sample:"
  63        << " wrong range size";
  64     throw std::logic_error(os.str());
  65   }
  66
  67   // collect the sample
  68   RandomAccessIterator3 beyond = sampler.fill(suffixes);
  69   if (suffixes_end != beyond) {
  70     std::ostringstream os;
  71     os << "sort_dc_sample:"
  72        << " sample.fill produced " << beyond-suffixes
  73        << " samples but samplesize is " << size;
  74     throw std::logic_error(os.str());
  75   }
  76
  77   // sort the sample to limited depth
  78   suffix_mkqsort(str, str_end, suffixes, suffixes_end, sampler.period(),
  79                  mark_unsorted_group());
  80
  81   // compute ranks
  82   RandomAccessIterator3 first = suffixes;
  83   while (first != suffixes_end) {
  84     if (*first >= 0) {
  85       RandomAccessIterator3 last;
  86       ranks[sampler.pack(*first)] = first - suffixes;
  87       for (last=first+1; last != suffixes_end && *last >= 0; ++last) {
  88         ranks[sampler.pack(*last)] = last - suffixes;
  89       }
  90       *first = -(last-first);
  91       first = last;
  92     } else {
  93       RandomAccessIterator3 last;
  94       *first = ~*first;
  95       for (last=first+1; *last >= 0; ++last) ;
  96       *last = ~*last;
  97       for ( ; first <= last; ++first) {
  98         *first = sampler.pack(*first);
  99         ranks[*first] = last - suffixes;
 100       }
 101     }
 102   }
 103
 104   // complete sorting with the doubling algorithm
 105   doubling_sort(suffixes, suffixes_end, ranks, ranks_end,
 106                 sampler.packed_period());
 107
 108 }
 109
 110 #endif // DCSAMPLESORT_HPP