gsBoundedPriorityQueue< ValueType, T > Class Template Reference

Detailed Description

template<class ValueType, class T = real_t>
class gismo::gsBoundedPriorityQueue< ValueType, T >

An implementation of the bounded priority queue abstraction.

A bounded priority queue is in many ways like a regular priority queue. It stores a collection of elements tagged with a real- valued priority, and allows for access to the element whose priority is the smallest. However, unlike a regular priority queue, the number of elements in a bounded priority queue has a hard limit that is specified in the constructor. Whenever an element is added to the bounded priority queue such that the size exceeds the maximum, the element with the highest priority value will be ejected from the bounded priority queue. In this sense, a bounded priority queue is like a high score table for a video game that stores a fixed number of elements and deletes the least-important entry whenever a new value is inserted.

When creating a bounded priority queue, you must specify the maximum number of elements to store in the queue as an argument to the constructor.

For example:

gsBoundedPriorityQueue<int> bpq(15); // Holds up to fifteen values.

The maximum size of the bounded priority queue can be obtained using the maxSize() function, as in

size_t k = bpq.maxSize();

Beyond these restrictions, the bounded priority queue behaves similarly to other containers. You can query its size using size() and check whether it is empty using empty(). You can enqueue an element into the bounded priority queue by writing

bpq.enqueue(elem, priority);

Note that after enqueuing the element, there is no guarantee that the value will actually be in the queue. If the queue is full and the new element's priority exceeds the largest priority in the container, it will not be added.

You can dequeue elements from a bounded priority queue using the dequeueMin() function, as in

int val = bpq.dequeueMin();

The bounded priority queue also allows you to query the min and max priorities of the values in the queue. These values can be queried using the best() and worst() functions, which return the smallest and largest priorities in the queue, respectively.

Public Member Functions
void	print (std::ostream &os) const
	Prints the object as a string.

Friends
std::ostream &	operator<< (std::ostream &os, const gsBoundedPriorityQueue &obj)
	Print (as string) operator.