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

#include <OSG/Utils/HeapT.hh>

Public Member Functions
bool	check ()
	check heap condition
void	clear ()
	clear the heap
bool	empty () const
	is heap empty?
HeapEntry	front () const
	get the first entry
	HeapT (const HeapInterface &_interface)
	Construct with a given `HeapIterface`.
	HeapT ()
	Constructor.
void	insert (HeapEntry _h)
	insert the entry _h
bool	is_stored (HeapEntry _h)
	is an entry in the heap?
void	pop_front ()
	delete the first entry
void	remove (HeapEntry _h)
	remove an entry
void	reserve (unsigned int _n)
	reserve space for _n entries
void	reset_heap_position (HeapEntry _h)
	reset heap position to -1 (not in heap)
unsigned int	size () const
	returns the size of heap
void	update (HeapEntry _h)
	~HeapT ()
	Destructor.
Protected Attributes
HeapInterface	interface_
	Instance of HeapInterface.
Private Types
typedef std::vector< HeapEntry >	Base
typedef std::vector< HeapEntry >	HeapVector
Private Member Functions
void	downheap (unsigned int _idx)
	Downheap. Establish heap property.
void	entry (unsigned int _idx, HeapEntry _h)
	Set entry _h to index _idx and update _h's heap position.
HeapEntry	entry (unsigned int _idx) const
	Get the entry at index _idx.
unsigned int	left (unsigned int _i)
	Get left child's index.
unsigned int	parent (unsigned int _i)
	Get parent's index.
unsigned int	right (unsigned int _i)
	Get right child's index.
void	upheap (unsigned int _idx)
	Upheap. Establish heap property.

Detailed Description

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

An efficient, highly customizable heap.

The main difference (and performace boost) of this heap compared to e.g. the heap of the STL is that here to 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 127 of file HeapT.hh.

Member Typedef Documentation

template<class HeapEntry , class HeapInterface = HeapEntry>

typedef std::vector<HeapEntry> OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::Base [private]

Definition at line 130 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

typedef std::vector<HeapEntry> OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::HeapVector [private]

Definition at line 259 of file HeapT.hh.

Constructor & Destructor Documentation

template<class HeapEntry , class HeapInterface = HeapEntry>

OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::HeapT ( ) [inline]

Constructor.

Definition at line 135 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::HeapT ( const HeapInterface & _interface ) [inline]

Construct with a given HeapIterface.

Definition at line 138 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::~HeapT ( ) [inline]

Destructor.

Definition at line 143 of file HeapT.hh.

Member Function Documentation

template<class HeapEntry , class HeapInterface = HeapEntry>

bool OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::check ( ) [inline]

check heap condition

Definition at line 233 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::clear ( void ) [inline]

clear the heap

Definition at line 147 of file HeapT.hh.

template<class HeapEntry , class HeapInterface >

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::downheap ( unsigned int _idx ) [inline, private]

Downheap. Establish heap property.

Definition at line 327 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

bool OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::empty ( ) const [inline]

is heap empty?

Definition at line 150 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::entry	(	unsigned int	_idx,
		HeapEntry	_h
	)			`[inline, private]`

Set entry _h to index _idx and update _h's heap position.

Definition at line 279 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

HeapEntry OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::entry ( unsigned int _idx ) const [inline, private]

Get the entry at index _idx.

Definition at line 271 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

HeapEntry OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::front ( ) const [inline]

get the first entry

Definition at line 174 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::insert ( HeapEntry _h ) [inline]

insert the entry _h

Definition at line 167 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

bool OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::is_stored ( HeapEntry _h ) [inline]

is an entry in the heap?

Definition at line 163 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

unsigned int OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::left ( unsigned int _i ) [inline, private]

Get left child's index.

Definition at line 290 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

unsigned int OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::parent ( unsigned int _i ) [inline, private]

Get parent's index.

Definition at line 288 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::pop_front ( ) [inline]

delete the first entry

Definition at line 181 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::remove ( HeapEntry _h ) [inline]

remove an entry

Definition at line 198 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::reserve ( unsigned int _n ) [inline]

reserve space for _n entries

Definition at line 156 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::reset_heap_position ( HeapEntry _h ) [inline]

reset heap position to -1 (not in heap)

Definition at line 159 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

unsigned int OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::right ( unsigned int _i ) [inline, private]

Get right child's index.

Definition at line 292 of file HeapT.hh.

template<class HeapEntry , class HeapInterface = HeapEntry>

unsigned int OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::size ( ) const [inline]

returns the size of heap

Definition at line 153 of file HeapT.hh.

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 223 of file HeapT.hh.

template<class HeapEntry , class HeapInterface >

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::upheap ( unsigned int _idx ) [inline, private]

Upheap. Establish heap property.

Definition at line 305 of file HeapT.hh.

Member Data Documentation

template<class HeapEntry , class HeapInterface = HeapEntry>

HeapInterface OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::interface_ [protected]

Instance of HeapInterface.

Definition at line 255 of file HeapT.hh.

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

HeapT.hh

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

Public Member Functions

Protected Attributes

Private Types

Private Member Functions

Detailed Description

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

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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