1 | /* Fibonacci heap for GNU compiler. |
---|---|

2 | Copyright (C) 1998-2017 Free Software Foundation, Inc. |

3 | Contributed by Daniel Berlin (dan@cgsoftware.com). |

4 | Re-implemented in C++ by Martin Liska <mliska@suse.cz> |

5 | |

6 | This file is part of GCC. |

7 | |

8 | GCC is free software; you can redistribute it and/or modify it under |

9 | the terms of the GNU General Public License as published by the Free |

10 | Software Foundation; either version 3, or (at your option) any later |

11 | version. |

12 | |

13 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |

14 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |

15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |

16 | for more details. |

17 | |

18 | You should have received a copy of the GNU General Public License |

19 | along with GCC; see the file COPYING3. If not see |

20 | <http://www.gnu.org/licenses/>. */ |

21 | |

22 | /* Fibonacci heaps are somewhat complex, but, there's an article in |

23 | DDJ that explains them pretty well: |

24 | |

25 | http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms |

26 | |

27 | Introduction to algorithms by Corman and Rivest also goes over them. |

28 | |

29 | The original paper that introduced them is "Fibonacci heaps and their |

30 | uses in improved network optimization algorithms" by Tarjan and |

31 | Fredman (JACM 34(3), July 1987). |

32 | |

33 | Amortized and real worst case time for operations: |

34 | |

35 | ExtractMin: O(lg n) amortized. O(n) worst case. |

36 | DecreaseKey: O(1) amortized. O(lg n) worst case. |

37 | Insert: O(1) amortized. |

38 | Union: O(1) amortized. */ |

39 | |

40 | #ifndef GCC_FIBONACCI_HEAP_H |

41 | #define GCC_FIBONACCI_HEAP_H |

42 | |

43 | /* Forward definition. */ |

44 | |

45 | template<class K, class V> |

46 | class fibonacci_heap; |

47 | |

48 | /* Fibonacci heap node class. */ |

49 | |

50 | template<class K, class V> |

51 | class fibonacci_node |

52 | { |

53 | typedef fibonacci_node<K,V> fibonacci_node_t; |

54 | friend class fibonacci_heap<K,V>; |

55 | |

56 | public: |

57 | /* Default constructor. */ |

58 | fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this), |

59 | m_right (this), m_degree (0), m_mark (0) |

60 | { |

61 | } |

62 | |

63 | /* Constructor for a node with given KEY. */ |

64 | fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL), |

65 | m_left (this), m_right (this), m_key (key), m_data (data), |

66 | m_degree (0), m_mark (0) |

67 | { |

68 | } |

69 | |

70 | /* Compare fibonacci node with OTHER node. */ |

71 | int compare (fibonacci_node_t *other) |

72 | { |

73 | if (m_key < other->m_key) |

74 | return -1; |

75 | if (m_key > other->m_key) |

76 | return 1; |

77 | return 0; |

78 | } |

79 | |

80 | /* Compare the node with a given KEY. */ |

81 | int compare_data (K key) |

82 | { |

83 | return fibonacci_node_t (key).compare (this); |

84 | } |

85 | |

86 | /* Remove fibonacci heap node. */ |

87 | fibonacci_node_t *remove (); |

88 | |

89 | /* Link the node with PARENT. */ |

90 | void link (fibonacci_node_t *parent); |

91 | |

92 | /* Return key associated with the node. */ |

93 | K get_key () |

94 | { |

95 | return m_key; |

96 | } |

97 | |

98 | /* Return data associated with the node. */ |

99 | V *get_data () |

100 | { |

101 | return m_data; |

102 | } |

103 | |

104 | private: |

105 | /* Put node B after this node. */ |

106 | void insert_after (fibonacci_node_t *b); |

107 | |

108 | /* Insert fibonacci node B after this node. */ |

109 | void insert_before (fibonacci_node_t *b) |

110 | { |

111 | m_left->insert_after (b); |

112 | } |

113 | |

114 | /* Parent node. */ |

115 | fibonacci_node *m_parent; |

116 | /* Child node. */ |

117 | fibonacci_node *m_child; |

118 | /* Left sibling. */ |

119 | fibonacci_node *m_left; |

120 | /* Right node. */ |

121 | fibonacci_node *m_right; |

122 | /* Key associated with node. */ |

