tree.hpp

// Copyright Take Vos 2022.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt)
 
#pragma once
 
#include "utility.hpp"
#include "assert.hpp"
#include <map>
 
namespace hi::inline v1 {
 
template<typename Key, typename T, typename Compare = std::less<Key>>
class tree {
public:
    using key_type = Key;
    using value_type = T;
 
    constexpr ~tree() = default;
    constexpr tree(tree const&) noexcept = default;
    constexpr tree(tree&&) noexcept = default;
    constexpr tree& operator=(tree const&) noexcept = default;
    constexpr tree& operator=(tree&&) noexcept = default;
    constexpr tree() noexcept = default;
 
    value_type& operator()(auto path_first, auto path_last) noexcept
    {
        auto *ptr = find_or_create(path_first, path_last);
        hi_axiom(ptr != nullptr);
        return ptr->value;
    }
 
    value_type const& operator()(auto path_first, auto path_last) const noexcept
    {
        auto *ptr = find(path_first, path_last, [](value_type const&) -> void {});
        hi_axiom(ptr != nullptr);
        return ptr->value;
    }
 
    value_type& operator[](auto const& key) noexcept
    {
        using std::cbegin;
        using std::cend;
        return this->operator()(cbegin(key), cend(key));
    }
 
    value_type const& operator[](auto const& path) const noexcept
    {
        using std::cbegin;
        using std::cend;
        return this->operator()(cbegin(path), cend(path));
    }
 
    /* Walk the tree from the node pointed to by the path.
     *
     * @param path_first The first element of the path to the start node.
     * @param path_last On beyond the last element of the path to the start node.
     * @param func The function `(value_type &) -> void` to execute on the
     */
    void walk(auto path_first, auto path_last, auto&& func) noexcept
    {
        if (auto element = find(path_first, path_last, [](value_type&) -> void {})) {
            _walk(element, hi_forward(func));
        }
    }
 
    /* Walk the tree from the node pointed to by the path.
     *
     * @param path_first The first element of the path to the start node.
     * @param path_last On beyond the last element of the path to the start node.
     * @param func The function `(value_type const &) -> void` to execute on the
     */
    void walk(auto path_first, auto path_last, auto&& func) const noexcept
    {
        if (auto element = find(path_first, path_last, [](value_type const&) -> void {})) {
            _walk(element, hi_forward(func));
        }
    }
 
    /* Walk the tree from the node pointed to by the path.
     *
     * @param path The path (range) to the start node.
     * @param func The function `(value_type &) -> void` to execute on the
     */
    void walk(auto const& key, auto&& func) noexcept
    {
        using std::cbegin;
        using std::cend;
        return walk(cbegin(key), cend(key), hi_forward(func));
    }
 
    /* Walk the tree from the node pointed to by the path.
     *
     * @param path The path (range) to the start node.
     * @param func The function `(value_type const &) -> void` to execute on the
     */
    void walk(auto const& key, auto&& func) const noexcept
    {
        using std::cbegin;
        using std::cend;
        return walk(cbegin(key), cend(key), hi_forward(func));
    }
 
    void walk_including_path(auto path_first, auto path_last, auto const& func) noexcept
    {
        if (auto element = find(path_first, path_last, func)) {
            _walk(element, func);
        }
    }
 
    void walk_including_path(auto path_first, auto path_last, auto const& func) const noexcept
    {
        if (auto element = find(path_first, path_last, func)) {
            _walk(element, func);
        }
    }
 
    void walk_including_path(auto const& path, auto&& func) noexcept
    {
        using std::cbegin;
        using std::cend;
        return walk_including_path(cbegin(path), cend(path), hi_forward(func));
    }
 
    void walk_including_path(auto const& path, auto&& func) const noexcept
    {
        using std::cbegin;
        using std::cend;
        return walk_including_path(cbegin(path), cend(path), hi_forward(func));
    }
 
    void walk(auto&& func) noexcept
    {
        _walk(std::addressof(_root), hi_forward(func));
    }
 
    void walk(auto&& func) const noexcept
    {
        _walk(std::addressof(_root), hi_forward(func));
    }
 
private:
    struct node_type {
        value_type value;
        std::map<key_type, node_type> children;
    };
 
    node_type _root;
 
    [[nodiscard]] constexpr node_type *find(auto path_first, auto path_last, auto const& func) noexcept
    {
        auto *node = &_root;
        for (auto path_it = path_first; path_it != path_last; ++path_it) {
            func(node->value);
 
            if (auto node_it = node->children.find(*path_it); node_it != node->children.end()) {
                node = &node_it->second;
            } else {
                return nullptr;
            }
        }
        return node;
    }
 
    [[nodiscard]] constexpr node_type const *find(auto path_first, auto path_last, auto const& func) const noexcept
    {
        node_type const *node = std::addressof(_root);
        for (auto path_it = path_first; path_it != path_last; ++path_it) {
            func(node->value);
 
            if (auto node_it = node->children.find(*path_it); node_it != node->children.end()) {
                node = std::addressof(node_it->second);
            } else {
                return nullptr;
            }
        }
        return node;
    }
 
    [[nodiscard]] constexpr node_type *find_or_create(auto path_first, auto path_last) noexcept
    {
        auto *node = &_root;
        for (auto path_it = path_first; path_it != path_last; ++path_it) {
            node = &node->children[*path_it];
        }
        return node;
    }
 
    constexpr void _walk(node_type *node, auto const& func) noexcept
    {
        func(node->value);
        for (auto& child : node->children) {
            _walk(&child.second, func);
        }
    }
 
    constexpr void _walk(node_type const *node, auto const& func) const noexcept
    {
        func(node->value);
        for (auto& child : node->children) {
            _walk(&child.second, func);
        }
    }
};
 
} // namespace hi::inline v1