1151497Sru/* A Fibonacci heap datatype. 2151497Sru Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc. 3151497Sru Contributed by Daniel Berlin (dan@cgsoftware.com). 4151497Sru 5151497SruThis file is part of GNU CC. 6151497Sru 7151497SruGNU CC is free software; you can redistribute it and/or modify it 8151497Sruunder the terms of the GNU General Public License as published by 9151497Sruthe Free Software Foundation; either version 2, or (at your option) 10151497Sruany later version. 11151497Sru 12151497SruGNU CC is distributed in the hope that it will be useful, but 13151497SruWITHOUT ANY WARRANTY; without even the implied warranty of 14151497SruMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15151497SruGeneral Public License for more details. 16151497Sru 17151497SruYou should have received a copy of the GNU General Public License 18151497Srualong with GNU CC; see the file COPYING. If not, write to 19151497Sruthe Free Software Foundation, 51 Franklin Street - Fifth Floor, 20151497SruBoston, MA 02110-1301, USA. */ 21151497Sru 22151497Sru#ifdef HAVE_CONFIG_H 23151497Sru#include "config.h" 24151497Sru#endif 25151497Sru#ifdef HAVE_LIMITS_H 26151497Sru#include <limits.h> 27151497Sru#endif 28151497Sru#ifdef HAVE_STDLIB_H 29151497Sru#include <stdlib.h> 30151497Sru#endif 31151497Sru#ifdef HAVE_STRING_H 32151497Sru#include <string.h> 33151497Sru#endif 34151497Sru#include "libiberty.h" 35151497Sru#include "fibheap.h" 36151497Sru 37151497Sru 38151497Sru#define FIBHEAPKEY_MIN LONG_MIN 39151497Sru 40151497Srustatic void fibheap_ins_root (fibheap_t, fibnode_t); 41151497Srustatic void fibheap_rem_root (fibheap_t, fibnode_t); 42151497Srustatic void fibheap_consolidate (fibheap_t); 43151497Srustatic void fibheap_link (fibheap_t, fibnode_t, fibnode_t); 44151497Srustatic void fibheap_cut (fibheap_t, fibnode_t, fibnode_t); 45151497Srustatic void fibheap_cascading_cut (fibheap_t, fibnode_t); 46151497Srustatic fibnode_t fibheap_extr_min_node (fibheap_t); 47151497Srustatic int fibheap_compare (fibheap_t, fibnode_t, fibnode_t); 48151497Srustatic int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t); 49151497Srustatic fibnode_t fibnode_new (void); 50151497Srustatic void fibnode_insert_after (fibnode_t, fibnode_t); 51151497Sru#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b) 52151497Srustatic fibnode_t fibnode_remove (fibnode_t); 53151497Sru 54151497Sru 55151497Sru/* Create a new fibonacci heap. */ 56151497Srufibheap_t 57151497Srufibheap_new (void) 58151497Sru{ 59151497Sru return (fibheap_t) xcalloc (1, sizeof (struct fibheap)); 60151497Sru} 61151497Sru 62151497Sru/* Create a new fibonacci heap node. */ 63151497Srustatic fibnode_t 64151497Srufibnode_new (void) 65151497Sru{ 66151497Sru fibnode_t node; 67151497Sru 68151497Sru node = (fibnode_t) xcalloc (1, sizeof *node); 69151497Sru node->left = node; 70151497Sru node->right = node; 71151497Sru 72151497Sru return node; 73151497Sru} 74151497Sru 75151497Srustatic inline int 76151497Srufibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b) 77151497Sru{ 78151497Sru if (a->key < b->key) 79151497Sru return -1; 80151497Sru if (a->key > b->key) 81151497Sru return 1; 82151497Sru return 0; 83151497Sru} 84151497Sru 85151497Srustatic inline int 86151497Srufibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b) 87151497Sru{ 88151497Sru struct fibnode a; 89151497Sru 90151497Sru a.key = key; 91151497Sru a.data = data; 92151497Sru 93151497Sru return fibheap_compare (heap, &a, b); 94151497Sru} 95151497Sru 96151497Sru/* Insert DATA, with priority KEY, into HEAP. */ 97151497Srufibnode_t 98151497Srufibheap_insert (fibheap_t heap, fibheapkey_t key, void *data) 99151497Sru{ 100151497Sru fibnode_t node; 101151497Sru 102151497Sru /* Create the new node. */ 103151497Sru node = fibnode_new (); 104151497Sru 105151497Sru /* Set the node's data. */ 106151497Sru node->data = data; 107151497Sru node->key = key; 108151497Sru 109151497Sru /* Insert it into the root list. */ 110151497Sru fibheap_ins_root (heap, node); 111151497Sru 112151497Sru /* If their was no minimum, or this key is less than the min, 113151497Sru it's the new min. */ 114151497Sru if (heap->min == NULL || node->key < heap->min->key) 115151497Sru heap->min = node; 116151497Sru 117151497Sru heap->nodes++; 118151497Sru 119151497Sru return node; 120151497Sru} 121151497Sru 122151497Sru/* Return the data of the minimum node (if we know it). */ 123151497Sruvoid * 124151497Srufibheap_min (fibheap_t heap) 125151497Sru{ 126151497Sru /* If there is no min, we can't easily return it. */ 127151497Sru if (heap->min == NULL) 128151497Sru return NULL; 129151497Sru return heap->min->data; 130151497Sru} 131151497Sru 132151497Sru/* Return the key of the minimum node (if we know it). */ 133151497Srufibheapkey_t 134151497Srufibheap_min_key (fibheap_t heap) 135151497Sru{ 136151497Sru /* If there is no min, we can't easily return it. */ 137151497Sru if (heap->min == NULL) 138151497Sru return 0; 139151497Sru return heap->min->key; 140151497Sru} 141151497Sru 142151497Sru/* Union HEAPA and HEAPB into a new heap. */ 143151497Srufibheap_t 144151497Srufibheap_union (fibheap_t heapa, fibheap_t heapb) 145151497Sru{ 146151497Sru fibnode_t a_root, b_root, temp; 147151497Sru 148151497Sru /* If one of the heaps is empty, the union is just the other heap. */ 149151497Sru if ((a_root = heapa->root) == NULL) 150151497Sru { 151151497Sru free (heapa); 152151497Sru return heapb; 153151497Sru } 154151497Sru if ((b_root = heapb->root) == NULL) 155151497Sru { 156151497Sru free (heapb); 157151497Sru return heapa; 158151497Sru } 159151497Sru 160151497Sru /* Merge them to the next nodes on the opposite chain. */ 161151497Sru a_root->left->right = b_root; 162151497Sru b_root->left->right = a_root; 163151497Sru temp = a_root->left; 164151497Sru a_root->left = b_root->left; 165151497Sru b_root->left = temp; 166151497Sru heapa->nodes += heapb->nodes; 167151497Sru 168151497Sru /* And set the new minimum, if it's changed. */ 169151497Sru if (fibheap_compare (heapa, heapb->min, heapa->min) < 0) 170151497Sru heapa->min = heapb->min; 171151497Sru 172151497Sru free (heapb); 173151497Sru return heapa; 174151497Sru} 175151497Sru 176151497Sru/* Extract the data of the minimum node from HEAP. */ 177151497Sruvoid * 178151497Srufibheap_extract_min (fibheap_t heap) 179151497Sru{ 180151497Sru fibnode_t z; 181151497Sru void *ret = NULL; 182151497Sru 183151497Sru /* If we don't have a min set, it means we have no nodes. */ 184151497Sru if (heap->min != NULL) 185151497Sru { 186151497Sru /* Otherwise, extract the min node, free the node, and return the 187151497Sru node's data. */ 188151497Sru z = fibheap_extr_min_node (heap); 189151497Sru ret = z->data; 190151497Sru free (z); 191151497Sru } 192151497Sru 193151497Sru return ret; 194151497Sru} 195151497Sru 196151497Sru/* Replace both the KEY and the DATA associated with NODE. */ 197151497Sruvoid * 198151497Srufibheap_replace_key_data (fibheap_t heap, fibnode_t node, 199151497Sru fibheapkey_t key, void *data) 200151497Sru{ 201151497Sru void *odata; 202151497Sru fibheapkey_t okey; 203151497Sru fibnode_t y; 204151497Sru 205151497Sru /* If we wanted to, we could actually do a real increase by redeleting and 206151497Sru inserting. However, this would require O (log n) time. So just bail out 207151497Sru for now. */ 208151497Sru if (fibheap_comp_data (heap, key, data, node) > 0) 209151497Sru return NULL; 210151497Sru 211151497Sru odata = node->data; 212151497Sru okey = node->key; 213151497Sru node->data = data; 214151497Sru node->key = key; 215151497Sru y = node->parent; 216151497Sru 217151497Sru /* Short-circuit if the key is the same, as we then don't have to 218151497Sru do anything. Except if we're trying to force the new node to 219151497Sru be the new minimum for delete. */ 220151497Sru if (okey == key && okey != FIBHEAPKEY_MIN) 221151497Sru return odata; 222151497Sru 223151497Sru /* These two compares are specifically <= 0 to make sure that in the case 224151497Sru of equality, a node we replaced the data on, becomes the new min. This 225151497Sru is needed so that delete's call to extractmin gets the right node. */ 226151497Sru if (y != NULL && fibheap_compare (heap, node, y) <= 0) 227151497Sru { 228151497Sru fibheap_cut (heap, node, y); 229151497Sru fibheap_cascading_cut (heap, y); 230151497Sru } 231151497Sru 232151497Sru if (fibheap_compare (heap, node, heap->min) <= 0) 233151497Sru heap->min = node; 234151497Sru 235151497Sru return odata; 236151497Sru} 237151497Sru 238151497Sru/* Replace the DATA associated with NODE. */ 239151497Sruvoid * 240151497Srufibheap_replace_data (fibheap_t heap, fibnode_t node, void *data) 241151497Sru{ 242151497Sru return fibheap_replace_key_data (heap, node, node->key, data); 243151497Sru} 244151497Sru 245151497Sru/* Replace the KEY associated with NODE. */ 246151497Srufibheapkey_t 247151497Srufibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key) 248151497Sru{ 249151497Sru int okey = node->key; 250151497Sru fibheap_replace_key_data (heap, node, key, node->data); 251151497Sru return okey; 252151497Sru} 253151497Sru 254151497Sru/* Delete NODE from HEAP. */ 255151497Sruvoid * 256151497Srufibheap_delete_node (fibheap_t heap, fibnode_t node) 257151497Sru{ 258151497Sru void *ret = node->data; 259151497Sru 260151497Sru /* To perform delete, we just make it the min key, and extract. */ 261151497Sru fibheap_replace_key (heap, node, FIBHEAPKEY_MIN); 262151497Sru if (node != heap->min) 263151497Sru { 264151497Sru fprintf (stderr, "Can't force minimum on fibheap.\n"); 265151497Sru abort (); 266151497Sru } 267151497Sru fibheap_extract_min (heap); 268151497Sru 269151497Sru return ret; 270151497Sru} 271151497Sru 272151497Sru/* Delete HEAP. */ 273151497Sruvoid 274151497Srufibheap_delete (fibheap_t heap) 275151497Sru{ 276151497Sru while (heap->min != NULL) 277151497Sru free (fibheap_extr_min_node (heap)); 278151497Sru 279151497Sru free (heap); 280151497Sru} 281151497Sru 282151497Sru/* Determine if HEAP is empty. */ 283151497Sruint 284151497Srufibheap_empty (fibheap_t heap) 285151497Sru{ 286151497Sru return heap->nodes == 0; 287151497Sru} 288151497Sru 289151497Sru/* Extract the minimum node of the heap. */ 290151497Srustatic fibnode_t 291151497Srufibheap_extr_min_node (fibheap_t heap) 292151497Sru{ 293151497Sru fibnode_t ret = heap->min; 294151497Sru fibnode_t x, y, orig; 295151497Sru 296151497Sru /* Attach the child list of the minimum node to the root list of the heap. 297151497Sru If there is no child list, we don't do squat. */ 298151497Sru for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y) 299151497Sru { 300151497Sru if (orig == NULL) 301151497Sru orig = x; 302151497Sru y = x->right; 303151497Sru x->parent = NULL; 304151497Sru fibheap_ins_root (heap, x); 305151497Sru } 306151497Sru 307151497Sru /* Remove the old root. */ 308151497Sru fibheap_rem_root (heap, ret); 309151497Sru heap->nodes--; 310151497Sru 311151497Sru /* If we are left with no nodes, then the min is NULL. */ 312151497Sru if (heap->nodes == 0) 313151497Sru heap->min = NULL; 314151497Sru else 315151497Sru { 316151497Sru /* Otherwise, consolidate to find new minimum, as well as do the reorg 317151497Sru work that needs to be done. */ 318151497Sru heap->min = ret->right; 319151497Sru fibheap_consolidate (heap); 320151497Sru } 321151497Sru 322151497Sru return ret; 323151497Sru} 324151497Sru 325151497Sru/* Insert NODE into the root list of HEAP. */ 326151497Srustatic void 327151497Srufibheap_ins_root (fibheap_t heap, fibnode_t node) 328151497Sru{ 329151497Sru /* If the heap is currently empty, the new node becomes the singleton 330151497Sru circular root list. */ 331151497Sru if (heap->root == NULL) 332151497Sru { 333151497Sru heap->root = node; 334151497Sru node->left = node; 335151497Sru node->right = node; 336151497Sru return; 337151497Sru } 338151497Sru 339151497Sru /* Otherwise, insert it in the circular root list between the root 340151497Sru and it's right node. */ 341151497Sru fibnode_insert_after (heap->root, node); 342151497Sru} 343151497Sru 344151497Sru/* Remove NODE from the rootlist of HEAP. */ 345151497Srustatic void 346151497Srufibheap_rem_root (fibheap_t heap, fibnode_t node) 347151497Sru{ 348151497Sru if (node->left == node) 349151497Sru heap->root = NULL; 350151497Sru else 351151497Sru heap->root = fibnode_remove (node); 352151497Sru} 353151497Sru 354151497Sru/* Consolidate the heap. */ 355151497Srustatic void 356151497Srufibheap_consolidate (fibheap_t heap) 357151497Sru{ 358151497Sru fibnode_t a[1 + 8 * sizeof (long)]; 359151497Sru fibnode_t w; 360151497Sru fibnode_t y; 361151497Sru fibnode_t x; 362151497Sru int i; 363151497Sru int d; 364151497Sru int D; 365151497Sru 366151497Sru D = 1 + 8 * sizeof (long); 367151497Sru 368151497Sru memset (a, 0, sizeof (fibnode_t) * D); 369151497Sru 370151497Sru while ((w = heap->root) != NULL) 371151497Sru { 372151497Sru x = w; 373151497Sru fibheap_rem_root (heap, w); 374151497Sru d = x->degree; 375151497Sru while (a[d] != NULL) 376151497Sru { 377151497Sru y = a[d]; 378151497Sru if (fibheap_compare (heap, x, y) > 0) 379151497Sru { 380151497Sru fibnode_t temp; 381151497Sru temp = x; 382151497Sru x = y; 383151497Sru y = temp; 384151497Sru } 385151497Sru fibheap_link (heap, y, x); 386151497Sru a[d] = NULL; 387151497Sru d++; 388151497Sru } 389151497Sru a[d] = x; 390151497Sru } 391151497Sru heap->min = NULL; 392151497Sru for (i = 0; i < D; i++) 393151497Sru if (a[i] != NULL) 394151497Sru { 395151497Sru fibheap_ins_root (heap, a[i]); 396151497Sru if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0) 397151497Sru heap->min = a[i]; 398151497Sru } 399151497Sru} 400151497Sru 401151497Sru/* Make NODE a child of PARENT. */ 402151497Srustatic void 403151497Srufibheap_link (fibheap_t heap ATTRIBUTE_UNUSED, 404151497Sru fibnode_t node, fibnode_t parent) 405151497Sru{ 406151497Sru if (parent->child == NULL) 407151497Sru parent->child = node; 408151497Sru else 409151497Sru fibnode_insert_before (parent->child, node); 410151497Sru node->parent = parent; 411151497Sru parent->degree++; 412151497Sru node->mark = 0; 413151497Sru} 414151497Sru 415151497Sru/* Remove NODE from PARENT's child list. */ 416151497Srustatic void 417151497Srufibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent) 418151497Sru{ 419151497Sru fibnode_remove (node); 420151497Sru parent->degree--; 421151497Sru fibheap_ins_root (heap, node); 422151497Sru node->parent = NULL; 423151497Sru node->mark = 0; 424151497Sru} 425151497Sru 426151497Srustatic void 427151497Srufibheap_cascading_cut (fibheap_t heap, fibnode_t y) 428151497Sru{ 429151497Sru fibnode_t z; 430151497Sru 431151497Sru while ((z = y->parent) != NULL) 432151497Sru { 433151497Sru if (y->mark == 0) 434151497Sru { 435151497Sru y->mark = 1; 436151497Sru return; 437151497Sru } 438151497Sru else 439151497Sru { 440151497Sru fibheap_cut (heap, y, z); 441151497Sru y = z; 442151497Sru } 443151497Sru } 444151497Sru} 445151497Sru 446151497Srustatic void 447151497Srufibnode_insert_after (fibnode_t a, fibnode_t b) 448151497Sru{ 449151497Sru if (a == a->right) 450151497Sru { 451151497Sru a->right = b; 452151497Sru a->left = b; 453151497Sru b->right = a; 454151497Sru b->left = a; 455151497Sru } 456151497Sru else 457151497Sru { 458151497Sru b->right = a->right; 459151497Sru a->right->left = b; 460151497Sru a->right = b; 461151497Sru b->left = a; 462151497Sru } 463151497Sru} 464151497Sru 465151497Srustatic fibnode_t 466151497Srufibnode_remove (fibnode_t node) 467151497Sru{ 468151497Sru fibnode_t ret; 469151497Sru 470151497Sru if (node == node->left) 471151497Sru ret = NULL; 472151497Sru else 473151497Sru ret = node->left; 474151497Sru 475151497Sru if (node->parent != NULL && node->parent->child == node) 476151497Sru node->parent->child = ret; 477151497Sru 478151497Sru node->right->left = node->left; 479151497Sru node->left->right = node->right; 480151497Sru 481151497Sru node->parent = NULL; 482151497Sru node->left = node; 483151497Sru node->right = node; 484151497Sru 485151497Sru return ret; 486151497Sru} 487151497Sru