bintree.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_BINTREE_H
#define FENNEC_CONTAINERS_BINTREE_H
 
#include <fennec/containers/dynarray.h>
#include <fennec/containers/list.h>
#include <fennec/containers/optional.h>
#include <fennec/containers/traversal.h>
#include <fennec/memory/allocator.h>
 
namespace fennec
{
 
template<typename TypeT, class AllocT = allocator<TypeT>>
struct bintree {
 
// Definitions =========================================================================================================
protected:
    struct node;
 
public:
    using value_t = TypeT;
    using alloc_t = allocator_traits<AllocT>::template rebind<node>;
    static constexpr size_t npos = -1;
 
    friend class iterator;
    friend class const_iterator;
 
protected:
    struct node {
        value_t value;
        size_t  parent;
        size_t  child[2];
 
        constexpr node()
            : value()
            , parent(npos), child{ npos, npos } {
        }
 
        template<typename...ArgsT>
        constexpr node(size_t p, size_t l, size_t r, ArgsT&&...args)
            : value(fennec::forward<ArgsT>(args)...)
            , parent(p), child{ l, r } {
        }
 
        constexpr ~node() {
            parent   = npos;
            child[0] = npos;
            child[1] = npos;
        }
 
        size_t& operator[](bool d) {
            return child[d];
        }
    };
 
    using table_t = allocation<node, alloc_t>;
    using freed_t = list<size_t, alloc_t>;
 
// Constructors & Destructor ===========================================================================================
public:
 
 
    constexpr bintree()
        : _table()
        , _freed()
        , _root(npos)
        , _size(0) {
    }
 
    constexpr bintree(bintree&& tree) noexcept
        : _table(fennec::move(tree._table))
        , _freed(fennec::move(tree._freed))
        , _root(tree._root)
        , _size(tree._size) {
    }
 
    constexpr bintree(const bintree& tree)
        : _table(tree._table)
        , _freed(tree._freed)
        , _root(tree._root)
        , _size(tree._size) {
    }
 
    constexpr ~bintree() {
        clear();
    }
 
 
 
// Properties ==========================================================================================================
public:
 
    constexpr size_t size() const {
        return _size;
    }
 
    constexpr bool empty() const {
        return _size == 0;
    }
 
    constexpr size_t capacity() const {
        return _table.capacity();
    }
 
    constexpr size_t next_id() const {
        size_t i = _size;
        if (not _freed.empty()) {
            i = _freed.front();
        }
        return i;
    }
 
    constexpr size_t root() const {
        return _root;
    }
 
 
 
// Navigation ==========================================================================================================
public:
 
 
    constexpr size_t parent(size_t i) const {
        return i == npos ? npos : _table[i].parent;
    }
 
    constexpr size_t grandparent(size_t i) const {
        return parent(parent(i));
    }
 
    constexpr size_t left(size_t i) const {
        return i == npos ? npos : _table[i].child[false];
    }
 
    constexpr size_t right(size_t i) const {
        return i == npos ? npos : _table[i].child[true];
    }
 
    constexpr size_t child(size_t i, bool dir) const {
        return i == npos ? npos : _table[i].child[dir];
    }
 
    constexpr bool direction(size_t i) const {
        return i == npos ? false : i == right(_parent(i));
    }
 
    constexpr size_t sibling(size_t i) const {
        if (i == npos) {
            return npos;
        }
        if (i == _root) {
            return npos;
        }
        size_t p = _parent(i);
        bool   d = i == _right(p);
        return _child(p, !d);
    }
 
    constexpr size_t depth(size_t i) const {
        size_t d = 0;
        while (i != npos) {
            i = _parent(i);
            ++d;
        }
        return d;
    }
 
    constexpr size_t left_most(size_t i) const {
        if (i >= _table.size()) {
            return npos;
        }
        while (_table[i].child[false] != npos) {
            i = _table[i].child[false];
        }
        return i;
    }
 
    constexpr size_t right_most(size_t i) const {
        if (i >= _table.size()) {
            return npos;
        }
        while (_table[i].right[false] != npos) {
            i = _table[i].right[false];
        }
        return i;
    }
 
 
 
// Access ==============================================================================================================
public:
 
 
    constexpr value_t& operator[](size_t i) {
        assertd(i < _table.size(), "Index out of bounds.");
        return _table[i].value;
    }
 
    constexpr const value_t& operator[](size_t i) const {
        assertd(i < _table.size(), "Index out of bounds.");
        return _table[i].value;
    }
 
 
// Modifiers ===========================================================================================================
 
 
    constexpr size_t insert_left(size_t p, value_t&& val) {
        return this->_insert_left(p, fennec::forward<value_t>(val));
    }
 
    constexpr size_t insert_left(size_t p, const value_t& val) {
        return this->_insert_left(p, val);
    }
 
    template<typename...ArgsT>
    constexpr size_t emplace_left(size_t p, ArgsT&&...args) {
        return this->_insert_left(p, fennec::forward<ArgsT>(args)...);
    }
 
    constexpr size_t insert_right(size_t p, value_t&& val) {
        return this->_insert_right(p, fennec::forward<value_t>(val));
    }
 
