prioritized.hpp

Go to the documentation of this file.

#pragma once
 
 
#include <commons/types.hpp>
 
#include <algorithm>
#include <concepts>
#include <cstddef>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#include <set>
#include <type_traits>
#include <utility>
 
// ---------------------------------------------------------------------------
// Configurable sentinel values (override seam)
//
// These live here rather than in commons/config.hpp (which is reserved for the
// boolean COMMONS_WITH_* integration gates) so the umbrella does not force
// <limits> on every consumer. The static constexpr members of `Prioritized`
// below are the canonical surface; these macros exist only so a build system or
// consumer can predefine an override before this header is first included.
// ---------------------------------------------------------------------------
 
#if !defined(COMMONS_PRIORITIZED_HIGHEST_PRECEDENCE)
#define COMMONS_PRIORITIZED_HIGHEST_PRECEDENCE (std::numeric_limits<int>::min())
#endif
#if !defined(COMMONS_PRIORITIZED_LOWEST_PRECEDENCE)
#define COMMONS_PRIORITIZED_LOWEST_PRECEDENCE (std::numeric_limits<int>::max())
#endif
#if !defined(COMMONS_PRIORITIZED_DEFAULT_PRIORITY)
#define COMMONS_PRIORITIZED_DEFAULT_PRIORITY 0
#endif
 
namespace comms {
 
// ---------------------------------------------------------------------------
// Prioritized — abstract interface (virtual-with-default, not pure)
// ---------------------------------------------------------------------------
 
struct Prioritized {
    // The sentinels keep Spring's `Ordered` SCREAMING_CASE spelling rather than
    // the project's lower_case constant style — it is the recognized convention
    // for these specific values.
    // NOLINTBEGIN(readability-identifier-naming)
    static constexpr int HIGHEST_PRECEDENCE = COMMONS_PRIORITIZED_HIGHEST_PRECEDENCE;
    static constexpr int LOWEST_PRECEDENCE = COMMONS_PRIORITIZED_LOWEST_PRECEDENCE;
    static constexpr int DEFAULT_PRIORITY = COMMONS_PRIORITIZED_DEFAULT_PRIORITY;
    // NOLINTEND(readability-identifier-naming)
 
    virtual ~Prioritized() = default;
 
    [[nodiscard]] virtual int priority() const noexcept {
        return DEFAULT_PRIORITY;
    }
 
protected:
    Prioritized() = default;
    Prioritized(const Prioritized&) = default;
    Prioritized(Prioritized&&) = default;
    Prioritized& operator=(const Prioritized&) = default;
    Prioritized& operator=(Prioritized&&) = default;
};
 
template <typename T>
concept Prioritizable = requires(const T& t) {
    { t.priority() } -> std::convertible_to<int>;
};
 
// ---------------------------------------------------------------------------
// get_priority — uniform priority lookup
// ---------------------------------------------------------------------------
 
namespace detail {
 
template <typename T>
concept PointerReturningGet = requires(const T& t) {
    { t.get() } -> std::convertible_to<const volatile void*>;
};
 
template <typename T>
[[nodiscard]] inline int get_priority_ptr(const T* ptr) noexcept {
    if (ptr == nullptr) {
        return Prioritized::DEFAULT_PRIORITY;
    }
    if constexpr (Prioritizable<T>) {
        return ptr->priority();
    } else if constexpr (std::is_polymorphic_v<T>) {
        if (const auto* p = dynamic_cast<const Prioritized*>(ptr)) {
            return p->priority();
        }
        return Prioritized::DEFAULT_PRIORITY;
    } else {
        return Prioritized::DEFAULT_PRIORITY;
    }
}
 
}  // namespace detail
 
template <typename T>
    requires(!std::is_pointer_v<T>)
[[nodiscard]] inline int get_priority(const T& value) noexcept {
    if constexpr (std::is_base_of_v<Prioritized, T> || Prioritizable<T>) {
        return value.priority();
    } else if constexpr (detail::PointerReturningGet<T>) {
        return detail::get_priority_ptr(value.get());
    } else {
        return Prioritized::DEFAULT_PRIORITY;
    }
}
 
template <typename T>
[[nodiscard]] inline int get_priority(const T* ptr) noexcept {
    return detail::get_priority_ptr(ptr);
}
 
// ---------------------------------------------------------------------------
// Comparators (strict-weak; lower value sorts first)
// ---------------------------------------------------------------------------
 
struct PrioritizedCompare {
    [[nodiscard]] bool operator()(const std::shared_ptr<Prioritized>& a,
                                  const std::shared_ptr<Prioritized>& b) const noexcept {
        const int pa = a ? a->priority() : Prioritized::DEFAULT_PRIORITY;
        if (const int pb = b ? b->priority() : Prioritized::DEFAULT_PRIORITY; pa != pb) {
            return pa < pb;
        }
        return std::less<const Prioritized*>{}(a.get(), b.get());
    }
};
 
template <typename T>
struct LenientPrioritizedCompare {
    [[nodiscard]] bool operator()(const std::shared_ptr<T>& a,
                                  const std::shared_ptr<T>& b) const noexcept {
        const int pa = get_priority(a);
        if (const int pb = get_priority(b); pa != pb) {
            return pa < pb;
        }
        return std::less<const T*>{}(a.get(), b.get());
    }
};
 
// ---------------------------------------------------------------------------
// PrioritizedSet — a transparent std::set<T> with priority on top
// ---------------------------------------------------------------------------
 
template <typename T>
class PrioritizedSet {
    static_assert(std::equality_comparable<T>,
                  "PrioritizedSet<T> requires T to be equality-comparable");
 
