22 #ifndef TESSERACT_CCUTIL_GENERICHEAP_H_ 23 #define TESSERACT_CCUTIL_GENERICHEAP_H_ 26 #include "genericvector.h" 57 template <
typename Pair>
87 const Pair&
get(
int index)
const {
103 hole_index =
SiftUp(hole_index, *entry);
104 heap_[hole_index] = *entry;
122 if (entry !=
nullptr)
127 Pair hole_pair =
heap_[new_size];
129 int hole_index =
SiftDown(0, hole_pair);
130 heap_[hole_index] = hole_pair;
142 if (worst_index < 0)
return false;
144 if (entry !=
nullptr)
145 *entry =
heap_[worst_index];
149 Pair hole_pair =
heap_[heap_size];
150 int hole_index =
SiftUp(worst_index, hole_pair);
151 heap_[hole_index] = hole_pair;
160 if (heap_size == 0)
return -1;
165 int worst_index = heap_size - 1;
167 for (
int i = worst_index - 1; i > end_parent; --i) {
168 if (
heap_[worst_index] <
heap_[i]) worst_index = i;
183 int index = pair - &
heap_[0];
184 Pair hole_pair = heap_[index];
186 index =
SiftUp(index, hole_pair);
187 heap_[index] = hole_pair;
194 int SiftUp(
int hole_index,
const Pair& pair) {
196 while (hole_index > 0 && pair <
heap_[parent =
ParentNode(hole_index)]) {
209 while ((child =
LeftChild(hole_index)) < heap_size) {
210 if (child + 1 < heap_size &&
heap_[child + 1] <
heap_[child])
212 if (
heap_[child] < pair) {
225 return (index + 1) / 2 - 1;
228 return index * 2 + 1;
237 #endif // TESSERACT_CCUTIL_GENERICHEAP_H_ Definition: genericheap.h:58
bool PopWorst(Pair *entry)
Definition: genericheap.h:140
void Reshuffle(Pair *pair)
Definition: genericheap.h:182
int SiftUp(int hole_index, const Pair &pair)
Definition: genericheap.h:194
int LeftChild(int index) const
Definition: genericheap.h:227
const Pair & PeekWorst() const
Definition: genericheap.h:112
int push_back(T object)
Definition: genericvector.h:799
int size_reserved() const
Definition: genericheap.h:74
void truncate(int size)
Definition: genericvector.h:136
Definition: baseapi.cpp:94
void clear()
Definition: genericheap.h:77
const Pair & PeekTop() const
Definition: genericheap.h:108
void Push(Pair *entry)
Definition: genericheap.h:95
int SiftDown(int hole_index, const Pair &pair)
Definition: genericheap.h:206
int IndexOfWorst() const
Definition: genericheap.h:158
int ParentNode(int index) const
Definition: genericheap.h:224
GenericHeap(int initial_size)
Definition: genericheap.h:63
T & back() const
Definition: genericvector.h:730
bool empty() const
Definition: genericheap.h:68
GenericVector< Pair > heap_
Definition: genericheap.h:232
int size() const
Definition: genericvector.h:71
int size() const
Definition: genericheap.h:71
bool Pop(Pair *entry)
Definition: genericheap.h:118
void reserve(int size)
Definition: genericvector.h:684
int size_reserved() const
Definition: genericvector.h:81
GenericVector< Pair > * heap()
Definition: genericheap.h:83
bool empty() const
Definition: genericvector.h:90