/* IF WANT TO COMPILE & RUN THIS                           cc fibheap.c -lm */
/*
#define STAND_ALONE
*/

/* IF HEAPS TO BE PRINTED */
/*
#define PRINT_HEAP_AFTER_INSERT
#define PRINT_HEAP_AFTER_EXTRACT_MIN
#define PRINT_HEAP_AFTER_DECREASE_KEY
*/

#ifdef STAND_ALONE
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#endif

/*****************************************************************************/
/* USER MUST PROVIDE FOLLOWING 4 PIECES OF INFORMATION                       */
/*****************************************************************************/

#ifdef STAND_ALONE
#define key_type int
#define KEY_FORMAT "\tK:%d\t"
#define key_extras int
#define printkeyextras(x) printf("\tK:%d\n", x );
#define copy_key_extras(x,x_extras,y,y_extras) (x_extras) = (y_extras)
#endif

#define FibHeapKey(x)        (x)->key
#define FibHeapKeyExtras(x)  (x)->extras







/*****************************************************************************/
/* DEFINITIONS                                                               */
/*****************************************************************************/

#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif

#define HEAPNODESPERBLOCK  2048

#ifndef FIBHEAP
#define FIBHEAP
struct fibonacci_heap {
    key_type key;
    key_extras extras;
    int FHdegree;  /* number of children                                     */
    int FHmark;    /* flag: lost a child since it was last made a child of   */
                   /*       another node?                                    */
    struct fibonacci_heap *FHparent, *FHchild;
    struct fibonacci_heap *left, *right;
};
#endif

/*****************************************************************************/
/* USER FUNCTIONS                                                            */
/*****************************************************************************/
int                    FibHeapInit();
struct fibonacci_heap *FibHeapAlloc();
void                   FibHeapDeAlloc( );
struct fibonacci_heap *FibHeapMin();
                       FibHeapInsert( );
struct fibonacci_heap *FibHeapExtractMin();
void                   FibHeapDecreaseKey( );
void                   FibHeapDecreaseKey( );
/*
key_type               FibHeapKey( );
key_extras             FibHeapKeyExtras( );

struct fibonacci_heap *minH;  --- root of heap
*/


struct fibonacci_heap *minH=NULL;     /* point to  root with min value       */
int                    nH=0;          /* number of nodes currently in H      */
int                    NumNodesInRoot=0;
struct fibonacci_heap *firstheapnode, *nextheapnode, *nowheapnode;
int heapnodesleft;
int heapnodes = 0;
struct fibonacci_heap FHtempstruc;
struct fibonacci_heap *FHtemp;


#define printheapnode( x )                                                   \
        if (x) {                                                             \
            printf("Node: %d", x);                                           \
            printf("\tDegree:%d", (x)->FHdegree);                            \
            printf(KEY_FORMAT, (x)->key);                                    \
            printkeyextras( x->extras );                                     \
            printf("\n");                                                    \
        } else printf("NODE x EMPTY\n")

#define FibHeapMin()    minH

/* max FHdegree of any node in n-node FH */
#define MaxDegree( n )  ((int)(ceil(log((double)n))))

#define InsertXListIntoYList( x, y )  /* eg Insert( x, minH ) */              \
        if (y) {                                                              \
            FHtemp = (y)->right;                                              \
            (y)->right->left = (x);                                           \
            (y)->right = (x)->right;                                          \
            (x)->right->left = (y);                                           \
            (x)->right = FHtemp;                                              \
        } else {                                                              \
            y = x;                                                            \
            (y)->right = y;                                                   \
            (y)->left = y;                                                    \
        }

#define InsertXElementIntoYList( x, y )  /* eg Insert( x, minH ) */           \
        (x)->right = x;                                                       \
        (x)->left = x;                                                        \
        if (y) {                                                              \
            FHtemp = (y)->right;                                              \
            (y)->right->left = (x);                                           \
            (y)->right = (x)->right;                                          \
            (x)->right->left = (y);                                           \
            (x)->right = FHtemp;                                              \
        } else {                                                              \
            y = x;                                                            \
        }

#define RemoveXNodefromYList( x, y ) /* eg Remove( x, minH ) */               \
        (x)->left->right = (x)->right;                                        \
        (x)->right->left = (x)->left
        
