mdds
flat_segment_tree.hpp
1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2/*************************************************************************
3 *
4 * Copyright (c) 2008-2017 Kohei Yoshida
5 *
6 * Permission is hereby granted, free of charge, to any person
7 * obtaining a copy of this software and associated documentation
8 * files (the "Software"), to deal in the Software without
9 * restriction, including without limitation the rights to use,
10 * copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following
13 * conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 * OTHER DEALINGS IN THE SOFTWARE.
26 *
27 ************************************************************************/
28
29#ifndef INCLUDED_MDDS_FLAT_SEGMENT_TREE_HPP
30#define INCLUDED_MDDS_FLAT_SEGMENT_TREE_HPP
31
32#include <iostream>
33#include <sstream>
34#include <utility>
35#include <cassert>
36
37#include "mdds/node.hpp"
38#include "mdds/flat_segment_tree_itr.hpp"
39#include "mdds/global.hpp"
40
41#ifdef MDDS_UNIT_TEST
42#include <cstdio>
43#include <vector>
44#endif
45
46namespace mdds {
47
48template<typename Key, typename Value>
50{
51public:
52 typedef Key key_type;
53 typedef Value value_type;
54 typedef size_t size_type;
55
57 {
58 key_type low;
59 key_type high;
60
61 bool operator==(const nonleaf_value_type& r) const
62 {
63 return low == r.low && high == r.high;
64 }
65
66 nonleaf_value_type() : low(0), high(0)
67 {}
68 };
69
71 {
72 key_type key;
73 value_type value;
74
75 bool operator==(const leaf_value_type& r) const
76 {
77 return key == r.key && value == r.value;
78 }
79
80 leaf_value_type() : key(0), value()
81 {}
82 };
83
84 // Handlers required by the node template class.
86 struct init_handler;
87 struct dispose_handler;
88#ifdef MDDS_UNIT_TEST
89 struct to_string_handler;
90#endif
91
93 typedef typename node::node_ptr node_ptr;
94
96
98 {
99 void operator()(
101 const __st::node_base* right_node)
102 {
103 // Parent node should carry the range of all of its child nodes.
104 if (left_node)
105 {
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;
109 }
110 else
111 {
112 // Having a left node is prerequisite.
113 throw general_error(
114 "flat_segment_tree::fill_nonleaf_value_handler: Having a left node is prerequisite.");
115 }
116
117 if (right_node)
118 {
119 if (right_node->is_leaf)
120 {
121 // When the child nodes are leaf nodes, the upper bound
122 // must be the value of the node that comes after the
123 // right leaf node (if such node exists).
124 const node* p = static_cast<const node*>(right_node);
125 if (p->next)
126 _self.value_nonleaf.high = p->next->value_leaf.key;
127 else
128 _self.value_nonleaf.high = p->value_leaf.key;
129 }
130 else
131 {
132 _self.value_nonleaf.high = static_cast<const nonleaf_node*>(right_node)->value_nonleaf.high;
133 }
134 }
135 else
136 {
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;
140 }
141 }
142 };
143
144#ifdef MDDS_UNIT_TEST
145 struct to_string_handler
146 {
147 std::string operator()(const node& _self) const
148 {
149 std::ostringstream os;
150 os << "(" << _self.value_leaf.key << ") ";
151 return os.str();
152 }
153
154 std::string operator()(const mdds::__st::nonleaf_node<flat_segment_tree>& _self) const
155 {
156 std::ostringstream os;
157 os << "(" << _self.value_nonleaf.low << "-" << _self.value_nonleaf.high << ") ";
158 return os.str();
159 }
160 };
161#endif
162
164 {
165 void operator()(node& /*_self*/)
166 {}
167 void operator()(__st::nonleaf_node<flat_segment_tree>& /*_self*/)
168 {}
169 };
170
172 {
173 void operator()(node& /*_self*/)
174 {}
175 void operator()(__st::nonleaf_node<flat_segment_tree>& /*_self*/)
176 {}
177 };
178
179private:
180 friend struct ::mdds::__fst::itr_forward_handler<flat_segment_tree>;
181 friend struct ::mdds::__fst::itr_reverse_handler<flat_segment_tree>;
182
183public:
185 flat_segment_tree, ::mdds::__fst::itr_forward_handler<flat_segment_tree>>
186 {
189 base_type;
190 friend class flat_segment_tree;
191
192 public:
193 const_iterator() : base_type(nullptr, false)
194 {}
195
196 private:
197 explicit const_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
198 {}
199
200 explicit const_iterator(const typename base_type::fst_type* _db, const node* p) : base_type(_db, p)
201 {}
202 };
203
205 flat_segment_tree, ::mdds::__fst::itr_reverse_handler<flat_segment_tree>>
206 {
209 base_type;
210 friend class flat_segment_tree;
211
212 public:
213 const_reverse_iterator() : base_type(nullptr, false)
214 {}
215
216 private:
217 explicit const_reverse_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
218 {}
219 };
220
222
231 {
232 return const_iterator(this, false);
233 }
234
244 {
245 return const_iterator(this, true);
246 }
247
257 {
258 return const_reverse_iterator(this, false);
259 }
260
271 {
272 return const_reverse_iterator(this, true);
273 }
274
286
299
311 flat_segment_tree(key_type min_val, key_type max_val, value_type init_val);
312
317
319
324
331
337 void clear();
338
353 std::pair<const_iterator, bool> insert_front(key_type start_key, key_type end_key, value_type val)
354 {
355 return insert_segment_impl(start_key, end_key, val, true);
356 }
357
373 std::pair<const_iterator, bool> insert_back(key_type start_key, key_type end_key, value_type val)
374 {
375 return insert_segment_impl(start_key, end_key, val, false);
376 }
377
393 std::pair<const_iterator, bool> insert(
394 const const_iterator& pos, key_type start_key, key_type end_key, value_type val);
395
405 void shift_left(key_type start_key, key_type end_key);
406
419 void shift_right(key_type pos, key_type size, bool skip_start_node);
420
438 std::pair<const_iterator, bool> search(
439 key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
440
459 std::pair<const_iterator, bool> search(
460 const const_iterator& pos, key_type key, value_type& value, key_type* start_key = nullptr,
461 key_type* end_key = nullptr) const;
462
482 std::pair<const_iterator, bool> search_tree(
483 key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
484
491
496 bool is_tree_valid() const
497 {
498 return m_valid_tree;
499 }
500
507
508 bool operator!=(const flat_segment_tree<key_type, value_type>& r) const
509 {
510 return !operator==(r);
511 }
512
513 key_type min_key() const
514 {
515 return m_left_leaf->value_leaf.key;
516 }
517
518 key_type max_key() const
519 {
520 return m_right_leaf->value_leaf.key;
521 }
522
523 value_type default_value() const
524 {
525 return m_init_val;
526 }
527
533 size_type leaf_size() const;
534
535#ifdef MDDS_UNIT_TEST
536 nonleaf_node* get_root_node() const
537 {
538 return m_root_node;
539 }
540
541 void dump_tree() const
542 {
543 using ::std::cout;
544 using ::std::endl;
545
546 if (!m_valid_tree)
547 assert(!"attempted to dump an invalid tree!");
548
549 size_t node_count = mdds::__st::tree_dumper<node, nonleaf_node>::dump(m_root_node);
550 size_t node_instance_count = node::get_instance_count();
551 size_t leaf_count = leaf_size();
552
553 cout << "tree node count = " << node_count << "; node instance count = " << node_instance_count
554 << "; leaf node count = " << leaf_count << endl;
555
556 assert(leaf_count == node_instance_count);
557 }
558
559 void dump_leaf_nodes() const
560 {
561 using ::std::cout;
562 using ::std::endl;
563
564 cout << "------------------------------------------" << endl;
565
566 node_ptr cur_node = m_left_leaf;
567 long node_id = 0;
568 while (cur_node)
569 {
570 cout << " node " << node_id++ << ": key = " << cur_node->value_leaf.key
571 << "; value = " << cur_node->value_leaf.value << endl;
572 cur_node = cur_node->next;
573 }
574 cout << endl << " node instance count = " << node::get_instance_count() << endl;
575 }
576
584 bool verify_keys(const ::std::vector<key_type>& key_values) const
585 {
586 {
587 // Start from the left-most node, and traverse right.
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)
591 {
592 if (!cur_node)
593 // Position past the right-mode node. Invalid.
594 return false;
595
596 if (cur_node->value_leaf.key != *itr)
597 // Key values differ.
598 return false;
599
600 cur_node = cur_node->next.get();
601 }
602
603 if (cur_node)
604 // At this point, we expect the current node to be at the position
605 // past the right-most node, which is nullptr.
606 return false;
607 }
608
609 {
610 // Start from the right-most node, and traverse left.
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)
615 {
616 if (!cur_node)
617 // Position past the left-mode node. Invalid.
618 return false;
619
620 if (cur_node->value_leaf.key != *itr)
621 // Key values differ.
622 return false;
623
624 cur_node = cur_node->prev.get();
625 }
626
627 if (cur_node)
628 // Likewise, we expect the current position to be past the
629 // left-most node, in which case the node value is nullptr.
630 return false;
631 }
632
633 return true;
634 }
635
643 bool verify_values(const ::std::vector<value_type>& values) const
644 {
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)
649 {
650 if (cur_node == end_node || !cur_node)
651 return false;
652
653 if (cur_node->value_leaf.value != *itr)
654 // Key values differ.
655 return false;
656
657 cur_node = cur_node->next.get();
658 }
659
660 if (cur_node != end_node)
661 // At this point, we expect the current node to be at the end of
662 // range.
663 return false;
664
665 return true;
666 }
667#endif
668
669private:
670 flat_segment_tree(); // default constructor is not allowed.
671
672 void append_new_segment(key_type start_key)
673 {
674 if (m_right_leaf->prev->value_leaf.key == start_key)
675 {
676 m_right_leaf->prev->value_leaf.value = m_init_val;
677 return;
678 }
679
680#ifdef MDDS_UNIT_TEST
681 // The start position must come after the position of the last node
682 // before the right-most node.
683 assert(m_right_leaf->prev->value_leaf.key < start_key);
684#endif
685
686 if (m_right_leaf->prev->value_leaf.value == m_init_val)
687 // The existing segment has the same value. No need to insert a
688 // new segment.
689 return;
690
691 node_ptr new_node(new node);
692 new_node->value_leaf.key = start_key;
693 new_node->value_leaf.value = m_init_val;
694 new_node->prev = m_right_leaf->prev;
695 new_node->next = m_right_leaf;
696 m_right_leaf->prev->next = new_node;
697 m_right_leaf->prev = new_node;
698 m_valid_tree = false;
699 }
700
701 ::std::pair<const_iterator, bool> insert_segment_impl(
702 key_type start_key, key_type end_key, value_type val, bool forward);
703
704 ::std::pair<const_iterator, bool> insert_to_pos(
705 node_ptr& start_pos, key_type start_key, key_type end_key, value_type val);
706
707 ::std::pair<const_iterator, bool> search_impl(
708 const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key) const;
709
710 const node* get_insertion_pos_leaf_reverse(key_type key, const node* start_pos) const;
711
712 const node* get_insertion_pos_leaf(key_type key, const node* start_pos) const;
713
714 static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
715 {
716 node* cur_node_p = begin_node.get();
717 node* end_node_p = end_node.get();
718 while (cur_node_p != end_node_p)
719 {
720 cur_node_p->value_leaf.key -= shift_value;
721 cur_node_p = cur_node_p->next.get();
722 }
723 }
724
725 static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
726 {
727 key_type end_node_key = end_node->value_leaf.key;
728 while (cur_node.get() != end_node.get())
729 {
730 cur_node->value_leaf.key += shift_value;
731 if (cur_node->value_leaf.key < end_node_key)
732 {
733 // The node is still in-bound. Keep shifting.
734 cur_node = cur_node->next;
735 continue;
736 }
737
738 // This node has been pushed outside the end node position.
739 // Remove all nodes that follows, and connect the previous node
740 // with the end node.
741
742 node_ptr last_node = cur_node->prev;
743 while (cur_node.get() != end_node.get())
744 {
745 node_ptr next_node = cur_node->next;
746 disconnect_all_nodes(cur_node.get());
747 cur_node = next_node;
748 }
749 last_node->next = end_node;
750 end_node->prev = last_node;
751 return;
752 }
753 }
754
755 void destroy();
756
764 bool adjust_segment_range(key_type& start_key, key_type& end_key) const;
765
766private:
767 std::vector<nonleaf_node> m_nonleaf_node_pool;
768
769 nonleaf_node* m_root_node;
770 node_ptr m_left_leaf;
771 node_ptr m_right_leaf;
772 value_type m_init_val;
773 bool m_valid_tree;
774};
775
776template<typename Key, typename Value>
777void swap(flat_segment_tree<Key, Value>& left, flat_segment_tree<Key, Value>& right)
778{
779 left.swap(right);
780}
781
782} // namespace mdds
783
784#include "flat_segment_tree_def.inl"
785
786#endif
787
788/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition: flat_segment_tree_itr.hpp:95
Definition: flat_segment_tree_itr.hpp:193
Definition: flat_segment_tree.hpp:186
Definition: flat_segment_tree.hpp:206
Definition: flat_segment_tree.hpp:50
flat_segment_tree(const flat_segment_tree< key_type, value_type > &r)
size_type leaf_size() const
void swap(flat_segment_tree< key_type, value_type > &other)
void shift_left(key_type start_key, key_type end_key)
void shift_right(key_type pos, key_type size, bool skip_start_node)
const_segment_iterator end_segment() const
const_reverse_iterator rbegin() const
Definition: flat_segment_tree.hpp:256
std::pair< const_iterator, bool > insert_front(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:353
const_iterator begin() const
Definition: flat_segment_tree.hpp:230
bool is_tree_valid() const
Definition: flat_segment_tree.hpp:496
std::pair< const_iterator, bool > search(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
flat_segment_tree< key_type, value_type > & operator=(const flat_segment_tree< key_type, value_type > &other)
bool operator==(const flat_segment_tree< key_type, value_type > &r) 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
std::pair< const_iterator, bool > insert(const const_iterator &pos, key_type start_key, key_type end_key, value_type val)
std::pair< const_iterator, bool > search(const const_iterator &pos, key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
std::pair< const_iterator, bool > insert_back(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:373
const_segment_iterator begin_segment() const
const_iterator end() const
Definition: flat_segment_tree.hpp:243
flat_segment_tree(key_type min_val, key_type max_val, value_type init_val)
const_reverse_iterator rend() const
Definition: flat_segment_tree.hpp:270
Definition: global.hpp:84
Definition: flat_segment_tree_itr.hpp:38
Definition: flat_segment_tree_itr.hpp:68
Definition: node.hpp:44
bool is_leaf
parent nonleaf_node
Definition: node.hpp:46
Definition: node.hpp:140
node_ptr next
previous sibling leaf node.
Definition: node.hpp:162
Definition: node.hpp:56
Definition: flat_segment_tree.hpp:172
Definition: flat_segment_tree.hpp:98
Definition: flat_segment_tree.hpp:164
Definition: flat_segment_tree.hpp:71
Definition: flat_segment_tree.hpp:57
key_type high
low range value (inclusive)
Definition: flat_segment_tree.hpp:59
bool operator==(const nonleaf_value_type &r) const
high range value (non-inclusive)
Definition: flat_segment_tree.hpp:61