--- jsr166/src/main/java/util/PriorityQueue.java 2013/01/16 01:59:47 1.80 +++ jsr166/src/main/java/util/PriorityQueue.java 2015/10/11 00:50:06 1.108 @@ -1,12 +1,12 @@ /* - * Copyright (c) 2003, 2006, 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 * under the terms of the GNU General Public License version 2 only, as - * published by the Free Software Foundation. Sun designates this + * published by the Free Software Foundation. Oracle designates this * particular file as subject to the "Classpath" exception as provided - * by Sun in the LICENSE file that accompanied this code. + * 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 @@ -25,6 +25,8 @@ 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 @@ -75,9 +77,8 @@ package java.util; * * @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 */ -@SuppressWarnings("unchecked") public class PriorityQueue extends AbstractQueue implements java.io.Serializable { @@ -93,12 +94,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' @@ -110,7 +111,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 @@ -135,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. * @@ -244,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; @@ -331,6 +345,7 @@ public class PriorityQueue extends Ab return true; } + @SuppressWarnings("unchecked") public E peek() { return (size == 0) ? null : (E) queue[0]; } @@ -391,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; } /** @@ -433,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()}. @@ -447,7 +462,9 @@ 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()); @@ -472,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, @@ -492,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 @@ -512,6 +529,7 @@ public class PriorityQueue extends Ab (forgetMeNot != null && !forgetMeNot.isEmpty()); } + @SuppressWarnings("unchecked") public E next() { if (expectedModCount != modCount) throw new ConcurrentModificationException(); @@ -536,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) { @@ -564,6 +582,7 @@ public class PriorityQueue extends Ab size = 0; } + @SuppressWarnings("unchecked") public E poll() { if (size == 0) return null; @@ -589,7 +608,8 @@ 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) { + @SuppressWarnings("unchecked") + E removeAt(int i) { // assert i >= 0 && i < size; modCount++; int s = --size; @@ -627,6 +647,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) { @@ -640,6 +661,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; @@ -667,6 +689,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 @@ -685,6 +708,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) { @@ -706,6 +730,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]); @@ -730,6 +755,8 @@ public class PriorityQueue extends Ab * @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 { @@ -745,7 +772,13 @@ public class PriorityQueue extends Ab } /** - * Reconstitutes this queue from a stream (that is, deserializes it). + * Reconstitutes the {@code PriorityQueue} instance from a stream + * (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 { @@ -765,4 +798,112 @@ public class PriorityQueue extends Ab // 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 {@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 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; + 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 hi = getFence(), lo = index, mid = (lo + hi) >>> 1; + return (lo >= mid) ? null : + new PriorityQueueSpliterator<>(pq, 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; + } + } + } + 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)pq.queue[lo]; + if (e == null) + throw new ConcurrentModificationException(); + action.accept(e); + if (pq.modCount != expectedModCount) + throw new ConcurrentModificationException(); + return true; + } + return false; + } + + public long estimateSize() { + return (long) (getFence() - index); + } + + public int characteristics() { + return Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.NONNULL; + } + } }