123 | K m_key; |

124 | /* Data associated with node. */ |

125 | V *m_data; |

126 | |

127 | #if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4) |

128 | /* Degree of the node. */ |

129 | __extension__ unsigned long int m_degree : 31; |

130 | /* Mark of the node. */ |

131 | __extension__ unsigned long int m_mark : 1; |

132 | #else |

133 | /* Degree of the node. */ |

134 | unsigned int m_degree : 31; |

135 | /* Mark of the node. */ |

136 | unsigned int m_mark : 1; |

137 | #endif |

138 | }; |

139 | |

140 | /* Fibonacci heap class. */ |

141 | template<class K, class V> |

142 | class fibonacci_heap |

143 | { |

144 | typedef fibonacci_node<K,V> fibonacci_node_t; |

145 | friend class fibonacci_node<K,V>; |

146 | |

147 | public: |

148 | /* Default constructor. */ |

149 | fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL), |

150 | m_global_min_key (global_min_key) |

151 | { |

152 | } |

153 | |

154 | /* Destructor. */ |

155 | ~fibonacci_heap () |

156 | { |

157 | while (m_min != NULL) |

158 | delete (extract_minimum_node ()); |

159 | } |

160 | |

161 | /* Insert new node given by KEY and DATA associated with the key. */ |

162 | fibonacci_node_t *insert (K key, V *data); |

163 | |

164 | /* Return true if no entry is present. */ |

165 | bool empty () |

166 | { |

167 | return m_nodes == 0; |

168 | } |

169 | |

170 | /* Return the number of nodes. */ |

171 | size_t nodes () |

172 | { |

173 | return m_nodes; |

174 | } |

175 | |

176 | /* Return minimal key presented in the heap. */ |

177 | K min_key () |

178 | { |

179 | if (m_min == NULL) |

180 | gcc_unreachable (); |

181 | |

182 | return m_min->m_key; |

183 | } |

184 | |

185 | /* For given NODE, set new KEY value. */ |

186 | K replace_key (fibonacci_node_t *node, K key) |

187 | { |

188 | K okey = node->m_key; |

189 | |

190 | replace_key_data (node, key, node->m_data); |

191 | return okey; |

192 | } |

193 | |

194 | /* For given NODE, decrease value to new KEY. */ |

195 | K decrease_key (fibonacci_node_t *node, K key) |

196 | { |

197 | gcc_assert (key <= node->m_key); |

198 | return replace_key (node, key); |

199 | } |

200 | |

201 | /* For given NODE, set new KEY and DATA value. */ |

202 | V *replace_key_data (fibonacci_node_t *node, K key, V *data); |

203 | |

204 | /* Extract minimum node in the heap. If RELEASE is specified, |

205 | memory is released. */ |

206 | V *extract_min (bool release = true); |

207 | |

208 | /* Return value associated with minimum node in the heap. */ |

209 | V *min () |

210 | { |

211 | if (m_min == NULL) |

212 | return NULL; |

213 | |

214 | return m_min->m_data; |

215 | } |

216 | |

217 | /* Replace data associated with NODE and replace it with DATA. */ |

218 | V *replace_data (fibonacci_node_t *node, V *data) |

219 | { |

220 | return replace_key_data (node, node->m_key, data); |

221 | } |

222 | |

223 | /* Delete NODE in the heap. */ |

224 | V *delete_node (fibonacci_node_t *node, bool release = true); |

225 | |

226 | /* Union the heap with HEAPB. */ |

227 | fibonacci_heap *union_with (fibonacci_heap *heapb); |

228 | |

229 | private: |

230 | /* Insert new NODE given by KEY and DATA associated with the key. */ |

231 | fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data); |

232 | |

233 | /* Insert new NODE that has already filled key and value. */ |

234 | fibonacci_node_t *insert_node (fibonacci_node_t *node); |

235 | |

236 | /* Insert it into the root list. */ |

237 | void insert_root (fibonacci_node_t *node); |

238 | |

239 | /* Remove NODE from PARENT's child list. */ |

240 | void cut (fibonacci_node_t *node, fibonacci_node_t *parent); |

241 | |

242 | /* Process cut of node Y and do it recursivelly. */ |

243 | void cascading_cut (fibonacci_node_t *y); |

244 | |

245 | /* Extract minimum node from the heap. */ |

