28#ifndef __MDDS_NODE_HXX__
29#define __MDDS_NODE_HXX__
35#include <boost/intrusive_ptr.hpp>
37namespace mdds {
namespace __st {
39#ifdef MDDS_DEBUG_NODE_BASE
40size_t node_instance_count = 0;
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);
239inline void intrusive_ptr_add_ref(node<T>* p)
245inline void intrusive_ptr_release(node<T>* p)
253void link_nodes(
typename node<T>::node_ptr& left,
typename node<T>::node_ptr& right)
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;
360void disconnect_all_nodes(
node<T>* p)
371void disconnect_leaf_nodes(node<T>* left_node, node<T>* right_node)
373 if (!left_node || !right_node)
377 node<T>* cur_node = left_node;
380 node<T>* next_node = cur_node->next.get();
381 disconnect_all_nodes(cur_node);
382 cur_node = next_node;
383 }
while (cur_node != right_node);
385 disconnect_all_nodes(right_node);
389size_t count_leaf_nodes(
const node<T>* left_end,
const node<T>* right_end)
391 size_t leaf_count = 1;
392 const node<T>* p = left_end;
393 const node<T>* p_end = right_end;
394 for (; p != p_end; p = p->next.get(), ++leaf_count)
400inline size_t count_needed_nonleaf_nodes(
size_t leaf_count)
402 size_t nonleaf_count = 0;
408 if ((leaf_count % 2) == 1)
413 nonleaf_count += leaf_count;
416 return nonleaf_count;
421template<
typename _Leaf,
typename _NonLeaf>
424 typedef std::vector<const node_base*> node_list_type;
427 static size_t dump(
const node_base* root_node)
432 node_list_type node_list;
433 node_list.push_back(root_node);
434 return dump_layer(node_list, 0);
438 static size_t dump_layer(
const node_list_type& node_list,
unsigned int level)
443 if (node_list.empty())
446 size_t node_count = node_list.size();
448 bool is_leaf = node_list.front()->is_leaf;
449 cout <<
"level " << level <<
" (" << (is_leaf ?
"leaf" :
"non-leaf") <<
")" << endl;
451 node_list_type new_list;
452 typename node_list_type::const_iterator it = node_list.begin(), it_end = node_list.end();
453 for (; it != it_end; ++it)
455 const node_base* p = *it;
463 static_cast<const _Leaf*
>(p)->dump_value();
465 static_cast<const _NonLeaf*
>(p)->dump_value();
470 if (
static_cast<const _NonLeaf*
>(p)->left)
472 new_list.push_back(
static_cast<const _NonLeaf*
>(p)->left);
473 if (
static_cast<const _NonLeaf*
>(p)->right)
474 new_list.push_back(
static_cast<const _NonLeaf*
>(p)->right);
479 if (!new_list.empty())
480 node_count += dump_layer(new_list, level + 1);
bool is_leaf
parent nonleaf_node
Definition: node.hpp:46
size_t refcount
next sibling leaf node.
Definition: node.hpp:164
node_ptr next
previous sibling leaf node.
Definition: node.hpp:162
node & operator=(const node &r)
Definition: node.hpp:197
node(const node &r)
Definition: node.hpp:186
node_base * right
left child nonleaf_node
Definition: node.hpp:67
nonleaf_node & operator=(const nonleaf_node &r)
Definition: node.hpp:95
nonleaf_node(const nonleaf_node &r)
Definition: node.hpp:87