tesseract  5.0.0-alpha-619-ge9db
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  }

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  }

◆ 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>
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  }

◆ 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()]; }

◆ 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  }

◆ 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  }

The documentation for this class was generated from the following file:
GenericVector::back
T & back() const
Definition: genericvector.h:728
GenericVector::push_back
int push_back(T object)
Definition: genericvector.h:799
GenericVector::empty
bool empty() const
Definition: genericvector.h:86
GenericVector::size_reserved
int size_reserved() const
Definition: genericvector.h:81
GenericVector::reserve
void reserve(int size)
Definition: genericvector.h:679
GenericVector::truncate
void truncate(int size)
Definition: genericvector.h:132
GenericVector::size
int size() const
Definition: genericvector.h:71
tesseract::GenericHeap::IndexOfWorst
int IndexOfWorst() const
Definition: genericheap.h:158