    struct Item {
        T value;
        int priority;
        u64 order;
    };
 
    struct ItemCompare {
        [[nodiscard]] bool operator()(const Item& a, const Item& b) const noexcept {
            if (a.priority != b.priority) {
                return a.priority < b.priority;
            }
            return a.order < b.order;
        }
    };
 
    using set_type = std::set<Item, ItemCompare>;
 
public:
    using key_type = T;
    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using reference = const T&;
    using const_reference = const T&;
 
    // STL-style lower_case name (not the project's CamelCase) so the type reads
    // as a standard container iterator at the call site.
    // NOLINTNEXTLINE(readability-identifier-naming)
    class const_iterator {
    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = const T*;
        using reference = const T&;
 
        const_iterator() = default;
 
        [[nodiscard]] reference operator*() const noexcept {
            return it_->value;
        }
        [[nodiscard]] pointer operator->() const noexcept {
            return &it_->value;
        }
 
        const_iterator& operator++() noexcept {
            ++it_;
            return *this;
        }
        const_iterator operator++(int) noexcept {
            const_iterator tmp = *this;
            ++it_;
            return tmp;
        }
        const_iterator& operator--() noexcept {
            --it_;
            return *this;
        }
        const_iterator operator--(int) noexcept {
            const_iterator tmp = *this;
            --it_;
            return tmp;
        }
 
        [[nodiscard]] bool operator==(const const_iterator&) const = default;
 
    private:
        friend class PrioritizedSet;
        explicit const_iterator(typename set_type::const_iterator it) noexcept : it_(it) {}
        typename set_type::const_iterator it_{};
    };
 
    using iterator = const_iterator;  // elements are immutable, like std::set keys
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = reverse_iterator;
 
    PrioritizedSet() = default;
 
    PrioritizedSet(std::initializer_list<T> init) {
        for (const auto& v : init) {
            insert(v);
        }
    }
 
    template <typename It>
    PrioritizedSet(It first, It last) {
        for (; first != last; ++first) {
            insert(*first);
        }
    }
 
    // -- std::set-shaped, T-facing API ---------------------------------------
 
    std::pair<iterator, bool> insert(const T& v) {
        return insert(get_priority(v), v);
    }
 
    std::pair<iterator, bool> insert(T&& v) {
        const int p = get_priority(v);
        return insert(p, std::move(v));
    }
 
