tesseract::GenericHeap< Pair > Class Template Reference

#include <genericheap.h>

Public Member Functions
	GenericHeap ()
	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
bool	Pop (Pair *entry)
bool	PopWorst (Pair *entry)
void	Reshuffle (Pair *pair)

Detailed Description

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

Definition at line 58 of file genericheap.h.

Constructor & Destructor Documentation

template<typename Pair>

tesseract::GenericHeap< Pair >::GenericHeap ( )

inline

Definition at line 60 of file genericheap.h.

{}

template<typename Pair>

tesseract::GenericHeap< Pair >::GenericHeap ( int  initial_size )

inlineexplicit

Definition at line 63 of file genericheap.h.

                                         {
    heap_.reserve(initial_size);
  }

Member Function Documentation

template<typename Pair>

void tesseract::GenericHeap< Pair >::clear ( )

inline

Definition at line 77 of file genericheap.h.

               {
    // Clear truncates to 0 to keep the number reserved in tact.
    heap_.truncate(0);
  }

template<typename Pair>

bool tesseract::GenericHeap< Pair >::empty ( ) const

inline

Definition at line 68 of file genericheap.h.

                     {
    return heap_.empty();
  }

template<typename Pair>

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

inline

Definition at line 87 of file genericheap.h.

                                   {
    return heap_[index];
  }

template<typename Pair>

GenericVector<Pair>* tesseract::GenericHeap< Pair >::heap ( )

inline

Definition at line 83 of file genericheap.h.

                              {
    return &heap_;
  }

template<typename Pair>

const Pair& tesseract::GenericHeap< Pair >::PeekTop ( ) const

inline

Definition at line 108 of file genericheap.h.

                              {
    return heap_[0];
  }

template<typename Pair>

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

inline

Definition at line 116 of file genericheap.h.

                        {
    int new_size = heap_.size() - 1;
    if (new_size < 0)
      return false;  // Already empty.
    if (entry != NULL)
      *entry = heap_[0];
    if (new_size > 0) {
      // Sift the hole at the start of the heap_ downwards to match the last
      // element.
      Pair hole_pair = heap_[new_size];
      heap_.truncate(new_size);
      int hole_index = SiftDown(0, hole_pair);
      heap_[hole_index] = hole_pair;
    } else {
      heap_.truncate(new_size);
    }
    return true;
  }

template<typename Pair>

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

inline

Definition at line 138 of file genericheap.h.

                             {
    int heap_size = heap_.size();
    if (heap_size == 0) return false;  // It cannot be empty!

    // Find the maximum element. Its index is guaranteed to be greater than
    // the index of the parent of the last element, since by the heap invariant
    // the parent must be less than or equal to the children.
    int worst_index = heap_size - 1;
    int end_parent = ParentNode(worst_index);
    for (int i = worst_index - 1; i > end_parent; --i) {
      if (heap_[worst_index] < heap_[i])
        worst_index = i;
    }
    // Extract the worst element from the heap, leaving a hole at worst_index.
    if (entry != NULL)
      *entry = heap_[worst_index];
    --heap_size;
    if (heap_size > 0) {
      // Sift the hole upwards to match the last element of the heap_
      Pair hole_pair = heap_[heap_size];
      int hole_index = SiftUp(worst_index, hole_pair);
      heap_[hole_index] = hole_pair;
    }
    heap_.truncate(heap_size);
    return true;
  }

template<typename Pair>

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

inline

Definition at line 95 of file genericheap.h.

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

template<typename Pair>

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

inline

Definition at line 174 of file genericheap.h.

                             {
    int index = pair - &heap_[0];
    Pair hole_pair = heap_[index];
    index = SiftDown(index, hole_pair);
    index = SiftUp(index, hole_pair);
    heap_[index] = hole_pair;
  }

template<typename Pair>

int tesseract::GenericHeap< Pair >::size ( ) const

inline

Definition at line 71 of file genericheap.h.

                   {
    return heap_.size();
  }

template<typename Pair>

int tesseract::GenericHeap< Pair >::size_reserved ( ) const

inline

Definition at line 74 of file genericheap.h.

                            {
    return heap_.size_reserved();
  }

---

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

• ccutil/genericheap.h