Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
dc3.cpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * examples/suffix_sorting/dc3.cpp
3  *
4  * Part of Project Thrill - http://project-thrill.org
5  *
6  * Copyright (C) 2015-2016 Timo Bingmann <[email protected]>
7  *
8  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
9  ******************************************************************************/
10 
13 
15 #include <thrill/api/cache.hpp>
16 #include <thrill/api/collapse.hpp>
17 #include <thrill/api/dia.hpp>
18 #include <thrill/api/gather.hpp>
19 #include <thrill/api/max.hpp>
20 #include <thrill/api/merge.hpp>
21 #include <thrill/api/prefixsum.hpp>
22 #include <thrill/api/print.hpp>
23 #include <thrill/api/size.hpp>
24 #include <thrill/api/sort.hpp>
25 #include <thrill/api/sum.hpp>
26 #include <thrill/api/union.hpp>
27 #include <thrill/api/window.hpp>
28 #include <thrill/api/zip.hpp>
33 
34 #include <algorithm>
35 #include <iomanip>
36 #include <limits>
37 #include <random>
38 #include <stdexcept>
39 #include <string>
40 #include <tuple>
41 #include <utility>
42 #include <vector>
43 
44 namespace examples {
45 namespace suffix_sorting {
46 namespace dc3_local {
47 
48 //! A triple with index (i,t_i,t_{i+1},t_{i+2}).
49 template <typename AlphabetType>
50 struct Chars {
51  AlphabetType ch[3];
52 
53  bool operator == (const Chars& b) const {
54  return std::tie(ch[0], ch[1], ch[2])
55  == std::tie(b.ch[0], b.ch[1], b.ch[2]);
56  }
57 
58  bool operator < (const Chars& b) const {
59  return std::tie(ch[0], ch[1], ch[2])
60  < std::tie(b.ch[0], b.ch[1], b.ch[2]);
61  }
62 
63  friend std::ostream& operator << (std::ostream& os, const Chars& chars) {
64  return os << '[' << chars.ch[0] << ',' << chars.ch[1]
65  << ',' << chars.ch[2] << ']';
66  }
67 
68  static Chars Lowest() {
69  return Chars {
70  {
71  std::numeric_limits<AlphabetType>::lowest(),
72  std::numeric_limits<AlphabetType>::lowest(),
73  std::numeric_limits<AlphabetType>::lowest()
74  }
75  };
76  }
78 
79 //! A triple with index (i,t_i,t_{i+1},t_{i+2}).
80 template <typename Index, typename AlphabetType>
81 struct IndexChars {
82  Index index;
83  Chars<AlphabetType> chars;
84 
85  const AlphabetType& at_radix(size_t depth) const { return chars.ch[depth]; }
86 
87  friend std::ostream& operator << (std::ostream& os, const IndexChars& tc) {
88  return os << '[' << tc.index << '|' << tc.chars << ']';
89  }
91 
92 //! A pair (index, rank)
93 template <typename Index>
94 struct IndexRank {
95  Index index;
96  Index rank;
97 
98  friend std::ostream& operator << (std::ostream& os, const IndexRank& tr) {
99  return os << '(' << tr.index << '|' << tr.rank << ')';
100  }
102 
103 //! Fragments at String Positions i = 0 Mod 3.
104 template <typename Index, typename AlphabetType>
105 struct StringFragmentMod0 {
106  Index index;
107  Index r1, r2;
108  AlphabetType t0, t1;
109 
110  friend std::ostream& operator << (std::ostream& os,
111  const StringFragmentMod0& sf) {
112  return os << "i=" << sf.index
113  << " t0=" << sf.t0 << " t1=" << sf.t1
114  << " r1=" << sf.r1 << " r2=" << sf.r2;
115  }
117 
118 //! Fragments at String Positions i = 1 Mod 3.
119 template <typename Index, typename AlphabetType>
120 struct StringFragmentMod1 {
121  Index index;
122  Index r0, r1;
123  AlphabetType t0;
124 
125  friend std::ostream& operator << (std::ostream& os,
126  const StringFragmentMod1& sf) {
127  return os << "i=" << sf.index
128  << " t0=" << sf.t0 << " r0=" << sf.r0 << " r1=" << sf.r1;
129  }
131 
132 //! Fragments at String Positions i = 2 Mod 3.
133 template <typename Index, typename AlphabetType>
134 struct StringFragmentMod2 {
135  Index index;
136  Index r0, r2;
137  AlphabetType t0, t1;
138 
139  friend std::ostream& operator << (std::ostream& os,
140  const StringFragmentMod2& sf) {
141  return os << "i=" << sf.index
142  << " t0=" << sf.t0 << " r0=" << sf.r0
143  << " t1=" << sf.t1 << " r2=" << sf.r2;
144  }
146 
147 //! Union of String Fragments with Index
148 template <typename Index, typename AlphabetType>
149 struct StringFragment {
150 
151  struct Common {
152  Index index;
153  Index ranks[2];
154  AlphabetType text[2];
156 
157  union {
158  Index index;
159  Common common;
160  StringFragmentMod0<Index, AlphabetType> mod0;
161  StringFragmentMod1<Index, AlphabetType> mod1;
162  StringFragmentMod2<Index, AlphabetType> mod2;
164 
165  StringFragment() = default;
166 
167  // conversion from StringFragmentMod0
168  explicit StringFragment(
169  const StringFragmentMod0<Index, AlphabetType>& _mod0) : mod0(_mod0) { }
170 
171  // conversion from StringFragmentMod1
172  explicit StringFragment(
173  const StringFragmentMod1<Index, AlphabetType>& _mod1) : mod1(_mod1) { }
174 
175  // conversion from StringFragmentMod2
176  explicit StringFragment(
177  const StringFragmentMod2<Index, AlphabetType>& _mod2) : mod2(_mod2) { }
178 
179  friend std::ostream& operator << (std::ostream& os,
180  const StringFragment& tc) {
181  os << '[' << std::to_string(tc.index) << '|';
182  if (tc.index % 3 == 0)
183  return os << "0|" << tc.mod0 << ']';
184  else if (tc.index % 3 == 1)
185  return os << "1|" << tc.mod1 << ']';
186  else if (tc.index % 3 == 2)
187  return os << "2|" << tc.mod2 << ']';
188  abort();
189  }
190 
191  AlphabetType at_radix(size_t depth) const { return common.text[depth]; }
192  Index sort_rank() const { return common.ranks[0]; }
194 
195 static constexpr size_t fragment_comparator_params[3][3][3] =
196 {
197  {
198  { 1, 0, 0 }, { 1, 0, 1 }, { 2, 1, 1 }
199  },
200  {
201  { 1, 1, 0 }, { 0, 0, 0 }, { 0, 0, 0 }
202  },
203  {
204  { 2, 1, 1 }, { 0, 0, 0 }, { 0, 0, 0 }
205  },
206 };
207 
208 template <typename StringFragment>
209 struct FragmentComparator {
210 
211  bool operator () (const StringFragment& a, const StringFragment& b) const {
212 
213  unsigned ai = a.index % 3, bi = b.index % 3;
214 
215  const size_t* params = fragment_comparator_params[ai][bi];
216 
217  for (size_t d = 0; d < params[0]; ++d)
218  {
219  if (a.common.text[d] == b.common.text[d]) continue;
220  return (a.common.text[d] < b.common.text[d]);
221  }
222 
223  return a.common.ranks[params[1]] < b.common.ranks[params[2]];
224  }
225 };
226 
227 template <typename Index, typename Char>
228 struct CharsRanks12 {
229  Chars<Char> chars;
230  Index rank1;
231  Index rank2;
232 
233  friend std::ostream& operator << (
234  std::ostream& os, const CharsRanks12& c) {
235  return os << "(ch=" << c.chars
236  << " r1=" << c.rank1 << " r2=" << c.rank2 << ")";
237  }
239 
240 template <typename Index, typename Char>
241 struct IndexCR12Pair {
242  Index index;
243  CharsRanks12<Index, Char> cr0;
244  CharsRanks12<Index, Char> cr1;
246 
247 template <typename Type, size_t MaxDepth>
248 class RadixSortFragment
249 {
250 public:
251  explicit RadixSortFragment(size_t K) : K_(K) { }
252  template <typename CompareFunction>
253  void operator () (
254  typename std::vector<Type>::iterator begin,
255  typename std::vector<Type>::iterator end,
256  const CompareFunction& cmp) const {
257  if (K_ <= 4096) {
258  thrill::common::radix_sort_CI<MaxDepth>(
259  begin, end, K_, cmp, [](auto begin, auto end, auto) {
260  // sub sorter: sort StringFragments by rank
261  std::sort(begin, end, [](const Type& a, const Type& b) {
262  return a.sort_rank() < b.sort_rank();
263  });
264  });
265  }
266  else {
267  std::sort(begin, end, cmp);
268  }
269  }
270 
271 private:
272  const size_t K_;
273 };
274 
275 } // namespace dc3_local
276 
277 using namespace thrill; // NOLINT
279 
280 template <typename Index, typename InputDIA>
281 DIA<dc3_local::StringFragment<Index, typename InputDIA::ValueType> >
282 DC3Recursive(const InputDIA& input_dia, size_t input_size, size_t K) {
283 
284  using Char = typename InputDIA::ValueType;
285  using IndexChars = dc3_local::IndexChars<Index, Char>;
286  using IndexRank = dc3_local::IndexRank<Index>;
287  using Chars = dc3_local::Chars<Char>;
288 
289  Context& ctx = input_dia.context();
290 
291  auto triple_unsorted =
292  input_dia.Keep()
293  // map (t_i) -> (i,t_i,t_{i+1},t_{i+2}) where i neq 0 mod 3
294  .template FlatWindow<IndexChars>(
295  3,
296  [](size_t index, const RingBuffer<Char>& rb, auto emit) {
297  if (index % 3 != 0)
298  emit(IndexChars { Index(index), {
299  { rb[0], rb[1], rb[2] }
300  }
301  });
302  },
303  [input_size](size_t index, const RingBuffer<Char>& rb, auto emit) {
304  // emit last sentinel items.
305  if (index % 3 != 0) {
306  emit(IndexChars {
307  Index(index), {
308  { rb.size() >= 1 ? rb[0] : Char(),
309  rb.size() >= 2 ? rb[1] : Char(), Char() }
310  }
311  });
312  }
313  if (index + 1 == input_size && input_size % 3 == 1) {
314  // emit a sentinel tuple for inputs n % 3 == 1 to separate
315  // mod1 and mod2 strings in recursive subproblem. example
316  // which needs this: aaaaaaaaaa.
317  emit(IndexChars { Index(input_size), Chars::Lowest() });
318  }
319  });
320 
321  if (debug_print)
322  triple_unsorted.Keep().Print("triple_unsorted");
323 
324  auto triple_sorted =
325  triple_unsorted
326  // sort triples by contained letters
327  .Sort([](const IndexChars& a, const IndexChars& b) {
328  return a.chars < b.chars;
330 
331  if (debug_print)
332  triple_sorted.Keep().Print("triple_sorted");
333 
334  // save triple's indexes (sorted by triple content) -> less storage
335  auto triple_index_sorted =
336  triple_sorted
337  .Map([](const IndexChars& tc) { return tc.index; })
338  .Cache();
339 
340  auto triple_prenames =
341  triple_sorted
342  .template FlatWindow<Index>(
343  2, [](size_t index, const RingBuffer<IndexChars>& rb, auto emit) {
344  assert(rb.size() == 2);
345 
346  // emit one sentinel for index 0.
347  if (index == 0) emit(0);
348 
349  // emit 0 or 1 depending on whether previous triple is equal
350  emit(rb[0].chars == rb[1].chars ? 0 : 1);
351  });
352 
353  if (debug_print)
354  triple_prenames.Keep().Print("triple_prenames");
355 
356  auto triple_lexname_sums = triple_prenames.PrefixSum();
357 
358  if (debug_print)
359  triple_lexname_sums.Keep().Print("triple_lexname_sums");
360 
361  // get the last element via an associative reduce.
362  const Index max_lexname = triple_lexname_sums.Keep().Max();
363 
364  // compute the size of the 2/3 subproblem.
365  const Index size_subp = Index((input_size / 3) * 2 + (input_size % 3 != 0));
366 
367  // size of the mod1 part of the recursive subproblem
368  const Index size_mod1 = Index(input_size / 3 + (input_size % 3 != 0));
369 
370  if (debug_print) {
371  sLOG1 << "max_lexname=" << max_lexname
372  << " size_subp=" << size_subp
373  << " size_mod1=" << size_mod1;
374  }
375 
376  DIA<IndexRank> ranks_mod12;
377 
378  if (max_lexname + Index(1) != size_subp) {
379 
380  // some lexical name is not unique -> perform recursion on two
381  // substrings (mod 1 and mod 2)
382 
383  // zip triples and ranks.
384  auto triple_ranks =
385  triple_index_sorted
386  .Zip(NoRebalanceTag,
387  triple_lexname_sums,
388  [](const Index& triple_index, const Index& rank) {
389  return IndexRank { triple_index, rank };
390  });
391 
392  if (debug_print)
393  triple_ranks.Keep().Print("triple_ranks");
394 
395  // construct recursion string with all ranks at mod 1 indices followed
396  // by all ranks at mod 2 indices.
397  auto triple_ranks_sorted =
398  triple_ranks
399  .Sort([](const IndexRank& a, const IndexRank& b) {
400  if (a.index % 3 == b.index % 3)
401  return a.index < b.index;
402  else
403  return a.index % 3 < b.index % 3;
404  });
405 
406  if (debug_print)
407  triple_ranks_sorted.Keep().Print("triple_ranks_sorted");
408 
409  DIA<Index> string_mod12 =
410  triple_ranks_sorted
411  .Map([](const IndexRank& tr) {
412  return tr.rank;
413  })
414  .Cache();
415 
416  if (debug_print)
417  string_mod12.Keep().Print("string_mod12");
418 
419  using RecStringFragment = dc3_local::StringFragment<Index, Index>;
420 
421  DIA<RecStringFragment> suffix_array_rec = DC3Recursive<Index>(
422  string_mod12, size_subp, max_lexname + Index(1));
423 
424  // reverse suffix array of recursion strings to find ranks for mod 1
425  // and mod 2 positions.
426 
427  if (debug_print)
428  suffix_array_rec.Keep().Print("suffix_array_rec");
429 
430  ranks_mod12 =
431  suffix_array_rec
432  .ZipWithIndex([](const RecStringFragment& sa, const size_t& i) {
433  // add one to ranks such that zero can be used as sentinel
434  // for suffixes beyond the end of the string.
435  return IndexRank { sa.index, Index(i + 1) };
436  })
437  .Sort([size_mod1](const IndexRank& a, const IndexRank& b) {
438  // use sort order to interleave ranks mod 1/2
439  return a.index % size_mod1 < b.index % size_mod1 || (
440  a.index % size_mod1 == b.index % size_mod1 &&
441  a.index < b.index);
442  });
443 
444  if (debug_print) {
445  // check that ranks are correctly interleaved
446  ranks_mod12.Keep()
447  .Window(
448  DisjointTag, 2,
449  [size_mod1](size_t, const std::vector<IndexRank>& ir) {
450  die_unless(ir[0].index < size_mod1);
451  die_unless(ir[1].index >= size_mod1 || ir[1].rank == Index(0));
452  return true;
453  })
454  .Execute();
455  ranks_mod12.Keep().Print("ranks_mod12");
456  }
457  }
458  else {
459  if (ctx.my_rank() == 0)
460  sLOG1 << "*** recursion finished ***";
461 
462  if (debug_print)
463  triple_index_sorted.Keep().Print("triple_index_sorted");
464 
465  ranks_mod12 =
466  triple_index_sorted
467  .ZipWithIndex([](const Index& sa, const size_t& i) {
468  // add one to ranks such that zero can be used as sentinel
469  // for suffixes beyond the end of the string.
470  return IndexRank { sa, Index(i + 1) };
471  })
472  .Sort([](const IndexRank& a, const IndexRank& b) {
473  // use sort order to interleave ranks mod 1/2
474  return a.index / 3 < b.index / 3 || (
475  a.index / 3 == b.index / 3 &&
476  a.index < b.index);
477  });
478 
479  if (debug_print) {
480  // check that ranks are correctly interleaved
481  ranks_mod12.Keep()
482  .Window(
483  DisjointTag, 2,
484  [](size_t, const std::vector<IndexRank>& ir) {
485  die_unless(ir[0].index % 3 == 1);
486  die_unless(ir[1].index % 3 != 1 || ir[1].rank == Index(0));
487  return true;
488  })
489  .Execute();
490  ranks_mod12.Keep().Print("ranks_mod12");
491  }
492  }
493 
494  // *** construct StringFragments ***
495 
496  // Zip together the two arrays, create pairs, and extract needed
497  // tuples into string fragments.
498 
499  using StringFragmentMod0 = dc3_local::StringFragmentMod0<Index, Char>;
500  using StringFragmentMod1 = dc3_local::StringFragmentMod1<Index, Char>;
501  using StringFragmentMod2 = dc3_local::StringFragmentMod2<Index, Char>;
502 
503  using CharsRanks12 = dc3_local::CharsRanks12<Index, Char>;
504  using IndexCR12Pair = dc3_local::IndexCR12Pair<Index, Char>;
505 
506  auto zip_triple_pairs1 =
507  ZipWindow(
508  ArrayTag, PadTag, /* window_size */ {
509  { 3, 2 }
510  },
511  [](const std::array<Char, 3>& ch, const std::array<IndexRank, 2>& mod12) {
512  return CharsRanks12 {
513  {
514  { ch[0], ch[1], ch[2] }
515  }, mod12[0].rank, mod12[1].rank
516  };
517  },
518  std::make_tuple(std::numeric_limits<Char>::lowest(), IndexRank { 0, 0 }),
519  input_dia, ranks_mod12);
520 
521  if (debug_print)
522  zip_triple_pairs1.Keep().Print("zip_triple_pairs1");
523 
524  auto zip_triple_pairs =
525  zip_triple_pairs1
526  .template FlatWindow<IndexCR12Pair>(
527  2, [size_mod1](size_t index,
528  const RingBuffer<CharsRanks12>& rb, auto emit) {
529  emit(IndexCR12Pair { Index(3 * index), rb[0], rb[1] });
530  if (index + 2 == size_mod1) {
531  // emit last sentinel
532  emit(IndexCR12Pair { Index(3 * (index + 1)), rb[1],
533  CharsRanks12 { Chars::Lowest(), 0, 0 }
534  });
535  }
536  });
537 
538  auto fragments_mod0 =
539  zip_triple_pairs
540  .Map([](const IndexCR12Pair& ip) {
541  return StringFragmentMod0 {
542  ip.index,
543  ip.cr0.rank1, ip.cr0.rank2,
544  ip.cr0.chars.ch[0], ip.cr0.chars.ch[1]
545  };
546  })
547  .Filter([input_size](const StringFragmentMod0& mod0) {
548  return mod0.index < Index(input_size);
549  });
550 
551  auto fragments_mod1 =
552  zip_triple_pairs
553  .Map([](const IndexCR12Pair& ip) {
554  return StringFragmentMod1 {
555  ip.index + Index(1),
556  ip.cr0.rank1, ip.cr0.rank2,
557  ip.cr0.chars.ch[1]
558  };
559  })
560  .Filter([input_size](const StringFragmentMod1& mod1) {
561  return mod1.index < Index(input_size);
562  });
563 
564  auto fragments_mod2 =
565  zip_triple_pairs
566  .Map([](const IndexCR12Pair& ip) {
567  return StringFragmentMod2 {
568  ip.index + Index(2),
569  ip.cr0.rank2, ip.cr1.rank1,
570  ip.cr0.chars.ch[2], ip.cr1.chars.ch[0]
571  };
572  })
573  .Filter([input_size](const StringFragmentMod2& mod2) {
574  return mod2.index < Index(input_size);
575  });
576 
577  if (debug_print) {
578  fragments_mod0.Keep().Print("fragments_mod0");
579  fragments_mod1.Keep().Print("fragments_mod1");
580  fragments_mod2.Keep().Print("fragments_mod2");
581  }
582 
583  // Sort/Merge and map to only suffix array
584 
585  using StringFragment = dc3_local::StringFragment<Index, Char>;
586 
587  auto string_fragments_mod0 =
588  fragments_mod0
589  .Map([](const StringFragmentMod0& mod0)
590  { return StringFragment(mod0); });
591 
592  auto string_fragments_mod1 =
593  fragments_mod1
594  .Map([](const StringFragmentMod1& mod1)
595  { return StringFragment(mod1); });
596 
597  auto string_fragments_mod2 =
598  fragments_mod2
599  .Map([](const StringFragmentMod2& mod2)
600  { return StringFragment(mod2); });
601 
602  auto suffix_array =
603  Union(string_fragments_mod0,
604  string_fragments_mod1,
605  string_fragments_mod2)
606  .Sort(dc3_local::FragmentComparator<StringFragment>())
607  .Execute();
608 
609  // debug output
610 
611  if (debug_print) {
612  std::vector<Char> input_vec = input_dia.Keep().AllGather();
613  std::vector<Index> vec =
614  suffix_array.Keep()
615  .Map([](const StringFragment& a) { return a.index; })
616  .Gather();
617 
618  if (ctx.my_rank() == 0) {
619  for (const Index& index : vec)
620  {
621  std::cout << std::setw(5) << index << " =";
622  for (Index i = index;
623  i < index + Index(64) && i < Index(input_size); ++i) {
624  std::cout << ' ' << input_vec[i];
625  }
626  std::cout << '\n';
627  }
628  }
629  }
630 
631  // check intermediate result, requires an input_dia.Keep() above!
632  // die_unless(CheckSA(input_dia, suffix_array.Keep()));
633 
634  return suffix_array.Collapse();
635 }
636 
637 template <typename Index, typename InputDIA>
638 DIA<Index> DC3(const InputDIA& input_dia, size_t input_size, size_t K) {
639 
640  using Char = typename InputDIA::ValueType;
641  using StringFragment = dc3_local::StringFragment<Index, Char>;
642 
643  return DC3Recursive<Index>(input_dia, input_size, K)
644  .Map([](const StringFragment& a) { return a.index; })
645  .Collapse();
646 }
647 
648 template DIA<uint32_t> DC3<uint32_t>(
649  const DIA<uint8_t>& input_dia, size_t input_size, size_t K);
650 
651 #if !THRILL_ON_TRAVIS
652 
653 template DIA<common::uint40> DC3<common::uint40>(
654  const DIA<uint8_t>& input_dia, size_t input_size, size_t K);
655 
656 template DIA<uint64_t> DC3<uint64_t>(
657  const DIA<uint8_t>& input_dia, size_t input_size, size_t K);
658 
659 #endif
660 
661 } // namespace suffix_sorting
662 } // namespace examples
663 
664 /******************************************************************************/
template DIA< uint32_t > DC3< uint32_t >(const DIA< uint8_t > &input_dia, size_t input_size, size_t K)
tlx::RingBuffer< Type, Allocator > RingBuffer
Definition: ring_buffer.hpp:21
static constexpr size_t fragment_comparator_params[3][3][3]
Definition: dc3.cpp:195
DIA< Index > DC3(const InputDIA &input_dia, size_t input_size, size_t K)
Definition: dc3.cpp:638
#define die_unless(X)
Definition: die.hpp:52
#define sLOG1
Definition: logger.hpp:188
const struct PadTag PadTag
global const PadTag instance
Definition: dia.hpp:83
Type
VFS object type.
Definition: file_io.hpp:52
auto Union(const FirstDIA &first_dia, const DIAs &...dias)
Union is a LOp, which creates the union of all items from any number of DIAs as a single DIA...
Definition: union.hpp:320
struct examples::suffix_sorting::dc3_local::Chars TLX_ATTRIBUTE_PACKED
static by_string to_string(int val)
convert to string
auto ZipWindow(const std::array< size_t, 1+sizeof...(DIAs)> &window_size, const ZipFunction &zip_function, const DIA< FirstDIAType, FirstDIAStack > &first_dia, const DIAs &...dias)
Zips two DIAs of equal size in style of functional programming by applying zip_function to the i-th f...
Definition: zip_window.hpp:619
static bool operator==(const std::string &a, const StringView &b) noexcept
DIA< dc3_local::StringFragment< Index, typename InputDIA::ValueType > > DC3Recursive(const InputDIA &input_dia, size_t input_size, size_t K)
Definition: dc3.cpp:282
template DIA< uint64_t > DC3< uint64_t >(const DIA< uint8_t > &input_dia, size_t input_size, size_t K)
list params
Definition: gen_data.py:30
const struct ArrayTag ArrayTag
global const ArrayTag instance
Definition: zip_window.hpp:48
const struct NoRebalanceTag NoRebalanceTag
global const NoRebalanceTag instance
Definition: dia.hpp:91
const struct DisjointTag DisjointTag
global const DisjointTag instance
Definition: dia.hpp:67
std::ostream & operator<<(std::ostream &os, const DIABase &d)
make ostream-able.
Definition: dia_base.cpp:448
SortAlgorithm class for use with api::Sort() which calls radix_sort_CI() if K is small enough...
Definition: radix_sort.hpp:146