text: /*******************************************************************************
   * DANIEL'S ALGORITHM IMPLEMENTAIONS
   *
   *  /\  |  _   _  ._ o _|_ |_  ._ _   _ 
   * /--\ | (_| (_) |  |  |_ | | | | | _> 
   *         _|                      
   *
   * FIBONACCI HEAP
   *
   * In computer science, a Fibonacci heap is a heap data structure consisting of 
   * a collection of trees. It has a better amortized running time than a binomial
   * heap. Fibonacci heaps were developed by Michael L. Fredman and Robert E. Tarjan
   * in 1984 and first published in a scientific journal in 1987. The name of 
   * Fibonacci heap comes from Fibonacci numbers which are used in the 
   * running time analysis.
   *
   * http://en.wikipedia.org/wiki/Fibonacci_heap
   ******************************************************************************/
  
  #ifndef ALGO_FIB_HEAP_H__
  #define ALGO_FIB_HEAP_H__
  #include <math.h>
  #include <stdint.h>
  #include <unistd.h>
  #include "double_linked_list.h"
  namespace alg {
  		template<typename _Key, typename _Val>
  		class FibHeap {
  			public:
  				typedef _Key key_type;
  				typedef _Val value_type;
  				struct node_t {
  					int32_t degree;
  					node_t * parent;
  					bool mark;
  					key_type key;
  					value_type value;
  					struct list_head child_head;	// child list head
  					struct list_head node;	// sibling list
  				};
  				typedef struct node_t *Node;
  			private:
  				FibHeap(const FibHeap &);
  				FibHeap& operator=(const FibHeap&);
  			private:
  				int32_t n;	
  				Node min;
  				struct list_head m_root;	// root list
  			public:
  				FibHeap():n(0),min(NULL){
  					INIT_LIST_HEAD(&m_root);
  				}
  
  				/**
  				 * insert a value into the Fibonacci Heap
  				 */
  				void Insert(key_type key, value_type value) {
  					Node x = new node_t;
  					x->degree = 0;
  					x->parent = NULL;
  					x->mark = false;
  					x->key = key;
  					x->value = value;
  					INIT_LIST_HEAD(&x->child_head);
  					if (min == NULL) {
  						min = x;
  						list_add(&x->node, &m_root);
  					} else {
  						list_add(&x->node, &m_root);
  						if (x->key < min->key) {
  							min = x;
  						}
  					}
  					n = n+1;
  				}
  
  				/**
  				 * Union 2 Fibonacci-Heap
  				 */
  				static FibHeap* Union(FibHeap *H1, FibHeap *H2) {
  					FibHeap * H = new FibHeap();
  					H->min = H1->min;
  					H->m_root = H1->m_root;
  					list_splice(&H->m_root, &H1->m_root);	// concat 2 root-list
  					list_splice(&H->m_root, &H2->m_root);
  					if (H1->min == NULL || (H2->min != NULL && H2->min.key < H1->min.key)) {
  						H->min = H2->min;
  					}
  					H->n = H1->n + H2->n;
  					return H;
  				}
  
  				/**
  				 * Extract Min Element
  				 */
  				Node ExtractMin() {
  					Node z = min;
  					if (z != NULL) {
  						Node x, xs;
  						// for each child x of z, add x to the root list of H
  						list_for_each_entry_safe(x, xs, &z->child_head, node) {
  							list_del(&x->node);
  							list_add(&x->node, &m_root);
  							x->parent = NULL;
  						}
  
  						list_del(&z->node);
  						if (!list_empty(&m_root)) {
  							min = list_entry(m_root.next, node_t, node);	// is this necessary?
  							CONSOLIDATE();
  						} else { // the only node on the root list
  							min = NULL;
  						}
  						// remove z from the root list of H
  						n = n + 1;
  					}
  					return z;
  				}
  
  				/**
  				 * FIB-HEAP-DECREASE-KEY(H,x, k) /
  				 */
  				void DecreaseKey(Node x, key_type k) {
  					if (k > x->key) {
  						return;
  					}
  					x->key = k;
  					Node y = x->parent;	
  					if (y != NULL && x->key < y->key) {
  						CUT(x,y);
  						CASCADING_CUT(y);
  					}
  				}
  
  			private:
  				/**
  				 * CUT(H,x,y)
  				 * 1 remove x from the child list of y, decrementing y.degree
  				 * 2 add x to the root list of H
  				 * 3 x.p = NIL
  				 * 4 x.mark = FALSE
  				 */
  				void CUT(Node x, Node y) {
  					list_del(&x->node);
  					list_add(&x->node, &m_root);
  					x->parent = NULL;
  					x->mark = false;
  				}
  
  				void CASCADING_CUT(Node y) {
  					Node z = y->parent;
  					if (z!=NULL) {
  						if (y->mark == false) {
  							y->mark = true;
  						} else {
  							CUT(y,z);
  							CASCADING_CUT(z);
  						}
  					}
  				}
  
  				void CONSOLIDATE() {
  					int32_t dn = D(n);
  					Node A[dn+1];			// let A[0..D(H.n)] to be a new array
  					int32_t i;	
  					for (i=0;i<=dn;i++) {
  						A[i] = NULL;
  					}
  
  					Node w, ws;
  					// for each node w in the root list of H
  					list_for_each_entry_safe(w, ws, &m_root, node) {
  						Node x = w;
  						int32_t d = x->degree;
  						while (A[d] != NULL) {
  							Node y = A[d];	// another node with the same degree as x
  							if (x->key > y->key) {	// exchange x with y
  								Node tmp = x;
  								x = y;
  								y = tmp;
  							}
  							LINK(y,x);
  							A[d] = NULL;
  							d = d + 1;
  						}
  						A[d] = x;
  					}
  					min = NULL;
  					for (i=0;i<=dn;i++) {
  						if (A[i]!=NULL) {
  							if (min == NULL) {
  								// create a root list for H containing just A[i]
  								INIT_LIST_HEAD(&m_root);
  								list_add(&A[i]->node, &m_root);
  								min = A[i];
  							} else {
  								list_add(&A[i]->node, &m_root);
  								if (A[i]->key < min->key) {
  									min = A[i];
  								}
  							}
  						}
  					}
  				}
  
  				int32_t D(int32_t n) {
  					float p1 =  logf(n);
  					float p2 =  logf(1.61803);	// golden ratio
  					//printf("D(n) = %f\n", floor(p1/p2));
  					return int32_t(floor(p1/p2));
  				}
  			
  				/**
  				 * FIB-HEAP-LINK(H, y, x)
  				 * 1 remove y from the root list of H
  				 * 2 makey a child of x, incrementing x.degree
  				 * 3 y.mark = FALSE
  				 */
  				void LINK(Node y, Node x) {
  					y->parent = x;
  					list_add(&y->node, &x->child_head);
  					x->degree = x->degree + 1;
  					y->mark = false;
  				}
  		};
  }
  
  #endif //
  