segment_tree.hpp

/*************************************************************************
 *
 * Copyright (c) 2010-2015 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_SEGMENTTREE_HPP
#define INCLUDED_MDDS_SEGMENTTREE_HPP

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

#include <vector>
#include <deque>
#include <iostream>
#include <map>
#include <unordered_map>
#include <memory>
#include <sstream>

namespace mdds {

template<typename KeyT, typename ValueT>
class segment_tree
{
public:
    using key_type = KeyT;
    using value_type = ValueT;
    using size_type = std::size_t;

private:
    struct segment_type
    {
        key_type start;
        key_type end;
        value_type value;

        segment_type();
        segment_type(key_type _start, key_type _end, value_type _value);
        segment_type(const segment_type&) = default;
        segment_type(segment_type&&) = default;

        segment_type& operator=(const segment_type& r) = default;
        segment_type& operator=(segment_type&& r) = default;
        bool operator<(const segment_type& r) const;
        bool operator==(const segment_type& r) const;
        bool operator!=(const segment_type& r) const;
    };

    using segment_store_type = std::deque<segment_type>;
    using value_pos_type = typename segment_store_type::size_type;
    using value_chain_type = std::vector<value_pos_type>;

    using node_chain_type = std::vector<st::detail::node_base*>;
    using value_to_nodes_type = std::map<value_pos_type, node_chain_type>;

    struct nonleaf_value_type
    {
        std::unique_ptr<value_chain_type> data_chain;

        nonleaf_value_type()
        {}
        nonleaf_value_type(const nonleaf_value_type& r)
        {
            if (r.data_chain)
                data_chain = std::make_unique<value_chain_type>(*r.data_chain);
        }

        bool operator==(const nonleaf_value_type& r) const
        {
            return data_chain == r.data_chain;
        }

        ~nonleaf_value_type()
        {}
    };

    struct leaf_value_type
    {
        std::unique_ptr<value_chain_type> data_chain;

        leaf_value_type()
        {}
        leaf_value_type(const leaf_value_type& r)
        {
            if (r.data_chain)
                data_chain = std::make_unique<value_chain_type>(*r.data_chain);
        }

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

        ~leaf_value_type()
        {}
    };

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

private:
    class search_result_inserter;

    class search_results_base
    {
        friend class search_result_inserter;

    public:
        typedef std::vector<value_chain_type*> res_chains_type;
        typedef std::shared_ptr<res_chains_type> res_chains_ptr;

    protected:
        search_results_base(const segment_store_type& segment_store) : m_segment_store(&segment_store)
        {}

        search_results_base(const search_results_base& r)
            : m_segment_store(r.m_segment_store), mp_res_chains(r.mp_res_chains)
        {}

        bool empty() const;

        size_type size() const;

        void push_back_chain(value_chain_type* chain);

        const segment_store_type* get_segment_store() const
        {
            return m_segment_store;
        }

        const res_chains_ptr& get_res_chains() const
        {
            return mp_res_chains;
        }

    private:
        const segment_store_type* m_segment_store = nullptr;
        res_chains_ptr mp_res_chains;
    };

    class const_iterator_base
    {
        friend class segment_tree;

    protected:
        typedef typename search_results_base::res_chains_type res_chains_type;
        typedef typename search_results_base::res_chains_ptr res_chains_ptr;

        const_iterator_base(const segment_store_type* segment_store, const res_chains_ptr& p)
            : m_segment_store(segment_store), mp_res_chains(p), m_end_pos(true)
        {}

    public:
        using iterator_category = std::bidirectional_iterator_tag;
        using value_type = const segment_tree::segment_type;
        using pointer = value_type*;
        using reference = value_type&;
        using difference_type = std::ptrdiff_t;

        const_iterator_base() = default;
        const_iterator_base(const const_iterator_base& r) = default;
        const_iterator_base& operator=(const const_iterator_base& r) = default;

        value_type* operator++();
        value_type* operator--();

        bool operator==(const const_iterator_base& r) const;
        bool operator!=(const const_iterator_base& r) const;

        value_type& operator*()
        {
            return cur_value();
        }

        const value_type* operator->()
        {
            return &cur_value();
        }

    protected:
        void move_to_front();
        void move_to_end();

    private:
        value_type& cur_value()
        {
            auto pos = *m_cur_pos_in_chain;
            return (*m_segment_store)[pos];
        }

        size_type cur_pos() const
        {
            return *m_cur_pos_in_chain;
        }

        const segment_store_type* m_segment_store = nullptr;
        res_chains_ptr mp_res_chains;
        typename res_chains_type::const_iterator m_cur_chain;
        typename value_chain_type::const_iterator m_cur_pos_in_chain;
        bool m_end_pos = true;
    };

    class search_result_inserter
    {
    public:
        search_result_inserter(search_results_base& results) : m_results(results)
        {}
        void operator()(value_chain_type* node_data)
        {
            if (!node_data)
                return;

            m_results.push_back_chain(node_data);
        }

    private:
        search_results_base& m_results;
    };

public:
    class search_results : public search_results_base
    {
        friend class segment_tree;

        typedef typename search_results_base::res_chains_type res_chains_type;
        typedef typename search_results_base::res_chains_ptr res_chains_ptr;

        search_results(const segment_store_type& segment_tree) : search_results_base(segment_tree)
        {}

    public:
        class const_iterator : public const_iterator_base
        {
            friend class segment_tree<KeyT, ValueT>::search_results;

        private:
            const_iterator(const segment_store_type* segment_store, const res_chains_ptr& p)
                : const_iterator_base(segment_store, p)
            {}

        public:
            const_iterator() : const_iterator_base()
            {}

            const_iterator(const const_iterator& r) : const_iterator_base(r)
            {}

            const_iterator& operator=(const const_iterator& r)
            {
                const_iterator_base::operator=(r);
                return *this;
            }
        };

        bool empty() const
        {
            return search_results_base::empty();
        }

        size_type size() const
        {
            return search_results_base::size();
        }

        typename search_results::const_iterator begin() const
        {
            typename search_results::const_iterator it(
                search_results_base::get_segment_store(), search_results_base::get_res_chains());
            it.move_to_front();
            return it;
        }

        typename search_results::const_iterator end() const
        {
            typename search_results::const_iterator it(
                search_results_base::get_segment_store(), search_results_base::get_res_chains());
            it.move_to_end();
            return it;
        }
    };

    segment_tree();
    segment_tree(const segment_tree& r);
    segment_tree(segment_tree&& r);
    ~segment_tree();

    segment_tree& operator=(const segment_tree& r);
    segment_tree& operator=(segment_tree&& r);

    bool operator==(const segment_tree& r) const;

    bool operator!=(const segment_tree& r) const;

    bool valid_tree() const noexcept
    {
        return m_valid_tree;
    }

    void build_tree();

    void insert(key_type start_key, key_type end_key, value_type value);

    search_results search(const key_type& point) const;

    void erase(const typename search_results::const_iterator& pos);

    template<typename Pred>
    size_type erase_if(Pred pred);

    void swap(segment_tree& r) noexcept;

    void clear();

    size_type size() const;

    bool empty() const;

    size_type leaf_size() const;

    std::string to_string() const;

    std::vector<key_type> boundary_keys() const;

    struct integrity_check_properties
    {
        struct leaf_node
        {
            key_type key = {};
            std::vector<value_type> value_chain;
        };

        std::vector<leaf_node> leaf_nodes;
    };

    void check_integrity(const integrity_check_properties& props) const;

private:
    static void create_leaf_node_instances(std::vector<key_type> keys, node_ptr& left, node_ptr& right);

    void descend_tree_and_mark(
        st::detail::node_base* pnode, value_pos_type value, const key_type& start_key, const key_type& end_key,
        node_chain_type& nodelist);

    void build_leaf_nodes();

    void remove_data_from_nodes(node_chain_type& nodelist, value_pos_type value);
    void remove_data_from_chain(value_chain_type& chain, value_pos_type value);
    void remove_value_pos(size_type pos);

    void clear_all_nodes();

private:
    struct tree_dumper_traits
    {
        using leaf_type = node;
        using nonleaf_type = nonleaf_node;
        using tree_type = segment_tree;

        struct to_string
        {
            const tree_type& tree;

            to_string(const tree_type& _tree);
            std::string operator()(const leaf_type& leaf) const;
            std::string operator()(const nonleaf_type& nonleaf) const;
        };
    };

    std::vector<nonleaf_node> m_nonleaf_node_pool;

    segment_store_type m_segment_store;

    value_to_nodes_type m_tagged_nodes_map;

    nonleaf_node* m_root_node;
    node_ptr m_left_leaf;
    node_ptr m_right_leaf;
    bool m_valid_tree;
};

} // namespace mdds

#include "segment_tree_def.inl"

#endif