updateable priority queue class. this priority queue works on an external array of elements T. More...

#include <boxsort2.h>

Public Member Functions
size_t	arr_size () const
	returns size of external array

	BoxPriorityQueue2 ()

	BoxPriorityQueue2 (const std::vector< T > &v)

	BoxPriorityQueue2 (size_t n, const T *arr_)

void	create (const std::vector< T > &v)

void	create (size_t n, const T *arr_)
	creates the queue on a external array arr_[0]..arr_[n-1]

size_t	get_max () const
	returns the index in m_arr of maximal element of the heap

size_t	height () const
	returns nr of elements in the heap.

void	insert_item (size_t i)

bool	is_in (size_t i)

void	remove (size_t i)
	removes index i in arr

size_t	remove_max ()
	returns the index in arr of maximal element of the heap

void	reset ()

void	update (size_t i)

	~BoxPriorityQueue2 ()
	deconstructor

Private Member Functions
	BoxPriorityQueue2 (const BoxPriorityQueue2< T > &other)

void	size_check (size_t i)

Private Attributes
const T *	arr

stdvector< stdvector< size_t > >	m_box

stdvector< int >	m_boxBegin

stdvector< int >	m_boxEnd

size_t	m_height

stdvector< int >	m_next

stdvector< int >	m_prev

size_t	m_size

stdvector< size_t >	m_values

Detailed Description

template<typename T>
class ug::BoxPriorityQueue2< T >

updateable priority queue class. this priority queue works on an external array of elements T.

Note: none of the elements of m_arr[0]..m_arr[size-1] are in the queue at the begining. You can insert elements by using BoxPriorityQueue::insert_item(i);

Parameters

T	type of elements in the maxheap. Has to support size_t T::get_val() const, and get_val() has to be between 0 and and small number (for example, 500).

Elements are put in "boxes" depending on their get_val()-value - this makes sorting extremely easy: sorting and accessing is O(1), and inserting is maximal a) creation of enough boxes, and b) inserting into a box, so it is O(maximal get_val()). This algorithm is like a "radical" radix exchange sort.

Note: memory requirements are O(maximal get_val()) + O(size).; : in the current implementation, this is not a "stable" sort

Constructor & Destructor Documentation

◆ BoxPriorityQueue2() [1/4]

template<typename T >

ug::BoxPriorityQueue2< T >::BoxPriorityQueue2 ( const BoxPriorityQueue2< T > & other )

private

◆ BoxPriorityQueue2() [2/4]

template<typename T >

ug::BoxPriorityQueue2< T >::BoxPriorityQueue2 ( )

inline

◆ BoxPriorityQueue2() [3/4]

template<typename T >

ug::BoxPriorityQueue2< T >::BoxPriorityQueue2	(	size_t	n,
		const T *	arr_
	)

inline

constructor

Parameters

n	maximal number of elements
arr_	array with elements which are to compare. note that non of these are in the queue in the beginning

References ug::BoxPriorityQueue2< T >::create().

◆ BoxPriorityQueue2() [4/4]

template<typename T >

ug::BoxPriorityQueue2< T >::BoxPriorityQueue2 ( const std::vector< T > & v )

inline

References ug::BoxPriorityQueue2< T >::create().

◆ ~BoxPriorityQueue2()

template<typename T >

ug::BoxPriorityQueue2< T >::~BoxPriorityQueue2 ( )

inline

deconstructor

Member Function Documentation

◆ arr_size()

template<typename T >

size_t ug::BoxPriorityQueue2< T >::arr_size ( ) const

inline

returns size of external array

References ug::BoxPriorityQueue2< T >::m_size.

Referenced by ug::BoxPriorityQueue2< T >::size_check().

◆ create() [1/2]

template<typename T >

void ug::BoxPriorityQueue2< T >::create ( const std::vector< T > & v )

inline

References ug::BoxPriorityQueue2< T >::create().

◆ create() [2/2]

template<typename T >

void ug::BoxPriorityQueue2< T >::create	(	size_t	n,
		const T *	arr_
	)

inline

creates the queue on a external array arr_[0]..arr_[n-1]

create

References ug::BoxPriorityQueue2< T >::arr, ug::BoxPriorityQueue2< T >::m_next, ug::BoxPriorityQueue2< T >::m_prev, ug::BoxPriorityQueue2< T >::m_size, ug::BoxPriorityQueue2< T >::m_values, and ug::BoxPriorityQueue2< T >::reset().

