/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author nick
 */
public class PriorityQueue<T> {
    private FibNode<T> _min;
    private final FibList<T> _rootList;
    private final java.util.Comparator<T> _comparer;
    private int _count;
    
    public PriorityQueue(java.util.Comparator<T> comparer) {
        _rootList = new FibList();
        _comparer = comparer;
        _count = 0;
    }
    
    public void insert(T item) {
        FibNode<T> node = new FibNode(item);
        insertToRootList(node);
        _count++;
    }
    public T peek() {
        T data = null;
        if (_min != null) {
            data = _min.getData();
        }
        return data;
    }
    
    public boolean isEmpty() {
        return _count == 0;
    }
    
    public PriorityQueue<T> union(PriorityQueue<T> queue) {
        PriorityQueue<T> q = new PriorityQueue(_comparer);
        q._min = _min;
        queue._rootList.addList(q._rootList);
        if (this._min == null || 
            (queue._min != null && 
            _comparer.compare(queue._min.getData(), this._min.getData()) < 0)) 
        {
            q._min = queue._min;
        }
        q._count = this._count + queue._count;
        
        return q;
    }
    
    public T removeMin() {
        FibNode<T> z = _min;
        T data = null;
        
        if (z != null) {
            
            /* promote all of z's children to the root list */
            FibList<T> list = z.getChildren();
            int count = _rootList.getCount();
            FibNode<T> child = list.getHead();
            
            if (child != null) {
                while (!child.isSentinal) {
                    FibNode<T> tmp = child.getRight();
                    _rootList.add(child);
                    child.setParent(null);
                    child = tmp;
                }
            }
            _rootList.remove(z);
            
            FibNode<T> right = z.getRight();
            
            /* if count is 1, then z was the only element, so set
             * min to null, otherwise set z's next to _min and consolidate
             */
            if (count == 1) {
                _min = null;
            } else {
                _min = right;
                consolidate();
            }
            _count--;
            data = z.getData();
        }
        
        return data;
    }
    
    private void consolidate() {
        int count = D(_count);
        FibNode<T>[] A = new FibNode[count];
        FibNode<T> node =  _rootList.getHead();
        
        do {
            FibNode<T> x = node;
            int d = x.getDegree();
            node = node.getRight();
            
            /* group nodes by same degree */
            while (A[d] != null) {
                FibNode<T> y = A[d];
                if (_comparer.compare(x.getData(), y.getData()) > 0) {
                    FibNode<T> tmp = x;
                    x = y;
                    y = tmp;
                }
                heapLink(y, x);
                A[d] = null;
                d++;
            }
            A[d] = x;
        } while (!node.isSentinal);
        
        /* reset the root list */
        _min = null;
        for (int i=0; i < count; i++) {
            if (A[i] != null) {
                insertToRootList(A[i]);
            }
        }
    }
    
    private int D(int n) {
        if (n == 0)
            throw new IllegalArgumentException();
        
        return 1 + (int)(1.44 * (Math.log(n)/Math.log(2.0)));
    }
    
    private void heapLink(FibNode<T> y, FibNode<T> x) {
        _rootList.remove(y);
        x.addChild(y);
        y.mark = false;
    }
    
    private void insertToRootList(FibNode<T> node) {
        _rootList.add(node);
        node.setParent(null);
        if (_min == null ||
            _comparer.compare(node.getData(), _min.getData()) < 0) 
        {
            _min = node;
        }
    }
    
    private void decreaseKey(FibNode<T> x, T data)
        throws java.lang.IllegalArgumentException 
    {
        if (_comparer.compare(x.getData(), data) > 0)
            throw new java.lang.IllegalArgumentException("key cannot be less than x's key");
        
        x.setData(data);
        FibNode<T> node = x.getParent();
        
        if (node != null && _comparer.compare(x.getData(), node.getData()) < 0 ) {
            cut(x, node);
            cascadingCut(node);
        }
        if (_comparer.compare(x.getData(), _min.getData()) < 0) {
            _min = x;
        }
    }
    
