1 // boost heap: heap node helper classes
3 // Copyright (C) 2010 Tim Blechmann
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)
9 #ifndef BOOST_HEAP_DETAIL_HEAP_NODE_HPP
10 #define BOOST_HEAP_DETAIL_HEAP_NODE_HPP
12 #include <boost/assert.hpp>
13 #include <boost/static_assert.hpp>
14 #include <boost/intrusive/list.hpp>
15 #include <boost/mpl/if.hpp>
17 #ifdef BOOST_HEAP_SANITYCHECKS
18 #define BOOST_HEAP_ASSERT BOOST_ASSERT
20 #define BOOST_HEAP_ASSERT(expression)
28 namespace bi = boost::intrusive;
29 namespace mpl = boost::mpl;
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>
40 typedef bi::list<heap_node_base<false> > heap_node_list;
45 void operator()(T * n)
47 BOOST_HEAP_ASSERT(false);
51 template <typename Node, typename HeapBase>
52 bool is_heap(const Node * n, typename HeapBase::value_compare const & cmp)
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);
58 if (cmp(HeapBase::get_value(n->value), HeapBase::get_value(child->value)) ||
59 !is_heap<Node, HeapBase>(child, cmp))
65 template <typename Node>
66 std::size_t count_nodes(const Node * n);
68 template <typename Node, typename List>
69 std::size_t count_list_nodes(List const & node_list)
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);
80 template <typename Node>
81 std::size_t count_nodes(const Node * n)
83 return 1 + count_list_nodes<Node, typename Node::child_list>(n->children);
89 * Requires `Clone Constructor':
90 * template <typename Alloc>
91 * Node::Node(Node const &, Alloc &)
93 * template <typename Alloc>
94 * Node::Node(Node const &, Alloc &, Node * parent)
97 template <typename Node,
102 node_cloner(Alloc & allocator):
106 Node * operator() (NodeBase const & node)
108 Node * ret = allocator.allocate(1);
109 new (ret) Node(static_cast<Node const &>(node), allocator);
113 Node * operator() (NodeBase const & node, Node * parent)
115 Node * ret = allocator.allocate(1);
116 new (ret) Node(static_cast<Node const &>(node), allocator, parent);
127 * Node::clear_subtree(Alloc &) clears the subtree via allocator
130 template <typename Node,
135 typedef typename Alloc::pointer node_pointer;
137 node_disposer(Alloc & alloc):
141 void operator()(NodeBase * base)
143 node_pointer n = static_cast<node_pointer>(base);
144 n->clear_subtree(alloc_);
146 alloc_.deallocate(n, 1);
153 template <typename ValueType,
154 bool constant_time_child_size = true
157 heap_node_base<!constant_time_child_size>
159 typedef heap_node_base<!constant_time_child_size> node_base;
162 typedef ValueType value_type;
164 typedef bi::list<node_base,
165 bi::constant_time_size<constant_time_child_size> > child_list;
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;
171 heap_node(ValueType const & v):
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)...)
183 heap_node(heap_node const & rhs):
186 /* we don't copy the child list, but clone it later */
191 template <typename Alloc>
192 heap_node (heap_node const & rhs, Alloc & allocator):
195 children.clone_from(rhs.children, node_cloner<heap_node, node_base, Alloc>(allocator), nop_disposer());
198 size_type child_count(void) const
200 BOOST_STATIC_ASSERT(constant_time_child_size);
201 return children.size();
204 void add_child(heap_node * n)
206 children.push_back(*n);
209 template <typename Alloc>
210 void clear_subtree(Alloc & alloc)
212 children.clear_and_dispose(node_disposer<heap_node, node_base, Alloc>(alloc));
215 void swap_children(heap_node * rhs)
217 children.swap(rhs->children);
224 template <typename value_type>
225 struct parent_pointing_heap_node:
226 heap_node<value_type>
228 typedef heap_node<value_type> super_t;
230 parent_pointing_heap_node(value_type const & v):
231 super_t(v), parent(NULL)
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)
241 template <typename Alloc>
244 node_cloner(Alloc & allocator, parent_pointing_heap_node * parent):
245 allocator(allocator), parent_(parent)
248 parent_pointing_heap_node * operator() (typename super_t::node_base const & node)
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_);
257 parent_pointing_heap_node * parent_;
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)
264 super_t::children.clone_from(rhs.children, node_cloner<Alloc>(allocator, this), nop_disposer());
267 void update_children(void)
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;
276 void remove_from_parent(void)
278 BOOST_HEAP_ASSERT(parent);
279 parent->children.erase(heap_node_list::s_iterator_to(*this));
283 void add_child(parent_pointing_heap_node * n)
285 BOOST_HEAP_ASSERT(n->parent == NULL);
287 super_t::add_child(n);
290 parent_pointing_heap_node * get_parent(void)
295 const parent_pointing_heap_node * get_parent(void) const
300 parent_pointing_heap_node * parent;
304 template <typename value_type>
305 struct marked_heap_node:
306 parent_pointing_heap_node<value_type>
308 typedef parent_pointing_heap_node<value_type> super_t;
310 marked_heap_node(value_type const & v):
311 super_t(v), mark(false)
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)
321 marked_heap_node * get_parent(void)
323 return static_cast<marked_heap_node*>(super_t::parent);
326 const marked_heap_node * get_parent(void) const
328 return static_cast<marked_heap_node*>(super_t::parent);
335 template <typename Node>
338 template <typename NodeBase>
339 bool operator()(NodeBase const & left,
340 NodeBase const & right)
342 return static_cast<const Node*>(&left)->child_count() < static_cast<const Node*>(&right)->child_count();
346 template <typename List, typename Node, typename Cmp>
347 Node * find_max_child(List const & list, Cmp const & cmp)
349 BOOST_HEAP_ASSERT(!list.empty());
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);
355 if (cmp(ret->value, current->value))
359 return const_cast<Node*>(ret);
362 } /* namespace detail */
363 } /* namespace heap */
364 } /* namespace boost */
366 #undef BOOST_HEAP_ASSERT
367 #endif /* BOOST_HEAP_DETAIL_HEAP_NODE_HPP */