#pragma once
/* Copyright (c) 2017
Swarthmore College Computer Science Department, Swarthmore PA
A. Danner, M. Gagne, J. Brody, Z. Palmer, A. Soni
Distributed as course material for Fall 2017
CPSC 035: Data Structures and Algorithms
*/
#include <stdexcept>
#include <queue>
#include <vector>
#include <utility>
using std::pair;
using std::runtime_error;
using std::vector;
#include <cs35/minPriorityQueue.h>
template <typename T, typename U>
class FirstGreater {
public:
bool operator()(pair<T,U> a, pair<T,U> b);
};
template <typename T, typename U>
bool FirstGreater<T,U>::operator()(pair<T,U> a, pair<T,U> b) {
return a.first > b.first;
}
template <typename P, typename V>
class STLMinPriorityQueue : public MinPriorityQueue<P,V> {
public:
STLMinPriorityQueue();
~STLMinPriorityQueue();
void insert(P priority, V value);
V removeMin();
V getMin();
P getMinPriority();
int getSize();
bool isEmpty();
private:
std::priority_queue<pair<P,V>, vector<pair<P,V>>, FirstGreater<P,V>>*
actualPriorityQueue;
// You can safely ignore the following code. This eliminates some default
// class routines, preventing you from using them accidentally.
// Specifically, we are disabling the use of the copy constructor and the
// copy assignment operator. You can read more here:
// http://www.cplusplus.com/articles/y8hv0pDG/
private:
STLMinPriorityQueue(const STLMinPriorityQueue& other) = delete;
STLMinPriorityQueue& operator=(const STLMinPriorityQueue& other) = delete;
};
template <typename P, typename V>
STLMinPriorityQueue<P,V>::STLMinPriorityQueue() {
actualPriorityQueue =
new std::priority_queue<
pair<P,V>,
vector<pair<P,V>>, FirstGreater<P,V>>();
}
template <typename P, typename V>
STLMinPriorityQueue<P,V>::~STLMinPriorityQueue() {
delete actualPriorityQueue;
}
template <typename P, typename V>
void STLMinPriorityQueue<P,V>::insert(P priority, V value) {
actualPriorityQueue->push(pair<P,V>(priority, value));
}
template <typename P, typename V>
V STLMinPriorityQueue<P,V>::removeMin() {
if (actualPriorityQueue->empty()) {
throw runtime_error("STLMinPriorityQueue::removeMin(): empty prio queue");
}
V v = actualPriorityQueue->top().second;
actualPriorityQueue->pop();
return v;
}
template <typename P, typename V>
V STLMinPriorityQueue<P,V>::getMin() {
if (actualPriorityQueue->empty()) {
throw runtime_error("STLMinPriorityQueue::getMin(): empty prio queue");
}
return actualPriorityQueue->top().second;
}
template <typename P, typename V>
P STLMinPriorityQueue<P,V>::getMinPriority() {
if (actualPriorityQueue->empty()) {
throw runtime_error("STLMinPriorityQueue::getMinPriority(): empty prio queue");
}
return actualPriorityQueue->top().first;
}
template <typename P, typename V>
int STLMinPriorityQueue<P,V>::getSize() {
return actualPriorityQueue->size();
}
template <typename P, typename V>
bool STLMinPriorityQueue<P,V>::isEmpty() {
return actualPriorityQueue->empty();
}