priority_queue.h

Go to the documentation of this file.

// =====================================================================================================================
//  fennec, a free and open source game engine
//  Copyright © 2025  Medusa Slockbower
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program.  If not, see <https://www.gnu.org/licenses/>.
// =====================================================================================================================
 
 
#ifndef FENNEC_CONTAINERS_PRIORITY_QUEUE_H
#define FENNEC_CONTAINERS_PRIORITY_QUEUE_H
 
#include <fennec/containers/object_pool.h>
#include <fennec/lang/compare.h>
#include <fennec/lang/types.h>
#include <fennec/memory/allocator.h>
 
// Binary heaps are just kinda busted.
// In-array binary heaps are one of the most efficient data structures for computers
// -> Cache Locality
// -> log(n) runtime
// -> No auxiliary structures or constant runtimes
//
// I tried just about every heap under the sun
// -> strict fibonacci heap, got blown out of the water by std::priority_queue
// -> fibonacci heap, got blown out of the water by std::priority_queue
// -> binomial heap, on-par with std::set, blown out of the water by std::priority_queue
//
// Then I relented and fell back to ye old binary heap
// This implementation roughly matches gcc's std::priority_queue
 
namespace fennec
{
 
template<typename ValueT, class CompareT = less<ValueT>, class AllocT = allocator<ValueT>>
struct priority_queue {
 
// Definitions & Constants =============================================================================================
public:
    using value_t   = ValueT;
    using compare_t = CompareT;
    using alloc_t   = allocation<value_t, AllocT>;
 
    static constexpr size_t npos = -1;
 
private:
    constexpr size_t left(size_t n) const {
        n = n * 2 + 1;
        return n >= _size ? npos : n;
    }
 
    constexpr size_t right(size_t n) const {
        n = n * 2 + 2;
        return n >= _size ? npos : n;
    }
 
    constexpr size_t parent(size_t n) const {
        return n == 0 ? npos : (n - 1) / 2;
    }
 
 
// Constructors & Destructor ===========================================================================================
public:
    constexpr priority_queue()
        : _size(0) {
    }
 
    constexpr ~priority_queue() {
        while (_size > 0) {
            --_size;
            fennec::destruct(&_table[_size]);
        }
    }
 
 
// Properties ==========================================================================================================
 
    constexpr size_t size() const {
        return _size;
    }
 
    constexpr size_t capacity() const {
        return _table.capacity();
    }
 
    constexpr bool empty() const {
        return size() == 0;
    }
 
 
// Access ==============================================================================================================
 
    constexpr const value_t& front() const {
        return _table[0];
    }
 
 
// Modifiers ===========================================================================================================
 
    constexpr void push(const value_t& key) {
        this->_insert(key);
    }
 
    constexpr void push(value_t&& key) {
        this->_insert(fennec::forward<value_t>(key));
    }
 
    template<typename...ArgsT>
    constexpr void emplace(ArgsT&&...args) {
        this->_insert(fennec::forward<ArgsT>(args)...);
    }
 
    constexpr void pop() {
        fennec::swap(_table[0], _table[--_size]);
        fennec::destruct(&_table[_size]);
        _fix_erase(0);
    }
 
 
// Members =============================================================================================================
private:
    compare_t _compare;
    alloc_t   _table;
    size_t    _size;
 
// Helpers =============================================================================================================
 
    template<typename...ArgsT>
    constexpr void _insert(ArgsT&&...args) {
        if (_size == _table.capacity()) {
            _expand();
        }
        fennec::construct(&_table[_size], fennec::forward<ArgsT>(args)...);
        _fix_insert(_size++);
    }
 
    constexpr void _expand() {
        _table.reallocate((_table.capacity() + 1) * 2 - 1);
    }
 
    constexpr size_t _min(size_t a, size_t b) {
        if (a == npos) { return b; }
        if (b == npos) { return a; }
        return _compare(_table[a], _table[b]) ? a : b;
    }
 
    void _fix_insert(size_t n) {
        size_t p = parent(n);
        while (p != npos && _compare(_table[n], _table[p])) {
            fennec::swap(_table[n], _table[p]);
            n = p;
            p = parent(n);
        }
    }
 
    void _fix_erase(size_t n) {
        size_t c = _min(left(n), right(n));
        while (n != npos && c != npos && _compare(_table[c], _table[n])) {
            fennec::swap(_table[c], _table[n]);
            n = c;
            c = _min(left(n), right(n));
        }
    }
 
 
};
 
}
 
 
#endif // FENNEC_CONTAINERS_PRIORITY_QUEUE_H