Loading...
Searching...
No Matches
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;
}
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: */
mdds::flat_segment_tree::const_iterator
Definition flat_segment_tree.hpp:87
mdds::flat_segment_tree::const_iterator::to_segment
const_segment_iterator to_segment() const
mdds::flat_segment_tree::const_reverse_iterator
Definition flat_segment_tree.hpp:117
mdds::flat_segment_tree::const_segment_range_type
Definition flat_segment_tree.hpp:133
mdds::flat_segment_tree
Definition flat_segment_tree.hpp:28
mdds::flat_segment_tree::flat_segment_tree
flat_segment_tree(flat_segment_tree &&other) noexcept(nothrow_move_constructible_v)
mdds::flat_segment_tree::clear
void clear()
mdds::flat_segment_tree::segment_range
const_segment_range_type segment_range() const
mdds::flat_segment_tree::operator=
flat_segment_tree< Key, Value > & operator=(const flat_segment_tree &other)
mdds::flat_segment_tree::shift_left
void shift_left(key_type start_key, key_type end_key)
mdds::flat_segment_tree::flat_segment_tree
flat_segment_tree(const flat_segment_tree &r)
mdds::flat_segment_tree::swap
void swap(flat_segment_tree &other) noexcept(nothrow_swappable_v)
mdds::flat_segment_tree::shift_right
void shift_right(key_type pos, key_type size, bool skip_start_node)
mdds::flat_segment_tree::end_segment
const_segment_iterator end_segment() const
mdds::flat_segment_tree::search
const_iterator search(const_iterator pos, key_type key) const
mdds::flat_segment_tree::rbegin
const_reverse_iterator rbegin() const
Definition flat_segment_tree.hpp:177
mdds::flat_segment_tree::insert_front
std::pair< const_iterator, bool > insert_front(key_type start_key, key_type end_key, value_type val)
Definition flat_segment_tree.hpp:300
mdds::flat_segment_tree::operator=
flat_segment_tree< Key, Value > & operator=(flat_segment_tree &&other) noexcept(nothrow_move_assignable_v)
mdds::flat_segment_tree::build_tree
void build_tree()
mdds::flat_segment_tree::begin
const_iterator begin() const
Definition flat_segment_tree.hpp:151
mdds::flat_segment_tree::search
std::pair< const_iterator, bool > search(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
mdds::flat_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 flat_segment_tree.hpp:516
mdds::flat_segment_tree::valid_tree
bool valid_tree() const noexcept
Definition flat_segment_tree.hpp:479
mdds::flat_segment_tree::search_tree
std::pair< const_iterator, bool > search_tree(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
mdds::flat_segment_tree::insert_back
std::pair< const_iterator, bool > insert_back(key_type start_key, key_type end_key, value_type val)
Definition flat_segment_tree.hpp:320
mdds::flat_segment_tree::begin_segment
const_segment_iterator begin_segment() const
mdds::flat_segment_tree::search
const_iterator search(key_type key) const
mdds::flat_segment_tree::operator==
bool operator==(const flat_segment_tree &other) const noexcept(nothrow_eq_comparable_v)
mdds::flat_segment_tree::end
const_iterator end() const
Definition flat_segment_tree.hpp:164
mdds::flat_segment_tree::flat_segment_tree
flat_segment_tree(key_type min_val, key_type max_val, value_type init_val)
mdds::flat_segment_tree::insert
std::pair< const_iterator, bool > insert(const_iterator pos, key_type start_key, key_type end_key, value_type val)
mdds::flat_segment_tree::search_tree
const_iterator search_tree(key_type key) const
mdds::flat_segment_tree::rend
const_reverse_iterator rend() const
Definition flat_segment_tree.hpp:191
mdds::flat_segment_tree::search
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
mdds::fst::detail::const_iterator_base
Definition flat_segment_tree_itr.hpp:74
mdds::fst::detail::const_segment_iterator
Definition flat_segment_tree_itr.hpp:171
mdds::flat_segment_tree::nonleaf_value_type
Definition flat_segment_tree.hpp:35
mdds::fst::detail::forward_itr_handler
Definition flat_segment_tree_itr.hpp:17
mdds::fst::detail::reverse_itr_handler
Definition flat_segment_tree_itr.hpp:47
mdds::st::detail::node
Definition node.hpp:106
mdds::st::detail::nonleaf_node
Definition node.hpp:40