Referenced by ug::BoxPriorityQueue2< T >::BoxPriorityQueue2(), ug::BoxPriorityQueue2< T >::BoxPriorityQueue2(), and ug::BoxPriorityQueue2< T >::create().

◆ get_max()

template<typename T >

size_t ug::BoxPriorityQueue2< T >::get_max ( ) const

inline

returns the index in m_arr of maximal element of the heap

References ug::BoxPriorityQueue2< T >::m_box, ug::BoxPriorityQueue2< T >::m_boxBegin, ug::BoxPriorityQueue2< T >::m_height, and UG_ASSERT.

◆ height()

template<typename T >

size_t ug::BoxPriorityQueue2< T >::height ( ) const

inline

returns nr of elements in the heap.

References ug::BoxPriorityQueue2< T >::m_height.

◆ insert_item()

template<typename T >

void ug::BoxPriorityQueue2< T >::insert_item ( size_t i )

inline

insertItem inserts Item arr[i] (see constructor) into heap

Parameters

i	index of item in arr

References ug::BoxPriorityQueue2< T >::arr, ug::BOXPRIORITYQUEUE2_MAXIMAL_VALUE, ug::BOXPRIORITYQUEUE_MAXIMAL_VALUE, ug::get_val(), ug::BoxPriorityQueue2< T >::is_in(), ug::BoxPriorityQueue2< T >::m_box, ug::BoxPriorityQueue2< T >::m_boxBegin, ug::BoxPriorityQueue2< T >::m_boxEnd, ug::BoxPriorityQueue2< T >::m_height, ug::BoxPriorityQueue2< T >::m_next, ug::BoxPriorityQueue2< T >::m_prev, ug::BoxPriorityQueue2< T >::m_values, ug::BoxPriorityQueue2< T >::size_check(), and UG_ASSERT.

Referenced by ug::BoxPriorityQueue2< T >::update().

◆ is_in()

template<typename T >

bool ug::BoxPriorityQueue2< T >::is_in ( size_t i )

inline

References ug::BoxPriorityQueue2< T >::m_prev.

Referenced by ug::BoxPriorityQueue2< T >::insert_item(), ug::BoxPriorityQueue2< T >::remove(), and ug::BoxPriorityQueue2< T >::update().

◆ remove()

template<typename T >

void ug::BoxPriorityQueue2< T >::remove ( size_t i )

inline

removes index i in arr

References ug::BoxPriorityQueue2< T >::is_in(), ug::BoxPriorityQueue2< T >::m_boxBegin, ug::BoxPriorityQueue2< T >::m_boxEnd, ug::BoxPriorityQueue2< T >::m_height, ug::BoxPriorityQueue2< T >::m_next, ug::BoxPriorityQueue2< T >::m_prev, ug::BoxPriorityQueue2< T >::m_values, ug::BoxPriorityQueue2< T >::size_check(), and UG_ASSERT.

Referenced by ug::BoxPriorityQueue2< T >::remove_max(), and ug::BoxPriorityQueue2< T >::update().

◆ remove_max()

template<typename T >

size_t ug::BoxPriorityQueue2< T >::remove_max ( )

inline

returns the index in arr of maximal element of the heap

References ug::BoxPriorityQueue2< T >::m_box, ug::BoxPriorityQueue2< T >::m_boxBegin, ug::BoxPriorityQueue2< T >::m_height, ug::BoxPriorityQueue2< T >::remove(), and UG_ASSERT.

◆ reset()

template<typename T >

void ug::BoxPriorityQueue2< T >::reset ( )

inline

References ug::BoxPriorityQueue2< T >::m_box, ug::BoxPriorityQueue2< T >::m_height, and ug::BoxPriorityQueue2< T >::m_prev.

Referenced by ug::BoxPriorityQueue2< T >::create().

◆ size_check()

template<typename T >

void ug::BoxPriorityQueue2< T >::size_check ( size_t i )

inlineprivate

debug print output

References ug::BoxPriorityQueue2< T >::arr_size(), and UG_ASSERT.

Referenced by ug::BoxPriorityQueue2< T >::insert_item(), and ug::BoxPriorityQueue2< T >::remove().

◆ update()

template<typename T >

