hyperoctree.hpp

Go to the documentation of this file.

/*
 * Copyright (C) 2023  Christopher J. Howard
 *
 * This file is part of Antkeeper source code.
 *
 * Antkeeper source code 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.
 *
 * Antkeeper source code 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 Antkeeper source code.  If not, see <http://www.gnu.org/licenses/>.
 */
 
#ifndef ANTKEEPER_GEOM_HYPEROCTREE_HPP
#define ANTKEEPER_GEOM_HYPEROCTREE_HPP
 
#include <engine/math/compile.hpp>
#include <algorithm>
#include <array>
#include <bit>
#include <concepts>
#include <cstddef>
#include <set>
#include <type_traits>
#include <unordered_set>
 
namespace geom {
 
enum class hyperoctree_order
{
    unordered,
    
    dfs_pre,
    
    bfs
};
 
template <std::unsigned_integral T>
using hyperoctree_dfs_pre_compare = std::less<T>;
 
template <std::unsigned_integral T, std::size_t DepthBits>
struct hyperoctree_bfs_compare
{
    constexpr bool operator()(const T& lhs, const T& rhs) const noexcept
    {
        return std::rotr(lhs, DepthBits) < std::rotr(rhs, DepthBits);
    }
};
 
template <hyperoctree_order Order, std::unsigned_integral T, std::size_t DepthBits>
struct hyperoctree_container {};
 
template <std::unsigned_integral T, std::size_t DepthBits>
struct hyperoctree_container<hyperoctree_order::unordered, T, DepthBits>
{
    typedef std::unordered_set<T> type;
};
 
template <std::unsigned_integral T, std::size_t DepthBits>
struct hyperoctree_container<hyperoctree_order::dfs_pre, T, DepthBits>
{
    typedef std::set<T, hyperoctree_dfs_pre_compare<T>> type;
};
 
template <std::unsigned_integral T, std::size_t DepthBits>
struct hyperoctree_container<hyperoctree_order::bfs, T, DepthBits>
{
    typedef std::set<T, hyperoctree_bfs_compare<T, DepthBits>> type;
};
 
template <std::unsigned_integral T, std::size_t N, hyperoctree_order Order = hyperoctree_order::dfs_pre>
class hyperoctree
{
private:
    static consteval std::size_t find_max_depth() noexcept
    {
        std::size_t max_depth = 0;
        for (std::size_t i = 1; i <= sizeof(T) * 8; ++i)
        {
            const std::size_t location_bits = sizeof(T) * 8 - i;
            max_depth = location_bits / N - 1;
            const std::size_t depth_bits = static_cast<std::size_t>(std::bit_width(max_depth));
            
            if (depth_bits + location_bits < sizeof(T) * 8)
                break;
        }
        return static_cast<T>(max_depth);
    }
    
public:
    typedef T node_type;
    
    static constexpr std::size_t dimensions = N;
    
    static constexpr hyperoctree_order order = Order;
    
    static constexpr node_type max_depth = find_max_depth();
    
    static constexpr node_type node_bits = sizeof(node_type) * 8;
    
    static constexpr node_type depth_bits = std::bit_width(max_depth);
    
    static constexpr node_type location_bits = (max_depth + 1) * N;
    
    static constexpr node_type divider_bits = node_bits - (depth_bits + location_bits);
    
    static constexpr node_type children_per_node = math::compile::exp2<node_type>(N);
    
    static constexpr node_type siblings_per_node = children_per_node - 1;
    
    static constexpr node_type resolution = math::compile::exp2<node_type>(max_depth);
    
    static constexpr std::size_t max_node_count = (math::compile::pow<std::size_t>(resolution * 2, N) - 1) / siblings_per_node;
    
    static constexpr node_type root = 0;
    
    typedef typename hyperoctree_container<order, node_type, depth_bits>::type container_type;
    
    typedef typename container_type::iterator iterator;
    
    typedef typename container_type::const_iterator const_iterator;
    
    typedef std::conditional<order != hyperoctree_order::unordered, std::reverse_iterator<iterator>, iterator>::type reverse_iterator;
    
    typedef std::conditional<order != hyperoctree_order::unordered, std::reverse_iterator<const_iterator>, const_iterator>::type const_reverse_iterator;
    
 
    static inline constexpr node_type depth(node_type node) noexcept
    {
        constexpr node_type mask = math::compile::exp2<node_type>(depth_bits) - 1;
        return node & mask;
    }
    
    static inline constexpr node_type location(node_type node) noexcept
    {
        return node >> ((node_bits - 1) - depth(node) * N);
    }
    
    static constexpr std::array<node_type, 2> split(node_type node) noexcept
    {
        const node_type depth = hyperoctree::depth(node);
        const node_type location = node >> ((node_bits - 1) - depth * N);
        return {depth, location};
    }
    
