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