71 using size_type = std::size_t;
82 segment_type(
const segment_type&) =
default;
83 segment_type(segment_type&&) =
default;
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;
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>;
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>;
99 struct nonleaf_value_type
101 std::unique_ptr<value_chain_type> data_chain;
105 nonleaf_value_type(
const nonleaf_value_type& r)
108 data_chain = std::make_unique<value_chain_type>(*r.data_chain);
111 bool operator==(
const nonleaf_value_type& r)
const
113 return data_chain == r.data_chain;
116 ~nonleaf_value_type()
120 struct leaf_value_type
122 std::unique_ptr<value_chain_type> data_chain;
126 leaf_value_type(
const leaf_value_type& r)
129 data_chain = std::make_unique<value_chain_type>(*r.data_chain);
132 bool operator==(
const leaf_value_type& r)
const
134 return data_chain == r.data_chain;
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>;
147 class search_result_inserter;
153 class search_results_base
155 friend class search_result_inserter;
158 typedef std::vector<value_chain_type*> res_chains_type;
159 typedef std::shared_ptr<res_chains_type> res_chains_ptr;
162 search_results_base(
const segment_store_type& segment_store) : m_segment_store(&segment_store)
165 search_results_base(
const search_results_base& r)
166 : m_segment_store(r.m_segment_store), mp_res_chains(r.mp_res_chains)
171 size_type size()
const;
173 void push_back_chain(value_chain_type* chain);
175 const segment_store_type* get_segment_store()
const
177 return m_segment_store;
180 const res_chains_ptr& get_res_chains()
const
182 return mp_res_chains;
186 const segment_store_type* m_segment_store =
nullptr;
187 res_chains_ptr mp_res_chains;
190 class const_iterator_base
192 friend class segment_tree;
195 typedef typename search_results_base::res_chains_type res_chains_type;
196 typedef typename search_results_base::res_chains_ptr res_chains_ptr;
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)
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;
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;
213 value_type* operator++();
214 value_type* operator--();
216 bool operator==(
const const_iterator_base& r)
const;
217 bool operator!=(
const const_iterator_base& r)
const;
219 value_type& operator*()
224 const value_type* operator->()
230 void move_to_front();
234 value_type& cur_value()
236 auto pos = *m_cur_pos_in_chain;
237 return (*m_segment_store)[pos];
240 size_type cur_pos()
const
242 return *m_cur_pos_in_chain;
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;
252 class search_result_inserter
255 search_result_inserter(search_results_base& results) : m_results(results)
257 void operator()(value_chain_type* node_data)
262 m_results.push_back_chain(node_data);
266 search_results_base& m_results;
274 typedef typename search_results_base::res_chains_type res_chains_type;
275 typedef typename search_results_base::res_chains_ptr res_chains_ptr;
286 const_iterator(const segment_store_type* segment_store, const res_chains_ptr& p)
287 : const_iterator_base(segment_store, p)
299 const_iterator_base::operator=(r);
311 return search_results_base::empty();
321 return search_results_base::size();
327 search_results_base::get_segment_store(), search_results_base::get_res_chains());
332 typename search_results::const_iterator end()
const
334 typename search_results::const_iterator it(
335 search_results_base::get_segment_store(), search_results_base::get_res_chains());
342 segment_tree(
const segment_tree& r);
343 segment_tree(segment_tree&& r);
346 segment_tree& operator=(
const segment_tree& r);
347 segment_tree& operator=(segment_tree&& r);
437 template<
typename Pred>
489 std::vector<value_type> value_chain;
492 std::vector<leaf_node> leaf_nodes;
498 static void create_leaf_node_instances(std::vector<key_type> keys, node_ptr& left, node_ptr& right);
505 void descend_tree_and_mark(
507 node_chain_type& nodelist);
509 void build_leaf_nodes();
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);
519 void clear_all_nodes();
522 struct tree_dumper_traits
524 using leaf_type =
node;
525 using nonleaf_type = nonleaf_node;
533 std::string operator()(
const leaf_type& leaf)
const;
534 std::string operator()(
const nonleaf_type& nonleaf)
const;
538 std::vector<nonleaf_node> m_nonleaf_node_pool;
545 segment_store_type m_segment_store;
552 value_to_nodes_type m_tagged_nodes_map;
554 nonleaf_node* m_root_node;
555 node_ptr m_left_leaf;
556 node_ptr m_right_leaf;