IndexHeap is a heap that allows changing of the elements. More...

#include <dynamic_priority_queue.h>

Classes
struct	extended_element
	store per element, whether it is empty and a link to the next empty element or to the heap location More...

Public Types
typedef T	element_type

Public Member Functions
	dynamic_priority_queue ()
	empty construction

void	clear ()
	remove all elements

bool	empty () const
	check if heap is empty

size_t	size () const
	return the number of elements in the heap

size_t	size_of_element_container () const
	return the number of elements in the heap

queue interface
unsigned int	top () const
	return the top element

void	pop ()
	remove top element

int	extract ()
	extract top element

dynamic element access
bool	is_empty (unsigned int idx) const

const element_type &	operator[] (unsigned int idx) const

element_type &	operator[] (unsigned int idx)

unsigned int	insert (const element_type &e)
	insert the given element and return its index in the element container

void	update (unsigned int idx)
	update after a change to the predicate

void	remove (unsigned int idx)
	remove element at location idx

Protected Member Functions
bool	valid (unsigned int hp) const
	check if a position is outside of range

void	updateLink (unsigned int hp)
	make sure that the link for hp is ok

bool	isBetter (unsigned int hp1, unsigned int hp2) const
	check if hp1 is less than hp2, if true, exchange elements

bool	exchangeIfBetter (unsigned int hp1, unsigned int hp2)
	check if hp1 is less than hp2, if true, exchange elements

void	heapify (unsigned int hp)

void	move (unsigned int hp1, unsigned int hp2)
	move one element to another position, that should be empty

void	removeHeap (unsigned int hp)
	remove an element on a certain heap pos

void	positionDownward (unsigned int &hp)
	move an element downward to the correct position

bool	positionUpward (unsigned int &hp)
	move an element upward to the correct position

Protected Attributes
std::vector< extended_element >	elements
	container for elements

int	last_empty_element
	store index of last empty element or -1 if there is non

std::vector< unsigned int >	heap
	store indices to the elements on the heap

Detailed Description

template<typename T>
class cgv::data::dynamic_priority_queue< T >

IndexHeap is a heap that allows changing of the elements.

Definition at line 9 of file dynamic_priority_queue.h.

Member Typedef Documentation

◆ element_type

template<typename T >

typedef T cgv::data::dynamic_priority_queue< T >::element_type

Definition at line 12 of file dynamic_priority_queue.h.

Constructor & Destructor Documentation

◆ dynamic_priority_queue()

template<typename T >

cgv::data::dynamic_priority_queue< T >::dynamic_priority_queue ( )

inline

empty construction

Definition at line 90 of file dynamic_priority_queue.h.

Member Function Documentation

◆ clear()

template<typename T >

void cgv::data::dynamic_priority_queue< T >::clear ( )

inline

remove all elements

Definition at line 92 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::elements, cgv::data::dynamic_priority_queue< T >::heap, and cgv::data::dynamic_priority_queue< T >::last_empty_element.

◆ empty()

template<typename T >

bool cgv::data::dynamic_priority_queue< T >::empty ( ) const

inline

check if heap is empty

Definition at line 94 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::heap.

◆ exchangeIfBetter()

template<typename T >

bool cgv::data::dynamic_priority_queue< T >::exchangeIfBetter	(	unsigned int	hp1,
		unsigned int	hp2
	)

inlineprotected

check if hp1 is less than hp2, if true, exchange elements

Definition at line 36 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::heap, cgv::data::dynamic_priority_queue< T >::isBetter(), and cgv::data::dynamic_priority_queue< T >::updateLink().

Referenced by cgv::data::dynamic_priority_queue< T >::positionDownward(), and cgv::data::dynamic_priority_queue< T >::positionUpward().

◆ extract()

template<typename T >

int cgv::data::dynamic_priority_queue< T >::extract ( )

inline

extract top element

Definition at line 107 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::pop(), and cgv::data::dynamic_priority_queue< T >::top().

◆ heapify()

template<typename T >

void cgv::data::dynamic_priority_queue< T >::heapify ( unsigned int hp )

inlineprotected

Definition at line 47 of file dynamic_priority_queue.h.

◆ insert()

template<typename T >

unsigned int cgv::data::dynamic_priority_queue< T >::insert ( const element_type & e )

inline

insert the given element and return its index in the element container

Definition at line 123 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::elements, cgv::data::dynamic_priority_queue< T >::heap, cgv::data::dynamic_priority_queue< T >::last_empty_element, cgv::data::dynamic_priority_queue< T >::positionUpward(), and cgv::data::dynamic_priority_queue< T >::updateLink().

◆ is_empty()

template<typename T >

bool cgv::data::dynamic_priority_queue< T >::is_empty ( unsigned int idx ) const

inline

Definition at line 118 of file dynamic_priority_queue.h.

◆ isBetter()

template<typename T >

bool cgv::data::dynamic_priority_queue< T >::isBetter	(	unsigned int	hp1,
		unsigned int	hp2
	)		const

inlineprotected

check if hp1 is less than hp2, if true, exchange elements

Definition at line 32 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::elements, and cgv::data::dynamic_priority_queue< T >::heap.

Referenced by cgv::data::dynamic_priority_queue< T >::exchangeIfBetter(), and cgv::data::dynamic_priority_queue< T >::positionDownward().

◆ move()

template<typename T >

void cgv::data::dynamic_priority_queue< T >::move	(	unsigned int	hp1,
		unsigned int	hp2
	)

inlineprotected

move one element to another position, that should be empty

Definition at line 49 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::heap, and cgv::data::dynamic_priority_queue< T >::updateLink().

Referenced by cgv::data::dynamic_priority_queue< T >::removeHeap().

◆ operator[]() [1/2]

template<typename T >