    static inline constexpr node_type node(node_type depth, node_type location) noexcept
    {
        return (location << ((node_bits - 1) - depth * N)) | depth;
    }
    
    static inline constexpr node_type ancestor(node_type node, node_type depth) noexcept
    {
        const node_type mask = (~node_type(0)) << ((node_bits - 1) - depth * N);
        return (node & mask) | depth;
    }
    
    static inline constexpr node_type parent(node_type node) noexcept
    {
        return ancestor(node, depth(node) - 1);
    }
    
    static constexpr node_type sibling(node_type node, node_type n) noexcept
    {
        constexpr node_type mask = (1 << N) - 1;
        const auto [depth, location] = split(node);
        const node_type sibling_location = (location & (~mask)) | ((location + n) & mask);
        return hyperoctree::node(depth, sibling_location);
    }
    
    static inline constexpr node_type child(node_type node, T n) noexcept
    {
        return sibling(node + 1, n);
    }
    
    static constexpr node_type common_ancestor(node_type a, node_type b) noexcept
    {
        const node_type bits = std::min<node_type>(depth(a), depth(b)) * N;
        const node_type marker = (node_type(1) << (node_bits - 1)) >> bits;
        const node_type depth = node_type(std::countl_zero((a ^ b) | marker) / N);
        return ancestor(a, depth);
    }
    
    hyperoctree():
        nodes({root})
    {}
    
 
    inline iterator begin() noexcept
    {
        return nodes.begin();
    }
    inline const_iterator begin() const noexcept
    {
        return nodes.begin();
    }
    inline const_iterator cbegin() const noexcept
    {
        return nodes.cbegin();
    }
    
    inline iterator end() noexcept
    {
        return nodes.end();
    }
    inline const_iterator end() const noexcept
    {
        return nodes.end();
    }
    inline const_iterator cend() const noexcept
    {
        return nodes.cend();
    }
    
    inline reverse_iterator rbegin() noexcept
    {
        if constexpr (order != hyperoctree_order::unordered)
            return nodes.rbegin();
        else
            return nodes.begin();
    }
    inline const_reverse_iterator rbegin() const noexcept
    {
        if constexpr (order != hyperoctree_order::unordered)
            return nodes.rbegin();
        else
            return nodes.begin();
    }
    inline const_reverse_iterator crbegin() const noexcept
    {
        if constexpr (order != hyperoctree_order::unordered)
            return nodes.crbegin();
        else
            return nodes.cbegin();
    }
    
    inline reverse_iterator rend() noexcept
    {
        if constexpr (order != hyperoctree_order::unordered)
            return nodes.rend();
        else
            return nodes.end();
    }
    inline const_reverse_iterator rend() const noexcept
    {
        if constexpr (order != hyperoctree_order::unordered)
            return nodes.rend();
        else
            return nodes.end();
    }
    inline const_reverse_iterator crend() const noexcept
    {
        if constexpr (order != hyperoctree_order::unordered)
            return nodes.crend();
        else
            return nodes.cend();
    }
    
 
    inline bool empty() const noexcept
    {
        return nodes.empty();
    }
    
    inline bool full() const noexcept
    {
        return size() == max_size();
    }
    
    inline std::size_t size() const noexcept
    {
        return nodes.size();
    }
    
    constexpr std::size_t max_size() const noexcept
    {
        return max_node_count;
    }
    
 
    inline void clear()
    {
        nodes = {root};
    }
    
    void insert(node_type node)
    {
        if (contains(node))
            return;
        
        // Insert node
        nodes.emplace(node);
        
        // Insert node siblings
        for (node_type i = 1; i < children_per_node; ++i)
            nodes.emplace(sibling(node, i));
        
        // Insert node ancestors
        insert(parent(node));
    }
    
    void erase(node_type node)
    {
        if (node == root || !contains(node))
            return;
        
        // Erase node and its descendants
        nodes.erase(node);
        erase(child(node, 0));
        
        // Erase node siblings
        for (node_type i = 0; i < siblings_per_node; ++i)
        {
            node = sibling(node, 1);
            
            // Erase sibling and its descendants
            nodes.erase(node);
            erase(child(node, 0));
        }
    }
    
 
    inline bool contains(node_type node) const
    {
        return nodes.contains(node);
    }
    
    inline bool is_leaf(node_type node) const
    {
        return !contains(child(node, 0));
    }
    
private:
    container_type nodes;
};
 
template <std::unsigned_integral T, std::size_t N>
using unordered_hyperoctree = hyperoctree<T, N, hyperoctree_order::unordered>;
 
} // namespace geom
 
#endif // ANTKEEPER_GEOM_HYPEROCTREE_HPP