    std::pair<iterator, bool> insert(int priority, T v) {
        if (const auto found = find_item(v); found != items_.end()) {
            return {const_iterator{found}, false};
        }
        const auto [it, ok] = items_.insert(
            Item{.value = std::move(v), .priority = priority, .order = next_order_++});
        return {const_iterator{it}, ok};
    }
 
    template <typename... Args>
    std::pair<iterator, bool> emplace(Args&&... args) {
        return insert(T(std::forward<Args>(args)...));
    }
 
    void insert(std::initializer_list<T> init) {
        for (const auto& v : init) {
            insert(v);
        }
    }
 
    template <typename It>
    void insert(It first, It last) {
        for (; first != last; ++first) {
            insert(*first);
        }
    }
 
    iterator erase(const_iterator pos) {
        return const_iterator{items_.erase(pos.it_)};
    }
 
    iterator erase(const_iterator first, const_iterator last) {
        return const_iterator{items_.erase(first.it_, last.it_)};
    }
 
    size_type erase(const T& v) {
        const auto it = find_item(v);
        if (it == items_.end()) {
            return 0;
        }
        items_.erase(it);
        return 1;
    }
 
    [[nodiscard]] iterator find(const T& v) const {
        return const_iterator{find_item(v)};
    }
 
    [[nodiscard]] size_type count(const T& v) const {
        return contains(v) ? 1U : 0U;
    }
 
    [[nodiscard]] bool contains(const T& v) const {
        return find_item(v) != items_.end();
    }
 
    // -- priority-specific extras --------------------------------------------
 
    [[nodiscard]] int priority_of(const T& v) const {
        const auto it = find_item(v);
        return it != items_.end() ? it->priority : Prioritized::DEFAULT_PRIORITY;
    }
 
    bool set_priority(const T& v, int priority) {
        const auto it = find_item(v);
        if (it == items_.end()) {
            return false;
        }
        if (it->priority == priority) {
            return true;
        }
        Item updated = *it;  // preserves the original `order` tie-break
        updated.priority = priority;
        items_.erase(it);
        items_.insert(std::move(updated));
        return true;
    }
 
    [[nodiscard]] size_type size() const noexcept {
        return items_.size();
    }
    [[nodiscard]] bool empty() const noexcept {
        return items_.empty();
    }
 
    void clear() noexcept {
        items_.clear();
    }
 
    void swap(PrioritizedSet& other) noexcept {
        items_.swap(other.items_);
        std::swap(next_order_, other.next_order_);
    }
 
    [[nodiscard]] iterator begin() const noexcept {
        return const_iterator{items_.begin()};
    }
    [[nodiscard]] iterator end() const noexcept {
        return const_iterator{items_.end()};
    }
    [[nodiscard]] iterator cbegin() const noexcept {
        return begin();
    }
    [[nodiscard]] iterator cend() const noexcept {
        return end();
    }
    [[nodiscard]] reverse_iterator rbegin() const noexcept {
        return reverse_iterator{end()};
    }
    [[nodiscard]] reverse_iterator rend() const noexcept {
        return reverse_iterator{begin()};
    }
    [[nodiscard]] const_reverse_iterator crbegin() const noexcept {
        return rbegin();
    }
    [[nodiscard]] const_reverse_iterator crend() const noexcept {
        return rend();
    }
 
    [[nodiscard]] friend bool operator==(const PrioritizedSet& a, const PrioritizedSet& b) {
        return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin());
    }
 
private:
    [[nodiscard]] typename set_type::const_iterator find_item(const T& v) const {
        for (auto it = items_.begin(); it != items_.end(); ++it) {
            if (it->value == v) {
                return it;
            }
        }
        return items_.end();
    }
 
    set_type items_;
    u64 next_order_ = 0;
};
 
template <typename T>
void swap(PrioritizedSet<T>& a, PrioritizedSet<T>& b) noexcept {
    a.swap(b);
}
 
// ---------------------------------------------------------------------------
// PrioritizedBuilder — CRTP mixin (mirrors FlagBuilderMixin)
// ---------------------------------------------------------------------------
 
