node.hpp

// SPDX-FileCopyrightText: 2008 - 2025 Kohei Yoshida
//
// SPDX-License-Identifier: MIT
 
#pragma once
 
#include "mdds/global.hpp"
 
#include <iostream>
#include <vector>
#include <cassert>
#include <sstream>
 
#include <boost/intrusive_ptr.hpp>
 
namespace mdds { namespace st { namespace detail {
 
#ifdef MDDS_DEBUG_NODE_BASE
 
inline std::size_t node_instance_count = 0;
 
#endif
 
struct node_base
{
    node_base* parent; 
    bool is_leaf;
 
    node_base(bool _is_leaf) noexcept : parent(nullptr), is_leaf(_is_leaf)
    {}
    node_base(const node_base& r) noexcept : parent(nullptr), is_leaf(r.is_leaf)
    {}
};

template<typename KeyT, typename ValueT>
struct nonleaf_node : public node_base
{
    using key_type = KeyT;
    using nonleaf_value_type = ValueT;
 
    nonleaf_value_type value_nonleaf;
 
    key_type low = {}; 
    key_type high = {}; 
 
    node_base* left = nullptr; 
    node_base* right = nullptr; 
 
    static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<key_type> &&
                                                            std::is_nothrow_default_constructible_v<nonleaf_value_type>;
 
    static constexpr bool nothrow_eq_comparable_v =
        noexcept(std::declval<key_type>() == std::declval<key_type>()) &&
        noexcept(std::declval<nonleaf_value_type>() == std::declval<nonleaf_value_type>());
 
public:
    nonleaf_node() noexcept(nothrow_default_constructible_v) : node_base(false), value_nonleaf()
    {}

    nonleaf_node(const nonleaf_node& r) : node_base(r), value_nonleaf(r.value_nonleaf), low(r.low), high(r.high)
    {}

    nonleaf_node& operator=(const nonleaf_node& r)
    {
        if (this == &r)
            // assignment to self.
            return *this;
 
        value_nonleaf = r.value_nonleaf;
        return *this;
    }
 
    bool operator==(const nonleaf_node& r) const noexcept(nothrow_eq_comparable_v)
    {
        return low == r.low && high == r.high && value_nonleaf == r.value_nonleaf;
    }
 
    bool operator!=(const nonleaf_node& r) const noexcept(nothrow_eq_comparable_v)
    {
        return !operator==(r);
    }
 
    std::string to_string() const
    {
        std::ostringstream os;
        os << "[" << low << "-" << high << ")";
        return os.str();
    }
};

template<typename KeyT, typename ValueT>
struct node : node_base
{
    using key_type = KeyT;
    using leaf_value_type = ValueT;
    using node_ptr = boost::intrusive_ptr<node>;
 
    static size_t get_instance_count()
    {
#ifdef MDDS_DEBUG_NODE_BASE
        return node_instance_count;
#else
        return 0;
#endif
    }
 
    leaf_value_type value_leaf;
 
    key_type key = {};
 
    node_ptr prev; 
    node_ptr next; 
 
    std::size_t refcount = 0;
 
    static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<key_type> &&
                                                            std::is_nothrow_default_constructible_v<leaf_value_type> &&
                                                            std::is_nothrow_default_constructible_v<node_ptr>;
 
    static constexpr bool nothrow_eq_comparable_v =
        noexcept(std::declval<key_type>() == std::declval<key_type>()) &&
        noexcept(std::declval<leaf_value_type>() == std::declval<leaf_value_type>());
 
public:
    node() noexcept(nothrow_default_constructible_v) : node_base(true)
    {
#ifdef MDDS_DEBUG_NODE_BASE
        ++node_instance_count;
#endif
    }

    node(const node& r) : node_base(r), key(r.key)
    {
#ifdef MDDS_DEBUG_NODE_BASE
        ++node_instance_count;
#endif
        value_leaf = r.value_leaf;
    }

    node& operator=(const node& r)
    {
        if (this == &r)
            // assignment to self.
            return *this;
 
        value_leaf = r.value_leaf;
        return *this;
    }
 
    ~node()
    {
#ifdef MDDS_DEBUG_NODE_BASE
        --node_instance_count;
#endif
    }
 
    bool operator==(const node& r) const noexcept(nothrow_eq_comparable_v)
    {
        return key == r.key && value_leaf == r.value_leaf;
    }
 
