BoundedPriorityDeque.hpp

Go to the documentation of this file.

//
// Created by Cooper Larson on 7/30/24.
//
 
#ifndef BOUNDED_PRIORITY_DEQUE_H
#define BOUNDED_PRIORITY_DEQUE_H
 
#include <vector>
 
#ifdef ENABLE_DEBUG
#include <stdexcept>
#endif
 
template <typename T>
class has_comparison_operator {
    template <typename U, typename = decltype(std::declval<U>()(std::declval<const T&>(), std::declval<const T&>()))>
    static std::true_type check(U*);
 
    static std::false_type check(...);
 
public:
    static constexpr bool value = decltype(check(std::declval<T*>()))::value;
};
 
template <typename T>
inline constexpr bool has_comparison_operator_v = has_comparison_operator<T>::value;
 
template<typename K, typename V, typename Enable = void>
class BoundingPair {
public:
    K key; 
    V value; 
 
    bool operator<(const BoundingPair& other) const {
        return this->key < other.key;
    }
};
 
template<typename K, typename V>
class BoundingPair<K, V, std::enable_if_t<has_comparison_operator_v<K>>> : public std::pair<K, V> {
public:
    bool operator<(const BoundingPair& other) const {
        K comparator;
        return comparator(this->key, other.key);
    }
};
 
template<typename K, typename V>
class BoundedPriorityDequeBase {
protected:
    std::vector<BoundingPair<K, V>> _buffer;
    size_t _k, _size = 0, _head = 0, _tail = 0;
 
    virtual bool compare(K a, K b) const = 0;
 
    [[nodiscard]] size_t nextIndex(size_t current) const { return (current + 1) % _k; }
 
    [[nodiscard]] size_t prevIndex(size_t current) const { return (current + _k - 1) % _k; }
 
    size_t binarySearch(const BoundingPair<K, V>& target) const {
        size_t start = 0;
        auto end = _size;
        while (start != end) {
            size_t mid = start + (end - start) / 2;
            if (compare(_buffer[(_head + mid) % _k].key, target.key)) start = mid + 1;
            else end = mid;
        }
        return (_head + start) % _k;
    }
 
    void insert(const BoundingPair<K, V>& element) {
        if (_size == 0) {
            _buffer[0] = element;
            _head = 0;
            _tail = 0;
            _size = 1;
            return;
        }
 
        auto index = binarySearch(element);
        if (index == nextIndex(_tail)) {
            if (index == prevIndex(_head) && compare(element.key, topK())) _head = prevIndex(_head);
            else _tail = nextIndex(_tail);
        }
        else if (index == prevIndex(_head)) _head = prevIndex(_head);
        else if (_head <= _tail && _head > 0) {
            std::move(_buffer.begin() + _head, _buffer.begin() + index + 1, _buffer.begin() + _head - 1);
            --_head;
        } else {
            std::move_backward(_buffer.begin() + index, _buffer.begin() + _tail + 1, _buffer.begin() + _tail + 2);
            ++_tail;
        }
 
        _buffer[index] = element;
        ++_size;
    }
 
    void _popTop() {
        _head = nextIndex(_head);
        if (--_size == 0) clear();
    }
 
    void _popBottom() {
        _tail = prevIndex(_tail);
        if (--_size == 0) clear();
    }
 
public:
    explicit BoundedPriorityDequeBase(size_t capacity = 0) : _buffer(capacity), _k(capacity) {}
 
    BoundingPair<K, V> top() const {
#ifdef ENABLE_DEBUG
        if (empty()) throw std::runtime_error("Attempted to access top element of empty BoundedPriorityDeque");
#endif
        return _buffer[_head];
    }
 
    BoundingPair<K, V> bottom() const {
#ifdef ENABLE_DEBUG
        if (empty()) throw std::runtime_error("Attempted to access bottom element of empty BoundedPriorityDeque");
#endif
        return _buffer[_tail];
    }
 
    [[nodiscard]] K topK() const {
#ifdef ENABLE_DEBUG
        if (empty()) throw std::runtime_error("Attempted to access bottom element of empty BoundedPriorityDeque");
#endif
        return _buffer[_head].key;
    }
 
    [[nodiscard]] K bottomK() const {
#ifdef ENABLE_DEBUG
        if (empty()) throw std::runtime_error("Attempted to access bottom element of empty BoundedPriorityDeque");
#endif
        return _buffer[_tail].key;
    }
 
    void emplace(K key, const V& value) {
        if (_size == _k) {
            if (compare(key, _buffer[_tail].key)) _popBottom();
            else return;
        }
        insert({ key, value });
    }
 
    void push(const BoundingPair<K, V>& element) {
        if (_size == _k) {
            if (compare(element.key, _buffer[_tail].key)) _popBottom();
            else return;
        }
        insert(element);
    }
 
