27class flat_segment_tree
31 typedef Value value_type;
32 typedef size_t size_type;
42 struct leaf_value_type
46 bool operator==(
const leaf_value_type& r)
const
47 noexcept(
noexcept(std::declval<value_type>() == std::declval<value_type>()))
49 return value == r.value;
52 leaf_value_type() : value{}
57 using node_ptr =
typename node::node_ptr;
61 friend struct ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>;
62 friend struct ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>;
64 static constexpr bool nothrow_move_constructible_v =
65 std::is_nothrow_move_constructible_v<std::vector<nonleaf_node>> &&
66 std::is_nothrow_move_constructible_v<value_type>;
68 static constexpr bool nothrow_swappable_v =
69 std::is_nothrow_swappable_v<value_type> && std::is_nothrow_swappable_v<std::vector<nonleaf_node>>;
71 static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;
73 static constexpr bool nothrow_eq_comparable_v =
74 noexcept(std::declval<key_type>() == std::declval<key_type>()) &&
75 noexcept(std::declval<leaf_value_type>() == std::declval<leaf_value_type>());
81 flat_segment_tree, ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>>
86 friend class flat_segment_tree;
88 using base_type::get_parent;
89 using base_type::get_pos;
90 using base_type::is_end_pos;
93 const_iterator() : base_type(
nullptr,
false)
103 explicit const_iterator(
const typename base_type::fst_type* _db,
bool _end) : base_type(_db, _end)
106 explicit const_iterator(
const typename base_type::fst_type* _db,
const node* p) : base_type(_db, p)
111 flat_segment_tree, ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>>
116 friend class flat_segment_tree;
119 const_reverse_iterator() : base_type(
nullptr,
false)
123 explicit const_reverse_iterator(
const typename base_type::fst_type* _db,
bool _end) : base_type(_db, _end)
127 class const_segment_range_type
129 node_ptr m_left_leaf;
130 node_ptr m_right_leaf;
133 const_segment_range_type(node_ptr left_leaf, node_ptr right_leaf);
135 const_segment_iterator
begin()
const;
136 const_segment_iterator
end()
const;
221 flat_segment_tree() =
delete;
249 ~flat_segment_tree();
258 flat_segment_tree<Key, Value>&
operator=(
const flat_segment_tree& other);
265 flat_segment_tree<Key, Value>&
operator=(flat_segment_tree&& other)
noexcept(nothrow_move_assignable_v);
272 void swap(flat_segment_tree& other)
noexcept(nothrow_swappable_v);
295 std::pair<const_iterator, bool>
insert_front(key_type start_key, key_type end_key, value_type val)
297 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val),
true);
315 std::pair<const_iterator, bool>
insert_back(key_type start_key, key_type end_key, value_type val)
317 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val),
false);
335 std::pair<const_iterator, bool>
insert(
const_iterator pos, key_type start_key, key_type end_key, value_type val);
360 void shift_right(key_type pos, key_type size,
bool skip_start_node);
380 key_type key, value_type& value, key_type* start_key =
nullptr, key_type* end_key =
nullptr)
const;
401 const_iterator pos, key_type key, value_type& value, key_type* start_key =
nullptr,
402 key_type* end_key =
nullptr)
const;
449 key_type key, value_type& value, key_type* start_key =
nullptr, key_type* end_key =
nullptr)
const;
484 bool operator==(
const flat_segment_tree& other)
const noexcept(nothrow_eq_comparable_v);
486 const key_type& min_key() const noexcept
488 return m_left_leaf->key;
491 const key_type& max_key() const noexcept
493 return m_right_leaf->key;
496 const value_type& default_value() const noexcept
507 noexcept(noexcept(st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get())))
509 return st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get());
513 const nonleaf_node* get_root_node()
const
518 struct tree_dumper_traits
520 using leaf_type = node;
521 using nonleaf_type = nonleaf_node;
522 using tree_type = flat_segment_tree;
526 to_string(
const tree_type&)
529 std::string operator()(
const leaf_type& leaf)
const
531 return leaf.to_string();
534 std::string operator()(
const nonleaf_type& nonleaf)
const
536 return nonleaf.to_string();
541 void dump_tree()
const
547 assert(!
"attempted to dump an invalid tree!");
549 size_t node_count = mdds::st::detail::tree_dumper<tree_dumper_traits>::dump(std::cout, *
this, m_root_node);
550 size_t node_instance_count = node::get_instance_count();
553 cout <<
"tree node count = " << node_count <<
"; node instance count = " << node_instance_count
554 <<
"; leaf node count = " << leaf_count << endl;
556 assert(leaf_count == node_instance_count);
559 void dump_leaf_nodes()
const
564 cout <<
"------------------------------------------" << endl;
566 node_ptr cur_node = m_left_leaf;
570 cout <<
" node " << node_id++ <<
": key = " << cur_node->key <<
"; value = " << cur_node->value_leaf.value
572 cur_node = cur_node->next;
574 cout << endl <<
" node instance count = " << node::get_instance_count() << endl;
584 bool verify_keys(const ::std::vector<key_type>& key_values)
const
588 node* cur_node = m_left_leaf.get();
589 typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
590 for (; itr != itr_end; ++itr)
596 if (cur_node->key != *itr)
600 cur_node = cur_node->next.get();
611 node* cur_node = m_right_leaf.get();
612 typename ::std::vector<key_type>::const_reverse_iterator itr = key_values.rbegin(),
613 itr_end = key_values.rend();
614 for (; itr != itr_end; ++itr)
620 if (cur_node->key != *itr)
624 cur_node = cur_node->prev.get();
643 bool verify_values(const ::std::vector<value_type>& values)
const
645 node* cur_node = m_left_leaf.get();
646 node* end_node = m_right_leaf.get();
647 typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
648 for (; itr != itr_end; ++itr)
650 if (cur_node == end_node || !cur_node)
653 if (cur_node->value_leaf.value != *itr)
657 cur_node = cur_node->next.get();
660 if (cur_node != end_node)
670 const_iterator search_by_key_impl(
const node* start_pos, key_type key)
const;
672 const node* search_tree_for_leaf_node(key_type key)
const;
674 void append_new_segment(key_type start_key)
676 if (m_right_leaf->prev->key == start_key)
678 m_right_leaf->prev->value_leaf.value = m_init_val;
685 assert(m_right_leaf->prev->key < start_key);
688 if (m_right_leaf->prev->value_leaf.value == m_init_val)
693 node_ptr new_node(
new node);
694 new_node->key = start_key;
695 new_node->value_leaf.value = m_init_val;
696 new_node->prev = m_right_leaf->prev;
697 new_node->next = m_right_leaf;
698 m_right_leaf->prev->next = new_node;
699 m_right_leaf->prev = std::move(new_node);
700 m_valid_tree =
false;
703 ::std::pair<const_iterator, bool> insert_segment_impl(
704 key_type start_key, key_type end_key, value_type val,
bool forward);
706 ::std::pair<const_iterator, bool> insert_to_pos(
707 node_ptr start_pos, key_type start_key, key_type end_key, value_type val);
709 ::std::pair<const_iterator, bool> search_impl(
710 const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key)
const;
712 const node* get_insertion_pos_leaf_reverse(
const key_type& key,
const node* start_pos)
const;
724 const node* get_insertion_pos_leaf(
const key_type& key,
const node* start_pos)
const;
726 static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
728 node* cur_node_p = begin_node.get();
729 node* end_node_p = end_node.get();
730 while (cur_node_p != end_node_p)
732 cur_node_p->key -= shift_value;
733 cur_node_p = cur_node_p->next.get();
737 static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
739 key_type end_node_key = end_node->key;
740 while (cur_node.get() != end_node.get())
742 cur_node->key += shift_value;
743 if (cur_node->key < end_node_key)
746 cur_node = cur_node->next;
754 node_ptr last_node = cur_node->prev;
755 while (cur_node.get() != end_node.get())
757 node_ptr next_node = cur_node->next;
758 disconnect_all_nodes(cur_node.get());
759 cur_node = std::move(next_node);
761 last_node->next = end_node;
762 end_node->prev = std::move(last_node);
776 bool adjust_segment_range(key_type& start_key, key_type& end_key)
const;
779 std::vector<nonleaf_node> m_nonleaf_node_pool;
781 const nonleaf_node* m_root_node;
782 node_ptr m_left_leaf;
783 node_ptr m_right_leaf;
784 value_type m_init_val;