    constexpr size_t insert_right(size_t p, const value_t& val) {
        return this->_insert_right(p, val);
    }
 
    template<typename...ArgsT>
    constexpr size_t emplace_right(size_t p, ArgsT&&...args) {
        return this->_insert_right(p, fennec::forward<ArgsT>(args)...);
    }
 
 
 
    constexpr size_t rotate(size_t sub, bool dir) {
        if (sub == npos) {
            return npos;
        }
        size_t sub_parent = _parent(sub);
        size_t new_root   = _child(sub, not dir);
        size_t new_child  = _child(new_root, dir);
 
        _child(sub, not dir) = new_child;
        if (new_child != npos) {
            _parent(new_child) = sub;
        }
        _child(new_root, dir) = sub;
 
        _parent(new_root) = sub_parent;
        _parent(sub) = new_root;
        if (sub_parent != npos) {
            _child(sub_parent, sub == _right(sub_parent)) = new_root;
        } else {
            _root = new_root;
        }
        return new_root;
    }
 
    constexpr size_t insert(size_t p, bool d, value_t&& val) {
        return this->_insert(p, d, fennec::forward<value_t>(val));
    }
 
    constexpr size_t insert(size_t p, bool d, const value_t& val) {
        return this->_insert(p, d, val);
    }
 
    template<typename...ArgsT>
    constexpr size_t emplace(size_t p, bool d, ArgsT&&...args) {
        return this->_insert(p, d, fennec::forward<ArgsT>(args)...);
    }
 
    constexpr void clear() {
        list<size_t> queue;
 
        if (_root != npos) {
            queue.push_back(_root);
        }
 
        while (not queue.empty()) {
            size_t i = queue.front();
            queue.pop_front();
 
            if (_right(i)  != npos) {
                queue.push_front(_right(i));
            }
            if (_left(i)  != npos) {
                queue.push_front(_left(i));
            }
 
            fennec::destruct(&_table[i]);
        }
 
        _size = 0;
        _root = npos;
    }
 
 
 
// Traversal ===========================================================================================================
 
    template<typename OrderT, typename VisitorT>
    constexpr void traverse(VisitorT&& visit, size_t i) {
        OrderT order;
        i = order(*this, i);
        while (i != npos) {
            uint8_t mode = traversal_control_continue;
            if (_table[i].value) {
                mode = visit(_table[i].value, i);
            }
            if (mode == traversal_control_break) {
                break;
            }
            i = order[*this, i, mode];
        }
    }
 
    struct breadth_first {
        list<size_t> visit;
        size_t       head;
 
        size_t operator()(const bintree&, size_t start) {
            return head = start;
        }
 
        size_t operator[](const bintree& tree, size_t node, uint8_t mode) {
            if (node == npos) {
                return npos;
            }
 
            size_t lft = tree.left(tree.parent(node));
            size_t nxt = lft == node ? tree.right(tree.parent(node)) : npos;
            size_t chd = tree.left(node);
 
            if (nxt != npos && node != head) {
                visit.push_front(nxt);
            }
 
            if (chd != npos && mode != traversal_control_jump_over) {
                visit.push_back(chd);
            }
 
            if (not visit.empty()) {
                node = visit.front();
                visit.pop_front();
            } else {
                node = npos;
            }
 
            return node;
        }
    };
 
    struct pre_order {
        list<size_t> visit;
        size_t       head;
 
        constexpr size_t operator()(const bintree&, size_t start) {
            head = start;
            return start;
        }
 
        constexpr size_t operator[](const bintree& tree, size_t node, uint8_t mode) {
            if (node == npos) {
                return npos;
            }
 
            size_t nxt = tree.right(tree.parent(node));
            size_t chd = tree.left(node);
            nxt = node == nxt ? npos : nxt;
 
            if (nxt != npos && node != head) {
                visit.push_front(nxt);
            }
 
            if (chd != npos && mode != traversal_control_jump_over) {
                visit.push_front(chd);
            }
 
            if (not visit.empty()) {
                node = visit.front();
                visit.pop_front();
            } else {
                node = npos;
            }
 
            return node;
        }
    };
 
    struct in_order {
        list<size_t> visit;
        size_t       head;
 
        constexpr size_t operator()(const bintree& tree, size_t start) {
            head = start;
            return tree.left_most(start);
        }
 
        constexpr size_t operator[](const bintree& tree, size_t node, uint8_t) {
            if (node == npos) {
                return npos;
            }
 
            size_t parent = tree.parent(node);
            size_t pright = tree.right(parent);
            size_t next   = tree.left_most(tree.right(node));
 
            if (node != pright && parent != npos) {
                visit.push_front(parent);
            }
 
            if (next != npos) {
                visit.push_front(next);
            }
 
            if (not visit.empty()) {
                node = visit.front();
                visit.pop_front();
            } else {
                node = npos;
            }
 
            return node;
        }
    };
 
    struct post_order {
        list<size_t> visit;
        size_t       head;
 
