RLib  5.7
RLib - an opensource, lightweight and multi-platform framework for cpp programming
System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator > Class Template Reference

Priority Queue More...

Public Types

typedef pqueue_pri_t(* pqueue_get_pri_f) (const data_t *a)
 
typedef void(* pqueue_set_pri_f) (data_t *a, pqueue_pri_t pri)
 
typedef int(* pqueue_cmp_pri_f) (pqueue_pri_t next, pqueue_pri_t curr)
 
typedef size_t(* pqueue_get_pos_f) (const data_t *a)
 
typedef void(* pqueue_set_pos_f) (data_t *a, size_t pos)
 
typedef int(* pqueue_iterator_f) (data_t *a, const data_t *user_data)
 

Public Member Functions

 PriorityQueue (size_t n, pqueue_cmp_pri_f cmppri, pqueue_get_pri_f getpri, pqueue_set_pri_f setpri, pqueue_get_pos_f getpos, pqueue_set_pos_f setpos)
 
 ~PriorityQueue ()
 
size_t pqueue_size ()
 
int pqueue_insert (data_t *d)
 
void pqueue_change_priority (pqueue_pri_t new_pri, data_t *d)
 
void * pqueue_pop ()
 
int pqueue_remove (data_t *d)
 
void * pqueue_peek ()
 
void * pqueue_iterate (pqueue_iterator_f iterator, const data_t *user_data)
 

Public Attributes

 RLIB_DECLARE_DYNCREATE
 
size_t size
 
size_t avail
 
size_t step
 
pqueue_cmp_pri_f cmppri
 
pqueue_get_pri_f getpri
 
pqueue_set_pri_f setpri
 
pqueue_get_pos_f getpos
 
pqueue_set_pos_f setpos
 
data_t ** d
 

Protected Member Functions

void bubble_up (size_t i)
 
size_t maxchild (size_t i)
 
void percolate_down (size_t i)
 
int subtree_is_valid (int pos)
 

Protected Attributes

struct {
   size_t   size
 
   size_t   avail
 
   size_t   step
 
   pqueue_cmp_pri_f   cmppri
 
   pqueue_get_pri_f   getpri
 
   pqueue_set_pri_f   setpri
 
   pqueue_get_pos_f   getpos
 
   pqueue_set_pos_f   setpos
 
   data_t **   d
 
}; 
 

Detailed Description

template<typename data_t, typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
class System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >

Priority Queue

Member Typedef Documentation

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
typedef size_t(* System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::pqueue_get_pos_f) (const data_t *a)

callback functions to get/set the position of an element

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
typedef pqueue_pri_t(* System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::pqueue_get_pri_f) (const data_t *a)

callback functions to get/set/compare the priority of an element

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
typedef int(* System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::pqueue_iterator_f) (data_t *a, const data_t *user_data)

callback function to iterate a entry

Constructor & Destructor Documentation

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::PriorityQueue ( size_t  n,
pqueue_cmp_pri_f  cmppri,
pqueue_get_pri_f  getpri,
pqueue_set_pri_f  setpri,
pqueue_get_pos_f  getpos,
pqueue_set_pos_f  setpos 
)
inline

initialize the queue

Parameters
nthe initial estimate of the number of queue items for which memory should be preallocated
cmppriThe callback function to run to compare two elements This callback should return 0 for 'lower' and non-zero for 'higher', or vice versa if reverse priority is desired
setprithe callback function to run to assign a score to an element
getprithe callback function to run to set a score to an element
getposthe callback function to get the current element's position
setposthe callback function to set the current element's position
template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::~PriorityQueue ( )
inline

free all memory used by the queue

Member Function Documentation

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
void System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::pqueue_change_priority ( pqueue_pri_t  new_pri,
data_t *  d 
)
inline

move an existing entry to a different priority

Parameters
new_prithe new priority
dthe entry
template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
int System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::pqueue_insert ( data_t *  d)
inline

insert an item into the queue.

Parameters
dthe item
Returns
0 on success
template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
void* System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::pqueue_iterate ( pqueue_iterator_f  iterator,
const data_t *  user_data 
)
inline

iterate the queue

Parameters
thecallback function to iterate the entry
template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
void* System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::pqueue_peek ( )
inline

access highest-ranking item without removing it.

Returns
NULL on error, otherwise the entry
template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
void* System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::pqueue_pop ( )
inline

pop the highest-ranking item from the queue.

Returns
NULL on error, otherwise the entry
template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
int System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::pqueue_remove ( data_t *  d)
inline

remove an item from the queue.

Parameters
dthe entry
Returns
0 on success
template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
size_t System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::pqueue_size ( )
inline

return the size of the queue.

Member Data Documentation

struct { ... }

the priority queue handle

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
size_t System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::avail

slots available in this queue

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
pqueue_cmp_pri_f System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::cmppri

callback to compare nodes

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
data_t** System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::d

The actualy queue in binary heap form

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
pqueue_get_pos_f System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::getpos

callback to get position of a node

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
pqueue_get_pri_f System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::getpri

callback to get priority of a node

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
pqueue_set_pos_f System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::setpos

callback to set position of a node

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
pqueue_set_pri_f System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::setpri

callback to set priority of a node

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
size_t System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::size

number of elements in this queue

template<typename data_t , typename pqueue_pri_t = unsigned long long, class allocator = IO::IAllocator>
size_t System::Collections::Generic::PriorityQueue< data_t, pqueue_pri_t, allocator >::step

growth stepping setting


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