#define FibHeapLink( y, x )                                                   \
        RemoveXNodefromYList( (y), minH );                                    \
        (y)->right = (y);                                                     \
        (y)->left = (y);                                                      \
        /* make y a child of x */                                             \
        InsertXListIntoYList( (y), (x)->FHchild )                             \
        (y)->FHparent = (x);                                                  \
        ((x)->FHdegree)++;                                                    \
        (y)->FHmark = FALSE

#define FibHeapExchange( x, y )                                               \
        FHtempstruc.key = (x)->key;                                           \
        copy_key_extras( &FHtempstruc, FHtempstruc.extras, x, (x)->extras );  \
        (x)->key = (y)->key;                                                  \
        copy_key_extras( x, (x)->extras, y, (y)->extras );                    \
        (y)->key = FHtempstruc.key;                                           \
        copy_key_extras( y, (y)->extras, &FHtempstruc, FHtempstruc.extras )

#define FibHeapCut( x, parent )                                               \
        RemoveXNodefromYList( x, parent );                                    \
        ((parent)->FHdegree)--;                                               \
        if ((parent)->FHdegree) {                                             \
            (parent)->FHchild = (x)->right;                                   \
        } else {                                                              \
            (parent)->FHchild = NULL;                                         \
        }                                                                     \
        InsertXElementIntoYList( x, minH );                                   \
        NumNodesInRoot++;                                                     \
        (x)->FHparent = NULL;                                                 \
        (x)->FHmark = FALSE

/*****************************************************************************/
/* FUNCTION printheap                                                        */
/*     prints all the nodes in the current heap                              */
/*****************************************************************************/
void printheap( curr_root, indent, numsiblings )
struct fibonacci_heap *curr_root;
int indent;
int numsiblings;
{
  struct fibonacci_heap *FHchild;
  int i,j;

  if (curr_root) {
    for( j=0; j<numsiblings; j++) {
      for(i=0;i<indent;i++){
        printf("    ");
      }
      printf("Node: %x\t", curr_root );
      printf("\tDegree:%d\n", curr_root->FHdegree);
      printf(KEY_FORMAT, curr_root->key);
      printkeyextras(curr_root->extras);
      printf("\tDegree:%d\n", (curr_root)->FHdegree);
      for(i=0;i<indent;i++){ printf("    "); }
      printf("     P:%x C:%x   LS:%x RS:%x\n", (curr_root)->FHparent,
	     (curr_root)->FHchild, (curr_root)->left, (curr_root)->right);
      
      FHchild = curr_root->FHchild;
      printheap( FHchild, indent+1, curr_root->FHdegree );

      curr_root = curr_root->right;
    }
  }
}


/*****************************************************************************/
/* FUNCTION FibHeapInit                                                      */
/*     allocates enough memory for nodes                                     */
/*****************************************************************************/
int FibHeapInit()
/* returns whether or not allocation was successful or not                   */
{
    firstheapnode = (struct fibonacci_heap *)
                malloc( (HEAPNODESPERBLOCK+1) * sizeof(struct fibonacci_heap) );
    nowheapnode = firstheapnode;
    nextheapnode = nowheapnode + sizeof( struct fibonacci_heap );
    heapnodesleft = HEAPNODESPERBLOCK;
    heapnodes = 0;

    return( firstheapnode != NULL );
}

/*****************************************************************************/
/* FUNCTION FibHeapAlloc                                                     */
/*     allocates one node                                                    */
/*****************************************************************************/
struct fibonacci_heap *FibHeapAlloc()
/* returns pointer to the heap node allocated, NULL if no space left         */
{
    struct fibonacci_heap *newheapnode;

    if (heapnodesleft == 0) {
        nowheapnode = (struct fibonacci_heap *)
                malloc( (HEAPNODESPERBLOCK+1) * sizeof(struct fibonacci_heap) );
        nextheapnode = nowheapnode;
        heapnodesleft = HEAPNODESPERBLOCK;
    }
    newheapnode = nextheapnode;
    nextheapnode += sizeof( struct fibonacci_heap );
    heapnodesleft--;

    return( newheapnode );
}