    bool operator!=(const node& r) const noexcept(nothrow_eq_comparable_v)
    {
        return !operator==(r);
    }
 
    std::string to_string() const
    {
        std::ostringstream os;
        os << "[" << key << "]";
        return os.str();
    }
};
 
template<typename KeyT, typename ValueT>
inline void intrusive_ptr_add_ref(node<KeyT, ValueT>* p)
{
    ++p->refcount;
}
 
template<typename KeyT, typename ValueT>
inline void intrusive_ptr_release(node<KeyT, ValueT>* p)
{
    --p->refcount;
    if (!p->refcount)
        delete p;
}
 
template<typename NodePtrT>
void link_nodes(NodePtrT& left, NodePtrT& right)
{
    left->next = right;
    right->prev = left;
}
 
template<typename T>
class tree_builder
{
public:
    typedef typename T::node leaf_node;
    typedef typename leaf_node::node_ptr leaf_node_ptr;
    typedef typename T::nonleaf_node nonleaf_node;
    typedef std::vector<nonleaf_node> nonleaf_node_pool_type;
 
    tree_builder(nonleaf_node_pool_type& pool) : m_pool(pool), m_pool_pos(pool.begin()), m_pool_pos_end(pool.end())
    {}
 
    nonleaf_node* build(const leaf_node_ptr& left_leaf_node)
    {
        if (!left_leaf_node)
            // The left leaf node is empty.  Nothing to build.
            return nullptr;
 
        leaf_node_ptr node1 = left_leaf_node;
 
        std::vector<nonleaf_node*> node_list;
        while (true)
        {
            leaf_node_ptr node2 = node1->next;
            nonleaf_node* parent_node = make_parent_node(node1.get(), node2.get());
            node_list.push_back(parent_node);
 
            if (!node2 || !node2->next)
                // no more nodes.  Break out of the loop.
                break;
 
            node1 = node2->next;
        }
 
        return build_tree_non_leaf(node_list);
    }
 
private:
    nonleaf_node* make_parent_node(node_base* node1, node_base* node2)
    {
        assert(m_pool_pos != m_pool_pos_end);
 
        nonleaf_node* parent_node = &(*m_pool_pos);
        ++m_pool_pos;
        node1->parent = parent_node;
        parent_node->left = node1;
        if (node2)
        {
            node2->parent = parent_node;
            parent_node->right = node2;
        }
 
        fill_nonleaf_parent_node(parent_node, node1, node2);
        return parent_node;
    }
 
    void fill_nonleaf_parent_node(nonleaf_node* parent_node, const node_base* left_node, const node_base* right_node)
    {
        // Parent node should carry the range of all of its child nodes.
        if (left_node)
        {
            parent_node->low = left_node->is_leaf ? static_cast<const leaf_node*>(left_node)->key
                                                  : static_cast<const nonleaf_node*>(left_node)->low;
        }
        else
        {
            // Having a left node is prerequisite.
            throw general_error("fill_nonleaf_parent_node: Having a left node is prerequisite.");
        }
 
        if (right_node)
        {
            if (right_node->is_leaf)
            {
                // When the child nodes are leaf nodes, the upper bound
                // must be the value of the node that comes after the
                // right leaf node (if such node exists).
 
                const auto* p = static_cast<const leaf_node*>(right_node);
                if (p->next)
                    parent_node->high = p->next->key;
                else
                    parent_node->high = p->key;
            }
            else
            {
                parent_node->high = static_cast<const nonleaf_node*>(right_node)->high;
            }
        }
        else
        {
            parent_node->high = left_node->is_leaf ? static_cast<const leaf_node*>(left_node)->key
                                                   : static_cast<const nonleaf_node*>(left_node)->high;
        }
    }
 
    nonleaf_node* build_tree_non_leaf(const std::vector<nonleaf_node*>& node_list)
    {
        size_t node_count = node_list.size();
        if (node_count == 1)
        {
            return node_list.front();
        }
        else if (node_count == 0)
            return nullptr;
 
        std::vector<nonleaf_node*> new_node_list;
        nonleaf_node* node1 = nullptr;
        typename std::vector<nonleaf_node*>::const_iterator it = node_list.begin();
        typename std::vector<nonleaf_node*>::const_iterator it_end = node_list.end();
        for (bool even_itr = false; it != it_end; ++it, even_itr = !even_itr)
        {
            if (even_itr)
            {
                nonleaf_node* node2 = *it;
                nonleaf_node* parent_node = make_parent_node(node1, node2);
                new_node_list.push_back(parent_node);
                node1 = nullptr;
                node2 = nullptr;
            }
            else
                node1 = *it;
        }
 
        if (node1)
        {
            // Un-paired node still needs a parent...
            nonleaf_node* parent_node = make_parent_node(node1, nullptr);
            new_node_list.push_back(parent_node);
        }
 
        // Move up one level, and do the same procedure until the root node is reached.
        return build_tree_non_leaf(new_node_list);
    }
 
