1 /* 2 * Copyright (c) 2003, 2013, 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 30 /** 31 * An unbounded priority {@linkplain Queue queue} based on a priority heap. 32 * The elements of the priority queue are ordered according to their 33 * {@linkplain Comparable natural ordering}, or by a {@link Comparator} 34 * provided at queue construction time, depending on which constructor is 35 * used. A priority queue does not permit {@code null} elements. 36 * A priority queue relying on natural ordering also does not permit 37 * insertion of non-comparable objects (doing so may result in 38 * {@code ClassCastException}). 39 * 40 * <p>The <em>head</em> of this queue is the <em>least</em> element 41 * with respect to the specified ordering. If multiple elements are 42 * tied for least value, the head is one of those elements -- ties are 43 * broken arbitrarily. The queue retrieval operations {@code poll}, 44 * {@code remove}, {@code peek}, and {@code element} access the 45 * element at the head of the queue. 46 * 47 * <p>A priority queue is unbounded, but has an internal 48 * <i>capacity</i> governing the size of an array used to store the 49 * elements on the queue. It is always at least as large as the queue 50 * size. As elements are added to a priority queue, its capacity 51 * grows automatically. The details of the growth policy are not 52 * specified. 53 * 54 * <p>This class and its iterator implement all of the 55 * <em>optional</em> methods of the {@link Collection} and {@link 56 * Iterator} interfaces. The Iterator provided in method {@link 57 * #iterator()} is <em>not</em> guaranteed to traverse the elements of 58 * the priority queue in any particular order. If you need ordered 59 * traversal, consider using {@code Arrays.sort(pq.toArray())}. 60 * 61 * <p><strong>Note that this implementation is not synchronized.</strong> 62 * Multiple threads should not access a {@code PriorityQueue} 63 * instance concurrently if any of the threads modifies the queue. 64 * Instead, use the thread-safe {@link 65 * java.util.concurrent.PriorityBlockingQueue} class. 66 * 67 * <p>Implementation note: this implementation provides 68 * O(log(n)) time for the enqueuing and dequeuing methods 69 * ({@code offer}, {@code poll}, {@code remove()} and {@code add}); 70 * linear time for the {@code remove(Object)} and {@code contains(Object)} 71 * methods; and constant time for the retrieval methods 72 * ({@code peek}, {@code element}, and {@code size}). 73 * 74 * <p>This class is a member of the 75 * <a href="{@docRoot}openjdk-redirect.html?v=8&path=/technotes/guides/collections/index.html"> 76 * Java Collections Framework</a>. 77 * 78 * @since 1.5 79 * @author Josh Bloch, Doug Lea 80 * @param <E> the type of elements held in this queue 81 */ 82 public class PriorityQueue<E> extends AbstractQueue<E> 83 implements java.io.Serializable { 84 85 private static final long serialVersionUID = -7720805057305804111L; 86 87 private static final int DEFAULT_INITIAL_CAPACITY = 11; 88 89 /** 90 * Priority queue represented as a balanced binary heap: the two 91 * children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The 92 * priority queue is ordered by comparator, or by the elements' 93 * natural ordering, if comparator is null: For each node n in the 94 * heap and each descendant d of n, n <= d. The element with the 95 * lowest value is in queue[0], assuming the queue is nonempty. 96 */ 97 transient Object[] queue; // non-private to simplify nested class access 98 99 /** 100 * The number of elements in the priority queue. 101 */ 102 int size; 103 104 /** 105 * The comparator, or null if priority queue uses elements' 106 * natural ordering. 107 */ 108 private final Comparator<? super E> comparator; 109 110 /** 111 * The number of times this priority queue has been 112 * <i>structurally modified</i>. See AbstractList for gory details. 113 */ 114 transient int modCount; // non-private to simplify nested class access 115 116 /** 117 * Creates a {@code PriorityQueue} with the default initial 118 * capacity (11) that orders its elements according to their 119 * {@linkplain Comparable natural ordering}. 120 */ PriorityQueue()121 public PriorityQueue() { 122 this(DEFAULT_INITIAL_CAPACITY, null); 123 } 124 125 /** 126 * Creates a {@code PriorityQueue} with the specified initial 127 * capacity that orders its elements according to their 128 * {@linkplain Comparable natural ordering}. 129 * 130 * @param initialCapacity the initial capacity for this priority queue 131 * @throws IllegalArgumentException if {@code initialCapacity} is less 132 * than 1 133 */ PriorityQueue(int initialCapacity)134 public PriorityQueue(int initialCapacity) { 135 this(initialCapacity, null); 136 } 137 138 /** 139 * Creates a {@code PriorityQueue} with the default initial capacity and 140 * whose elements are ordered according to the specified comparator. 141 * 142 * @param comparator the comparator that will be used to order this 143 * priority queue. If {@code null}, the {@linkplain Comparable 144 * natural ordering} of the elements will be used. 145 * @since 1.8 146 */ PriorityQueue(Comparator<? super E> comparator)147 public PriorityQueue(Comparator<? super E> comparator) { 148 this(DEFAULT_INITIAL_CAPACITY, comparator); 149 } 150 151 /** 152 * Creates a {@code PriorityQueue} with the specified initial capacity 153 * that orders its elements according to the specified comparator. 154 * 155 * @param initialCapacity the initial capacity for this priority queue 156 * @param comparator the comparator that will be used to order this 157 * priority queue. If {@code null}, the {@linkplain Comparable 158 * natural ordering} of the elements will be used. 159 * @throws IllegalArgumentException if {@code initialCapacity} is 160 * less than 1 161 */ PriorityQueue(int initialCapacity, Comparator<? super E> comparator)162 public PriorityQueue(int initialCapacity, 163 Comparator<? super E> comparator) { 164 // Note: This restriction of at least one is not actually needed, 165 // but continues for 1.5 compatibility 166 if (initialCapacity < 1) 167 throw new IllegalArgumentException(); 168 this.queue = new Object[initialCapacity]; 169 this.comparator = comparator; 170 } 171 172 /** 173 * Creates a {@code PriorityQueue} containing the elements in the 174 * specified collection. If the specified collection is an instance of 175 * a {@link SortedSet} or is another {@code PriorityQueue}, this 176 * priority queue will be ordered according to the same ordering. 177 * Otherwise, this priority queue will be ordered according to the 178 * {@linkplain Comparable natural ordering} of its elements. 179 * 180 * @param c the collection whose elements are to be placed 181 * into this priority queue 182 * @throws ClassCastException if elements of the specified collection 183 * cannot be compared to one another according to the priority 184 * queue's ordering 185 * @throws NullPointerException if the specified collection or any 186 * of its elements are null 187 */ 188 @SuppressWarnings("unchecked") PriorityQueue(Collection<? extends E> c)189 public PriorityQueue(Collection<? extends E> c) { 190 if (c instanceof SortedSet<?>) { 191 SortedSet<? extends E> ss = (SortedSet<? extends E>) c; 192 this.comparator = (Comparator<? super E>) ss.comparator(); 193 initElementsFromCollection(ss); 194 } 195 else if (c instanceof PriorityQueue<?>) { 196 PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c; 197 this.comparator = (Comparator<? super E>) pq.comparator(); 198 initFromPriorityQueue(pq); 199 } 200 else { 201 this.comparator = null; 202 initFromCollection(c); 203 } 204 } 205 206 /** 207 * Creates a {@code PriorityQueue} containing the elements in the 208 * specified priority queue. This priority queue will be 209 * ordered according to the same ordering as the given priority 210 * queue. 211 * 212 * @param c the priority queue whose elements are to be placed 213 * into this priority queue 214 * @throws ClassCastException if elements of {@code c} cannot be 215 * compared to one another according to {@code c}'s 216 * ordering 217 * @throws NullPointerException if the specified priority queue or any 218 * of its elements are null 219 */ 220 @SuppressWarnings("unchecked") PriorityQueue(PriorityQueue<? extends E> c)221 public PriorityQueue(PriorityQueue<? extends E> c) { 222 this.comparator = (Comparator<? super E>) c.comparator(); 223 initFromPriorityQueue(c); 224 } 225 226 /** 227 * Creates a {@code PriorityQueue} containing the elements in the 228 * specified sorted set. This priority queue will be ordered 229 * according to the same ordering as the given sorted set. 230 * 231 * @param c the sorted set whose elements are to be placed 232 * into this priority queue 233 * @throws ClassCastException if elements of the specified sorted 234 * set cannot be compared to one another according to the 235 * sorted set's ordering 236 * @throws NullPointerException if the specified sorted set or any 237 * of its elements are null 238 */ 239 @SuppressWarnings("unchecked") PriorityQueue(SortedSet<? extends E> c)240 public PriorityQueue(SortedSet<? extends E> c) { 241 this.comparator = (Comparator<? super E>) c.comparator(); 242 initElementsFromCollection(c); 243 } 244 initFromPriorityQueue(PriorityQueue<? extends E> c)245 private void initFromPriorityQueue(PriorityQueue<? extends E> c) { 246 if (c.getClass() == PriorityQueue.class) { 247 this.queue = c.toArray(); 248 this.size = c.size(); 249 } else { 250 initFromCollection(c); 251 } 252 } 253 initElementsFromCollection(Collection<? extends E> c)254 private void initElementsFromCollection(Collection<? extends E> c) { 255 Object[] a = c.toArray(); 256 // If c.toArray incorrectly doesn't return Object[], copy it. 257 if (a.getClass() != Object[].class) 258 a = Arrays.copyOf(a, a.length, Object[].class); 259 int len = a.length; 260 if (len == 1 || this.comparator != null) 261 for (Object e : a) 262 if (e == 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) >= 0; 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; 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 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 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 * @throws java.io.IOException if an I/O error occurs 760 */ writeObject(java.io.ObjectOutputStream s)761 private void writeObject(java.io.ObjectOutputStream s) 762 throws java.io.IOException { 763 // Write out element count, and any hidden stuff 764 s.defaultWriteObject(); 765 766 // Write out array length, for compatibility with 1.5 version 767 s.writeInt(Math.max(2, size + 1)); 768 769 // Write out all elements in the "proper order". 770 for (int i = 0; i < size; i++) 771 s.writeObject(queue[i]); 772 } 773 774 /** 775 * Reconstitutes the {@code PriorityQueue} instance from a stream 776 * (that is, deserializes it). 777 * 778 * @param s the stream 779 * @throws ClassNotFoundException if the class of a serialized object 780 * could not be found 781 * @throws java.io.IOException if an I/O error occurs 782 */ readObject(java.io.ObjectInputStream s)783 private void readObject(java.io.ObjectInputStream s) 784 throws java.io.IOException, ClassNotFoundException { 785 // Read in size, and any hidden stuff 786 s.defaultReadObject(); 787 788 // Read in (and discard) array length 789 s.readInt(); 790 791 queue = new Object[size]; 792 793 // Read in all elements. 794 for (int i = 0; i < size; i++) 795 queue[i] = s.readObject(); 796 797 // Elements are guaranteed to be in "proper order", but the 798 // spec has never explained what that might be. 799 heapify(); 800 } 801 802 /** 803 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> 804 * and <em>fail-fast</em> {@link Spliterator} over the elements in this 805 * queue. 806 * 807 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, 808 * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}. 809 * Overriding implementations should document the reporting of additional 810 * characteristic values. 811 * 812 * @return a {@code Spliterator} over the elements in this queue 813 * @since 1.8 814 */ spliterator()815 public final Spliterator<E> spliterator() { 816 return new PriorityQueueSpliterator<>(this, 0, -1, 0); 817 } 818 819 static final class PriorityQueueSpliterator<E> implements Spliterator<E> { 820 /* 821 * This is very similar to ArrayList Spliterator, except for 822 * extra null checks. 823 */ 824 private final PriorityQueue<E> pq; 825 private int index; // current index, modified on advance/split 826 private int fence; // -1 until first use 827 private int expectedModCount; // initialized when fence set 828 829 /** Creates new spliterator covering the given range. */ PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence, int expectedModCount)830 PriorityQueueSpliterator(PriorityQueue<E> pq, int origin, int fence, 831 int expectedModCount) { 832 this.pq = pq; 833 this.index = origin; 834 this.fence = fence; 835 this.expectedModCount = expectedModCount; 836 } 837 getFence()838 private int getFence() { // initialize fence to size on first use 839 int hi; 840 if ((hi = fence) < 0) { 841 expectedModCount = pq.modCount; 842 hi = fence = pq.size; 843 } 844 return hi; 845 } 846 trySplit()847 public PriorityQueueSpliterator<E> trySplit() { 848 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 849 return (lo >= mid) ? null : 850 new PriorityQueueSpliterator<>(pq, lo, index = mid, 851 expectedModCount); 852 } 853 854 @SuppressWarnings("unchecked") forEachRemaining(Consumer<? super E> action)855 public void forEachRemaining(Consumer<? super E> action) { 856 int i, hi, mc; // hoist accesses and checks from loop 857 PriorityQueue<E> q; Object[] a; 858 if (action == null) 859 throw new NullPointerException(); 860 if ((q = pq) != null && (a = q.queue) != null) { 861 if ((hi = fence) < 0) { 862 mc = q.modCount; 863 hi = q.size; 864 } 865 else 866 mc = expectedModCount; 867 if ((i = index) >= 0 && (index = hi) <= a.length) { 868 for (E e;; ++i) { 869 if (i < hi) { 870 if ((e = (E) a[i]) == null) // must be CME 871 break; 872 action.accept(e); 873 } 874 else if (q.modCount != mc) 875 break; 876 else 877 return; 878 } 879 } 880 } 881 throw new ConcurrentModificationException(); 882 } 883 tryAdvance(Consumer<? super E> action)884 public boolean tryAdvance(Consumer<? super E> action) { 885 if (action == null) 886 throw new NullPointerException(); 887 int hi = getFence(), lo = index; 888 if (lo >= 0 && lo < hi) { 889 index = lo + 1; 890 @SuppressWarnings("unchecked") E e = (E)pq.queue[lo]; 891 if (e == null) 892 throw new ConcurrentModificationException(); 893 action.accept(e); 894 if (pq.modCount != expectedModCount) 895 throw new ConcurrentModificationException(); 896 return true; 897 } 898 return false; 899 } 900 estimateSize()901 public long estimateSize() { 902 return (long) (getFence() - index); 903 } 904 characteristics()905 public int characteristics() { 906 return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL; 907 } 908 } 909 } 910