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-2023 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{}, high{}
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{}, 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::detail::forward_itr_handler<flat_segment_tree>;
181 friend struct ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>;
182
183public:
185
187 flat_segment_tree, ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>>
188 {
191 base_type;
192 friend class flat_segment_tree;
193
194 using base_type::get_parent;
195 using base_type::get_pos;
196 using base_type::is_end_pos;
197
198 public:
199 const_iterator() : base_type(nullptr, false)
200 {}
201
207
208 private:
209 explicit const_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
210 {}
211
212 explicit const_iterator(const typename base_type::fst_type* _db, const node* p) : base_type(_db, p)
213 {}
214 };
215
217 flat_segment_tree, ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>>
218 {
221 base_type;
222 friend class flat_segment_tree;
223
224 public:
225 const_reverse_iterator() : base_type(nullptr, false)
226 {}
227
228 private:
229 explicit const_reverse_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
230 {}
231 };
232
234 {
235 node_ptr m_left_leaf;
236 node_ptr m_right_leaf;
237
238 public:
239 const_segment_range_type(node_ptr left_leaf, node_ptr right_leaf);
240
241 const_segment_iterator begin() const;
242 const_segment_iterator end() const;
243 };
244
253 {
254 return const_iterator(this, false);
255 }
256
266 {
267 return const_iterator(this, true);
268 }
269
279 {
280 return const_reverse_iterator(this, false);
281 }
282
293 {
294 return const_reverse_iterator(this, true);
295 }
296
308
321
326
327 flat_segment_tree() = delete;
328
340 flat_segment_tree(key_type min_val, key_type max_val, value_type init_val);
341
346
354
356
365
372
379
385 void clear();
386
401 std::pair<const_iterator, bool> insert_front(key_type start_key, key_type end_key, value_type val)
402 {
403 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val), true);
404 }
405
421 std::pair<const_iterator, bool> insert_back(key_type start_key, key_type end_key, value_type val)
422 {
423 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val), false);
424 }
425
441 std::pair<const_iterator, bool> insert(
442 const const_iterator& pos, key_type start_key, key_type end_key, value_type val);
443
453 void shift_left(key_type start_key, key_type end_key);
454
467 void shift_right(key_type pos, key_type size, bool skip_start_node);
468
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;
488
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;
510
520 const_iterator search(key_type key) const;
521
534 const_iterator search(const const_iterator& pos, key_type key) const;
535
555 std::pair<const_iterator, bool> search_tree(
556 key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
557
568 const_iterator search_tree(key_type key) const;
569
576
581 bool is_tree_valid() const
582 {
583 return m_valid_tree;
584 }
585
591 bool operator==(const flat_segment_tree& other) const;
592
593 bool operator!=(const flat_segment_tree& other) const
594 {
595 return !operator==(other);
596 }
597
598 key_type min_key() const
599 {
600 return m_left_leaf->value_leaf.key;
601 }
602
603 key_type max_key() const
604 {
605 return m_right_leaf->value_leaf.key;
606 }
607
608 value_type default_value() const
609 {
610 return m_init_val;
611 }
612
618 size_type leaf_size() const;
619
620#ifdef MDDS_UNIT_TEST
621 const nonleaf_node* get_root_node() const
622 {
623 return m_root_node;
624 }
625
626 void dump_tree() const
627 {
628 using ::std::cout;
629 using ::std::endl;
630
631 if (!m_valid_tree)
632 assert(!"attempted to dump an invalid tree!");
633
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();
636 size_t leaf_count = leaf_size();
637
638 cout << "tree node count = " << node_count << "; node instance count = " << node_instance_count
639 << "; leaf node count = " << leaf_count << endl;
640
641 assert(leaf_count == node_instance_count);
642 }
643
644 void dump_leaf_nodes() const
645 {
646 using ::std::cout;
647 using ::std::endl;
648
649 cout << "------------------------------------------" << endl;
650
651 node_ptr cur_node = m_left_leaf;
652 long node_id = 0;
653 while (cur_node)
654 {
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;
658 }
659 cout << endl << " node instance count = " << node::get_instance_count() << endl;
660 }
661
669 bool verify_keys(const ::std::vector<key_type>& key_values) const
670 {
671 {
672 // Start from the left-most node, and traverse right.
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)
676 {
677 if (!cur_node)
678 // Position past the right-mode node. Invalid.
679 return false;
680
681 if (cur_node->value_leaf.key != *itr)
682 // Key values differ.
683 return false;
684
685 cur_node = cur_node->next.get();
686 }
687
688 if (cur_node)
689 // At this point, we expect the current node to be at the position
690 // past the right-most node, which is nullptr.
691 return false;
692 }
693
694 {
695 // Start from the right-most node, and traverse left.
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)
700 {
701 if (!cur_node)
702 // Position past the left-mode node. Invalid.
703 return false;
704
705 if (cur_node->value_leaf.key != *itr)
706 // Key values differ.
707 return false;
708
709 cur_node = cur_node->prev.get();
710 }
711
712 if (cur_node)
713 // Likewise, we expect the current position to be past the
714 // left-most node, in which case the node value is nullptr.
715 return false;
716 }
717
718 return true;
719 }
720
728 bool verify_values(const ::std::vector<value_type>& values) const
729 {
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)
734 {
735 if (cur_node == end_node || !cur_node)
736 return false;
737
738 if (cur_node->value_leaf.value != *itr)
739 // Key values differ.
740 return false;
741
742 cur_node = cur_node->next.get();
743 }
744
745 if (cur_node != end_node)
746 // At this point, we expect the current node to be at the end of
747 // range.
748 return false;
749
750 return true;
751 }
752#endif
753
754private:
755 const_iterator search_by_key_impl(const node* start_pos, key_type key) const;
756
757 const node* search_tree_for_leaf_node(key_type key) const;
758
759 void append_new_segment(key_type start_key)
760 {
761 if (m_right_leaf->prev->value_leaf.key == start_key)
762 {
763 m_right_leaf->prev->value_leaf.value = m_init_val;
764 return;
765 }
766
767#ifdef MDDS_UNIT_TEST
768 // The start position must come after the position of the last node
769 // before the right-most node.
770 assert(m_right_leaf->prev->value_leaf.key < start_key);
771#endif
772
773 if (m_right_leaf->prev->value_leaf.value == m_init_val)
774 // The existing segment has the same value. No need to insert a
775 // new segment.
776 return;
777
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;
786 }
787
788 ::std::pair<const_iterator, bool> insert_segment_impl(
789 key_type start_key, key_type end_key, value_type val, bool forward);
790
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);
793
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;
796
797 const node* get_insertion_pos_leaf_reverse(const key_type& key, const node* start_pos) const;
798
809 const node* get_insertion_pos_leaf(const key_type& key, const node* start_pos) const;
810
811 static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
812 {
813 node* cur_node_p = begin_node.get();
814 node* end_node_p = end_node.get();
815 while (cur_node_p != end_node_p)
816 {
817 cur_node_p->value_leaf.key -= shift_value;
818 cur_node_p = cur_node_p->next.get();
819 }
820 }
821
822 static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
823 {
824 key_type end_node_key = end_node->value_leaf.key;
825 while (cur_node.get() != end_node.get())
826 {
827 cur_node->value_leaf.key += shift_value;
828 if (cur_node->value_leaf.key < end_node_key)
829 {
830 // The node is still in-bound. Keep shifting.
831 cur_node = cur_node->next;
832 continue;
833 }
834
835 // This node has been pushed outside the end node position.
836 // Remove all nodes that follows, and connect the previous node
837 // with the end node.
838
839 node_ptr last_node = cur_node->prev;
840 while (cur_node.get() != end_node.get())
841 {
842 node_ptr next_node = cur_node->next;
843 disconnect_all_nodes(cur_node.get());
844 cur_node = next_node;
845 }
846 last_node->next = end_node;
847 end_node->prev = last_node;
848 return;
849 }
850 }
851
852 void destroy();
853
861 bool adjust_segment_range(key_type& start_key, key_type& end_key) const;
862
863private:
864 std::vector<nonleaf_node> m_nonleaf_node_pool;
865
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;
870 bool m_valid_tree;
871};
872
873template<typename Key, typename Value>
874void swap(flat_segment_tree<Key, Value>& left, flat_segment_tree<Key, Value>& right)
875{
876 left.swap(right);
877}
878
879} // namespace mdds
880
881#include "flat_segment_tree_def.inl"
882
883#endif
884
885/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition: flat_segment_tree.hpp:188
const_segment_iterator to_segment() const
Definition: flat_segment_tree.hpp:218
Definition: flat_segment_tree.hpp:234
Definition: flat_segment_tree.hpp:50
size_type leaf_size() const
const_segment_range_type segment_range() const
flat_segment_tree< Key, Value > & operator=(const flat_segment_tree &other)
void shift_left(key_type start_key, key_type end_key)
flat_segment_tree(const flat_segment_tree &r)
flat_segment_tree(flat_segment_tree &&other)
flat_segment_tree< Key, Value > & operator=(flat_segment_tree &&other)
void shift_right(key_type pos, key_type size, bool skip_start_node)
const_segment_iterator end_segment() const
bool operator==(const flat_segment_tree &other) const
const_reverse_iterator rbegin() const
Definition: flat_segment_tree.hpp:278
const_iterator search(const const_iterator &pos, key_type key) const
std::pair< const_iterator, bool > insert_front(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:401
const_iterator begin() const
Definition: flat_segment_tree.hpp:252
bool is_tree_valid() const
Definition: flat_segment_tree.hpp:581
std::pair< const_iterator, bool > search(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) 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:421
const_segment_iterator begin_segment() const
const_iterator search(key_type key) const
void swap(flat_segment_tree &other)
const_iterator end() const
Definition: flat_segment_tree.hpp:265
flat_segment_tree(key_type min_val, key_type max_val, value_type init_val)
const_iterator search_tree(key_type key) const
const_reverse_iterator rend() const
Definition: flat_segment_tree.hpp:292
Definition: flat_segment_tree_itr.hpp:95
Definition: flat_segment_tree_itr.hpp:199
Definition: global.hpp:84
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
Definition: flat_segment_tree_itr.hpp:38
Definition: flat_segment_tree_itr.hpp:68