template <typename Derived>
class PrioritizedBuilder : public Prioritized {
public:
    [[nodiscard]] int priority() const noexcept override {
        return priority_;
    }
 
    Derived& priority(const int p) noexcept {
        priority_ = p;
        return self();
    }
 
    Derived& highest_priority() noexcept {
        priority_ = HIGHEST_PRECEDENCE;
        return self();
    }
 
    Derived& lowest_priority() noexcept {
        priority_ = LOWEST_PRECEDENCE;
        return self();
    }
 
protected:
    int priority_ = Prioritized::DEFAULT_PRIORITY;
 
private:
    Derived& self() noexcept {
        return static_cast<Derived&>(*this);
    }
};
 
// ---------------------------------------------------------------------------
// WithPriority — attach a priority to an existing value
// ---------------------------------------------------------------------------
 
template <typename T>
inline constexpr bool with_priority_inherits = std::is_class_v<T> && !std::is_final_v<T>;
 
namespace detail {
 
template <typename T>
class WithPriorityInherit : public T, public Prioritized {
public:
    using value_type = T;
 
    template <typename... Args>
    explicit WithPriorityInherit(const int p, Args&&... args)
        : T(std::forward<Args>(args)...), priority_(p) {}
 
    [[nodiscard]] int priority() const noexcept override {
        return priority_;
    }
    void set_priority(const int p) noexcept {
        priority_ = p;
    }
 
    [[nodiscard]] T& value() noexcept {
        return static_cast<T&>(*this);
    }
    [[nodiscard]] const T& value() const noexcept {
        return static_cast<const T&>(*this);
    }
 
protected:
    int priority_ = Prioritized::DEFAULT_PRIORITY;
};
 
template <typename T>
class WithPriorityCompose : public Prioritized {
public:
    using value_type = T;
 
    template <typename... Args>
    explicit WithPriorityCompose(const int p, Args&&... args)
        : value_(std::forward<Args>(args)...), priority_(p) {}
 
    [[nodiscard]] int priority() const noexcept override {
        return priority_;
    }
    void set_priority(const int p) noexcept {
        priority_ = p;
    }
 
    [[nodiscard]] T& value() noexcept {
        return value_;
    }
    [[nodiscard]] const T& value() const noexcept {
        return value_;
    }
 
    [[nodiscard]] T& operator*() noexcept {
        return value_;
    }
    [[nodiscard]] const T& operator*() const noexcept {
        return value_;
    }
    [[nodiscard]] T* operator->() noexcept {
        return &value_;
    }
    [[nodiscard]] const T* operator->() const noexcept {
        return &value_;
    }
 
protected:
    T value_{};
    int priority_ = Prioritized::DEFAULT_PRIORITY;
};
 
template <typename T>
using WithPriorityBase =
    std::conditional_t<with_priority_inherits<T>, WithPriorityInherit<T>, WithPriorityCompose<T>>;
 
}  // namespace detail
 
template <typename T>
class WithPriority : public detail::WithPriorityBase<T> {
    using base = detail::WithPriorityBase<T>;
 
public:
    using value_type = T;
    using base::base;
 
    WithPriority()
        requires std::default_initializable<T>
        : base(Prioritized::DEFAULT_PRIORITY) {}
};
 
template <typename T>
[[nodiscard]] WithPriority<std::remove_cvref_t<T>> with_priority(int p, T&& item) {
    return WithPriority<std::remove_cvref_t<T>>(p, std::forward<T>(item));
}
 
template <typename T, typename... Args>
[[nodiscard]] std::shared_ptr<WithPriority<T>> make_prioritized(int p, Args&&... args) {
    return std::make_shared<WithPriority<T>>(p, std::forward<Args>(args)...);
}
 
}  // namespace comms
 
// ---------------------------------------------------------------------------
// Override seam macros (mirror flag.hpp's trailing declaration macros). These
// only take effect if predefined before this header is first included; the
// static constexpr members of `comms::Prioritized` are the canonical surface.
// ---------------------------------------------------------------------------