Want more features on Pastebin? Sign Up, it's FREE!
Guest

quattro

By: a guest on Aug 30th, 2009  |  syntax: Java  |  size: 9.50 KB  |  views: 196  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
This paste has a previous version, view the difference. Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. /*
  2.  * To change this template, choose Tools | Templates
  3.  * and open the template in the editor.
  4.  */
  5.  
  6. /**
  7.  *
  8.  * @author nick
  9.  */
  10. public class PriorityQueue<T> {
  11.     private FibNode<T> _min;
  12.     private final FibList<T> _rootList;
  13.     private final java.util.Comparator<T> _comparer;
  14.     private int _count;
  15.    
  16.     public PriorityQueue(java.util.Comparator<T> comparer) {
  17.         _rootList = new FibList();
  18.         _comparer = comparer;
  19.         _count = 0;
  20.     }
  21.    
  22.     public void insert(T item) {
  23.         FibNode<T> node = new FibNode(item);
  24.         insertToRootList(node);
  25.         _count++;
  26.     }
  27.     public T peek() {
  28.         T data = null;
  29.         if (_min != null) {
  30.             data = _min.getData();
  31.         }
  32.         return data;
  33.     }
  34.    
  35.     public boolean isEmpty() {
  36.         return _count == 0;
  37.     }
  38.    
  39.     public PriorityQueue<T> union(PriorityQueue<T> queue) {
  40.         PriorityQueue<T> q = new PriorityQueue(_comparer);
  41.         q._min = _min;
  42.         queue._rootList.addList(q._rootList);
  43.         if (this._min == null ||
  44.             (queue._min != null &&
  45.             _comparer.compare(queue._min.getData(), this._min.getData()) < 0))
  46.         {
  47.             q._min = queue._min;
  48.         }
  49.         q._count = this._count + queue._count;
  50.        
  51.         return q;
  52.     }
  53.    
  54.     public T removeMin() {
  55.         FibNode<T> z = _min;
  56.         T data = null;
  57.        
  58.         if (z != null) {
  59.            
  60.             /* promote all of z's children to the root list */
  61.             FibList<T> list = z.getChildren();
  62.             int count = _rootList.getCount();
  63.             FibNode<T> child = list.getHead();
  64.            
  65.             if (child != null) {
  66.                 while (!child.isSentinal) {
  67.                     FibNode<T> tmp = child.getRight();
  68.                     _rootList.add(child);
  69.                     child.setParent(null);
  70.                     child = tmp;
  71.                 }
  72.             }
  73.             _rootList.remove(z);
  74.            
  75.             FibNode<T> right = z.getRight();
  76.            
  77.             /* if count is 1, then z was the only element, so set
  78.              * min to null, otherwise set z's next to _min and consolidate
  79.              */
  80.             if (count == 1) {
  81.                 _min = null;
  82.             } else {
  83.                 _min = right;
  84.                 consolidate();
  85.             }
  86.             _count--;
  87.             data = z.getData();
  88.         }
  89.        
  90.         return data;
  91.     }
  92.    
  93.     private void consolidate() {
  94.         int count = D(_count);
  95.         FibNode<T>[] A = new FibNode[count];
  96.         FibNode<T> node =  _rootList.getHead();
  97.        
  98.         do {
  99.             FibNode<T> x = node;
  100.             int d = x.getDegree();
  101.             node = node.getRight();
  102.            
  103.             /* group nodes by same degree */
  104.             while (A[d] != null) {
  105.                 FibNode<T> y = A[d];
  106.                 if (_comparer.compare(x.getData(), y.getData()) > 0) {
  107.                     FibNode<T> tmp = x;
  108.                     x = y;
  109.                     y = tmp;
  110.                 }
  111.                 heapLink(y, x);
  112.                 A[d] = null;
  113.                 d++;
  114.             }
  115.             A[d] = x;
  116.         } while (!node.isSentinal);
  117.        
  118.         /* reset the root list */
  119.         _min = null;
  120.         for (int i=0; i < count; i++) {
  121.             if (A[i] != null) {
  122.                 insertToRootList(A[i]);
  123.             }
  124.         }
  125.     }
  126.    
  127.     private int D(int n) {
  128.         if (n == 0)
  129.             throw new IllegalArgumentException();
  130.        
  131.         return 1 + (int)(1.44 * (Math.log(n)/Math.log(2.0)));
  132.     }
  133.    
  134.     private void heapLink(FibNode<T> y, FibNode<T> x) {
  135.         _rootList.remove(y);
  136.         x.addChild(y);
  137.         y.mark = false;
  138.     }
  139.    
  140.     private void insertToRootList(FibNode<T> node) {
  141.         _rootList.add(node);
  142.         node.setParent(null);
  143.         if (_min == null ||
  144.             _comparer.compare(node.getData(), _min.getData()) < 0)
  145.         {
  146.             _min = node;
  147.         }
  148.     }
  149.    
  150.     private void decreaseKey(FibNode<T> x, T data)
  151.         throws java.lang.IllegalArgumentException
  152.     {
  153.         if (_comparer.compare(x.getData(), data) > 0)
  154.             throw new java.lang.IllegalArgumentException("key cannot be less than x's key");
  155.        
  156.         x.setData(data);
  157.         FibNode<T> node = x.getParent();
  158.        
  159.         if (node != null && _comparer.compare(x.getData(), node.getData()) < 0 ) {
  160.             cut(x, node);
  161.             cascadingCut(node);
  162.         }
  163.         if (_comparer.compare(x.getData(), _min.getData()) < 0) {
  164.             _min = x;
  165.         }
  166.     }
  167.    
  168.     private void cut(FibNode<T> x, FibNode<T> y) {
  169.         y.getChildren().remove(x);
  170.         _rootList.add(x);
  171.         x.setParent(null);
  172.         x.mark = false;
  173.     }
  174.    
  175.     private void cascadingCut(FibNode<T> y) {
  176.         FibNode<T> z = y.getParent();
  177.         if (z != null) {
  178.             if (!y.mark) {
  179.                 y.mark = true;
  180.             } else {
  181.                 cut(y, z);
  182.                 cascadingCut(z);
  183.             }
  184.         }
  185.     }
  186.    
  187.     private class FibNode<T> {
  188.         private FibNode<T> _parent;
  189.         private FibNode<T> _left;
  190.         private FibNode<T> _right;
  191.         private FibList<T> _children;
  192.         public boolean     mark;
  193.         public boolean     isSentinal;
  194.         private T           _data;
  195.        
  196.         public FibNode() {
  197.             _parent = null;
  198.             _data = null;
  199.             _children = new FibList();
  200.             _left = _right = this;
  201.             isSentinal = mark = false;
  202.         }
  203.         public FibNode(FibList<T> children) {
  204.             _parent = null;
  205.             _data = null;
  206.             _children = children;
  207.             _left = _right = this;
  208.             mark = false;
  209.             isSentinal = true;
  210.         }
  211.         public FibNode(T data) {
  212.             this();
  213.             _data = data;
  214.         }
  215.        
  216.         public boolean hasSiblings() {
  217.             return _left == this && _right == this;
  218.         }
  219.         public int getDegree() {
  220.             return _children.getCount();
  221.         }
  222.        
  223.         public FibNode<T> getRight() {
  224.             return _right;
  225.         }
  226.        
  227.         public FibNode<T> getLeft() {
  228.             return _left;
  229.         }
  230.        
  231.         public FibNode<T> getParent() {
  232.             return _parent;
  233.         }
  234.        
  235.         public FibList<T> getChildren() {
  236.             return _children;
  237.         }
  238.        
  239.         public T getData() {
  240.             return _data;
  241.         }
  242.        
  243.         public void addChild(FibNode<T> node) {
  244.             _children.add(node);
  245.             node.setParent(this);
  246.         }
  247.         public void setRight(FibNode<T> node) {
  248.             _right = node;
  249.         }
  250.        
  251.         public void setLeft(FibNode<T> node) {
  252.             _left = node;
  253.         }
  254.        
  255.         public void setParent(FibNode<T> node) {
  256.             _parent = node;
  257.         }
  258.        
  259.         public void setData(T data) {
  260.             _data = data;
  261.         }
  262.     }
  263.    
  264.     private class FibList<T>
  265.             implements java.lang.Iterable<FibNode<T>>
  266.     {
  267.         private final FibNode<T> _sentinal;
  268.         private int _count;
  269.        
  270.         public FibList() {
  271.             _count = 0;
  272.             _sentinal = new FibNode(null);
  273.         }
  274.        
  275.         public void add(FibNode<T> node) {
  276.             node.setRight(_sentinal.getRight());
  277.             _sentinal.getRight().setLeft(node);
  278.             _sentinal.setRight(node);
  279.             node.setLeft(_sentinal);
  280.             _count++;
  281.         }
  282.        
  283.         public void remove(FibNode<T> node) {
  284.             node.getLeft().setRight(node.getRight());
  285.             node.getRight().setLeft(node.getLeft());
  286.             _count--;
  287.         }
  288.        
  289.         public void addList(FibList<T> list) {
  290.             FibNode<T> otherSent = list._sentinal;
  291.             _sentinal.getLeft().setRight(otherSent.getRight());
  292.             otherSent.getLeft().setRight(_sentinal);
  293.            
  294.             _count += list._count;
  295.         }
  296.        
  297.         public int getCount() {
  298.             return _count;
  299.         }
  300.        
  301.         public FibNode<T> getHead() {
  302.             return (_count > 0) ? _sentinal.getRight() : null;
  303.         }
  304.        
  305.         public java.util.Iterator<FibNode<T>> iterator() {
  306.             return new FibListIterator(_sentinal);
  307.         }
  308.        
  309.         private class FibListIterator<T>
  310.                 implements java.util.Iterator<FibNode<T>>
  311.         {
  312.             private FibNode<T> _head;
  313.            
  314.             public FibListIterator(FibNode head) {
  315.                 if (head == null)
  316.                     throw new java.lang.IllegalArgumentException("FibListIterator.ctor");
  317.                
  318.                 _head = head;
  319.             }
  320.            
  321.             public boolean hasNext() {
  322.                 return (!_head.getRight().isSentinal);
  323.             }
  324.            
  325.             public FibNode<T> next() {
  326.                 FibNode<T> node = _head.getRight();
  327.                
  328.                 if (node.isSentinal)
  329.                     throw new java.util.NoSuchElementException("FibListIterator.next");
  330.                
  331.                 _head = node;
  332.                
  333.                 return node;
  334.             }
  335.            
  336.             public void remove() {
  337.                 throw new java.lang.UnsupportedOperationException("FibListIterator.remove");
  338.             }
  339.            
  340.         }
  341.     }
  342.  
  343. }
clone this paste RAW Paste Data