50 using size_type = std::size_t;
59 segment_type() =
default;
61 segment_type(
const segment_type&) =
default;
62 segment_type(segment_type&&) =
default;
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;
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>;
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>;
77 struct nonleaf_value_type
79 std::unique_ptr<value_chain_type> data_chain;
83 nonleaf_value_type(
const nonleaf_value_type& r)
86 data_chain = std::make_unique<value_chain_type>(*r.data_chain);
89 bool operator==(
const nonleaf_value_type& r)
const
91 return data_chain == r.data_chain;
98 struct leaf_value_type
100 std::unique_ptr<value_chain_type> data_chain;
104 leaf_value_type(
const leaf_value_type& r)
107 data_chain = std::make_unique<value_chain_type>(*r.data_chain);
110 bool operator==(
const leaf_value_type& r)
const
112 return data_chain == r.data_chain;
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>;
125 class search_result_inserter;
131 class search_results_base
133 friend class search_result_inserter;
136 typedef std::vector<value_chain_type*> res_chains_type;
137 typedef std::shared_ptr<res_chains_type> res_chains_ptr;
140 search_results_base(
const segment_store_type& segment_store) : m_segment_store(&segment_store)
143 search_results_base(
const search_results_base& r)
144 : m_segment_store(r.m_segment_store), mp_res_chains(r.mp_res_chains)
149 size_type
size()
const;
151 void push_back_chain(value_chain_type* chain);
153 const segment_store_type* get_segment_store()
const
155 return m_segment_store;
158 const res_chains_ptr& get_res_chains()
const
160 return mp_res_chains;
164 const segment_store_type* m_segment_store =
nullptr;
165 res_chains_ptr mp_res_chains;
168 class const_iterator_base
170 friend class segment_tree;
173 typedef typename search_results_base::res_chains_type res_chains_type;
174 typedef typename search_results_base::res_chains_ptr res_chains_ptr;
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)
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;
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;
191 value_type* operator++();
192 value_type* operator--();
194 bool operator==(
const const_iterator_base& r)
const;
196 value_type& operator*()
201 const value_type* operator->()
207 void move_to_front();
211 value_type& cur_value()
213 auto pos = *m_cur_pos_in_chain;
214 return (*m_segment_store)[pos];
217 size_type cur_pos()
const
219 return *m_cur_pos_in_chain;
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;
229 class search_result_inserter
232 search_result_inserter(search_results_base& results) : m_results(results)
234 void operator()(value_chain_type* node_data)
239 m_results.push_back_chain(node_data);
243 search_results_base& m_results;
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>;
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>;
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>;
261 static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;
264 class search_results :
public search_results_base
266 friend class segment_tree;
268 typedef typename search_results_base::res_chains_type res_chains_type;
269 typedef typename search_results_base::res_chains_ptr res_chains_ptr;
271 search_results(
const segment_store_type& segment_tree) : search_results_base(segment_tree)
275 class const_iterator :
public const_iterator_base
277 friend class segment_tree<KeyT, ValueT>::search_results;
280 const_iterator(const segment_store_type* segment_store, const res_chains_ptr& p)
281 : const_iterator_base(segment_store, p)
285 const_iterator() : const_iterator_base()
288 const_iterator(
const const_iterator& r) : const_iterator_base(r)
291 const_iterator& operator=(
const const_iterator& r)
293 const_iterator_base::operator=(r);
305 return search_results_base::empty();
315 return search_results_base::size();
321 search_results_base::get_segment_store(), search_results_base::get_res_chains());
326 typename search_results::const_iterator end()
const
328 typename search_results::const_iterator it(
329 search_results_base::get_segment_store(), search_results_base::get_res_chains());
335 segment_tree() noexcept(nothrow_default_constructible_v);
336 segment_tree(const segment_tree& r);
337 segment_tree(segment_tree&& r) = default;
340 segment_tree& operator=(const segment_tree& r);
341 segment_tree& operator=(segment_tree&& r) noexcept(nothrow_move_assignable_v);
350 bool operator==(const segment_tree& r) const;
429 template<
typename Pred>
437 void swap(segment_tree& r)
noexcept(nothrow_swappable_v);
460 noexcept(noexcept(st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get())))
462 return st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get());
485 std::vector<value_type> value_chain;
488 std::vector<leaf_node> leaf_nodes;
494 static void create_leaf_node_instances(std::vector<key_type> keys, node_ptr& left, node_ptr& right);
501 void descend_tree_and_mark(
503 node_chain_type& nodelist);
505 void build_leaf_nodes();
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);
515 void clear_all_nodes();
518 struct tree_dumper_traits
520 using leaf_type = node;
521 using nonleaf_type = nonleaf_node;
522 using tree_type = segment_tree;
526 const tree_type& tree;
529 std::string operator()(
const leaf_type& leaf)
const;
530 std::string operator()(
const nonleaf_type& nonleaf)
const;
534 std::vector<nonleaf_node> m_nonleaf_node_pool;
541 segment_store_type m_segment_store;
548 value_to_nodes_type m_tagged_nodes_map;
550 nonleaf_node* m_root_node;
551 node_ptr m_left_leaf;
552 node_ptr m_right_leaf;