246 | fibonacci_node_t * extract_minimum_node (); |

247 | |

248 | /* Remove root NODE from the heap. */ |

249 | void remove_root (fibonacci_node_t *node); |

250 | |

251 | /* Consolidate heap. */ |

252 | void consolidate (); |

253 | |

254 | /* Number of nodes. */ |

255 | size_t m_nodes; |

256 | /* Minimum node of the heap. */ |

257 | fibonacci_node_t *m_min; |

258 | /* Root node of the heap. */ |

259 | fibonacci_node_t *m_root; |

260 | /* Global minimum given in the heap construction. */ |

261 | K m_global_min_key; |

262 | }; |

263 | |

264 | /* Remove fibonacci heap node. */ |

265 | |

266 | template<class K, class V> |

267 | fibonacci_node<K,V> * |

268 | fibonacci_node<K,V>::remove () |

269 | { |

270 | fibonacci_node<K,V> *ret; |

271 | |

272 | if (this == m_left) |

273 | ret = NULL; |

274 | else |

275 | ret = m_left; |

276 | |

277 | if (m_parent != NULL && m_parent->m_child == this) |

278 | m_parent->m_child = ret; |

279 | |

280 | m_right->m_left = m_left; |

281 | m_left->m_right = m_right; |

282 | |

283 | m_parent = NULL; |

284 | m_left = this; |

285 | m_right = this; |

286 | |

287 | return ret; |

288 | } |

289 | |

290 | /* Link the node with PARENT. */ |

291 | |

292 | template<class K, class V> |

293 | void |

294 | fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent) |

295 | { |

296 | if (parent->m_child == NULL) |

297 | parent->m_child = this; |

298 | else |

299 | parent->m_child->insert_before (this); |

300 | m_parent = parent; |

301 | parent->m_degree++; |

302 | m_mark = 0; |

303 | } |

304 | |

305 | /* Put node B after this node. */ |

306 | |

307 | template<class K, class V> |

308 | void |

309 | fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b) |

310 | { |

311 | fibonacci_node<K,V> *a = this; |

312 | |

313 | if (a == a->m_right) |

314 | { |

315 | a->m_right = b; |

316 | a->m_left = b; |

317 | b->m_right = a; |

318 | b->m_left = a; |

319 | } |

320 | else |

321 | { |

322 | b->m_right = a->m_right; |

323 | a->m_right->m_left = b; |

324 | a->m_right = b; |

325 | b->m_left = a; |

326 | } |

327 | } |

328 | |

329 | /* Insert new node given by KEY and DATA associated with the key. */ |

330 | |

331 | template<class K, class V> |

332 | fibonacci_node<K,V>* |

333 | fibonacci_heap<K,V>::insert (K key, V *data) |

334 | { |

335 | /* Create the new node. */ |

336 | fibonacci_node<K,V> *node = new fibonacci_node_t (key, data); |

337 | |

338 | return insert_node (node); |

339 | } |

340 | |

341 | /* Insert new NODE given by DATA associated with the key. */ |

342 | |

343 | template<class K, class V> |

344 | fibonacci_node<K,V>* |

345 | fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data) |

346 | { |

347 | /* Set the node's data. */ |

348 | node->m_data = data; |

349 | node->m_key = key; |

350 | |

351 | return insert_node (node); |

352 | } |

353 | |

354 | /* Insert new NODE that has already filled key and value. */ |

355 | |

356 | template<class K, class V> |

357 | fibonacci_node<K,V>* |

358 | fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node) |

359 | { |

360 | /* Insert it into the root list. */ |

361 | insert_root (node); |

362 | |

363 | /* If their was no minimum, or this key is less than the min, |

364 | it's the new min. */ |

365 | if (m_min == NULL || node->m_key < m_min->m_key) |

366 | m_min = node; |

367 | |

368 | m_nodes++; |

369 | |

370 | return node; |

371 | } |

372 | |

373 | /* For given NODE, set new KEY and DATA value. */ |

374 | |

375 | template<class K, class V> |

376 | V* |

377 | fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key, |

378 | V *data) |

