Chris@16: // boost heap: heap node helper classes
Chris@16: //
Chris@16: // Copyright (C) 2010 Tim Blechmann
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_HEAP_DETAIL_HEAP_NODE_HPP
Chris@16: #define BOOST_HEAP_DETAIL_HEAP_NODE_HPP
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/static_assert.hpp>
Chris@16: #include <boost/intrusive/list.hpp>
Chris@16: #include <boost/mpl/if.hpp>
Chris@16: 
Chris@16: #ifdef BOOST_HEAP_SANITYCHECKS
Chris@16: #define BOOST_HEAP_ASSERT BOOST_ASSERT
Chris@16: #else
Chris@16: #define BOOST_HEAP_ASSERT(expression)
Chris@16: #endif
Chris@16: 
Chris@16: 
Chris@16: namespace boost  {
Chris@16: namespace heap   {
Chris@16: namespace detail {
Chris@16: 
Chris@16: namespace bi = boost::intrusive;
Chris@16: namespace mpl = boost::mpl;
Chris@16: 
Chris@16: template <bool auto_unlink = false>
Chris@16: struct heap_node_base:
Chris@16:     bi::list_base_hook<typename mpl::if_c<auto_unlink,
Chris@16:                                           bi::link_mode<bi::auto_unlink>,
Chris@16:                                           bi::link_mode<bi::safe_link>
Chris@16:                                          >::type
Chris@16:                       >
Chris@16: {};
Chris@16: 
Chris@16: typedef bi::list<heap_node_base<false> > heap_node_list;
Chris@16: 
Chris@16: struct nop_disposer
Chris@16: {
Chris@16:     template <typename T>
Chris@16:     void operator()(T * n)
Chris@16:     {
Chris@16:         BOOST_HEAP_ASSERT(false);
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename Node, typename HeapBase>
Chris@16: bool is_heap(const Node * n, typename HeapBase::value_compare const & cmp)
Chris@16: {
Chris@16:     for (typename Node::const_child_iterator it = n->children.begin(); it != n->children.end(); ++it) {
Chris@16:         Node const & this_node = static_cast<Node const &>(*it);
Chris@16:         const Node * child = static_cast<const Node*>(&this_node);
Chris@16: 
Chris@16:         if (cmp(HeapBase::get_value(n->value), HeapBase::get_value(child->value)) ||
Chris@16:             !is_heap<Node, HeapBase>(child, cmp))
Chris@16:             return false;
Chris@16:     }
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: template <typename Node>
Chris@16: std::size_t count_nodes(const Node * n);
Chris@16: 
Chris@16: template <typename Node, typename List>
Chris@16: std::size_t count_list_nodes(List const & node_list)
Chris@16: {
Chris@16:     std::size_t ret = 0;
Chris@16: 
Chris@16:     for (typename List::const_iterator it = node_list.begin(); it != node_list.end(); ++it) {
Chris@16:         const Node * child = static_cast<const Node*>(&*it);
Chris@16:         ret += count_nodes<Node>(child);
Chris@16:     }
Chris@16:     return ret;
Chris@16: }
Chris@16: 
Chris@16: template <typename Node>
Chris@16: std::size_t count_nodes(const Node * n)
Chris@16: {
Chris@16:     return 1 + count_list_nodes<Node, typename Node::child_list>(n->children);
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: /* node cloner
Chris@16:  *
Chris@16:  * Requires `Clone Constructor':
Chris@16:  * template <typename Alloc>
Chris@16:  * Node::Node(Node const &, Alloc &)
Chris@16:  *
Chris@16:  * template <typename Alloc>
Chris@16:  * Node::Node(Node const &, Alloc &, Node * parent)
Chris@16:  *
Chris@16:  * */
Chris@16: template <typename Node,
Chris@16:           typename NodeBase,
Chris@16:           typename Alloc>
Chris@16: struct node_cloner
Chris@16: {
Chris@16:     node_cloner(Alloc & allocator):
Chris@16:         allocator(allocator)
Chris@16:     {}
Chris@16: 
Chris@16:     Node * operator() (NodeBase const & node)
Chris@16:     {
Chris@16:         Node * ret = allocator.allocate(1);
Chris@16:         new (ret) Node(static_cast<Node const &>(node), allocator);
Chris@16:         return ret;
Chris@16:     }
Chris@16: 
Chris@16:     Node * operator() (NodeBase const & node, Node * parent)
Chris@16:     {
Chris@16:         Node * ret = allocator.allocate(1);
Chris@16:         new (ret) Node(static_cast<Node const &>(node), allocator, parent);
Chris@16:         return ret;
Chris@16:     }
Chris@16: 
Chris@16: private:
Chris@16:     Alloc & allocator;
Chris@16: };
Chris@16: 
Chris@16: /* node disposer
Chris@16:  *
Chris@16:  * Requirements:
Chris@16:  * Node::clear_subtree(Alloc &) clears the subtree via allocator
Chris@16:  *
Chris@16:  * */
Chris@16: template <typename Node,
Chris@16:           typename NodeBase,
Chris@16:           typename Alloc>
Chris@16: struct node_disposer
Chris@16: {
Chris@16:     typedef typename Alloc::pointer node_pointer;
Chris@16: 
Chris@16:     node_disposer(Alloc & alloc):
Chris@16:         alloc_(alloc)
Chris@16:     {}
Chris@16: 
Chris@16:     void operator()(NodeBase * base)
Chris@16:     {
Chris@16:         node_pointer n = static_cast<node_pointer>(base);
Chris@16:         n->clear_subtree(alloc_);
Chris@16:         alloc_.destroy(n);
Chris@16:         alloc_.deallocate(n, 1);
Chris@16:     }
Chris@16: 
Chris@16:     Alloc & alloc_;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename ValueType,
Chris@16:           bool constant_time_child_size = true
Chris@16:          >
Chris@16: struct heap_node:
Chris@16:     heap_node_base<!constant_time_child_size>
Chris@16: {
Chris@16:     typedef heap_node_base<!constant_time_child_size> node_base;
Chris@16: 
Chris@16: public:
Chris@16:     typedef ValueType value_type;
Chris@16: 
Chris@16:     typedef bi::list<node_base,
Chris@16:                      bi::constant_time_size<constant_time_child_size> > child_list;
Chris@16: 
Chris@16:     typedef typename child_list::iterator child_iterator;
Chris@16:     typedef typename child_list::const_iterator const_child_iterator;
Chris@16:     typedef typename child_list::size_type size_type;
Chris@16: 
Chris@16:     heap_node(ValueType const & v):
Chris@16:         value(v)
Chris@16:     {}
Chris@16: 
Chris@16: #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16:     template <class... Args>
Chris@16:     heap_node(Args&&... args):
Chris@16:         value(std::forward<Args>(args)...)
Chris@16:     {}
Chris@16: #endif
Chris@16: 
Chris@16: /* protected:                      */
Chris@16:     heap_node(heap_node const & rhs):
Chris@16:         value(rhs.value)
Chris@16:     {
Chris@16:         /* we don't copy the child list, but clone it later */
Chris@16:     }
Chris@16: 
Chris@16: public:
Chris@16: 
Chris@16:     template <typename Alloc>
Chris@16:     heap_node (heap_node const & rhs, Alloc & allocator):
Chris@16:         value(rhs.value)
Chris@16:     {
Chris@16:         children.clone_from(rhs.children, node_cloner<heap_node, node_base, Alloc>(allocator), nop_disposer());
Chris@16:     }
Chris@16: 
Chris@16:     size_type child_count(void) const
Chris@16:     {
Chris@16:         BOOST_STATIC_ASSERT(constant_time_child_size);
Chris@16:         return children.size();
Chris@16:     }
Chris@16: 
Chris@16:     void add_child(heap_node * n)
Chris@16:     {
Chris@16:         children.push_back(*n);
Chris@16:     }
Chris@16: 
Chris@16:     template <typename Alloc>
Chris@16:     void clear_subtree(Alloc & alloc)
Chris@16:     {
Chris@16:         children.clear_and_dispose(node_disposer<heap_node, node_base, Alloc>(alloc));
Chris@16:     }
Chris@16: 
Chris@16:     void swap_children(heap_node * rhs)
Chris@16:     {
Chris@16:         children.swap(rhs->children);
Chris@16:     }
Chris@16: 
Chris@16:     ValueType value;
Chris@16:     child_list children;
Chris@16: };
Chris@16: 
Chris@16: template <typename value_type>
Chris@16: struct parent_pointing_heap_node:
Chris@16:     heap_node<value_type>
Chris@16: {
Chris@16:     typedef heap_node<value_type> super_t;
Chris@16: 
Chris@16:     parent_pointing_heap_node(value_type const & v):
Chris@16:         super_t(v), parent(NULL)
Chris@16:     {}
Chris@16: 
Chris@16: #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16:     template <class... Args>
Chris@16:     parent_pointing_heap_node(Args&&... args):
Chris@16:         super_t(std::forward<Args>(args)...), parent(NULL)
Chris@16:     {}
Chris@16: #endif
Chris@16: 
Chris@16:     template <typename Alloc>
Chris@16:     struct node_cloner
Chris@16:     {
Chris@16:         node_cloner(Alloc & allocator, parent_pointing_heap_node * parent):
Chris@16:             allocator(allocator), parent_(parent)
Chris@16:         {}
Chris@16: 
Chris@16:         parent_pointing_heap_node * operator() (typename super_t::node_base const & node)
Chris@16:         {
Chris@16:             parent_pointing_heap_node * ret = allocator.allocate(1);
Chris@16:             new (ret) parent_pointing_heap_node(static_cast<parent_pointing_heap_node const &>(node), allocator, parent_);
Chris@16:             return ret;
Chris@16:         }
Chris@16: 
Chris@16:     private:
Chris@16:         Alloc & allocator;
Chris@16:         parent_pointing_heap_node * parent_;
Chris@16:     };
Chris@16: 
Chris@16:     template <typename Alloc>
Chris@16:     parent_pointing_heap_node (parent_pointing_heap_node const & rhs, Alloc & allocator, parent_pointing_heap_node * parent):
Chris@16:         super_t(static_cast<super_t const &>(rhs)), parent(parent)
Chris@16:     {
Chris@16:         super_t::children.clone_from(rhs.children, node_cloner<Alloc>(allocator, this), nop_disposer());
Chris@16:     }
Chris@16: 
Chris@16:     void update_children(void)
Chris@16:     {
Chris@16:         typedef heap_node_list::iterator node_list_iterator;
Chris@16:         for (node_list_iterator it = super_t::children.begin(); it != super_t::children.end(); ++it) {
Chris@16:             parent_pointing_heap_node * child = static_cast<parent_pointing_heap_node*>(&*it);
Chris@16:             child->parent = this;
Chris@16:         }
Chris@16:     }
Chris@16: 
Chris@16:     void remove_from_parent(void)
Chris@16:     {
Chris@16:         BOOST_HEAP_ASSERT(parent);
Chris@16:         parent->children.erase(heap_node_list::s_iterator_to(*this));
Chris@16:         parent = NULL;
Chris@16:     }
Chris@16: 
Chris@16:     void add_child(parent_pointing_heap_node * n)
Chris@16:     {
Chris@16:         BOOST_HEAP_ASSERT(n->parent == NULL);
Chris@16:         n->parent = this;
Chris@16:         super_t::add_child(n);
Chris@16:     }
Chris@16: 
Chris@16:     parent_pointing_heap_node * get_parent(void)
Chris@16:     {
Chris@16:         return parent;
Chris@16:     }
Chris@16: 
Chris@16:     const parent_pointing_heap_node * get_parent(void) const
Chris@16:     {
Chris@16:         return parent;
Chris@16:     }
Chris@16: 
Chris@16:     parent_pointing_heap_node * parent;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename value_type>
Chris@16: struct marked_heap_node:
Chris@16:     parent_pointing_heap_node<value_type>
Chris@16: {
Chris@16:     typedef parent_pointing_heap_node<value_type> super_t;
Chris@16: 
Chris@16:     marked_heap_node(value_type const & v):
Chris@16:         super_t(v), mark(false)
Chris@16:     {}
Chris@16: 
Chris@16: #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16:     template <class... Args>
Chris@16:     marked_heap_node(Args&&... args):
Chris@16:         super_t(std::forward<Args>(args)...), mark(false)
Chris@16:     {}
Chris@16: #endif
Chris@16: 
Chris@16:     marked_heap_node * get_parent(void)
Chris@16:     {
Chris@16:         return static_cast<marked_heap_node*>(super_t::parent);
Chris@16:     }
Chris@16: 
Chris@16:     const marked_heap_node * get_parent(void) const
Chris@16:     {
Chris@16:         return static_cast<marked_heap_node*>(super_t::parent);
Chris@16:     }
Chris@16: 
Chris@16:     bool mark;
Chris@16: };
Chris@16: 
Chris@16: 
Chris@16: template <typename Node>
Chris@16: struct cmp_by_degree
Chris@16: {
Chris@16:     template <typename NodeBase>
Chris@16:     bool operator()(NodeBase const & left,
Chris@16:                     NodeBase const & right)
Chris@16:     {
Chris@16:         return static_cast<const Node*>(&left)->child_count() < static_cast<const Node*>(&right)->child_count();
Chris@16:     }
Chris@16: };
Chris@16: 
Chris@16: template <typename List, typename Node, typename Cmp>
Chris@16: Node * find_max_child(List const & list, Cmp const & cmp)
Chris@16: {
Chris@16:     BOOST_HEAP_ASSERT(!list.empty());
Chris@16: 
Chris@16:     const Node * ret = static_cast<const Node *> (&list.front());
Chris@16:     for (typename List::const_iterator it = list.begin(); it != list.end(); ++it) {
Chris@16:         const Node * current = static_cast<const Node *> (&*it);
Chris@16: 
Chris@16:         if (cmp(ret->value, current->value))
Chris@16:             ret = current;
Chris@16:     }
Chris@16: 
Chris@16:     return const_cast<Node*>(ret);
Chris@16: }
Chris@16: 
Chris@16: } /* namespace detail */
Chris@16: } /* namespace heap */
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #undef BOOST_HEAP_ASSERT
Chris@16: #endif /* BOOST_HEAP_DETAIL_HEAP_NODE_HPP */