tesseract 4.1.1
Loading...
Searching...
No Matches
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 ()
 
GenericVector< 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 }
void reserve(int size)

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_.truncate(0);
80 }
void truncate(int size)

◆ 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 }
bool empty() const
Definition: genericvector.h:91

◆ 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 >
GenericVector< 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 158 of file genericheap.h.

158 {
159 int heap_size = heap_.size();
160 if (heap_size == 0) return -1; // It cannot be empty!
161
162 // Find the maximum element. Its index is guaranteed to be greater than
163 // the index of the parent of the last element, since by the heap invariant
164 // the parent must be less than or equal to the children.
165 int worst_index = heap_size - 1;
166 int end_parent = ParentNode(worst_index);
167 for (int i = worst_index - 1; i > end_parent; --i) {
168 if (heap_[worst_index] < heap_[i]) worst_index = i;
169 }
170 return worst_index;
171 }
int size() const
Definition: genericvector.h:72

◆ 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{ return heap_[IndexOfWorst()]; }
int IndexOfWorst() const
Definition: genericheap.h:158

◆ Pop()

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

Definition at line 118 of file genericheap.h.

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

◆ PopWorst()

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

Definition at line 140 of file genericheap.h.

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

◆ 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 }
int push_back(T object)
T & back() const

◆ Reshuffle()

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

Definition at line 182 of file genericheap.h.

182 {
183 int index = pair - &heap_[0];
184 Pair hole_pair = heap_[index];
185 index = SiftDown(index, hole_pair);
186 index = SiftUp(index, hole_pair);
187 heap_[index] = hole_pair;
188 }

◆ 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 }
int size_reserved() const
Definition: genericvector.h:82

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