tesseract  5.0.0
tesseract::GenericHeap< Pair > Class Template Reference

#include <genericheap.h>

Public Member Functions

 GenericHeap ()=default
 
 GenericHeap (int initial_size)
 
bool empty () const
 
int size () const
 
int size_reserved () const
 
void clear ()
 
std::vector< Pair > & heap ()
 
const Pair & get (int index) const
 
void Push (Pair *entry)
 
const Pair & PeekTop () const
 
const Pair & PeekWorst () const
 
bool Pop (Pair *entry)
 
bool PopWorst (Pair *entry)
 
int IndexOfWorst () const
 
void Reshuffle (Pair *pair)
 

Detailed Description

template<typename Pair>
class tesseract::GenericHeap< Pair >

Definition at line 58 of file genericheap.h.

Constructor & Destructor Documentation

◆ GenericHeap() [1/2]

template<typename Pair >
tesseract::GenericHeap< Pair >::GenericHeap ( )
default

◆ GenericHeap() [2/2]

template<typename Pair >
tesseract::GenericHeap< Pair >::GenericHeap ( int  initial_size)
inlineexplicit

Definition at line 63 of file genericheap.h.

63  {
64  heap_.reserve(initial_size);
65  }

Member Function Documentation

◆ clear()

template<typename Pair >
void tesseract::GenericHeap< Pair >::clear ( )
inline

Definition at line 77 of file genericheap.h.

77  {
78  // Clear truncates to 0 to keep the number reserved in tact.
79  heap_.clear();
80  }

◆ empty()

template<typename Pair >
bool tesseract::GenericHeap< Pair >::empty ( ) const
inline

Definition at line 68 of file genericheap.h.

68  {
69  return heap_.empty();
70  }

◆ get()

template<typename Pair >
const Pair& tesseract::GenericHeap< Pair >::get ( int  index) const
inline

Definition at line 87 of file genericheap.h.

87  {
88  return heap_[index];
89  }

◆ heap()

template<typename Pair >
std::vector<Pair>& tesseract::GenericHeap< Pair >::heap ( )
inline

Definition at line 83 of file genericheap.h.

83  {
84  return heap_;
85  }

◆ IndexOfWorst()

template<typename Pair >
int tesseract::GenericHeap< Pair >::IndexOfWorst ( ) const
inline

Definition at line 165 of file genericheap.h.

165  {
166  int heap_size = heap_.size();
167  if (heap_size == 0) {
168  return -1; // It cannot be empty!
169  }
170 
171  // Find the maximum element. Its index is guaranteed to be greater than
172  // the index of the parent of the last element, since by the heap invariant
173  // the parent must be less than or equal to the children.
174  int worst_index = heap_size - 1;
175  int end_parent = ParentNode(worst_index);
176  for (int i = worst_index - 1; i > end_parent; --i) {
177  if (heap_[worst_index] < heap_[i]) {
178  worst_index = i;
179  }
180  }
181  return worst_index;
182  }

◆ PeekTop()

template<typename Pair >
const Pair& tesseract::GenericHeap< Pair >::PeekTop ( ) const
inline

Definition at line 108 of file genericheap.h.

108  {
109  return heap_[0];
110  }

◆ PeekWorst()

template<typename Pair >
const Pair& tesseract::GenericHeap< Pair >::PeekWorst ( ) const
inline

Definition at line 112 of file genericheap.h.

112  {
113  return heap_[IndexOfWorst()];
114  }
int IndexOfWorst() const
Definition: genericheap.h:165

◆ Pop()

template<typename Pair >
bool tesseract::GenericHeap< Pair >::Pop ( Pair *  entry)
inline

Definition at line 120 of file genericheap.h.

120  {
121  int new_size = heap_.size() - 1;
122  if (new_size < 0) {
123  return false; // Already empty.
124  }
125  if (entry != nullptr) {
126  *entry = heap_[0];
127  }
128  if (new_size > 0) {
129  // Sift the hole at the start of the heap_ downwards to match the last
130  // element.
131  Pair hole_pair = heap_[new_size];
132  heap_.resize(new_size);
133  int hole_index = SiftDown(0, hole_pair);
134  heap_[hole_index] = hole_pair;
135  } else {
136  heap_.resize(new_size);
137  }
138  return true;
139  }

◆ PopWorst()

template<typename Pair >
bool tesseract::GenericHeap< Pair >::PopWorst ( Pair *  entry)
inline

Definition at line 144 of file genericheap.h.

144  {
145  int worst_index = IndexOfWorst();
146  if (worst_index < 0) {
147  return false; // It cannot be empty!
148  }
149  // Extract the worst element from the heap, leaving a hole at worst_index.
150  if (entry != nullptr) {
151  *entry = heap_[worst_index];
152  }
153  int heap_size = heap_.size() - 1;
154  if (heap_size > 0) {
155  // Sift the hole upwards to match the last element of the heap_
156  Pair hole_pair = heap_[heap_size];
157  int hole_index = SiftUp(worst_index, hole_pair);
158  heap_[hole_index] = hole_pair;
159  }
160  heap_.resize(heap_size);
161  return true;
162  }

◆ Push()

template<typename Pair >
void tesseract::GenericHeap< Pair >::Push ( Pair *  entry)
inline

Definition at line 95 of file genericheap.h.

95  {
96  int hole_index = heap_.size();
97  // Make a hole in the end of heap_ and sift it up to be the correct
98  // location for the new *entry. To avoid needing a default constructor
99  // for primitive types, and to allow for use of DoublePtr in the Pair
100  // somewhere, we have to incur a double copy here.
101  heap_.push_back(*entry);
102  *entry = heap_.back();
103  hole_index = SiftUp(hole_index, *entry);
104  heap_[hole_index] = *entry;
105  }

◆ Reshuffle()

template<typename Pair >
void tesseract::GenericHeap< Pair >::Reshuffle ( Pair *  pair)
inline

Definition at line 193 of file genericheap.h.

193  {
194  int index = pair - &heap_[0];
195  Pair hole_pair = heap_[index];
196  index = SiftDown(index, hole_pair);
197  index = SiftUp(index, hole_pair);
198  heap_[index] = hole_pair;
199  }

◆ size()

template<typename Pair >
int tesseract::GenericHeap< Pair >::size ( ) const
inline

Definition at line 71 of file genericheap.h.

71  {
72  return heap_.size();
73  }

◆ size_reserved()

template<typename Pair >
int tesseract::GenericHeap< Pair >::size_reserved ( ) const
inline

Definition at line 74 of file genericheap.h.

74  {
75  return heap_.size_reserved();
76  }

The documentation for this class was generated from the following file: