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 26package java.util; 27 28import 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()} and the Spliterator provided in method {@link #spliterator()} 58 * are <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}/java/util/package-summary.html#CollectionsFramework"> 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 queue 82 */ 83public 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 int size; 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; // 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 */ 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 */ 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 */ 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 */ 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") 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") 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") 241 public PriorityQueue(SortedSet<? extends E> c) { 242 this.comparator = (Comparator<? super E>) c.comparator(); 243 initElementsFromCollection(c); 244 } 245 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 255 private void initElementsFromCollection(Collection<? extends E> c) { 256 Object[] a = c.toArray(); 257 // If c.toArray incorrectly doesn't return Object[], copy it. 258 if (a.getClass() != Object[].class) 259 a = Arrays.copyOf(a, a.length, Object[].class); 260 int len = a.length; 261 if (len == 1 || this.comparator != null) 262 for (Object e : a) 263 if (e == null) 264 throw new NullPointerException(); 265 this.queue = a; 266 this.size = a.length; 267 } 268 269 /** 270 * Initializes queue array with elements from the given Collection. 271 * 272 * @param c the collection 273 */ 274 private void initFromCollection(Collection<? extends E> c) { 275 initElementsFromCollection(c); 276 heapify(); 277 } 278 279 /** 280 * The maximum size of array to allocate. 281 * Some VMs reserve some header words in an array. 282 * Attempts to allocate larger arrays may result in 283 * OutOfMemoryError: Requested array size exceeds VM limit 284 */ 285 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 286 287 /** 288 * Increases the capacity of the array. 289 * 290 * @param minCapacity the desired minimum capacity 291 */ 292 private void grow(int minCapacity) { 293 int oldCapacity = queue.length; 294 // Double size if small; else grow by 50% 295 int newCapacity = oldCapacity + ((oldCapacity < 64) ? 296 (oldCapacity + 2) : 297 (oldCapacity >> 1)); 298 // overflow-conscious code 299 if (newCapacity - MAX_ARRAY_SIZE > 0) 300 newCapacity = hugeCapacity(minCapacity); 301 queue = Arrays.copyOf(queue, newCapacity); 302 } 303 304 private static int hugeCapacity(int minCapacity) { 305 if (minCapacity < 0) // overflow 306 throw new OutOfMemoryError(); 307 return (minCapacity > MAX_ARRAY_SIZE) ? 308 Integer.MAX_VALUE : 309 MAX_ARRAY_SIZE; 310 } 311 312 /** 313 * Inserts the specified element into this priority queue. 314 * 315 * @return {@code true} (as specified by {@link Collection#add}) 316 * @throws ClassCastException if the specified element cannot be 317 * compared with elements currently in this priority queue 318 * according to the priority queue's ordering 319 * @throws NullPointerException if the specified element is null 320 */ 321 public boolean add(E e) { 322 return offer(e); 323 } 324 325 /** 326 * Inserts the specified element into this priority queue. 327 * 328 * @return {@code true} (as specified by {@link Queue#offer}) 329 * @throws ClassCastException if the specified element cannot be 330 * compared with elements currently in this priority queue 331 * according to the priority queue's ordering 332 * @throws NullPointerException if the specified element is null 333 */ 334 public boolean offer(E e) { 335 if (e == null) 336 throw new NullPointerException(); 337 modCount++; 338 int i = size; 339 if (i >= queue.length) 340 grow(i + 1); 341 siftUp(i, e); 342 size = i + 1; 343 return true; 344 } 345 346 @SuppressWarnings("unchecked") 347 public E peek() { 348 return (size == 0) ? null : (E) queue[0]; 349 } 350 351 private int indexOf(Object o) { 352 if (o != null) { 353 for (int i = 0; i < size; i++) 354 if (o.equals(queue[i])) 355 return i; 356 } 357 return -1; 358 } 359 360 /** 361 * Removes a single instance of the specified element from this queue, 362 * if it is present. More formally, removes an element {@code e} such 363 * that {@code o.equals(e)}, if this queue contains one or more such 364 * elements. Returns {@code true} if and only if this queue contained 365 * the specified element (or equivalently, if this queue changed as a 366 * result of the call). 367 * 368 * @param o element to be removed from this queue, if present 369 * @return {@code true} if this queue changed as a result of the call 370 */ 371 public boolean remove(Object o) { 372 int i = indexOf(o); 373 if (i == -1) 374 return false; 375 else { 376 removeAt(i); 377 return true; 378 } 379 } 380 381 /** 382 * Version of remove using reference equality, not equals. 383 * Needed by iterator.remove. 384 * 385 * @param o element to be removed from this queue, if present 386 * @return {@code true} if removed 387 */ 388 boolean removeEq(Object o) { 389 for (int i = 0; i < size; i++) { 390 if (o == queue[i]) { 391 removeAt(i); 392 return true; 393 } 394 } 395 return false; 396 } 397 398 /** 399 * Returns {@code true} if this queue contains the specified element. 400 * More formally, returns {@code true} if and only if this queue contains 401 * at least one element {@code e} such that {@code o.equals(e)}. 402 * 403 * @param o object to be checked for containment in this queue 404 * @return {@code true} if this queue contains the specified element 405 */ 406 public boolean contains(Object o) { 407 return indexOf(o) >= 0; 408 } 409 410 /** 411 * Returns an array containing all of the elements in this queue. 412 * The elements are in no particular order. 413 * 414 * <p>The returned array will be "safe" in that no references to it are 415 * maintained by this queue. (In other words, this method must allocate 416 * a new array). The caller is thus free to modify the returned array. 417 * 418 * <p>This method acts as bridge between array-based and collection-based 419 * APIs. 420 * 421 * @return an array containing all of the elements in this queue 422 */ 423 public Object[] toArray() { 424 return Arrays.copyOf(queue, size); 425 } 426 427 /** 428 * Returns an array containing all of the elements in this queue; the 429 * runtime type of the returned array is that of the specified array. 430 * The returned array elements are in no particular order. 431 * If the queue fits in the specified array, it is returned therein. 432 * Otherwise, a new array is allocated with the runtime type of the 433 * specified array and the size of this queue. 434 * 435 * <p>If the queue fits in the specified array with room to spare 436 * (i.e., the array has more elements than the queue), the element in 437 * the array immediately following the end of the collection is set to 438 * {@code null}. 439 * 440 * <p>Like the {@link #toArray()} method, this method acts as bridge between 441 * array-based and collection-based APIs. Further, this method allows 442 * precise control over the runtime type of the output array, and may, 443 * under certain circumstances, be used to save allocation costs. 444 * 445 * <p>Suppose {@code x} is a queue known to contain only strings. 446 * The following code can be used to dump the queue into a newly 447 * allocated array of {@code String}: 448 * 449 * <pre> {@code String[] y = x.toArray(new String[0]);}</pre> 450 * 451 * Note that {@code toArray(new Object[0])} is identical in function to 452 * {@code toArray()}. 453 * 454 * @param a the array into which the elements of the queue are to 455 * be stored, if it is big enough; otherwise, a new array of the 456 * same runtime type is allocated for this purpose. 457 * @return an array containing all of the elements in this queue 458 * @throws ArrayStoreException if the runtime type of the specified array 459 * is not a supertype of the runtime type of every element in 460 * this queue 461 * @throws NullPointerException if the specified array is null 462 */ 463 @SuppressWarnings("unchecked") 464 public <T> T[] toArray(T[] a) { 465 final int size = this.size; 466 if (a.length < size) 467 // Make a new array of a's runtime type, but my contents: 468 return (T[]) Arrays.copyOf(queue, size, a.getClass()); 469 System.arraycopy(queue, 0, a, 0, size); 470 if (a.length > size) 471 a[size] = null; 472 return a; 473 } 474 475 /** 476 * Returns an iterator over the elements in this queue. The iterator 477 * does not return the elements in any particular order. 478 * 479 * @return an iterator over the elements in this queue 480 */ 481 public Iterator<E> iterator() { 482 return new Itr(); 483 } 484 485 private final class Itr implements Iterator<E> { 486 /** 487 * Index (into queue array) of element to be returned by 488 * subsequent call to next. 489 */ 490 private int cursor; 491 492 /** 493 * Index of element returned by most recent call to next, 494 * unless that element came from the forgetMeNot list. 495 * Set to -1 if element is deleted by a call to remove. 496 */ 497 private int lastRet = -1; 498 499 /** 500 * A queue of elements that were moved from the unvisited portion of 501 * the heap into the visited portion as a result of "unlucky" element 502 * removals during the iteration. (Unlucky element removals are those 503 * that require a siftup instead of a siftdown.) We must visit all of 504 * the elements in this list to complete the iteration. We do this 505 * after we've completed the "normal" iteration. 506 * 507 * We expect that most iterations, even those involving removals, 508 * will not need to store elements in this field. 509 */ 510 private ArrayDeque<E> forgetMeNot; 511 512 /** 513 * Element returned by the most recent call to next iff that 514 * element was drawn from the forgetMeNot list. 515 */ 516 private E lastRetElt; 517 518 /** 519 * The modCount value that the iterator believes that the backing 520 * Queue should have. If this expectation is violated, the iterator 521 * has detected concurrent modification. 522 */ 523 private int expectedModCount = modCount; 524 525 Itr() {} // prevent access constructor creation 526 527 public boolean hasNext() { 528 return cursor < size || 529 (forgetMeNot != null && !forgetMeNot.isEmpty()); 530 } 531 532 @SuppressWarnings("unchecked") 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 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 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 */ 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") 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") 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 */ 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") 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") 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 */ 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") 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") 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 * This classic algorithm due to Floyd (1964) is known to be O(size). 733 */ 734 @SuppressWarnings("unchecked") 735 private void heapify() { 736 final Object[] es = queue; 737 int i = (size >>> 1) - 1; 738 if (comparator == null) 739 for (; i >= 0; i--) 740 siftDownComparable(i, (E) es[i]); 741 else 742 for (; i >= 0; i--) 743 siftDownUsingComparator(i, (E) es[i]); 744 } 745 746 /** 747 * Returns the comparator used to order the elements in this 748 * queue, or {@code null} if this queue is sorted according to 749 * the {@linkplain Comparable natural ordering} of its elements. 750 * 751 * @return the comparator used to order this queue, or 752 * {@code null} if this queue is sorted according to the 753 * natural ordering of its elements 754 */ 755 public Comparator<? super E> comparator() { 756 return comparator; 757 } 758 759 /** 760 * Saves this queue to a stream (that is, serializes it). 761 * 762 * @param s the stream 763 * @throws java.io.IOException if an I/O error occurs 764 * @serialData The length of the array backing the instance is 765 * emitted (int), followed by all of its elements 766 * (each an {@code Object}) in the proper order. 767 */ 768 private void writeObject(java.io.ObjectOutputStream s) 769 throws java.io.IOException { 770 // Write out element count, and any hidden stuff 771 s.defaultWriteObject(); 772 773 // Write out array length, for compatibility with 1.5 version 774 s.writeInt(Math.max(2, size + 1)); 775 776 // Write out all elements in the "proper order". 777 for (int i = 0; i < size; i++) 778 s.writeObject(queue[i]); 779 } 780 781 /** 782 * Reconstitutes the {@code PriorityQueue} instance from a stream 783 * (that is, deserializes it). 784 * 785 * @param s the stream 786 * @throws ClassNotFoundException if the class of a serialized object 787 * could not be found 788 * @throws java.io.IOException if an I/O error occurs 789 */ 790 private void readObject(java.io.ObjectInputStream s) 791 throws java.io.IOException, ClassNotFoundException { 792 // Read in size, and any hidden stuff 793 s.defaultReadObject(); 794 795 // Read in (and discard) array length 796 s.readInt(); 797 798 queue = new Object[size]; 799 800 // Read in all elements. 801 for (int i = 0; i < size; i++) 802 queue[i] = s.readObject(); 803 804 // Elements are guaranteed to be in "proper order", but the 805 // spec has never explained what that might be. 806 heapify(); 807 } 808 809 /** 810 * Creates a <em><a href="Spliterator.html#binding">late-binding</a></em> 811 * and <em>fail-fast</em> {@link Spliterator} over the elements in this 812 * queue. The spliterator does not traverse elements in any particular order 813 * (the {@link Spliterator#ORDERED ORDERED} characteristic is not reported). 814 * 815 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, 816 * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}. 817 * Overriding implementations should document the reporting of additional 818 * characteristic values. 819 * 820 * @return a {@code Spliterator} over the elements in this queue 821 * @since 1.8 822 */ 823 public final Spliterator<E> spliterator() { 824 return new PriorityQueueSpliterator(0, -1, 0); 825 } 826 827 final class PriorityQueueSpliterator implements Spliterator<E> { 828 private int index; // current index, modified on advance/split 829 private int fence; // -1 until first use 830 private int expectedModCount; // initialized when fence set 831 832 /** Creates new spliterator covering the given range. */ 833 PriorityQueueSpliterator(int origin, int fence, int expectedModCount) { 834 this.index = origin; 835 this.fence = fence; 836 this.expectedModCount = expectedModCount; 837 } 838 839 private int getFence() { // initialize fence to size on first use 840 int hi; 841 if ((hi = fence) < 0) { 842 expectedModCount = modCount; 843 hi = fence = size; 844 } 845 return hi; 846 } 847 848 public PriorityQueueSpliterator trySplit() { 849 int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; 850 return (lo >= mid) ? null : 851 new PriorityQueueSpliterator(lo, index = mid, expectedModCount); 852 } 853 854 @SuppressWarnings("unchecked") 855 public void forEachRemaining(Consumer<? super E> action) { 856 if (action == null) 857 throw new NullPointerException(); 858 if (fence < 0) { fence = size; expectedModCount = modCount; } 859 final Object[] a = queue; 860 int i, hi; E e; 861 for (i = index, index = hi = fence; i < hi; i++) { 862 if ((e = (E) a[i]) == null) 863 break; // must be CME 864 action.accept(e); 865 } 866 if (modCount != expectedModCount) 867 throw new ConcurrentModificationException(); 868 } 869 870 @SuppressWarnings("unchecked") 871 public boolean tryAdvance(Consumer<? super E> action) { 872 if (action == null) 873 throw new NullPointerException(); 874 if (fence < 0) { fence = size; expectedModCount = modCount; } 875 int i; 876 if ((i = index) < fence) { 877 index = i + 1; 878 E e; 879 if ((e = (E) queue[i]) == null 880 || modCount != expectedModCount) 881 throw new ConcurrentModificationException(); 882 action.accept(e); 883 return true; 884 } 885 return false; 886 } 887 888 public long estimateSize() { 889 return getFence() - index; 890 } 891 892 public int characteristics() { 893 return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL; 894 } 895 } 896} 897