--- jsr166/src/main/java/util/PriorityQueue.java 2015/06/16 23:06:01 1.106 +++ jsr166/src/main/java/util/PriorityQueue.java 2016/12/29 23:14:34 1.118 @@ -54,7 +54,8 @@ import java.util.function.Consumer; *

This class and its iterator implement all of the * optional methods of the {@link Collection} and {@link * Iterator} interfaces. The Iterator provided in method {@link - * #iterator()} is not guaranteed to traverse the elements of + * #iterator()} and the Spliterator provided in method {@link #spliterator()} + * are not guaranteed to traverse the elements of * the priority queue in any particular order. If you need ordered * traversal, consider using {@code Arrays.sort(pq.toArray())}. * @@ -99,7 +100,7 @@ public class PriorityQueue extends Ab /** * The number of elements in the priority queue. */ - private int size; + int size; /** * The comparator, or null if priority queue uses elements' @@ -337,11 +338,8 @@ public class PriorityQueue extends Ab int i = size; if (i >= queue.length) grow(i + 1); + siftUp(i, e); size = i + 1; - if (i == 0) - queue[0] = e; - else - siftUp(i, e); return true; } @@ -524,6 +522,8 @@ public class PriorityQueue extends Ab */ private int expectedModCount = modCount; + Itr() {} // prevent access constructor creation + public boolean hasNext() { return cursor < size || (forgetMeNot != null && !forgetMeNot.isEmpty()); @@ -609,7 +609,7 @@ public class PriorityQueue extends Ab * avoid missing traversing elements. */ @SuppressWarnings("unchecked") - private E removeAt(int i) { + E removeAt(int i) { // assert i >= 0 && i < size; modCount++; int s = --size; @@ -633,7 +633,7 @@ public class PriorityQueue extends Ab * promoting x up the tree until it is greater than or equal to * its parent, or is the root. * - * To simplify and speed up coercions and comparisons. the + * To simplify and speed up coercions and comparisons, the * Comparable and Comparator versions are separated into different * methods that are otherwise identical. (Similarly for siftDown.) * @@ -729,11 +729,18 @@ public class PriorityQueue extends Ab /** * Establishes the heap invariant (described above) in the entire tree, * assuming nothing about the order of the elements prior to the call. + * This classic algorithm due to Floyd (1964) is known to be O(size). */ @SuppressWarnings("unchecked") private void heapify() { - for (int i = (size >>> 1) - 1; i >= 0; i--) - siftDown(i, (E) queue[i]); + final Object[] es = queue; + int i = (size >>> 1) - 1; + if (comparator == null) + for (; i >= 0; i--) + siftDownComparable(i, (E) es[i]); + else + for (; i >= 0; i--) + siftDownUsingComparator(i, (E) es[i]); } /** @@ -752,11 +759,11 @@ public class PriorityQueue extends Ab /** * Saves this queue to a stream (that is, serializes it). * + * @param s the stream + * @throws java.io.IOException if an I/O error occurs * @serialData The length of the array backing the instance is * emitted (int), followed by all of its elements * (each an {@code Object}) in the proper order. - * @param s the stream - * @throws java.io.IOException if an I/O error occurs */ private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { @@ -802,7 +809,8 @@ public class PriorityQueue extends Ab /** * Creates a late-binding * and fail-fast {@link Spliterator} over the elements in this - * queue. + * queue. The spliterator does not traverse elements in any particular order + * (the {@link Spliterator#ORDERED ORDERED} characteristic is not reported). * *

The {@code Spliterator} reports {@link Spliterator#SIZED}, * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}. @@ -813,23 +821,16 @@ public class PriorityQueue extends Ab * @since 1.8 */ public final Spliterator spliterator() { - return new PriorityQueueSpliterator<>(this, 0, -1, 0); + return new PriorityQueueSpliterator(0, -1, 0); } - static final class PriorityQueueSpliterator implements Spliterator { - /* - * This is very similar to ArrayList Spliterator, except for - * extra null checks. - */ - private final PriorityQueue pq; + final class PriorityQueueSpliterator implements Spliterator { private int index; // current index, modified on advance/split private int fence; // -1 until first use private int expectedModCount; // initialized when fence set - /** Creates new spliterator covering the given range */ - PriorityQueueSpliterator(PriorityQueue pq, int origin, int fence, - int expectedModCount) { - this.pq = pq; + /** Creates new spliterator covering the given range. */ + PriorityQueueSpliterator(int origin, int fence, int expectedModCount) { this.index = origin; this.fence = fence; this.expectedModCount = expectedModCount; @@ -838,68 +839,54 @@ public class PriorityQueue extends Ab private int getFence() { // initialize fence to size on first use int hi; if ((hi = fence) < 0) { - expectedModCount = pq.modCount; - hi = fence = pq.size; + expectedModCount = modCount; + hi = fence = size; } return hi; } - public PriorityQueueSpliterator trySplit() { + public PriorityQueueSpliterator trySplit() { int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : - new PriorityQueueSpliterator<>(pq, lo, index = mid, - expectedModCount); + new PriorityQueueSpliterator(lo, index = mid, expectedModCount); } @SuppressWarnings("unchecked") public void forEachRemaining(Consumer action) { - int i, hi, mc; // hoist accesses and checks from loop - PriorityQueue q; Object[] a; if (action == null) throw new NullPointerException(); - if ((q = pq) != null && (a = q.queue) != null) { - if ((hi = fence) < 0) { - mc = q.modCount; - hi = q.size; - } - else - mc = expectedModCount; - if ((i = index) >= 0 && (index = hi) <= a.length) { - for (E e;; ++i) { - if (i < hi) { - if ((e = (E) a[i]) == null) // must be CME - break; - action.accept(e); - } - else if (q.modCount != mc) - break; - else - return; - } - } + if (fence < 0) { fence = size; expectedModCount = modCount; } + final Object[] a = queue; + int i, hi; E e; + for (i = index, index = hi = fence; i < hi; i++) { + if ((e = (E) a[i]) == null) + break; // must be CME + action.accept(e); } - throw new ConcurrentModificationException(); + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); } + @SuppressWarnings("unchecked") public boolean tryAdvance(Consumer action) { if (action == null) throw new NullPointerException(); - int hi = getFence(), lo = index; - if (lo >= 0 && lo < hi) { - index = lo + 1; - @SuppressWarnings("unchecked") E e = (E)pq.queue[lo]; - if (e == null) + if (fence < 0) { fence = size; expectedModCount = modCount; } + int i; + if ((i = index) < fence) { + index = i + 1; + E e; + if ((e = (E) queue[i]) == null + || modCount != expectedModCount) throw new ConcurrentModificationException(); action.accept(e); - if (pq.modCount != expectedModCount) - throw new ConcurrentModificationException(); return true; } return false; } public long estimateSize() { - return (long) (getFence() - index); + return getFence() - index; } public int characteristics() {