View difference between Paste ID: f6fc7d4b8 and

-
+/*
  * 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");
             }
 
         }
     }
 
 }