    nonleaf_node_pool_type& m_pool;
    typename nonleaf_node_pool_type::iterator m_pool_pos;
    typename nonleaf_node_pool_type::iterator m_pool_pos_end;
};
 
template<typename KeyT, typename ValueT>
void disconnect_all_nodes(node<KeyT, ValueT>* p)
{
    if (!p)
        return;
 
    p->prev.reset();
    p->next.reset();
    p->parent = nullptr;
}
 
template<typename KeyT, typename ValueT>
void disconnect_leaf_nodes(node<KeyT, ValueT>* left_node, node<KeyT, ValueT>* right_node)
{
    if (!left_node || !right_node)
        return;
 
    // Go through all leaf nodes, and disconnect their links.
    auto* cur_node = left_node;
    do
    {
        auto* next_node = cur_node->next.get();
        disconnect_all_nodes(cur_node);
        cur_node = next_node;
    } while (cur_node != right_node);
 
    disconnect_all_nodes(right_node);
}
 
template<typename SizeT, typename KeyT, typename ValueT>
SizeT count_leaf_nodes(const node<KeyT, ValueT>* left_end, const node<KeyT, ValueT>* right_end) noexcept(
    noexcept(++std::declval<SizeT&>()))
{
    SizeT leaf_count = 1;
    const auto* p = left_end;
    const auto* p_end = right_end;
    for (; p != p_end; p = p->next.get(), ++leaf_count)
        ;
 
    return leaf_count;
}
 
inline size_t count_needed_nonleaf_nodes(size_t leaf_count)
{
    size_t nonleaf_count = 0;
    while (true)
    {
        if (leaf_count == 1)
            break;
 
        if ((leaf_count % 2) == 1)
            // Add one to make it an even number.
            ++leaf_count;
 
        leaf_count /= 2;
        nonleaf_count += leaf_count;
    }
 
    return nonleaf_count;
}
 
template<typename TraitsT>
class tree_dumper
{
    using node_list_type = std::vector<const node_base*>;
    using tree_type = typename TraitsT::tree_type;
 
public:
    static size_t dump(std::ostream& os, const tree_type& tree, const node_base* root_node)
    {
        if (!root_node)
            return 0;
 
        node_list_type node_list;
        node_list.push_back(root_node);
        return dump_layer(os, tree, node_list, 0);
    }
 
private:
    static size_t dump_layer(
        std::ostream& os, const tree_type& tree, const node_list_type& node_list, unsigned int level)
    {
        using leaf_type = typename TraitsT::leaf_type;
        using nonleaf_type = typename TraitsT::nonleaf_type;
        using to_string = typename TraitsT::to_string;
 
        if (node_list.empty())
            return 0;
 
        size_t node_count = node_list.size();
 
        bool is_leaf = node_list.front()->is_leaf;
        os << "level " << level << ':' << std::endl;
        os << "  type: " << (is_leaf ? "leaf" : "non-leaf") << std::endl;
        os << "  nodes:" << std::endl;
 
        node_list_type new_list;
 
        for (const node_base* p : node_list)
        {
            os << "    - '";
 
            if (!p)
            {
                os << "*'" << std::endl;
                continue;
            }
 
            if (p->is_leaf)
            {
                const auto* pl = static_cast<const leaf_type*>(p);
                os << to_string{tree}(*pl) << "'" << std::endl;
                continue;
            }
 
            const auto* pnl = static_cast<const nonleaf_type*>(p);
            os << to_string{tree}(*pnl) << "'" << std::endl;
 
            if (pnl->left)
            {
                new_list.push_back(pnl->left);
                if (pnl->right)
                    new_list.push_back(pnl->right);
            }
        }
 
        if (!new_list.empty())
            node_count += dump_layer(os, tree, new_list, level + 1);
 
        return node_count;
    }
};
 
}}} // namespace mdds::st::detail