29 #ifndef INCLUDED_MDDS_FLAT_SEGMENT_TREE_HPP
30 #define INCLUDED_MDDS_FLAT_SEGMENT_TREE_HPP
37 #include "mdds/node.hpp"
38 #include "mdds/flat_segment_tree_itr.hpp"
39 #include "mdds/global.hpp"
48 template<
typename Key,
typename Value>
53 typedef Value value_type;
54 typedef size_t size_type;
63 return low == r.low && high == r.
high;
77 return key == r.key && value == r.value;
89 struct to_string_handler;
93 typedef typename node::node_ptr node_ptr;
106 _self.value_nonleaf.low = left_node->
is_leaf
107 ?
static_cast<const node*
>(left_node)->value_leaf.key
108 : static_cast<const nonleaf_node*>(left_node)->value_nonleaf.low;
114 "flat_segment_tree::fill_nonleaf_value_handler: Having a left node is prerequisite.");
124 const node* p =
static_cast<const node*
>(right_node);
126 _self.value_nonleaf.high = p->
next->value_leaf.key;
128 _self.value_nonleaf.high = p->value_leaf.key;
132 _self.value_nonleaf.high =
static_cast<const nonleaf_node*
>(right_node)->value_nonleaf.high;
137 _self.value_nonleaf.high = left_node->
is_leaf
138 ?
static_cast<const node*
>(left_node)->value_leaf.key
139 : static_cast<const nonleaf_node*>(left_node)->value_nonleaf.high;
144 #ifdef MDDS_UNIT_TEST
145 struct to_string_handler
147 std::string operator()(
const node& _self)
const
149 std::ostringstream os;
150 os <<
"(" << _self.value_leaf.key <<
") ";
156 std::ostringstream os;
157 os <<
"(" << _self.value_nonleaf.low <<
"-" << _self.value_nonleaf.high <<
") ";
165 void operator()(node& )
173 void operator()(node& )
180 friend struct ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>;
181 friend struct ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>;
187 flat_segment_tree, ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>>
189 typedef ::mdds::fst::detail::const_iterator_base<
192 friend class flat_segment_tree;
194 using base_type::get_parent;
195 using base_type::get_pos;
196 using base_type::is_end_pos;
217 flat_segment_tree, ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>>
219 typedef ::mdds::fst::detail::const_iterator_base<
222 friend class flat_segment_tree;
235 node_ptr m_left_leaf;
236 node_ptr m_right_leaf;
401 std::pair<const_iterator, bool>
insert_front(key_type start_key, key_type end_key, value_type val)
403 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val),
true);
421 std::pair<const_iterator, bool>
insert_back(key_type start_key, key_type end_key, value_type val)
423 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val),
false);
441 std::pair<const_iterator, bool>
insert(
442 const const_iterator& pos, key_type start_key, key_type end_key, value_type val);
453 void shift_left(key_type start_key, key_type end_key);
467 void shift_right(key_type pos, key_type size,
bool skip_start_node);
486 std::pair<const_iterator, bool>
search(
487 key_type key, value_type& value, key_type* start_key =
nullptr, key_type* end_key =
nullptr)
const;
507 std::pair<const_iterator, bool>
search(
508 const const_iterator& pos, key_type key, value_type& value, key_type* start_key =
nullptr,
509 key_type* end_key =
nullptr)
const;
520 const_iterator
search(key_type key)
const;
534 const_iterator
search(
const const_iterator& pos, key_type key)
const;
556 key_type key, value_type& value, key_type* start_key =
nullptr, key_type* end_key =
nullptr)
const;
598 key_type min_key()
const
600 return m_left_leaf->value_leaf.key;
603 key_type max_key()
const
605 return m_right_leaf->value_leaf.key;
608 value_type default_value()
const
620 #ifdef MDDS_UNIT_TEST
621 const nonleaf_node* get_root_node()
const
626 void dump_tree()
const
632 assert(!
"attempted to dump an invalid tree!");
634 size_t node_count = mdds::__st::tree_dumper<node, nonleaf_node>::dump(m_root_node);
635 size_t node_instance_count = node::get_instance_count();
638 cout <<
"tree node count = " << node_count <<
"; node instance count = " << node_instance_count
639 <<
"; leaf node count = " << leaf_count << endl;
641 assert(leaf_count == node_instance_count);
644 void dump_leaf_nodes()
const
649 cout <<
"------------------------------------------" << endl;
651 node_ptr cur_node = m_left_leaf;
655 cout <<
" node " << node_id++ <<
": key = " << cur_node->value_leaf.key
656 <<
"; value = " << cur_node->value_leaf.value << endl;
657 cur_node = cur_node->next;
659 cout << endl <<
" node instance count = " << node::get_instance_count() << endl;
669 bool verify_keys(const ::std::vector<key_type>& key_values)
const
673 node* cur_node = m_left_leaf.get();
674 typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
675 for (; itr != itr_end; ++itr)
681 if (cur_node->value_leaf.key != *itr)
685 cur_node = cur_node->next.get();
696 node* cur_node = m_right_leaf.get();
697 typename ::std::vector<key_type>::const_reverse_iterator itr = key_values.rbegin(),
698 itr_end = key_values.rend();
699 for (; itr != itr_end; ++itr)
705 if (cur_node->value_leaf.key != *itr)
709 cur_node = cur_node->prev.get();
728 bool verify_values(const ::std::vector<value_type>& values)
const
730 node* cur_node = m_left_leaf.get();
731 node* end_node = m_right_leaf.get();
732 typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
733 for (; itr != itr_end; ++itr)
735 if (cur_node == end_node || !cur_node)
738 if (cur_node->value_leaf.value != *itr)
742 cur_node = cur_node->next.get();
745 if (cur_node != end_node)
755 const_iterator search_by_key_impl(
const node* start_pos, key_type key)
const;
757 const node* search_tree_for_leaf_node(key_type key)
const;
759 void append_new_segment(key_type start_key)
761 if (m_right_leaf->prev->value_leaf.key == start_key)
763 m_right_leaf->prev->value_leaf.value = m_init_val;
767 #ifdef MDDS_UNIT_TEST
770 assert(m_right_leaf->prev->value_leaf.key < start_key);
773 if (m_right_leaf->prev->value_leaf.value == m_init_val)
778 node_ptr new_node(
new node);
779 new_node->value_leaf.key = start_key;
780 new_node->value_leaf.value = m_init_val;
781 new_node->prev = m_right_leaf->prev;
782 new_node->next = m_right_leaf;
783 m_right_leaf->prev->next = new_node;
784 m_right_leaf->prev = new_node;
785 m_valid_tree =
false;
788 ::std::pair<const_iterator, bool> insert_segment_impl(
789 key_type start_key, key_type end_key, value_type val,
bool forward);
791 ::std::pair<const_iterator, bool> insert_to_pos(
792 node_ptr start_pos, key_type start_key, key_type end_key, value_type val);
794 ::std::pair<const_iterator, bool> search_impl(
795 const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key)
const;
797 const node* get_insertion_pos_leaf_reverse(
const key_type& key,
const node* start_pos)
const;
809 const node* get_insertion_pos_leaf(
const key_type& key,
const node* start_pos)
const;
811 static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
813 node* cur_node_p = begin_node.get();
814 node* end_node_p = end_node.get();
815 while (cur_node_p != end_node_p)
817 cur_node_p->value_leaf.key -= shift_value;
818 cur_node_p = cur_node_p->next.get();
822 static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
824 key_type end_node_key = end_node->value_leaf.key;
825 while (cur_node.get() != end_node.get())
827 cur_node->value_leaf.key += shift_value;
828 if (cur_node->value_leaf.key < end_node_key)
831 cur_node = cur_node->next;
839 node_ptr last_node = cur_node->prev;
840 while (cur_node.get() != end_node.get())
842 node_ptr next_node = cur_node->next;
843 disconnect_all_nodes(cur_node.get());
844 cur_node = next_node;
846 last_node->next = end_node;
847 end_node->prev = last_node;
861 bool adjust_segment_range(key_type& start_key, key_type& end_key)
const;
864 std::vector<nonleaf_node> m_nonleaf_node_pool;
866 const nonleaf_node* m_root_node;
867 node_ptr m_left_leaf;
868 node_ptr m_right_leaf;
869 value_type m_init_val;
873 template<
typename Key,
typename Value>
874 void swap(flat_segment_tree<Key, Value>& left, flat_segment_tree<Key, Value>& right)
881 #include "flat_segment_tree_def.inl"
Definition: flat_segment_tree.hpp:233
Definition: flat_segment_tree_itr.hpp:67
Definition: flat_segment_tree.hpp:216
key_type high
low range value (inclusive)
Definition: flat_segment_tree.hpp:59
bool is_leaf
parent nonleaf_node
Definition: node.hpp:46
bool is_tree_valid() const
Definition: flat_segment_tree.hpp:581
const_reverse_iterator rbegin() const
Definition: flat_segment_tree.hpp:278
size_type leaf_size() const
const_segment_range_type segment_range() const
Definition: flat_segment_tree.hpp:70
const_segment_iterator end_segment() const
std::pair< const_iterator, bool > insert(const const_iterator &pos, key_type start_key, key_type end_key, value_type val)
bool operator==(const flat_segment_tree &other) const
const_reverse_iterator rend() const
Definition: flat_segment_tree.hpp:292
const_iterator end() const
Definition: flat_segment_tree.hpp:265
std::pair< const_iterator, bool > insert_front(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:401
std::pair< const_iterator, bool > search_tree(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
Definition: flat_segment_tree_itr.hpp:94
Definition: flat_segment_tree_itr.hpp:37
const_segment_iterator begin_segment() const
Definition: global.hpp:83
Definition: flat_segment_tree_itr.hpp:198
void shift_right(key_type pos, key_type size, bool skip_start_node)
bool operator==(const nonleaf_value_type &r) const
high range value (non-inclusive)
Definition: flat_segment_tree.hpp:61
Definition: flat_segment_tree.hpp:49
Definition: flat_segment_tree.hpp:46
Definition: flat_segment_tree.hpp:56
flat_segment_tree< Key, Value > & operator=(const flat_segment_tree &other)
std::pair< const_iterator, bool > insert_back(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:421
std::pair< const_iterator, bool > search(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
void shift_left(key_type start_key, key_type end_key)
Definition: flat_segment_tree.hpp:186
void swap(flat_segment_tree &other)
Definition: flat_segment_tree.hpp:97
const_segment_iterator to_segment() const
Definition: flat_segment_tree.hpp:171
node_ptr next
previous sibling leaf node.
Definition: node.hpp:162
const_iterator begin() const
Definition: flat_segment_tree.hpp:252
Definition: flat_segment_tree.hpp:163