379 | { |

380 | K okey; |

381 | fibonacci_node<K,V> *y; |

382 | V *odata = node->m_data; |

383 | |

384 | /* If we wanted to, we do a real increase by redeleting and |

385 | inserting. */ |

386 | if (node->compare_data (key) > 0) |

387 | { |

388 | delete_node (node, false); |

389 | |

390 | node = new (node) fibonacci_node_t (); |

391 | insert (node, key, data); |

392 | |

393 | return odata; |

394 | } |

395 | |

396 | okey = node->m_key; |

397 | node->m_data = data; |

398 | node->m_key = key; |

399 | y = node->m_parent; |

400 | |

401 | /* Short-circuit if the key is the same, as we then don't have to |

402 | do anything. Except if we're trying to force the new node to |

403 | be the new minimum for delete. */ |

404 | if (okey == key && okey != m_global_min_key) |

405 | return odata; |

406 | |

407 | /* These two compares are specifically <= 0 to make sure that in the case |

408 | of equality, a node we replaced the data on, becomes the new min. This |

409 | is needed so that delete's call to extractmin gets the right node. */ |

410 | if (y != NULL && node->compare (y) <= 0) |

411 | { |

412 | cut (node, y); |

413 | cascading_cut (y); |

414 | } |

415 | |

416 | if (node->compare (m_min) <= 0) |

417 | m_min = node; |

418 | |

419 | return odata; |

420 | } |

421 | |

422 | /* Extract minimum node in the heap. Delete fibonacci node if RELEASE |

423 | is true. */ |

424 | |

425 | template<class K, class V> |

426 | V* |

427 | fibonacci_heap<K,V>::extract_min (bool release) |

428 | { |

429 | fibonacci_node<K,V> *z; |

430 | V *ret = NULL; |

431 | |

432 | /* If we don't have a min set, it means we have no nodes. */ |

433 | if (m_min != NULL) |

434 | { |

435 | /* Otherwise, extract the min node, free the node, and return the |

436 | node's data. */ |

437 | z = extract_minimum_node (); |

438 | ret = z->m_data; |

439 | |

440 | if (release) |

441 | delete (z); |

442 | } |

443 | |

444 | return ret; |

445 | } |

446 | |

447 | /* Delete NODE in the heap, if RELEASE is specified memory is released. */ |

448 | |

449 | template<class K, class V> |

450 | V* |

451 | fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release) |

452 | { |

453 | V *ret = node->m_data; |

454 | |

455 | /* To perform delete, we just make it the min key, and extract. */ |

456 | replace_key (node, m_global_min_key); |

457 | if (node != m_min) |

458 | { |

459 | fprintf (stderr, "Can't force minimum on fibheap.\n"); |

460 | abort (); |

461 | } |

462 | extract_min (release); |

463 | |

464 | return ret; |

465 | } |

466 | |

467 | /* Union the heap with HEAPB. One of the heaps is going to be deleted. */ |

468 | |

469 | template<class K, class V> |

470 | fibonacci_heap<K,V>* |

471 | fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb) |

472 | { |

473 | fibonacci_heap<K,V> *heapa = this; |

474 | |

475 | fibonacci_node<K,V> *a_root, *b_root; |

476 | |

477 | /* If one of the heaps is empty, the union is just the other heap. */ |

478 | if ((a_root = heapa->m_root) == NULL) |

479 | { |

480 | delete (heapa); |

481 | return heapb; |

482 | } |

483 | if ((b_root = heapb->m_root) == NULL) |

484 | { |

485 | delete (heapb); |

486 | return heapa; |

487 | } |

488 | |

489 | /* Merge them to the next nodes on the opposite chain. */ |

490 | a_root->m_left->m_right = b_root; |

491 | b_root->m_left->m_right = a_root; |

492 | std::swap (a_root->m_left, b_root->m_left); |

493 | heapa->m_nodes += heapb->m_nodes; |

494 | |

495 | /* And set the new minimum, if it's changed. */ |

496 | if (heapb->m_min->compare (heapa->m_min) < 0) |

497 | heapa->m_min = heapb->m_min; |

498 | |

499 | /* Set m_min to NULL to not to delete live fibonacci nodes. */ |

500 | heapb->m_min = NULL; |

501 | delete (heapb); |

502 | |

503 | return heapa; |

504 | } |

505 | |

506 | /* Insert it into the root list. */ |

507 | |

508 | template<class K, class V> |

509 | void |

510 | fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node) |

