PriorityQueue.hpp

Go to the documentation of this file.

// <PriorityQueue.hpp> -*- C++ -*-
 
 
#pragma once
 
#include <list>
#include <algorithm>
#include <functional>
 
#include "sparta/utils/SpartaAssert.hpp"
#include "sparta/utils/FastList.hpp"
 
namespace sparta
{
 
    template <class DataT,
              class SortingAlgorithmT = std::less<DataT>,
              size_t bounded_cnt=0>
    class PriorityQueue
    {
    private:
        using PQueueType =
            typename std::conditional<bounded_cnt == 0,
                                      std::list<DataT>,
                                      utils::FastList<DataT>>::type;
 
    public:
 
        // For collection
        using size_type      = size_t;
        using iterator       = typename PQueueType::iterator;
        using const_iterator = typename PQueueType::const_iterator;
 
        PriorityQueue() :
            priority_items_(bounded_cnt)
        {}
 
        PriorityQueue(const SortingAlgorithmT & sort_alg) :
            priority_items_(bounded_cnt),
            sort_alg_(sort_alg)
        {}
 
        void insert(const DataT & data)
        {
            const auto eit = priority_items_.end();
            for(auto it = priority_items_.begin(); it != eit; ++it)
            {
                if(sort_alg_(data, *it)) {
                    priority_items_.insert(it, data);
                    return;
                }
            }
            priority_items_.emplace_back(data);
        }
 
        size_t size() const {
            return priority_items_.size();
        }
 
        bool empty() const {
            return priority_items_.empty();
        }
 
        const DataT & top() const {
            sparta_assert(false == empty(), "Grabbing top from an empty queue");
            return priority_items_.front();
        }
 
        const DataT & back() const {
            sparta_assert(false == empty(), "Grabbing back from an empty queue");
            return priority_items_.back();
        }
 
        void pop() {
            sparta_assert(false == empty(), "Popping on an empty priority queue");
            priority_items_.pop_front();
        }
 
        void clear() {
            priority_items_.clear();
        }
 
        void remove(const DataT & data) {
            priority_items_.remove(data);
        }
 
        void erase(const const_iterator & it) {
            priority_items_.erase(it);
        }
 
        void forceFront(const DataT & data) {
            priority_items_.emplace_front(data);
        }
 
        iterator        begin()       { return priority_items_.begin(); }
 
        const_iterator  begin() const { return priority_items_.begin(); }
 
        iterator        end()       { return priority_items_.end(); }
 
        const_iterator  end() const { return priority_items_.end(); }
    private:
 
        PQueueType        priority_items_;
 
        SortingAlgorithmT sort_alg_;
    };
}