BGI/SOAPdenovo2/standardPregraph/fib.c

   1 /*
   2  * fib.c
   3  *
   4  * This file is part of SOAPdenovo.
   5  *
   6  */
   7
   8 /*-
   9  * Copyright 1997-2003 John-Mark Gurney.
  10  * All rights reserved.
  11  *
  12  * Redistribution and use in source and binary forms, with or without
  13  * modification, are permitted provided that the following conditions
  14  * are met:
  15  * 1. Redistributions of source code must retain the above copyright
  16  *    notice, this list of conditions and the following disclaimer.
  17  * 2. Redistributions in binary form must reproduce the above copyright
  18  *    notice, this list of conditions and the following disclaimer in the
  19  *    documentation and/or other materials provided with the distribution.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  *  $Id: fib.c,v 1.10 2007/10/19 13:09:26 zerbino Exp $
  34  *
  35  */
  36 #include <limits.h>
  37 #include <stdlib.h>
  38 #include "fib.h"
  39 #include "fibpriv.h"
  40 #include "extfunc2.h"
  41
  42 #define HEAPBLOCKSIZE 10000
  43
  44 static int fh_comparedata ( FibHeap * h, Coordinate key, unsigned int data, FibHeapNode * b );
  45 unsigned int fh_replacekeydata ( FibHeap * h, FibHeapNode * x, Coordinate key, unsigned int data );
  46
  47 static FibHeapNode * allocateFibHeapEl ( FibHeap * heap )
  48 {
  49         return ( FibHeapNode * ) getItem ( heap->nodeMemory );
  50 };
  51
  52 static void deallocateFibHeapEl ( FibHeapNode * a, FibHeap * heap )
  53 {
  54         returnItem ( heap->nodeMemory, a );
  55 }
  56
  57 #define swap(type, a, b)        \
  58         do {            \
  59                 type c;     \
  60                 c = a;      \
  61                 a = b;      \
  62                 b = c;      \
  63         } while (0)     \
  64
  65 #define INT_BITS        (sizeof(IDnum) * 8)
  66
  67 static inline IDnum ceillog2 ( IDnum a )
  68 {
  69         IDnum oa;
  70         IDnum i;
  71         IDnum b;
  72         IDnum cons;
  73         oa = a;
  74         b = INT_BITS / 2;
  75         i = 0;
  76
  77         while ( b )
  78         {
  79                 i = ( i << 1 );
  80                 cons = ( ( IDnum ) 1 ) << b;
  81
  82                 if ( a >= cons )
  83                 {
  84                         a /= cons;
  85                         i = i | 1;
  86                 }
  87                 else
  88                 {
  89                         a &= cons - 1;
  90                 }
  91
  92                 b /= 2;
  93         }
  94
  95         if ( ( ( ( IDnum ) 1 << i ) ) == oa )
  96         {
  97                 return i;
  98         }
  99         else
 100         {
 101                 return i + 1;
 102         }
 103 }
 104
 105 /*
 106  * Private Heap Functions
 107  */
 108 static void fh_initheap ( FibHeap * new )
 109 {
 110         new->fh_cmp_fnct = NULL;
 111         new->nodeMemory = createMem_manager ( sizeof ( FibHeapNode ), HEAPBLOCKSIZE );
 112         new->fh_neginf = 0;
 113         new->fh_n = 0;
 114         new->fh_Dl = -1;
 115         new->fh_cons = NULL;
 116         new->fh_min = NULL;
 117         new->fh_root = NULL;
 118         new->fh_keys = 0;
 119 }
 120
 121 static void fh_destroyheap ( FibHeap * h )
 122 {
 123         h->fh_cmp_fnct = NULL;
 124         h->fh_neginf = 0;
 125
 126         if ( h->fh_cons != NULL )
 127         {
 128                 free ( h->fh_cons );
 129         }
 130
 131         h->fh_cons = NULL;
 132         free ( h );
 133 }
 134
 135 /*
 136  * Public Heap Functions
 137  */
 138 FibHeap * fh_makekeyheap ()
 139 {
 140         FibHeap * n;
 141
 142         if ( ( n = malloc ( sizeof * n ) ) == NULL )
 143         {
 144                 return NULL;
 145         }
 146
 147         fh_initheap ( n );
 148         n->fh_keys = 1;
 149         return n;
 150 }
 151
 152 FibHeap * fh_makeheap ()
 153 {
 154         FibHeap * n;
 155
 156         if ( ( n = malloc ( sizeof * n ) ) == NULL )
 157         {
 158                 return NULL;
 159         }
 160
 161         fh_initheap ( n );
 162         return n;
 163 }
 164
 165 voidcmp fh_setcmp ( FibHeap * h, voidcmp fnct )
 166 {
 167         voidcmp oldfnct;
 168         oldfnct = h->fh_cmp_fnct;
 169         h->fh_cmp_fnct = fnct;
 170         return oldfnct;
 171 }
 172
 173 unsigned int fh_setneginf ( FibHeap * h, unsigned int data )
 174 {
 175         unsigned int old;
 176         old = h->fh_neginf;
 177         h->fh_neginf = data;
 178         return old;
 179 }
 180
 181 FibHeap * fh_union ( FibHeap * ha, FibHeap * hb )
 182 {
 183         FibHeapNode * x;
 184
 185         if ( ha->fh_root == NULL || hb->fh_root == NULL )
 186         {
 187                 /* either one or both are empty */
 188                 if ( ha->fh_root == NULL )
 189                 {
 190                         fh_destroyheap ( ha );
 191                         return hb;
 192                 }
 193                 else
 194                 {
 195                         fh_destroyheap ( hb );
 196                         return ha;
 197                 }
 198         }
 199
 200         ha->fh_root->fhe_left->fhe_right = hb->fh_root;
 201         hb->fh_root->fhe_left->fhe_right = ha->fh_root;
 202         x = ha->fh_root->fhe_left;
 203         ha->fh_root->fhe_left = hb->fh_root->fhe_left;
 204         hb->fh_root->fhe_left = x;
 205         ha->fh_n += hb->fh_n;
 206         /*
 207          * we probably should also keep stats on number of unions
 208          */
 209
 210         /* set fh_min if necessary */
 211         if ( fh_compare ( ha, hb->fh_min, ha->fh_min ) < 0 )
 212         {
 213                 ha->fh_min = hb->fh_min;
 214         }
 215
 216         fh_destroyheap ( hb );
 217         return ha;
 218 }
 219
 220 void fh_deleteheap ( FibHeap * h )
 221 {
 222         freeMem_manager ( h->nodeMemory );
 223         h->nodeMemory = NULL;
 224         fh_destroyheap ( h );
 225 }
 226
 227 /*
 228  * Public Key Heap Functions
 229  */
 230 FibHeapNode * fh_insertkey ( FibHeap * h, Coordinate key, unsigned int data )
 231 {
 232         FibHeapNode * x;
 233
 234         if ( ( x = fhe_newelem ( h ) ) == NULL )
 235         {
 236                 return NULL;
 237         }
 238
 239         /* just insert on root list, and make sure it's not the new min */
 240         x->fhe_data = data;
 241         x->fhe_key = key;
 242         fh_insertel ( h, x );
 243         return x;
 244 }
 245
 246 boolean fh_isempty ( FibHeap * h )
 247 {
 248         if ( h->fh_min == NULL )
 249         {
 250                 return 1;
 251         }
 252         else
 253         {
 254                 return 0;
 255         }
 256 }
 257
 258 Coordinate fh_minkey ( FibHeap * h )
 259 {
 260         if ( h->fh_min == NULL )
 261         {
 262                 return INT_MIN;
 263         }
 264
 265         return h->fh_min->fhe_key;
 266 }
 267
 268 unsigned int fh_replacekeydata ( FibHeap * h, FibHeapNode * x, Coordinate key, unsigned int data )
 269 {
 270         unsigned int odata;
 271         Coordinate okey;
 272         FibHeapNode * y;
 273         int r;
 274         odata = x->fhe_data;
 275         okey = x->fhe_key;
 276
 277         /*
 278          * we can increase a key by deleting and reinserting, that
 279          * requires O(lgn) time.
 280          */
 281         if ( ( r = fh_comparedata ( h, key, data, x ) ) > 0 )
 282         {
 283                 /* XXX - bad code! */
 284                 abort ();
 285         }
 286
 287         x->fhe_data = data;
 288         x->fhe_key = key;
 289
 290         /* because they are equal, we don't have to do anything */
 291         if ( r == 0 )
 292         {
 293                 return odata;
 294         }
 295
 296         y = x->fhe_p;
 297
 298         if ( h->fh_keys && okey == key )
 299         {
 300                 return odata;
 301         }
 302
 303         if ( y != NULL && fh_compare ( h, x, y ) <= 0 )
 304         {
 305                 fh_cut ( h, x, y );
 306                 fh_cascading_cut ( h, y );
 307         }
 308
 309         /*
 310          * the = is so that the call from fh_delete will delete the proper
 311          * element.
 312          */
 313         if ( fh_compare ( h, x, h->fh_min ) <= 0 )
 314         {
 315                 h->fh_min = x;
 316         }
 317
 318         return odata;
 319 }
 320
 321 Coordinate fh_replacekey ( FibHeap * h, FibHeapNode * x, Coordinate key )
 322 {
 323         Coordinate ret;
 324         ret = x->fhe_key;
 325         ( void ) fh_replacekeydata ( h, x, key, x->fhe_data );
 326         return ret;
 327 }
 328
 329 /*
 330  * Public void * Heap Functions
 331  */
 332 /*
 333  * this will return these values:
 334  *  NULL    failed for some reason
 335  *  ptr token to use for manipulation of data
 336  */
 337 FibHeapNode * fh_insert ( FibHeap * h, unsigned int data )
 338 {
 339         FibHeapNode * x;
 340
 341         if ( ( x = fhe_newelem ( h ) ) == NULL )
 342         {
 343                 return NULL;
 344         }
 345
 346         /* just insert on root list, and make sure it's not the new min */
 347         x->fhe_data = data;
 348         fh_insertel ( h, x );
 349         return x;
 350 }
 351
 352 unsigned int fh_min ( FibHeap * h )
 353 {
 354         if ( h->fh_min == NULL )
 355         {
 356                 return 0;
 357         }
 358
 359         return h->fh_min->fhe_data;
 360 }
 361
 362 unsigned int fh_extractmin ( FibHeap * h )
 363 {
 364         FibHeapNode * z;
 365         unsigned int ret = 0;
 366
 367         if ( h->fh_min != NULL )
 368         {
 369                 z = fh_extractminel ( h );
 370                 ret = z->fhe_data;
 371 #ifndef NO_FREE
 372                 deallocateFibHeapEl ( z, h );
 373 #endif
 374         }
 375
 376         return ret;
 377 }
 378
 379 unsigned int fh_replacedata ( FibHeapNode * x, unsigned int data )
 380 {
 381         unsigned int odata = x->fhe_data;
 382         x->fhe_data = data;
 383         return odata;
 384 }
 385
 386 unsigned int fh_delete ( FibHeap * h, FibHeapNode * x )
 387 {
 388         unsigned int k;
 389         k = x->fhe_data;
 390
 391         if ( !h->fh_keys )
 392         {
 393                 fh_replacedata ( x, h->fh_neginf );
 394         }
 395         else
 396         {
 397                 fh_replacekey ( h, x, INT_MIN );
 398         }
 399
 400         fh_extractmin ( h );
 401         return k;
 402 }
 403
 404 /*
 405  * begin of private element fuctions
 406  */
 407 static FibHeapNode * fh_extractminel ( FibHeap * h )
 408 {
 409         FibHeapNode * ret;
 410         FibHeapNode * x, *y, *orig;
 411         ret = h->fh_min;
 412         orig = NULL;
 413
 414         /* put all the children on the root list */
 415         /* for true consistancy, we should use fhe_remove */
 416         for ( x = ret->fhe_child; x != orig && x != NULL; )
 417         {
 418                 if ( orig == NULL )
 419                 {
 420                         orig = x;
 421                 }
 422
 423                 y = x->fhe_right;
 424                 x->fhe_p = NULL;
 425                 fh_insertrootlist ( h, x );
 426                 x = y;
 427         }
 428
 429         /* remove minimum from root list */
 430         fh_removerootlist ( h, ret );
 431         h->fh_n--;
 432
 433         /* if we aren't empty, consolidate the heap */
 434         if ( h->fh_n == 0 )
 435         {
 436                 h->fh_min = NULL;
 437         }
 438         else
 439         {
 440                 h->fh_min = ret->fhe_right;
 441                 fh_consolidate ( h );
 442         }
 443
 444         return ret;
 445 }
 446
 447 static void fh_insertrootlist ( FibHeap * h, FibHeapNode * x )
 448 {
 449         if ( h->fh_root == NULL )
 450         {
 451                 h->fh_root = x;
 452                 x->fhe_left = x;
 453                 x->fhe_right = x;
 454                 return;
 455         }
 456
 457         fhe_insertafter ( h->fh_root, x );
 458 }
 459
 460 static void fh_removerootlist ( FibHeap * h, FibHeapNode * x )
 461 {
 462         if ( x->fhe_left == x )
 463         {
 464                 h->fh_root = NULL;
 465         }
 466         else
 467         {
 468                 h->fh_root = fhe_remove ( x );
 469         }
 470 }
 471
 472 static void fh_consolidate ( FibHeap * h )
 473 {
 474         FibHeapNode ** a;
 475         FibHeapNode * w;
 476         FibHeapNode * y;
 477         FibHeapNode * x;
 478         IDnum i;
 479         IDnum d;
 480         IDnum D;
 481         fh_checkcons ( h );
 482         /* assign a the value of h->fh_cons so I don't have to rewrite code */
 483         D = h->fh_Dl + 1;
 484         a = h->fh_cons;
 485
 486         for ( i = 0; i < D; i++ )
 487         {
 488                 a[i] = NULL;
 489         }
 490
 491         while ( ( w = h->fh_root ) != NULL )
 492         {
 493                 x = w;
 494                 fh_removerootlist ( h, w );
 495                 d = x->fhe_degree;
 496
 497                 /* XXX - assert that d < D */
 498                 while ( a[d] != NULL )
 499                 {
 500                         y = a[d];
 501
 502                         if ( fh_compare ( h, x, y ) > 0 )
 503                         {
 504                                 swap ( FibHeapNode *, x, y );
 505                         }
 506
 507                         fh_heaplink ( h, y, x );
 508                         a[d] = NULL;
 509                         d++;
 510                 }
 511
 512                 a[d] = x;
 513         }
 514
 515         h->fh_min = NULL;
 516
 517         for ( i = 0; i < D; i++ )
 518                 if ( a[i] != NULL )
 519                 {
 520                         fh_insertrootlist ( h, a[i] );
 521
 522                         if ( h->fh_min == NULL || fh_compare ( h, a[i], h->fh_min ) < 0 )
 523                         {
 524                                 h->fh_min = a[i];
 525                         }
 526                 }
 527 }
 528
 529 static void fh_heaplink ( FibHeap * h, FibHeapNode * y, FibHeapNode * x )
 530 {
 531         /* make y a child of x */
 532         if ( x->fhe_child == NULL )
 533         {
 534                 x->fhe_child = y;
 535         }
 536         else
 537         {
 538                 fhe_insertbefore ( x->fhe_child, y );
 539         }
 540
 541         y->fhe_p = x;
 542         x->fhe_degree++;
 543         y->fhe_mark = 0;
 544 }
 545
 546 static void fh_cut ( FibHeap * h, FibHeapNode * x, FibHeapNode * y )
 547 {
 548         fhe_remove ( x );
 549         y->fhe_degree--;
 550         fh_insertrootlist ( h, x );
 551         x->fhe_p = NULL;
 552         x->fhe_mark = 0;
 553 }
 554
 555 static void fh_cascading_cut ( FibHeap * h, FibHeapNode * y )
 556 {
 557         FibHeapNode * z;
 558
 559         while ( ( z = y->fhe_p ) != NULL )
 560         {
 561                 if ( y->fhe_mark == 0 )
 562                 {
 563                         y->fhe_mark = 1;
 564                         return;
 565                 }
 566                 else
 567                 {
 568                         fh_cut ( h, y, z );
 569                         y = z;
 570                 }
 571         }
 572 }
 573
 574 /*
 575  * begining of handling elements of fibheap
 576  */
 577 static FibHeapNode * fhe_newelem ( FibHeap * h )
 578 {
 579         FibHeapNode * e;
 580
 581         if ( ( e = allocateFibHeapEl ( h ) ) == NULL )
 582         {
 583                 return NULL;
 584         }
 585
 586         fhe_initelem ( e );
 587         return e;
 588 }
 589
 590 static void fhe_initelem ( FibHeapNode * e )
 591 {
 592         e->fhe_degree = 0;
 593         e->fhe_mark = 0;
 594         e->fhe_p = NULL;
 595         e->fhe_child = NULL;
 596         e->fhe_left = e;
 597         e->fhe_right = e;
 598         e->fhe_data = 0;
 599 }
 600
 601 static void fhe_insertafter ( FibHeapNode * a, FibHeapNode * b )
 602 {
 603         if ( a == a->fhe_right )
 604         {
 605                 a->fhe_right = b;
 606                 a->fhe_left = b;
 607                 b->fhe_right = a;
 608                 b->fhe_left = a;
 609         }
 610         else
 611         {
 612                 b->fhe_right = a->fhe_right;
 613                 a->fhe_right->fhe_left = b;
 614                 a->fhe_right = b;
 615                 b->fhe_left = a;
 616         }
 617 }
 618
 619 static inline void fhe_insertbefore ( FibHeapNode * a, FibHeapNode * b )
 620 {
 621         fhe_insertafter ( a->fhe_left, b );
 622 }
 623
 624 static FibHeapNode * fhe_remove ( FibHeapNode * x )
 625 {
 626         FibHeapNode * ret;
 627
 628         if ( x == x->fhe_left )
 629         {
 630                 ret = NULL;
 631         }
 632         else
 633         {
 634                 ret = x->fhe_left;
 635         }
 636
 637         /* fix the parent pointer */
 638         if ( x->fhe_p != NULL && x->fhe_p->fhe_child == x )
 639         {
 640                 x->fhe_p->fhe_child = ret;
 641         }
 642
 643         x->fhe_right->fhe_left = x->fhe_left;
 644         x->fhe_left->fhe_right = x->fhe_right;
 645         /* clear out hanging pointers */
 646         x->fhe_p = NULL;
 647         x->fhe_left = x;
 648         x->fhe_right = x;
 649         return ret;
 650 }
 651
 652 static void fh_checkcons ( FibHeap * h )
 653 {
 654         IDnum oDl;
 655
 656         /* make sure we have enough memory allocated to "reorganize" */
 657         if ( h->fh_Dl == -1 || h->fh_n > ( 1 << h->fh_Dl ) )
 658         {
 659                 oDl = h->fh_Dl;
 660
 661                 if ( ( h->fh_Dl = ceillog2 ( h->fh_n ) + 1 ) < 8 )
 662                 {
 663                         h->fh_Dl = 8;
 664                 }
 665
 666                 if ( oDl != h->fh_Dl )
 667                         { h->fh_cons = ( FibHeapNode ** ) realloc ( h->fh_cons, sizeof * h->fh_cons * ( h->fh_Dl + 1 ) ); }
 668
 669                 if ( h->fh_cons == NULL )
 670                 {
 671                         abort ();
 672                 }
 673         }
 674 }
 675
 676 static int fh_compare ( FibHeap * h, FibHeapNode * a, FibHeapNode * b )
 677 {
 678         if ( a->fhe_key < b->fhe_key )
 679         {
 680                 return -1;
 681         }
 682
 683         if ( a->fhe_key == b->fhe_key )
 684         {
 685                 return 0;
 686         }
 687
 688         return 1;
 689 }
 690
 691 static int fh_comparedata ( FibHeap * h, Coordinate key, unsigned int data, FibHeapNode * b )
 692 {
 693         FibHeapNode a;
 694         a.fhe_key = key;
 695         a.fhe_data = data;
 696         return fh_compare ( h, &a, b );
 697 }
 698
 699 static void fh_insertel ( FibHeap * h, FibHeapNode * x )
 700 {
 701         fh_insertrootlist ( h, x );
 702
 703         if ( h->fh_min == NULL || ( h->fh_keys ? x->fhe_key < h->fh_min->fhe_key : h->fh_cmp_fnct ( x->fhe_data, h->fh_min->fhe_data ) < 0 ) )
 704         {
 705                 h->fh_min = x;
 706         }
 707
 708         h->fh_n++;
 709 }