--- jsr166/src/main/java/util/PriorityQueue.java 2006/03/07 07:11:39 1.63 +++ jsr166/src/main/java/util/PriorityQueue.java 2013/01/19 18:11:56 1.84 @@ -1,11 +1,33 @@ /* - * %W% %E% + * Copyright (c) 2003, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * - * Copyright 2006 Sun Microsystems, Inc. All rights reserved. - * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. */ package java.util; +import java.util.stream.Stream; +import java.util.Spliterator; +import java.util.stream.Streams; +import java.util.function.Block; /** * An unbounded priority {@linkplain Queue queue} based on a priority heap. @@ -38,7 +60,7 @@ package java.util; * the priority queue in any particular order. If you need ordered * traversal, consider using {@code Arrays.sort(pq.toArray())}. * - *

Note that this implementation is not synchronized. + *

Note that this implementation is not synchronized. * Multiple threads should not access a {@code PriorityQueue} * instance concurrently if any of the threads modifies the queue. * Instead, use the thread-safe {@link @@ -52,11 +74,10 @@ package java.util; * ({@code peek}, {@code element}, and {@code size}). * *

This class is a member of the - * + * * Java Collections Framework. * * @since 1.5 - * @version %I%, %G% * @author Josh Bloch, Doug Lea * @param the type of elements held in this collection */ @@ -75,7 +96,7 @@ public class PriorityQueue extends Ab * heap and each descendant d of n, n <= d. The element with the * lowest value is in queue[0], assuming the queue is nonempty. */ - private transient Object[] queue; + transient Object[] queue; // non-private to simplify nested class access /** * The number of elements in the priority queue. @@ -92,7 +113,7 @@ public class PriorityQueue extends Ab * The number of times this priority queue has been * structurally modified. See AbstractList for gory details. */ - private transient int modCount = 0; + transient int modCount = 0; // non-private to simplify nested class access /** * Creates a {@code PriorityQueue} with the default initial @@ -153,17 +174,21 @@ public class PriorityQueue extends Ab * @throws NullPointerException if the specified collection or any * of its elements are null */ + @SuppressWarnings("unchecked") public PriorityQueue(Collection c) { - initFromCollection(c); - if (c instanceof SortedSet) - comparator = (Comparator) - ((SortedSet)c).comparator(); - else if (c instanceof PriorityQueue) - comparator = (Comparator) - ((PriorityQueue)c).comparator(); + if (c instanceof SortedSet) { + SortedSet ss = (SortedSet) c; + this.comparator = (Comparator) ss.comparator(); + initElementsFromCollection(ss); + } + else if (c instanceof PriorityQueue) { + PriorityQueue pq = (PriorityQueue) c; + this.comparator = (Comparator) pq.comparator(); + initFromPriorityQueue(pq); + } else { - comparator = null; - heapify(); + this.comparator = null; + initFromCollection(c); } } @@ -181,9 +206,10 @@ public class PriorityQueue extends Ab * @throws NullPointerException if the specified priority queue or any * of its elements are null */ + @SuppressWarnings("unchecked") public PriorityQueue(PriorityQueue c) { - comparator = (Comparator)c.comparator(); - initFromCollection(c); + this.comparator = (Comparator) c.comparator(); + initFromPriorityQueue(c); } /** @@ -199,9 +225,33 @@ public class PriorityQueue extends Ab * @throws NullPointerException if the specified sorted set or any * of its elements are null */ + @SuppressWarnings("unchecked") public PriorityQueue(SortedSet c) { - comparator = (Comparator)c.comparator(); - initFromCollection(c); + this.comparator = (Comparator) c.comparator(); + initElementsFromCollection(c); + } + + private void initFromPriorityQueue(PriorityQueue c) { + if (c.getClass() == PriorityQueue.class) { + this.queue = c.toArray(); + this.size = c.size(); + } else { + initFromCollection(c); + } + } + + private void initElementsFromCollection(Collection c) { + Object[] a = c.toArray(); + // If c.toArray incorrectly doesn't return Object[], copy it. + if (a.getClass() != Object[].class) + 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) + throw new NullPointerException(); + this.queue = a; + this.size = a.length; } /** @@ -210,34 +260,43 @@ public class PriorityQueue extends Ab * @param c the collection */ private void initFromCollection(Collection c) { - Object[] a = c.toArray(); - // If c.toArray incorrectly doesn't return Object[], copy it. - if (a.getClass() != Object[].class) - a = Arrays.copyOf(a, a.length, Object[].class); - queue = a; - size = a.length; + initElementsFromCollection(c); + heapify(); } /** + * The maximum size of array to allocate. + * Some VMs reserve some header words in an array. + * Attempts to allocate larger arrays may result in + * OutOfMemoryError: Requested array size exceeds VM limit + */ + private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; + + /** * Increases the capacity of the array. * * @param minCapacity the desired minimum capacity */ private void grow(int minCapacity) { - if (minCapacity < 0) // overflow - throw new OutOfMemoryError(); - int oldCapacity = queue.length; + int oldCapacity = queue.length; // Double size if small; else grow by 50% - int newCapacity = ((oldCapacity < 64)? - ((oldCapacity + 1) * 2): - ((oldCapacity / 2) * 3)); - if (newCapacity < 0) // overflow - newCapacity = Integer.MAX_VALUE; - if (newCapacity < minCapacity) - newCapacity = minCapacity; + int newCapacity = oldCapacity + ((oldCapacity < 64) ? + (oldCapacity + 2) : + (oldCapacity >> 1)); + // overflow-conscious code + if (newCapacity - MAX_ARRAY_SIZE > 0) + newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); } + private static int hugeCapacity(int minCapacity) { + if (minCapacity < 0) // overflow + throw new OutOfMemoryError(); + return (minCapacity > MAX_ARRAY_SIZE) ? + Integer.MAX_VALUE : + MAX_ARRAY_SIZE; + } + /** * Inserts the specified element into this priority queue. * @@ -275,14 +334,13 @@ public class PriorityQueue extends Ab return true; } + @SuppressWarnings("unchecked") public E peek() { - if (size == 0) - return null; - return (E) queue[0]; + return (size == 0) ? null : (E) queue[0]; } private int indexOf(Object o) { - if (o != null) { + if (o != null) { for (int i = 0; i < size; i++) if (o.equals(queue[i])) return i; @@ -302,13 +360,13 @@ public class PriorityQueue extends Ab * @return {@code true} if this queue changed as a result of the call */ public boolean remove(Object o) { - int i = indexOf(o); - if (i == -1) - return false; - else { - removeAt(i); - return true; - } + int i = indexOf(o); + if (i == -1) + return false; + else { + removeAt(i); + return true; + } } /** @@ -319,8 +377,8 @@ public class PriorityQueue extends Ab * @return {@code true} if removed */ boolean removeEq(Object o) { - for (int i = 0; i < size; i++) { - if (o == queue[i]) { + for (int i = 0; i < size; i++) { + if (o == queue[i]) { removeAt(i); return true; } @@ -337,7 +395,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) != -1; } /** @@ -375,15 +433,14 @@ public class PriorityQueue extends Ab * precise control over the runtime type of the output array, and may, * under certain circumstances, be used to save allocation costs. * - *

