mdds
Loading...
Searching...
No Matches
segment_tree.hpp
1/*************************************************************************
2 *
3 * Copyright (c) 2010-2015 Kohei Yoshida
4 *
5 * Permission is hereby granted, free of charge, to any person
6 * obtaining a copy of this software and associated documentation
7 * files (the "Software"), to deal in the Software without
8 * restriction, including without limitation the rights to use,
9 * copy, modify, merge, publish, distribute, sublicense, and/or sell
10 * copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following
12 * conditions:
13 *
14 * The above copyright notice and this permission notice shall be
15 * included in all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24 * OTHER DEALINGS IN THE SOFTWARE.
25 *
26 ************************************************************************/
27
28#ifndef INCLUDED_MDDS_SEGMENTTREE_HPP
29#define INCLUDED_MDDS_SEGMENTTREE_HPP
30
31#include "mdds/node.hpp"
32#include "mdds/global.hpp"
33
34#include <vector>
35#include <deque>
36#include <iostream>
37#include <map>
38#include <unordered_map>
39#include <memory>
40#include <sstream>
41
42namespace mdds {
43
63template<typename KeyT, typename ValueT>
65{
66public:
68 using key_type = KeyT;
70 using value_type = ValueT;
71 using size_type = std::size_t;
72
73private:
74 struct segment_type
75 {
76 key_type start;
77 key_type end;
78 value_type value;
79
80 segment_type();
81 segment_type(key_type _start, key_type _end, value_type _value);
82 segment_type(const segment_type&) = default;
83 segment_type(segment_type&&) = default;
84
85 segment_type& operator=(const segment_type& r) = default;
86 segment_type& operator=(segment_type&& r) = default;
87 bool operator<(const segment_type& r) const;
88 bool operator==(const segment_type& r) const;
89 bool operator!=(const segment_type& r) const;
90 };
91
92 using segment_store_type = std::deque<segment_type>;
93 using value_pos_type = typename segment_store_type::size_type;
94 using value_chain_type = std::vector<value_pos_type>;
95
96 using node_chain_type = std::vector<st::detail::node_base*>;
97 using value_to_nodes_type = std::map<value_pos_type, node_chain_type>;
98
99 struct nonleaf_value_type
100 {
101 std::unique_ptr<value_chain_type> data_chain;
102
103 nonleaf_value_type()
104 {}
105 nonleaf_value_type(const nonleaf_value_type& r)
106 {
107 if (r.data_chain)
108 data_chain = std::make_unique<value_chain_type>(*r.data_chain);
109 }
110
111 bool operator==(const nonleaf_value_type& r) const
112 {
113 return data_chain == r.data_chain;
114 }
115
116 ~nonleaf_value_type()
117 {}
118 };
119
120 struct leaf_value_type
121 {
122 std::unique_ptr<value_chain_type> data_chain;
123
124 leaf_value_type()
125 {}
126 leaf_value_type(const leaf_value_type& r)
127 {
128 if (r.data_chain)
129 data_chain = std::make_unique<value_chain_type>(*r.data_chain);
130 }
131
132 bool operator==(const leaf_value_type& r) const
133 {
134 return data_chain == r.data_chain;
135 }
136
137 ~leaf_value_type()
138 {}
139 };
140
141public:
142 using node = st::detail::node<key_type, leaf_value_type>;
143 using node_ptr = typename node::node_ptr;
144 using nonleaf_node = typename st::detail::nonleaf_node<key_type, nonleaf_value_type>;
145
146private:
147 class search_result_inserter;
148
153 class search_results_base
154 {
155 friend class search_result_inserter;
156
157 public:
158 typedef std::vector<value_chain_type*> res_chains_type;
159 typedef std::shared_ptr<res_chains_type> res_chains_ptr;
160
161 protected:
162 search_results_base(const segment_store_type& segment_store) : m_segment_store(&segment_store)
163 {}
164
165 search_results_base(const search_results_base& r)
166 : m_segment_store(r.m_segment_store), mp_res_chains(r.mp_res_chains)
167 {}
168
169 bool empty() const;
170
171 size_type size() const;
172
173 void push_back_chain(value_chain_type* chain);
174
175 const segment_store_type* get_segment_store() const
176 {
177 return m_segment_store;
178 }
179
180 const res_chains_ptr& get_res_chains() const
181 {
182 return mp_res_chains;
183 }
184
185 private:
186 const segment_store_type* m_segment_store = nullptr;
187 res_chains_ptr mp_res_chains;
188 };
189
190 class const_iterator_base
191 {
192 friend class segment_tree;
193
194 protected:
195 typedef typename search_results_base::res_chains_type res_chains_type;
196 typedef typename search_results_base::res_chains_ptr res_chains_ptr;
197
198 const_iterator_base(const segment_store_type* segment_store, const res_chains_ptr& p)
199 : m_segment_store(segment_store), mp_res_chains(p), m_end_pos(true)
200 {}
201
202 public:
203 using iterator_category = std::bidirectional_iterator_tag;
204 using value_type = const segment_tree::segment_type;
205 using pointer = value_type*;
206 using reference = value_type&;
207 using difference_type = std::ptrdiff_t;
208
209 const_iterator_base() = default;
210 const_iterator_base(const const_iterator_base& r) = default;
211 const_iterator_base& operator=(const const_iterator_base& r) = default;
212
213 value_type* operator++();
214 value_type* operator--();
215
216 bool operator==(const const_iterator_base& r) const;
217 bool operator!=(const const_iterator_base& r) const;
218
219 value_type& operator*()
220 {
221 return cur_value();
222 }
223
224 const value_type* operator->()
225 {
226 return &cur_value();
227 }
228
229 protected:
230 void move_to_front();
231 void move_to_end();
232
233 private:
234 value_type& cur_value()
235 {
236 auto pos = *m_cur_pos_in_chain;
237 return (*m_segment_store)[pos];
238 }
239
240 size_type cur_pos() const
241 {
242 return *m_cur_pos_in_chain;
243 }
244
245 const segment_store_type* m_segment_store = nullptr;
246 res_chains_ptr mp_res_chains;
247 typename res_chains_type::const_iterator m_cur_chain;
248 typename value_chain_type::const_iterator m_cur_pos_in_chain;
249 bool m_end_pos = true;
250 };
251
252 class search_result_inserter
253 {
254 public:
255 search_result_inserter(search_results_base& results) : m_results(results)
256 {}
257 void operator()(value_chain_type* node_data)
258 {
259 if (!node_data)
260 return;
261
262 m_results.push_back_chain(node_data);
263 }
264
265 private:
266 search_results_base& m_results;
267 };
268
269public:
270 class search_results : public search_results_base
271 {
272 friend class segment_tree;
273
274 typedef typename search_results_base::res_chains_type res_chains_type;
275 typedef typename search_results_base::res_chains_ptr res_chains_ptr;
276
277 search_results(const segment_store_type& segment_tree) : search_results_base(segment_tree)
278 {}
279
280 public:
281 class const_iterator : public const_iterator_base
282 {
283 friend class segment_tree<KeyT, ValueT>::search_results;
284
285 private:
286 const_iterator(const segment_store_type* segment_store, const res_chains_ptr& p)
287 : const_iterator_base(segment_store, p)
288 {}
289
290 public:
291 const_iterator() : const_iterator_base()
292 {}
293
294 const_iterator(const const_iterator& r) : const_iterator_base(r)
295 {}
296
297 const_iterator& operator=(const const_iterator& r)
298 {
299 const_iterator_base::operator=(r);
300 return *this;
301 }
302 };
303
309 bool empty() const
310 {
311 return search_results_base::empty();
312 }
313
319 size_type size() const
320 {
321 return search_results_base::size();
322 }
323
324 typename search_results::const_iterator begin() const
325 {
327 search_results_base::get_segment_store(), search_results_base::get_res_chains());
328 it.move_to_front();
329 return it;
330 }
331
332 typename search_results::const_iterator end() const
333 {
334 typename search_results::const_iterator it(
335 search_results_base::get_segment_store(), search_results_base::get_res_chains());
336 it.move_to_end();
337 return it;
338 }
339 };
340
341 segment_tree();
342 segment_tree(const segment_tree& r);
343 segment_tree(segment_tree&& r);
344 ~segment_tree();
345
346 segment_tree& operator=(const segment_tree& r);
347 segment_tree& operator=(segment_tree&& r);
348
356 bool operator==(const segment_tree& r) const;
357
358 bool operator!=(const segment_tree& r) const;
359
366 bool valid_tree() const noexcept
367 {
368 return m_valid_tree;
369 }
370
378
387 void insert(key_type start_key, key_type end_key, value_type value);
388
405 search_results search(const key_type& point) const;
406
414 void erase(const typename search_results::const_iterator& pos);
415
437 template<typename Pred>
438 size_type erase_if(Pred pred);
439
445 void swap(segment_tree& r) noexcept;
446
450 void clear();
451
455 size_type size() const;
456
460 bool empty() const;
461
467 size_type leaf_size() const;
468
474 std::string to_string() const;
475
482 std::vector<key_type> boundary_keys() const;
483
485 {
487 {
488 key_type key = {};
489 std::vector<value_type> value_chain;
490 };
491
492 std::vector<leaf_node> leaf_nodes;
493 };
494
495 void check_integrity(const integrity_check_properties& props) const;
496
497private:
498 static void create_leaf_node_instances(std::vector<key_type> keys, node_ptr& left, node_ptr& right);
499
505 void descend_tree_and_mark(
506 st::detail::node_base* pnode, value_pos_type value, const key_type& start_key, const key_type& end_key,
507 node_chain_type& nodelist);
508
509 void build_leaf_nodes();
510
515 void remove_data_from_nodes(node_chain_type& nodelist, value_pos_type value);
516 void remove_data_from_chain(value_chain_type& chain, value_pos_type value);
517 void remove_value_pos(size_type pos);
518
519 void clear_all_nodes();
520
521private:
522 struct tree_dumper_traits
523 {
524 using leaf_type = node;
525 using nonleaf_type = nonleaf_node;
526 using tree_type = segment_tree;
527
529 {
530 const tree_type& tree;
531
532 to_string(const tree_type& _tree);
533 std::string operator()(const leaf_type& leaf) const;
534 std::string operator()(const nonleaf_type& nonleaf) const;
535 };
536 };
537
538 std::vector<nonleaf_node> m_nonleaf_node_pool;
539
545 segment_store_type m_segment_store;
546
552 value_to_nodes_type m_tagged_nodes_map;
553
554 nonleaf_node* m_root_node;
555 node_ptr m_left_leaf;
556 node_ptr m_right_leaf;
557 bool m_valid_tree;
558};
559
560} // namespace mdds
561
562#include "segment_tree_def.inl"
563
564#endif
Definition segment_tree.hpp:271
size_type size() const
Definition segment_tree.hpp:319
bool empty() const
Definition segment_tree.hpp:309
Definition segment_tree.hpp:65
bool empty() const
KeyT key_type
Definition segment_tree.hpp:68
size_type leaf_size() const
ValueT value_type
Definition segment_tree.hpp:70
void insert(key_type start_key, key_type end_key, value_type value)
void erase(const typename search_results::const_iterator &pos)
size_type size() const
bool operator==(const segment_tree &r) const
std::vector< key_type > boundary_keys() const
std::string to_string() const
void swap(segment_tree &r) noexcept
search_results search(const key_type &point) const
bool valid_tree() const noexcept
Definition segment_tree.hpp:366
size_type erase_if(Pred pred)
Definition segment_tree.hpp:485
Definition node.hpp:49
Definition node.hpp:123