heap/detail/heap_node.hpp

0001 // boost heap: heap node helper classes
0002 //
0003 // Copyright (C) 2010 Tim Blechmann
0004 //
0005 // Distributed under the Boost Software License, Version 1.0. (See
0006 // accompanying file LICENSE_1_0.txt or copy at
0007 // http://www.boost.org/LICENSE_1_0.txt)
0008
0009 #ifndef BOOST_HEAP_DETAIL_HEAP_NODE_HPP
0010 #define BOOST_HEAP_DETAIL_HEAP_NODE_HPP
0011
0012 #include <boost/assert.hpp>
0013 #include <boost/static_assert.hpp>
0014 #include <boost/core/allocator_access.hpp>
0015 #include <boost/intrusive/list.hpp>
0016 #include <boost/type_traits/conditional.hpp>
0017
0018 #ifdef BOOST_HEAP_SANITYCHECKS
0019 #define BOOST_HEAP_ASSERT BOOST_ASSERT
0020 #else
0021 #define BOOST_HEAP_ASSERT(expression)
0022 #endif
0023
0024
0025 namespace boost  {
0026 namespace heap   {
0027 namespace detail {
0028
0029 namespace bi = boost::intrusive;
0030
0031 template <bool auto_unlink = false>
0032 struct heap_node_base:
0033     bi::list_base_hook<typename boost::conditional<auto_unlink,
0034                                           bi::link_mode<bi::auto_unlink>,
0035                                           bi::link_mode<bi::safe_link>
0036                                          >::type
0037                       >
0038 {};
0039
0040 typedef bi::list<heap_node_base<false> > heap_node_list;
0041
0042 struct nop_disposer
0043 {
0044     template <typename T>
0045     void operator()(T * n)
0046     {
0047         BOOST_HEAP_ASSERT(false);
0048     }
0049 };
0050
0051 template <typename Node, typename HeapBase>
0052 bool is_heap(const Node * n, typename HeapBase::value_compare const & cmp)
0053 {
0054     for (typename Node::const_child_iterator it = n->children.begin(); it != n->children.end(); ++it) {
0055         Node const & this_node = static_cast<Node const &>(*it);
0056         const Node * child = static_cast<const Node*>(&this_node);
0057
0058         if (cmp(HeapBase::get_value(n->value), HeapBase::get_value(child->value)) ||
0059             !is_heap<Node, HeapBase>(child, cmp))
0060             return false;
0061     }
0062     return true;
0063 }
0064
0065 template <typename Node>
0066 std::size_t count_nodes(const Node * n);
0067
0068 template <typename Node, typename List>
0069 std::size_t count_list_nodes(List const & node_list)
0070 {
0071     std::size_t ret = 0;
0072
0073     for (typename List::const_iterator it = node_list.begin(); it != node_list.end(); ++it) {
0074         const Node * child = static_cast<const Node*>(&*it);
0075         ret += count_nodes<Node>(child);
0076     }
0077     return ret;
0078 }
0079
0080 template <typename Node>
0081 std::size_t count_nodes(const Node * n)
0082 {
0083     return 1 + count_list_nodes<Node, typename Node::child_list>(n->children);
0084 }
0085
0086 template<class Node>
0087 void destroy_node(Node& node)
0088 {
0089     node.~Node();
0090 }
0091
0092
0093 /* node cloner
0094  *
0095  * Requires `Clone Constructor':
0096  * template <typename Alloc>
0097  * Node::Node(Node const &, Alloc &)
0098  *
0099  * template <typename Alloc>
0100  * Node::Node(Node const &, Alloc &, Node * parent)
0101  *
0102  * */
0103 template <typename Node,
0104           typename NodeBase,
0105           typename Alloc>
0106 struct node_cloner
0107 {
0108     node_cloner(Alloc & allocator):
0109         allocator(allocator)
0110     {}
0111
0112     Node * operator() (NodeBase const & node)
0113     {
0114         Node * ret = allocator.allocate(1);
0115         new (ret) Node(static_cast<Node const &>(node), allocator);
0116         return ret;
0117     }
0118
0119     Node * operator() (NodeBase const & node, Node * parent)
0120     {
0121         Node * ret = allocator.allocate(1);
0122         new (ret) Node(static_cast<Node const &>(node), allocator, parent);
0123         return ret;
0124     }
0125
0126 private:
0127     Alloc & allocator;
0128 };
0129
0130 /* node disposer
0131  *
0132  * Requirements:
0133  * Node::clear_subtree(Alloc &) clears the subtree via allocator
0134  *
0135  * */
0136 template <typename Node,
0137           typename NodeBase,
0138           typename Alloc>
0139 struct node_disposer
0140 {
0141     typedef typename boost::allocator_pointer<Alloc>::type node_pointer;
0142
0143     node_disposer(Alloc & alloc):
0144         alloc_(alloc)
0145     {}
0146
0147     void operator()(NodeBase * base)
0148     {
0149         node_pointer n = static_cast<node_pointer>(base);
0150         n->clear_subtree(alloc_);
0151         boost::heap::detail::destroy_node(*n);
0152         alloc_.deallocate(n, 1);
0153     }
0154
0155     Alloc & alloc_;
0156 };
0157
0158
0159 template <typename ValueType,
0160           bool constant_time_child_size = true
0161          >
0162 struct heap_node:
0163     heap_node_base<!constant_time_child_size>
0164 {
0165     typedef heap_node_base<!constant_time_child_size> node_base;
0166
0167 public:
0168     typedef ValueType value_type;
0169
0170     typedef bi::list<node_base,
0171                      bi::constant_time_size<constant_time_child_size> > child_list;
0172
0173     typedef typename child_list::iterator child_iterator;
0174     typedef typename child_list::const_iterator const_child_iterator;
0175     typedef typename child_list::size_type size_type;
0176
0177     heap_node(ValueType const & v):
0178         value(v)
0179     {}
0180
0181 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0182     template <class... Args>
0183     heap_node(Args&&... args):
0184         value(std::forward<Args>(args)...)
0185     {}
0186 #endif
0187
0188 /* protected:                      */
0189     heap_node(heap_node const & rhs):
0190         value(rhs.value)
0191     {
0192         /* we don't copy the child list, but clone it later */
0193     }
0194
0195 public:
0196
0197     template <typename Alloc>
0198     heap_node (heap_node const & rhs, Alloc & allocator):
0199         value(rhs.value)
0200     {
0201         children.clone_from(rhs.children, node_cloner<heap_node, node_base, Alloc>(allocator), nop_disposer());
0202     }
0203
0204     size_type child_count(void) const
0205     {
0206         BOOST_STATIC_ASSERT(constant_time_child_size);
0207         return children.size();
0208     }
0209
0210     void add_child(heap_node * n)
0211     {
0212         children.push_back(*n);
0213     }
0214
0215     template <typename Alloc>
0216     void clear_subtree(Alloc & alloc)
0217     {
0218         children.clear_and_dispose(node_disposer<heap_node, node_base, Alloc>(alloc));
0219     }
0220
0221     void swap_children(heap_node * rhs)
0222     {
0223         children.swap(rhs->children);
0224     }
0225
0226     ValueType value;
0227     child_list children;
0228 };
0229
0230 template <typename value_type>
0231 struct parent_pointing_heap_node:
0232     heap_node<value_type>
0233 {
0234     typedef heap_node<value_type> super_t;
0235
0236     parent_pointing_heap_node(value_type const & v):
0237         super_t(v), parent(NULL)
0238     {}
0239
0240 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0241     template <class... Args>
0242     parent_pointing_heap_node(Args&&... args):
0243         super_t(std::forward<Args>(args)...), parent(NULL)
0244     {}
0245 #endif
0246
0247     template <typename Alloc>
0248     struct node_cloner
0249     {
0250         node_cloner(Alloc & allocator, parent_pointing_heap_node * parent):
0251             allocator(allocator), parent_(parent)
0252         {}
0253
0254         parent_pointing_heap_node * operator() (typename super_t::node_base const & node)
0255         {
0256             parent_pointing_heap_node * ret = allocator.allocate(1);
0257             new (ret) parent_pointing_heap_node(static_cast<parent_pointing_heap_node const &>(node), allocator, parent_);
0258             return ret;
0259         }
0260
0261     private:
0262         Alloc & allocator;
0263         parent_pointing_heap_node * parent_;
0264     };
0265
0266     template <typename Alloc>
0267     parent_pointing_heap_node (parent_pointing_heap_node const & rhs, Alloc & allocator, parent_pointing_heap_node * parent):
0268         super_t(static_cast<super_t const &>(rhs)), parent(parent)
0269     {
0270         super_t::children.clone_from(rhs.children, node_cloner<Alloc>(allocator, this), nop_disposer());
0271     }
0272
0273     void update_children(void)
0274     {
0275         typedef heap_node_list::iterator node_list_iterator;
0276         for (node_list_iterator it = super_t::children.begin(); it != super_t::children.end(); ++it) {
0277             parent_pointing_heap_node * child = static_cast<parent_pointing_heap_node*>(&*it);
0278             child->parent = this;
0279         }
0280     }
0281
0282     void remove_from_parent(void)
0283     {
0284         BOOST_HEAP_ASSERT(parent);
0285         parent->children.erase(heap_node_list::s_iterator_to(*this));
0286         parent = NULL;
0287     }
0288
0289     void add_child(parent_pointing_heap_node * n)
0290     {
0291         BOOST_HEAP_ASSERT(n->parent == NULL);
0292         n->parent = this;
0293         super_t::add_child(n);
0294     }
0295
0296     parent_pointing_heap_node * get_parent(void)
0297     {
0298         return parent;
0299     }
0300
0301     const parent_pointing_heap_node * get_parent(void) const
0302     {
0303         return parent;
0304     }
0305
0306     parent_pointing_heap_node * parent;
0307 };
0308
0309
0310 template <typename value_type>
0311 struct marked_heap_node:
0312     parent_pointing_heap_node<value_type>
0313 {
0314     typedef parent_pointing_heap_node<value_type> super_t;
0315
0316     marked_heap_node(value_type const & v):
0317         super_t(v), mark(false)
0318     {}
0319
0320 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0321     template <class... Args>
0322     marked_heap_node(Args&&... args):
0323         super_t(std::forward<Args>(args)...), mark(false)
0324     {}
0325 #endif
0326
0327     marked_heap_node * get_parent(void)
0328     {
0329         return static_cast<marked_heap_node*>(super_t::parent);
0330     }
0331
0332     const marked_heap_node * get_parent(void) const
0333     {
0334         return static_cast<marked_heap_node*>(super_t::parent);
0335     }
0336
0337     bool mark;
0338 };
0339
0340
0341 template <typename Node>
0342 struct cmp_by_degree
0343 {
0344     template <typename NodeBase>
0345     bool operator()(NodeBase const & left,
0346                     NodeBase const & right)
0347     {
0348         return static_cast<const Node*>(&left)->child_count() < static_cast<const Node*>(&right)->child_count();
0349     }
0350 };
0351
0352 template <typename List, typename Node, typename Cmp>
0353 Node * find_max_child(List const & list, Cmp const & cmp)
0354 {
0355     BOOST_HEAP_ASSERT(!list.empty());
0356
0357     const Node * ret = static_cast<const Node *> (&list.front());
0358     for (typename List::const_iterator it = list.begin(); it != list.end(); ++it) {
0359         const Node * current = static_cast<const Node *> (&*it);
0360
0361         if (cmp(ret->value, current->value))
0362             ret = current;
0363     }
0364
0365     return const_cast<Node*>(ret);
0366 }
0367
0368 } /* namespace detail */
0369 } /* namespace heap */
0370 } /* namespace boost */
0371
0372 #undef BOOST_HEAP_ASSERT
0373 #endif /* BOOST_HEAP_DETAIL_HEAP_NODE_HPP */