Developer Documentation
OpenMesh::Utils::HeapT< HeapEntry, HeapInterface > Class Template Reference

#include <OSG/Utils/HeapT.hh>

Inheritance diagram for OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >:

Public Member Functions

 HeapT ()
 Constructor.
 
 HeapT (const HeapInterface &_interface)
 Construct with a given HeapIterface.
 
 ~HeapT ()
 Destructor.
 
HeapInterface & getInterface ()
 
const HeapInterface & getInterface () const
 
void clear ()
 clear the heap
 
bool empty () const
 is heap empty?
 
size_t size () const
 returns the size of heap
 
void reserve (size_t _n)
 reserve space for _n entries
 
void reset_heap_position (HeapEntry _h)
 reset heap position to -1 (not in heap)
 
bool is_stored (HeapEntry _h)
 is an entry in the heap?
 
void insert (HeapEntry _h)
 insert the entry _h
 
HeapEntry front () const
 get the first entry
 
void pop_front ()
 delete the first entry
 
void remove (HeapEntry _h)
 remove an entry
 
void update (HeapEntry _h)
 
bool check ()
 check heap condition
 

Protected Attributes

HeapInterface interface_
 Instance of HeapInterface.
 

Private Types

typedef std::vector< HeapEntry > Base
 
typedef std::vector< HeapEntry > HeapVector
 

Private Member Functions

void upheap (size_t _idx)
 Upheap. Establish heap property.
 
void downheap (size_t _idx)
 Downheap. Establish heap property.
 
HeapEntry entry (size_t _idx) const
 Get the entry at index _idx.
 
void entry (size_t _idx, HeapEntry _h)
 Set entry _h to index _idx and update _h's heap position.
 
size_t parent (size_t _i)
 Get parent's index.
 
size_t left (size_t _i)
 Get left child's index.
 
size_t right (size_t _i)
 Get right child's index.
 

Detailed Description

template<class HeapEntry, class HeapInterface = HeapEntry>
class OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >

An efficient, highly customizable heap.

The main difference (and performance boost) of this heap compared to e.g. the heap of the STL is that here the positions of the heap's elements are accessible from the elements themself. Therefore if one changes the priority of an element one does not have to remove and re-insert this element, but can just call the update(HeapEntry) method.

This heap class is parameterized by two template arguments:

  • the class HeapEntry, that will be stored in the heap
  • the HeapInterface telling the heap how to compare heap entries and how to store the heap positions in the heap entries.

As an example how to use the class see declaration of class Decimater::DecimaterT.

See also
HeapInterfaceT

Definition at line 138 of file HeapT.hh.

Member Function Documentation

◆ update()

template<class HeapEntry , class HeapInterface = HeapEntry>
void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::update ( HeapEntry  _h)
inline

update an entry: change the key and update the position to reestablish the heap property.

Definition at line 248 of file HeapT.hh.


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