--- jsr166/src/main/java/util/PriorityQueue.java 2006/03/19 01:00:40 1.64 +++ jsr166/src/main/java/util/PriorityQueue.java 2016/11/30 18:12:52 1.114 @@ -1,12 +1,32 @@ /* - * %W% %E% + * Copyright (c) 2003, 2013, 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.function.Consumer; + /** * An unbounded priority {@linkplain Queue queue} based on a priority heap. * The elements of the priority queue are ordered according to their @@ -34,31 +54,31 @@ package java.util; *

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())}. * - *

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 * 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 * ({@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 + * @param the type of elements held in this queue */ public class PriorityQueue extends AbstractQueue implements java.io.Serializable { @@ -75,12 +95,12 @@ 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. */ - private int size = 0; + int size; /** * The comparator, or null if priority queue uses elements' @@ -92,7 +112,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; // non-private to simplify nested class access /** * Creates a {@code PriorityQueue} with the default initial @@ -117,6 +137,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. * @@ -153,17 +186,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 +218,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 +237,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 (Object e : a) + if (e == null) + throw new NullPointerException(); + this.queue = a; + this.size = a.length; } /** @@ -210,34 +272,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. * @@ -267,22 +338,18 @@ 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; } + @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 +369,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 +386,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 +404,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; } /** @@ -375,15 +442,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 +460,13 @@ public class PriorityQueue extends Ab * this queue * @throws NullPointerException if the specified array is null */ + @SuppressWarnings("unchecked") public T[] toArray(T[] a) { + final int size = this.size; 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; @@ -419,7 +487,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, @@ -439,13 +507,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 @@ -459,6 +527,7 @@ public class PriorityQueue extends Ab (forgetMeNot != null && !forgetMeNot.isEmpty()); } + @SuppressWarnings("unchecked") public E next() { if (expectedModCount != modCount) throw new ConcurrentModificationException(); @@ -483,7 +552,7 @@ public class PriorityQueue extends Ab cursor--; else { if (forgetMeNot == null) - forgetMeNot = new ArrayDeque(); + forgetMeNot = new ArrayDeque<>(); forgetMeNot.add(moved); } } else if (lastRetElt != null) { @@ -491,7 +560,7 @@ public class PriorityQueue extends Ab lastRetElt = null; } else { throw new IllegalStateException(); - } + } expectedModCount = modCount; } } @@ -511,6 +580,7 @@ public class PriorityQueue extends Ab size = 0; } + @SuppressWarnings("unchecked") public E poll() { if (size == 0) return null; @@ -536,8 +606,9 @@ public class PriorityQueue extends Ab * position before i. This fact is used by iterator.remove so as to * avoid missing traversing elements. */ - private E removeAt(int i) { - assert i >= 0 && i < size; + @SuppressWarnings("unchecked") + E removeAt(int i) { + // assert i >= 0 && i < size; modCount++; int s = --size; if (s == i) // removed last element @@ -574,6 +645,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 +659,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 +687,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 +706,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) { @@ -652,10 +727,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; + final int half = (size >>> 1) - 1; + if (comparator == null) + for (int i = half; i >= 0; i--) + siftDownComparable(i, (E) es[i]); + else + for (int i = half; i >= 0; i--) + siftDownUsingComparator(i, (E) es[i]); } /** @@ -672,16 +755,16 @@ 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). * + * @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 */ 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(); @@ -698,6 +781,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 { @@ -707,14 +793,119 @@ 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. 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(); + // Elements are guaranteed to be in "proper order", but the + // spec has never explained what that might be. + heapify(); + } + + /** + * Creates a late-binding + * and fail-fast {@link Spliterator} over the elements in this + * 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}. + * 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(0, -1, 0); + } + + final class PriorityQueueSpliterator implements Spliterator { + /* + * This is very similar to ArrayList Spliterator, except for + * extra null checks. + */ + 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(int origin, int fence, int expectedModCount) { + 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 = modCount; + hi = fence = size; + } + return hi; + } + + public PriorityQueueSpliterator trySplit() { + int hi = getFence(), lo = index, mid = (lo + hi) >>> 1; + return (lo >= mid) ? null : + new PriorityQueueSpliterator(lo, index = mid, expectedModCount); + } + + @SuppressWarnings("unchecked") + public void forEachRemaining(Consumer action) { + int i, hi, mc; // hoist accesses and checks from loop + final Object[] a; + if (action == null) + throw new NullPointerException(); + if ((a = queue) != null) { + if ((hi = fence) < 0) { + mc = modCount; + hi = 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 (modCount != mc) + break; + else + return; + } + } + } + throw new ConcurrentModificationException(); + } + + 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)queue[lo]; + if (e == null) + throw new ConcurrentModificationException(); + action.accept(e); + if (modCount != expectedModCount) + throw new ConcurrentModificationException(); + return true; + } + return false; + } + + public long estimateSize() { + return getFence() - index; + } + + public int characteristics() { + return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL; + } } }