annotate gcc/fibonacci_heap.h @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents
children 84e7813d76e9
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
16
kono
parents:
diff changeset
1 /* Fibonacci heap for GNU compiler.
kono
parents:
diff changeset
2 Copyright (C) 1998-2017 Free Software Foundation, Inc.
kono
parents:
diff changeset
3 Contributed by Daniel Berlin (dan@cgsoftware.com).
kono
parents:
diff changeset
4 Re-implemented in C++ by Martin Liska <mliska@suse.cz>
kono
parents:
diff changeset
5
kono
parents:
diff changeset
6 This file is part of GCC.
kono
parents:
diff changeset
7
kono
parents:
diff changeset
8 GCC is free software; you can redistribute it and/or modify it under
kono
parents:
diff changeset
9 the terms of the GNU General Public License as published by the Free
kono
parents:
diff changeset
10 Software Foundation; either version 3, or (at your option) any later
kono
parents:
diff changeset
11 version.
kono
parents:
diff changeset
12
kono
parents:
diff changeset
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
kono
parents:
diff changeset
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
kono
parents:
diff changeset
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
kono
parents:
diff changeset
16 for more details.
kono
parents:
diff changeset
17
kono
parents:
diff changeset
18 You should have received a copy of the GNU General Public License
kono
parents:
diff changeset
19 along with GCC; see the file COPYING3. If not see
kono
parents:
diff changeset
20 <http://www.gnu.org/licenses/>. */
kono
parents:
diff changeset
21
kono
parents:
diff changeset
22 /* Fibonacci heaps are somewhat complex, but, there's an article in
kono
parents:
diff changeset
23 DDJ that explains them pretty well:
kono
parents:
diff changeset
24
kono
parents:
diff changeset
25 http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
kono
parents:
diff changeset
26
kono
parents:
diff changeset
27 Introduction to algorithms by Corman and Rivest also goes over them.
kono
parents:
diff changeset
28
kono
parents:
diff changeset
29 The original paper that introduced them is "Fibonacci heaps and their
kono
parents:
diff changeset
30 uses in improved network optimization algorithms" by Tarjan and
kono
parents:
diff changeset
31 Fredman (JACM 34(3), July 1987).
kono
parents:
diff changeset
32
kono
parents:
diff changeset
33 Amortized and real worst case time for operations:
kono
parents:
diff changeset
34
kono
parents:
diff changeset
35 ExtractMin: O(lg n) amortized. O(n) worst case.
kono
parents:
diff changeset
36 DecreaseKey: O(1) amortized. O(lg n) worst case.
kono
parents:
diff changeset
37 Insert: O(1) amortized.
kono
parents:
diff changeset
38 Union: O(1) amortized. */
kono
parents:
diff changeset
39
kono
parents:
diff changeset
40 #ifndef GCC_FIBONACCI_HEAP_H
kono
parents:
diff changeset
41 #define GCC_FIBONACCI_HEAP_H
kono
parents:
diff changeset
42
kono
parents:
diff changeset
43 /* Forward definition. */
kono
parents:
diff changeset
44
kono
parents:
diff changeset
45 template<class K, class V>
kono
parents:
diff changeset
46 class fibonacci_heap;
kono
parents:
diff changeset
47
kono
parents:
diff changeset
48 /* Fibonacci heap node class. */
kono
parents:
diff changeset
49
kono
parents:
diff changeset
50 template<class K, class V>
kono
parents:
diff changeset
51 class fibonacci_node
kono
parents:
diff changeset
52 {
kono
parents:
diff changeset
53 typedef fibonacci_node<K,V> fibonacci_node_t;
kono
parents:
diff changeset
54 friend class fibonacci_heap<K,V>;
kono
parents:
diff changeset
55
kono
parents:
diff changeset
56 public:
kono
parents:
diff changeset
57 /* Default constructor. */
kono
parents:
diff changeset
58 fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this),
kono
parents:
diff changeset
59 m_right (this), m_degree (0), m_mark (0)
kono
parents:
diff changeset
60 {
kono
parents:
diff changeset
61 }
kono
parents:
diff changeset
62
kono
parents:
diff changeset
63 /* Constructor for a node with given KEY. */
kono
parents:
diff changeset
64 fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
kono
parents:
diff changeset
65 m_left (this), m_right (this), m_key (key), m_data (data),
kono
parents:
diff changeset
66 m_degree (0), m_mark (0)
kono
parents:
diff changeset
67 {
kono
parents:
diff changeset
68 }
kono
parents:
diff changeset
69
kono
parents:
diff changeset
70 /* Compare fibonacci node with OTHER node. */
kono
parents:
diff changeset
71 int compare (fibonacci_node_t *other)
kono
parents:
diff changeset
72 {
kono
parents:
diff changeset
73 if (m_key < other->m_key)
kono
parents:
diff changeset
74 return -1;
kono
parents:
diff changeset
75 if (m_key > other->m_key)
kono
parents:
diff changeset
76 return 1;
kono
parents:
diff changeset
77 return 0;
kono
parents:
diff changeset
78 }
kono
parents:
diff changeset
79
kono
parents:
diff changeset
80 /* Compare the node with a given KEY. */
kono
parents:
diff changeset
81 int compare_data (K key)
kono
parents:
diff changeset
82 {
kono
parents:
diff changeset
83 return fibonacci_node_t (key).compare (this);
kono
parents:
diff changeset
84 }
kono
parents:
diff changeset
85
kono
parents:
diff changeset
86 /* Remove fibonacci heap node. */
kono
parents:
diff changeset
87 fibonacci_node_t *remove ();
kono
parents:
diff changeset
88
kono
parents:
diff changeset
89 /* Link the node with PARENT. */
kono
parents:
diff changeset
90 void link (fibonacci_node_t *parent);
kono
parents:
diff changeset
91
kono
parents:
diff changeset
92 /* Return key associated with the node. */
kono
parents:
diff changeset
93 K get_key ()
kono
parents:
diff changeset
94 {
kono
parents:
diff changeset
95 return m_key;
kono
parents:
diff changeset
96 }
kono
parents:
diff changeset
97
kono
parents:
diff changeset
98 /* Return data associated with the node. */
kono
parents:
diff changeset
99 V *get_data ()
kono
parents:
diff changeset
100 {
kono
parents:
diff changeset
101 return m_data;
kono
parents:
diff changeset
102 }
kono
parents:
diff changeset
103
kono
parents:
diff changeset
104 private:
kono
parents:
diff changeset
105 /* Put node B after this node. */
kono
parents:
diff changeset
106 void insert_after (fibonacci_node_t *b);
kono
parents:
diff changeset
107
kono
parents:
diff changeset
108 /* Insert fibonacci node B after this node. */
kono
parents:
diff changeset
109 void insert_before (fibonacci_node_t *b)
kono
parents:
diff changeset
110 {
kono
parents:
diff changeset
111 m_left->insert_after (b);
kono
parents:
diff changeset
112 }
kono
parents:
diff changeset
113
kono
parents:
diff changeset
114 /* Parent node. */
kono
parents:
diff changeset
115 fibonacci_node *m_parent;
kono
parents:
diff changeset
116 /* Child node. */
kono
parents:
diff changeset
117 fibonacci_node *m_child;
kono
parents:
diff changeset
118 /* Left sibling. */
kono
parents:
diff changeset
119 fibonacci_node *m_left;
kono
parents:
diff changeset
120 /* Right node. */
kono
parents:
diff changeset
121 fibonacci_node *m_right;
kono
parents:
diff changeset
122 /* Key associated with node. */
kono
parents:
diff changeset
123 K m_key;
kono
parents:
diff changeset
124 /* Data associated with node. */
kono
parents:
diff changeset
125 V *m_data;
kono
parents:
diff changeset
126
kono
parents:
diff changeset
127 #if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
kono
parents:
diff changeset
128 /* Degree of the node. */
kono
parents:
diff changeset
129 __extension__ unsigned long int m_degree : 31;
kono
parents:
diff changeset
130 /* Mark of the node. */
kono
parents:
diff changeset
131 __extension__ unsigned long int m_mark : 1;
kono
parents:
diff changeset
132 #else
kono
parents:
diff changeset
133 /* Degree of the node. */
kono
parents:
diff changeset
134 unsigned int m_degree : 31;
kono
parents:
diff changeset
135 /* Mark of the node. */
kono
parents:
diff changeset
136 unsigned int m_mark : 1;
kono
parents:
diff changeset
137 #endif
kono
parents:
diff changeset
138 };
kono
parents:
diff changeset
139
kono
parents:
diff changeset
140 /* Fibonacci heap class. */
kono
parents:
diff changeset
141 template<class K, class V>
kono
parents:
diff changeset
142 class fibonacci_heap
kono
parents:
diff changeset
143 {
kono
parents:
diff changeset
144 typedef fibonacci_node<K,V> fibonacci_node_t;
kono
parents:
diff changeset
145 friend class fibonacci_node<K,V>;
kono
parents:
diff changeset
146
kono
parents:
diff changeset
147 public:
kono
parents:
diff changeset
148 /* Default constructor. */
kono
parents:
diff changeset
149 fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL),
kono
parents:
diff changeset
150 m_global_min_key (global_min_key)
kono
parents:
diff changeset
151 {
kono
parents:
diff changeset
152 }
kono
parents:
diff changeset
153
kono
parents:
diff changeset
154 /* Destructor. */
kono
parents:
diff changeset
155 ~fibonacci_heap ()
kono
parents:
diff changeset
156 {
kono
parents:
diff changeset
157 while (m_min != NULL)
kono
parents:
diff changeset
158 delete (extract_minimum_node ());
kono
parents:
diff changeset
159 }
kono
parents:
diff changeset
160
kono
parents:
diff changeset
161 /* Insert new node given by KEY and DATA associated with the key. */
kono
parents:
diff changeset
162 fibonacci_node_t *insert (K key, V *data);
kono
parents:
diff changeset
163
kono
parents:
diff changeset
164 /* Return true if no entry is present. */
kono
parents:
diff changeset
165 bool empty ()
kono
parents:
diff changeset
166 {
kono
parents:
diff changeset
167 return m_nodes == 0;
kono
parents:
diff changeset
168 }
kono
parents:
diff changeset
169
kono
parents:
diff changeset
170 /* Return the number of nodes. */
kono
parents:
diff changeset
171 size_t nodes ()
kono
parents:
diff changeset
172 {
kono
parents:
diff changeset
173 return m_nodes;
kono
parents:
diff changeset
174 }
kono
parents:
diff changeset
175
kono
parents:
diff changeset
176 /* Return minimal key presented in the heap. */
kono
parents:
diff changeset
177 K min_key ()
kono
parents:
diff changeset
178 {
kono
parents:
diff changeset
179 if (m_min == NULL)
kono
parents:
diff changeset
180 gcc_unreachable ();
kono
parents:
diff changeset
181
kono
parents:
diff changeset
182 return m_min->m_key;
kono
parents:
diff changeset
183 }
kono
parents:
diff changeset
184
kono
parents:
diff changeset
185 /* For given NODE, set new KEY value. */
kono
parents:
diff changeset
186 K replace_key (fibonacci_node_t *node, K key)
kono
parents:
diff changeset
187 {
kono
parents:
diff changeset
188 K okey = node->m_key;
kono
parents:
diff changeset
189
kono
parents:
diff changeset
190 replace_key_data (node, key, node->m_data);
kono
parents:
diff changeset
191 return okey;
kono
parents:
diff changeset
192 }
kono
parents:
diff changeset
193
kono
parents:
diff changeset
194 /* For given NODE, decrease value to new KEY. */
kono
parents:
diff changeset
195 K decrease_key (fibonacci_node_t *node, K key)
kono
parents:
diff changeset
196 {
kono
parents:
diff changeset
197 gcc_assert (key <= node->m_key);
kono
parents:
diff changeset
198 return replace_key (node, key);
kono
parents:
diff changeset
199 }
kono
parents:
diff changeset
200
kono
parents:
diff changeset
201 /* For given NODE, set new KEY and DATA value. */
kono
parents:
diff changeset
202 V *replace_key_data (fibonacci_node_t *node, K key, V *data);
kono
parents:
diff changeset
203
kono
parents:
diff changeset
204 /* Extract minimum node in the heap. If RELEASE is specified,
kono
parents:
diff changeset
205 memory is released. */
kono
parents:
diff changeset
206 V *extract_min (bool release = true);
kono
parents:
diff changeset
207
kono
parents:
diff changeset
208 /* Return value associated with minimum node in the heap. */
kono
parents:
diff changeset
209 V *min ()
kono
parents:
diff changeset
210 {
kono
parents:
diff changeset
211 if (m_min == NULL)
kono
parents:
diff changeset
212 return NULL;
kono
parents:
diff changeset
213
kono
parents:
diff changeset
214 return m_min->m_data;
kono
parents:
diff changeset
215 }
kono
parents:
diff changeset
216
kono
parents:
diff changeset
217 /* Replace data associated with NODE and replace it with DATA. */
kono
parents:
diff changeset
218 V *replace_data (fibonacci_node_t *node, V *data)
kono
parents:
diff changeset
219 {
kono
parents:
diff changeset
220 return replace_key_data (node, node->m_key, data);
kono
parents:
diff changeset
221 }
kono
parents:
diff changeset
222
kono
parents:
diff changeset
223 /* Delete NODE in the heap. */
kono
parents:
diff changeset
224 V *delete_node (fibonacci_node_t *node, bool release = true);
kono
parents:
diff changeset
225
kono
parents:
diff changeset
226 /* Union the heap with HEAPB. */
kono
parents:
diff changeset
227 fibonacci_heap *union_with (fibonacci_heap *heapb);
kono
parents:
diff changeset
228
kono
parents:
diff changeset
229 private:
kono
parents:
diff changeset
230 /* Insert new NODE given by KEY and DATA associated with the key. */
kono
parents:
diff changeset
231 fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
kono
parents:
diff changeset
232
kono
parents:
diff changeset
233 /* Insert new NODE that has already filled key and value. */
kono
parents:
diff changeset
234 fibonacci_node_t *insert_node (fibonacci_node_t *node);
kono
parents:
diff changeset
235
kono
parents:
diff changeset
236 /* Insert it into the root list. */
kono
parents:
diff changeset
237 void insert_root (fibonacci_node_t *node);
kono
parents:
diff changeset
238
kono
parents:
diff changeset
239 /* Remove NODE from PARENT's child list. */
kono
parents:
diff changeset
240 void cut (fibonacci_node_t *node, fibonacci_node_t *parent);
kono
parents:
diff changeset
241
kono
parents:
diff changeset
242 /* Process cut of node Y and do it recursivelly. */
kono
parents:
diff changeset
243 void cascading_cut (fibonacci_node_t *y);
kono
parents:
diff changeset
244
kono
parents:
diff changeset
245 /* Extract minimum node from the heap. */
kono
parents:
diff changeset
246 fibonacci_node_t * extract_minimum_node ();
kono
parents:
diff changeset
247
kono
parents:
diff changeset
248 /* Remove root NODE from the heap. */
kono
parents:
diff changeset
249 void remove_root (fibonacci_node_t *node);
kono
parents:
diff changeset
250
kono
parents:
diff changeset
251 /* Consolidate heap. */
kono
parents:
diff changeset
252 void consolidate ();
kono
parents:
diff changeset
253
kono
parents:
diff changeset
254 /* Number of nodes. */
kono
parents:
diff changeset
255 size_t m_nodes;
kono
parents:
diff changeset
256 /* Minimum node of the heap. */
kono
parents:
diff changeset
257 fibonacci_node_t *m_min;
kono
parents:
diff changeset
258 /* Root node of the heap. */
kono
parents:
diff changeset
259 fibonacci_node_t *m_root;
kono
parents:
diff changeset
260 /* Global minimum given in the heap construction. */
kono
parents:
diff changeset
261 K m_global_min_key;
kono
parents:
diff changeset
262 };
kono
parents:
diff changeset
263
kono
parents:
diff changeset
264 /* Remove fibonacci heap node. */
kono
parents:
diff changeset
265
kono
parents:
diff changeset
266 template<class K, class V>
kono
parents:
diff changeset
267 fibonacci_node<K,V> *
kono
parents:
diff changeset
268 fibonacci_node<K,V>::remove ()
kono
parents:
diff changeset
269 {
kono
parents:
diff changeset
270 fibonacci_node<K,V> *ret;
kono
parents:
diff changeset
271
kono
parents:
diff changeset
272 if (this == m_left)
kono
parents:
diff changeset
273 ret = NULL;
kono
parents:
diff changeset
274 else
kono
parents:
diff changeset
275 ret = m_left;
kono
parents:
diff changeset
276
kono
parents:
diff changeset
277 if (m_parent != NULL && m_parent->m_child == this)
kono
parents:
diff changeset
278 m_parent->m_child = ret;
kono
parents:
diff changeset
279
kono
parents:
diff changeset
280 m_right->m_left = m_left;
kono
parents:
diff changeset
281 m_left->m_right = m_right;
kono
parents:
diff changeset
282
kono
parents:
diff changeset
283 m_parent = NULL;
kono
parents:
diff changeset
284 m_left = this;
kono
parents:
diff changeset
285 m_right = this;
kono
parents:
diff changeset
286
kono
parents:
diff changeset
287 return ret;
kono
parents:
diff changeset
288 }
kono
parents:
diff changeset
289
kono
parents:
diff changeset
290 /* Link the node with PARENT. */
kono
parents:
diff changeset
291
kono
parents:
diff changeset
292 template<class K, class V>
kono
parents:
diff changeset
293 void
kono
parents:
diff changeset
294 fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
kono
parents:
diff changeset
295 {
kono
parents:
diff changeset
296 if (parent->m_child == NULL)
kono
parents:
diff changeset
297 parent->m_child = this;
kono
parents:
diff changeset
298 else
kono
parents:
diff changeset
299 parent->m_child->insert_before (this);
kono
parents:
diff changeset
300 m_parent = parent;
kono
parents:
diff changeset
301 parent->m_degree++;
kono
parents:
diff changeset
302 m_mark = 0;
kono
parents:
diff changeset
303 }
kono
parents:
diff changeset
304
kono
parents:
diff changeset
305 /* Put node B after this node. */
kono
parents:
diff changeset
306
kono
parents:
diff changeset
307 template<class K, class V>
kono
parents:
diff changeset
308 void
kono
parents:
diff changeset
309 fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
kono
parents:
diff changeset
310 {
kono
parents:
diff changeset
311 fibonacci_node<K,V> *a = this;
kono
parents:
diff changeset
312
kono
parents:
diff changeset
313 if (a == a->m_right)
kono
parents:
diff changeset
314 {
kono
parents:
diff changeset
315 a->m_right = b;
kono
parents:
diff changeset
316 a->m_left = b;
kono
parents:
diff changeset
317 b->m_right = a;
kono
parents:
diff changeset
318 b->m_left = a;
kono
parents:
diff changeset
319 }
kono
parents:
diff changeset
320 else
kono
parents:
diff changeset
321 {
kono
parents:
diff changeset
322 b->m_right = a->m_right;
kono
parents:
diff changeset
323 a->m_right->m_left = b;
kono
parents:
diff changeset
324 a->m_right = b;
kono
parents:
diff changeset
325 b->m_left = a;
kono
parents:
diff changeset
326 }
kono
parents:
diff changeset
327 }
kono
parents:
diff changeset
328
kono
parents:
diff changeset
329 /* Insert new node given by KEY and DATA associated with the key. */
kono
parents:
diff changeset
330
kono
parents:
diff changeset
331 template<class K, class V>
kono
parents:
diff changeset
332 fibonacci_node<K,V>*
kono
parents:
diff changeset
333 fibonacci_heap<K,V>::insert (K key, V *data)
kono
parents:
diff changeset
334 {
kono
parents:
diff changeset
335 /* Create the new node. */
kono
parents:
diff changeset
336 fibonacci_node<K,V> *node = new fibonacci_node_t (key, data);
kono
parents:
diff changeset
337
kono
parents:
diff changeset
338 return insert_node (node);
kono
parents:
diff changeset
339 }
kono
parents:
diff changeset
340
kono
parents:
diff changeset
341 /* Insert new NODE given by DATA associated with the key. */
kono
parents:
diff changeset
342
kono
parents:
diff changeset
343 template<class K, class V>
kono
parents:
diff changeset
344 fibonacci_node<K,V>*
kono
parents:
diff changeset
345 fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
kono
parents:
diff changeset
346 {
kono
parents:
diff changeset
347 /* Set the node's data. */
kono
parents:
diff changeset
348 node->m_data = data;
kono
parents:
diff changeset
349 node->m_key = key;
kono
parents:
diff changeset
350
kono
parents:
diff changeset
351 return insert_node (node);
kono
parents:
diff changeset
352 }
kono
parents:
diff changeset
353
kono
parents:
diff changeset
354 /* Insert new NODE that has already filled key and value. */
kono
parents:
diff changeset
355
kono
parents:
diff changeset
356 template<class K, class V>
kono
parents:
diff changeset
357 fibonacci_node<K,V>*
kono
parents:
diff changeset
358 fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
kono
parents:
diff changeset
359 {
kono
parents:
diff changeset
360 /* Insert it into the root list. */
kono
parents:
diff changeset
361 insert_root (node);
kono
parents:
diff changeset
362
kono
parents:
diff changeset
363 /* If their was no minimum, or this key is less than the min,
kono
parents:
diff changeset
364 it's the new min. */
kono
parents:
diff changeset
365 if (m_min == NULL || node->m_key < m_min->m_key)
kono
parents:
diff changeset
366 m_min = node;
kono
parents:
diff changeset
367
kono
parents:
diff changeset
368 m_nodes++;
kono
parents:
diff changeset
369
kono
parents:
diff changeset
370 return node;
kono
parents:
diff changeset
371 }
kono
parents:
diff changeset
372
kono
parents:
diff changeset
373 /* For given NODE, set new KEY and DATA value. */
kono
parents:
diff changeset
374
kono
parents:
diff changeset
375 template<class K, class V>
kono
parents:
diff changeset
376 V*
kono
parents:
diff changeset
377 fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
kono
parents:
diff changeset
378 V *data)
kono
parents:
diff changeset
379 {
kono
parents:
diff changeset
380 K okey;
kono
parents:
diff changeset
381 fibonacci_node<K,V> *y;
kono
parents:
diff changeset
382 V *odata = node->m_data;
kono
parents:
diff changeset
383
kono
parents:
diff changeset
384 /* If we wanted to, we do a real increase by redeleting and
kono
parents:
diff changeset
385 inserting. */
kono
parents:
diff changeset
386 if (node->compare_data (key) > 0)
kono
parents:
diff changeset
387 {
kono
parents:
diff changeset
388 delete_node (node, false);
kono
parents:
diff changeset
389
kono
parents:
diff changeset
390 node = new (node) fibonacci_node_t ();
kono
parents:
diff changeset
391 insert (node, key, data);
kono
parents:
diff changeset
392
kono
parents:
diff changeset
393 return odata;
kono
parents:
diff changeset
394 }
kono
parents:
diff changeset
395
kono
parents:
diff changeset
396 okey = node->m_key;
kono
parents:
diff changeset
397 node->m_data = data;
kono
parents:
diff changeset
398 node->m_key = key;
kono
parents:
diff changeset
399 y = node->m_parent;
kono
parents:
diff changeset
400
kono
parents:
diff changeset
401 /* Short-circuit if the key is the same, as we then don't have to
kono
parents:
diff changeset
402 do anything. Except if we're trying to force the new node to
kono
parents:
diff changeset
403 be the new minimum for delete. */
kono
parents:
diff changeset
404 if (okey == key && okey != m_global_min_key)
kono
parents:
diff changeset
405 return odata;
kono
parents:
diff changeset
406
kono
parents:
diff changeset
407 /* These two compares are specifically <= 0 to make sure that in the case
kono
parents:
diff changeset
408 of equality, a node we replaced the data on, becomes the new min. This
kono
parents:
diff changeset
409 is needed so that delete's call to extractmin gets the right node. */
kono
parents:
diff changeset
410 if (y != NULL && node->compare (y) <= 0)
kono
parents:
diff changeset
411 {
kono
parents:
diff changeset
412 cut (node, y);
kono
parents:
diff changeset
413 cascading_cut (y);
kono
parents:
diff changeset
414 }
kono
parents:
diff changeset
415
kono
parents:
diff changeset
416 if (node->compare (m_min) <= 0)
kono
parents:
diff changeset
417 m_min = node;
kono
parents:
diff changeset
418
kono
parents:
diff changeset
419 return odata;
kono
parents:
diff changeset
420 }
kono
parents:
diff changeset
421
kono
parents:
diff changeset
422 /* Extract minimum node in the heap. Delete fibonacci node if RELEASE
kono
parents:
diff changeset
423 is true. */
kono
parents:
diff changeset
424
kono
parents:
diff changeset
425 template<class K, class V>
kono
parents:
diff changeset
426 V*
kono
parents:
diff changeset
427 fibonacci_heap<K,V>::extract_min (bool release)
kono
parents:
diff changeset
428 {
kono
parents:
diff changeset
429 fibonacci_node<K,V> *z;
kono
parents:
diff changeset
430 V *ret = NULL;
kono
parents:
diff changeset
431
kono
parents:
diff changeset
432 /* If we don't have a min set, it means we have no nodes. */
kono
parents:
diff changeset
433 if (m_min != NULL)
kono
parents:
diff changeset
434 {
kono
parents:
diff changeset
435 /* Otherwise, extract the min node, free the node, and return the
kono
parents:
diff changeset
436 node's data. */
kono
parents:
diff changeset
437 z = extract_minimum_node ();
kono
parents:
diff changeset
438 ret = z->m_data;
kono
parents:
diff changeset
439
kono
parents:
diff changeset
440 if (release)
kono
parents:
diff changeset
441 delete (z);
kono
parents:
diff changeset
442 }
kono
parents:
diff changeset
443
kono
parents:
diff changeset
444 return ret;
kono
parents:
diff changeset
445 }
kono
parents:
diff changeset
446
kono
parents:
diff changeset
447 /* Delete NODE in the heap, if RELEASE is specified memory is released. */
kono
parents:
diff changeset
448
kono
parents:
diff changeset
449 template<class K, class V>
kono
parents:
diff changeset
450 V*
kono
parents:
diff changeset
451 fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
kono
parents:
diff changeset
452 {
kono
parents:
diff changeset
453 V *ret = node->m_data;
kono
parents:
diff changeset
454
kono
parents:
diff changeset
455 /* To perform delete, we just make it the min key, and extract. */
kono
parents:
diff changeset
456 replace_key (node, m_global_min_key);
kono
parents:
diff changeset
457 if (node != m_min)
kono
parents:
diff changeset
458 {
kono
parents:
diff changeset
459 fprintf (stderr, "Can't force minimum on fibheap.\n");
kono
parents:
diff changeset
460 abort ();
kono
parents:
diff changeset
461 }
kono
parents:
diff changeset
462 extract_min (release);
kono
parents:
diff changeset
463
kono
parents:
diff changeset
464 return ret;
kono
parents:
diff changeset
465 }
kono
parents:
diff changeset
466
kono
parents:
diff changeset
467 /* Union the heap with HEAPB. One of the heaps is going to be deleted. */
kono
parents:
diff changeset
468
kono
parents:
diff changeset
469 template<class K, class V>
kono
parents:
diff changeset
470 fibonacci_heap<K,V>*
kono
parents:
diff changeset
471 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
kono
parents:
diff changeset
472 {
kono
parents:
diff changeset
473 fibonacci_heap<K,V> *heapa = this;
kono
parents:
diff changeset
474
kono
parents:
diff changeset
475 fibonacci_node<K,V> *a_root, *b_root;
kono
parents:
diff changeset
476
kono
parents:
diff changeset
477 /* If one of the heaps is empty, the union is just the other heap. */
kono
parents:
diff changeset
478 if ((a_root = heapa->m_root) == NULL)
kono
parents:
diff changeset
479 {
kono
parents:
diff changeset
480 delete (heapa);
kono
parents:
diff changeset
481 return heapb;
kono
parents:
diff changeset
482 }
kono
parents:
diff changeset
483 if ((b_root = heapb->m_root) == NULL)
kono
parents:
diff changeset
484 {
kono
parents:
diff changeset
485 delete (heapb);
kono
parents:
diff changeset
486 return heapa;
kono
parents:
diff changeset
487 }
kono
parents:
diff changeset
488
kono
parents:
diff changeset
489 /* Merge them to the next nodes on the opposite chain. */
kono
parents:
diff changeset
490 a_root->m_left->m_right = b_root;
kono
parents:
diff changeset
491 b_root->m_left->m_right = a_root;
kono
parents:
diff changeset
492 std::swap (a_root->m_left, b_root->m_left);
kono
parents:
diff changeset
493 heapa->m_nodes += heapb->m_nodes;
kono
parents:
diff changeset
494
kono
parents:
diff changeset
495 /* And set the new minimum, if it's changed. */
kono
parents:
diff changeset
496 if (heapb->m_min->compare (heapa->m_min) < 0)
kono
parents:
diff changeset
497 heapa->m_min = heapb->m_min;
kono
parents:
diff changeset
498
kono
parents:
diff changeset
499 /* Set m_min to NULL to not to delete live fibonacci nodes. */
kono
parents:
diff changeset
500 heapb->m_min = NULL;
kono
parents:
diff changeset
501 delete (heapb);
kono
parents:
diff changeset
502
kono
parents:
diff changeset
503 return heapa;
kono
parents:
diff changeset
504 }
kono
parents:
diff changeset
505
kono
parents:
diff changeset
506 /* Insert it into the root list. */
kono
parents:
diff changeset
507
kono
parents:
diff changeset
508 template<class K, class V>
kono
parents:
diff changeset
509 void
kono
parents:
diff changeset
510 fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
kono
parents:
diff changeset
511 {
kono
parents:
diff changeset
512 /* If the heap is currently empty, the new node becomes the singleton
kono
parents:
diff changeset
513 circular root list. */
kono
parents:
diff changeset
514 if (m_root == NULL)
kono
parents:
diff changeset
515 {
kono
parents:
diff changeset
516 m_root = node;
kono
parents:
diff changeset
517 node->m_left = node;
kono
parents:
diff changeset
518 node->m_right = node;
kono
parents:
diff changeset
519 return;
kono
parents:
diff changeset
520 }
kono
parents:
diff changeset
521
kono
parents:
diff changeset
522 /* Otherwise, insert it in the circular root list between the root
kono
parents:
diff changeset
523 and it's right node. */
kono
parents:
diff changeset
524 m_root->insert_after (node);
kono
parents:
diff changeset
525 }
kono
parents:
diff changeset
526
kono
parents:
diff changeset
527 /* Remove NODE from PARENT's child list. */
kono
parents:
diff changeset
528
kono
parents:
diff changeset
529 template<class K, class V>
kono
parents:
diff changeset
530 void
kono
parents:
diff changeset
531 fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
kono
parents:
diff changeset
532 fibonacci_node<K,V> *parent)
kono
parents:
diff changeset
533 {
kono
parents:
diff changeset
534 node->remove ();
kono
parents:
diff changeset
535 parent->m_degree--;
kono
parents:
diff changeset
536 insert_root (node);
kono
parents:
diff changeset
537 node->m_parent = NULL;
kono
parents:
diff changeset
538 node->m_mark = 0;
kono
parents:
diff changeset
539 }
kono
parents:
diff changeset
540
kono
parents:
diff changeset
541 /* Process cut of node Y and do it recursivelly. */
kono
parents:
diff changeset
542
kono
parents:
diff changeset
543 template<class K, class V>
kono
parents:
diff changeset
544 void
kono
parents:
diff changeset
545 fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
kono
parents:
diff changeset
546 {
kono
parents:
diff changeset
547 fibonacci_node<K,V> *z;
kono
parents:
diff changeset
548
kono
parents:
diff changeset
549 while ((z = y->m_parent) != NULL)
kono
parents:
diff changeset
550 {
kono
parents:
diff changeset
551 if (y->m_mark == 0)
kono
parents:
diff changeset
552 {
kono
parents:
diff changeset
553 y->m_mark = 1;
kono
parents:
diff changeset
554 return;
kono
parents:
diff changeset
555 }
kono
parents:
diff changeset
556 else
kono
parents:
diff changeset
557 {
kono
parents:
diff changeset
558 cut (y, z);
kono
parents:
diff changeset
559 y = z;
kono
parents:
diff changeset
560 }
kono
parents:
diff changeset
561 }
kono
parents:
diff changeset
562 }
kono
parents:
diff changeset
563
kono
parents:
diff changeset
564 /* Extract minimum node from the heap. */
kono
parents:
diff changeset
565
kono
parents:
diff changeset
566 template<class K, class V>
kono
parents:
diff changeset
567 fibonacci_node<K,V>*
kono
parents:
diff changeset
568 fibonacci_heap<K,V>::extract_minimum_node ()
kono
parents:
diff changeset
569 {
kono
parents:
diff changeset
570 fibonacci_node<K,V> *ret = m_min;
kono
parents:
diff changeset
571 fibonacci_node<K,V> *x, *y, *orig;
kono
parents:
diff changeset
572
kono
parents:
diff changeset
573 /* Attach the child list of the minimum node to the root list of the heap.
kono
parents:
diff changeset
574 If there is no child list, we don't do squat. */
kono
parents:
diff changeset
575 for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
kono
parents:
diff changeset
576 {
kono
parents:
diff changeset
577 if (orig == NULL)
kono
parents:
diff changeset
578 orig = x;
kono
parents:
diff changeset
579 y = x->m_right;
kono
parents:
diff changeset
580 x->m_parent = NULL;
kono
parents:
diff changeset
581 insert_root (x);
kono
parents:
diff changeset
582 }
kono
parents:
diff changeset
583
kono
parents:
diff changeset
584 /* Remove the old root. */
kono
parents:
diff changeset
585 remove_root (ret);
kono
parents:
diff changeset
586 m_nodes--;
kono
parents:
diff changeset
587
kono
parents:
diff changeset
588 /* If we are left with no nodes, then the min is NULL. */
kono
parents:
diff changeset
589 if (m_nodes == 0)
kono
parents:
diff changeset
590 m_min = NULL;
kono
parents:
diff changeset
591 else
kono
parents:
diff changeset
592 {
kono
parents:
diff changeset
593 /* Otherwise, consolidate to find new minimum, as well as do the reorg
kono
parents:
diff changeset
594 work that needs to be done. */
kono
parents:
diff changeset
595 m_min = ret->m_right;
kono
parents:
diff changeset
596 consolidate ();
kono
parents:
diff changeset
597 }
kono
parents:
diff changeset
598
kono
parents:
diff changeset
599 return ret;
kono
parents:
diff changeset
600 }
kono
parents:
diff changeset
601
kono
parents:
diff changeset
602 /* Remove root NODE from the heap. */
kono
parents:
diff changeset
603
kono
parents:
diff changeset
604 template<class K, class V>
kono
parents:
diff changeset
605 void
kono
parents:
diff changeset
606 fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
kono
parents:
diff changeset
607 {
kono
parents:
diff changeset
608 if (node->m_left == node)
kono
parents:
diff changeset
609 m_root = NULL;
kono
parents:
diff changeset
610 else
kono
parents:
diff changeset
611 m_root = node->remove ();
kono
parents:
diff changeset
612 }
kono
parents:
diff changeset
613
kono
parents:
diff changeset
614 /* Consolidate heap. */
kono
parents:
diff changeset
615
kono
parents:
diff changeset
616 template<class K, class V>
kono
parents:
diff changeset
617 void fibonacci_heap<K,V>::consolidate ()
kono
parents:
diff changeset
618 {
kono
parents:
diff changeset
619 int D = 1 + 8 * sizeof (long);
kono
parents:
diff changeset
620 auto_vec<fibonacci_node<K,V> *> a (D);
kono
parents:
diff changeset
621 a.safe_grow_cleared (D);
kono
parents:
diff changeset
622 fibonacci_node<K,V> *w, *x, *y;
kono
parents:
diff changeset
623 int i, d;
kono
parents:
diff changeset
624
kono
parents:
diff changeset
625 while ((w = m_root) != NULL)
kono
parents:
diff changeset
626 {
kono
parents:
diff changeset
627 x = w;
kono
parents:
diff changeset
628 remove_root (w);
kono
parents:
diff changeset
629 d = x->m_degree;
kono
parents:
diff changeset
630 while (a[d] != NULL)
kono
parents:
diff changeset
631 {
kono
parents:
diff changeset
632 y = a[d];
kono
parents:
diff changeset
633 if (x->compare (y) > 0)
kono
parents:
diff changeset
634 std::swap (x, y);
kono
parents:
diff changeset
635 y->link (x);
kono
parents:
diff changeset
636 a[d] = NULL;
kono
parents:
diff changeset
637 d++;
kono
parents:
diff changeset
638 }
kono
parents:
diff changeset
639 a[d] = x;
kono
parents:
diff changeset
640 }
kono
parents:
diff changeset
641 m_min = NULL;
kono
parents:
diff changeset
642 for (i = 0; i < D; i++)
kono
parents:
diff changeset
643 if (a[i] != NULL)
kono
parents:
diff changeset
644 {
kono
parents:
diff changeset
645 insert_root (a[i]);
kono
parents:
diff changeset
646 if (m_min == NULL || a[i]->compare (m_min) < 0)
kono
parents:
diff changeset
647 m_min = a[i];
kono
parents:
diff changeset
648 }
kono
parents:
diff changeset
649 }
kono
parents:
diff changeset
650
kono
parents:
diff changeset
651 #endif // GCC_FIBONACCI_HEAP_H