511 | { |

512 | /* If the heap is currently empty, the new node becomes the singleton |

513 | circular root list. */ |

514 | if (m_root == NULL) |

515 | { |

516 | m_root = node; |

517 | node->m_left = node; |

518 | node->m_right = node; |

519 | return; |

520 | } |

521 | |

522 | /* Otherwise, insert it in the circular root list between the root |

523 | and it's right node. */ |

524 | m_root->insert_after (node); |

525 | } |

526 | |

527 | /* Remove NODE from PARENT's child list. */ |

528 | |

529 | template<class K, class V> |

530 | void |

531 | fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node, |

532 | fibonacci_node<K,V> *parent) |

533 | { |

534 | node->remove (); |

535 | parent->m_degree--; |

536 | insert_root (node); |

537 | node->m_parent = NULL; |

538 | node->m_mark = 0; |

539 | } |

540 | |

541 | /* Process cut of node Y and do it recursivelly. */ |

542 | |

543 | template<class K, class V> |

544 | void |

545 | fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y) |

546 | { |

547 | fibonacci_node<K,V> *z; |

548 | |

549 | while ((z = y->m_parent) != NULL) |

550 | { |

551 | if (y->m_mark == 0) |

552 | { |

553 | y->m_mark = 1; |

554 | return; |

555 | } |

556 | else |

557 | { |

558 | cut (y, z); |

559 | y = z; |

560 | } |

561 | } |

562 | } |

563 | |

564 | /* Extract minimum node from the heap. */ |

565 | |

566 | template<class K, class V> |

567 | fibonacci_node<K,V>* |

568 | fibonacci_heap<K,V>::extract_minimum_node () |

569 | { |

570 | fibonacci_node<K,V> *ret = m_min; |

571 | fibonacci_node<K,V> *x, *y, *orig; |

572 | |

573 | /* Attach the child list of the minimum node to the root list of the heap. |

574 | If there is no child list, we don't do squat. */ |

575 | for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y) |

576 | { |

577 | if (orig == NULL) |

578 | orig = x; |

579 | y = x->m_right; |

580 | x->m_parent = NULL; |

581 | insert_root (x); |

582 | } |

583 | |

584 | /* Remove the old root. */ |

585 | remove_root (ret); |

586 | m_nodes--; |

587 | |

588 | /* If we are left with no nodes, then the min is NULL. */ |

589 | if (m_nodes == 0) |

590 | m_min = NULL; |

591 | else |

592 | { |

593 | /* Otherwise, consolidate to find new minimum, as well as do the reorg |

594 | work that needs to be done. */ |

595 | m_min = ret->m_right; |

596 | consolidate (); |

597 | } |

598 | |

599 | return ret; |

600 | } |

601 | |

602 | /* Remove root NODE from the heap. */ |

603 | |

604 | template<class K, class V> |

605 | void |

606 | fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node) |

607 | { |

608 | if (node->m_left == node) |

609 | m_root = NULL; |

610 | else |

611 | m_root = node->remove (); |

612 | } |

613 | |

614 | /* Consolidate heap. */ |

615 | |

616 | template<class K, class V> |

617 | void fibonacci_heap<K,V>::consolidate () |

618 | { |

619 | int D = 1 + 8 * sizeof (long); |

620 | auto_vec<fibonacci_node<K,V> *> a (D); |

621 | a.safe_grow_cleared (D); |

622 | fibonacci_node<K,V> *w, *x, *y; |

623 | int i, d; |

624 | |

625 | while ((w = m_root) != NULL) |

626 | { |

627 | x = w; |

628 | remove_root (w); |

629 | d = x->m_degree; |

630 | while (a[d] != NULL) |

631 | { |

632 | y = a[d]; |

633 | if (x->compare (y) > 0) |

634 | std::swap (x, y); |

635 | y->link (x); |

636 | a[d] = NULL; |

637 | d++; |

638 | } |

639 | a[d] = x; |

640 | } |

641 | m_min = NULL; |

642 | for (i = 0; i < D; i++) |

643 | if (a[i] != NULL) |

644 | { |

645 | insert_root (a[i]); |

646 | if (m_min == NULL || a[i]->compare (m_min) < 0) |

647 | m_min = a[i]; |

648 | } |

649 | } |

650 | |

651 | #endif // GCC_FIBONACCI_HEAP_H |

652 |