tudocomp
– The TU Dortmund Compression Framework
SLPDepSort.hpp
Go to the documentation of this file.
1 #pragma once
2 
4 #include <queue>
5 
6 namespace tdc {namespace esp {
7  inline void slp_dep_sort(SLP& slp) {
8  std::vector<size_t> first_child;
9  first_child.reserve(slp.rules.size() + esp::GRAMMAR_PD_ELLIDED_PREFIX);
10  first_child.resize(slp.rules.size() + esp::GRAMMAR_PD_ELLIDED_PREFIX);
11  for (size_t i = 0; i < first_child.size(); i++) {
12  first_child[i] = i;
13  }
14 
15  std::vector<size_t> next_child;
16  next_child.reserve(slp.rules.size() + esp::GRAMMAR_PD_ELLIDED_PREFIX);
17  next_child.resize(slp.rules.size() + esp::GRAMMAR_PD_ELLIDED_PREFIX);
18  for (size_t i = 0; i < next_child.size(); i++) {
19  next_child[i] = i;
20  }
21 
22  auto append = [&](size_t i, size_t node) {
23  DCHECK_NE(i, node);
24  if (first_child[i] == i) {
25  first_child[i] = node;
26  } else {
27  auto old_next = first_child[i];
28  first_child[i] = node;
29  next_child[node] = old_next;
30  }
31  };
32 
33  auto for_all = [&](size_t i, auto f) {
34  size_t l = first_child[i];
35  if (l != i) {
36  f(l);
37  while (true) {
38  if (next_child[l] != l) {
39  l = next_child[l];
40  } else {
41  break;
42  }
43  f(l);
44  }
45  }
46  };
47 
48  for (size_t i = 0; i < slp.rules.size(); i++) {
49  auto j = slp.rules.size() - i - 1;
50  {
51  auto node = j + esp::GRAMMAR_PD_ELLIDED_PREFIX;
52  auto left_child = slp.rules[j][0];
53  append(left_child, node);
54  }
55  }
56 
57  std::vector<size_t> rename;
58  rename.reserve(slp.rules.size());
59  rename.resize(slp.rules.size());
60 
61  std::queue<size_t> queue;
62  for (size_t i = 0; i < 256; i++) {
63  queue.push(i);
64  }
65  size_t counter = 0;
66 
67  while (!queue.empty()) {
68  auto elem = queue.front();
69  queue.pop();
70  for_all(elem, [&](size_t child) {
71  queue.push(child);
72  });
73 
74  auto new_value = counter++;
75 
76  if (elem < 256) {
77  DCHECK_EQ(elem, new_value);
78  } else {
79  auto original_idx = elem - esp::GRAMMAR_PD_ELLIDED_PREFIX;
80  auto new_idx = new_value - esp::GRAMMAR_PD_ELLIDED_PREFIX;
81 
82  rename[original_idx] = new_idx;
83  }
84 
85  //std::cout << elem << ": " << new_value << "\n";
86  }
87 
88  {
89  auto discard = std::move(first_child);
90  discard = std::move(next_child);
91  }
92 
93  // TODO: Could save one n alloc here by renaming DL and DR after each other
94  std::vector<std::array<size_t, 2>> renamed_slp;
95  renamed_slp.reserve(slp.rules.size());
96  renamed_slp.resize(slp.rules.size());
97 
98  for (size_t i = 0; i < renamed_slp.size(); i++) {
99  renamed_slp[rename[i]] = slp.rules[i];
100  for (auto& e : renamed_slp[rename[i]]) {
101  if (e > 255) {
103  }
104  }
105  }
106 
107  slp.rules = std::move(renamed_slp);
108  if (slp.root_rule > 255) {
110  }
111  }
112 }}
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
std::vector< std::array< size_t, 2 > > rules
Definition: SLP.hpp:13
size_t GRAMMAR_PD_ELLIDED_PREFIX
Definition: SLP.hpp:10
size_t root_rule
Definition: SLP.hpp:14
void slp_dep_sort(SLP &slp)
Definition: SLPDepSort.hpp:7