    private void cut(FibNode<T> x, FibNode<T> y) {
        y.getChildren().remove(x);
        _rootList.add(x);
        x.setParent(null);
        x.mark = false;
    }
    
    private void cascadingCut(FibNode<T> y) {
        FibNode<T> z = y.getParent();
        if (z != null) {
            if (!y.mark) {
                y.mark = true;
            } else {
                cut(y, z);
                cascadingCut(z);
            }
        }
    }
    
    private class FibNode<T> {
        private FibNode<T> _parent;
        private FibNode<T> _left;
        private FibNode<T> _right;
        private FibList<T> _children;
        public boolean     mark;
        public boolean     isSentinal;
        private T           _data;
        
        public FibNode() {
            _parent = null;
            _data = null;
            _children = new FibList();
            _left = _right = this;
            isSentinal = mark = false;
        }
        public FibNode(FibList<T> children) {
            _parent = null;
            _data = null;
            _children = children;
            _left = _right = this;
            mark = false;
            isSentinal = true;
        }
        public FibNode(T data) {
            this();
            _data = data;
        }
        
        public boolean hasSiblings() {
            return _left == this && _right == this;
        }
        public int getDegree() {
            return _children.getCount();
        }
        
        public FibNode<T> getRight() {
            return _right;
        }
        
        public FibNode<T> getLeft() {
            return _left;
        }
        
        public FibNode<T> getParent() {
            return _parent;
        }
        
        public FibList<T> getChildren() {
            return _children;
        }
        
        public T getData() {
            return _data;
        }
        
        public void addChild(FibNode<T> node) {
            _children.add(node);
            node.setParent(this);
        }
        public void setRight(FibNode<T> node) {
            _right = node;
        }
        
        public void setLeft(FibNode<T> node) {
            _left = node;
        }
        
        public void setParent(FibNode<T> node) {
            _parent = node;
        }
        
        public void setData(T data) {
            _data = data;
        }
    }
    
    private class FibList<T> 
            implements java.lang.Iterable<FibNode<T>> 
    {
        private final FibNode<T> _sentinal;
        private int _count;
        
        public FibList() {
            _count = 0;
            _sentinal = new FibNode(null);
        }
        
        public void add(FibNode<T> node) {
            node.setRight(_sentinal.getRight());
            _sentinal.getRight().setLeft(node);
            _sentinal.setRight(node);
            node.setLeft(_sentinal);
            _count++;
        }
        
        public void remove(FibNode<T> node) {
            node.getLeft().setRight(node.getRight());
            node.getRight().setLeft(node.getLeft());
            _count--;
        }
        
        public void addList(FibList<T> list) {
            FibNode<T> otherSent = list._sentinal;
            _sentinal.getLeft().setRight(otherSent.getRight());
            otherSent.getLeft().setRight(_sentinal);
            
            _count += list._count;
        }
        
        public int getCount() {
            return _count;
        }
        
        public FibNode<T> getHead() {
            return (_count > 0) ? _sentinal.getRight() : null;
        }
        
        public java.util.Iterator<FibNode<T>> iterator() {
            return new FibListIterator(_sentinal);
        }
        
        private class FibListIterator<T>
                implements java.util.Iterator<FibNode<T>> 
        {
            private FibNode<T> _head;
            
            public FibListIterator(FibNode head) {
                if (head == null)
                    throw new java.lang.IllegalArgumentException("FibListIterator.ctor");
                
                _head = head;
            }
            
            public boolean hasNext() {
                return (!_head.getRight().isSentinal);
            }
            
            public FibNode<T> next() {
                FibNode<T> node = _head.getRight();
                
                if (node.isSentinal)
                    throw new java.util.NoSuchElementException("FibListIterator.next");
                
                _head = node;
                
                return node;
            }
            
            public void remove() {
                throw new java.lang.UnsupportedOperationException("FibListIterator.remove");
            }
            
        }
    }

}