--- jsr166/src/main/java/util/PriorityQueue.java 2013/01/19 18:18:10 1.85 +++ jsr166/src/main/java/util/PriorityQueue.java 2015/06/16 23:06:01 1.106 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -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' @@ -113,7 +111,7 @@ public class PriorityQueue extends Ab * The number of times this priority queue has been * structurally modified. See AbstractList for gory details. */ - transient int modCount = 0; // non-private to simplify nested class access + transient int modCount; // non-private to simplify nested class access /** * Creates a {@code PriorityQueue} with the default initial @@ -138,6 +136,19 @@ public class PriorityQueue extends Ab } /** + * Creates a {@code PriorityQueue} with the default initial capacity and + * whose elements are ordered according to the specified comparator. + * + * @param comparator the comparator that will be used to order this + * priority queue. If {@code null}, the {@linkplain Comparable + * natural ordering} of the elements will be used. + * @since 1.8 + */ + public PriorityQueue(Comparator comparator) { + this(DEFAULT_INITIAL_CAPACITY, comparator); + } + + /** * Creates a {@code PriorityQueue} with the specified initial capacity * that orders its elements according to the specified comparator. * @@ -247,8 +258,8 @@ public class PriorityQueue extends Ab a = Arrays.copyOf(a, a.length, Object[].class); int len = a.length; if (len == 1 || this.comparator != null) - for (int i = 0; i < len; i++) - if (a[i] == null) + for (Object e : a) + if (e == null) throw new NullPointerException(); this.queue = a; this.size = a.length; @@ -395,7 +406,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; } /** @@ -437,7 +448,7 @@ public class PriorityQueue extends Ab * The following code can be used to dump the queue into a newly * allocated array of {@code String}: * - * 

 {@code String[] y = x.toArray(new String[0]);}
+ * 
 {@code String[] y = x.toArray(new String[0]);}
* * Note that {@code toArray(new Object[0])} is identical in function to * {@code toArray()}. @@ -478,7 +489,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 +509,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 +554,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 +756,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 +776,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 +799,111 @@ 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 { + /** + * Creates a late-binding + * and fail-fast {@link Spliterator} over the elements in this + * queue. + * + *

The {@code Spliterator} reports {@link Spliterator#SIZED}, + * {@link Spliterator#SUBSIZED}, and {@link Spliterator#NONNULL}. + * Overriding implementations should document the reporting of additional + * characteristic values. + * + * @return a {@code Spliterator} over the elements in this queue + * @since 1.8 + */ + public final Spliterator spliterator() { + return new PriorityQueueSpliterator<>(this, 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; - 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; } + 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 PriorityQueueSpliterator trySplit() { - int lo = index, mid = (lo + fence) >>> 1; + int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; return (lo >= mid) ? null : - new PriorityQueueSpliterator(pq, lo, index = mid, - expectedModCount); + new PriorityQueueSpliterator<>(pq, lo, index = mid, + 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) { + 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) + 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; } } }