    BoundingPair<K, V> operator[](size_t offsetTop) const {
        return _buffer[_head <= _tail ? _head + offsetTop : (_head + offsetTop) % _k];
    }
 
    BoundingPair<K, V> pop() {
#ifdef ENABLE_DEBUG
        if (empty()) throw std::runtime_error("Attempted to pop from empty BoundedPriorityDeque");
#endif
        auto index = _head;
        _popTop();
        return _buffer[index];
    }
 
    BoundingPair<K, V> popBottom() {
#ifdef ENABLE_DEBUG
        if (empty()) throw std::runtime_error("Attempted to pop from empty BoundedPriorityDeque");
#endif
        auto index = _tail;
        _popBottom();
        return _buffer[index];
    }
 
    void operator+=(const BoundedPriorityDequeBase<K, V>& rhs) {
        for (size_t i = 0; i < rhs.size(); ++i) {
            if (_size == _k) {
                if (compare(rhs[i].key, bottomK())) _popBottom();
                else return;
            }
            insert(rhs[i]);
        }
    }
 
    void clear() {
        _head = 0;
        _tail = 0;
        _size = 0;
    }
 
    [[nodiscard]] size_t size() const { return _size; }
 
    [[nodiscard]] size_t capacity() const { return _k; }
 
    [[nodiscard]] bool empty() const { return _size == 0; }
 
    [[nodiscard]] bool full() const { return _size == _k; }
 
    void resize(size_t k) {
        if (k == 0) return;
 
        std::vector<BoundingPair<K, V>> newBuffer(k);
 
        if (_head <= _tail) {
            size_t elementsToCopy = std::min(_size, k);
            std::move(_buffer.begin() + _head, _buffer.begin() + _head + elementsToCopy, newBuffer.begin());
            _size = elementsToCopy;
        } else {
            size_t topSize = _k - _head;
            size_t bottomSize = _tail + 1;
            size_t elementsToCopyTop = std::min(topSize, k);
            size_t elementsToCopyBottom = std::min(bottomSize, k - elementsToCopyTop);
 
            std::move(_buffer.begin() + _head, _buffer.begin() + _head + elementsToCopyTop, newBuffer.begin());
            std::move(_buffer.begin(), _buffer.begin() + elementsToCopyBottom, newBuffer.begin() + elementsToCopyTop);
 
            _size = elementsToCopyTop + elementsToCopyBottom;
        }
 
        _buffer.swap(newBuffer);
        _k = k;
        _head = 0;
        _tail = _size - 1;
    }
};
 
template<typename K, typename V>
class BoundedMinPriorityDeque : public BoundedPriorityDequeBase<K, V> {
protected:
    [[nodiscard]] bool compare(K a, K b) const override { return a < b; }
 
public:
    explicit BoundedMinPriorityDeque(unsigned int capacity = 0) : BoundedPriorityDequeBase<K, V>(capacity) {}
};
 
template<typename K, typename V>
class BoundedMaxPriorityDeque : public BoundedPriorityDequeBase<K, V> {
protected:
    [[nodiscard]] bool compare(K a, K b) const override { return a > b; }
 
public:
    explicit BoundedMaxPriorityDeque(unsigned int capacity = 0) : BoundedPriorityDequeBase<K, V>(capacity) {}
};
 
template<typename K, typename V, typename Comparator = std::less<K>>
class BoundedPriorityDequeKeyed : public BoundedPriorityDequeBase<K, V> {
protected:
    Comparator comparator;
 
    [[nodiscard]] bool compare(K a, K b) const override { return comparator(a, b); }
 
public:
    explicit BoundedPriorityDequeKeyed(unsigned int capacity = 0, Comparator comp = Comparator()) :
            BoundedPriorityDequeBase<K, V>(capacity), comparator(comp) {}
};
 
template<typename V, typename Comparator, typename K = decltype(std::declval<Comparator>().comparisonValue(std::declval<V>()))>
class BoundedPriorityDeque : public BoundedPriorityDequeBase<K, V> {
protected:
    Comparator comparator;
 
    [[nodiscard]] bool compare(K a, K b) const override {
        return comparator(a, b);
    }
 
    K extractKey(const V& value) const {
        return comparator.comparisonValue(value);
    }
 
public:
    explicit BoundedPriorityDeque(unsigned int capacity = 0, Comparator comp = Comparator()) :
            BoundedPriorityDequeBase<K, V>(capacity), comparator(comp) {}
 
    void emplace(const V& value) {
        K key = extractKey(value);
        BoundedPriorityDequeBase<K, V>::emplace(key, value);
    }
 
    void push(const V& value) { emplace(value); }
};
 
#endif // BOUNDED_PRIORITY_DEQUE_H