flat_segment_tree.hpp

/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/*************************************************************************
 *
 * Copyright (c) 2008-2023 Kohei Yoshida
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 *
 ************************************************************************/

#ifndef INCLUDED_MDDS_FLAT_SEGMENT_TREE_HPP
#define INCLUDED_MDDS_FLAT_SEGMENT_TREE_HPP

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

#include "mdds/node.hpp"
#include "mdds/flat_segment_tree_itr.hpp"
#include "mdds/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
    {
    };

    struct leaf_value_type
    {
        value_type value;

        bool operator==(const leaf_value_type& r) const
        {
            return value == r.value;
        }

        bool operator!=(const leaf_value_type& r) const
        {
            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>;

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);

    ~flat_segment_tree();

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

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

    void swap(flat_segment_tree& other);

    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 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 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 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;
    }

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

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

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

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

    value_type default_value() const
    {
        return m_init_val;
    }

    size_type leaf_size() const;

#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)
{
    left.swap(right);
}

} // namespace mdds

#include "flat_segment_tree_def.inl"

#endif

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