mdds
Loading...
Searching...
No Matches
segment_tree.hpp
1// SPDX-FileCopyrightText: 2010 - 2025 Kohei Yoshida
2//
3// SPDX-License-Identifier: MIT
4
5#pragma once
6
7#include "./node.hpp"
8#include "./global.hpp"
9
10#include <vector>
11#include <compare>
12#include <deque>
13#include <iostream>
14#include <map>
15#include <unordered_map>
16#include <memory>
17#include <sstream>
18#include <type_traits>
19#include <utility>
20
21namespace mdds {
22
42template<typename KeyT, typename ValueT>
43class segment_tree
44{
45public:
47 using key_type = KeyT;
49 using value_type = ValueT;
50 using size_type = std::size_t;
51
52private:
53 struct segment_type
54 {
55 key_type start;
56 key_type end;
57 value_type value;
58
59 segment_type() = default;
60 segment_type(key_type _start, key_type _end, value_type _value);
61 segment_type(const segment_type&) = default;
62 segment_type(segment_type&&) = default;
63
64 segment_type& operator=(const segment_type& r) = default;
65 segment_type& operator=(segment_type&& r) = default;
66 auto operator<=>(const segment_type& r) const = default;
67 bool operator==(const segment_type& r) const = default;
68 };
69
70 using segment_store_type = std::deque<segment_type>;
71 using value_pos_type = typename segment_store_type::size_type;
72 using value_chain_type = std::vector<value_pos_type>;
73
74 using node_chain_type = std::vector<st::detail::node_base*>;
75 using value_to_nodes_type = std::map<value_pos_type, node_chain_type>;
76
77 struct nonleaf_value_type
78 {
79 std::unique_ptr<value_chain_type> data_chain;
80
81 nonleaf_value_type()
82 {}
83 nonleaf_value_type(const nonleaf_value_type& r)
84 {
85 if (r.data_chain)
86 data_chain = std::make_unique<value_chain_type>(*r.data_chain);
87 }
88
89 bool operator==(const nonleaf_value_type& r) const
90 {
91 return data_chain == r.data_chain;
92 }
93
94 ~nonleaf_value_type()
95 {}
96 };
97
98 struct leaf_value_type
99 {
100 std::unique_ptr<value_chain_type> data_chain;
101
102 leaf_value_type()
103 {}
104 leaf_value_type(const leaf_value_type& r)
105 {
106 if (r.data_chain)
107 data_chain = std::make_unique<value_chain_type>(*r.data_chain);
108 }
109
110 bool operator==(const leaf_value_type& r) const
111 {
112 return data_chain == r.data_chain;
113 }
114
115 ~leaf_value_type()
116 {}
117 };
118
119public:
120 using node = st::detail::node<key_type, leaf_value_type>;
121 using node_ptr = typename node::node_ptr;
122 using nonleaf_node = typename st::detail::nonleaf_node<key_type, nonleaf_value_type>;
123
124private:
125 class search_result_inserter;
126
131 class search_results_base
132 {
133 friend class search_result_inserter;
134
135 public:
136 typedef std::vector<value_chain_type*> res_chains_type;
137 typedef std::shared_ptr<res_chains_type> res_chains_ptr;
138
139 protected:
140 search_results_base(const segment_store_type& segment_store) : m_segment_store(&segment_store)
141 {}
142
143 search_results_base(const search_results_base& r)
144 : m_segment_store(r.m_segment_store), mp_res_chains(r.mp_res_chains)
145 {}
146
147 bool empty() const;
148
149 size_type size() const;
150
151 void push_back_chain(value_chain_type* chain);
152
153 const segment_store_type* get_segment_store() const
154 {
155 return m_segment_store;
156 }
157
158 const res_chains_ptr& get_res_chains() const
159 {
160 return mp_res_chains;
161 }
162
163 private:
164 const segment_store_type* m_segment_store = nullptr;
165 res_chains_ptr mp_res_chains;
166 };
167
168 class const_iterator_base
169 {
170 friend class segment_tree;
171
172 protected:
173 typedef typename search_results_base::res_chains_type res_chains_type;
174 typedef typename search_results_base::res_chains_ptr res_chains_ptr;
175
176 const_iterator_base(const segment_store_type* segment_store, const res_chains_ptr& p)
177 : m_segment_store(segment_store), mp_res_chains(p), m_end_pos(true)
178 {}
179
180 public:
181 using iterator_category = std::bidirectional_iterator_tag;
182 using value_type = const segment_tree::segment_type;
183 using pointer = value_type*;
184 using reference = value_type&;
185 using difference_type = std::ptrdiff_t;
186
187 const_iterator_base() = default;
188 const_iterator_base(const const_iterator_base& r) = default;
189 const_iterator_base& operator=(const const_iterator_base& r) = default;
190
191 value_type* operator++();
192 value_type* operator--();
193
194 bool operator==(const const_iterator_base& r) const;
195
196 value_type& operator*()
197 {
198 return cur_value();
199 }
200
201 const value_type* operator->()
202 {
203 return &cur_value();
204 }
205
206 protected:
207 void move_to_front();
208 void move_to_end();
209
210 private:
211 value_type& cur_value()
212 {
213 auto pos = *m_cur_pos_in_chain;
214 return (*m_segment_store)[pos];
215 }
216
217 size_type cur_pos() const
218 {
219 return *m_cur_pos_in_chain;
220 }
221
222 const segment_store_type* m_segment_store = nullptr;
223 res_chains_ptr mp_res_chains;
224 typename res_chains_type::const_iterator m_cur_chain;
225 typename value_chain_type::const_iterator m_cur_pos_in_chain;
226 bool m_end_pos = true;
227 };
228
229 class search_result_inserter
230 {
231 public:
232 search_result_inserter(search_results_base& results) : m_results(results)
233 {}
234 void operator()(value_chain_type* node_data)
235 {
236 if (!node_data)
237 return;
238
239 m_results.push_back_chain(node_data);
240 }
241
242 private:
243 search_results_base& m_results;
244 };
245
246 static constexpr bool nothrow_default_constructible_v =
247 std::is_nothrow_default_constructible_v<std::vector<nonleaf_node>> &&
248 std::is_nothrow_default_constructible_v<segment_store_type> &&
249 std::is_nothrow_default_constructible_v<value_to_nodes_type> &&
250 std::is_nothrow_default_constructible_v<node_ptr>;
251
252 static constexpr bool nothrow_move_constructible_v =
253 std::is_nothrow_move_constructible_v<std::vector<nonleaf_node>> &&
254 std::is_nothrow_move_constructible_v<segment_store_type> &&
255 std::is_nothrow_move_constructible_v<value_to_nodes_type> && std::is_nothrow_move_constructible_v<node_ptr>;
256
257 static constexpr bool nothrow_swappable_v =
258 std::is_nothrow_swappable_v<std::vector<nonleaf_node>> && std::is_nothrow_swappable_v<segment_store_type> &&
259 std::is_nothrow_swappable_v<value_to_nodes_type> && std::is_nothrow_swappable_v<node_ptr>;
260
261 static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;
262
263public:
264 class search_results : public search_results_base
265 {
266 friend class segment_tree;
267
268 typedef typename search_results_base::res_chains_type res_chains_type;
269 typedef typename search_results_base::res_chains_ptr res_chains_ptr;
270
271 search_results(const segment_store_type& segment_tree) : search_results_base(segment_tree)
272 {}
273
274 public:
275 class const_iterator : public const_iterator_base
276 {
277 friend class segment_tree<KeyT, ValueT>::search_results;
278
279 private:
280 const_iterator(const segment_store_type* segment_store, const res_chains_ptr& p)
281 : const_iterator_base(segment_store, p)
282 {}
283
284 public:
285 const_iterator() : const_iterator_base()
286 {}
287
288 const_iterator(const const_iterator& r) : const_iterator_base(r)
289 {}
290
291 const_iterator& operator=(const const_iterator& r)
292 {
293 const_iterator_base::operator=(r);
294 return *this;
295 }
296 };
297
303 bool empty() const
304 {
305 return search_results_base::empty();
306 }
307
313 size_type size() const
314 {
315 return search_results_base::size();
316 }
317
318 typename search_results::const_iterator begin() const
319 {
321 search_results_base::get_segment_store(), search_results_base::get_res_chains());
322 it.move_to_front();
323 return it;
324 }
325
326 typename search_results::const_iterator end() const
327 {
328 typename search_results::const_iterator it(
329 search_results_base::get_segment_store(), search_results_base::get_res_chains());
330 it.move_to_end();
331 return it;
332 }
333 };
334
335 segment_tree() noexcept(nothrow_default_constructible_v);
336 segment_tree(const segment_tree& r);
337 segment_tree(segment_tree&& r) = default;
338 ~segment_tree();
339
340 segment_tree& operator=(const segment_tree& r);
341 segment_tree& operator=(segment_tree&& r) noexcept(nothrow_move_assignable_v);
342
350 bool operator==(const segment_tree& r) const;
351
358 bool valid_tree() const noexcept
359 {
360 return m_valid_tree;
361 }
362
370
379 void insert(key_type start_key, key_type end_key, value_type value);
380
398
406 void erase(const typename search_results::const_iterator& pos);
407
429 template<typename Pred>
430 size_type erase_if(Pred pred);
431
437 void swap(segment_tree& r) noexcept(nothrow_swappable_v);
438
442 void clear();
443
447 size_type size() const;
448
452 bool empty() const;
453
459 size_type leaf_size() const
460 noexcept(noexcept(st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get())))
461 {
462 return st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get());
463 }
464
470 std::string to_string() const;
471
478 std::vector<key_type> boundary_keys() const;
479
481 {
483 {
484 key_type key = {};
485 std::vector<value_type> value_chain;
486 };
487
488 std::vector<leaf_node> leaf_nodes;
489 };
490
491 void check_integrity(const integrity_check_properties& props) const;
492
493private:
494 static void create_leaf_node_instances(std::vector<key_type> keys, node_ptr& left, node_ptr& right);
495
501 void descend_tree_and_mark(
502 st::detail::node_base* pnode, value_pos_type value, const key_type& start_key, const key_type& end_key,
503 node_chain_type& nodelist);
504
505 void build_leaf_nodes();
506
511 void remove_data_from_nodes(node_chain_type& nodelist, value_pos_type value);
512 void remove_data_from_chain(value_chain_type& chain, value_pos_type value);
513 void remove_value_pos(size_type pos);
514
515 void clear_all_nodes();
516
517private:
518 struct tree_dumper_traits
519 {
520 using leaf_type = node;
521 using nonleaf_type = nonleaf_node;
522 using tree_type = segment_tree;
523
524 struct to_string
525 {
526 const tree_type& tree;
527
528 to_string(const tree_type& _tree);
529 std::string operator()(const leaf_type& leaf) const;
530 std::string operator()(const nonleaf_type& nonleaf) const;
531 };
532 };
533
534 std::vector<nonleaf_node> m_nonleaf_node_pool;
535
541 segment_store_type m_segment_store;
542
548 value_to_nodes_type m_tagged_nodes_map;
549
550 nonleaf_node* m_root_node;
551 node_ptr m_left_leaf;
552 node_ptr m_right_leaf;
553 bool m_valid_tree;
554};
555
556} // namespace mdds
557
558#include "segment_tree_def.inl"
Definition segment_tree.hpp:265
size_type size() const
Definition segment_tree.hpp:313
bool empty() const
Definition segment_tree.hpp:303
bool empty() const
KeyT key_type
Definition segment_tree.hpp:47
ValueT value_type
Definition segment_tree.hpp:49
void insert(key_type start_key, key_type end_key, value_type value)
void erase(const typename search_results::const_iterator &pos)
size_type leaf_size() const noexcept(noexcept(st::detail::count_leaf_nodes< size_type >(m_left_leaf.get(), m_right_leaf.get())))
Definition segment_tree.hpp:459
size_type size() const
bool operator==(const segment_tree &r) const
std::vector< key_type > boundary_keys() const
std::string to_string() const
search_results search(const key_type &point) const
void swap(segment_tree &r) noexcept(nothrow_swappable_v)
bool valid_tree() const noexcept
Definition segment_tree.hpp:358
size_type erase_if(Pred pred)
Definition segment_tree.hpp:481
Definition node.hpp:25