Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- * 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");
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement