rdtree.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_RDTREE_H
#define FENNEC_CONTAINERS_RDTREE_H
 
#include <fennec/containers/list.h>
#include <fennec/containers/optional.h>
#include <fennec/containers/traversal.h>
#include <fennec/containers/pair.h>
 
#include <fennec/memory/allocator.h>
 
namespace fennec
{
 
template<typename TypeT, typename AllocT = allocator<TypeT>>
struct rdtree {
 
// Definitions =========================================================================================================
protected:
    struct node;
 
public:
    using value_t = TypeT;
    using alloc_t = typename allocator_traits<AllocT>::template rebind<node>;
    static constexpr size_t root = 0;
    static constexpr size_t npos = -1;
 
protected:
    struct node {
        value_t value;
        size_t  parent, child, prev, next;
        size_t  depth, num_children;
 
        constexpr node()
            : value(nullopt)
            , parent(npos), child(npos)
            , prev(npos), next(npos)
            , depth(0), num_children(0) {
        }
 
        template<typename...ArgsT>
        constexpr node(size_t p, size_t c, size_t v, size_t n, size_t d, ArgsT&&...args)
            : value(fennec::forward<ArgsT>(args)...)
            , parent(p), child(c), prev(v), next(n)
            , depth(d), num_children(0) {
        }
 
        constexpr ~node() {
            parent       = npos;
            child        = npos;
            prev         = npos;
            next         = npos;
            depth        = 0;
            num_children = 0;
        }
    };
 
public:
 
// Constructors ========================================================================================================
 
 
    template<typename...ArgsT>
    explicit constexpr rdtree(ArgsT&&...args)
        : _table(), _freed(), _size(1) {
        _table.creallocate(8);
        fennec::construct(&_table[0], npos, npos, npos, npos, 0, fennec::forward<ArgsT>(args)...);
    }
 
    constexpr rdtree(const rdtree& tree)
        : _table(tree._table), _freed(tree._freed), _size(tree._size) {
    }
 
    constexpr rdtree(rdtree&& tree) noexcept
        : _table(fennec::move(tree._table)), _freed(fennec::move(tree._freed)), _size(tree._size) {
    }
 
 
 
// Assignment ==========================================================================================================
 
 
    constexpr rdtree& operator=(const rdtree& rhs) {
        for (value_t* it : this->_table) {
            fennec::destruct(it);
        }
        _table = rhs._table;
        _freed = rhs._freed;
        _size  = rhs._size;
        return *this;
    }
 
    constexpr rdtree& operator=(rdtree&& rhs) noexcept {
        for (value_t* it : _table) {
            fennec::destruct(it);
        }
        _table = fennec::move(rhs._table);
        _freed = fennec::move(rhs._freed);
        _size  = rhs._size;
        return *this;
    }
 
 
// 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 size_t parent(size_t i) const {
        if (i >= _table.capacity()) return npos;
        return i == npos ? npos : _table[i].parent;
    }
 
    constexpr size_t child(size_t i, size_t n = 0) const {
        if (i >= _table.capacity() && n != npos) return npos;
        size_t c = i == npos ? npos : _table[i].child;
        if (n != 0)
            return next(c, n == npos ? npos : n - 1);
        return c;
    }
 
    constexpr size_t next(size_t i, size_t n = 0) const {
        if (i >= _table.capacity() && n != npos) return npos;
        if (i == npos) {
            return npos;
        }
 
        size_t org = i;
        size_t nxt = _table[i].next;
        while (nxt != npos) {
            i = nxt;
            nxt = _table[i].next;
            if (n != npos) {
                if (n-- == 0) {
                    break;
                }
            }
        }
 
        return i == org && n != npos ? npos : i;
    }
 
    constexpr size_t prev(size_t i, size_t n = 0) const {
        if (i >= _table.capacity()) return npos;
        if (i == npos) {
            return npos;
        }
 
        size_t org = i;
        size_t prv = _table[i].prev;
        while (prv != npos) {
            i = prv;
            prv = _table[i].prev;
            if (n != npos) {
                if (n-- == 0) {
                    break;
                }
            }
        }
 
        return i == org && n != npos ? npos : i;
    }
 
    constexpr size_t left_most(size_t i) const {
        if (i >= _table.capacity()) return npos;
        size_t n = i;
        if ((n = child(n)) == npos) {
            return i;
        }
        while (true) {
            size_t p = n;
            if ((n = child(n)) == npos) {
                return p;
            }
        }
    }
 
    constexpr size_t right_most(size_t i) const {
        if (i >= _table.capacity()) return npos;
        if ((i = child(i)) == npos) {
            return npos;
        }
        while (true) {
            size_t n;
            while ((n = next(i)) != npos) {
                i = n;
            }
            n = i;
            if ((i = child(i)) == npos) {
                return n;
            }
        }
    }
 
    constexpr size_t depth(size_t i) const {
        if (i >= _table.capacity()) return npos;
        return i == npos ? npos : _table[i].depth;
    }
 
    constexpr size_t num_children(size_t i) const {
        if (i >= _table.capacity()) return 0;
        return i == npos ? 0 : _table[i].num_children;
    }
 
    constexpr size_t next_id() const {
        size_t i = _size;
        if (not _freed.empty()) {
            i = _freed.front();
        }
        return i;
    }
 
    constexpr value_t& operator[](size_t i) {
        return _table[i].value;
    }
 
    constexpr const value_t& operator[](size_t i) const {
        return _table[i].value;
    }
 
 
// Insertion & Deletion ================================================================================================
 
    constexpr size_t insert(size_t parent, size_t next, const value_t& val) {
        return this->_insert(parent, next, val);
    }
 
    constexpr size_t insert(size_t parent, size_t next, value_t&& val) {
        return this->_insert(parent, next, fennec::forward<value_t>(val));
    }
 
    constexpr size_t insert(size_t parent, size_t next, const rdtree& tree) {
        list<pair<size_t, size_t>> visit;
        visit.push_front({ root, parent });
        size_t res = npos;
 
        while (not visit.empty()) {
            auto node = visit.front();
            visit.pop_front();
 
            size_t p = this->_insert(node.second, node.second == parent ? next : npos, tree[node.first]);
 
            res = (res == npos) ? p : res;
 
            size_t c = tree.child(node.first, npos);
            while (c != npos) {
                visit.push_front({ c, p });
                c = tree._table[c].prev;
            }
        }
 
        return res;
    }
 
    template<typename...ArgsT>
    constexpr size_t emplace(size_t parent, size_t next, ArgsT&&...args) {
        return this->_insert(parent, next, fennec::forward<ArgsT>(args)...);
    }
 
    constexpr void swap(size_t i0, size_t i1) {
        assertf(i0 != root and i1 != root, "Cannot Swap With Root");
 
        size_t p0 = parent(i0);
        size_t p1 = parent(i1);
 
        fennec::swap(_table[i0].parent,       _table[i1].parent);
        fennec::swap(_table[i0].child,        _table[i1].child);
        fennec::swap(_table[i0].next,         _table[i1].next);
        fennec::swap(_table[i0].prev,         _table[i1].prev);
        fennec::swap(_table[i0].depth,        _table[i1].depth);
        fennec::swap(_table[i0].num_children, _table[i1].num_children);
 
        if (child(p0) == i0) _table[p0].child = i1;
        if (child(p1) == i1) _table[p1].child = i0;
    }
 
 
    constexpr void erase(size_t i) {
        _erase(i);
    }
 
 
 
 
// Traversal ===========================================================================================================
 
    template<typename OrderT, typename VisitorT>
    constexpr void traverse(VisitorT&& visit, size_t i = root) {
        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;
 
        constexpr size_t operator()(const rdtree&, size_t start) {
            head = start;
            return start;
        }
 
        constexpr size_t operator[](const rdtree& tree, size_t node, uint8_t mode) {
            if (node == npos) {
                return npos;
            }
 
            size_t nxt = tree.next(node);
            size_t chd = tree.next(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 rdtree&, size_t start) {
            head = start;
            return start;
        }
 
        constexpr size_t operator[](const rdtree& tree, size_t node, uint8_t mode) {
            if (node == npos) {
                return npos;
            }
 
            size_t nxt = tree.next(node);
            size_t chd = tree.child(node);
 
            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 rdtree& tree, size_t start) {
            head = start;
            return tree.left_most(start);
        }
 
        constexpr size_t operator[](const rdtree& tree, size_t node, uint8_t) {
            if (node == npos) {
                return npos;
            }
 
            size_t prnt = tree.parent(node);
            size_t next = tree.next(node);
            if (node != head) {
                if (tree.child(prnt) == node) {
                    visit.push_back(prnt);
                    if (next != npos) {
                        visit.push_back(tree.left_most(next));
                    }
                } else if (next != npos) {
                    visit.push_front(tree.left_most(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 operator()(const rdtree& tree, size_t start) {
            head = start;
            return tree.left_most(start);
        }
 
        constexpr size_t operator[](const rdtree& tree, size_t node, uint8_t) {
            if (node == npos) {
                return npos;
            }
 
            size_t prnt = tree.parent(node);
            size_t next = tree.next(node);
 
            if (node != head) {
                if (next != npos) {
                    visit.push_front(tree.left_most(next));
                } else {
                    visit.push_front(prnt);
                }
            }
 
            if (not visit.empty()) {
                node = visit.front();
                visit.pop_front();
            } else {
                node = npos;
            }
 
            return node;
        }
    };
 
 
protected:
    allocation<node, alloc_t> _table;
    list<size_t>              _freed;
    size_t                    _size;
 
    void _expand() {
        _table.creallocate(_table.capacity() * 2);
    }
 
    size_t _next_free() {
        size_t next = _size;
        if (not _freed.empty()) {
            next = _freed.front();
            _freed.pop_front();
        }
        if (_size >= capacity()) {
            _expand();
        }
        ++_size;
        return next;
    }
 
    template<typename...ArgsT>
    constexpr size_t _insert(size_t p, size_t n, ArgsT&&...args) {
        if (_size == 0) {
            fennec::construct(&_table[root], npos, npos, npos, npos, 0, fennec::forward<ArgsT>(args)...);
            _size = 1;
            return root;
        }
 
        if (p == npos) {
            _table[root].value = value_t(fennec::forward<ArgsT>(args)...);
            _size = _size == 0 ? 1 : _size;
            return root;
        }
 
        size_t idx = _next_free();
        size_t nxt = child(p, n);
        size_t prv = n == npos ? npos : prev(n);
 
        ++_table[p].num_children;
        if ((nxt == child(p) && n != npos) || nxt == npos) {
            _table[p].child = idx;
        }
 
        if (n == npos) {
            if (nxt != npos) {
                _table[nxt].next = idx;
            }
            fennec::construct(&_table[idx], p, npos, nxt, npos, depth(p) + 1, fennec::forward<ArgsT>(args)...);
        } else {
            if (nxt != npos) {
                _table[nxt].prev = idx;
            }
            if (prv != npos) {
                _table[prv].next = idx;
            }
            fennec::construct(&_table[idx], p, npos, prv, nxt, depth(p) + 1, fennec::forward<ArgsT>(args)...);
        }
        return idx;
    }
 
    constexpr void _erase(size_t i) {
        list<size_t> queue;
        queue.push_back(child(i));
        while (not queue.empty()) {
            size_t n = queue.front(); queue.pop_front();
            if (n == npos) continue;
            queue.push_back(next(n));
            queue.push_back(child(n));
            fennec::destruct(&_table[n]);
            _freed.push_back(n);
            --_size;
        }
 
        fennec::destruct(&_table[i]);
        if (i != root) _freed.push_back(i);
        --_size;
    }
};
 
}
 
#endif // FENNEC_CONTAINERS_RDTREE_H