package datastructures;

import java.util.AbstractQueue;
import java.util.Comparator;
import java.util.ConcurrentModificationException;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;


public final class FibonacciHeap<E>  extends AbstractQueue<E> {

 public static final class Node<E> {
  int degree = 0;
  boolean mark = false;
  private Node<E> parent = null;
  private Node<E> child = null;
  
  private Node<E> left = null;
  private Node<E> right = null;
  private E element;
  
  public E getElement(){return element;}
  public void setElement(E element){this.element=element;}
  
  public Node (E elem)
  {
   this.element=elem;
   left = right = this;
  }
 }
 
 private class DefaultComparator implements Comparator<E>
    {
        public int compare (Object o1, Object o2)
        {
         if(o1==null && o2 ==null)
          return 0;
         if(o1==null)
          return -1;
         if(o2==null)
          return 1;
            return ((Comparable) o1).compareTo(o2);
        }
    }
 
    private Comparator<E> myComp = new DefaultComparator();
 private int size=0;
 private Node<E> min=null;
 
 public boolean offer(E e) {
  if (e==null)
   return false;
  Node<E> x = new Node<E>(e);
  if (min == null)
  {
   min = x;
  }
  else
  {
   min = mergeLists(min, x);
  }
  size++;
  return true;
 }
 
 public boolean isEmpty() {
        return min == null;
    }

 public Nide<E> minimum() {
	return this.min;
 }
 public void merge(FibonacciHeap<E> h2)
 {
  min=mergeLists(this.min, h2.min);
  this.size += h2.size;
  //destroy the added one
  h2.min=null;
  h2.size=0;
 }
 
 public E poll() {
  Node<E> z = min;
  if (z!=null)
  {
   if(z.child!=null)
   {
    Node<E> current =z.child;
    do
    {
     current.parent = null;
     current = current.right;
    }
    while(current != z.child);
   }
   mergeLists(min, z.child);
   if(z.right!=z)
   {
    z.right.left = z.left;
    z.left.right = z.right;
    min = z.right;
    consolidate();
   }
   else
    min = null;   
 
  }
  size--;
  return z.getElement();
 }
 
 private void consolidate() 
 {
  Object[] A = new Object[(int)(Math.log(size)/Math.log(2))+2];
  Node<E> current = min;
  HashSet<Node<E>> used = new HashSet<Node<E>>();
  do
  {
   Node<E> x = current;
   used.add(x);
   current = current.right;
   int d = x.degree;
   while(A[d] != null)
   {
    Node<E> y = (Node<E>) A[d];
    if (myComp.compare(x.element, y.element)>0)
    {
     Node<E> temp =x;
     x=y;
     y=temp;
    }
    fibHeapLink(y,x);
    A[d] = null;
    d = d+1;
   }
   A[d] = x;
  }
  while(!used.contains(current));
   
  
  min=null;
  for (int i=0; i<A.length; i++)
  {
   if(A[i] != null)
   {
    if(min==null)
     min=(Node<E>) A[i];
    else
     min = (Node<E>) (myComp.compare(min.element, ((Node<E>) A[i]).element)<0 ? min : A[i]);
   }
  }
  
 }
 
 private void fibHeapLink(Node<E>y, Node<E>x)
 {  
  //It cannot be than y is the only one in root list as x has to be too
  
  y.right.left = y.left;
  y.left.right = y.right;
  y.right=y;
  y.left=y;
  if(x.child!=null)
  {
   x.child = mergeLists(x.child, y);
  }
  else
   x.child = y;
  x.degree += 1;
  y.mark = false;
 }

 public E peek() {
  if(size==0)
   return null;
  return min.getElement();
 }
 
