/**************************************************************
* File: BoundedPQueue.h
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* 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:
*
* BoundedPQueue<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.
*/

#ifndef BoundedPQueue_Included
#define BoundedPQueue_Included

#include <map>        // For std::multimap
#include <limits>     // For std::numeric_limits
#include <functional> // For std::less
#include <stdlib.h>   // For size_t

template <typename T, typename Comparator = std::less<T> >
class BoundedPQueue {
public:
/* Constructor: BoundedPQueue(size_t maxSize);
* Usage: BoundedPQueue<int> bpq(15);
* --------------------------------------------------
* Constructs a new, empty BoundedPQueue with
* maximum size equal to the constructor argument.
*/

explicit BoundedPQueue(size_t maxSize, Comparator comp = Comparator());

/* void enqueue(const T& value, double priority);
* Usage: bpq.enqueue("Hi!", 2.71828);
* --------------------------------------------------
* Enqueues a new element into the BoundedPQueue with
* the specified priority.  If this overflows the maximum
* size of the queue, the element with the highest
* priority will be deleted from the queue.  Note that
* this might be the element that was just added.
*/

void enqueue(const T& value, double priority);

/* T dequeueMin();
* Usage: int val = bpq.dequeueMin();
* --------------------------------------------------
* Returns the element from the BoundedPQueue with the
* smallest priority value, then removes that element
* from the queue.
*/

T dequeueMin();

/* size_t size() const;
* bool  empty() const;
* Usage: while (!bpq.empty()) { ... }
* --------------------------------------------------
* Returns the number of elements in the queue and whether
* the queue is empty, respectively.
*/

size_t size() const;
bool empty() const;

/* size_t maxSize() const;
* Usage: size_t queueSize = bpq.maxSize();
* --------------------------------------------------
* Returns the maximum number of elements that can be
* stored in the queue.
*/

size_t maxSize() const;

/* double best() const;
* double worst() const;
* Usage: double highestPriority = bpq.worst();
* --------------------------------------------------
* best() returns the smallest priority of an element
* stored in the container (i.e. the priority of the
* element that will be dequeued first using dequeueMin).
* worst() returns the largest priority of an element
* stored in the container.  If an element is enqueued
* with a priority above this value, it will automatically
* be deleted from the queue.  Both functions return
* numeric_limits<double>::infinity() if the queue is
* empty.
*/

double best()  const;
double worst() const;

private:
/* This class is layered on top of a multimap mapping from priorities
* to elements with those priorities.
*/

std::multimap<double, T, Comparator> elems;
size_t maximumSize;
};

/*************** Implementation Starts Here *****************/

/* Constructor accepts and stores the maximum size.  It also forwards the
* comparator to the backing multimap.
*/

template <typename T, typename Comparator>
BoundedPQueue<T, Comparator>::BoundedPQueue(size_t maxSize, Comparator comp) :
elems(comp) {
maximumSize = maxSize;
}

/* enqueue adds the element to the map, then deletes the last element of the
* map if there size exceeds the maximum size.
*/

template <typename T, typename Comparator>
void BoundedPQueue<T, Comparator>::enqueue(const T& value, double priority) {
/* Optimization: If this isn't going to be added, don't add it. */
if (size() == maxSize() && elems.key_comp()(worst(), priority))
return;

/* Add the element to the collection. */
elems.insert(make_pair(priority, value));

/* If there are too many elements in the queue, drop off the last one. */
if (size() > maxSize()) {
typename std::multimap<double, T, Comparator>::iterator last = elems.end();
--last; // Now points to highest-priority element
elems.erase(last);
}
}

/* dequeueMin copies the lowest element of the map (the one pointed at by
* begin()) and then removes it.
*/

template <typename T, typename Comparator>
T BoundedPQueue<T, Comparator>::dequeueMin() {
/* Copy the best value. */
T result = elems.begin()->second;

/* Remove it from the map. */
elems.erase(elems.begin());

return result;
}

/* size() and empty() call directly down to the underlying map. */
template <typename T, typename Comparator>
size_t BoundedPQueue<T, Comparator>::size() const {
return elems.size();
}
template <typename T, typename Comparator>
bool BoundedPQueue<T, Comparator>::empty() const {
return elems.empty();
}

/* maxSize just returns the appropriate data member. */
template <typename T, typename Comparator>
size_t BoundedPQueue<T, Comparator>::maxSize() const {
return maximumSize;
}

/* The best() and worst() functions check if the queue is empty,
* and if so return infinity.
*/

template <typename T, typename Comparator>
double BoundedPQueue<T, Comparator>::best() const {
return empty()? std::numeric_limits<double>::infinity() :
elems.begin()->first;
}
template <typename T, typename Comparator>
double BoundedPQueue<T, Comparator>::worst() const{
return empty()? std::numeric_limits<double>::infinity() :
elems.rbegin()->first;
}

#endif