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>
52 typedef _Key key_type;
53 typedef _Value value_type;
54 typedef size_t size_type;
63 return low == r.low && high == r.
high;
80 return key == r.key && value == r.value;
95 struct to_string_handler;
99 typedef typename node::node_ptr node_ptr;
110 _self.value_nonleaf.low =
112 static_cast<const node*
>(left_node)->value_leaf.key :
113 static_cast<const nonleaf_node*>(left_node)->value_nonleaf.low;
118 throw general_error(
"flat_segment_tree::fill_nonleaf_value_handler: Having a left node is prerequisite.");
128 const node* p =
static_cast<const node*
>(right_node);
130 _self.value_nonleaf.high = p->
next->value_leaf.key;
132 _self.value_nonleaf.high = p->value_leaf.key;
136 _self.value_nonleaf.high =
static_cast<const nonleaf_node*
>(right_node)->value_nonleaf.high;
141 _self.value_nonleaf.high =
143 static_cast<const node*
>(left_node)->value_leaf.key :
144 static_cast<const nonleaf_node*>(left_node)->value_nonleaf.high;
149 #ifdef MDDS_UNIT_TEST
150 struct to_string_handler
152 std::string operator() (
const node& _self)
const
154 std::ostringstream os;
155 os <<
"(" << _self.value_leaf.key <<
") ";
161 std::ostringstream os;
162 os <<
"(" << _self.value_nonleaf.low <<
"-" << _self.value_nonleaf.high <<
") ";
170 void operator() (node& ) {}
176 void operator() (node& ) {}
182 friend struct ::mdds::__fst::itr_forward_handler<flat_segment_tree>;
183 friend struct ::mdds::__fst::itr_reverse_handler<flat_segment_tree>;
187 flat_segment_tree, ::mdds::__fst::itr_forward_handler<flat_segment_tree> >
189 typedef ::mdds::__fst::const_iterator_base<
192 friend class flat_segment_tree;
195 base_type(
nullptr,
false) {}
199 base_type(_db, _end) {}
206 flat_segment_tree, ::mdds::__fst::itr_reverse_handler<flat_segment_tree> >
208 typedef ::mdds::__fst::const_iterator_base<
211 friend class flat_segment_tree;
214 base_type(
nullptr,
false) {}
217 base_type(_db, _end) {}
225 const_iterator end()
const
227 return const_iterator(
this,
true);
230 const_reverse_iterator rbegin()
const
232 return const_reverse_iterator(
this,
false);
235 const_reverse_iterator rend()
const
237 return const_reverse_iterator(
this,
true);
240 flat_segment_tree(key_type min_val, key_type max_val, value_type init_val);
245 flat_segment_tree(
const flat_segment_tree<key_type, value_type>& r);
247 ~flat_segment_tree();
252 flat_segment_tree<key_type, value_type>&
253 operator=(
const flat_segment_tree<key_type, value_type>& other);
255 void swap(flat_segment_tree<key_type, value_type>& other);
273 std::pair<const_iterator, bool>
276 return insert_segment_impl(start_key, end_key, val,
true);
294 std::pair<const_iterator, bool>
297 return insert_segment_impl(start_key, end_key, val,
false);
315 std::pair<const_iterator, bool>
316 insert(
const const_iterator& pos, key_type start_key, key_type end_key, value_type val);
327 void shift_left(key_type start_key, key_type end_key);
341 void shift_right(key_type pos, key_type size,
bool skip_start_node);
360 std::pair<const_iterator, bool>
361 search(key_type key, value_type& value, key_type* start_key =
nullptr, key_type* end_key =
nullptr)
const;
381 std::pair<const_iterator, bool>
382 search(
const const_iterator& pos, key_type key, value_type& value, key_type* start_key =
nullptr, key_type* end_key =
nullptr)
const;
403 std::pair<const_iterator, bool>
404 search_tree(key_type key, value_type& value, key_type* start_key =
nullptr, key_type* end_key =
nullptr)
const;
434 key_type min_key()
const
436 return m_left_leaf->value_leaf.key;
439 key_type max_key()
const
441 return m_right_leaf->value_leaf.key;
444 value_type default_value()
const
456 #ifdef MDDS_UNIT_TEST
457 nonleaf_node* get_root_node()
const
462 void dump_tree()
const
468 assert(!
"attempted to dump an invalid tree!");
470 size_t node_count = mdds::__st::tree_dumper<node, nonleaf_node>::dump(m_root_node);
471 size_t node_instance_count = node::get_instance_count();
474 cout <<
"tree node count = " << node_count <<
"; node instance count = "
475 << node_instance_count <<
"; leaf node count = " << leaf_count << endl;
477 assert(leaf_count == node_instance_count);
480 void dump_leaf_nodes()
const
485 cout <<
"------------------------------------------" << endl;
487 node_ptr cur_node = m_left_leaf;
491 cout <<
" node " << node_id++ <<
": key = " << cur_node->value_leaf.key
492 <<
"; value = " << cur_node->value_leaf.value
494 cur_node = cur_node->next;
496 cout << endl <<
" node instance count = " << node::get_instance_count() << endl;
506 bool verify_keys(const ::std::vector<key_type>& key_values)
const
510 node* cur_node = m_left_leaf.get();
511 typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
512 for (; itr != itr_end; ++itr)
518 if (cur_node->value_leaf.key != *itr)
522 cur_node = cur_node->next.get();
533 node* cur_node = m_right_leaf.get();
534 typename ::std::vector<key_type>::const_reverse_iterator itr = key_values.rbegin(), itr_end = key_values.rend();
535 for (; itr != itr_end; ++itr)
541 if (cur_node->value_leaf.key != *itr)
545 cur_node = cur_node->prev.get();
564 bool verify_values(const ::std::vector<value_type>& values)
const
566 node* cur_node = m_left_leaf.get();
567 node* end_node = m_right_leaf.get();
568 typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
569 for (; itr != itr_end; ++itr)
571 if (cur_node == end_node || !cur_node)
574 if (cur_node->value_leaf.value != *itr)
578 cur_node = cur_node->next.get();
581 if (cur_node != end_node)
593 void append_new_segment(key_type start_key)
595 if (m_right_leaf->prev->value_leaf.key == start_key)
597 m_right_leaf->prev->value_leaf.value = m_init_val;
601 #ifdef MDDS_UNIT_TEST
604 assert(m_right_leaf->prev->value_leaf.key < start_key);
607 if (m_right_leaf->prev->value_leaf.value == m_init_val)
612 node_ptr new_node(
new node);
613 new_node->value_leaf.key = start_key;
614 new_node->value_leaf.value = m_init_val;
615 new_node->prev = m_right_leaf->prev;
616 new_node->next = m_right_leaf;
617 m_right_leaf->prev->next = new_node;
618 m_right_leaf->prev = new_node;
619 m_valid_tree =
false;
622 ::std::pair<const_iterator, bool>
623 insert_segment_impl(key_type start_key, key_type end_key, value_type val,
bool forward);
625 ::std::pair<const_iterator, bool>
626 insert_to_pos(node_ptr& start_pos, key_type start_key, key_type end_key, value_type val);
628 ::std::pair<const_iterator, bool>
629 search_impl(
const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key)
const;
631 const node* get_insertion_pos_leaf_reverse(key_type key,
const node* start_pos)
const;
633 const node* get_insertion_pos_leaf(key_type key,
const node* start_pos)
const;
635 static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
637 node* cur_node_p = begin_node.get();
638 node* end_node_p = end_node.get();
639 while (cur_node_p != end_node_p)
641 cur_node_p->value_leaf.key -= shift_value;
642 cur_node_p = cur_node_p->next.get();
646 static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
648 key_type end_node_key = end_node->value_leaf.key;
649 while (cur_node.get() != end_node.get())
651 cur_node->value_leaf.key += shift_value;
652 if (cur_node->value_leaf.key < end_node_key)
655 cur_node = cur_node->next;
663 node_ptr last_node = cur_node->prev;
664 while (cur_node.get() != end_node.get())
666 node_ptr next_node = cur_node->next;
667 disconnect_all_nodes(cur_node.get());
668 cur_node = next_node;
670 last_node->next = end_node;
671 end_node->prev = last_node;
685 bool adjust_segment_range(key_type& start_key, key_type& end_key)
const;
688 std::vector<nonleaf_node> m_nonleaf_node_pool;
690 nonleaf_node* m_root_node;
691 node_ptr m_left_leaf;
692 node_ptr m_right_leaf;
693 value_type m_init_val;
697 template<
typename _Key,
typename _Value>
699 swap(flat_segment_tree<_Key, _Value>& left, flat_segment_tree<_Key, _Value>& right)
706 #include "flat_segment_tree_def.inl"
std::pair< const_iterator, bool > insert_front(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:274
void shift_left(key_type start_key, key_type end_key)
Definition: flat_segment_tree.hpp:205
bool is_leaf
parent nonleaf_node
Definition: node.hpp:46
bool operator==(const flat_segment_tree< key_type, value_type > &r) const
std::pair< const_iterator, bool > insert(const const_iterator &pos, key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree_itr.hpp:37
Definition: flat_segment_tree.hpp:73
std::pair< const_iterator, bool > search(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
Definition: global.hpp:58
std::pair< const_iterator, bool > insert_back(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:295
Definition: flat_segment_tree.hpp:49
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: default_deleter.hpp:33
bool is_tree_valid() const
Definition: flat_segment_tree.hpp:417
key_type high
low range value (inclusive)
Definition: flat_segment_tree.hpp:59
Definition: flat_segment_tree.hpp:56
flat_segment_tree< key_type, value_type > & operator=(const flat_segment_tree< key_type, value_type > &other)
Definition: flat_segment_tree_itr.hpp:67
size_type leaf_size() const
Definition: flat_segment_tree_itr.hpp:94
void shift_right(key_type pos, key_type size, bool skip_start_node)
Definition: flat_segment_tree.hpp:186
bool operator==(const nonleaf_value_type &r) const
high range value (non-inclusive)
Definition: flat_segment_tree.hpp:61
Definition: flat_segment_tree.hpp:103
Definition: flat_segment_tree.hpp:174
node_ptr next
previous sibling leaf node.
Definition: node.hpp:166
Definition: flat_segment_tree.hpp:168