/*****************************************************************************/
/* FUNCTION FibHeapDeAlloc                                                   */
/*     Deallocates space for one node                                        */
/*****************************************************************************/
void FibHeapDeAlloc( node )
struct fibonacci_heap *node;
{
/* empty for now */
}

/*****************************************************************************/
/* FUNCTION FibHeapInsert                                                    */
/*     Puts a node into the heap                                             */
/*     Does not remove duplicate nodes                                       */
/*     Requires space to be allocated already. Key already set.              */
/*****************************************************************************/
FibHeapInsert( newnode )
struct fibonacci_heap *newnode;
{
    newnode->FHdegree = 0;
    newnode->FHparent = NULL;
    newnode->FHchild = NULL;
    newnode->left = newnode;
    newnode->right = newnode;
    newnode->FHmark = FALSE;

/*  concatenate the root list containing newnode with root list minH   */
    InsertXListIntoYList( newnode, minH )

    if ( (minH == NULL) || ( FibHeapKey(newnode) < FibHeapKey(minH) ) ) {
        minH = newnode;
    }
    NumNodesInRoot++;
    nH++;

#ifdef PRINT_HEAP_AFTER_INSERT
    printf("INSERT CURRENT HEAP NumNodesInRoot=%d\n",NumNodesInRoot);
    printheap( minH, 0, NumNodesInRoot );
    printf("INSERT CURRENT HEAP end\n");
#endif
}


/*****************************************************************************/
/* FUNCTION FibHeapConsolidate                                               */
/*     links trees together so only one of each degree                       */
/*****************************************************************************/
void FibHeapConsolidate()
{
    struct fibonacci_heap **A;
    struct fibonacci_heap *curr_root, *curr_tree, *FHchild_tree, temp;
    int i,  d;

    if (minH == NULL) {
        return;
    }

    A = (struct fibonacci_heap **)
        malloc( (1+MaxDegree(nH)) * sizeof(struct fibonnacci_heap *) );

    for( i = 0; i<= MaxDegree(nH) ; i++ ) {
        A[i] = NULL;
    }

    curr_root = minH;
    for( i=0; i<NumNodesInRoot; i++) {
        curr_tree = curr_root;
        d = curr_tree->FHdegree;
        while (A[d] != NULL) {
            FHchild_tree = A[d];
            if (FibHeapKey(curr_tree) > FibHeapKey(FHchild_tree)) {
                FibHeapExchange( curr_tree, FHchild_tree );
            }
            FibHeapLink( FHchild_tree, curr_tree);

            A[d] = NULL;
            d++;
        }
        A[d] = curr_tree;
        curr_root = curr_root->right;
      }

    minH = NULL;
    NumNodesInRoot = 0;
    for( i = 0; i<= MaxDegree(nH) ; i++ ) {
        if (A[i] != NULL) {
	  InsertXElementIntoYList( A[i], minH )
	  if (FibHeapKey(A[i]) < FibHeapKey(minH)) {
	    minH = A[i];
	  }
	  NumNodesInRoot++;
        }
    }
    free( (void *) A );

}

/*****************************************************************************/
/* FUNCTION FibHeapExtractMin                                                */
/*     Extracts Minimum node in heap                                         */
/*****************************************************************************/
struct fibonacci_heap *FibHeapExtractMin()
{
    struct fibonacci_heap *minnode;
    struct fibonacci_heap *FHchild;

    minnode = minH;

    if (minnode != NULL) {
        FHchild = minnode->FHchild;

        if (FHchild != NULL) {
	  /* add FHchild & sibs to root list of minH */
	  while (FHchild->FHparent != NULL) {
	    FHchild->FHparent = NULL;
	    FHchild = FHchild->right;
	  }
	  InsertXListIntoYList( FHchild, minH ) 
	  NumNodesInRoot += minnode->FHdegree;
	  minnode->FHchild = NULL;
	  minnode->FHdegree = 0;
	}
	
        /* remove minnode from root list */
        RemoveXNodefromYList( minnode, minH );

	NumNodesInRoot--;
        if (minnode == minnode->right) {
            minH = NULL;
        } else {
            minH = minnode->right;
            FibHeapConsolidate();
        }
        nH--;
    }

#ifdef PRINT_HEAP_AFTER_EXTRACT_MIN
    printf("EXTRACT MIN CURRENT HEAP NumNodesInRoot=%d\n",NumNodesInRoot);
    printheap( minH, 0, NumNodesInRoot );
    printf("EXTRACT MIN CURRENT HEAP end\n");
#endif

