tudocomp
– The TU Dortmund Compression Framework
landmarks.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 //#include <tudocomp/compressors/esp/>
4 
5 namespace tdc {namespace esp {
6  // TODO: Change to take iterator-like
7  template<class T>
8  bool check_landmarks(const T& t, bool allow_long = false) {
9  if (allow_long) return true;
10  size_t last = 0;
11  size_t i = 0;
12  for(; i < t.size(); i++) {
13  if (t[i] == 1u) {
14  if (i > 1) return false;
15  last = i;
16  i++;
17  break;
18  }
19  }
20  for(; i < t.size(); i++) {
21  if (t[i] == 1u) {
22  if ((i - last) > 3 || (i - last) < 2) return false;
23  last = i;
24  }
25  }
26  return true;
27  }
28 
29  template<typename LmPred, typename SpanPush>
30  void landmark_spanner(size_t size,
31  LmPred pred,
32  SpanPush push,
33  bool tie) {
34  struct Block {
35  size_t left;
36  size_t right;
37  inline size_t size() { return right - left + 1; }
38  };
39  std::array<Block, 2> blocks {{
40  {0, 0},
41  {0, 0},
42  }};
43  uint8_t bi = 0;
44 
45  for(size_t i = 0; i < size; i++) {
46  if (pred(i)) {
47  blocks[1].left = (i == 0) ? (i) : (i - 1);
48  blocks[1].right = (i == size - 1) ? (i) : (i + 1);
49  /*std::cout <<
50  "i: " << i << ", "
51  "old: (" << left << ", " << right << "), "
52  "new: (" << new_left << ", " << new_right << ")\n";*/
53 
54  if (bi > 0) {
55  // Adjust overlap of adjacent landmarks
56  if (blocks[1].left == blocks[0].right) {
57  if (tie) {
58  blocks[0].right--;
59  } else {
60  blocks[1].left++;
61  }
62  }
63  }
64 
65  if (bi == 0) {
66  bi = 1;
67  } else {
68  push(blocks[0].left, blocks[0].right);
69  }
70  for (size_t j = 0; j < 1; j++) {
71  blocks[j] = blocks[j + 1];
72  }
73  }
74  }
75  if (bi == 1) {
76  // entered at least once, one unused block
77  push(blocks[1].left, blocks[1].right);
78  }
79  }
80 }}
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
bool check_landmarks(const T &t, bool allow_long=false)
Definition: landmarks.hpp:8
void landmark_spanner(size_t size, LmPred pred, SpanPush push, bool tie)
Definition: landmarks.hpp:30