        constexpr size_t successor(const bintree& tree, size_t n) {
            size_t s = tree.left_most(n);
            while (n == s) {
                size_t r = tree.right(n);
                if (r != npos) {
                    n = r;
                    s = tree.left_most(n);
                } else {
                    break;
                }
            }
            return s == npos ? n : s;
        }
 
        constexpr size_t operator()(const bintree& tree, size_t start) {
            head = start;
            return this->successor(tree, start);
        }
 
        constexpr size_t operator[](const bintree& tree, size_t node, uint8_t) {
            if (node == npos) {
                return npos;
            }
 
            size_t parent = tree.parent(node);
            size_t pright = tree.right(parent);
 
            if (node == pright) {
                if (parent != npos) {
                    visit.push_front(parent);
                }
            } else if (pright != npos) {
                visit.push_front(this->successor(tree, pright));
            }
 
            if (not visit.empty()) {
                node = visit.front();
                visit.pop_front();
            } else {
                node = npos;
            }
 
 
            return node;
        }
    };
 
// Iterator ============================================================================================================
 
    class iterator {
    protected:
        bintree* _tree;
        in_order _order;
        size_t   _n;
 
    public:
        constexpr iterator(bintree* tree, size_t root)
            : _tree(tree)
            , _order()
            , _n(_order(*tree, root)) {
        }
 
        constexpr iterator(bintree* tree, size_t root, size_t node)
            : _tree(tree)
            , _order()
            , _n(node) {
            _order.head = root;
        }
 
        size_t index() const {
            return _n;
        }
 
        iterator& operator++() {
            return _n = _order[*_tree, _n, traversal_control_continue], *this;
        }
 
        value_t& operator*() {
            return (*_tree)[_n];
        }
 
        value_t* operator->() {
            return &(*_tree)[_n];
        }
 
        const value_t& operator*() const {
            return (*_tree)[_n];
        }
 
        const value_t* operator->() const {
            return &(*_tree)[_n];
        }
 
        constexpr bool operator==(const iterator& it) {
            return _tree == it._tree and _n == it._n;
        }
 
        constexpr bool operator!=(const iterator& it) {
            return _tree != it._tree or _n != it._n;
        }
 
    };
 
// Fields ==============================================================================================================
protected:
    table_t _table;
    freed_t _freed;
    size_t  _root, _size;
 
// Helpers =============================================================================================================
 
    constexpr size_t _next_free() {
        size_t i = _size;
        if (not _freed.empty()) {
            i = _freed.front();
            _freed.pop_front();
        }
        if (i >= _table.capacity()) {
            _table.creallocate(2 * fennec::max(_table.capacity(), size_t(4)));
        }
        ++_size;
        return i;
    }
 
    template<typename...ArgsT>
    constexpr size_t _insert_left(size_t p, ArgsT&&...args) {
        size_t i = p >= capacity() ? npos : p;
        i = i == npos ? _root : _left(i);
        if (i != npos) {
            _table[i].value = value_t(fennec::forward<ArgsT>(args)...);
        } else {
            i = _next_free();
            if (p != npos) {
                _left(p) = i;
            }
            if (_root == npos) {
                _root = i;
            }
            fennec::construct(&_table[i], p, npos, npos, fennec::forward<ArgsT>(args)...);
        }
        return i;
    }
 
    template<typename...ArgsT>
    constexpr size_t _insert_right(size_t p, ArgsT&&...args) {
        size_t i = p == npos ? _root : _right(p);
        if (i != npos) {
            _table[i].value = value_t(fennec::forward<ArgsT>(args)...);
        } else {
            i = _next_free();
            if (p != npos) {
                _right(p) = i;
            }
            if (_root == npos) {
                _root = i;
            }
            fennec::construct(&_table[i], p, npos, npos, fennec::forward<ArgsT>(args)...);
        }
        return i;
    }
 
    template<typename...ArgsT>
    constexpr size_t _insert(size_t p, bool d, ArgsT&&...args) {
        size_t i = p == npos ? _root : _child(p, d);
        if (i != npos) {
            _table[i].value = value_t(fennec::forward<ArgsT>(args)...);
            return i;
        }
 
        i = _next_free();
        if (p != npos) {
            _child(p, d) = i;
        }
        if (_root == npos) {
            _root = i;
        }
        fennec::construct(&_table[i], p, npos, npos, fennec::forward<ArgsT>(args)...);
        return i;
    }
 
 
    constexpr size_t& _parent(size_t i) {
        return _table[i].parent;
    }
 
    constexpr size_t& _grandparent(size_t i) {
        return _parent(_parent(i));
    }
 
    constexpr size_t& _left(size_t i) {
        return _table[i].child[false];
    }
 
    constexpr size_t& _right(size_t i) {
        return _table[i].child[true];
    }
 
    constexpr size_t& _child(size_t i, bool dir) {
        return _table[i].child[dir];
    }
 
    constexpr size_t& _sibling(size_t i) {
        size_t p = _parent(i);
        bool   d = i == _right(p);
        return _child(p, !d);
    }
};
 
}
 
#endif // FENNEC_CONTAINERS_BINTREE_H