boost/heap/detail/heap_node.hpp

   1 // boost heap: heap node helper classes
   2 //
   3 // Copyright (C) 2010 Tim Blechmann
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_HEAP_DETAIL_HEAP_NODE_HPP
  10 #define BOOST_HEAP_DETAIL_HEAP_NODE_HPP
  11
  12 #include <boost/assert.hpp>
  13 #include <boost/static_assert.hpp>
  14 #include <boost/intrusive/list.hpp>
  15 #include <boost/mpl/if.hpp>
  16
  17 #ifdef BOOST_HEAP_SANITYCHECKS
  18 #define BOOST_HEAP_ASSERT BOOST_ASSERT
  19 #else
  20 #define BOOST_HEAP_ASSERT(expression)
  21 #endif
  22
  23
  24 namespace boost  {
  25 namespace heap   {
  26 namespace detail {
  27
  28 namespace bi = boost::intrusive;
  29 namespace mpl = boost::mpl;
  30
  31 template <bool auto_unlink = false>
  32 struct heap_node_base:
  33     bi::list_base_hook<typename mpl::if_c<auto_unlink,
  34                                           bi::link_mode<bi::auto_unlink>,
  35                                           bi::link_mode<bi::safe_link>
  36                                          >::type
  37                       >
  38 {};
  39
  40 typedef bi::list<heap_node_base<false> > heap_node_list;
  41
  42 struct nop_disposer
  43 {
  44     template <typename T>
  45     void operator()(T * n)
  46     {
  47         BOOST_HEAP_ASSERT(false);
  48     }
  49 };
  50
  51 template <typename Node, typename HeapBase>
  52 bool is_heap(const Node * n, typename HeapBase::value_compare const & cmp)
  53 {
  54     for (typename Node::const_child_iterator it = n->children.begin(); it != n->children.end(); ++it) {
  55         Node const & this_node = static_cast<Node const &>(*it);
  56         const Node * child = static_cast<const Node*>(&this_node);
  57
  58         if (cmp(HeapBase::get_value(n->value), HeapBase::get_value(child->value)) ||
  59             !is_heap<Node, HeapBase>(child, cmp))
  60             return false;
  61     }
  62     return true;
  63 }
  64
  65 template <typename Node>
  66 std::size_t count_nodes(const Node * n);
  67
  68 template <typename Node, typename List>
  69 std::size_t count_list_nodes(List const & node_list)
  70 {
  71     std::size_t ret = 0;
  72
  73     for (typename List::const_iterator it = node_list.begin(); it != node_list.end(); ++it) {
  74         const Node * child = static_cast<const Node*>(&*it);
  75         ret += count_nodes<Node>(child);
  76     }
  77     return ret;
  78 }
  79
  80 template <typename Node>
  81 std::size_t count_nodes(const Node * n)
  82 {
  83     return 1 + count_list_nodes<Node, typename Node::child_list>(n->children);
  84 }
  85
  86
  87 /* node cloner
  88  *
  89  * Requires `Clone Constructor':
  90  * template <typename Alloc>
  91  * Node::Node(Node const &, Alloc &)
  92  *
  93  * template <typename Alloc>
  94  * Node::Node(Node const &, Alloc &, Node * parent)
  95  *
  96  * */
  97 template <typename Node,
  98           typename NodeBase,
  99           typename Alloc>
 100 struct node_cloner
 101 {
 102     node_cloner(Alloc & allocator):
 103         allocator(allocator)
 104     {}
 105
 106     Node * operator() (NodeBase const & node)
 107     {
 108         Node * ret = allocator.allocate(1);
 109         new (ret) Node(static_cast<Node const &>(node), allocator);
 110         return ret;
 111     }
 112
 113     Node * operator() (NodeBase const & node, Node * parent)
 114     {
 115         Node * ret = allocator.allocate(1);
 116         new (ret) Node(static_cast<Node const &>(node), allocator, parent);
 117         return ret;
 118     }
 119
 120 private:
 121     Alloc & allocator;
 122 };
 123
 124 /* node disposer
 125  *
 126  * Requirements:
 127  * Node::clear_subtree(Alloc &) clears the subtree via allocator
 128  *
 129  * */
 130 template <typename Node,
 131           typename NodeBase,
 132           typename Alloc>
 133 struct node_disposer
 134 {
 135     typedef typename Alloc::pointer node_pointer;
 136
 137     node_disposer(Alloc & alloc):
 138         alloc_(alloc)
 139     {}
 140
 141     void operator()(NodeBase * base)
 142     {
 143         node_pointer n = static_cast<node_pointer>(base);
 144         n->clear_subtree(alloc_);
 145         alloc_.destroy(n);
 146         alloc_.deallocate(n, 1);
 147     }
 148
 149     Alloc & alloc_;
 150 };
 151
 152
 153 template <typename ValueType,
 154           bool constant_time_child_size = true
 155          >
 156 struct heap_node:
 157     heap_node_base<!constant_time_child_size>
 158 {
 159     typedef heap_node_base<!constant_time_child_size> node_base;
 160
 161 public:
 162     typedef ValueType value_type;
 163
 164     typedef bi::list<node_base,
 165                      bi::constant_time_size<constant_time_child_size> > child_list;
 166
 167     typedef typename child_list::iterator child_iterator;
 168     typedef typename child_list::const_iterator const_child_iterator;
 169     typedef typename child_list::size_type size_type;
 170
 171     heap_node(ValueType const & v):
 172         value(v)
 173     {}
 174
 175 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 176     template <class... Args>
 177     heap_node(Args&&... args):
 178         value(std::forward<Args>(args)...)
 179     {}
 180 #endif
 181
 182 /* protected:                      */
 183     heap_node(heap_node const & rhs):
 184         value(rhs.value)
 185     {
 186         /* we don't copy the child list, but clone it later */
 187     }
 188
 189 public:
 190
 191     template <typename Alloc>
 192     heap_node (heap_node const & rhs, Alloc & allocator):
 193         value(rhs.value)
 194     {
 195         children.clone_from(rhs.children, node_cloner<heap_node, node_base, Alloc>(allocator), nop_disposer());
 196     }
 197
 198     size_type child_count(void) const
 199     {
 200         BOOST_STATIC_ASSERT(constant_time_child_size);
 201         return children.size();
 202     }
 203
 204     void add_child(heap_node * n)
 205     {
 206         children.push_back(*n);
 207     }
 208
 209     template <typename Alloc>
 210     void clear_subtree(Alloc & alloc)
 211     {
 212         children.clear_and_dispose(node_disposer<heap_node, node_base, Alloc>(alloc));
 213     }
 214
 215     void swap_children(heap_node * rhs)
 216     {
 217         children.swap(rhs->children);
 218     }
 219
 220     ValueType value;
 221     child_list children;
 222 };
 223
 224 template <typename value_type>
 225 struct parent_pointing_heap_node:
 226     heap_node<value_type>
 227 {
 228     typedef heap_node<value_type> super_t;
 229
 230     parent_pointing_heap_node(value_type const & v):
 231         super_t(v), parent(NULL)
 232     {}
 233
 234 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 235     template <class... Args>
 236     parent_pointing_heap_node(Args&&... args):
 237         super_t(std::forward<Args>(args)...), parent(NULL)
 238     {}
 239 #endif
 240
 241     template <typename Alloc>
 242     struct node_cloner
 243     {
 244         node_cloner(Alloc & allocator, parent_pointing_heap_node * parent):
 245             allocator(allocator), parent_(parent)
 246         {}
 247
 248         parent_pointing_heap_node * operator() (typename super_t::node_base const & node)
 249         {
 250             parent_pointing_heap_node * ret = allocator.allocate(1);
 251             new (ret) parent_pointing_heap_node(static_cast<parent_pointing_heap_node const &>(node), allocator, parent_);
 252             return ret;
 253         }
 254
 255     private:
 256         Alloc & allocator;
 257         parent_pointing_heap_node * parent_;
 258     };
 259
 260     template <typename Alloc>
 261     parent_pointing_heap_node (parent_pointing_heap_node const & rhs, Alloc & allocator, parent_pointing_heap_node * parent):
 262         super_t(static_cast<super_t const &>(rhs)), parent(parent)
 263     {
 264         super_t::children.clone_from(rhs.children, node_cloner<Alloc>(allocator, this), nop_disposer());
 265     }
 266
 267     void update_children(void)
 268     {
 269         typedef heap_node_list::iterator node_list_iterator;
 270         for (node_list_iterator it = super_t::children.begin(); it != super_t::children.end(); ++it) {
 271             parent_pointing_heap_node * child = static_cast<parent_pointing_heap_node*>(&*it);
 272             child->parent = this;
 273         }
 274     }
 275
 276     void remove_from_parent(void)
 277     {
 278         BOOST_HEAP_ASSERT(parent);
 279         parent->children.erase(heap_node_list::s_iterator_to(*this));
 280         parent = NULL;
 281     }
 282
 283     void add_child(parent_pointing_heap_node * n)
 284     {
 285         BOOST_HEAP_ASSERT(n->parent == NULL);
 286         n->parent = this;
 287         super_t::add_child(n);
 288     }
 289
 290     parent_pointing_heap_node * get_parent(void)
 291     {
 292         return parent;
 293     }
 294
 295     const parent_pointing_heap_node * get_parent(void) const
 296     {
 297         return parent;
 298     }
 299
 300     parent_pointing_heap_node * parent;
 301 };
 302
 303
 304 template <typename value_type>
 305 struct marked_heap_node:
 306     parent_pointing_heap_node<value_type>
 307 {
 308     typedef parent_pointing_heap_node<value_type> super_t;
 309
 310     marked_heap_node(value_type const & v):
 311         super_t(v), mark(false)
 312     {}
 313
 314 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 315     template <class... Args>
 316     marked_heap_node(Args&&... args):
 317         super_t(std::forward<Args>(args)...), mark(false)
 318     {}
 319 #endif
 320
 321     marked_heap_node * get_parent(void)
 322     {
 323         return static_cast<marked_heap_node*>(super_t::parent);
 324     }
 325
 326     const marked_heap_node * get_parent(void) const
 327     {
 328         return static_cast<marked_heap_node*>(super_t::parent);
 329     }
 330
 331     bool mark;
 332 };
 333
 334
 335 template <typename Node>
 336 struct cmp_by_degree
 337 {
 338     template <typename NodeBase>
 339     bool operator()(NodeBase const & left,
 340                     NodeBase const & right)
 341     {
 342         return static_cast<const Node*>(&left)->child_count() < static_cast<const Node*>(&right)->child_count();
 343     }
 344 };
 345
 346 template <typename List, typename Node, typename Cmp>
 347 Node * find_max_child(List const & list, Cmp const & cmp)
 348 {
 349     BOOST_HEAP_ASSERT(!list.empty());
 350
 351     const Node * ret = static_cast<const Node *> (&list.front());
 352     for (typename List::const_iterator it = list.begin(); it != list.end(); ++it) {
 353         const Node * current = static_cast<const Node *> (&*it);
 354
 355         if (cmp(ret->value, current->value))
 356             ret = current;
 357     }
 358
 359     return const_cast<Node*>(ret);
 360 }
 361
 362 } /* namespace detail */
 363 } /* namespace heap */
 364 } /* namespace boost */
 365
 366 #undef BOOST_HEAP_ASSERT
 367 #endif /* BOOST_HEAP_DETAIL_HEAP_NODE_HPP */