#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/priorityQueue.h>
template <typename T, typename U>
class FirstLess {
public:
bool operator()(pair<T,U> a, pair<T,U> b);
};
template <typename T, typename U>
bool FirstLess<T,U>::operator()(pair<T,U> a, pair<T,U> b) {
return a.first < b.first;
}
template <typename P, typename V>
class STLPriorityQueue : public PriorityQueue<P,V> {
public:
STLPriorityQueue();
~STLPriorityQueue();
void insert(P priority, V value);
V removeMax();
V getMax();
P getMaxPriority();
int getSize();
bool isEmpty();
private:
std::priority_queue<pair<P,V>, vector<pair<P,V>>, FirstLess<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:
STLPriorityQueue(const STLPriorityQueue& other) = delete;
STLPriorityQueue& operator=(const STLPriorityQueue& other) = delete;
};
template <typename P, typename V>
STLPriorityQueue<P,V>::STLPriorityQueue() {
actualPriorityQueue =
new std::priority_queue<
pair<P,V>,
vector<pair<P,V>>, FirstLess<P,V>>();
}
template <typename P, typename V>
STLPriorityQueue<P,V>::~STLPriorityQueue() {
delete actualPriorityQueue;
}
template <typename P, typename V>
void STLPriorityQueue<P,V>::insert(P priority, V value) {
actualPriorityQueue->push(pair<P,V>(priority, value));
}
template <typename P, typename V>
V STLPriorityQueue<P,V>::removeMax() {
if (actualPriorityQueue->empty()) {
throw runtime_error("STLPriorityQueue::removeMax(): empty prio queue");
}
V v = actualPriorityQueue->top().second;
actualPriorityQueue->pop();
return v;
}
template <typename P, typename V>
V STLPriorityQueue<P,V>::getMax() {
if (actualPriorityQueue->empty()) {
throw runtime_error("STLPriorityQueue::getMax(): empty prio queue");
}
return actualPriorityQueue->top().second;
}
template <typename P, typename V>
P STLPriorityQueue<P,V>::getMaxPriority() {
if (actualPriorityQueue->empty()) {
throw runtime_error("STLPriorityQueue::getMaxPriority(): empty prio queue");
}
return actualPriorityQueue->top().first;
}
template <typename P, typename V>
int STLPriorityQueue<P,V>::getSize() {
return actualPriorityQueue->size();
}
template <typename P, typename V>
bool STLPriorityQueue<P,V>::isEmpty() {
return actualPriorityQueue->empty();
}