4 * Copyright 2003 Max-Planck-Institut fuer Informatik
5 * Copyright 2004 Juha Ka"rkka"inen <juha.karkkainen@cs.helsinki.fi>
9 #ifndef DCSAMPLESORT_HPP
10 #define DCSAMPLESORT_HPP
12 #include "difference_cover.hpp"
13 #include "doubling.hpp"
14 #include "stringsort.hpp"
26 //----------------------------------------------------------------------
27 // functor mark_unsorted_group
29 // When string sorting leaves a group of suffixes unsorted,
30 // it marks that group by calling this functor.
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
36 //----------------------------------------------------------------------
37 class mark_unsorted_group {
39 template <typename SArrayIterator>
40 void operator() (SArrayIterator beg, SArrayIterator end) const {
43 *end = ~*end; // note: group of size one stays unmarked
50 template <class Sampler, class RandomAccessIterator1,
51 class RandomAccessIterator2, class RandomAccessIterator3>
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)
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());
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());
77 // sort the sample to limited depth
78 suffix_mkqsort(str, str_end, suffixes, suffixes_end, sampler.period(),
79 mark_unsorted_group());
82 RandomAccessIterator3 first = suffixes;
83 while (first != suffixes_end) {
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;
90 *first = -(last-first);
93 RandomAccessIterator3 last;
95 for (last=first+1; *last >= 0; ++last) ;
97 for ( ; first <= last; ++first) {
98 *first = sampler.pack(*first);
99 ranks[*first] = last - suffixes;
104 // complete sorting with the doubling algorithm
105 doubling_sort(suffixes, suffixes_end, ranks, ranks_end,
106 sampler.packed_period());
110 #endif // DCSAMPLESORT_HPP