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