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