 public int size() {
  return size;
 }
    
    
 private Node<E> mergeLists(Node<E> list1, Node<E> list2) 
 {
          if (list1 == null && list2 == null) {
              return null;
          }
          if ( list2 == null) {
              return list1;
          }
          if (list1 == null ) {
              return list2;
          }
          else { 
            // Both non-null; actually do the splice.
            /* The idea is that we'll have two lists that look like this:
             *
             * +----+     +----+     +----+
             * |    |--R->| l1 |--R->|l1R |
             * |    |<-L--|    |<-L--|    |
             * +----+     +----+     +----+
             *
             *
             * +----+     +----+     +----+
             * |    |--R->| l2 |--R->|    |
             * |    |<-L--|    |<-L--|    |
             * +----+     +----+     +----+
             *
             * And we want to relink everything to get
             *
             * +----+     +----+     +----+---+
             * |    |--R->| l1 |     |l1R |   |
             * |    |<-L--|    |     |    |<+ |
             * +----+     +----+<-\  +----+ | |
             *                  \  R        | |
             *                   L  \       R |
             * +----+     +----+  \->+----+ | |
             * |    |--R->| l2 |     |    | | |
             * |    |<-L--|    |     |    | | L
             * +----+     +----+     +----+ | |
             *              ^ |             | |
             *              | +-------------+ |
             *              +-----------------+
             *
             */
            Node<E> l1R = list1.right;
            list1.right = list2.right;
            list1.right.left =list1;
            list2.right = l1R;
            list2.right.left = list2;

            /* Return a pointer to whichever is smaller. */
            return myComp.compare(list1.element, list2.element)<0 ? list1 : list2;
        }
    }
 
 private void print(Node<E> node, String prefix, boolean start)
 {
  if(node == null)
   return;
  System.out.println(prefix + node.getElement().toString());
  print(node.child, prefix+"\t", true);
  if(start)
  {
   Node<E> current=node.right;
   while(current!=node)
   {
    print(current, prefix, false);
    current = current.right;
   }
  }
 } 
 
 public void print()
 {
  print(min);
 }
 
 private void print(Node<E> e)
 {
  print(e, "", true);
 }
 
 public void decreaseKey(Node<E> x, E val)
 {
  if(myComp.compare(val,x.getElement())>0)
   throw new IllegalArgumentException("New key is greater than current");
  x.setElement(val);
  Node<E> y = x.parent;
  if (y != null && myComp.compare(x.getElement(), y.getElement())<0)
  {
   cut(x,y);
   cascadingCut(y);
  }
  if(myComp.compare(x.getElement(), min.getElement())<0)
   min=x;
 }

 private void cut(Node<E> x, Node<E> y)
 {
  if(x.right==x)
   y.child = null;
  else
  { 
   x.left.right = x.right;
   x.right.left = x.left;
   if (y.child == x)
    y.child = x.right;
   x.right = x.left = x;
  }
  min = mergeLists(x, min);
  x.parent = null;
  x.mark = false;
 }
 
 private void cascadingCut(Node<E> y) 
 {
  Node<E> z = y.parent;
  if (z != null)
  {
   if(y.mark == false)   
    y.mark=true;
   else
   {
    cut(y,z);
    cascadingCut(z); 
   }
  }
 }
 
 
 
 public Iterator<E> iterator() {
  Iterator<E> it = new Iterator<E>() {
   public boolean hasNext() {
    return visited.size()<size;
   }

   public E next() {
    E value = current.getElement();
    visited.add(current);
    if(hasNext())
    {
     if(current.child!=null)
     {
      stack.push(current);
      current = current.child;
     }
     else
     {
      while(visited.contains(current.right))
      {
       if(!stack.isEmpty())
        current = stack.pop();
       else
        throw new ConcurrentModificationException();
      }
      current = current.right;
     }
    }
    return value;
   }

   public void remove() {
    throw new UnsupportedOperationException("remove not implemented");
   }
   Node<E> current = min;
   LinkedList<Node<E>> stack = new LinkedList<Node<E>>();
   HashSet<Node<E>> visited = new HashSet<Node<E>>(); 
  };
        
  return it;
 }
  
 public void delete(Node<E> node)
 {
  decreaseKey(node, null); // We use null to indicate -Inf
  poll();
 }
}