tudocomp
– The TU Dortmund Compression Framework
BlockAdjust.hpp
Go to the documentation of this file.
1 #pragma once
2 
4 
5 namespace tdc {namespace esp {
6  bool needs_merge(const TypedBlock& a) {
7  return a.len == 1;
8  };
9 
10  bool needs_merge(const TypedBlock& a, const TypedBlock& b) {
11  return a.len == 1 || b.len == 1;
12  };
13 
14  size_t merge(TypedBlock& a, TypedBlock& b, size_t type) {
15  if (a.len + b.len == 2) {
16  a.len = 2;
17  b.len = 2;
18  a.type = type;
19  b.type = type;
20  return 1;
21  } else if (a.len + b.len == 3) {
22  a.len = 3;
23  b.len = 3;
24  a.type = type;
25  b.type = type;
26  return 1;
27  } else if (a.len + b.len == 4) {
28  a.len = 2;
29  b.len = 2;
30  a.type = type;
31  b.type = type;
32  return 2;
33  } else {
34  DCHECK(false) << "should never happen";
35  return 0;
36  }
37  };
38 
39  void adjust_blocks(std::vector<TypedBlock>& blocks) {
40  if (blocks.size() < 2) return;
41 
42  auto adjust2 = [&](auto f) {
44  auto read_it = blocks.begin();
45  auto write_it = blocks.begin();
46 
47  auto fill = [&]() {
48  while ((!queue.full()) && (read_it != blocks.end())) {
49  queue.push_back(std::move(*read_it));
50  ++read_it;
51  }
52  };
53 
54  fill();
55  while(queue.view().size() > 0) {
56  // std::cout << "Adjust loop:\n";
57  // std::cout << " before: ";
58  // nice_block_lengths(queue.view(), std::cout) << "\n";
59  do {
60  fill();
61  //std::cout << " loop fill: ";
62  //nice_block_lengths(queue.view(), std::cout) << "\n";
63  } while(f(queue));
64  //std::cout << " after: ";
65  //nice_block_lengths(queue.view(), std::cout) << "\n";
66 
67  auto e = queue.pop_front();
68  *write_it = e;
69  ++write_it;
70  }
71 
72  size_t diff = read_it - write_it;
73  for (size_t i = 0; i < diff; i++) {
74  blocks.pop_back();
75  }
76  };
77 
78  adjust2([](auto& vec) {
79  auto v = vec.view();
80 
81  bool has_one = false;
82  for (auto& e : v) {
83  if (e.len == 1) {
84  has_one = true;
85  }
86  }
87 
88  if (!has_one) return false;
89 
90  if (v.size() == 3) {
91  auto& a = v[1];
92  auto& b = v[2];
93 
94  if (needs_merge(a, b) && a.type == 2 && b.type == 2) {
95  if (merge(a, b, 2) == 1) {
96  vec.pop_back();
97  }
98  return true;
99  }
100  }
101  if (v.size() >= 2) {
102  auto& a = v[0];
103  auto& b = v[1];
104 
105  if (needs_merge(a, b) && a.type == 2 && b.type == 2) {
106  if (merge(a, b, 2) == 1) {
107  vec.pop_front();
108  }
109  return true;
110  }
111  if (needs_merge(a, b) && a.type == 3) {
112  if (merge(a, b, 3) == 1) {
113  vec.pop_front();
114  }
115  return true;
116  }
117  if (needs_merge(a, b) && (a.type == 1 || b.type == 1)) {
118  if (merge(a, b, 1) == 1) {
119  vec.pop_front();
120  }
121  return true;
122  }
123  }
124 
125  // We did all we could do do far
126  if (v.size() > 0 && v[0].len > 1) {
127  return false;
128  }
129 
130  DCHECK(false) << "should not be reached";
131  return true;
132 
133  });
134  }
135 }}
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
bool needs_merge(const TypedBlock &a)
Definition: BlockAdjust.hpp:6
void adjust_blocks(std::vector< TypedBlock > &blocks)
Definition: BlockAdjust.hpp:39
size_t merge(TypedBlock &a, TypedBlock &b, size_t type)
Definition: BlockAdjust.hpp:14
GenericView< T > view()
Definition: FixedVector.hpp:36