Line data    Source code

       1             : #pragma once
       2             : 
       3             : #include <cstddef>
       4             : 
       5             : namespace Alg {
       6             : /**
       7             :  * @brief Minimum priority queue.
       8             :  *
       9             :  * Unlike std::priority_queue, PriorityQueue exposes a decreaseKey operation.
      10             :  * You can use it by storing the Element& objects returned when calling push(T),
      11             :  * and then calling Element::decreaseKey(T).
      12             :  *
      13             :  * @tparam T Type of elements being stored in queue
      14             :  */
      15             : template<class T>
      16          19 : class PriorityQueue {
      17             :    public:
      18             :     /**
      19             :      * @brief Priority queue element. Allows to decrease key
      20             :      */
      21             :     class Element {
      22             :        public:
      23             :         /// @brief Get element value
      24             :         virtual T getValue() = 0;
      25             :         /// @brief Decrease value of element
      26             :         virtual void decreaseKey(T t) = 0;
      27             :         virtual ~Element(){};
      28             :     };
      29             : 
      30             :     /// @brief Get top element
      31             :     virtual T top() = 0;
      32             :     /// @brief Get queue size
      33             :     virtual size_t size() = 0;
      34             :     /// @brief Test if queue is empty
      35       14730 :     bool empty() { return size() == 0; }
      36             :     /// @brief Push new element into queue
      37             :     virtual Element& push(T t) = 0;
      38             :     /// @brief Pop smallest element of the queue
      39             :     virtual T pop() = 0;
      40             : 
      41          19 :     virtual ~PriorityQueue(){};
      42             : };
      43             : }  // namespace Alg