Suppose x is a queue known to contain only strings. + *

Suppose {@code x} is a queue known to contain only strings. * The following code can be used to dump the queue into a newly - * allocated array of String: + * allocated array of {@code String}: * - * 

-     *     String[] y = x.toArray(new String[0]);
+ * 
 {@code String[] y = x.toArray(new String[0]);}
* - * Note that toArray(new Object[0]) is identical in function to - * toArray(). + * Note that {@code toArray(new Object[0])} is identical in function to + * {@code toArray()}. * * @param a the array into which the elements of the queue are to * be stored, if it is big enough; otherwise, a new array of the @@ -394,11 +451,12 @@ public class PriorityQueue extends Ab * this queue * @throws NullPointerException if the specified array is null */ + @SuppressWarnings("unchecked") public T[] toArray(T[] a) { if (a.length < size) // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(queue, size, a.getClass()); - System.arraycopy(queue, 0, a, 0, size); + System.arraycopy(queue, 0, a, 0, size); if (a.length > size) a[size] = null; return a; @@ -459,6 +517,7 @@ public class PriorityQueue extends Ab (forgetMeNot != null && !forgetMeNot.isEmpty()); } + @SuppressWarnings("unchecked") public E next() { if (expectedModCount != modCount) throw new ConcurrentModificationException(); @@ -491,7 +550,7 @@ public class PriorityQueue extends Ab lastRetElt = null; } else { throw new IllegalStateException(); - } + } expectedModCount = modCount; } } @@ -511,6 +570,7 @@ public class PriorityQueue extends Ab size = 0; } + @SuppressWarnings("unchecked") public E poll() { if (size == 0) return null; @@ -536,8 +596,9 @@ public class PriorityQueue extends Ab * position before i. This fact is used by iterator.remove so as to * avoid missing traversing elements. */ + @SuppressWarnings("unchecked") private E removeAt(int i) { - assert i >= 0 && i < size; + // assert i >= 0 && i < size; modCount++; int s = --size; if (s == i) // removed last element @@ -574,6 +635,7 @@ public class PriorityQueue extends Ab siftUpComparable(k, x); } + @SuppressWarnings("unchecked") private void siftUpComparable(int k, E x) { Comparable key = (Comparable) x; while (k > 0) { @@ -587,6 +649,7 @@ public class PriorityQueue extends Ab queue[k] = key; } + @SuppressWarnings("unchecked") private void siftUpUsingComparator(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1; @@ -614,6 +677,7 @@ public class PriorityQueue extends Ab siftDownComparable(k, x); } + @SuppressWarnings("unchecked") private void siftDownComparable(int k, E x) { Comparable key = (Comparable)x; int half = size >>> 1; // loop while a non-leaf @@ -632,6 +696,7 @@ public class PriorityQueue extends Ab queue[k] = key; } + @SuppressWarnings("unchecked") private void siftDownUsingComparator(int k, E x) { int half = size >>> 1; while (k < half) { @@ -653,6 +718,7 @@ 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. */ + @SuppressWarnings("unchecked") private void heapify() { for (int i = (size >>> 1) - 1; i >= 0; i--) siftDown(i, (E) queue[i]); @@ -672,8 +738,7 @@ public class PriorityQueue extends Ab } /** - * Saves the state of the instance to a stream (that - * is, serializes it). + * Saves this queue to a stream (that is, serializes it). * * @serialData The length of the array backing the instance is * emitted (int), followed by all of its elements @@ -681,14 +746,14 @@ public class PriorityQueue extends Ab * @param s the stream */ private void writeObject(java.io.ObjectOutputStream s) - throws java.io.IOException{ + throws java.io.IOException { // Write out element count, and any hidden stuff s.defaultWriteObject(); // Write out array length, for compatibility with 1.5 version s.writeInt(Math.max(2, size + 1)); - // Write out all elements in the proper order. + // Write out all elements in the "proper order". for (int i = 0; i < size; i++) s.writeObject(queue[i]); } @@ -707,10 +772,102 @@ public class PriorityQueue extends Ab // Read in (and discard) array length s.readInt(); - queue = new Object[size]; + queue = new Object[size]; - // Read in all elements in the proper order. + // Read in all elements. for (int i = 0; i < size; i++) queue[i] = s.readObject(); + + // Elements are guaranteed to be in "proper order", but the + // spec has never explained what that might be. + 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 { + 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 + + /** Create 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.expectedModCount = expectedModCount; + } + + public PriorityQueueSpliterator trySplit() { + int lo = index, mid = (lo + fence) >>> 1; + return (lo >= mid) ? null : + 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) + 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(); + } + } + + public boolean tryAdvance(Block block) { + if (index >= 0 && index < fence) { + 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 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; + } } }