52 typedef Value value_type;
53 typedef size_t size_type;
65 return value == r.value;
70 return !operator==(r);
78 using node_ptr =
typename node::node_ptr;
82 friend struct ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>;
83 friend struct ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>;
89 flat_segment_tree, ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>>
96 using base_type::get_parent;
97 using base_type::get_pos;
98 using base_type::is_end_pos;
114 explicit const_iterator(
const typename base_type::fst_type* _db,
const node* p) : base_type(_db, p)
119 flat_segment_tree, ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>>
137 node_ptr m_left_leaf;
138 node_ptr m_right_leaf;
303 std::pair<const_iterator, bool>
insert_front(key_type start_key, key_type end_key, value_type val)
305 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val),
true);
323 std::pair<const_iterator, bool>
insert_back(key_type start_key, key_type end_key, value_type val)
325 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val),
false);
343 std::pair<const_iterator, bool>
insert(
const_iterator pos, key_type start_key, key_type end_key, value_type val);
368 void shift_right(key_type pos, key_type size,
bool skip_start_node);
388 key_type key, value_type& value, key_type* start_key =
nullptr, key_type* end_key =
nullptr)
const;
409 const_iterator pos, key_type key, value_type& value, key_type* start_key =
nullptr,
410 key_type* end_key =
nullptr)
const;
457 key_type key, value_type& value, key_type* start_key =
nullptr, key_type* end_key =
nullptr)
const;
499 key_type min_key()
const
501 return m_left_leaf->key;
504 key_type max_key()
const
506 return m_right_leaf->key;
509 value_type default_value()
const
527 struct tree_dumper_traits
529 using leaf_type = node;
530 using nonleaf_type = nonleaf_node;
535 to_string(
const tree_type&)
538 std::string operator()(
const leaf_type& leaf)
const
540 return leaf.to_string();
543 std::string operator()(
const nonleaf_type& nonleaf)
const
545 return nonleaf.to_string();
550 void dump_tree()
const
556 assert(!
"attempted to dump an invalid tree!");
559 size_t node_instance_count = node::get_instance_count();
562 cout <<
"tree node count = " << node_count <<
"; node instance count = " << node_instance_count
563 <<
"; leaf node count = " << leaf_count << endl;
565 assert(leaf_count == node_instance_count);
568 void dump_leaf_nodes()
const
573 cout <<
"------------------------------------------" << endl;
575 node_ptr cur_node = m_left_leaf;
579 cout <<
" node " << node_id++ <<
": key = " << cur_node->key <<
"; value = " << cur_node->value_leaf.value
581 cur_node = cur_node->next;
583 cout << endl <<
" node instance count = " << node::get_instance_count() << endl;
593 bool verify_keys(const ::std::vector<key_type>& key_values)
const
597 node* cur_node = m_left_leaf.get();
598 typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
599 for (; itr != itr_end; ++itr)
605 if (cur_node->key != *itr)
609 cur_node = cur_node->next.get();
620 node* cur_node = m_right_leaf.get();
621 typename ::std::vector<key_type>::const_reverse_iterator itr = key_values.rbegin(),
622 itr_end = key_values.rend();
623 for (; itr != itr_end; ++itr)
629 if (cur_node->key != *itr)
633 cur_node = cur_node->prev.get();
652 bool verify_values(const ::std::vector<value_type>& values)
const
654 node* cur_node = m_left_leaf.get();
655 node* end_node = m_right_leaf.get();
656 typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
657 for (; itr != itr_end; ++itr)
659 if (cur_node == end_node || !cur_node)
662 if (cur_node->value_leaf.value != *itr)
666 cur_node = cur_node->next.get();
669 if (cur_node != end_node)
679 const_iterator search_by_key_impl(
const node* start_pos, key_type key)
const;
681 const node* search_tree_for_leaf_node(key_type key)
const;
683 void append_new_segment(key_type start_key)
685 if (m_right_leaf->prev->key == start_key)
687 m_right_leaf->prev->value_leaf.value = m_init_val;
694 assert(m_right_leaf->prev->key < start_key);
697 if (m_right_leaf->prev->value_leaf.value == m_init_val)
702 node_ptr new_node(
new node);
703 new_node->key = start_key;
704 new_node->value_leaf.value = m_init_val;
705 new_node->prev = m_right_leaf->prev;
706 new_node->next = m_right_leaf;
707 m_right_leaf->prev->next = new_node;
708 m_right_leaf->prev = std::move(new_node);
709 m_valid_tree =
false;
712 ::std::pair<const_iterator, bool> insert_segment_impl(
713 key_type start_key, key_type end_key, value_type val,
bool forward);
715 ::std::pair<const_iterator, bool> insert_to_pos(
716 node_ptr start_pos, key_type start_key, key_type end_key, value_type val);
718 ::std::pair<const_iterator, bool> search_impl(
719 const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key)
const;
721 const node* get_insertion_pos_leaf_reverse(
const key_type& key,
const node* start_pos)
const;
733 const node* get_insertion_pos_leaf(
const key_type& key,
const node* start_pos)
const;
735 static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
737 node* cur_node_p = begin_node.get();
738 node* end_node_p = end_node.get();
739 while (cur_node_p != end_node_p)
741 cur_node_p->key -= shift_value;
742 cur_node_p = cur_node_p->next.get();
746 static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
748 key_type end_node_key = end_node->key;
749 while (cur_node.get() != end_node.get())
751 cur_node->key += shift_value;
752 if (cur_node->key < end_node_key)
755 cur_node = cur_node->next;
763 node_ptr last_node = cur_node->prev;
764 while (cur_node.get() != end_node.get())
766 node_ptr next_node = cur_node->next;
767 disconnect_all_nodes(cur_node.get());
768 cur_node = std::move(next_node);
770 last_node->next = end_node;
771 end_node->prev = std::move(last_node);
785 bool adjust_segment_range(key_type& start_key, key_type& end_key)
const;
788 std::vector<nonleaf_node> m_nonleaf_node_pool;
790 const nonleaf_node* m_root_node;
791 node_ptr m_left_leaf;
792 node_ptr m_right_leaf;
793 value_type m_init_val;