Priority queue

prioqueue.hpp

/*
Copyright (c) 2026 Oskar Manhart
SPDX-Identifier: EUPL-1.2

Free software licensed under https://eupl.eu
*/

template <typename Value, typename Priority>
class KVMinPriorityQueue
{
    std::vector<Value> queue;
    RedBlackBST<Value, Priority> priorities;

    Priority default_priority;

    void sort()
    {
        std::sort(queue.begin(), queue.end(), [this](const Value& left, const Value& right)
        {
            return this->get(left) > this->get(right);
        });
    }
public:
    explicit KVMinPriorityQueue(const Priority& default_priority)
        : default_priority(default_priority)
    {
    }

    // Add an item to the queue; if it exists, update the item
    void put(const Value value, const Priority priority)
    {
        if (priorities.contains(value))
        {
            update_priority(value, priority);
            return;
        }

        queue.emplace_back(value);
        priorities.put(value, priority);
        sort();
    }

    // Change the priority for an item and re-sort the array
    void update_priority(const Value value, const Priority priority)
    {
        priorities.put(value, priority);
        sort();
    }

    // Get the amount of items in the queue
    [[nodiscard]] int size()
    {
        return queue.size();
    }

    // Get the item with the lowest priority
    [[nodiscard]] Value pop()
    {
        Value result = queue.back();
        queue.pop_back();
        return result;
    }

    // Get the priority of an item
    [[nodiscard]] Priority get(const Value& value) const
    {
        if (priorities.contains(value))
            return *priorities.get(value);

        return default_priority;
    }
};