--- jsr166/src/main/java/util/PriorityQueue.java 2013/02/18 03:10:15 1.91 +++ jsr166/src/main/java/util/PriorityQueue.java 2015/10/11 00:50:06 1.108 @@ -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,9 +24,8 @@ */ package java.util; + import java.util.function.Consumer; -import java.util.stream.Stream; -import java.util.stream.Streams; /** * An unbounded priority {@linkplain Queue queue} based on a priority heap. @@ -66,7 +65,7 @@ import java.util.stream.Streams; * 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 @@ -78,7 +77,7 @@ import java.util.stream.Streams; * * @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 { @@ -100,7 +99,7 @@ public class PriorityQueue extends Ab /** * The number of elements in the priority queue. */ - private int size = 0; + int size; /** * The comparator, or null if priority queue uses elements' @@ -112,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 @@ -137,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. * @@ -246,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; @@ -394,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; } /** @@ -436,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()}. @@ -477,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, @@ -497,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 @@ -597,7 +609,7 @@ public class PriorityQueue extends Ab * avoid missing traversing elements. */ @SuppressWarnings("unchecked") - private E removeAt(int i) { + E removeAt(int i) { // assert i >= 0 && i < size; modCount++; int s = --size; @@ -744,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 { @@ -763,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 { @@ -783,16 +799,21 @@ public class PriorityQueue extends Ab heapify(); } - final Spliterator spliterator() { - return new PriorityQueueSpliterator(this, 0, -1, 0); - } - - public Stream stream() { - return Streams.stream(spliterator()); - } - - public Stream parallelStream() { - return Streams.parallelStream(spliterator()); + /** + * 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 { @@ -805,9 +826,9 @@ public class PriorityQueue extends Ab private int fence; // -1 until first use private int expectedModCount; // initialized when fence set - /** Creates new spliterator covering the given range */ + /** Creates new spliterator covering the given range. */ PriorityQueueSpliterator(PriorityQueue pq, int origin, int fence, - int expectedModCount) { + int expectedModCount) { this.pq = pq; this.index = origin; this.fence = fence; @@ -826,12 +847,12 @@ public class PriorityQueue extends Ab public PriorityQueueSpliterator trySplit() { 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); } @SuppressWarnings("unchecked") - public void forEach(Consumer action) { + public void forEachRemaining(Consumer action) { int i, hi, mc; // hoist accesses and checks from loop PriorityQueue q; Object[] a; if (action == null) @@ -861,6 +882,8 @@ public class PriorityQueue extends Ab } public boolean tryAdvance(Consumer action) { + if (action == null) + throw new NullPointerException(); int hi = getFence(), lo = index; if (lo >= 0 && lo < hi) { index = lo + 1;