flat_segment_tree.hpp

/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */

// SPDX-FileCopyrightText: 2008 - 2025 Kohei Yoshida
//
// SPDX-License-Identifier: MIT

#pragma once

#include <iostream>
#include <sstream>
#include <utility>
#include <cassert>
#include <type_traits>

#include "./node.hpp"
#include "./flat_segment_tree_itr.hpp"
#include "./global.hpp"

#ifdef MDDS_UNIT_TEST
#include <cstdio>
#include <vector>
#endif

namespace mdds {

template<typename Key, typename Value>
class flat_segment_tree
{
public:
    typedef Key key_type;
    typedef Value value_type;
    typedef size_t size_type;

    struct nonleaf_value_type
    {
        bool operator==(const nonleaf_value_type&) const noexcept
        {
            return true;
        }
    };

    struct leaf_value_type
    {
        value_type value;

        bool operator==(const leaf_value_type& r) const
            noexcept(noexcept(std::declval<value_type>() == std::declval<value_type>()))
        {
            return value == r.value;
        }

        bool operator!=(const leaf_value_type& r) const noexcept(noexcept(!operator==(r)))
        {
            return !operator==(r);
        }

        leaf_value_type() : value{}
        {}
    };

    using node = st::detail::node<key_type, leaf_value_type>;
    using node_ptr = typename node::node_ptr;
    using nonleaf_node = st::detail::nonleaf_node<key_type, nonleaf_value_type>;

private:
    friend struct ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>;
    friend struct ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>;

    static constexpr bool nothrow_move_constructible_v =
        std::is_nothrow_move_constructible_v<std::vector<nonleaf_node>> &&
        std::is_nothrow_move_constructible_v<value_type>;

    static constexpr bool nothrow_swappable_v =
        std::is_nothrow_swappable_v<value_type> && std::is_nothrow_swappable_v<std::vector<nonleaf_node>>;

    static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;

    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:
    using const_segment_iterator = mdds::fst::detail::const_segment_iterator<flat_segment_tree>;

    class const_iterator : public ::mdds::fst::detail::const_iterator_base<
                               flat_segment_tree, ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>>
    {
        typedef ::mdds::fst::detail::const_iterator_base<
            flat_segment_tree, ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>>
            base_type;
        friend class flat_segment_tree;

        using base_type::get_parent;
        using base_type::get_pos;
        using base_type::is_end_pos;

    public:
        const_iterator() : base_type(nullptr, false)
        {}

        const_segment_iterator to_segment() const;

    private:
        explicit const_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
        {}

        explicit const_iterator(const typename base_type::fst_type* _db, const node* p) : base_type(_db, p)
        {}
    };

    class const_reverse_iterator : public ::mdds::fst::detail::const_iterator_base<
                                       flat_segment_tree, ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>>
    {
        typedef ::mdds::fst::detail::const_iterator_base<
            flat_segment_tree, ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>>
            base_type;
        friend class flat_segment_tree;

    public:
        const_reverse_iterator() : base_type(nullptr, false)
        {}

    private:
        explicit const_reverse_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
        {}
    };

    class const_segment_range_type
    {
        node_ptr m_left_leaf;
        node_ptr m_right_leaf;

    public:
        const_segment_range_type(node_ptr left_leaf, node_ptr right_leaf);

        const_segment_iterator begin() const;
        const_segment_iterator end() const;
    };

    const_iterator begin() const
    {
        return const_iterator(this, false);
    }

    const_iterator end() const
    {
        return const_iterator(this, true);
    }

    const_reverse_iterator rbegin() const
    {
        return const_reverse_iterator(this, false);
    }

    const_reverse_iterator rend() const
    {
        return const_reverse_iterator(this, true);
    }

    const_segment_iterator begin_segment() const;

    const_segment_iterator end_segment() const;

    const_segment_range_type segment_range() const;

    flat_segment_tree() = delete;

    flat_segment_tree(key_type min_val, key_type max_val, value_type init_val);

    flat_segment_tree(const flat_segment_tree& r);

    flat_segment_tree(flat_segment_tree&& other) noexcept(nothrow_move_constructible_v);

    ~flat_segment_tree();

    flat_segment_tree<Key, Value>& operator=(const flat_segment_tree& other);

    flat_segment_tree<Key, Value>& operator=(flat_segment_tree&& other) noexcept(nothrow_move_assignable_v);