void ug::BoxPriorityQueue2< T >::update ( size_t i )

inline

Parameters

i	index in arr for which to update

References ug::BoxPriorityQueue2< T >::arr, ug::get_val(), ug::BoxPriorityQueue2< T >::insert_item(), ug::BoxPriorityQueue2< T >::is_in(), ug::BoxPriorityQueue2< T >::m_values, and ug::BoxPriorityQueue2< T >::remove().

Member Data Documentation

◆ arr

template<typename T >

const T* ug::BoxPriorityQueue2< T >::arr

private

Referenced by ug::BoxPriorityQueue2< T >::create(), ug::BoxPriorityQueue2< T >::insert_item(), and ug::BoxPriorityQueue2< T >::update().

◆ m_box

template<typename T >

stdvector<stdvector<size_t> > ug::BoxPriorityQueue2< T >::m_box

private

Referenced by ug::BoxPriorityQueue2< T >::get_max(), ug::BoxPriorityQueue2< T >::insert_item(), ug::BoxPriorityQueue2< T >::remove_max(), and ug::BoxPriorityQueue2< T >::reset().

◆ m_boxBegin

template<typename T >

stdvector<int> ug::BoxPriorityQueue2< T >::m_boxBegin

private

Referenced by ug::BoxPriorityQueue2< T >::get_max(), ug::BoxPriorityQueue2< T >::insert_item(), ug::BoxPriorityQueue2< T >::remove(), and ug::BoxPriorityQueue2< T >::remove_max().

◆ m_boxEnd

template<typename T >

stdvector<int> ug::BoxPriorityQueue2< T >::m_boxEnd

private

Referenced by ug::BoxPriorityQueue2< T >::insert_item(), and ug::BoxPriorityQueue2< T >::remove().

◆ m_height

template<typename T >

size_t ug::BoxPriorityQueue2< T >::m_height

private

Referenced by ug::BoxPriorityQueue2< T >::get_max(), ug::BoxPriorityQueue2< T >::height(), ug::BoxPriorityQueue2< T >::insert_item(), ug::BoxPriorityQueue2< T >::remove(), ug::BoxPriorityQueue2< T >::remove_max(), and ug::BoxPriorityQueue2< T >::reset().

◆ m_next

template<typename T >

stdvector<int> ug::BoxPriorityQueue2< T >::m_next

private

Referenced by ug::BoxPriorityQueue2< T >::create(), ug::BoxPriorityQueue2< T >::insert_item(), and ug::BoxPriorityQueue2< T >::remove().

◆ m_prev

template<typename T >

stdvector<int> ug::BoxPriorityQueue2< T >::m_prev

private

Referenced by ug::BoxPriorityQueue2< T >::create(), ug::BoxPriorityQueue2< T >::insert_item(), ug::BoxPriorityQueue2< T >::is_in(), ug::BoxPriorityQueue2< T >::remove(), and ug::BoxPriorityQueue2< T >::reset().

◆ m_size

template<typename T >

size_t ug::BoxPriorityQueue2< T >::m_size

private

Referenced by ug::BoxPriorityQueue2< T >::arr_size(), and ug::BoxPriorityQueue2< T >::create().

◆ m_values

template<typename T >

stdvector<size_t> ug::BoxPriorityQueue2< T >::m_values

private

Referenced by ug::BoxPriorityQueue2< T >::create(), ug::BoxPriorityQueue2< T >::insert_item(), ug::BoxPriorityQueue2< T >::remove(), and ug::BoxPriorityQueue2< T >::update().

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

ugbase/lib_algebra/common/heap/boxsort2.h

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ BoxPriorityQueue2() [1/4]

◆ BoxPriorityQueue2() [2/4]

◆ BoxPriorityQueue2() [3/4]

◆ BoxPriorityQueue2() [4/4]

◆ ~BoxPriorityQueue2()

Member Function Documentation

◆ arr_size()

◆ create() [1/2]

◆ create() [2/2]

◆ get_max()

◆ height()

◆ insert_item()

◆ is_in()

◆ remove()

◆ remove_max()

◆ reset()

◆ size_check()

◆ update()

Member Data Documentation

◆ arr

◆ m_box

◆ m_boxBegin

◆ m_boxEnd

◆ m_height

◆ m_next

◆ m_prev

◆ m_size

◆ m_values