#pragma once /* Copyright (c) 2018 Swarthmore College Computer Science Department, Swarthmore PA A. Danner, M. Gagne, J. Brody, Z. Palmer, A. Soni, L. Meeden Distributed as course material for Spring 2018 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(); }