47static inline typename StringSet::Iterator
med3func(
49 typename StringSet::Iterator a,
typename StringSet::Iterator b,
50 typename StringSet::Iterator c,
size_t depth) {
51 typename StringSet::Char va = ss.get_char(*a, depth);
52 typename StringSet::Char vb = ss.get_char(*b, depth);
55 typename StringSet::Char vc = ss.get_char(*c, depth);
56 if (vc == va || vc == vb)
59 ? (vb < vc ? b : (va < vc ? c : a))
60 : (vb > vc ? b : (va < vc ? a : c));
75 const StringPtr& strptr,
size_t depth,
size_t memory) {
78 typedef typename StringSet::Iterator Iterator;
80 const StringSet& ss = strptr.
active();
81 const Iterator a = ss.begin();
85 static const size_t memory_use =
86 2 *
sizeof(size_t) +
sizeof(StringSet) + 5 *
sizeof(Iterator);
88 if (n < 32 || (memory != 0 && memory < memory_use + 1)) {
93 Iterator pa, pb, pc, pd, pn;
97 Iterator pm = a + (n / 2);
102 pl =
med3func(ss, pl, pl + d, pl + 2 * d, depth);
103 pm =
med3func(ss, pm - d, pm, pm + d, depth);
104 pn =
med3func(ss, pn - 2 * d, pn - d, pn, depth);
106 pm =
med3func(ss, pl, pm, pn, depth);
108 int pivot = ss.get_char(*a, depth);
112 while (pb <= pc && (r =
static_cast<int>(ss.get_char(*pb, depth)) - pivot) <= 0) {
113 if (r == 0) std::swap(*pa++, *pb);
116 while (pb <= pc && (r =
static_cast<int>(ss.get_char(*pc, depth)) - pivot) >= 0) {
117 if (r == 0) std::swap(*pc, *pd--);
121 std::swap(*pb++, *pc--);
125 size_t pe_start_index, pe_end_index;
126 r = std::min(pa - a, pb - pa);
127 vec_swap<StringSet>(a, pb - r, r);
129 r = std::min(pd - pc, pn - pd - 1);
130 pe_end_index = (pn - a) - r;
131 vec_swap<StringSet>(pb, pn - r, r);
133 for (
size_t it = pe_start_index + 1; it < pe_end_index; ++it)
140 strptr.
set_lcp(a - ss.begin() + r, depth);
144 depth, memory - memory_use);
146 if (ss.get_char(*(a + r), depth) != 0) {
148 strptr.
sub(a - ss.begin() + r, (pa - a) + (pn - pd - 1)),
149 depth + 1, memory - memory_use);
153 strptr.
set_lcp(a - ss.begin() + n - r, depth);
155 if ((r = pd - pc) > 1) {
157 depth, memory - memory_use);