#include <OSG/Utils/HeapT.hh>

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

Public Member Functions
	HeapT ()
	Constructor. More...

	HeapT (const HeapInterface &_interface)
	Construct with a given `HeapIterface`. More...

	~HeapT ()
	Destructor. More...

HeapInterface &	getInterface ()

const HeapInterface &	getInterface () const

void	clear ()
	clear the heap More...

bool	empty () const
	is heap empty? More...

size_t	size () const
	returns the size of heap More...

void	reserve (size_t _n)
	reserve space for _n entries More...

void	reset_heap_position (HeapEntry _h)
	reset heap position to -1 (not in heap) More...

bool	is_stored (HeapEntry _h)
	is an entry in the heap? More...

void	insert (HeapEntry _h)
	insert the entry _h More...

HeapEntry	front () const
	get the first entry More...

void	pop_front ()
	delete the first entry More...

void	remove (HeapEntry _h)
	remove an entry More...

void	update (HeapEntry _h)

bool	check ()
	check heap condition More...

Protected Attributes
HeapInterface	interface_
	Instance of HeapInterface. More...

Private Types
typedef std::vector< HeapEntry >	Base

typedef std::vector< HeapEntry >	HeapVector

Private Member Functions
void	upheap (size_t _idx)
	Upheap. Establish heap property. More...

void	downheap (size_t _idx)
	Downheap. Establish heap property. More...

HeapEntry	entry (size_t _idx) const
	Get the entry at index _idx. More...

void	entry (size_t _idx, HeapEntry _h)
	Set entry _h to index _idx and update _h's heap position. More...

size_t	parent (size_t _i)
	Get parent's index. More...

size_t	left (size_t _i)
	Get left child's index. More...

size_t	right (size_t _i)
	Get right child's index. More...

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 Typedef Documentation

◆ Base

template<class HeapEntry , class HeapInterface = HeapEntry>

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

private

Definition at line 141 of file HeapT.hh.

◆ HeapVector

template<class HeapEntry , class HeapInterface = HeapEntry>

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

private

Definition at line 284 of file HeapT.hh.

Constructor & Destructor Documentation

◆ HeapT() [1/2]

template<class HeapEntry , class HeapInterface = HeapEntry>

OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::HeapT ( )

inline

Constructor.

Definition at line 146 of file HeapT.hh.

◆ HeapT() [2/2]

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inlineexplicit

Construct with a given HeapIterface.

Definition at line 155 of file HeapT.hh.

◆ ~HeapT()

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

Destructor.

Definition at line 161 of file HeapT.hh.

Member Function Documentation

◆ check()

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

check heap condition

Definition at line 258 of file HeapT.hh.

◆ clear()

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

clear the heap

Definition at line 172 of file HeapT.hh.

◆ downheap()

template<class HeapEntry , class HeapInterface >

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::downheap ( size_t _idx )

private

Downheap. Establish heap property.

Definition at line 350 of file HeapT.hh.

◆ empty()

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

is heap empty?

Definition at line 175 of file HeapT.hh.

◆ entry() [1/2]

template<class HeapEntry , class HeapInterface = HeapEntry>

HeapEntry OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::entry ( size_t _idx ) const

inlineprivate

Get the entry at index _idx.

Definition at line 296 of file HeapT.hh.

◆ entry() [2/2]

template<class HeapEntry , class HeapInterface = HeapEntry>

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::entry	(	size_t	_idx,
		HeapEntry	_h
	)

inlineprivate

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

Definition at line 304 of file HeapT.hh.

◆ front()

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

get the first entry

Definition at line 199 of file HeapT.hh.

◆ getInterface() [1/2]

template<class HeapEntry , class HeapInterface = HeapEntry>

HeapInterface & OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::getInterface ( )

inline

Definition at line 163 of file HeapT.hh.

◆ getInterface() [2/2]

template<class HeapEntry , class HeapInterface = HeapEntry>

const HeapInterface & OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::getInterface ( ) const

inline

Definition at line 167 of file HeapT.hh.

◆ insert()

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

insert the entry _h

Definition at line 192 of file HeapT.hh.

◆ is_stored()

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

◆ left()

template<class HeapEntry , class HeapInterface = HeapEntry>

size_t OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::left ( size_t _i )

inlineprivate

Get left child's index.

Definition at line 315 of file HeapT.hh.

◆ parent()

template<class HeapEntry , class HeapInterface = HeapEntry>

size_t OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::parent ( size_t _i )

inlineprivate

Get parent's index.

Definition at line 313 of file HeapT.hh.

◆ pop_front()

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

delete the first entry

Definition at line 206 of file HeapT.hh.

◆ remove()

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

remove an entry

Definition at line 223 of file HeapT.hh.

◆ reserve()

template<class HeapEntry , class HeapInterface = HeapEntry>

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::reserve ( size_t _n )

inline

reserve space for _n entries

Definition at line 181 of file HeapT.hh.

◆ reset_heap_position()

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

◆ right()

template<class HeapEntry , class HeapInterface = HeapEntry>

size_t OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::right ( size_t _i )

inlineprivate

Get right child's index.

Definition at line 317 of file HeapT.hh.

◆ size()

template<class HeapEntry , class HeapInterface = HeapEntry>

size_t OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::size ( ) const

inline

returns the size of heap

Definition at line 178 of file HeapT.hh.

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

◆ upheap()

template<class HeapEntry , class HeapInterface >

void OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::upheap ( size_t _idx )

private

Upheap. Establish heap property.

Definition at line 329 of file HeapT.hh.

Member Data Documentation

◆ interface_

template<class HeapEntry , class HeapInterface = HeapEntry>

HeapInterface OpenMesh::Utils::HeapT< HeapEntry, HeapInterface >::interface_

protected

Instance of HeapInterface.

Definition at line 280 of file HeapT.hh.

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

OpenFlipper/libs_required/OpenMesh/src/OpenMesh/Tools/Utils/HeapT.hh

Public Member Functions

Protected Attributes

Private Types

Private Member Functions

Detailed Description

Member Typedef Documentation

◆ Base

◆ HeapVector

Constructor & Destructor Documentation

◆ HeapT() [1/2]

◆ HeapT() [2/2]

◆ ~HeapT()

Member Function Documentation

◆ check()

◆ clear()

◆ downheap()

◆ empty()

◆ entry() [1/2]

◆ entry() [2/2]

◆ front()

◆ getInterface() [1/2]

◆ getInterface() [2/2]

◆ insert()

◆ is_stored()

◆ left()

◆ parent()

◆ pop_front()

◆ remove()

◆ reserve()

◆ reset_heap_position()

◆ right()

◆ size()

◆ update()

◆ upheap()

Member Data Documentation

◆ interface_