sc/inc/mdds/node.hxx

   1 /*************************************************************************
   2  *
   3  * Copyright (c) 2008-2009 Kohei Yoshida
   4  *
   5  * Permission is hereby granted, free of charge, to any person
   6  * obtaining a copy of this software and associated documentation
   7  * files (the "Software"), to deal in the Software without
   8  * restriction, including without limitation the rights to use,
   9  * copy, modify, merge, publish, distribute, sublicense, and/or sell
  10  * copies of the Software, and to permit persons to whom the
  11  * Software is furnished to do so, subject to the following
  12  * conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be
  15  * included in all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
  19  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  20  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
  21  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
  22  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  23  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  24  * OTHER DEALINGS IN THE SOFTWARE.
  25  *
  26  ************************************************************************/
  27
  28 #ifndef __MDDS_NODE_HXX__
  29 #define __MDDS_NODE_HXX__
  30
  31 #include <iostream>
  32 #include <list>
  33 #include <cassert>
  34
  35 //#define DEBUG_NODE_BASE 1
  36
  37 #define USE_INTRUSIVE_PTR 0
  38
  39 #if USE_INTRUSIVE_PTR
  40 #include <boost/intrusive_ptr.hpp>
  41 #else
  42 #include <boost/shared_ptr.hpp>
  43 #endif
  44
  45 namespace mdds {
  46
  47 struct intrusive_ref_base
  48 {
  49 #if USE_INTRUSIVE_PTR
  50     size_t _refcount;
  51
  52     intrusive_ref_base() :
  53         _refcount(0) {}
  54 #endif
  55     virtual ~intrusive_ref_base() {}
  56 };
  57
  58 #if USE_INTRUSIVE_PTR
  59 inline void intrusive_ptr_add_ref(intrusive_ref_base* p)
  60 {
  61     ++p->_refcount;
  62 }
  63
  64 inline void intrusive_ptr_release(intrusive_ref_base* p)
  65 {
  66     --p->_refcount;
  67     if (!p->_refcount)
  68         delete p;
  69 }
  70 #endif
  71
  72 #ifdef DEBUG_NODE_BASE
  73 size_t node_instance_count = 0;
  74 #endif
  75
  76 struct node_base;
  77 #if USE_INTRUSIVE_PTR
  78 typedef ::boost::intrusive_ptr<node_base> node_base_ptr;
  79 #else
  80 typedef ::boost::shared_ptr<node_base> node_base_ptr;
  81 #endif
  82
  83 struct node_base : public intrusive_ref_base
  84 {
  85     static size_t get_instance_count()
  86     {
  87 #ifdef DEBUG_NODE_BASE
  88         return node_instance_count;
  89 #else
  90         return 0;
  91 #endif
  92     }
  93     node_base_ptr   parent; /// parent node
  94     node_base_ptr   left;   /// left child node or previous sibling if it's a leaf node.
  95     node_base_ptr   right;  /// right child node or next sibling if it's aleaf node.
  96     bool            is_leaf;
  97
  98     node_base(bool _is_leaf) :
  99         intrusive_ref_base(),
 100         parent(static_cast<node_base*>(NULL)),
 101         left(static_cast<node_base*>(NULL)),
 102         right(static_cast<node_base*>(NULL)),
 103         is_leaf(_is_leaf)
 104     {
 105 #ifdef DEBUG_NODE_BASE
 106         ++node_instance_count;
 107 #endif
 108     }
 109
 110     virtual ~node_base()
 111     {
 112 #ifdef DEBUG_NODE_BASE
 113         --node_instance_count;
 114 #endif
 115     }
 116
 117     // These methods are specific to concrete class implementation.
 118
 119     virtual void fill_nonleaf_value(const node_base_ptr& left_node, const node_base_ptr& right_node) = 0;
 120     virtual void dump_value() const = 0;
 121     virtual node_base* create_new(bool leaf) const = 0;
 122 };
 123
 124 template<typename _NodePtr>
 125 void disconnect_node(_NodePtr p)
 126 {
 127     if (!p)
 128         return;
 129
 130     p->left.reset();
 131     p->right.reset();
 132     p->parent.reset();
 133 }
 134
 135 template<typename _NodePtr>
 136 void link_nodes(_NodePtr& left, _NodePtr& right)
 137 {
 138     left->right = right;
 139     right->left = left;
 140 }
 141
 142 /**
 143  * Disconnect all non-leaf nodes so that their ref-counted instances will
 144  * all get destroyed afterwards.
 145  */
 146 template<typename _NodePtr>
 147 void clear_tree(const _NodePtr& node)
 148 {
 149     if (!node)
 150         // Nothing to do.
 151         return;
 152
 153     if (node->is_leaf)
 154     {
 155         node->parent.reset();
 156         return;
 157     }
 158
 159     clear_tree(node->left);
 160     clear_tree(node->right);
 161     disconnect_node(node.get());
 162 }
 163
 164 template<typename _NodePtr>
 165 _NodePtr make_parent_node(const _NodePtr& node1, const _NodePtr& node2)
 166 {
 167     _NodePtr parent_node(node1->create_new(false));
 168     node1->parent = parent_node;
 169     parent_node->left = node1;
 170     if (node2)
 171     {
 172         node2->parent = parent_node;
 173         parent_node->right = node2;
 174     }
 175
 176     parent_node->fill_nonleaf_value(node1, node2);
 177     return parent_node;
 178 }
 179
 180 template<typename _NodePtr>
 181 _NodePtr build_tree(const _NodePtr& left_leaf_node)
 182 {
 183     if (!left_leaf_node)
 184         // The left leaf node is empty.  Nothing to build.
 185         return _NodePtr();
 186
 187     _NodePtr node1, node2;
 188     node1 = left_leaf_node;
 189
 190     ::std::list<_NodePtr> node_list;
 191     while (true)
 192     {
 193         node2 = node1->right;
 194         _NodePtr parent_node = make_parent_node(node1, node2);
 195         node_list.push_back(parent_node);
 196
 197         if (!node2 || !node2->right)
 198             // no more nodes.  Break out of the loop.
 199             break;
 200
 201         node1 = node2->right;
 202     }
 203
 204     return build_tree_non_leaf(node_list);
 205 }
 206
 207 template<typename _NodePtr>
 208 _NodePtr build_tree_non_leaf(const ::std::list<_NodePtr>& node_list)
 209 {
 210     size_t node_count = node_list.size();
 211     if (node_count == 1)
 212     {
 213         return node_list.front();
 214     }
 215     else if (node_count == 0)
 216         return _NodePtr();
 217
 218     ::std::list<_NodePtr> new_node_list;
 219     _NodePtr node_pair[2];
 220     typename ::std::list<_NodePtr>::const_iterator itr    = node_list.begin();
 221     typename ::std::list<_NodePtr>::const_iterator itrEnd = node_list.end();
 222     for (bool even_itr = false; itr != itrEnd; ++itr, even_itr = !even_itr)
 223     {
 224         node_pair[even_itr] = *itr;
 225         if (even_itr)
 226         {
 227             _NodePtr parent_node = make_parent_node(node_pair[0], node_pair[1]);
 228             node_pair[0].reset();
 229             node_pair[1].reset();
 230             new_node_list.push_back(parent_node);
 231         }
 232     }
 233
 234     if (node_pair[0])
 235     {
 236         // Un-paired node still needs a parent...
 237         _NodePtr parent_node = make_parent_node(node_pair[0], _NodePtr());
 238         node_pair[0].reset();
 239         node_pair[1].reset();
 240         new_node_list.push_back(parent_node);
 241     }
 242
 243     // Move up one level, and do the same procedure until the root node is reached.
 244     return build_tree_non_leaf(new_node_list);
 245 }
 246
 247 #ifdef UNIT_TEST
 248 template<typename _NodePtr>
 249 size_t dump_tree_layer(const ::std::list<_NodePtr>& node_list, unsigned int level)
 250 {
 251     using ::std::cout;
 252     using ::std::endl;
 253
 254     if (node_list.empty())
 255         return 0;
 256
 257     size_t node_count = node_list.size();
 258
 259     bool isLeaf = node_list.front()->is_leaf;
 260     cout << "level " << level << " (" << (isLeaf?"leaf":"non-leaf") << ")" << endl;
 261
 262     ::std::list<_NodePtr> newList;
 263     typename ::std::list<_NodePtr>::const_iterator itr = node_list.begin(), itrEnd = node_list.end();
 264     for (; itr != itrEnd; ++itr)
 265     {
 266         const _NodePtr& p = *itr;
 267         if (!p)
 268         {
 269             cout << "(x) ";
 270             continue;
 271         }
 272
 273         p->dump_value();
 274
 275         if (p->is_leaf)
 276             continue;
 277
 278         if (p->left)
 279         {
 280             newList.push_back(p->left);
 281             if (p->right)
 282                 newList.push_back(p->right);
 283         }
 284     }
 285     cout << endl;
 286
 287     if (!newList.empty())
 288         node_count += dump_tree_layer(newList, level+1);
 289
 290     return node_count;
 291 }
 292
 293 template<typename _NodePtr>
 294 size_t dump_tree(const _NodePtr& root_node)
 295 {
 296     if (!root_node)
 297         return 0;
 298
 299     ::std::list<_NodePtr> node_list;
 300     node_list.push_back(root_node);
 301     return dump_tree_layer(node_list, 0);
 302 }
 303 #endif
 304
 305 }
 306
 307 #endif