    return( minnode );
}


/*****************************************************************************/
/* FUNCTION FibHeapCascadingCut                                              */
/*     cuts children from parents so that no node gets too sparse            */
/*****************************************************************************/
void FibHeapCascadingCut( FHchild )
struct fibonacci_heap *FHchild;
{
    struct fibonacci_heap *FHparent = FHchild->FHparent;

    if (FHparent) {
        if (FHchild->FHmark == FALSE) {
            FHchild->FHmark = TRUE;
        } else {
            FibHeapCut( FHchild, FHparent );
            FibHeapCascadingCut( FHparent );
        }
    }
}

/*****************************************************************************/
/* FUNCTION FibHeapSetKey                                                    */
/*     changes key to new value key, then cuts child if necessary            */
/*****************************************************************************/
void FibHeapSetKey( node, value )
struct fibonacci_heap *node;
key_type value;
{
    struct fibonacci_heap *FHparent;

    if (node==NULL) {
        return;
    }

    if ( value > FibHeapKey(node) ) {
        printf("New key is greater than current key\n");
        printheapnode( node );
        exit(1);
    }

    node->key =  value;

    FHparent = node->FHparent;
    if (FHparent && (FibHeapKey(node) < FibHeapKey(FHparent)) ) {
        FibHeapCut( node, FHparent );
        FibHeapCascadingCut( FHparent );
    }

    if (FibHeapKey(node) < FibHeapKey(minH)) {
        minH = node;
    }

#ifdef PRINT_HEAP_AFTER_DECREASE_KEY
    printf("SET KEY CURRENT HEAP NumNodesInRoot=%d\n",NumNodesInRoot);
    printheap( minH, 0, NumNodesInRoot );
    printf("SET KEY end\n");
#endif
}

/*****************************************************************************/
/* FUNCTION FibHeapDecreaseKey                                               */
/*     subtracts delta from the key, then cuts child if necessary            */
/*****************************************************************************/
void FibHeapDecreaseKey( node, delta )
struct fibonacci_heap *node;
key_type delta;
{
    struct fibonacci_heap *FHparent;

    if (node==NULL) {
        return;
    }

    if ( FibHeapKey(node)-delta > FibHeapKey(node) ) {
        printf("New key is greater than current key\n");
        printheapnode( node );
        exit(1);
    }

    node->key =  (FibHeapKey(node)-delta);

    FHparent = node->FHparent;
    if (FHparent && (FibHeapKey(node) < FibHeapKey(FHparent)) ) {
        FibHeapCut( node, FHparent );
        FibHeapCascadingCut( FHparent );
    }

    if (FibHeapKey(node) < FibHeapKey(minH)) {
        minH = node;
    }

#ifdef PRINT_HEAP_AFTER_DECREASE_KEY
    printf("DECREASE KEY CURRENT HEAP NumNodesInRoot=%d\n",NumNodesInRoot);
    printheap( minH, 0, NumNodesInRoot );
    printf("DECREASE KEY end\n");
#endif
}

#ifdef STAND_ALONE
/*****************************************************************************/
/* FUNCTION main                                                             */
/*****************************************************************************/
main()
{
    struct fibonacci_heap *a;
    struct fibonacci_heap *b;

    FibHeapInit();

    b = a = FibHeapAlloc();
    a->key = 0;
    FibHeapInsert( a );
    b = a = FibHeapAlloc();
    a->key = 9;
    FibHeapInsert( a );
    b = a = FibHeapAlloc();
    a->key = 9;
    FibHeapInsert( a );
    b = a = FibHeapAlloc();
    a->key = 9;
    FibHeapInsert( a );
    a = FibHeapAlloc();
    a->key = 9;
    FibHeapInsert( a );
    a = FibHeapAlloc();
    a->key = 9;
    FibHeapInsert( a );
    a = FibHeapAlloc();
    a->key = 9;
    FibHeapInsert( a );

    FibHeapDecreaseKey( b, 3 );

    a = FibHeapExtractMin();
    printf("EXTRACT MIN:\n");
    printheapnode( a );

}
#endif