#include <ACG/Utils/HeapT.hh>

Inheritance diagram for ACG::HeapT< HeapEntry, HeapInterface >:

Public Types
typedef std::vector< HeapEntry >	Base

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

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

	~HeapT ()
	Destructor. More...

void	clear ()
	clear the heap More...

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

unsigned int	size ()
	returns the size of heap More...

void	reserve (unsigned int _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 ()
	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...

Private Types
typedef std::vector< HeapEntry >	HeapVector

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

void	downheap (unsigned int _idx)
	Downheap. Establish heap property. More...

HeapEntry	entry (unsigned int _idx)
	Get the entry at index _idx. More...

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

unsigned int	parent (unsigned int _i)
	Get parent's index. More...

unsigned int	left (unsigned int _i)
	Get left child's index. More...

unsigned int	right (unsigned int _i)
	Get right child's index. More...

Private Attributes
HeapInterface	interface_
	Instance of HeapInterface. More...

Detailed Description

template<class HeapEntry, class HeapInterface = HeapEntry>
class ACG::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.

Definition at line 115 of file HeapT.hh.

Member Typedef Documentation

◆ Base

template<class HeapEntry , class HeapInterface = HeapEntry>

typedef std::vector<HeapEntry> ACG::HeapT< HeapEntry, HeapInterface >::Base

Definition at line 119 of file HeapT.hh.

◆ HeapVector

template<class HeapEntry , class HeapInterface = HeapEntry>

typedef std::vector<HeapEntry> ACG::HeapT< HeapEntry, HeapInterface >::HeapVector

private

Definition at line 230 of file HeapT.hh.

Constructor & Destructor Documentation

◆ HeapT() [1/2]

template<class HeapEntry , class HeapInterface = HeapEntry>

ACG::HeapT< HeapEntry, HeapInterface >::HeapT ( )

inline

Constructor.

Definition at line 123 of file HeapT.hh.

◆ HeapT() [2/2]

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

Construct with a given HeapIterface.

Definition at line 126 of file HeapT.hh.

◆ ~HeapT()

template<class HeapEntry , class HeapInterface = HeapEntry>

ACG::HeapT< HeapEntry, HeapInterface >::~HeapT ( )

inline

Destructor.

Definition at line 131 of file HeapT.hh.

Member Function Documentation

◆ check()

template<class HeapEntry , class HeapInterface = HeapEntry>

bool ACG::HeapT< HeapEntry, HeapInterface >::check ( )

inline

check heap condition

Definition at line 208 of file HeapT.hh.

◆ clear()

template<class HeapEntry , class HeapInterface = HeapEntry>

void ACG::HeapT< HeapEntry, HeapInterface >::clear ( )

inline

clear the heap

Definition at line 135 of file HeapT.hh.

◆ downheap()

template<class HeapEntry , class HeapInterface >

void ACG::HeapT< HeapEntry, HeapInterface >::downheap ( unsigned int _idx )

private

Downheap. Establish heap property.

Definition at line 298 of file HeapT.hh.

◆ empty()

template<class HeapEntry , class HeapInterface = HeapEntry>

bool ACG::HeapT< HeapEntry, HeapInterface >::empty ( )

inline

is heap empty?

Definition at line 138 of file HeapT.hh.

◆ entry() [1/2]

template<class HeapEntry , class HeapInterface = HeapEntry>

HeapEntry ACG::HeapT< HeapEntry, HeapInterface >::entry ( unsigned int _idx )

inlineprivate

Get the entry at index _idx.

Definition at line 242 of file HeapT.hh.

◆ entry() [2/2]

template<class HeapEntry , class HeapInterface = HeapEntry>

void ACG::HeapT< HeapEntry, HeapInterface >::entry	(	unsigned int	_idx,
		HeapEntry	_h
	)

inlineprivate

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

Definition at line 249 of file HeapT.hh.

◆ front()

template<class HeapEntry , class HeapInterface = HeapEntry>

HeapEntry ACG::HeapT< HeapEntry, HeapInterface >::front ( )

inline

get the first entry

Definition at line 158 of file HeapT.hh.

◆ insert()

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

insert the entry _h

Definition at line 155 of file HeapT.hh.

◆ is_stored()

template<class HeapEntry , class HeapInterface = HeapEntry>

bool ACG::HeapT< HeapEntry, HeapInterface >::is_stored ( HeapEntry _h )

inline

is an entry in the heap?

Definition at line 151 of file HeapT.hh.

◆ left()

template<class HeapEntry , class HeapInterface = HeapEntry>

unsigned int ACG::HeapT< HeapEntry, HeapInterface >::left ( unsigned int _i )

inlineprivate

Get left child's index.

Definition at line 259 of file HeapT.hh.

◆ parent()

template<class HeapEntry , class HeapInterface = HeapEntry>

unsigned int ACG::HeapT< HeapEntry, HeapInterface >::parent ( unsigned int _i )

inlineprivate

Get parent's index.

Definition at line 257 of file HeapT.hh.

◆ pop_front()

template<class HeapEntry , class HeapInterface = HeapEntry>

void ACG::HeapT< HeapEntry, HeapInterface >::pop_front ( )

inline

delete the first entry

Definition at line 161 of file HeapT.hh.

◆ remove()

template<class HeapEntry , class HeapInterface = HeapEntry>

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

inline

remove an entry

Definition at line 175 of file HeapT.hh.

◆ reserve()

template<class HeapEntry , class HeapInterface = HeapEntry>

void ACG::HeapT< HeapEntry, HeapInterface >::reserve ( unsigned int _n )

inline

reserve space for _n entries

Definition at line 144 of file HeapT.hh.

◆ reset_heap_position()

template<class HeapEntry , class HeapInterface = HeapEntry>

void ACG::HeapT< HeapEntry, HeapInterface >::reset_heap_position ( HeapEntry _h )

inline

reset heap position to -1 (not in heap)

Definition at line 147 of file HeapT.hh.

◆ right()

template<class HeapEntry , class HeapInterface = HeapEntry>

unsigned int ACG::HeapT< HeapEntry, HeapInterface >::right ( unsigned int _i )

inlineprivate

Get right child's index.

Definition at line 261 of file HeapT.hh.

◆ size()

template<class HeapEntry , class HeapInterface = HeapEntry>

unsigned int ACG::HeapT< HeapEntry, HeapInterface >::size ( )

inline

returns the size of heap

Definition at line 141 of file HeapT.hh.

◆ update()

template<class HeapEntry , class HeapInterface = HeapEntry>

void ACG::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 198 of file HeapT.hh.

◆ upheap()

template<class HeapEntry , class HeapInterface >

void ACG::HeapT< HeapEntry, HeapInterface >::upheap ( unsigned int _idx )

private

Upheap. Establish heap property.

Definition at line 276 of file HeapT.hh.

Member Data Documentation

◆ interface_

template<class HeapEntry , class HeapInterface = HeapEntry>

HeapInterface ACG::HeapT< HeapEntry, HeapInterface >::interface_

private

Instance of HeapInterface.

Definition at line 265 of file HeapT.hh.

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

OpenFlipper/libs_required/ACG/Utils/HeapT.hh

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

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()

◆ insert()

◆ is_stored()

◆ left()

◆ parent()

◆ pop_front()

◆ remove()

◆ reserve()

◆ reset_heap_position()

◆ right()

◆ size()

◆ update()

◆ upheap()

Member Data Documentation

◆ interface_