--- jsr166/src/main/java/util/PriorityQueue.java 2013/01/19 18:18:10 1.85 +++ jsr166/src/main/java/util/PriorityQueue.java 2014/12/31 09:37:20 1.103 @@ -24,10 +24,8 @@ */ package java.util; -import java.util.stream.Stream; -import java.util.Spliterator; -import java.util.stream.Streams; -import java.util.function.Block; + +import java.util.function.Consumer; /** * An unbounded priority {@linkplain Queue queue} based on a priority heap. @@ -67,7 +65,7 @@ import java.util.function.Block; * java.util.concurrent.PriorityBlockingQueue} class. * *

Implementation note: this implementation provides - * O(log(n)) time for the enqueing and dequeing methods + * O(log(n)) time for the enqueuing and dequeuing methods * ({@code offer}, {@code poll}, {@code remove()} and {@code add}); * linear time for the {@code remove(Object)} and {@code contains(Object)} * methods; and constant time for the retrieval methods @@ -79,7 +77,7 @@ import java.util.function.Block; * * @since 1.5 * @author Josh Bloch, Doug Lea - * @param the type of elements held in this collection + * @param the type of elements held in this queue */ public class PriorityQueue extends AbstractQueue implements java.io.Serializable { @@ -101,7 +99,7 @@ public class PriorityQueue extends Ab /** * The number of elements in the priority queue. */ - private int size = 0; + private int size; /** * The comparator, or null if priority queue uses elements' @@ -395,7 +393,7 @@ public class PriorityQueue extends Ab * @return {@code true} if this queue contains the specified element */ public boolean contains(Object o) { - return indexOf(o) != -1; + return indexOf(o) >= 0; } /** @@ -478,7 +476,7 @@ public class PriorityQueue extends Ab * Index (into queue array) of element to be returned by * subsequent call to next. */ - private int cursor = 0; + private int cursor; /** * Index of element returned by most recent call to next, @@ -498,13 +496,13 @@ public class PriorityQueue extends Ab * We expect that most iterations, even those involving removals, * will not need to store elements in this field. */ - private ArrayDeque forgetMeNot = null; + private ArrayDeque forgetMeNot; /** * Element returned by the most recent call to next iff that * element was drawn from the forgetMeNot list. */ - private E lastRetElt = null; + private E lastRetElt; /** * The modCount value that the iterator believes that the backing @@ -543,7 +541,7 @@ public class PriorityQueue extends Ab cursor--; else { if (forgetMeNot == null) - forgetMeNot = new ArrayDeque(); + forgetMeNot = new ArrayDeque<>(); forgetMeNot.add(moved); } } else if (lastRetElt != null) { @@ -745,6 +743,7 @@ public class PriorityQueue extends Ab * 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 { @@ -764,6 +763,9 @@ public class PriorityQueue extends Ab * (that is, deserializes it). * * @param s the stream + * @throws ClassNotFoundException if the class of a serialized object + * could not be found + * @throws java.io.IOException if an I/O error occurs */ private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { @@ -784,91 +786,96 @@ public class PriorityQueue extends Ab heapify(); } - // wrapping constructor in method avoids transient javac problems - final PriorityQueueSpliterator spliterator(int origin, int fence, - int expectedModCount) { - return new PriorityQueueSpliterator(this, origin, fence, - expectedModCount); - } - - public Stream stream() { - int flags = Streams.STREAM_IS_SIZED; - return Streams.stream - (() -> spliterator(0, size, modCount), flags); - } - public Stream parallelStream() { - int flags = Streams.STREAM_IS_SIZED; - return Streams.parallelStream - (() -> spliterator(0, size, modCount), flags); - } - - /** Index-based split-by-two Spliterator */ - static final class PriorityQueueSpliterator - implements Spliterator, Iterator { + public Spliterator spliterator() { + return new PriorityQueueSpliterator(this, 0, -1, 0); + } + + /** + * This is very similar to ArrayList Spliterator, except for extra + * null checks. + */ + static final class PriorityQueueSpliterator implements Spliterator { private final PriorityQueue pq; - private int index; // current index, modified on advance/split - private final int fence; // one past last index - private final int expectedModCount; // for comodification checks + private int index; // current index, modified on advance/split + private int fence; // -1 until first use + private int expectedModCount; // initialized when fence set - /** Create new spliterator covering the given range */ + /** Creates new spliterator covering the given range */ PriorityQueueSpliterator(PriorityQueue pq, int origin, int fence, int expectedModCount) { - this.pq = pq; this.index = origin; this.fence = fence; + this.pq = pq; + this.index = origin; + this.fence = fence; this.expectedModCount = expectedModCount; } - public PriorityQueueSpliterator trySplit() { - int lo = index, mid = (lo + fence) >>> 1; + private int getFence() { // initialize fence to size on first use + int hi; + if ((hi = fence) < 0) { + expectedModCount = pq.modCount; + hi = fence = pq.size; + } + return hi; + } + + public Spliterator trySplit() { + int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : new PriorityQueueSpliterator(pq, lo, index = mid, - expectedModCount); + expectedModCount); } - public void forEach(Block block) { - Object[] a; int i, hi; // hoist accesses and checks from loop - if (block == null) + @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 ((a = pq.queue).length >= (hi = fence) && - (i = index) >= 0 && i < hi) { - index = hi; - do { - @SuppressWarnings("unchecked") E e = (E) a[i]; - block.accept(e); - } while (++i < hi); - if (pq.modCount != expectedModCount) - throw new ConcurrentModificationException(); + 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; + } + } } + throw new ConcurrentModificationException(); } - public boolean tryAdvance(Block block) { - if (index >= 0 && index < fence) { + public boolean tryAdvance(Consumer action) { + int hi = getFence(), lo = index; + if (lo >= 0 && lo < hi) { + index = lo + 1; + @SuppressWarnings("unchecked") E e = (E)pq.queue[lo]; + if (e == null) + throw new ConcurrentModificationException(); + action.accept(e); if (pq.modCount != expectedModCount) throw new ConcurrentModificationException(); - @SuppressWarnings("unchecked") E e = - (E)pq.queue[index++]; - block.accept(e); return true; } return false; } - public long estimateSize() { return (long)(fence - index); } - public boolean hasExactSize() { return true; } - public boolean hasExactSplits() { return true; } - - // Iterator support - public Iterator iterator() { return this; } - public void remove() { throw new UnsupportedOperationException(); } - public boolean hasNext() { return index >= 0 && index < fence; } + public long estimateSize() { + return (long) (getFence() - index); + } - public E next() { - if (index < 0 || index >= fence) - throw new NoSuchElementException(); - if (pq.modCount != expectedModCount) - throw new ConcurrentModificationException(); - @SuppressWarnings("unchecked") E e = - (E) pq.queue[index++]; - return e; + public int characteristics() { + return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL; } } }