4 * Copyright 2003 Max-Planck-Institut fuer Informatik
5 * Copyright 2004 Juha Ka"rkka"inen <juha.karkkainen@cs.helsinki.fi>
9 #ifndef DCSUFFIXSORT_HPP
10 #define DCSUFFIXSORT_HPP
12 #include "stringsort.hpp"
13 #include "difference_cover.hpp"
14 #include "partition.hpp"
16 #include "doubling.hpp"
17 #include "stringsort.hpp"
18 #include "checker.hpp"
33 //----------------------------------------------------------------------
36 // compare two suffixes using difference covers
37 //----------------------------------------------------------------------
38 template <typename RankIterator>
39 class dc_suffix_compare {
41 typedef typename std::iterator_traits<RankIterator>::value_type
43 const RankIterator sample_ranks;
44 const dc_sampler<rank_type>& sample;
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];
56 //----------------------------------------------------------------------
57 // functor mark_unsorted_group
59 // When string sorting leaves a group of suffixes unsorted,
60 // it marks that group by calling this functor.
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
66 //----------------------------------------------------------------------
67 class mark_unsorted_group2 {
69 template <typename SArrayIterator>
70 void operator() (SArrayIterator beg, SArrayIterator end) const {
73 *end = ~*end; // note: group of size one stays unmarked
78 //----------------------------------------------------------------------
81 // Replaces mark_unsorted_group when nothing needs to be done
82 // to unsorted groups (this happens when doing stringsort only)
83 //----------------------------------------------------------------------
86 template <typename Iterator>
87 void operator() (Iterator, Iterator) {}
92 //----------------------------------------------------------------------
93 // function dc_sort_suffixes
95 // Sort a set of suffixes using a difference cover sample.
96 //----------------------------------------------------------------------
97 template <typename StringIterator, typename SArrayIterator,
98 typename DCSampler, typename RankIterator>
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)
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());
112 suffix_mkqsort(str, str_end, sa, sa_end, sampler.period(),
113 mark_unsorted_group2());
115 SArrayIterator first = sa;
117 while (first != sa_end && *first >= 0) ++first;
118 if (first == sa_end) break;
120 SArrayIterator last = first + 1;
121 while (*last >= 0) ++last;
124 quicksort(first, last,
125 dc_suffix_compare<RankIterator>(ranks, sampler));
131 #endif // DCSUFFIXSORT_HPP