/*
 * Program to learn Fibonacci Heap Data Structure
 *
 * https://www.programiz.com/dsa/fibonacci-heap
 *
 * Compiling: >c -V fbn_heap.c -LF
 */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#ifndef false
#define false 0
#endif
#ifndef true
#define true 1
#endif

typedef struct _NODE {
  int key;
  int degree;
  struct _NODE *left_sibling;
  struct _NODE *right_sibling;
  struct _NODE *parent;
  struct _NODE *child;
  char mark;
  char visited;
} NODE;

typedef struct fibanocci_heap {
  int n;
  NODE *min;
  int phi;
  int degree;
} FIB_HEAP;


FIB_HEAP *make_fib_heap();
void insertion(FIB_HEAP *H, NODE *new, int val);
NODE *extract_min(FIB_HEAP *H);
void consolidate(FIB_HEAP *H);
void fib_heap_link(FIB_HEAP *H, NODE *y, NODE *x);
NODE *find_min_node(FIB_HEAP *H);
void decrease_key(FIB_HEAP *H, NODE *node, int key);
void cut(FIB_HEAP *H, NODE *node_to_be_decrease, NODE *parent_node);
void cascading_cut(FIB_HEAP *H, NODE *parent_node);
void Delete_Node(FIB_HEAP *H, int dec_key);

FIB_HEAP *make_fib_heap() 
{
	FIB_HEAP *H;
	H = (FIB_HEAP *)malloc(sizeof(FIB_HEAP));
	H->n = 0;
	H->min = NULL;
	H->phi = 0;
	H->degree = 0;
	return H;
}

/* Printing the heap */
void print_heap(NODE *n, char printLines) 
{
	NODE *x;
	
	if (printLines)
		printf("================================================\n");
	
	for (x = n;; x = x->right_sibling) 
	{
		if (x->child == NULL) 
		{
			printf("Node with no child (%d) \n", x->key);
		} 
		else 
		{
			printf("NODE(%d) with child (%d)\n", x->key, x->child->key);
			print_heap(x->child, false);
		}
	
		if (x->right_sibling == n) 
		{
			break;
		}
	}
	if (printLines)
		printf("================================================\n");
}

/* Inserting nodes */
void insertion(FIB_HEAP *H, NODE *new, int val) 
{
	new = (NODE *)malloc(sizeof(NODE));
	new->key = val;
	new->degree = 0;
	new->mark = false;
	new->parent = NULL;
	new->child = NULL;
	new->visited = false;
	new->left_sibling = new;
	new->right_sibling = new;
	if (H->min == NULL) 
	{
		H->min = new;
	} 
	else 
	{
		H->min->left_sibling->right_sibling = new;
		new->right_sibling = H->min;
		new->left_sibling = H->min->left_sibling;
		H->min->left_sibling = new;
		
		if (new->key < H->min->key) 
		{
		  H->min = new;
		}
	}
	(H->n)++;
}

/* Find min node */
NODE *find_min_node(FIB_HEAP *H) 
{
	if (H == NULL) 
	{
		printf(" \n Fibonacci heap not yet created \n");
		return NULL;
	} 
	else
		return H->min;
}

/* Union operation */
FIB_HEAP *unionHeap(FIB_HEAP *H1, FIB_HEAP *H2)
{
	FIB_HEAP *Hnew;
	NODE *temp1, *temp2;
	Hnew = make_fib_heap();
	Hnew->min = H1->min;

	temp1 = Hnew->min->right_sibling;
	temp2 = H2->min->left_sibling;

	Hnew->min->right_sibling->left_sibling = H2->min->left_sibling;
	Hnew->min->right_sibling = H2->min;
	H2->min->left_sibling = Hnew->min;
	temp2->right_sibling = temp1;

	if ((H1->min == NULL) || (H2->min != NULL && H2->min->key < H1->min->key))
		Hnew->min = H2->min;

	Hnew->n = H1->n + H2->n;
	return Hnew;
}

/* Calculate the degree */
int cal_degree(int n) 
{
	int count = 0;
	while (n > 0)
	{
		n = n / 2;
		count++;
	}
	  
	/*printf("\n n: %d => Degree: %d\n", n, count);*/
	  
	return count;
}

/* Consolidate function */
void consolidate(FIB_HEAP *H) 
{
	int degree, i, d;
	NODE *A[50]; /* Pointer to an array of 50 NODEs, its size is hardcoded ... */
	NODE *x, *y/*, *z*/;
  
	degree = cal_degree(H->n);
	/*
	 * ... because HI-TECH compiler doesn't allow to do:
	 * NODE *A[degree];
	 * here
 	 */
	
	
	for (i = 0; i <= degree; i++) 
	{
		A[i] = NULL;
	}
  
	x = H->min;
	do 
	{
		d = x->degree;
		while (A[d] != NULL) 
		{
			y = A[d];
			if (x->key > y->key) 
			{
				NODE *exchange_help;
				exchange_help = x;
				x = y;
				y = exchange_help;
			}
		  
			if (y == H->min)
				H->min = x;
		
			fib_heap_link(H, y, x);
		  
			if (y->right_sibling == x)
				H->min = x;
		
			A[d] = NULL;
			d++;
		}
		
		A[d] = x;
		x = x->right_sibling;
	} while (x != H->min);

	H->min = NULL;
	for (i = 0; i < degree; i++) 
	{
		if (A[i] != NULL) 
		{
			A[i]->left_sibling = A[i];
			A[i]->right_sibling = A[i];
			if (H->min == NULL) 
			{
				H->min = A[i];
			}
			else 
			{
				H->min->left_sibling->right_sibling = A[i];
				A[i]->right_sibling = H->min;
				A[i]->left_sibling = H->min->left_sibling;
				H->min->left_sibling = A[i];
				
				if (A[i]->key < H->min->key) 
				{
					H->min = A[i];
				}
			}
			
			if (H->min == NULL) 
			{
				H->min = A[i];
			}
			else if (A[i]->key < H->min->key) 
			{
				H->min = A[i];
			}
		}
	}
}

/* Linking */
void fib_heap_link(FIB_HEAP *H, NODE *y, NODE *x) 
{
	y->right_sibling->left_sibling = y->left_sibling;
	y->left_sibling->right_sibling = y->right_sibling;

	if (x->right_sibling == x)
		H->min = x;

	y->left_sibling = y;
	y->right_sibling = y;
	y->parent = x;

	if (x->child == NULL) 
	{
		x->child = y;
	}

	y->right_sibling = x->child;
	y->left_sibling = x->child->left_sibling;
	x->child->left_sibling->right_sibling = y;
	x->child->left_sibling = y;
	
	if ((y->key) < (x->child->key))
		x->child = y;

	(x->degree)++;
}

/* Extract min */
NODE *extract_min(FIB_HEAP *H) 
{
	NODE *x;
	
	if (H->min == NULL)
		printf("\n The heap is empty");
	else 
	{
		NODE *temp = H->min;
		NODE *pntr;
		pntr = temp;
		x = NULL;
		
		if (temp->child != NULL) 
		{
			x = temp->child;
			do
			{
				pntr = x->right_sibling;
				(H->min->left_sibling)->right_sibling = x;
				x->right_sibling = H->min;
				x->left_sibling = H->min->left_sibling;
				H->min->left_sibling = x;
				
				if (x->key < H->min->key)
				  H->min = x;
			  
				x->parent = NULL;
				x = pntr;
			} while (pntr != temp->child);
		}

			(temp->left_sibling)->right_sibling = temp->right_sibling;
			(temp->right_sibling)->left_sibling = temp->left_sibling;
			H->min = temp->right_sibling;

		if (temp == temp->right_sibling && temp->child == NULL)
			H->min = NULL;
		else 
		{
			H->min = temp->right_sibling;
			consolidate(H);
		}
		
		H->n = H->n - 1;
		return temp;
	}
	return H->min;
}

void cut(FIB_HEAP *H, NODE *node_to_be_decrease, NODE *parent_node) 
{
	/*NODE *temp_parent_check;*/

	if (node_to_be_decrease == node_to_be_decrease->right_sibling)
		parent_node->child = NULL;

	node_to_be_decrease->left_sibling->right_sibling = node_to_be_decrease->right_sibling;
	node_to_be_decrease->right_sibling->left_sibling = node_to_be_decrease->left_sibling;
	
	if (node_to_be_decrease == parent_node->child)
		parent_node->child = node_to_be_decrease->right_sibling;
	
	(parent_node->degree)--;

	node_to_be_decrease->left_sibling = node_to_be_decrease;
	node_to_be_decrease->right_sibling = node_to_be_decrease;
	H->min->left_sibling->right_sibling = node_to_be_decrease;
	node_to_be_decrease->right_sibling = H->min;
	node_to_be_decrease->left_sibling = H->min->left_sibling;
	H->min->left_sibling = node_to_be_decrease;

	node_to_be_decrease->parent = NULL;
	node_to_be_decrease->mark = false;
}

void cascading_cut(FIB_HEAP *H, NODE *parent_node)
{
	NODE *aux;
	aux = parent_node->parent;
  
	if (aux != NULL) 
	{
		if (parent_node->mark == false) 
		{
			parent_node->mark = true;
		} 
		else 
		{
			cut(H, parent_node, aux);
			cascading_cut(H, aux);
		}
	}
}

void decrease_key(FIB_HEAP *H, NODE *node_to_be_decrease, int new_key) 
{
	NODE *parent_node;
	if (H == NULL) 
	{
		printf("\n FIbonacci heap not created ");
		return;
	}
  
	if (node_to_be_decrease == NULL) 
	{
		printf("Node is not in the heap");
	}
	else
	{
		if (node_to_be_decrease->key < new_key) 
		{
		  printf("\n Invalid new key for decrease key operation \n ");
		} 
		else 
		{
			node_to_be_decrease->key = new_key;
			parent_node = node_to_be_decrease->parent;
		  
			if ((parent_node != NULL) && (node_to_be_decrease->key < parent_node->key)) 
			{
				printf("\n cut called");
				cut(H, node_to_be_decrease, parent_node);
				printf("\n cascading cut called");
				cascading_cut(H, parent_node);
			}
		  
			if (node_to_be_decrease->key < H->min->key) 
			{
				H->min = node_to_be_decrease;
			}
		}
	}
}

void *find_node(FIB_HEAP *H, NODE *n, int key, int new_key) 
{
	NODE *find_use = n;
	NODE *f = NULL;
	find_use->visited = true;
	  
	if (find_use->key == key) 
	{
		find_use->visited = false;
		f = find_use;
		decrease_key(H, f, new_key);
	}
	
	if (find_use->child != NULL) 
	{
		find_node(H, find_use->child, key, new_key);
	}
	
	if ((find_use->right_sibling->visited != true)) 
	{
		find_node(H, find_use->right_sibling, key, new_key);
	}

	find_use->visited = false;
	return NULL;
}

FIB_HEAP *insertion_procedure() 
{
	FIB_HEAP *temp;
	int no_of_nodes, ele, i;
	NODE *new_node;
	temp = (FIB_HEAP *) malloc(sizeof(FIB_HEAP));
	temp = NULL;
	  
	if (temp == NULL) 
	{
		temp = make_fib_heap();
	}
	
	printf(" \n Enter number of nodes to be insert = ");
	scanf("%d", &no_of_nodes);
	for (i = 1; i <= no_of_nodes; i++) 
	{
		printf("\n Node %d and its key value = ", i);
		scanf("%d", &ele);
		insertion(temp, new_node, ele);
	}
	return temp;
}

void Delete_Node(FIB_HEAP *H, int dec_key) 
{
	NODE *p = NULL;
	find_node(H, H->min, dec_key, -5000);
	p = extract_min(H);
	  
	if (p != NULL)
		printf("\n Node %d deleted", dec_key);
	else
		printf("\n Node not deleted: some error");
}

/* Entry point to program */
int main() 
{
	NODE *new_node, *min_node, *extracted_min/*, *node_to_be_decrease*/, *find_use;
	FIB_HEAP *heap, *h1/*, *h2*/;
	int operation_no, new_key, dec_key, ele, i, no_of_nodes;
	
	heap = (FIB_HEAP *) malloc(sizeof(FIB_HEAP));
	heap = NULL;
	
	while (true) 
	{
		printf(" \n Operations \n 1. Create Fibonacci heap \n 2. Insert nodes into Fibonacci heap \n 3. Find min \n 4. Union \n 5. Extract min \n 6. Decrease key \n 7. Delete node \n 8. Print heap \n 9. Exit \n Enter operation_no = ");
		scanf("%d", &operation_no);

		switch (operation_no) 
		{
			case 1:
				heap = make_fib_heap();
				break;

			case 2:
				if (heap == NULL) 
				{
				  heap = make_fib_heap();
				}
				printf(" Enter number of nodes to be insert = ");
				scanf("%d", &no_of_nodes);
				for (i = 1; i <= no_of_nodes; i++) 
				{
				  printf("\n node %d and its key value = ", i);
				  scanf("%d", &ele);
				  insertion(heap, new_node, ele);
				}
				break;

			case 3:
				min_node = find_min_node(heap);
				if (min_node == NULL)
				  printf("No minimum value");
				else
				  printf("\n Minimum value = %d", min_node->key);
				break;

			  case 4:
				if (heap == NULL) 
				{
				  printf("\n no FIbonacci heap created \n ");
				  break;
				}
				h1 = insertion_procedure();
				heap = unionHeap(heap, h1);
				printf("Unified Heap:\n");
				print_heap(heap->min, true);
				break;

			  case 5:
				if (heap == NULL)
				  printf("Empty Fibonacci heap");
				else 
				{
				  extracted_min = extract_min(heap);
				  printf("\n minimum value = %d", extracted_min->key);
				  printf("\n Updated heap: \n");
				  print_heap(heap->min, true);
				}
				break;

			  case 6:
				if (heap == NULL)
				  printf("Fibonacci heap is empty");
				else 
				{
				  printf(" \n node to be decreased = ");
				  scanf("%d", &dec_key);
				  printf(" \n enter the new key = ");
				  scanf("%d", &new_key);
				  find_use = heap->min;
				  find_node(heap, find_use, dec_key, new_key);
				  printf("\n Key decreased- Corresponding heap:\n");
				  print_heap(heap->min, true);
				}
				break;
			case 7:
				if (heap == NULL)
				  printf("Fibonacci heap is empty");
				else 
				{
				  printf(" \n Enter node key to be deleted = ");
				  scanf("%d", &dec_key);
				  Delete_Node(heap, dec_key);
				  printf("\n Node Deleted- Corresponding heap:\n");
				  print_heap(heap->min, true);
				  break;
				}
			case 8:
				print_heap(heap->min, true);
				break;

			case 9:
				free(new_node);
				free(heap);
				exit(0);

			default:
				printf("Invalid choice ");
		}
	}
	return 0;
}