rev 51958 : 8211122: Reduce the number of internal classes made accessible to jdk.unsupported
Reviewed-by: alanb, dfuchs, kvn

   1 /*
   2  * Copyright (c) 2003, 2018, 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 import java.util.function.Consumer;
  29 import java.util.function.Predicate;
  30 import jdk.internal.misc.SharedSecrets;
  31 
  32 /**
  33  * An unbounded priority {@linkplain Queue queue} based on a priority heap.
  34  * The elements of the priority queue are ordered according to their
  35  * {@linkplain Comparable natural ordering}, or by a {@link Comparator}
  36  * provided at queue construction time, depending on which constructor is
  37  * used.  A priority queue does not permit {@code null} elements.
  38  * A priority queue relying on natural ordering also does not permit
  39  * insertion of non-comparable objects (doing so may result in
  40  * {@code ClassCastException}).
  41  *
  42  * <p>The <em>head</em> of this queue is the <em>least</em> element
  43  * with respect to the specified ordering.  If multiple elements are
  44  * tied for least value, the head is one of those elements -- ties are
  45  * broken arbitrarily.  The queue retrieval operations {@code poll},
  46  * {@code remove}, {@code peek}, and {@code element} access the
  47  * element at the head of the queue.
  48  *
  49  * <p>A priority queue is unbounded, but has an internal
  50  * <i>capacity</i> governing the size of an array used to store the
  51  * elements on the queue.  It is always at least as large as the queue
  52  * size.  As elements are added to a priority queue, its capacity
  53  * grows automatically.  The details of the growth policy are not
  54  * specified.
  55  *
  56  * <p>This class and its iterator implement all of the
  57  * <em>optional</em> methods of the {@link Collection} and {@link
  58  * Iterator} interfaces.  The Iterator provided in method {@link
  59  * #iterator()} and the Spliterator provided in method {@link #spliterator()}
  60  * are <em>not</em> guaranteed to traverse the elements of
  61  * the priority queue in any particular order. If you need ordered
  62  * traversal, consider using {@code Arrays.sort(pq.toArray())}.
  63  *
  64  * <p><strong>Note that this implementation is not synchronized.</strong>
  65  * Multiple threads should not access a {@code PriorityQueue}
  66  * instance concurrently if any of the threads modifies the queue.
  67  * Instead, use the thread-safe {@link
  68  * java.util.concurrent.PriorityBlockingQueue} class.
  69  *
  70  * <p>Implementation note: this implementation provides
  71  * O(log(n)) time for the enqueuing and dequeuing methods
  72  * ({@code offer}, {@code poll}, {@code remove()} and {@code add});
  73  * linear time for the {@code remove(Object)} and {@code contains(Object)}
  74  * methods; and constant time for the retrieval methods
  75  * ({@code peek}, {@code element}, and {@code size}).
  76  *
  77  * <p>This class is a member of the
  78  * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
  79  * Java Collections Framework</a>.
  80  *
  81  * @since 1.5
  82  * @author Josh Bloch, Doug Lea
  83  * @param <E> the type of elements held in this queue
  84  */
  85 @SuppressWarnings("unchecked")
  86 public class PriorityQueue<E> extends AbstractQueue<E>
  87     implements java.io.Serializable {
  88 
  89     private static final long serialVersionUID = -7720805057305804111L;
  90 
  91     private static final int DEFAULT_INITIAL_CAPACITY = 11;
  92 
  93     /**
  94      * Priority queue represented as a balanced binary heap: the two
  95      * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
  96      * priority queue is ordered by comparator, or by the elements'
  97      * natural ordering, if comparator is null: For each node n in the
  98      * heap and each descendant d of n, n <= d.  The element with the
  99      * lowest value is in queue[0], assuming the queue is nonempty.
 100      */
 101     transient Object[] queue; // non-private to simplify nested class access
 102 
 103     /**
 104      * The number of elements in the priority queue.
 105      */
 106     int size;
 107 
 108     /**
 109      * The comparator, or null if priority queue uses elements'
 110      * natural ordering.
 111      */
 112     private final Comparator<? super E> comparator;
 113 
 114     /**
 115      * The number of times this priority queue has been
 116      * <i>structurally modified</i>.  See AbstractList for gory details.
 117      */
 118     transient int modCount;     // non-private to simplify nested class access
 119 
 120     /**
 121      * Creates a {@code PriorityQueue} with the default initial
 122      * capacity (11) that orders its elements according to their
 123      * {@linkplain Comparable natural ordering}.
 124      */
 125     public PriorityQueue() {
 126         this(DEFAULT_INITIAL_CAPACITY, null);
 127     }
 128 
 129     /**
 130      * Creates a {@code PriorityQueue} with the specified initial
 131      * capacity that orders its elements according to their
 132      * {@linkplain Comparable natural ordering}.
 133      *
 134      * @param initialCapacity the initial capacity for this priority queue
 135      * @throws IllegalArgumentException if {@code initialCapacity} is less
 136      *         than 1
 137      */
 138     public PriorityQueue(int initialCapacity) {
 139         this(initialCapacity, null);
 140     }
 141 
 142     /**
 143      * Creates a {@code PriorityQueue} with the default initial capacity and
 144      * whose elements are ordered according to the specified comparator.
 145      *
 146      * @param  comparator the comparator that will be used to order this
 147      *         priority queue.  If {@code null}, the {@linkplain Comparable
 148      *         natural ordering} of the elements will be used.
 149      * @since 1.8
 150      */
 151     public PriorityQueue(Comparator<? super E> comparator) {
 152         this(DEFAULT_INITIAL_CAPACITY, comparator);
 153     }
 154 
 155     /**
 156      * Creates a {@code PriorityQueue} with the specified initial capacity
 157      * that orders its elements according to the specified comparator.
 158      *
 159      * @param  initialCapacity the initial capacity for this priority queue
 160      * @param  comparator the comparator that will be used to order this
 161      *         priority queue.  If {@code null}, the {@linkplain Comparable
 162      *         natural ordering} of the elements will be used.
 163      * @throws IllegalArgumentException if {@code initialCapacity} is
 164      *         less than 1
 165      */
 166     public PriorityQueue(int initialCapacity,
 167                          Comparator<? super E> comparator) {
 168         // Note: This restriction of at least one is not actually needed,
 169         // but continues for 1.5 compatibility
 170         if (initialCapacity < 1)
 171             throw new IllegalArgumentException();
 172         this.queue = new Object[initialCapacity];
 173         this.comparator = comparator;
 174     }
 175 
 176     /**
 177      * Creates a {@code PriorityQueue} containing the elements in the
 178      * specified collection.  If the specified collection is an instance of
 179      * a {@link SortedSet} or is another {@code PriorityQueue}, this
 180      * priority queue will be ordered according to the same ordering.
 181      * Otherwise, this priority queue will be ordered according to the
 182      * {@linkplain Comparable natural ordering} of its elements.
 183      *
 184      * @param  c the collection whose elements are to be placed
 185      *         into this priority queue
 186      * @throws ClassCastException if elements of the specified collection
 187      *         cannot be compared to one another according to the priority
 188      *         queue's ordering
 189      * @throws NullPointerException if the specified collection or any
 190      *         of its elements are null
 191      */
 192     public PriorityQueue(Collection<? extends E> c) {
 193         if (c instanceof SortedSet<?>) {
 194             SortedSet<? extends E> ss = (SortedSet<? extends E>) c;
 195             this.comparator = (Comparator<? super E>) ss.comparator();
 196             initElementsFromCollection(ss);
 197         }
 198         else if (c instanceof PriorityQueue<?>) {
 199             PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c;
 200             this.comparator = (Comparator<? super E>) pq.comparator();
 201             initFromPriorityQueue(pq);
 202         }
 203         else {
 204             this.comparator = null;
 205             initFromCollection(c);
 206         }
 207     }
 208 
 209     /**
 210      * Creates a {@code PriorityQueue} containing the elements in the
 211      * specified priority queue.  This priority queue will be
 212      * ordered according to the same ordering as the given priority
 213      * queue.
 214      *
 215      * @param  c the priority queue whose elements are to be placed
 216      *         into this priority queue
 217      * @throws ClassCastException if elements of {@code c} cannot be
 218      *         compared to one another according to {@code c}'s
 219      *         ordering
 220      * @throws NullPointerException if the specified priority queue or any
 221      *         of its elements are null
 222      */
 223     public PriorityQueue(PriorityQueue<? extends E> c) {
 224         this.comparator = (Comparator<? super E>) c.comparator();
 225         initFromPriorityQueue(c);
 226     }
 227 
 228     /**
 229      * Creates a {@code PriorityQueue} containing the elements in the
 230      * specified sorted set.   This priority queue will be ordered
 231      * according to the same ordering as the given sorted set.
 232      *
 233      * @param  c the sorted set whose elements are to be placed
 234      *         into this priority queue
 235      * @throws ClassCastException if elements of the specified sorted
 236      *         set cannot be compared to one another according to the
 237      *         sorted set's ordering
 238      * @throws NullPointerException if the specified sorted set or any
 239      *         of its elements are null
 240      */
 241     public PriorityQueue(SortedSet<? extends E> c) {
 242         this.comparator = (Comparator<? super E>) c.comparator();
 243         initElementsFromCollection(c);
 244     }
 245 
 246     /** Ensures that queue[0] exists, helping peek() and poll(). */
 247     private static Object[] ensureNonEmpty(Object[] es) {
 248         return (es.length > 0) ? es : new Object[1];
 249     }
 250 
 251     private void initFromPriorityQueue(PriorityQueue<? extends E> c) {
 252         if (c.getClass() == PriorityQueue.class) {
 253             this.queue = ensureNonEmpty(c.toArray());
 254             this.size = c.size();
 255         } else {
 256             initFromCollection(c);
 257         }
 258     }
 259 
 260     private void initElementsFromCollection(Collection<? extends E> c) {
 261         Object[] es = c.toArray();
 262         int len = es.length;
 263         // If c.toArray incorrectly doesn't return Object[], copy it.
 264         if (es.getClass() != Object[].class)
 265             es = Arrays.copyOf(es, len, Object[].class);
 266         if (len == 1 || this.comparator != null)
 267             for (Object e : es)
 268                 if (e == null)
 269                     throw new NullPointerException();
 270         this.queue = ensureNonEmpty(es);
 271         this.size = len;
 272     }
 273 
 274     /**
 275      * Initializes queue array with elements from the given Collection.
 276      *
 277      * @param c the collection
 278      */
 279     private void initFromCollection(Collection<? extends E> c) {
 280         initElementsFromCollection(c);
 281         heapify();
 282     }
 283 
 284     /**
 285      * The maximum size of array to allocate.
 286      * Some VMs reserve some header words in an array.
 287      * Attempts to allocate larger arrays may result in
 288      * OutOfMemoryError: Requested array size exceeds VM limit
 289      */
 290     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 291 
 292     /**
 293      * Increases the capacity of the array.
 294      *
 295      * @param minCapacity the desired minimum capacity
 296      */
 297     private void grow(int minCapacity) {
 298         int oldCapacity = queue.length;
 299         // Double size if small; else grow by 50%
 300         int newCapacity = oldCapacity + ((oldCapacity < 64) ?
 301                                          (oldCapacity + 2) :
 302                                          (oldCapacity >> 1));
 303         // overflow-conscious code
 304         if (newCapacity - MAX_ARRAY_SIZE > 0)
 305             newCapacity = hugeCapacity(minCapacity);
 306         queue = Arrays.copyOf(queue, newCapacity);
 307     }
 308 
 309     private static int hugeCapacity(int minCapacity) {
 310         if (minCapacity < 0) // overflow
 311             throw new OutOfMemoryError();
 312         return (minCapacity > MAX_ARRAY_SIZE) ?
 313             Integer.MAX_VALUE :
 314             MAX_ARRAY_SIZE;
 315     }
 316 
 317     /**
 318      * Inserts the specified element into this priority queue.
 319      *
 320      * @return {@code true} (as specified by {@link Collection#add})
 321      * @throws ClassCastException if the specified element cannot be
 322      *         compared with elements currently in this priority queue
 323      *         according to the priority queue's ordering
 324      * @throws NullPointerException if the specified element is null
 325      */
 326     public boolean add(E e) {
 327         return offer(e);
 328     }
 329 
 330     /**
 331      * Inserts the specified element into this priority queue.
 332      *
 333      * @return {@code true} (as specified by {@link Queue#offer})
 334      * @throws ClassCastException if the specified element cannot be
 335      *         compared with elements currently in this priority queue
 336      *         according to the priority queue's ordering
 337      * @throws NullPointerException if the specified element is null
 338      */
 339     public boolean offer(E e) {
 340         if (e == null)
 341             throw new NullPointerException();
 342         modCount++;
 343         int i = size;
 344         if (i >= queue.length)
 345             grow(i + 1);
 346         siftUp(i, e);
 347         size = i + 1;
 348         return true;
 349     }
 350 
 351     public E peek() {
 352         return (E) queue[0];
 353     }
 354 
 355     private int indexOf(Object o) {
 356         if (o != null) {
 357             final Object[] es = queue;
 358             for (int i = 0, n = size; i < n; i++)
 359                 if (o.equals(es[i]))
 360                     return i;
 361         }
 362         return -1;
 363     }
 364 
 365     /**
 366      * Removes a single instance of the specified element from this queue,
 367      * if it is present.  More formally, removes an element {@code e} such
 368      * that {@code o.equals(e)}, if this queue contains one or more such
 369      * elements.  Returns {@code true} if and only if this queue contained
 370      * the specified element (or equivalently, if this queue changed as a
 371      * result of the call).
 372      *
 373      * @param o element to be removed from this queue, if present
 374      * @return {@code true} if this queue changed as a result of the call
 375      */
 376     public boolean remove(Object o) {
 377         int i = indexOf(o);
 378         if (i == -1)
 379             return false;
 380         else {
 381             removeAt(i);
 382             return true;
 383         }
 384     }
 385 
 386     /**
 387      * Identity-based version for use in Itr.remove.
 388      *
 389      * @param o element to be removed from this queue, if present
 390      */
 391     void removeEq(Object o) {
 392         final Object[] es = queue;
 393         for (int i = 0, n = size; i < n; i++) {
 394             if (o == es[i]) {
 395                 removeAt(i);
 396                 break;
 397             }
 398         }
 399     }
 400 
 401     /**
 402      * Returns {@code true} if this queue contains the specified element.
 403      * More formally, returns {@code true} if and only if this queue contains
 404      * at least one element {@code e} such that {@code o.equals(e)}.
 405      *
 406      * @param o object to be checked for containment in this queue
 407      * @return {@code true} if this queue contains the specified element
 408      */
 409     public boolean contains(Object o) {
 410         return indexOf(o) >= 0;
 411     }
 412 
 413     /**
 414      * Returns an array containing all of the elements in this queue.
 415      * The elements are in no particular order.
 416      *
 417      * <p>The returned array will be "safe" in that no references to it are
 418      * maintained by this queue.  (In other words, this method must allocate
 419      * a new array).  The caller is thus free to modify the returned array.
 420      *
 421      * <p>This method acts as bridge between array-based and collection-based
 422      * APIs.
 423      *
 424      * @return an array containing all of the elements in this queue
 425      */
 426     public Object[] toArray() {
 427         return Arrays.copyOf(queue, size);
 428     }
 429 
 430     /**
 431      * Returns an array containing all of the elements in this queue; the
 432      * runtime type of the returned array is that of the specified array.
 433      * The returned array elements are in no particular order.
 434      * If the queue fits in the specified array, it is returned therein.
 435      * Otherwise, a new array is allocated with the runtime type of the
 436      * specified array and the size of this queue.
 437      *
 438      * <p>If the queue fits in the specified array with room to spare
 439      * (i.e., the array has more elements than the queue), the element in
 440      * the array immediately following the end of the collection is set to
 441      * {@code null}.
 442      *
 443      * <p>Like the {@link #toArray()} method, this method acts as bridge between
 444      * array-based and collection-based APIs.  Further, this method allows
 445      * precise control over the runtime type of the output array, and may,
 446      * under certain circumstances, be used to save allocation costs.
 447      *
 448      * <p>Suppose {@code x} is a queue known to contain only strings.
 449      * The following code can be used to dump the queue into a newly
 450      * allocated array of {@code String}:
 451      *
 452      * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
 453      *
 454      * Note that {@code toArray(new Object[0])} is identical in function to
 455      * {@code toArray()}.
 456      *
 457      * @param a the array into which the elements of the queue are to
 458      *          be stored, if it is big enough; otherwise, a new array of the
 459      *          same runtime type is allocated for this purpose.
 460      * @return an array containing all of the elements in this queue
 461      * @throws ArrayStoreException if the runtime type of the specified array
 462      *         is not a supertype of the runtime type of every element in
 463      *         this queue
 464      * @throws NullPointerException if the specified array is null
 465      */
 466     public <T> T[] toArray(T[] a) {
 467         final int size = this.size;
 468         if (a.length < size)
 469             // Make a new array of a's runtime type, but my contents:
 470             return (T[]) Arrays.copyOf(queue, size, a.getClass());
 471         System.arraycopy(queue, 0, a, 0, size);
 472         if (a.length > size)
 473             a[size] = null;
 474         return a;
 475     }
 476 
 477     /**
 478      * Returns an iterator over the elements in this queue. The iterator
 479      * does not return the elements in any particular order.
 480      *
 481      * @return an iterator over the elements in this queue
 482      */
 483     public Iterator<E> iterator() {
 484         return new Itr();
 485     }
 486 
 487     private final class Itr implements Iterator<E> {
 488         /**
 489          * Index (into queue array) of element to be returned by
 490          * subsequent call to next.
 491          */
 492         private int cursor;
 493 
 494         /**
 495          * Index of element returned by most recent call to next,
 496          * unless that element came from the forgetMeNot list.
 497          * Set to -1 if element is deleted by a call to remove.
 498          */
 499         private int lastRet = -1;
 500 
 501         /**
 502          * A queue of elements that were moved from the unvisited portion of
 503          * the heap into the visited portion as a result of "unlucky" element
 504          * removals during the iteration.  (Unlucky element removals are those
 505          * that require a siftup instead of a siftdown.)  We must visit all of
 506          * the elements in this list to complete the iteration.  We do this
 507          * after we've completed the "normal" iteration.
 508          *
 509          * We expect that most iterations, even those involving removals,
 510          * will not need to store elements in this field.
 511          */
 512         private ArrayDeque<E> forgetMeNot;
 513 
 514         /**
 515          * Element returned by the most recent call to next iff that
 516          * element was drawn from the forgetMeNot list.
 517          */
 518         private E lastRetElt;
 519 
 520         /**
 521          * The modCount value that the iterator believes that the backing
 522          * Queue should have.  If this expectation is violated, the iterator
 523          * has detected concurrent modification.
 524          */
 525         private int expectedModCount = modCount;
 526 
 527         Itr() {}                        // prevent access constructor creation
 528 
 529         public boolean hasNext() {
 530             return cursor < size ||
 531                 (forgetMeNot != null && !forgetMeNot.isEmpty());
 532         }
 533 
 534         public E next() {
 535             if (expectedModCount != modCount)
 536                 throw new ConcurrentModificationException();
 537             if (cursor < size)
 538                 return (E) queue[lastRet = cursor++];
 539             if (forgetMeNot != null) {
 540                 lastRet = -1;
 541                 lastRetElt = forgetMeNot.poll();
 542                 if (lastRetElt != null)
 543                     return lastRetElt;
 544             }
 545             throw new NoSuchElementException();
 546         }
 547 
 548         public void remove() {
 549             if (expectedModCount != modCount)
 550                 throw new ConcurrentModificationException();
 551             if (lastRet != -1) {
 552                 E moved = PriorityQueue.this.removeAt(lastRet);
 553                 lastRet = -1;
 554                 if (moved == null)
 555                     cursor--;
 556                 else {
 557                     if (forgetMeNot == null)
 558                         forgetMeNot = new ArrayDeque<>();
 559                     forgetMeNot.add(moved);
 560                 }
 561             } else if (lastRetElt != null) {
 562                 PriorityQueue.this.removeEq(lastRetElt);
 563                 lastRetElt = null;
 564             } else {
 565                 throw new IllegalStateException();
 566             }
 567             expectedModCount = modCount;
 568         }
 569     }
 570 
 571     public int size() {
 572         return size;
 573     }
 574 
 575     /**
 576      * Removes all of the elements from this priority queue.
 577      * The queue will be empty after this call returns.
 578      */
 579     public void clear() {
 580         modCount++;
 581         final Object[] es = queue;
 582         for (int i = 0, n = size; i < n; i++)
 583             es[i] = null;
 584         size = 0;
 585     }
 586 
 587     public E poll() {
 588         final Object[] es;
 589         final E result;
 590 
 591         if ((result = (E) ((es = queue)[0])) != null) {
 592             modCount++;
 593             final int n;
 594             final E x = (E) es[(n = --size)];
 595             es[n] = null;
 596             if (n > 0) {
 597                 final Comparator<? super E> cmp;
 598                 if ((cmp = comparator) == null)
 599                     siftDownComparable(0, x, es, n);
 600                 else
 601                     siftDownUsingComparator(0, x, es, n, cmp);
 602             }
 603         }
 604         return result;
 605     }
 606 
 607     /**
 608      * Removes the ith element from queue.
 609      *
 610      * Normally this method leaves the elements at up to i-1,
 611      * inclusive, untouched.  Under these circumstances, it returns
 612      * null.  Occasionally, in order to maintain the heap invariant,
 613      * it must swap a later element of the list with one earlier than
 614      * i.  Under these circumstances, this method returns the element
 615      * that was previously at the end of the list and is now at some
 616      * position before i. This fact is used by iterator.remove so as to
 617      * avoid missing traversing elements.
 618      */
 619     E removeAt(int i) {
 620         // assert i >= 0 && i < size;
 621         final Object[] es = queue;
 622         modCount++;
 623         int s = --size;
 624         if (s == i) // removed last element
 625             es[i] = null;
 626         else {
 627             E moved = (E) es[s];
 628             es[s] = null;
 629             siftDown(i, moved);
 630             if (es[i] == moved) {
 631                 siftUp(i, moved);
 632                 if (es[i] != moved)
 633                     return moved;
 634             }
 635         }
 636         return null;
 637     }
 638 
 639     /**
 640      * Inserts item x at position k, maintaining heap invariant by
 641      * promoting x up the tree until it is greater than or equal to
 642      * its parent, or is the root.
 643      *
 644      * To simplify and speed up coercions and comparisons, the
 645      * Comparable and Comparator versions are separated into different
 646      * methods that are otherwise identical. (Similarly for siftDown.)
 647      *
 648      * @param k the position to fill
 649      * @param x the item to insert
 650      */
 651     private void siftUp(int k, E x) {
 652         if (comparator != null)
 653             siftUpUsingComparator(k, x, queue, comparator);
 654         else
 655             siftUpComparable(k, x, queue);
 656     }
 657 
 658     private static <T> void siftUpComparable(int k, T x, Object[] es) {
 659         Comparable<? super T> key = (Comparable<? super T>) x;
 660         while (k > 0) {
 661             int parent = (k - 1) >>> 1;
 662             Object e = es[parent];
 663             if (key.compareTo((T) e) >= 0)
 664                 break;
 665             es[k] = e;
 666             k = parent;
 667         }
 668         es[k] = key;
 669     }
 670 
 671     private static <T> void siftUpUsingComparator(
 672         int k, T x, Object[] es, Comparator<? super T> cmp) {
 673         while (k > 0) {
 674             int parent = (k - 1) >>> 1;
 675             Object e = es[parent];
 676             if (cmp.compare(x, (T) e) >= 0)
 677                 break;
 678             es[k] = e;
 679             k = parent;
 680         }
 681         es[k] = x;
 682     }
 683 
 684     /**
 685      * Inserts item x at position k, maintaining heap invariant by
 686      * demoting x down the tree repeatedly until it is less than or
 687      * equal to its children or is a leaf.
 688      *
 689      * @param k the position to fill
 690      * @param x the item to insert
 691      */
 692     private void siftDown(int k, E x) {
 693         if (comparator != null)
 694             siftDownUsingComparator(k, x, queue, size, comparator);
 695         else
 696             siftDownComparable(k, x, queue, size);
 697     }
 698 
 699     private static <T> void siftDownComparable(int k, T x, Object[] es, int n) {
 700         // assert n > 0;
 701         Comparable<? super T> key = (Comparable<? super T>)x;
 702         int half = n >>> 1;           // loop while a non-leaf
 703         while (k < half) {
 704             int child = (k << 1) + 1; // assume left child is least
 705             Object c = es[child];
 706             int right = child + 1;
 707             if (right < n &&
 708                 ((Comparable<? super T>) c).compareTo((T) es[right]) > 0)
 709                 c = es[child = right];
 710             if (key.compareTo((T) c) <= 0)
 711                 break;
 712             es[k] = c;
 713             k = child;
 714         }
 715         es[k] = key;
 716     }
 717 
 718     private static <T> void siftDownUsingComparator(
 719         int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
 720         // assert n > 0;
 721         int half = n >>> 1;
 722         while (k < half) {
 723             int child = (k << 1) + 1;
 724             Object c = es[child];
 725             int right = child + 1;
 726             if (right < n && cmp.compare((T) c, (T) es[right]) > 0)
 727                 c = es[child = right];
 728             if (cmp.compare(x, (T) c) <= 0)
 729                 break;
 730             es[k] = c;
 731             k = child;
 732         }
 733         es[k] = x;
 734     }
 735 
 736     /**
 737      * Establishes the heap invariant (described above) in the entire tree,
 738      * assuming nothing about the order of the elements prior to the call.
 739      * This classic algorithm due to Floyd (1964) is known to be O(size).
 740      */
 741     private void heapify() {
 742         final Object[] es = queue;
 743         int n = size, i = (n >>> 1) - 1;
 744         final Comparator<? super E> cmp;
 745         if ((cmp = comparator) == null)
 746             for (; i >= 0; i--)
 747                 siftDownComparable(i, (E) es[i], es, n);
 748         else
 749             for (; i >= 0; i--)
 750                 siftDownUsingComparator(i, (E) es[i], es, n, cmp);
 751     }
 752 
 753     /**
 754      * Returns the comparator used to order the elements in this
 755      * queue, or {@code null} if this queue is sorted according to
 756      * the {@linkplain Comparable natural ordering} of its elements.
 757      *
 758      * @return the comparator used to order this queue, or
 759      *         {@code null} if this queue is sorted according to the
 760      *         natural ordering of its elements
 761      */
 762     public Comparator<? super E> comparator() {
 763         return comparator;
 764     }
 765 
 766     /**
 767      * Saves this queue to a stream (that is, serializes it).
 768      *
 769      * @param s the stream
 770      * @throws java.io.IOException if an I/O error occurs
 771      * @serialData The length of the array backing the instance is
 772      *             emitted (int), followed by all of its elements
 773      *             (each an {@code Object}) in the proper order.
 774      */
 775     private void writeObject(java.io.ObjectOutputStream s)
 776         throws java.io.IOException {
 777         // Write out element count, and any hidden stuff
 778         s.defaultWriteObject();
 779 
 780         // Write out array length, for compatibility with 1.5 version
 781         s.writeInt(Math.max(2, size + 1));
 782 
 783         // Write out all elements in the "proper order".
 784         final Object[] es = queue;
 785         for (int i = 0, n = size; i < n; i++)
 786             s.writeObject(es[i]);
 787     }
 788 
 789     /**
 790      * Reconstitutes the {@code PriorityQueue} instance from a stream
 791      * (that is, deserializes it).
 792      *
 793      * @param s the stream
 794      * @throws ClassNotFoundException if the class of a serialized object
 795      *         could not be found
 796      * @throws java.io.IOException if an I/O error occurs
 797      */
 798     private void readObject(java.io.ObjectInputStream s)
 799         throws java.io.IOException, ClassNotFoundException {
 800         // Read in size, and any hidden stuff
 801         s.defaultReadObject();
 802 
 803         // Read in (and discard) array length
 804         s.readInt();
 805 
 806         SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
 807         final Object[] es = queue = new Object[Math.max(size, 1)];
 808 
 809         // Read in all elements.
 810         for (int i = 0, n = size; i < n; i++)
 811             es[i] = s.readObject();
 812 
 813         // Elements are guaranteed to be in "proper order", but the
 814         // spec has never explained what that might be.
 815         heapify();
 816     }
 817 
 818     /**
 819      * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
 820      * and <em>fail-fast</em> {@link Spliterator} over the elements in this
 821      * queue. The spliterator does not traverse elements in any particular order
 822      * (the {@link Spliterator#ORDERED ORDERED} characteristic is not reported).
 823      *
 824      * <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
 825      * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}.
 826      * Overriding implementations should document the reporting of additional
 827      * characteristic values.
 828      *
 829      * @return a {@code Spliterator} over the elements in this queue
 830      * @since 1.8
 831      */
 832     public final Spliterator<E> spliterator() {
 833         return new PriorityQueueSpliterator(0, -1, 0);
 834     }
 835 
 836     final class PriorityQueueSpliterator implements Spliterator<E> {
 837         private int index;            // current index, modified on advance/split
 838         private int fence;            // -1 until first use
 839         private int expectedModCount; // initialized when fence set
 840 
 841         /** Creates new spliterator covering the given range. */
 842         PriorityQueueSpliterator(int origin, int fence, int expectedModCount) {
 843             this.index = origin;
 844             this.fence = fence;
 845             this.expectedModCount = expectedModCount;
 846         }
 847 
 848         private int getFence() { // initialize fence to size on first use
 849             int hi;
 850             if ((hi = fence) < 0) {
 851                 expectedModCount = modCount;
 852                 hi = fence = size;
 853             }
 854             return hi;
 855         }
 856 
 857         public PriorityQueueSpliterator trySplit() {
 858             int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
 859             return (lo >= mid) ? null :
 860                 new PriorityQueueSpliterator(lo, index = mid, expectedModCount);
 861         }
 862 
 863         public void forEachRemaining(Consumer<? super E> action) {
 864             if (action == null)
 865                 throw new NullPointerException();
 866             if (fence < 0) { fence = size; expectedModCount = modCount; }
 867             final Object[] es = queue;
 868             int i, hi; E e;
 869             for (i = index, index = hi = fence; i < hi; i++) {
 870                 if ((e = (E) es[i]) == null)
 871                     break;      // must be CME
 872                 action.accept(e);
 873             }
 874             if (modCount != expectedModCount)
 875                 throw new ConcurrentModificationException();
 876         }
 877 
 878         public boolean tryAdvance(Consumer<? super E> action) {
 879             if (action == null)
 880                 throw new NullPointerException();
 881             if (fence < 0) { fence = size; expectedModCount = modCount; }
 882             int i;
 883             if ((i = index) < fence) {
 884                 index = i + 1;
 885                 E e;
 886                 if ((e = (E) queue[i]) == null
 887                     || modCount != expectedModCount)
 888                     throw new ConcurrentModificationException();
 889                 action.accept(e);
 890                 return true;
 891             }
 892             return false;
 893         }
 894 
 895         public long estimateSize() {
 896             return getFence() - index;
 897         }
 898 
 899         public int characteristics() {
 900             return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL;
 901         }
 902     }
 903 
 904     /**
 905      * @throws NullPointerException {@inheritDoc}
 906      */
 907     public boolean removeIf(Predicate<? super E> filter) {
 908         Objects.requireNonNull(filter);
 909         return bulkRemove(filter);
 910     }
 911 
 912     /**
 913      * @throws NullPointerException {@inheritDoc}
 914      */
 915     public boolean removeAll(Collection<?> c) {
 916         Objects.requireNonNull(c);
 917         return bulkRemove(e -> c.contains(e));
 918     }
 919 
 920     /**
 921      * @throws NullPointerException {@inheritDoc}
 922      */
 923     public boolean retainAll(Collection<?> c) {
 924         Objects.requireNonNull(c);
 925         return bulkRemove(e -> !c.contains(e));
 926     }
 927 
 928     // A tiny bit set implementation
 929 
 930     private static long[] nBits(int n) {
 931         return new long[((n - 1) >> 6) + 1];
 932     }
 933     private static void setBit(long[] bits, int i) {
 934         bits[i >> 6] |= 1L << i;
 935     }
 936     private static boolean isClear(long[] bits, int i) {
 937         return (bits[i >> 6] & (1L << i)) == 0;
 938     }
 939 
 940     /** Implementation of bulk remove methods. */
 941     private boolean bulkRemove(Predicate<? super E> filter) {
 942         final int expectedModCount = ++modCount;
 943         final Object[] es = queue;
 944         final int end = size;
 945         int i;
 946         // Optimize for initial run of survivors
 947         for (i = 0; i < end && !filter.test((E) es[i]); i++)
 948             ;
 949         if (i >= end) {
 950             if (modCount != expectedModCount)
 951                 throw new ConcurrentModificationException();
 952             return false;
 953         }
 954         // Tolerate predicates that reentrantly access the collection for
 955         // read (but writers still get CME), so traverse once to find
 956         // elements to delete, a second pass to physically expunge.
 957         final int beg = i;
 958         final long[] deathRow = nBits(end - beg);
 959         deathRow[0] = 1L;   // set bit 0
 960         for (i = beg + 1; i < end; i++)
 961             if (filter.test((E) es[i]))
 962                 setBit(deathRow, i - beg);
 963         if (modCount != expectedModCount)
 964             throw new ConcurrentModificationException();
 965         int w = beg;
 966         for (i = beg; i < end; i++)
 967             if (isClear(deathRow, i - beg))
 968                 es[w++] = es[i];
 969         for (i = size = w; i < end; i++)
 970             es[i] = null;
 971         heapify();
 972         return true;
 973     }
 974 
 975     /**
 976      * @throws NullPointerException {@inheritDoc}
 977      */
 978     public void forEach(Consumer<? super E> action) {
 979         Objects.requireNonNull(action);
 980         final int expectedModCount = modCount;
 981         final Object[] es = queue;
 982         for (int i = 0, n = size; i < n; i++)
 983             action.accept((E) es[i]);
 984         if (expectedModCount != modCount)
 985             throw new ConcurrentModificationException();
 986     }
 987 }
--- EOF ---