ug4
Public Member Functions | Private Member Functions | Private Attributes | List of all members
ug::BoxPriorityQueue< T > Class Template Reference

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

#include <boxsort.h>

Public Member Functions

size_t arr_size () const
 returns size of external array More...
 
 BoxPriorityQueue ()
 
 BoxPriorityQueue (const std::vector< T > &v)
 
 BoxPriorityQueue (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] More...
 
size_t get_max () const
 returns the index in m_arr of maximal element of the heap More...
 
size_t height () const
 returns nr of elements in the heap. More...
 
void insert_item (size_t i)
 
bool is_in (size_t i)
 
void remove (size_t i)
 removes index i in arr More...
 
size_t remove_max ()
 returns the index in arr of maximal element of the heap More...
 
void reset ()
 
void update (size_t i)
 
 ~BoxPriorityQueue ()
 deconstructor More...
 

Private Member Functions

 BoxPriorityQueue (const BoxPriorityQueue< T > &other)
 
void size_check (size_t i)
 

Private Attributes

const T * arr
 
stdvector< stdvector< size_t > > m_box
 
size_t m_height
 
stdvector< int > m_posInBox
 
size_t m_size
 
stdvector< size_t > m_values
 

Detailed Description

template<typename T>
class ug::BoxPriorityQueue< 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
Ttype 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

◆ BoxPriorityQueue() [1/4]

template<typename T >
ug::BoxPriorityQueue< T >::BoxPriorityQueue ( const BoxPriorityQueue< T > &  other)
private

◆ BoxPriorityQueue() [2/4]

template<typename T >
ug::BoxPriorityQueue< T >::BoxPriorityQueue ( )
inline

◆ BoxPriorityQueue() [3/4]

template<typename T >
ug::BoxPriorityQueue< T >::BoxPriorityQueue ( size_t  n,
const T *  arr_ 
)
inline

constructor

Parameters
nmaximal 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::BoxPriorityQueue< T >::create().

◆ BoxPriorityQueue() [4/4]

template<typename T >
ug::BoxPriorityQueue< T >::BoxPriorityQueue ( const std::vector< T > &  v)
inline

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

◆ ~BoxPriorityQueue()

template<typename T >
ug::BoxPriorityQueue< T >::~BoxPriorityQueue ( )
inline

deconstructor

Member Function Documentation

◆ arr_size()

template<typename T >
size_t ug::BoxPriorityQueue< T >::arr_size ( ) const
inline

returns size of external array

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

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

◆ create() [1/2]

template<typename T >
void ug::BoxPriorityQueue< T >::create ( const std::vector< T > &  v)
inline

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

◆ create() [2/2]

template<typename T >
void ug::BoxPriorityQueue< T >::create ( size_t  n,
const T *  arr_ 
)
inline

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

create

References ug::BoxPriorityQueue< T >::arr, ug::BoxPriorityQueue< T >::m_box, ug::BoxPriorityQueue< T >::m_height, ug::BoxPriorityQueue< T >::m_posInBox, ug::BoxPriorityQueue< T >::m_size, and ug::BoxPriorityQueue< T >::m_values.

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

◆ get_max()

template<typename T >
size_t ug::BoxPriorityQueue< T >::get_max ( ) const
inline

returns the index in m_arr of maximal element of the heap

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

◆ height()

template<typename T >
size_t ug::BoxPriorityQueue< T >::height ( ) const
inline

returns nr of elements in the heap.

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

◆ insert_item()

template<typename T >
void ug::BoxPriorityQueue< T >::insert_item ( size_t  i)
inline

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

Parameters
iindex of item in arr

References ug::BoxPriorityQueue< T >::arr, ug::BOXPRIORITYQUEUE_MAXIMAL_VALUE, ug::get_val(), ug::BoxPriorityQueue< T >::m_box, ug::BoxPriorityQueue< T >::m_height, ug::BoxPriorityQueue< T >::m_posInBox, ug::BoxPriorityQueue< T >::m_values, ug::BoxPriorityQueue< T >::size_check(), and UG_ASSERT.

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

◆ is_in()

template<typename T >
bool ug::BoxPriorityQueue< T >::is_in ( size_t  i)
inline

References ug::BoxPriorityQueue< T >::m_posInBox.

◆ remove()

template<typename T >
void ug::BoxPriorityQueue< T >::remove ( size_t  i)
inline

removes index i in arr

References ug::BoxPriorityQueue< T >::m_box, ug::BoxPriorityQueue< T >::m_height, ug::BoxPriorityQueue< T >::m_posInBox, ug::BoxPriorityQueue< T >::m_values, and ug::BoxPriorityQueue< T >::size_check().

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

◆ remove_max()

template<typename T >
size_t ug::BoxPriorityQueue< T >::remove_max ( )
inline

returns the index in arr of maximal element of the heap

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

◆ reset()

template<typename T >
void ug::BoxPriorityQueue< T >::reset ( )
inline

References ug::BoxPriorityQueue< T >::m_box.

◆ size_check()

template<typename T >
void ug::BoxPriorityQueue< T >::size_check ( size_t  i)
inlineprivate

debug print output

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

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

◆ update()

template<typename T >
void ug::BoxPriorityQueue< T >::update ( size_t  i)
inline
Parameters
iindex in arr for which to update

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

Member Data Documentation

◆ arr

template<typename T >
const T* ug::BoxPriorityQueue< T >::arr
private

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

◆ m_box

template<typename T >
stdvector<stdvector<size_t> > ug::BoxPriorityQueue< T >::m_box
private

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

◆ m_height

template<typename T >
size_t ug::BoxPriorityQueue< T >::m_height
private

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

◆ m_posInBox

template<typename T >
stdvector<int> ug::BoxPriorityQueue< T >::m_posInBox
private

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

◆ m_size

template<typename T >
size_t ug::BoxPriorityQueue< T >::m_size
private

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

◆ m_values

template<typename T >
stdvector<size_t> ug::BoxPriorityQueue< T >::m_values
private

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

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