    void swap(flat_segment_tree& other) noexcept(nothrow_swappable_v);

    void clear();

    std::pair<const_iterator, bool> insert_front(key_type start_key, key_type end_key, value_type val)
    {
        return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val), true);
    }

    std::pair<const_iterator, bool> insert_back(key_type start_key, key_type end_key, value_type val)
    {
        return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val), false);
    }

    std::pair<const_iterator, bool> insert(const_iterator pos, key_type start_key, key_type end_key, value_type val);

    void shift_left(key_type start_key, key_type end_key);

    void shift_right(key_type pos, key_type size, bool skip_start_node);

    std::pair<const_iterator, bool> search(
        key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;

    std::pair<const_iterator, bool> search(
        const_iterator pos, key_type key, value_type& value, key_type* start_key = nullptr,
        key_type* end_key = nullptr) const;

    const_iterator search(key_type key) const;

    const_iterator search(const_iterator pos, key_type key) const;

    std::pair<const_iterator, bool> search_tree(
        key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;

    const_iterator search_tree(key_type key) const;

    void build_tree();

    bool valid_tree() const noexcept
    {
        return m_valid_tree;
    }

    [[deprecated("Use valid_tree() instead")]]
    bool is_tree_valid() const noexcept
    {
        return m_valid_tree;
    }

    bool operator==(const flat_segment_tree& other) const noexcept(nothrow_eq_comparable_v);

    bool operator!=(const flat_segment_tree& other) const noexcept(nothrow_eq_comparable_v)
    {
        return !operator==(other);
    }

    const key_type& min_key() const noexcept
    {
        return m_left_leaf->key;
    }

    const key_type& max_key() const noexcept
    {
        return m_right_leaf->key;
    }

    const value_type& default_value() const noexcept
    {
        return m_init_val;
    }

    size_type leaf_size() const
        noexcept(noexcept(st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get())))
    {
        return st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get());
    }

#ifdef MDDS_UNIT_TEST
    const nonleaf_node* get_root_node() const
    {
        return m_root_node;
    }

    struct tree_dumper_traits
    {
        using leaf_type = node;
        using nonleaf_type = nonleaf_node;
        using tree_type = flat_segment_tree;

        struct to_string
        {
            to_string(const tree_type&)
            {}

            std::string operator()(const leaf_type& leaf) const
            {
                return leaf.to_string();
            }

            std::string operator()(const nonleaf_type& nonleaf) const
            {
                return nonleaf.to_string();
            }
        };
    };

    void dump_tree() const
    {
        using ::std::cout;
        using ::std::endl;

        if (!m_valid_tree)
            assert(!"attempted to dump an invalid tree!");

        size_t node_count = mdds::st::detail::tree_dumper<tree_dumper_traits>::dump(std::cout, *this, m_root_node);
        size_t node_instance_count = node::get_instance_count();
        size_t leaf_count = leaf_size();

        cout << "tree node count = " << node_count << "; node instance count = " << node_instance_count
             << "; leaf node count = " << leaf_count << endl;

        assert(leaf_count == node_instance_count);
    }

    void dump_leaf_nodes() const
    {
        using ::std::cout;
        using ::std::endl;

        cout << "------------------------------------------" << endl;

        node_ptr cur_node = m_left_leaf;
        long node_id = 0;
        while (cur_node)
        {
            cout << "  node " << node_id++ << ": key = " << cur_node->key << "; value = " << cur_node->value_leaf.value
                 << endl;
            cur_node = cur_node->next;
        }
        cout << endl << "  node instance count = " << node::get_instance_count() << endl;
    }

    bool verify_keys(const ::std::vector<key_type>& key_values) const
    {
        {
            // Start from the left-most node, and traverse right.
            node* cur_node = m_left_leaf.get();
            typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
            for (; itr != itr_end; ++itr)
            {
                if (!cur_node)
                    // Position past the right-mode node.  Invalid.
                    return false;

                if (cur_node->key != *itr)
                    // Key values differ.
                    return false;

                cur_node = cur_node->next.get();
            }

            if (cur_node)
                // At this point, we expect the current node to be at the position
                // past the right-most node, which is nullptr.
                return false;
        }

        {
            // Start from the right-most node, and traverse left.
            node* cur_node = m_right_leaf.get();
            typename ::std::vector<key_type>::const_reverse_iterator itr = key_values.rbegin(),
                                                                     itr_end = key_values.rend();
            for (; itr != itr_end; ++itr)
            {
                if (!cur_node)
                    // Position past the left-mode node.  Invalid.
                    return false;

                if (cur_node->key != *itr)
                    // Key values differ.
                    return false;

                cur_node = cur_node->prev.get();
            }

            if (cur_node)
                // Likewise, we expect the current position to be past the
                // left-most node, in which case the node value is nullptr.
                return false;
        }

        return true;
    }

    bool verify_values(const ::std::vector<value_type>& values) const
    {
        node* cur_node = m_left_leaf.get();
        node* end_node = m_right_leaf.get();
        typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
        for (; itr != itr_end; ++itr)
        {
            if (cur_node == end_node || !cur_node)
                return false;

            if (cur_node->value_leaf.value != *itr)
                // Key values differ.
                return false;

            cur_node = cur_node->next.get();
        }

        if (cur_node != end_node)
            // At this point, we expect the current node to be at the end of
            // range.
            return false;

        return true;
    }
