BoundedPQueue.h Bounded Priority Queue

BoundedPQueue.h

#ifndef BOUNDED_PRIORITY_QUEUE_H
#define BOUNDED_PRIORITY_QUEUE_H

#include <map>
#include <functional>
#include <limits>
#include <utility>

template<typename T, typename Comparator=std::less<T> >
class BoundedPQueue{
public:
	explicit BoundedPQueue(size_t maxSize, Comparator c=Comparator());
	
	void Enqueue(const T& elem, double priority);
	const T& DequeueMin();
	double Best();
	double Worst();
	size_t Size() const;
	size_t MaxSize() const;
	bool Empty() const;
private:
	std::multimap<double, T, Comparator> m_queue;
	size_t m_maxSize;
};

template<typename T, typename Comparator>
BoundedPQueue<T, Comparator>::BoundedPQueue(size_t maxSize, Comparator c) : m_maxSize(maxSize), m_queue(c) {}

template<typename T, typename Comparator>
void BoundedPQueue<T, Comparator>::Enqueue(const T& elem, double priority)
{
	if (m_queue.size()==m_maxSize && m_queue.key_comp()(Worst(), priority))
		return;

	m_queue.insert(std::make_pair(priority, elem));  //member is ordered

	if (m_queue.size()>m_maxSize)
	{
		std::multimap<double, T, Comparator>::iterator last = m_queue.end();
		last--;
		m_queue.erase(last);  //delete highest-priority element
	}
}

template<typename T, typename Comparator>
const T& BoundedPQueue<T, Comparator>::DequeueMin()
{
	T result = m_queue.begin()->second;
	m_queue.erase(m_queue.begin());
	return result;
}

template<typename T, typename Comparator>
double BoundedPQueue<T, Comparator>::Best()
{
	return m_queue.empty() ? std::numeric_limits<double>::infinity() : m_queue.begin()->first;
}

template<typename T, typename Comparator>
double BoundedPQueue<T, Comparator>::Worst()
{
	return m_queue.empty() ? std::numeric_limits<double>::infinity() : m_queue.rbegin()->first;
}

template<typename T, typename Comparator>
size_t BoundedPQueue<T, Comparator>::Size() const
{
	return m_queue.size();
}

template<typename T, typename Comparator>
size_t BoundedPQueue<T, Comparator>::MaxSize() const
{
	return m_maxSize;
}

template<typename T, typename Comparator>
bool BoundedPQueue<T, Comparator>::Empty() const
{
	return m_queue.empty();
}
#endif