tudocomp
– The TU Dortmund Compression Framework
ArrayMaxHeap.hpp
Go to the documentation of this file.
1 #pragma once
2 
3 #include <tudocomp/def.hpp>
4 #include <tudocomp/util.hpp>
6 
7 namespace tdc {
8 
16 template<typename array_t>
17 class ArrayMaxHeap {
18 
19 private:
20  enum perlocation_dir_t {
21  NONE,
22  LEFT,
23  RIGHT
24  };
25 
26  static inline len_t lc(len_t i) {
27  return 2*i+1;
28  }
29 
30  static inline len_t rc(len_t i) {
31  return 2*i+2;
32  }
33 
34  static inline len_t parent(len_t i) {
35  return (i-1)/2;
36  }
37 
38  // the array
39  array_t* m_array;
40 
41  // undefined position in heap
42  size_t m_undef;
43 
44  // heap
45  size_t m_size;
46  DynamicIntVector m_heap;
47 
48  // back mapping
49  DynamicIntVector m_pos;
50 
51  inline void put(size_t pos, len_t i) {
52  m_heap[pos] = i;
53  m_pos[i] = pos;
54  }
55 
56 public:
65  inline ArrayMaxHeap(array_t& array, const size_t array_size, const size_t heap_size)
66  : m_array(&array), m_size(0)
67  {
68  m_heap = DynamicIntVector(heap_size, 0, bits_for(array_size-1));
69  m_undef = heap_size;
70  m_pos = DynamicIntVector(array_size, m_undef, bits_for(m_undef));
71  }
72 
77  inline void insert(len_t i) {
78  DCHECK_EQ(m_pos[i], m_undef) << "trying to insert an item that's already in the heap";
79 
80  size_t pos = m_size++;
81 
82  // perlocate up
83  auto lcp_i = (*m_array)[i];
84  while(pos > 0 && lcp_i > (*m_array)[m_heap[parent(pos)]]) {
85  put(pos, m_heap[parent(pos)]);
86  pos = parent(pos);
87  }
88 
89  put(pos, i);
90 
91  IF_PARANOID({
92  DVLOG(2) << "checking heap after insert (size = " << m_size << ")";
93  check_heap_condition();
94  })
95  }
96 
97 private:
98  inline void perlocate_down(size_t pos, len_t k) {
99  auto lcp_k = (*m_array)[k];
100 
101  perlocation_dir_t dir = NONE;
102  do {
103  len_t lcp_lc = (lc(pos) < m_size) ? (*m_array)[m_heap[lc(pos)]] : 0;
104  len_t lcp_rc = (rc(pos) < m_size) ? (*m_array)[m_heap[rc(pos)]] : 0;
105 
106  // find perlocation direction
107  if(lcp_k < lcp_lc && lcp_k < lcp_rc) {
108  // both children are larger, pick the largest
109  dir = (lcp_lc > lcp_rc) ? LEFT : RIGHT;
110  } else if(lcp_k < lcp_lc) {
111  // go to the left
112  dir = LEFT;
113  } else if(lcp_k < lcp_rc) {
114  // go to the right
115  dir = RIGHT;
116  }
117  else if(lcp_k == lcp_lc && lcp_k == lcp_rc) {
118  // both children are larger, pick the smallest
119  dir = (lc(pos) < rc(pos)) ? LEFT : RIGHT;
120  } else if(lcp_k == lcp_lc && k > lc(pos)) {
121  // go to the left
122  dir = LEFT;
123  } else if(lcp_k == lcp_rc && k > rc(pos)) {
124  // go to the right
125  dir = RIGHT;
126  }
127  else {
128  dir = NONE;
129  }
130 
131 
132  // go down if necessary
133  if(dir == LEFT) {
134  // left
135  put(pos, m_heap[lc(pos)]);
136  pos = lc(pos);
137  } else if(dir == RIGHT) {
138  // right
139  put(pos, m_heap[rc(pos)]);
140  pos = rc(pos);
141  }
142  } while(dir != NONE);
143 
144  put(pos, k);
145  }
146 
147 public:
152  inline void remove(len_t i) {
153  size_t pos = m_pos[i];
154  if(pos != m_undef) { // never mind if it's not in the heap
155  // get last element in heap
156  auto k = m_heap[--m_size];
157 
158  // perlocate it down, starting at the former position of i
159  perlocate_down(pos, k);
160 
161  m_pos[i] = m_undef; // i was removed
162  }
163 
164  IF_PARANOID({
165  DVLOG(2) << "checking heap after remove (size = " << m_size << ")";
166  check_heap_condition();
167  })
168  }
169 
176  template<typename key_t>
177  inline void decrease_key(len_t i, key_t value) {
178  (*m_array)[i] = value;
179 
180  size_t pos = m_pos[i];
181  DCHECK_NE(pos, m_undef) << "trying to decrease_key on an item that's not in the heap";
182 
183  if(pos != m_undef) {
184  // perlocate item down, starting at its current position
185  perlocate_down(pos, i);
186  }
187 
188  IF_PARANOID({
189  DVLOG(2) << "checking heap after decrease_key (size = " << m_size << ")";
190  check_heap_condition();
191  })
192  }
193 
198  inline bool contains(len_t i) const {
199  return m_pos[i] != m_undef;
200  }
201 
204  inline size_t size() const {
205  return m_size;
206  }
207 
210  inline size_t get_max() const {
211  return m_heap[0];
212  }
213 
216  inline size_t top() const {
217  return get_max();
218  }
219 
224  inline len_t key(len_t i) const {
225  return (*m_array)[i];
226  }
227 
228  // for tests?
229  IF_DEBUG(
230  inline void check_heap_condition() const {
231  for(size_t i = 0; i < m_size; i++) {
232  auto value = (*m_array)[m_heap[i]];
233  if(lc(i) < m_size) DCHECK(value >= (*m_array)[m_heap[lc(i)]])
234  << "heap condition violated for a left child";
235  if(rc(i) < m_size) DCHECK(value >= (*m_array)[m_heap[rc(i)]])
236  << "heap condition violated for a right child";
237  }
238  })
239 };
240 
241 } //ns
242 
Contains the text compression and encoding framework.
Definition: namespaces.hpp:11
constexpr uint_fast8_t bits_for(size_t n)
Computes the number of bits required to store the given integer value.
A vector over arbitrary unsigned integer types.
Definition: IntVector.hpp:175
bool contains(len_t i) const
Checks whether or not an item is contained in this heap.
size_t top() const
Gets the top (first, maximum) item from the heap.
ArrayMaxHeap(array_t &array, const size_t array_size, const size_t heap_size)
Default constructor.
size_t size() const
Yields the number of items currently stored in the heap.
void insert(len_t i)
Inserts an item into the heap.
len_t key(len_t i) const
Gets an item&#39;s key.
fast_t< len_compact_t > len_t
Type to represent an length value.
Definition: def.hpp:114
len_compact_t pos
Definition: LZSSFactors.hpp:38
size_t get_max() const
Gets the first (maximum) item from the heap.
IntVector< dynamic_t > DynamicIntVector
Represents an integer vector with unspecified (dynamic) bit width.
Definition: IntVector.hpp:553
#define IF_PARANOID(x)
x is compiled only in debug builds and when the PARANOID macro is defined.
Definition: def.hpp:49
Represents a binary max heap backed by an external array of keys.
#define IF_DEBUG(x)
x is compiled only in debug builds.
Definition: def.hpp:32
void decrease_key(len_t i, key_t value)
Decreases the key of item in the heap.