Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
construct_bwt.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * examples/suffix_sorting/construct_bwt.hpp
3  *
4  * Part of Project Thrill - http://project-thrill.org
5  *
6  * Copyright (C) 2016 Florian Kurpicz <[email protected]>
7  *
8  * All rights reserved. Published under the BSD-2 license in the LICENSE file.
9  ******************************************************************************/
10 
11 #pragma once
12 #ifndef THRILL_EXAMPLES_SUFFIX_SORTING_CONSTRUCT_BWT_HEADER
13 #define THRILL_EXAMPLES_SUFFIX_SORTING_CONSTRUCT_BWT_HEADER
14 
15 #include <thrill/api/collapse.hpp>
16 #include <thrill/api/generate.hpp>
17 #include <thrill/api/max.hpp>
18 #include <thrill/api/size.hpp>
19 #include <thrill/api/sort.hpp>
20 #include <thrill/api/window.hpp>
21 #include <thrill/api/zip.hpp>
23 
24 namespace examples {
25 namespace suffix_sorting {
26 
27 template <typename InputDIA, typename SuffixArrayDIA>
28 InputDIA ConstructBWT(const InputDIA& input, const SuffixArrayDIA& suffix_array,
29  uint64_t input_size) {
30 
31  // thrill::Context& ctx = input.ctx();
32 
33  using Char = typename InputDIA::ValueType;
34  using Index = typename SuffixArrayDIA::ValueType;
35 
36  struct IndexRank {
37  Index index;
38  Index rank;
40 
41  struct IndexChar {
42  Index index;
43  Char ch;
45 
46  return suffix_array
47  .Map([input_size](const Index& i) {
48  if (i == Index(0))
49  return Index(input_size - 1);
50  return i - Index(1);
51  })
52  .ZipWithIndex([](const Index& text_pos, const size_t& i) {
53  return IndexRank { text_pos, Index(i) };
54  })
55  // .Zip(Generate(ctx, input_size),
56  // [](const Index& text_pos, const size_t& idx) {
57  // return IndexRank { text_pos, Index(idx) };
58  // })
59  .Sort([](const IndexRank& a, const IndexRank& b) {
60  return a.index < b.index;
61  })
62  .Zip(input,
63  [](const IndexRank& text_order, const Char& ch) {
64  return IndexChar { text_order.rank, ch };
65  })
66  .Sort([](const IndexChar& a, const IndexChar& b) {
67  return a.index < b.index;
68  })
69  .Map([](const IndexChar& ic) {
70  return ic.ch;
71  })
72  .Collapse();
73 }
74 
75 } // namespace suffix_sorting
76 } // namespace examples
77 
78 #endif // !THRILL_EXAMPLES_SUFFIX_SORTING_CONSTRUCT_BWT_HEADER
79 
80 /******************************************************************************/
auto Zip(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 e...
Definition: zip.hpp:424
struct examples::suffix_sorting::IndexRank TLX_ATTRIBUTE_PACKED
InputDIA ConstructBWT(const InputDIA &input, const SuffixArrayDIA &suffix_array, uint64_t input_size)