element_type & cgv::data::dynamic_priority_queue< T >::operator[] ( unsigned int idx )

inline

Definition at line 121 of file dynamic_priority_queue.h.

◆ operator[]() [2/2]

template<typename T >

const element_type & cgv::data::dynamic_priority_queue< T >::operator[] ( unsigned int idx ) const

inline

Definition at line 120 of file dynamic_priority_queue.h.

◆ pop()

template<typename T >

void cgv::data::dynamic_priority_queue< T >::pop ( )

inline

remove top element

Definition at line 105 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::remove(), and cgv::data::dynamic_priority_queue< T >::top().

Referenced by cgv::data::dynamic_priority_queue< T >::extract().

◆ positionDownward()

template<typename T >

void cgv::data::dynamic_priority_queue< T >::positionDownward ( unsigned int & hp )

inlineprotected

move an element downward to the correct position

Definition at line 66 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::exchangeIfBetter(), cgv::data::dynamic_priority_queue< T >::isBetter(), and cgv::data::dynamic_priority_queue< T >::valid().

◆ positionUpward()

template<typename T >

bool cgv::data::dynamic_priority_queue< T >::positionUpward ( unsigned int & hp )

inlineprotected

move an element upward to the correct position

Definition at line 77 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::exchangeIfBetter().

Referenced by cgv::data::dynamic_priority_queue< T >::insert().

◆ remove()

template<typename T >

void cgv::data::dynamic_priority_queue< T >::remove ( unsigned int idx )

inline

remove element at location idx

Definition at line 154 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::elements, cgv::data::dynamic_priority_queue< T >::last_empty_element, and cgv::data::dynamic_priority_queue< T >::removeHeap().

Referenced by cgv::data::dynamic_priority_queue< T >::pop().

◆ removeHeap()

template<typename T >

void cgv::data::dynamic_priority_queue< T >::removeHeap ( unsigned int hp )

inlineprotected

remove an element on a certain heap pos

Definition at line 55 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::heap, and cgv::data::dynamic_priority_queue< T >::move().

Referenced by cgv::data::dynamic_priority_queue< T >::remove().

◆ size()

template<typename T >

size_t cgv::data::dynamic_priority_queue< T >::size ( ) const

inline

return the number of elements in the heap

Definition at line 96 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::heap.

◆ size_of_element_container()

template<typename T >

size_t cgv::data::dynamic_priority_queue< T >::size_of_element_container ( ) const

inline

return the number of elements in the heap

Definition at line 98 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::elements.

◆ top()

template<typename T >

unsigned int cgv::data::dynamic_priority_queue< T >::top ( ) const

inline

return the top element

Definition at line 103 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::heap.

Referenced by cgv::data::dynamic_priority_queue< T >::extract(), and cgv::data::dynamic_priority_queue< T >::pop().

◆ update()

template<typename T >

void cgv::data::dynamic_priority_queue< T >::update ( unsigned int idx )

inline

update after a change to the predicate

Definition at line 148 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::elements.

◆ updateLink()

template<typename T >

void cgv::data::dynamic_priority_queue< T >::updateLink ( unsigned int hp )

inlineprotected

make sure that the link for hp is ok

Definition at line 30 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::elements, and cgv::data::dynamic_priority_queue< T >::heap.

Referenced by cgv::data::dynamic_priority_queue< T >::exchangeIfBetter(), cgv::data::dynamic_priority_queue< T >::insert(), and cgv::data::dynamic_priority_queue< T >::move().

◆ valid()

template<typename T >

bool cgv::data::dynamic_priority_queue< T >::valid ( unsigned int hp ) const

inlineprotected

check if a position is outside of range

Definition at line 28 of file dynamic_priority_queue.h.

References cgv::data::dynamic_priority_queue< T >::heap.

Referenced by cgv::data::dynamic_priority_queue< T >::positionDownward().

Member Data Documentation

◆ elements

template<typename T >

std::vector<extended_element> cgv::data::dynamic_priority_queue< T >::elements

protected

container for elements

Definition at line 22 of file dynamic_priority_queue.h.

Referenced by cgv::data::dynamic_priority_queue< T >::clear(), cgv::data::dynamic_priority_queue< T >::insert(), cgv::data::dynamic_priority_queue< T >::isBetter(), cgv::data::dynamic_priority_queue< T >::remove(), cgv::data::dynamic_priority_queue< T >::size_of_element_container(), cgv::data::dynamic_priority_queue< T >::update(), and cgv::data::dynamic_priority_queue< T >::updateLink().

◆ heap

template<typename T >

std::vector<unsigned int> cgv::data::dynamic_priority_queue< T >::heap

protected

store indices to the elements on the heap

Definition at line 26 of file dynamic_priority_queue.h.

◆ last_empty_element

template<typename T >

int cgv::data::dynamic_priority_queue< T >::last_empty_element

protected

store index of last empty element or -1 if there is non

Definition at line 24 of file dynamic_priority_queue.h.

Referenced by cgv::data::dynamic_priority_queue< T >::clear(), cgv::data::dynamic_priority_queue< T >::insert(), and cgv::data::dynamic_priority_queue< T >::remove().

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

cgv/data/dynamic_priority_queue.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ element_type

Constructor & Destructor Documentation

◆ dynamic_priority_queue()

Member Function Documentation

◆ clear()

◆ empty()

◆ exchangeIfBetter()

◆ extract()

◆ heapify()

◆ insert()

◆ is_empty()

◆ isBetter()

◆ move()

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ pop()

◆ positionDownward()

◆ positionUpward()

◆ remove()

◆ removeHeap()

◆ size()

◆ size_of_element_container()

◆ top()

◆ update()

◆ updateLink()

◆ valid()

Member Data Documentation

◆ elements

◆ heap

◆ last_empty_element