A heap priority queue. More...

#include <Heap.h>

Inheritance diagram for carl::Heap< C >:

Collaboration diagram for carl::Heap< C >:

[legend]

Data Structures
class	c_iterator

Public Types
using	Configuration = C

using	Entry = typename Configuration::Entry

using	const_iterator = c_iterator

Public Member Functions
	Heap (const Configuration &configuration)

Configuration &	getConfiguration ()

const Configuration &	getConfiguration () const

std::string	get_name () const

void	push (Entry entry)

void	push (const Entry begin, const Entry end)

Entry	pop ()

Entry	top () const

bool	empty () const

size_t	size () const

c_iterator	begin () const

c_iterator	end () const

std::vector< Entry >	getCopy () const

void	print (std::ostream &out=std::cout) const

void	decreaseTop (Entry newEntry)

void	decreasePos (Entry newEntry, c_iterator pos)

void	popPosition (c_iterator pos)

size_t	getMemoryUse () const

Private Types
using	Tree = CompactTree< Entry, Configuration::fastIndex >

using	Node = typename Tree::Node

Private Member Functions
Node	moveHoleDown (Node hole)

void	moveValueDown (Node pos, Entry value)

void	moveValueUp (Node pos, Entry value)

bool	isValid () const

Private Attributes
Tree	_tree

Configuration	_conf

Detailed Description

template<class C>
class carl::Heap< C >

A heap priority queue.

Configuration serves the same role as for Geobucket. It must have these fields that work as for Geobucket.

A type Entry A type CompareResult A const or static method: CompareResult compare(Entry, Entry) A const or static method: bool cmpLessThan(CompareResult) A static const bool supportDeduplication A static or const method: bool cmpEqual(CompareResult) A static or const method: Entry deduplicate(Entry a, Entry b)

It also has these additional fields:

A static const bool fastIndex If this field is true, then a faster way of calculating indexes is used. This requires sizeof(Entry) to be a power of two! This can be achieved by adding padding to Entry, but this class does not do that for you.

Definition at line 41 of file Heap.h.

Member Typedef Documentation

◆ Configuration

template<class C >

using carl::Heap< C >::Configuration = C

Definition at line 45 of file Heap.h.

◆ const_iterator

template<class C >

using carl::Heap< C >::const_iterator = c_iterator

Definition at line 182 of file Heap.h.

◆ Entry

template<class C >

using carl::Heap< C >::Entry = typename Configuration::Entry

Definition at line 46 of file Heap.h.

◆ Node

template<class C >

using carl::Heap< C >::Node = typename Tree::Node

private

Definition at line 115 of file Heap.h.

◆ Tree

template<class C >

using carl::Heap< C >::Tree = CompactTree<Entry, Configuration::fastIndex>

private

Definition at line 114 of file Heap.h.

Constructor & Destructor Documentation

◆ Heap()

template<class C >

carl::Heap< C >::Heap ( const Configuration & configuration )

inlineexplicit

Definition at line 48 of file Heap.h.

Member Function Documentation

◆ begin()

template<class C >

c_iterator carl::Heap< C >::begin ( ) const

inline

Definition at line 82 of file Heap.h.

◆ decreasePos()

template<class C >

void carl::Heap< C >::decreasePos	(	Entry	newEntry,
		c_iterator	pos
	)

◆ decreaseTop()

template<class C >

void carl::Heap< C >::decreaseTop ( Entry newEntry )

Definition at line 214 of file Heap.h.

◆ empty()

template<class C >

bool carl::Heap< C >::empty ( ) const

inline

Definition at line 72 of file Heap.h.

Here is the call graph for this function:

◆ end()

template<class C >

c_iterator carl::Heap< C >::end ( ) const

inline

Definition at line 87 of file Heap.h.

Here is the call graph for this function:

◆ get_name()

template<class C >

std::string carl::Heap< C >::get_name

Definition at line 192 of file Heap.h.

◆ getConfiguration() [1/2]

template<class C >

Configuration& carl::Heap< C >::getConfiguration ( )

inline

Definition at line 52 of file Heap.h.

◆ getConfiguration() [2/2]

template<class C >

const Configuration& carl::Heap< C >::getConfiguration ( ) const

inline

Definition at line 57 of file Heap.h.

◆ getCopy()

template<class C >

std::vector<Entry> carl::Heap< C >::getCopy ( ) const

inline

Definition at line 92 of file Heap.h.

Here is the call graph for this function:

◆ getMemoryUse()

template<class C >

size_t carl::Heap< C >::getMemoryUse

Definition at line 186 of file Heap.h.

◆ isValid()

template<class C >

bool carl::Heap< C >::isValid

private

Definition at line 330 of file Heap.h.

◆ moveHoleDown()

template<class C >

Heap< C >::Node carl::Heap< C >::moveHoleDown ( Node hole )

private

Definition at line 240 of file Heap.h.

Here is the caller graph for this function:

◆ moveValueDown()

template<class C >

void carl::Heap< C >::moveValueDown	(	Node	pos,
		Entry	value
	)

private

◆ moveValueUp()

template<class C >

void carl::Heap< C >::moveValueUp	(	Node	pos,
		Entry	value
	)

private

Definition at line 287 of file Heap.h.

Here is the caller graph for this function:

◆ pop()

template<class C >

Heap< C >::Entry carl::Heap< C >::pop

Definition at line 221 of file Heap.h.

◆ popPosition()

template<class C >

void carl::Heap< C >::popPosition ( c_iterator pos )

inline

Definition at line 102 of file Heap.h.

Here is the call graph for this function:

◆ print()

template<class C >

void carl::Heap< C >::print ( std::ostream & out = std::cout ) const

Definition at line 234 of file Heap.h.

◆ push() [1/2]

template<class C >

void carl::Heap< C >::push	(	const Entry *	begin,
		const Entry *	end
	)

Definition at line 207 of file Heap.h.

◆ push() [2/2]

template<class C >

void carl::Heap< C >::push ( Entry entry )

Definition at line 198 of file Heap.h.

◆ size()

template<class C >

size_t carl::Heap< C >::size ( ) const

inline

Definition at line 77 of file Heap.h.

Here is the call graph for this function:

◆ top()

template<class C >

Entry carl::Heap< C >::top ( ) const

inline

Definition at line 67 of file Heap.h.

Field Documentation

◆ _conf

template<class C >

Configuration carl::Heap< C >::_conf

private

Definition at line 124 of file Heap.h.

◆ _tree

template<class C >

Tree carl::Heap< C >::_tree

private

Definition at line 123 of file Heap.h.

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

carl-common/datastructures/Heap.h

Data Structures

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

template<class C> class carl::Heap< C >

Member Typedef Documentation

◆ Configuration

◆ const_iterator

◆ Entry

◆ Node

◆ Tree

Constructor & Destructor Documentation

◆ Heap()

Member Function Documentation

◆ begin()

◆ decreasePos()

◆ decreaseTop()

◆ empty()

◆ end()

◆ get_name()

◆ getConfiguration() [1/2]

◆ getConfiguration() [2/2]

◆ getCopy()

◆ getMemoryUse()

◆ isValid()

◆ moveHoleDown()

◆ moveValueDown()

◆ moveValueUp()

◆ pop()

◆ popPosition()

◆ print()

◆ push() [1/2]

◆ push() [2/2]

◆ size()

◆ top()

Field Documentation

◆ _conf

◆ _tree

template<class C>
class carl::Heap< C >