57 typedef typename T::nonleaf_value_type nonleaf_value_type;
58 typedef typename T::fill_nonleaf_value_handler fill_nonleaf_value_handler;
59 typedef typename T::init_handler init_handler;
60 typedef typename T::dispose_handler dispose_handler;
62 typedef typename T::to_string_handler to_string_handler;
64 nonleaf_value_type value_nonleaf;
70 fill_nonleaf_value_handler _hdl_fill_nonleaf;
71 init_handler _hdl_init;
72 dispose_handler _hdl_dispose;
74 to_string_handler _hdl_to_string;
89 value_nonleaf = r.value_nonleaf;
101 value_nonleaf = r.value_nonleaf;
115 bool equals(
const nonleaf_node& r)
const
117 return value_nonleaf == r.value_nonleaf;
120 void fill_nonleaf_value(
const node_base* left_node,
const node_base* right_node)
122 _hdl_fill_nonleaf(*
this, left_node, right_node);
126 void dump_value()
const
128 ::std::cout << _hdl_to_string(*
this);
131 ::std::string to_string()
const
133 return _hdl_to_string(*
this);
141 typedef ::boost::intrusive_ptr<node> node_ptr;
143 typedef typename T::leaf_value_type leaf_value_type;
144 typedef typename T::init_handler init_handler;
145 typedef typename T::dispose_handler dispose_handler;
147 typedef typename T::to_string_handler to_string_handler;
150 static size_t get_instance_count()
152#ifdef MDDS_DEBUG_NODE_BASE
153 return node_instance_count;
159 leaf_value_type value_leaf;
167 init_handler _hdl_init;
168 dispose_handler _hdl_dispose;
170 to_string_handler _hdl_to_string;
176#ifdef MDDS_DEBUG_NODE_BASE
177 ++node_instance_count;
188#ifdef MDDS_DEBUG_NODE_BASE
189 ++node_instance_count;
191 value_leaf = r.value_leaf;
203 value_leaf = r.value_leaf;
209#ifdef MDDS_DEBUG_NODE_BASE
210 --node_instance_count;
220 bool equals(
const node& r)
const
222 return value_leaf == r.value_leaf;
226 void dump_value()
const
228 ::std::cout << _hdl_to_string(*
this);
231 ::std::string to_string()
const
233 return _hdl_to_string(*
this);
264 typedef typename mdds::__st::node<T>::node_ptr leaf_node_ptr;
266 typedef std::vector<nonleaf_node> nonleaf_node_pool_type;
268 tree_builder(nonleaf_node_pool_type& pool) : m_pool(pool), m_pool_pos(pool.begin()), m_pool_pos_end(pool.end())
271 nonleaf_node* build(
const leaf_node_ptr& left_leaf_node)
277 leaf_node_ptr node1 = left_leaf_node;
279 std::vector<nonleaf_node*> node_list;
282 leaf_node_ptr node2 = node1->next;
283 nonleaf_node* parent_node = make_parent_node(node1.get(), node2.get());
284 node_list.push_back(parent_node);
286 if (!node2 || !node2->next)
293 return build_tree_non_leaf(node_list);
299 assert(m_pool_pos != m_pool_pos_end);
303 node1->parent = parent_node;
304 parent_node->left = node1;
307 node2->parent = parent_node;
308 parent_node->
right = node2;
311 parent_node->fill_nonleaf_value(node1, node2);
315 nonleaf_node* build_tree_non_leaf(
const std::vector<nonleaf_node*>& node_list)
317 size_t node_count = node_list.size();
320 return node_list.front();
322 else if (node_count == 0)
325 std::vector<nonleaf_node*> new_node_list;
327 typename std::vector<nonleaf_node*>::const_iterator it = node_list.begin();
328 typename std::vector<nonleaf_node*>::const_iterator it_end = node_list.end();
329 for (
bool even_itr =
false; it != it_end; ++it, even_itr = !even_itr)
334 nonleaf_node* parent_node = make_parent_node(node1, node2);
335 new_node_list.push_back(parent_node);
346 nonleaf_node* parent_node = make_parent_node(node1,
nullptr);
347 new_node_list.push_back(parent_node);
351 return build_tree_non_leaf(new_node_list);
354 nonleaf_node_pool_type& m_pool;
355 typename nonleaf_node_pool_type::iterator m_pool_pos;
356 typename nonleaf_node_pool_type::iterator m_pool_pos_end;