Save This Page
Home » openjdk-7 » java » util » [javadoc | source]
    1   /*
    2    * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
    3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
    4    *
    5    * This code is free software; you can redistribute it and/or modify it
    6    * under the terms of the GNU General Public License version 2 only, as
    7    * published by the Free Software Foundation.  Oracle designates this
    8    * particular file as subject to the "Classpath" exception as provided
    9    * by Oracle in the LICENSE file that accompanied this code.
   10    *
   11    * This code is distributed in the hope that it will be useful, but WITHOUT
   12    * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
   13    * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
   14    * version 2 for more details (a copy is included in the LICENSE file that
   15    * accompanied this code).
   16    *
   17    * You should have received a copy of the GNU General Public License version
   18    * 2 along with this work; if not, write to the Free Software Foundation,
   19    * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
   20    *
   21    * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
   22    * or visit www.oracle.com if you need additional information or have any
   23    * questions.
   24    */
   25   
   26   package java.util;
   27   
   28   /**
   29    * An unbounded priority {@linkplain Queue queue} based on a priority heap.
   30    * The elements of the priority queue are ordered according to their
   31    * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
   32    * provided at queue construction time, depending on which constructor is
   33    * used.  A priority queue does not permit {@code null} elements.
   34    * A priority queue relying on natural ordering also does not permit
   35    * insertion of non-comparable objects (doing so may result in
   36    * {@code ClassCastException}).
   37    *
   38    * <p>The <em>head</em> of this queue is the <em>least</em> element
   39    * with respect to the specified ordering.  If multiple elements are
   40    * tied for least value, the head is one of those elements -- ties are
   41    * broken arbitrarily.  The queue retrieval operations {@code poll},
   42    * {@code remove}, {@code peek}, and {@code element} access the
   43    * element at the head of the queue.
   44    *
   45    * <p>A priority queue is unbounded, but has an internal
   46    * <i>capacity</i> governing the size of an array used to store the
   47    * elements on the queue.  It is always at least as large as the queue
   48    * size.  As elements are added to a priority queue, its capacity
   49    * grows automatically.  The details of the growth policy are not
   50    * specified.
   51    *
   52    * <p>This class and its iterator implement all of the
   53    * <em>optional</em> methods of the {@link Collection} and {@link
   54    * Iterator} interfaces.  The Iterator provided in method {@link
   55    * #iterator()} is <em>not</em> guaranteed to traverse the elements of
   56    * the priority queue in any particular order. If you need ordered
   57    * traversal, consider using {@code Arrays.sort(pq.toArray())}.
   58    *
   59    * <p> <strong>Note that this implementation is not synchronized.</strong>
   60    * Multiple threads should not access a {@code PriorityQueue}
   61    * instance concurrently if any of the threads modifies the queue.
   62    * Instead, use the thread-safe {@link
   63    * java.util.concurrent.PriorityBlockingQueue} class.
   64    *
   65    * <p>Implementation note: this implementation provides
   66    * O(log(n)) time for the enqueing and dequeing methods
   67    * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
   68    * linear time for the {@code remove(Object)} and {@code contains(Object)}
   69    * methods; and constant time for the retrieval methods
   70    * ({@code peek}, {@code element}, and {@code size}).
   71    *
   72    * <p>This class is a member of the
   73    * <a href="{@docRoot}/../technotes/guides/collections/index.html">
   74    * Java Collections Framework</a>.
   75    *
   76    * @since 1.5
   77    * @author Josh Bloch, Doug Lea
   78    * @param <E> the type of elements held in this collection
   79    */
   80   public class PriorityQueue<E> extends AbstractQueue<E>
   81       implements java.io.Serializable {
   82   
   83       private static final long serialVersionUID = -7720805057305804111L;
   84   
   85       private static final int DEFAULT_INITIAL_CAPACITY = 11;
   86   
   87       /**
   88        * Priority queue represented as a balanced binary heap: the two
   89        * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
   90        * priority queue is ordered by comparator, or by the elements'
   91        * natural ordering, if comparator is null: For each node n in the
   92        * heap and each descendant d of n, n <= d.  The element with the
   93        * lowest value is in queue[0], assuming the queue is nonempty.
   94        */
   95       private transient Object[] queue;
   96   
   97       /**
   98        * The number of elements in the priority queue.
   99        */
  100       private int size = 0;
  101   
  102       /**
  103        * The comparator, or null if priority queue uses elements'
  104        * natural ordering.
  105        */
  106       private final Comparator<? super E> comparator;
  107   
  108       /**
  109        * The number of times this priority queue has been
  110        * <i>structurally modified</i>.  See AbstractList for gory details.
  111        */
  112       private transient int modCount = 0;
  113   
  114       /**
  115        * Creates a {@code PriorityQueue} with the default initial
  116        * capacity (11) that orders its elements according to their
  117        * {@linkplain Comparable natural ordering}.
  118        */
  119       public PriorityQueue() {
  120           this(DEFAULT_INITIAL_CAPACITY, null);
  121       }
  122   
  123       /**
  124        * Creates a {@code PriorityQueue} with the specified initial
  125        * capacity that orders its elements according to their
  126        * {@linkplain Comparable natural ordering}.
  127        *
  128        * @param initialCapacity the initial capacity for this priority queue
  129        * @throws IllegalArgumentException if {@code initialCapacity} is less
  130        *         than 1
  131        */
  132       public PriorityQueue(int initialCapacity) {
  133           this(initialCapacity, null);
  134       }
  135   
  136       /**
  137        * Creates a {@code PriorityQueue} with the specified initial capacity
  138        * that orders its elements according to the specified comparator.
  139        *
  140        * @param  initialCapacity the initial capacity for this priority queue
  141        * @param  comparator the comparator that will be used to order this
  142        *         priority queue.  If {@code null}, the {@linkplain Comparable
  143        *         natural ordering} of the elements will be used.
  144        * @throws IllegalArgumentException if {@code initialCapacity} is
  145        *         less than 1
  146        */
  147       public PriorityQueue(int initialCapacity,
  148                            Comparator<? super E> comparator) {
  149           // Note: This restriction of at least one is not actually needed,
  150           // but continues for 1.5 compatibility
  151           if (initialCapacity < 1)
  152               throw new IllegalArgumentException();
  153           this.queue = new Object[initialCapacity];
  154           this.comparator = comparator;
  155       }
  156   
  157       /**
  158        * Creates a {@code PriorityQueue} containing the elements in the
  159        * specified collection.  If the specified collection is an instance of
  160        * a {@link SortedSet} or is another {@code PriorityQueue}, this
  161        * priority queue will be ordered according to the same ordering.
  162        * Otherwise, this priority queue will be ordered according to the
  163        * {@linkplain Comparable natural ordering} of its elements.
  164        *
  165        * @param  c the collection whose elements are to be placed
  166        *         into this priority queue
  167        * @throws ClassCastException if elements of the specified collection
  168        *         cannot be compared to one another according to the priority
  169        *         queue's ordering
  170        * @throws NullPointerException if the specified collection or any
  171        *         of its elements are null
  172        */
  173       @SuppressWarnings("unchecked")
  174       public PriorityQueue(Collection<? extends E> c) {
  175           if (c instanceof SortedSet<?>) {
  176               SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
  177               this.comparator = (Comparator<? super E>) ss.comparator();
  178               initElementsFromCollection(ss);
  179           }
  180           else if (c instanceof PriorityQueue<?>) {
  181               PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
  182               this.comparator = (Comparator<? super E>) pq.comparator();
  183               initFromPriorityQueue(pq);
  184           }
  185           else {
  186               this.comparator = null;
  187               initFromCollection(c);
  188           }
  189       }
  190   
  191       /**
  192        * Creates a {@code PriorityQueue} containing the elements in the
  193        * specified priority queue.  This priority queue will be
  194        * ordered according to the same ordering as the given priority
  195        * queue.
  196        *
  197        * @param  c the priority queue whose elements are to be placed
  198        *         into this priority queue
  199        * @throws ClassCastException if elements of {@code c} cannot be
  200        *         compared to one another according to {@code c}'s
  201        *         ordering
  202        * @throws NullPointerException if the specified priority queue or any
  203        *         of its elements are null
  204        */
  205       @SuppressWarnings("unchecked")
  206       public PriorityQueue(PriorityQueue<? extends E> c) {
  207           this.comparator = (Comparator<? super E>) c.comparator();
  208           initFromPriorityQueue(c);
  209       }
  210   
  211       /**
  212        * Creates a {@code PriorityQueue} containing the elements in the
  213        * specified sorted set.   This priority queue will be ordered
  214        * according to the same ordering as the given sorted set.
  215        *
  216        * @param  c the sorted set whose elements are to be placed
  217        *         into this priority queue
  218        * @throws ClassCastException if elements of the specified sorted
  219        *         set cannot be compared to one another according to the
  220        *         sorted set's ordering
  221        * @throws NullPointerException if the specified sorted set or any
  222        *         of its elements are null
  223        */
  224       @SuppressWarnings("unchecked")
  225       public PriorityQueue(SortedSet<? extends E> c) {
  226           this.comparator = (Comparator<? super E>) c.comparator();
  227           initElementsFromCollection(c);
  228       }
  229   
  230       private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
  231           if (c.getClass() == PriorityQueue.class) {
  232               this.queue = c.toArray();
  233               this.size = c.size();
  234           } else {
  235               initFromCollection(c);
  236           }
  237       }
  238   
  239       private void initElementsFromCollection(Collection<? extends E> c) {
  240           Object[] a = c.toArray();
  241           // If c.toArray incorrectly doesn't return Object[], copy it.
  242           if (a.getClass() != Object[].class)
  243               a = Arrays.copyOf(a, a.length, Object[].class);
  244           int len = a.length;
  245           if (len == 1 || this.comparator != null)
  246               for (int i = 0; i < len; i++)
  247                   if (a[i] == null)
  248                       throw new NullPointerException();
  249           this.queue = a;
  250           this.size = a.length;
  251       }
  252   
  253       /**
  254        * Initializes queue array with elements from the given Collection.
  255        *
  256        * @param c the collection
  257        */
  258       private void initFromCollection(Collection<? extends E> c) {
  259           initElementsFromCollection(c);
  260           heapify();
  261       }
  262   
  263       /**
  264        * The maximum size of array to allocate.
  265        * Some VMs reserve some header words in an array.
  266        * Attempts to allocate larger arrays may result in
  267        * OutOfMemoryError: Requested array size exceeds VM limit
  268        */
  269       private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  270   
  271       /**
  272        * Increases the capacity of the array.
  273        *
  274        * @param minCapacity the desired minimum capacity
  275        */
  276       private void grow(int minCapacity) {
  277           int oldCapacity = queue.length;
  278           // Double size if small; else grow by 50%
  279           int newCapacity = oldCapacity + ((oldCapacity < 64) ?
  280                                            (oldCapacity + 2) :
  281                                            (oldCapacity >> 1));
  282           // overflow-conscious code
  283           if (newCapacity - MAX_ARRAY_SIZE > 0)
  284               newCapacity = hugeCapacity(minCapacity);
  285           queue = Arrays.copyOf(queue, newCapacity);
  286       }
  287   
  288       private static int hugeCapacity(int minCapacity) {
  289           if (minCapacity < 0) // overflow
  290               throw new OutOfMemoryError();
  291           return (minCapacity > MAX_ARRAY_SIZE) ?
  292               Integer.MAX_VALUE :
  293               MAX_ARRAY_SIZE;
  294       }
  295   
  296       /**
  297        * Inserts the specified element into this priority queue.
  298        *
  299        * @return {@code true} (as specified by {@link Collection#add})
  300        * @throws ClassCastException if the specified element cannot be
  301        *         compared with elements currently in this priority queue
  302        *         according to the priority queue's ordering
  303        * @throws NullPointerException if the specified element is null
  304        */
  305       public boolean add(E e) {
  306           return offer(e);
  307       }
  308   
  309       /**
  310        * Inserts the specified element into this priority queue.
  311        *
  312        * @return {@code true} (as specified by {@link Queue#offer})
  313        * @throws ClassCastException if the specified element cannot be
  314        *         compared with elements currently in this priority queue
  315        *         according to the priority queue's ordering
  316        * @throws NullPointerException if the specified element is null
  317        */
  318       public boolean offer(E e) {
  319           if (e == null)
  320               throw new NullPointerException();
  321           modCount++;
  322           int i = size;
  323           if (i >= queue.length)
  324               grow(i + 1);
  325           size = i + 1;
  326           if (i == 0)
  327               queue[0] = e;
  328           else
  329               siftUp(i, e);
  330           return true;
  331       }
  332   
  333       public E peek() {
  334           if (size == 0)
  335               return null;
  336           return (E) queue[0];
  337       }
  338   
  339       private int indexOf(Object o) {
  340           if (o != null) {
  341               for (int i = 0; i < size; i++)
  342                   if (o.equals(queue[i]))
  343                       return i;
  344           }
  345           return -1;
  346       }
  347   
  348       /**
  349        * Removes a single instance of the specified element from this queue,
  350        * if it is present.  More formally, removes an element {@code e} such
  351        * that {@code o.equals(e)}, if this queue contains one or more such
  352        * elements.  Returns {@code true} if and only if this queue contained
  353        * the specified element (or equivalently, if this queue changed as a
  354        * result of the call).
  355        *
  356        * @param o element to be removed from this queue, if present
  357        * @return {@code true} if this queue changed as a result of the call
  358        */
  359       public boolean remove(Object o) {
  360           int i = indexOf(o);
  361           if (i == -1)
  362               return false;
  363           else {
  364               removeAt(i);
  365               return true;
  366           }
  367       }
  368   
  369       /**
  370        * Version of remove using reference equality, not equals.
  371        * Needed by iterator.remove.
  372        *
  373        * @param o element to be removed from this queue, if present
  374        * @return {@code true} if removed
  375        */
  376       boolean removeEq(Object o) {
  377           for (int i = 0; i < size; i++) {
  378               if (o == queue[i]) {
  379                   removeAt(i);
  380                   return true;
  381               }
  382           }
  383           return false;
  384       }
  385   
  386       /**
  387        * Returns {@code true} if this queue contains the specified element.
  388        * More formally, returns {@code true} if and only if this queue contains
  389        * at least one element {@code e} such that {@code o.equals(e)}.
  390        *
  391        * @param o object to be checked for containment in this queue
  392        * @return {@code true} if this queue contains the specified element
  393        */
  394       public boolean contains(Object o) {
  395           return indexOf(o) != -1;
  396       }
  397   
  398       /**
  399        * Returns an array containing all of the elements in this queue.
  400        * The elements are in no particular order.
  401        *
  402        * <p>The returned array will be "safe" in that no references to it are
  403        * maintained by this queue.  (In other words, this method must allocate
  404        * a new array).  The caller is thus free to modify the returned array.
  405        *
  406        * <p>This method acts as bridge between array-based and collection-based
  407        * APIs.
  408        *
  409        * @return an array containing all of the elements in this queue
  410        */
  411       public Object[] toArray() {
  412           return Arrays.copyOf(queue, size);
  413       }
  414   
  415       /**
  416        * Returns an array containing all of the elements in this queue; the
  417        * runtime type of the returned array is that of the specified array.
  418        * The returned array elements are in no particular order.
  419        * If the queue fits in the specified array, it is returned therein.
  420        * Otherwise, a new array is allocated with the runtime type of the
  421        * specified array and the size of this queue.
  422        *
  423        * <p>If the queue fits in the specified array with room to spare
  424        * (i.e., the array has more elements than the queue), the element in
  425        * the array immediately following the end of the collection is set to
  426        * {@code null}.
  427        *
  428        * <p>Like the {@link #toArray()} method, this method acts as bridge between
  429        * array-based and collection-based APIs.  Further, this method allows
  430        * precise control over the runtime type of the output array, and may,
  431        * under certain circumstances, be used to save allocation costs.
  432        *
  433        * <p>Suppose <tt>x</tt> is a queue known to contain only strings.
  434        * The following code can be used to dump the queue into a newly
  435        * allocated array of <tt>String</tt>:
  436        *
  437        * <pre>
  438        *     String[] y = x.toArray(new String[0]);</pre>
  439        *
  440        * Note that <tt>toArray(new Object[0])</tt> is identical in function to
  441        * <tt>toArray()</tt>.
  442        *
  443        * @param a the array into which the elements of the queue are to
  444        *          be stored, if it is big enough; otherwise, a new array of the
  445        *          same runtime type is allocated for this purpose.
  446        * @return an array containing all of the elements in this queue
  447        * @throws ArrayStoreException if the runtime type of the specified array
  448        *         is not a supertype of the runtime type of every element in
  449        *         this queue
  450        * @throws NullPointerException if the specified array is null
  451        */
  452       public <T> T[] toArray(T[] a) {
  453           if (a.length < size)
  454               // Make a new array of a's runtime type, but my contents:
  455               return (T[]) Arrays.copyOf(queue, size, a.getClass());
  456           System.arraycopy(queue, 0, a, 0, size);
  457           if (a.length > size)
  458               a[size] = null;
  459           return a;
  460       }
  461   
  462       /**
  463        * Returns an iterator over the elements in this queue. The iterator
  464        * does not return the elements in any particular order.
  465        *
  466        * @return an iterator over the elements in this queue
  467        */
  468       public Iterator<E> iterator() {
  469           return new Itr();
  470       }
  471   
  472       private final class Itr implements Iterator<E> {
  473           /**
  474            * Index (into queue array) of element to be returned by
  475            * subsequent call to next.
  476            */
  477           private int cursor = 0;
  478   
  479           /**
  480            * Index of element returned by most recent call to next,
  481            * unless that element came from the forgetMeNot list.
  482            * Set to -1 if element is deleted by a call to remove.
  483            */
  484           private int lastRet = -1;
  485   
  486           /**
  487            * A queue of elements that were moved from the unvisited portion of
  488            * the heap into the visited portion as a result of "unlucky" element
  489            * removals during the iteration.  (Unlucky element removals are those
  490            * that require a siftup instead of a siftdown.)  We must visit all of
  491            * the elements in this list to complete the iteration.  We do this
  492            * after we've completed the "normal" iteration.
  493            *
  494            * We expect that most iterations, even those involving removals,
  495            * will not need to store elements in this field.
  496            */
  497           private ArrayDeque<E> forgetMeNot = null;
  498   
  499           /**
  500            * Element returned by the most recent call to next iff that
  501            * element was drawn from the forgetMeNot list.
  502            */
  503           private E lastRetElt = null;
  504   
  505           /**
  506            * The modCount value that the iterator believes that the backing
  507            * Queue should have.  If this expectation is violated, the iterator
  508            * has detected concurrent modification.
  509            */
  510           private int expectedModCount = modCount;
  511   
  512           public boolean hasNext() {
  513               return cursor < size ||
  514                   (forgetMeNot != null && !forgetMeNot.isEmpty());
  515           }
  516   
  517           public E next() {
  518               if (expectedModCount != modCount)
  519                   throw new ConcurrentModificationException();
  520               if (cursor < size)
  521                   return (E) queue[lastRet = cursor++];
  522               if (forgetMeNot != null) {
  523                   lastRet = -1;
  524                   lastRetElt = forgetMeNot.poll();
  525                   if (lastRetElt != null)
  526                       return lastRetElt;
  527               }
  528               throw new NoSuchElementException();
  529           }
  530   
  531           public void remove() {
  532               if (expectedModCount != modCount)
  533                   throw new ConcurrentModificationException();
  534               if (lastRet != -1) {
  535                   E moved = PriorityQueue.this.removeAt(lastRet);
  536                   lastRet = -1;
  537                   if (moved == null)
  538                       cursor--;
  539                   else {
  540                       if (forgetMeNot == null)
  541                           forgetMeNot = new ArrayDeque<>();
  542                       forgetMeNot.add(moved);
  543                   }
  544               } else if (lastRetElt != null) {
  545                   PriorityQueue.this.removeEq(lastRetElt);
  546                   lastRetElt = null;
  547               } else {
  548                   throw new IllegalStateException();
  549               }
  550               expectedModCount = modCount;
  551           }
  552       }
  553   
  554       public int size() {
  555           return size;
  556       }
  557   
  558       /**
  559        * Removes all of the elements from this priority queue.
  560        * The queue will be empty after this call returns.
  561        */
  562       public void clear() {
  563           modCount++;
  564           for (int i = 0; i < size; i++)
  565               queue[i] = null;
  566           size = 0;
  567       }
  568   
  569       public E poll() {
  570           if (size == 0)
  571               return null;
  572           int s = --size;
  573           modCount++;
  574           E result = (E) queue[0];
  575           E x = (E) queue[s];
  576           queue[s] = null;
  577           if (s != 0)
  578               siftDown(0, x);
  579           return result;
  580       }
  581   
  582       /**
  583        * Removes the ith element from queue.
  584        *
  585        * Normally this method leaves the elements at up to i-1,
  586        * inclusive, untouched.  Under these circumstances, it returns
  587        * null.  Occasionally, in order to maintain the heap invariant,
  588        * it must swap a later element of the list with one earlier than
  589        * i.  Under these circumstances, this method returns the element
  590        * that was previously at the end of the list and is now at some
  591        * position before i. This fact is used by iterator.remove so as to
  592        * avoid missing traversing elements.
  593        */
  594       private E removeAt(int i) {
  595           assert i >= 0 && i < size;
  596           modCount++;
  597           int s = --size;
  598           if (s == i) // removed last element
  599               queue[i] = null;
  600           else {
  601               E moved = (E) queue[s];
  602               queue[s] = null;
  603               siftDown(i, moved);
  604               if (queue[i] == moved) {
  605                   siftUp(i, moved);
  606                   if (queue[i] != moved)
  607                       return moved;
  608               }
  609           }
  610           return null;
  611       }
  612   
  613       /**
  614        * Inserts item x at position k, maintaining heap invariant by
  615        * promoting x up the tree until it is greater than or equal to
  616        * its parent, or is the root.
  617        *
  618        * To simplify and speed up coercions and comparisons. the
  619        * Comparable and Comparator versions are separated into different
  620        * methods that are otherwise identical. (Similarly for siftDown.)
  621        *
  622        * @param k the position to fill
  623        * @param x the item to insert
  624        */
  625       private void siftUp(int k, E x) {
  626           if (comparator != null)
  627               siftUpUsingComparator(k, x);
  628           else
  629               siftUpComparable(k, x);
  630       }
  631   
  632       private void siftUpComparable(int k, E x) {
  633           Comparable<? super E> key = (Comparable<? super E>) x;
  634           while (k > 0) {
  635               int parent = (k - 1) >>> 1;
  636               Object e = queue[parent];
  637               if (key.compareTo((E) e) >= 0)
  638                   break;
  639               queue[k] = e;
  640               k = parent;
  641           }
  642           queue[k] = key;
  643       }
  644   
  645       private void siftUpUsingComparator(int k, E x) {
  646           while (k > 0) {
  647               int parent = (k - 1) >>> 1;
  648               Object e = queue[parent];
  649               if (comparator.compare(x, (E) e) >= 0)
  650                   break;
  651               queue[k] = e;
  652               k = parent;
  653           }
  654           queue[k] = x;
  655       }
  656   
  657       /**
  658        * Inserts item x at position k, maintaining heap invariant by
  659        * demoting x down the tree repeatedly until it is less than or
  660        * equal to its children or is a leaf.
  661        *
  662        * @param k the position to fill
  663        * @param x the item to insert
  664        */
  665       private void siftDown(int k, E x) {
  666           if (comparator != null)
  667               siftDownUsingComparator(k, x);
  668           else
  669               siftDownComparable(k, x);
  670       }
  671   
  672       private void siftDownComparable(int k, E x) {
  673           Comparable<? super E> key = (Comparable<? super E>)x;
  674           int half = size >>> 1;        // loop while a non-leaf
  675           while (k < half) {
  676               int child = (k << 1) + 1; // assume left child is least
  677               Object c = queue[child];
  678               int right = child + 1;
  679               if (right < size &&
  680                   ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
  681                   c = queue[child = right];
  682               if (key.compareTo((E) c) <= 0)
  683                   break;
  684               queue[k] = c;
  685               k = child;
  686           }
  687           queue[k] = key;
  688       }
  689   
  690       private void siftDownUsingComparator(int k, E x) {
  691           int half = size >>> 1;
  692           while (k < half) {
  693               int child = (k << 1) + 1;
  694               Object c = queue[child];
  695               int right = child + 1;
  696               if (right < size &&
  697                   comparator.compare((E) c, (E) queue[right]) > 0)
  698                   c = queue[child = right];
  699               if (comparator.compare(x, (E) c) <= 0)
  700                   break;
  701               queue[k] = c;
  702               k = child;
  703           }
  704           queue[k] = x;
  705       }
  706   
  707       /**
  708        * Establishes the heap invariant (described above) in the entire tree,
  709        * assuming nothing about the order of the elements prior to the call.
  710        */
  711       private void heapify() {
  712           for (int i = (size >>> 1) - 1; i >= 0; i--)
  713               siftDown(i, (E) queue[i]);
  714       }
  715   
  716       /**
  717        * Returns the comparator used to order the elements in this
  718        * queue, or {@code null} if this queue is sorted according to
  719        * the {@linkplain Comparable natural ordering} of its elements.
  720        *
  721        * @return the comparator used to order this queue, or
  722        *         {@code null} if this queue is sorted according to the
  723        *         natural ordering of its elements
  724        */
  725       public Comparator<? super E> comparator() {
  726           return comparator;
  727       }
  728   
  729       /**
  730        * Saves the state of the instance to a stream (that
  731        * is, serializes it).
  732        *
  733        * @serialData The length of the array backing the instance is
  734        *             emitted (int), followed by all of its elements
  735        *             (each an {@code Object}) in the proper order.
  736        * @param s the stream
  737        */
  738       private void writeObject(java.io.ObjectOutputStream s)
  739           throws java.io.IOException{
  740           // Write out element count, and any hidden stuff
  741           s.defaultWriteObject();
  742   
  743           // Write out array length, for compatibility with 1.5 version
  744           s.writeInt(Math.max(2, size + 1));
  745   
  746           // Write out all elements in the "proper order".
  747           for (int i = 0; i < size; i++)
  748               s.writeObject(queue[i]);
  749       }
  750   
  751       /**
  752        * Reconstitutes the {@code PriorityQueue} instance from a stream
  753        * (that is, deserializes it).
  754        *
  755        * @param s the stream
  756        */
  757       private void readObject(java.io.ObjectInputStream s)
  758           throws java.io.IOException, ClassNotFoundException {
  759           // Read in size, and any hidden stuff
  760           s.defaultReadObject();
  761   
  762           // Read in (and discard) array length
  763           s.readInt();
  764   
  765           queue = new Object[size];
  766   
  767           // Read in all elements.
  768           for (int i = 0; i < size; i++)
  769               queue[i] = s.readObject();
  770   
  771           // Elements are guaranteed to be in "proper order", but the
  772           // spec has never explained what that might be.
  773           heapify();
  774       }
  775   }

Save This Page
Home » openjdk-7 » java » util » [javadoc | source]