priority_queue.h

Go to the documentation of this file.

#pragma once
 
#include "fl/stl/stdint.h"                 // for u64  // IWYU pragma: keep
#include "fl/stl/vector.h"                 // for vector
#include "fl/stl/move.h"                   // for remove_reference
#include "fl/stl/utility.h"                // for greater, less
#include "fl/stl/int.h"                        // for size  // IWYU pragma: keep
#include "fl/stl/memory_resource.h"
#include "fl/stl/noexcept.h"
 
namespace fl {
 
// Custom heap operations
template <typename Iterator, typename Compare>
void sift_down(Iterator first, Iterator last, Iterator start, Compare comp) {
    auto root = start;
    auto child = first + 2 * (root - first) + 1;
 
    while (child < last) {
        if (child + 1 < last && comp(*child, *(child + 1))) {
            ++child;
        }
 
        if (comp(*root, *child)) {
            auto tmp = *root;
            *root = *child;
            *child = tmp;
 
            root = child;
            child = first + 2 * (root - first) + 1;
        } else {
            break;
        }
    }
}
 
template <typename Iterator, typename Compare>
void push_heap(Iterator first, Iterator last, Compare comp) {
    auto pos = last - 1;
    auto parent = first + ((pos - first) - 1) / 2;
 
    while (pos > first && comp(*parent, *pos)) {
        auto tmp = *parent;
        *parent = *pos;
        *pos = tmp;
 
        pos = parent;
        parent = first + ((pos - first) - 1) / 2;
    }
}
 
template <typename Iterator> void push_heap(Iterator first, Iterator last) {
    using value_type = typename fl::remove_reference<decltype(*first)>::type;
    push_heap(first, last, [](const value_type &a, const value_type &b) { return a < b; });
}
 
template <typename Iterator, typename Compare>
void pop_heap(Iterator first, Iterator last, Compare comp) {
    --last;
    auto tmp = *first;
    *first = *last;
    *last = tmp;
 
    sift_down(first, last, first, comp);
}
 
template <typename Iterator> void pop_heap(Iterator first, Iterator last) {
    using value_type = typename fl::remove_reference<decltype(*first)>::type;
    pop_heap(first, last, [](const value_type &a, const value_type &b) { return a < b; });
}
 
template <typename T, typename Compare = fl::less<T>,
          typename VectorT = vector<T>>
class PriorityQueue {
  public:
    using value_type = T;
    using size_type = fl::size;
    using compare_type = Compare;
 
    PriorityQueue() FL_NOEXCEPT = default;
    explicit PriorityQueue(memory_resource* resource) : _data(resource) {}
    explicit PriorityQueue(const Compare &comp) : _comp(comp) {}
    PriorityQueue(const Compare &comp, memory_resource* resource) : _data(resource), _comp(comp) {}
 
    void push(const T &value) {
        _data.push_back(value);
        push_heap(_data.begin(), _data.end(), _comp);
    }
 
    void push(T &&value) {
        _data.push_back(fl::move(value));
        push_heap(_data.begin(), _data.end(), _comp);
    }
 
    template<typename... Args>
    void emplace(Args&&... args) {
        _data.emplace_back(fl::forward<Args>(args)...);
        push_heap(_data.begin(), _data.end(), _comp);
    }
 
    void pop() {
        pop_heap(_data.begin(), _data.end(), _comp);
        _data.pop_back();
    }
 
    const T &top() const { return _data.front(); }
 
    bool empty() const { return _data.size() == 0; }
    fl::size size() const { return _data.size(); }
 
    const Compare &compare() const { return _comp; }
    memory_resource* get_memory_resource() const { return _data.get_resource(); }

    bool operator==(const PriorityQueue& other) const {
        return _data == other._data;
    }

    bool operator!=(const PriorityQueue& other) const {
        return _data != other._data;
    }

    bool operator<(const PriorityQueue& other) const {
        return _data < other._data;
    }

    bool operator<=(const PriorityQueue& other) const {
        return _data <= other._data;
    }

    bool operator>(const PriorityQueue& other) const {
        return _data > other._data;
    }

    bool operator>=(const PriorityQueue& other) const {
        return _data >= other._data;
    }
 
  private:
    VectorT _data;
    Compare _comp;
};

template<typename T, typename Compare = fl::less<T>>
class priority_queue_stable {
private:
    struct StableElement {
        T mValue;
        u64 mSequence;
 
        // Comparison: primary by value, secondary by sequence (FIFO)
        bool operator<(const StableElement& other) const {
            Compare comp;
            // Use the Compare function to determine ordering
            if (comp(mValue, other.mValue)) return true;
            if (comp(other.mValue, mValue)) return false;
            // Values are equal according to comparator - use sequence for FIFO ordering
            // INVERTED: smaller sequence should be "greater" (pop first)
            return mSequence > other.mSequence;
        }
    };
 
public:
    using value_type = T;
    using size_type = fl::size;
 
    priority_queue_stable() FL_NOEXCEPT : mNextSequence(0) {}

    void push(const T& value) {
        mQueue.push({value, mNextSequence++});
    }
 
    template<typename... Args>
    void emplace(Args&&... args) {
        mQueue.push({T(fl::forward<Args>(args)...), mNextSequence++});
    }

    void pop() {
        mQueue.pop();
    }

    const T& top() const {
        return mQueue.top().mValue;
    }

    bool empty() const {
        return mQueue.empty();
    }

    fl::size size() const {
        return mQueue.size();
    }

    void clear() {
        while (!empty()) {
            pop();
        }
        mNextSequence = 0;
    }

    bool operator==(const priority_queue_stable& other) const {
        return mQueue == other.mQueue;
    }

    bool operator!=(const priority_queue_stable& other) const {
        return mQueue != other.mQueue;
    }

    bool operator<(const priority_queue_stable& other) const {
        return mQueue < other.mQueue;
    }

    bool operator<=(const priority_queue_stable& other) const {
        return mQueue <= other.mQueue;
    }

    bool operator>(const priority_queue_stable& other) const {
        return mQueue > other.mQueue;
    }

    bool operator>=(const priority_queue_stable& other) const {
        return mQueue >= other.mQueue;
    }
 
private:
    fl::PriorityQueue<StableElement> mQueue;
    u64 mNextSequence;
};
 
} // namespace fl