28#ifndef INCLUDED_MDDS_SEGMENTTREE_HPP
29#define INCLUDED_MDDS_SEGMENTTREE_HPP
31#include "mdds/node.hpp"
32#include "mdds/global.hpp"
37#include <unordered_map>
46template<
typename _Key,
typename _Value>
50 typedef _Key key_type;
51 typedef _Value value_type;
52 typedef size_t size_type;
53 typedef std::vector<value_type> search_results_type;
62 segment_data(key_type _beg, key_type _end, value_type p) : begin_key(_beg), end_key(_end), pdata(p)
67 return begin_key == r.begin_key && end_key == r.end_key && pdata == r.pdata;
70 bool operator!=(
const segment_data& r)
const
76 struct segment_map_printer
78 void operator()(const ::std::pair<value_type, ::std::pair<key_type, key_type>>& r)
const
81 cout << r.second.first <<
"-" << r.second.second <<
": " << r.first->name << endl;
87 typedef ::std::vector<value_type> data_chain_type;
88 typedef std::unordered_map<value_type, ::std::pair<key_type, key_type>> segment_map_type;
89 typedef ::std::map<value_type, ::std::pair<key_type, key_type>> sorted_segment_map_type;
106 data_chain_type* data_chain;
110 return key == r.key && data_chain == r.data_chain;
118 struct to_string_handler;
122 typedef typename node::node_ptr node_ptr;
135 _self.value_nonleaf.low = left_node->
is_leaf
136 ?
static_cast<const node*
>(left_node)->value_leaf.key
137 :
static_cast<const nonleaf_node*
>(left_node)->value_nonleaf.low;
142 throw general_error(
"segment_tree::fill_nonleaf_value_handler: Having a left node is prerequisite.");
153 const node* p =
static_cast<const node*
>(right_node);
155 _self.value_nonleaf.high = p->
next->value_leaf.key;
157 _self.value_nonleaf.high = p->value_leaf.key;
161 _self.value_nonleaf.high =
static_cast<const nonleaf_node*
>(right_node)->value_nonleaf.high;
166 _self.value_nonleaf.high = left_node->
is_leaf
167 ?
static_cast<const node*
>(left_node)->value_leaf.key
168 :
static_cast<const nonleaf_node*
>(left_node)->value_nonleaf.high;
174 struct to_string_handler
176 std::string operator()(
const node& _self)
const
178 std::ostringstream os;
179 os <<
"[" << _self.value_leaf.key <<
"] ";
185 std::ostringstream os;
186 os <<
"[" << _self.value_nonleaf.low <<
"-" << _self.value_nonleaf.high <<
")";
187 if (_self.value_nonleaf.data_chain)
190 typename data_chain_type::const_iterator itr, itr_beg = _self.value_nonleaf.data_chain->begin(),
191 itr_end = _self.value_nonleaf.data_chain->end();
192 for (itr = itr_beg; itr != itr_end; ++itr)
208 void operator()(
node& _self)
210 _self.value_leaf.data_chain =
nullptr;
215 _self.value_nonleaf.data_chain =
nullptr;
221 void operator()(
node& _self)
223 delete _self.value_leaf.data_chain;
228 delete _self.value_nonleaf.data_chain;
238 std::cout << static_cast<const node*>(p)->to_string() <<
" ";
240 std::cout << static_cast<const nonleaf_node*>(p)->to_string() <<
" ";
250 class search_results_base
253 typedef std::vector<data_chain_type*> res_chains_type;
254 typedef std::shared_ptr<res_chains_type> res_chains_ptr;
257 search_results_base() : mp_res_chains(static_cast<res_chains_type*>(nullptr))
260 search_results_base(
const search_results_base& r) : mp_res_chains(r.mp_res_chains)
269 typename res_chains_type::const_iterator itr = mp_res_chains->begin(), itr_end = mp_res_chains->end();
270 for (; itr != itr_end; ++itr)
271 combined += (*itr)->size();
275 void push_back_chain(data_chain_type* chain)
277 if (!chain || chain->empty())
281 mp_res_chains.reset(
new res_chains_type);
282 mp_res_chains->push_back(chain);
285 res_chains_ptr& get_res_chains()
287 return mp_res_chains;
291 res_chains_ptr mp_res_chains;
297 typedef typename search_results_base::res_chains_type res_chains_type;
298 typedef typename search_results_base::res_chains_ptr res_chains_ptr;
300 iterator_base(
const res_chains_ptr& p) : mp_res_chains(p), m_end_pos(true)
304 typedef ::std::bidirectional_iterator_tag iterator_category;
305 typedef typename data_chain_type::value_type value_type;
306 typedef typename data_chain_type::pointer pointer;
307 typedef typename data_chain_type::reference reference;
308 typedef typename data_chain_type::difference_type difference_type;
310 iterator_base() : mp_res_chains(static_cast<res_chains_type*>(nullptr)), m_end_pos(true)
313 iterator_base(
const iterator_base& r)
314 : mp_res_chains(r.mp_res_chains), m_cur_chain(r.m_cur_chain), m_cur_pos_in_chain(r.m_cur_pos_in_chain),
315 m_end_pos(r.m_end_pos)
318 iterator_base& operator=(
const iterator_base& r)
320 mp_res_chains = r.mp_res_chains;
321 m_cur_chain = r.m_cur_chain;
322 m_cur_pos_in_chain = r.m_cur_pos_in_chain;
323 m_end_pos = r.m_end_pos;
327 typename data_chain_type::value_type* operator++()
338 typename data_chain_type::iterator cur_pos_in_chain = m_cur_pos_in_chain;
340 if (++cur_pos_in_chain == (*m_cur_chain)->end())
343 typename res_chains_type::iterator cur_chain = m_cur_chain;
345 if (cur_chain == mp_res_chains->end())
350 m_cur_chain = cur_chain;
351 m_cur_pos_in_chain = (*m_cur_chain)->begin();
354 ++m_cur_pos_in_chain;
359 typename data_chain_type::value_type* operator--()
367 return &(*m_cur_pos_in_chain);
370 if (m_cur_pos_in_chain == (*m_cur_chain)->begin())
372 if (m_cur_chain == mp_res_chains->begin())
378 m_cur_pos_in_chain = (*m_cur_chain)->end();
380 --m_cur_pos_in_chain;
386 if (mp_res_chains.get())
389 return mp_res_chains.get() == r.mp_res_chains.get() && m_cur_chain == r.m_cur_chain &&
390 m_cur_pos_in_chain == r.m_cur_pos_in_chain && m_end_pos == r.m_end_pos;
394 if (r.mp_res_chains.get())
396 return m_end_pos == r.m_end_pos;
399 bool operator!=(
const iterator_base& r)
const
404 typename data_chain_type::value_type& operator*()
406 return *m_cur_pos_in_chain;
409 typename data_chain_type::value_type* operator->()
411 return &(*m_cur_pos_in_chain);
426 m_cur_chain = mp_res_chains->begin();
427 m_cur_pos_in_chain = (*m_cur_chain)->begin();
438 m_cur_chain = mp_res_chains->end();
440 m_cur_pos_in_chain = (*m_cur_chain)->end();
441 --m_cur_pos_in_chain;
445 res_chains_ptr mp_res_chains;
446 typename res_chains_type::iterator m_cur_chain;
447 typename data_chain_type::iterator m_cur_pos_in_chain;
454 typedef typename search_results_base::res_chains_type res_chains_type;
455 typedef typename search_results_base::res_chains_ptr res_chains_ptr;
463 iterator(const res_chains_ptr& p) : iterator_base(p)
491 void operator()(data_chain_type* node_data)
496 typename data_chain_type::const_iterator itr = node_data->begin(), itr_end = node_data->end();
497 for (; itr != itr_end; ++itr)
498 m_result.push_back(*itr);
502 search_results_type& m_result;
510 void operator()(data_chain_type* node_data)
515 m_result.push_back_chain(node_data);
519 search_results_base& m_result;
562 bool insert(key_type begin_key, key_type end_key, value_type pdata);
580 bool search(key_type point, search_results_type& result)
const;
625 void dump_tree()
const;
626 void dump_leaf_nodes()
const;
627 void dump_segment_data()
const;
628 bool verify_node_lists()
const;
630 struct leaf_node_check
633 data_chain_type data_chain;
636 bool verify_leaf_nodes(const ::std::vector<leaf_node_check>& checks)
const;
644 bool verify_segment_data(
const segment_map_type& checks)
const;
651 void search(key_type point, search_results_base& result)
const;
653 typedef std::vector<__st::node_base*> node_list_type;
654 typedef std::map<value_type, std::unique_ptr<node_list_type>> data_node_map_type;
656 static void create_leaf_node_instances(const ::std::vector<key_type>& keys, node_ptr& left, node_ptr& right);
663 void descend_tree_and_mark(
664 __st::node_base* pnode, value_type pdata, key_type begin_key, key_type end_key, node_list_type* plist);
666 void build_leaf_nodes();
672 void remove_data_from_nodes(node_list_type* plist,
const value_type pdata);
673 void remove_data_from_chain(data_chain_type& chain,
const value_type pdata);
675 void clear_all_nodes();
678 static bool has_data_pointer(
const node_list_type& node_list,
const value_type pdata);
679 static void print_leaf_value(
const leaf_value_type& v);
683 std::vector<nonleaf_node> m_nonleaf_node_pool;
685 segment_map_type m_segment_data;
692 data_node_map_type m_tagged_node_map;
694 nonleaf_node* m_root_node;
695 node_ptr m_left_leaf;
696 node_ptr m_right_leaf;
697 bool m_valid_tree : 1;
702#include "segment_tree_def.inl"
Definition: global.hpp:84
Definition: segment_tree.hpp:506
Definition: segment_tree.hpp:487
Definition: segment_tree.hpp:459
Definition: segment_tree.hpp:453
Definition: segment_tree.hpp:48
bool insert(key_type begin_key, key_type end_key, value_type pdata)
bool operator==(const segment_tree &r) const
bool search(key_type point, search_results_type &result) const
void remove(value_type value)
bool is_tree_valid() const
Definition: segment_tree.hpp:543
search_results search(key_type point) const
bool is_leaf
parent nonleaf_node
Definition: node.hpp:46
node_ptr next
previous sibling leaf node.
Definition: node.hpp:162
Definition: segment_tree.hpp:220
Definition: segment_tree.hpp:127
Definition: segment_tree.hpp:207
Definition: segment_tree.hpp:104
Definition: segment_tree.hpp:92
key_type high
low range value (inclusive)
Definition: segment_tree.hpp:94
data_chain_type * data_chain
high range value (non-inclusive)
Definition: segment_tree.hpp:95