#endif

private:
    const_iterator search_by_key_impl(const node* start_pos, key_type key) const;

    const node* search_tree_for_leaf_node(key_type key) const;

    void append_new_segment(key_type start_key)
    {
        if (m_right_leaf->prev->key == start_key)
        {
            m_right_leaf->prev->value_leaf.value = m_init_val;
            return;
        }

#ifdef MDDS_UNIT_TEST
        // The start position must come after the position of the last node
        // before the right-most node.
        assert(m_right_leaf->prev->key < start_key);
#endif

        if (m_right_leaf->prev->value_leaf.value == m_init_val)
            // The existing segment has the same value.  No need to insert a
            // new segment.
            return;

        node_ptr new_node(new node);
        new_node->key = start_key;
        new_node->value_leaf.value = m_init_val;
        new_node->prev = m_right_leaf->prev;
        new_node->next = m_right_leaf;
        m_right_leaf->prev->next = new_node;
        m_right_leaf->prev = std::move(new_node);
        m_valid_tree = false;
    }

    ::std::pair<const_iterator, bool> insert_segment_impl(
        key_type start_key, key_type end_key, value_type val, bool forward);

    ::std::pair<const_iterator, bool> insert_to_pos(
        node_ptr start_pos, key_type start_key, key_type end_key, value_type val);

    ::std::pair<const_iterator, bool> search_impl(
        const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key) const;

    const node* get_insertion_pos_leaf_reverse(const key_type& key, const node* start_pos) const;

    const node* get_insertion_pos_leaf(const key_type& key, const node* start_pos) const;

    static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
    {
        node* cur_node_p = begin_node.get();
        node* end_node_p = end_node.get();
        while (cur_node_p != end_node_p)
        {
            cur_node_p->key -= shift_value;
            cur_node_p = cur_node_p->next.get();
        }
    }

    static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
    {
        key_type end_node_key = end_node->key;
        while (cur_node.get() != end_node.get())
        {
            cur_node->key += shift_value;
            if (cur_node->key < end_node_key)
            {
                // The node is still in-bound.  Keep shifting.
                cur_node = cur_node->next;
                continue;
            }

            // This node has been pushed outside the end node position.
            // Remove all nodes that follows, and connect the previous node
            // with the end node.

            node_ptr last_node = cur_node->prev;
            while (cur_node.get() != end_node.get())
            {
                node_ptr next_node = cur_node->next;
                disconnect_all_nodes(cur_node.get());
                cur_node = std::move(next_node);
            }
            last_node->next = end_node;
            end_node->prev = std::move(last_node);
            return;
        }
    }

    void destroy();

    bool adjust_segment_range(key_type& start_key, key_type& end_key) const;

private:
    std::vector<nonleaf_node> m_nonleaf_node_pool;

    const nonleaf_node* m_root_node;
    node_ptr m_left_leaf;
    node_ptr m_right_leaf;
    value_type m_init_val;
    bool m_valid_tree;
};

template<typename Key, typename Value>
void swap(flat_segment_tree<Key, Value>& left, flat_segment_tree<Key, Value>& right) noexcept(
    std::is_nothrow_swappable_v<flat_segment_tree<Key, Value>>)
{
    left.swap(right);
}

} // namespace mdds

#include "flat_segment_tree_def.inl"

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */