]>
Commit | Line | Data |
---|---|---|
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 */ |