#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/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(); }