Loading...
Searching...
No Matches
segment_tree.hpp
// SPDX-FileCopyrightText: 2010 - 2025 Kohei Yoshida
//
// SPDX-License-Identifier: MIT
#pragma once
#include "./node.hpp"
#include "./global.hpp"
#include <vector>
#include <deque>
#include <iostream>
#include <map>
#include <unordered_map>
#include <memory>
#include <sstream>
#include <type_traits>
#include <utility>
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;
static constexpr bool is_nothrow_less_v = noexcept(std::declval<key_type>() < std::declval<key_type>()) &&
noexcept(std::declval<value_type>() < std::declval<value_type>());
static constexpr bool is_nothrow_equal_v = noexcept(std::declval<key_type>() == std::declval<key_type>()) &&
noexcept(std::declval<value_type>() == std::declval<value_type>());
segment_type() = default;
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 noexcept(is_nothrow_less_v && is_nothrow_equal_v);
bool operator==(const segment_type& r) const noexcept(is_nothrow_equal_v);
bool operator!=(const segment_type& r) const noexcept(is_nothrow_equal_v);
};
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;
};
static constexpr bool nothrow_default_constructible_v =
std::is_nothrow_default_constructible_v<std::vector<nonleaf_node>> &&
std::is_nothrow_default_constructible_v<segment_store_type> &&
std::is_nothrow_default_constructible_v<value_to_nodes_type> &&
std::is_nothrow_default_constructible_v<node_ptr>;
static constexpr bool nothrow_move_constructible_v =
std::is_nothrow_move_constructible_v<std::vector<nonleaf_node>> &&
std::is_nothrow_move_constructible_v<segment_store_type> &&
std::is_nothrow_move_constructible_v<value_to_nodes_type> && std::is_nothrow_move_constructible_v<node_ptr>;
static constexpr bool nothrow_swappable_v =
std::is_nothrow_swappable_v<std::vector<nonleaf_node>> && std::is_nothrow_swappable_v<segment_store_type> &&
std::is_nothrow_swappable_v<value_to_nodes_type> && std::is_nothrow_swappable_v<node_ptr>;
static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;
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() noexcept(nothrow_default_constructible_v);
segment_tree(const segment_tree& r);
segment_tree(segment_tree&& r) = default;
~segment_tree();
segment_tree& operator=(const segment_tree& r);
segment_tree& operator=(segment_tree&& r) noexcept(nothrow_move_assignable_v);
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(nothrow_swappable_v);
void clear();
size_type size() const;
bool empty() const;
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());
}
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"
mdds::point
mdds::segment_tree::search_results::const_iterator
Definition segment_tree.hpp:283
mdds::segment_tree::search_results
Definition segment_tree.hpp:272
mdds::segment_tree::search_results::size
size_type size() const
Definition segment_tree.hpp:320
mdds::segment_tree::search_results::empty
bool empty() const
Definition segment_tree.hpp:310
mdds::segment_tree::empty
bool empty() const
mdds::segment_tree::key_type
KeyT key_type
Definition segment_tree.hpp:46
mdds::segment_tree::build_tree
void build_tree()
mdds::segment_tree::value_type
ValueT value_type
Definition segment_tree.hpp:48
mdds::segment_tree::insert
void insert(key_type start_key, key_type end_key, value_type value)
mdds::segment_tree::erase
void erase(const typename search_results::const_iterator &pos)
mdds::segment_tree::clear
void clear()
mdds::segment_tree::leaf_size
size_type leaf_size() const noexcept(noexcept(st::detail::count_leaf_nodes< size_type >(m_left_leaf.get(), m_right_leaf.get())))
Definition segment_tree.hpp:468
mdds::segment_tree::size
size_type size() const
mdds::segment_tree::operator==
bool operator==(const segment_tree &r) const
mdds::segment_tree::boundary_keys
std::vector< key_type > boundary_keys() const
mdds::segment_tree::to_string
std::string to_string() const
mdds::segment_tree::search
search_results search(const key_type &point) const
mdds::segment_tree::swap
void swap(segment_tree &r) noexcept(nothrow_swappable_v)
mdds::segment_tree::valid_tree
bool valid_tree() const noexcept
Definition segment_tree.hpp:367
mdds::segment_tree::erase_if
size_type erase_if(Pred pred)
mdds::segment_tree::integrity_check_properties::leaf_node
Definition segment_tree.hpp:492
mdds::segment_tree::integrity_check_properties
Definition segment_tree.hpp:490
mdds::st::detail::node_base
Definition node.hpp:25