base::PriorityQueue< T > Class Template Reference

Fast, leak free, and controlled priority queue. More...

#include <PriorityQueue.h>

Inheritance diagram for base::PriorityQueue< T >:

List of all members.

Public Types
enum	{ DEC_ALLOC = 16 }
	If we want to have one allocation to fit on a page (4k), it is advisable to allocate slightly less than 4k for headers. More...
Public Member Functions
	PriorityQueue ()
	Constructor: initialize the heap (size 0).
	~PriorityQueue ()
	Destructor: update initial size & deallocate memory without calling any destructor.
void	push (const T &item)
	Push an item to the queue.
const T &	top () const
	Read the top element of the queue.
void	pop ()
	Remove the top element from the queue.
bool	empty () const
uint32_t	size () const
Private Member Functions
T *	alloc (uint32_t n)
void	ensureCapacity ()
	Ensure capacity for a new element to be added on the heap.
Private Attributes
uint32_t	capacity
	capacity of the heap
uint32_t	qsize
	size of the queue
T *	table
	table of items with a heap structure

---

Detailed Description

template<class T>
class base::PriorityQueue< T >

Fast, leak free, and controlled priority queue.

std::priority_queue is 20-30% slower. The difference with std::priority_queue is the ordering: here it is from lowest to highest, while in std::priority_queue it is from highest to lowest.

The element must be sortable and have a < comparison operator. Elements are copied and never destroyed. The algorithm is based on heaps. The the Introduction to Algorithms 2nd edition p130 for max-heapify and p140 for insertion. We use min instead of max, so invert the comparisons.

---

Member Enumeration Documentation

template<class T> anonymous enum

If we want to have one allocation to fit on a page (4k), it is advisable to allocate slightly less than 4k for headers. Enumeration values: DEC_ALLOC

---

Constructor & Destructor Documentation

template<class T> base::PriorityQueue< T >::PriorityQueue (   )  [inline]

Constructor: initialize the heap (size 0).

template<class T> base::PriorityQueue< T >::~PriorityQueue (   )  [inline]

Destructor: update initial size & deallocate memory without calling any destructor.

---

Member Function Documentation

template<class T> T* base::PriorityQueue< T >::alloc (  uint32_t  n  )  [inline, private]

Returns: allocated memory for T[n] without calling any constructor. Parameters: n,:  number of elements Precondition: T is int padded

template<class T> bool base::PriorityQueue< T >::empty (   )  const [inline]

Returns: true if the queue is empty, false otherwise.

template<class T> void base::PriorityQueue< T >::ensureCapacity (   )  [inline, private]

Ensure capacity for a new element to be added on the heap.

template<class T> void base::PriorityQueue< T >::pop (   )  [inline]

Remove the top element from the queue. Implement min-heapify (see max-heapify p130: Left(i) == l and Right(i) == l+1). Precondition: !empty()

template<class T> void base::PriorityQueue< T >::push (  const T &  item  )  [inline]

Push an item to the queue. Implements min-heap insert (p140). The original algorithm uses a swap, but it is to propagate the new item. Parameters: item,:  item to push. Precondition: item has a transitive < operator

template<class T> uint32_t base::PriorityQueue< T >::size (   )  const [inline]

Returns: the size of the queue.

template<class T> const T& base::PriorityQueue< T >::top (   )  const [inline]

Read the top element of the queue. It is the minimal one with respect to <

---

Member Data Documentation

template<class T> uint32_t base::PriorityQueue< T >::capacity [private]

capacity of the heap

template<class T> uint32_t base::PriorityQueue< T >::qsize [private]

size of the queue

template<class T> T* base::PriorityQueue< T >::table [private]

table of items with a heap structure

---

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

• /home/adavid/UPPAAL/trunk/server/modules/include/base/PriorityQueue.h

---