8011426: java.util collection Spliterator implementations
Summary: Spliterator implementations for collection classes in java.util.
Reviewed-by: mduigou, briangoetz
Contributed-by: Doug Lea <dl@cs.oswego.edu>, Paul Sandoz <paul.sandoz@oracle.com>
--- a/jdk/src/share/classes/java/util/ArrayDeque.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/ArrayDeque.java Wed Apr 17 11:34:31 2013 +0200
@@ -33,7 +33,9 @@
*/
package java.util;
-import java.io.*;
+
+import java.io.Serializable;
+import java.util.function.Consumer;
/**
* Resizable-array implementation of the {@link Deque} interface. Array
@@ -44,16 +46,16 @@
* {@link Stack} when used as a stack, and faster than {@link LinkedList}
* when used as a queue.
*
- * <p>Most <tt>ArrayDeque</tt> operations run in amortized constant time.
+ * <p>Most {@code ArrayDeque} operations run in amortized constant time.
* Exceptions include {@link #remove(Object) remove}, {@link
* #removeFirstOccurrence removeFirstOccurrence}, {@link #removeLastOccurrence
* removeLastOccurrence}, {@link #contains contains}, {@link #iterator
* iterator.remove()}, and the bulk operations, all of which run in linear
* time.
*
- * <p>The iterators returned by this class's <tt>iterator</tt> method are
+ * <p>The iterators returned by this class's {@code iterator} method are
* <i>fail-fast</i>: If the deque is modified at any time after the iterator
- * is created, in any way except through the iterator's own <tt>remove</tt>
+ * is created, in any way except through the iterator's own {@code remove}
* method, the iterator will generally throw a {@link
* ConcurrentModificationException}. Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than risking
@@ -63,7 +65,7 @@
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
- * throw <tt>ConcurrentModificationException</tt> on a best-effort basis.
+ * throw {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
@@ -93,20 +95,20 @@
* other. We also guarantee that all array cells not holding
* deque elements are always null.
*/
- private transient E[] elements;
+ transient Object[] elements; // non-private to simplify nested class access
/**
* The index of the element at the head of the deque (which is the
* element that would be removed by remove() or pop()); or an
* arbitrary number equal to tail if the deque is empty.
*/
- private transient int head;
+ transient int head;
/**
* The index at which the next element would be added to the tail
* of the deque (via addLast(E), add(E), or push(E)).
*/
- private transient int tail;
+ transient int tail;
/**
* The minimum capacity that we'll use for a newly created deque.
@@ -117,11 +119,10 @@
// ****** Array allocation and resizing utilities ******
/**
- * Allocate empty array to hold the given number of elements.
+ * Allocates empty array to hold the given number of elements.
*
* @param numElements the number of elements to hold
*/
- @SuppressWarnings("unchecked")
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
@@ -138,11 +139,11 @@
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
- elements = (E[]) new Object[initialCapacity];
+ elements = new Object[initialCapacity];
}
/**
- * Double the capacity of this deque. Call only when full, i.e.,
+ * Doubles the capacity of this deque. Call only when full, i.e.,
* when head and tail have wrapped around to become equal.
*/
private void doubleCapacity() {
@@ -153,8 +154,7 @@
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
- @SuppressWarnings("unchecked")
- E[] a = (E[]) new Object[newCapacity];
+ Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
@@ -184,9 +184,8 @@
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
- @SuppressWarnings("unchecked")
public ArrayDeque() {
- elements = (E[]) new Object[16];
+ elements = new Object[16];
}
/**
@@ -252,7 +251,7 @@
* Inserts the specified element at the front of this deque.
*
* @param e the element to add
- * @return <tt>true</tt> (as specified by {@link Deque#offerFirst})
+ * @return {@code true} (as specified by {@link Deque#offerFirst})
* @throws NullPointerException if the specified element is null
*/
public boolean offerFirst(E e) {
@@ -264,7 +263,7 @@
* Inserts the specified element at the end of this deque.
*
* @param e the element to add
- * @return <tt>true</tt> (as specified by {@link Deque#offerLast})
+ * @return {@code true} (as specified by {@link Deque#offerLast})
* @throws NullPointerException if the specified element is null
*/
public boolean offerLast(E e) {
@@ -294,7 +293,9 @@
public E pollFirst() {
int h = head;
- E result = elements[h]; // Element is null if deque empty
+ @SuppressWarnings("unchecked")
+ E result = (E) elements[h];
+ // Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
@@ -304,7 +305,8 @@
public E pollLast() {
int t = (tail - 1) & (elements.length - 1);
- E result = elements[t];
+ @SuppressWarnings("unchecked")
+ E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
@@ -316,48 +318,53 @@
* @throws NoSuchElementException {@inheritDoc}
*/
public E getFirst() {
- E x = elements[head];
- if (x == null)
+ @SuppressWarnings("unchecked")
+ E result = (E) elements[head];
+ if (result == null)
throw new NoSuchElementException();
- return x;
+ return result;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getLast() {
- E x = elements[(tail - 1) & (elements.length - 1)];
- if (x == null)
+ @SuppressWarnings("unchecked")
+ E result = (E) elements[(tail - 1) & (elements.length - 1)];
+ if (result == null)
throw new NoSuchElementException();
- return x;
+ return result;
}
+ @SuppressWarnings("unchecked")
public E peekFirst() {
- return elements[head]; // elements[head] is null if deque empty
+ // elements[head] is null if deque empty
+ return (E) elements[head];
}
+ @SuppressWarnings("unchecked")
public E peekLast() {
- return elements[(tail - 1) & (elements.length - 1)];
+ return (E) elements[(tail - 1) & (elements.length - 1)];
}
/**
* Removes the first occurrence of the specified element in this
* deque (when traversing the deque from head to tail).
* If the deque does not contain the element, it is unchanged.
- * More formally, removes the first element <tt>e</tt> such that
- * <tt>o.equals(e)</tt> (if such an element exists).
- * Returns <tt>true</tt> if this deque contained the specified element
+ * More formally, removes the first element {@code e} such that
+ * {@code o.equals(e)} (if such an element exists).
+ * Returns {@code true} if this deque contained the specified element
* (or equivalently, if this deque changed as a result of the call).
*
* @param o element to be removed from this deque, if present
- * @return <tt>true</tt> if the deque contained the specified element
+ * @return {@code true} if the deque contained the specified element
*/
public boolean removeFirstOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
- E x;
+ Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
@@ -372,20 +379,20 @@
* Removes the last occurrence of the specified element in this
* deque (when traversing the deque from head to tail).
* If the deque does not contain the element, it is unchanged.
- * More formally, removes the last element <tt>e</tt> such that
- * <tt>o.equals(e)</tt> (if such an element exists).
- * Returns <tt>true</tt> if this deque contained the specified element
+ * More formally, removes the last element {@code e} such that
+ * {@code o.equals(e)} (if such an element exists).
+ * Returns {@code true} if this deque contained the specified element
* (or equivalently, if this deque changed as a result of the call).
*
* @param o element to be removed from this deque, if present
- * @return <tt>true</tt> if the deque contained the specified element
+ * @return {@code true} if the deque contained the specified element
*/
public boolean removeLastOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = (tail - 1) & mask;
- E x;
+ Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
@@ -404,7 +411,7 @@
* <p>This method is equivalent to {@link #addLast}.
*
* @param e the element to add
- * @return <tt>true</tt> (as specified by {@link Collection#add})
+ * @return {@code true} (as specified by {@link Collection#add})
* @throws NullPointerException if the specified element is null
*/
public boolean add(E e) {
@@ -418,7 +425,7 @@
* <p>This method is equivalent to {@link #offerLast}.
*
* @param e the element to add
- * @return <tt>true</tt> (as specified by {@link Queue#offer})
+ * @return {@code true} (as specified by {@link Queue#offer})
* @throws NullPointerException if the specified element is null
*/
public boolean offer(E e) {
@@ -443,12 +450,12 @@
/**
* Retrieves and removes the head of the queue represented by this deque
* (in other words, the first element of this deque), or returns
- * <tt>null</tt> if this deque is empty.
+ * {@code null} if this deque is empty.
*
* <p>This method is equivalent to {@link #pollFirst}.
*
* @return the head of the queue represented by this deque, or
- * <tt>null</tt> if this deque is empty
+ * {@code null} if this deque is empty
*/
public E poll() {
return pollFirst();
@@ -470,12 +477,12 @@
/**
* Retrieves, but does not remove, the head of the queue represented by
- * this deque, or returns <tt>null</tt> if this deque is empty.
+ * this deque, or returns {@code null} if this deque is empty.
*
* <p>This method is equivalent to {@link #peekFirst}.
*
* @return the head of the queue represented by this deque, or
- * <tt>null</tt> if this deque is empty
+ * {@code null} if this deque is empty
*/
public E peek() {
return peekFirst();
@@ -530,7 +537,7 @@
*/
private boolean delete(int i) {
checkInvariants();
- final E[] elements = this.elements;
+ final Object[] elements = this.elements;
final int mask = elements.length - 1;
final int h = head;
final int t = tail;
@@ -579,9 +586,9 @@
}
/**
- * Returns <tt>true</tt> if this deque contains no elements.
+ * Returns {@code true} if this deque contains no elements.
*
- * @return <tt>true</tt> if this deque contains no elements
+ * @return {@code true} if this deque contains no elements
*/
public boolean isEmpty() {
return head == tail;
@@ -628,7 +635,8 @@
public E next() {
if (cursor == fence)
throw new NoSuchElementException();
- E result = elements[cursor];
+ @SuppressWarnings("unchecked")
+ E result = (E) elements[cursor];
// This check doesn't catch all possible comodifications,
// but does catch the ones that corrupt traversal
if (tail != fence || result == null)
@@ -647,6 +655,20 @@
}
lastRet = -1;
}
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ Object[] a = elements;
+ int m = a.length - 1, f = fence, i = cursor;
+ cursor = f;
+ while (i != f) {
+ @SuppressWarnings("unchecked") E e = (E)a[i];
+ i = (i + 1) & m;
+ if (e == null)
+ throw new ConcurrentModificationException();
+ action.accept(e);
+ }
+ }
}
private class DescendingIterator implements Iterator<E> {
@@ -667,7 +689,8 @@
if (cursor == fence)
throw new NoSuchElementException();
cursor = (cursor - 1) & (elements.length - 1);
- E result = elements[cursor];
+ @SuppressWarnings("unchecked")
+ E result = (E) elements[cursor];
if (head != fence || result == null)
throw new ConcurrentModificationException();
lastRet = cursor;
@@ -686,19 +709,19 @@
}
/**
- * Returns <tt>true</tt> if this deque contains the specified element.
- * More formally, returns <tt>true</tt> if and only if this deque contains
- * at least one element <tt>e</tt> such that <tt>o.equals(e)</tt>.
+ * Returns {@code true} if this deque contains the specified element.
+ * More formally, returns {@code true} if and only if this deque contains
+ * at least one element {@code e} such that {@code o.equals(e)}.
*
* @param o object to be checked for containment in this deque
- * @return <tt>true</tt> if this deque contains the specified element
+ * @return {@code true} if this deque contains the specified element
*/
public boolean contains(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
- E x;
+ Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x))
return true;
@@ -710,15 +733,15 @@
/**
* Removes a single instance of the specified element from this deque.
* If the deque does not contain the element, it is unchanged.
- * More formally, removes the first element <tt>e</tt> such that
- * <tt>o.equals(e)</tt> (if such an element exists).
- * Returns <tt>true</tt> if this deque contained the specified element
+ * More formally, removes the first element {@code e} such that
+ * {@code o.equals(e)} (if such an element exists).
+ * Returns {@code true} if this deque contained the specified element
* (or equivalently, if this deque changed as a result of the call).
*
- * <p>This method is equivalent to {@link #removeFirstOccurrence}.
+ * <p>This method is equivalent to {@link #removeFirstOccurrence(Object)}.
*
* @param o element to be removed from this deque, if present
- * @return <tt>true</tt> if this deque contained the specified element
+ * @return {@code true} if this deque contained the specified element
*/
public boolean remove(Object o) {
return removeFirstOccurrence(o);
@@ -770,22 +793,21 @@
* <p>If this deque fits in the specified array with room to spare
* (i.e., the array has more elements than this deque), the element in
* the array immediately following the end of the deque is set to
- * <tt>null</tt>.
+ * {@code null}.
*
* <p>Like the {@link #toArray()} method, this method acts as bridge between
* array-based and collection-based APIs. Further, this method allows
* precise control over the runtime type of the output array, and may,
* under certain circumstances, be used to save allocation costs.
*
- * <p>Suppose <tt>x</tt> is a deque known to contain only strings.
+ * <p>Suppose {@code x} is a deque known to contain only strings.
* The following code can be used to dump the deque into a newly
- * allocated array of <tt>String</tt>:
+ * allocated array of {@code String}:
*
- * <pre>
- * String[] y = x.toArray(new String[0]);</pre>
+ * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
*
- * Note that <tt>toArray(new Object[0])</tt> is identical in function to
- * <tt>toArray()</tt>.
+ * Note that {@code toArray(new Object[0])} is identical in function to
+ * {@code toArray()}.
*
* @param a the array into which the elements of the deque are to
* be stored, if it is big enough; otherwise, a new array of the
@@ -818,28 +840,25 @@
public ArrayDeque<E> clone() {
try {
@SuppressWarnings("unchecked")
- ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
+ ArrayDeque<E> result = (ArrayDeque<E>) super.clone();
result.elements = Arrays.copyOf(elements, elements.length);
return result;
-
} catch (CloneNotSupportedException e) {
throw new AssertionError();
}
}
- /**
- * Appease the serialization gods.
- */
private static final long serialVersionUID = 2340985798034038923L;
/**
- * Serialize this deque.
+ * Saves this deque to a stream (that is, serializes it).
*
- * @serialData The current size (<tt>int</tt>) of the deque,
+ * @serialData The current size ({@code int}) of the deque,
* followed by all of its elements (each an object reference) in
* first-to-last order.
*/
- private void writeObject(ObjectOutputStream s) throws IOException {
+ private void writeObject(java.io.ObjectOutputStream s)
+ throws java.io.IOException {
s.defaultWriteObject();
// Write out size
@@ -852,11 +871,10 @@
}
/**
- * Deserialize this deque.
+ * Reconstitutes this deque from a stream (that is, deserializes it).
*/
- @SuppressWarnings("unchecked")
- private void readObject(ObjectInputStream s)
- throws IOException, ClassNotFoundException {
+ private void readObject(java.io.ObjectInputStream s)
+ throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
// Read in size and allocate array
@@ -867,6 +885,88 @@
// Read in all elements in the proper order.
for (int i = 0; i < size; i++)
- elements[i] = (E)s.readObject();
+ elements[i] = s.readObject();
+ }
+
+ public Spliterator<E> spliterator() {
+ return new DeqSpliterator<E>(this, -1, -1);
}
+
+ static final class DeqSpliterator<E> implements Spliterator<E> {
+ private final ArrayDeque<E> deq;
+ private int fence; // -1 until first use
+ private int index; // current index, modified on traverse/split
+
+ /** Creates new spliterator covering the given array and range */
+ DeqSpliterator(ArrayDeque<E> deq, int origin, int fence) {
+ this.deq = deq;
+ this.index = origin;
+ this.fence = fence;
+ }
+
+ private int getFence() { // force initialization
+ int t;
+ if ((t = fence) < 0) {
+ t = fence = deq.tail;
+ index = deq.head;
+ }
+ return t;
+ }
+
+ public DeqSpliterator<E> trySplit() {
+ int t = getFence(), h = index, n = deq.elements.length;
+ if (h != t && ((h + 1) & (n - 1)) != t) {
+ if (h > t)
+ t += n;
+ int m = ((h + t) >>> 1) & (n - 1);
+ return new DeqSpliterator<>(deq, h, index = m);
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super E> consumer) {
+ if (consumer == null)
+ throw new NullPointerException();
+ Object[] a = deq.elements;
+ int m = a.length - 1, f = getFence(), i = index;
+ index = f;
+ while (i != f) {
+ @SuppressWarnings("unchecked") E e = (E)a[i];
+ i = (i + 1) & m;
+ if (e == null)
+ throw new ConcurrentModificationException();
+ consumer.accept(e);
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super E> consumer) {
+ if (consumer == null)
+ throw new NullPointerException();
+ Object[] a = deq.elements;
+ int m = a.length - 1, f = getFence(), i = index;
+ if (i != fence) {
+ @SuppressWarnings("unchecked") E e = (E)a[i];
+ index = (i + 1) & m;
+ if (e == null)
+ throw new ConcurrentModificationException();
+ consumer.accept(e);
+ return true;
+ }
+ return false;
+ }
+
+ public long estimateSize() {
+ int n = getFence() - index;
+ if (n < 0)
+ n += deq.elements.length;
+ return (long) n;
+ }
+
+ @Override
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.SIZED |
+ Spliterator.NONNULL | Spliterator.SUBSIZED;
+ }
+ }
+
}
--- a/jdk/src/share/classes/java/util/ArrayList.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/ArrayList.java Wed Apr 17 11:34:31 2013 +0200
@@ -29,6 +29,10 @@
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.function.UnaryOperator;
+
/**
* Resizable-array implementation of the <tt>List</tt> interface. Implements
* all optional list operations, and permits all elements, including
@@ -124,7 +128,7 @@
* empty ArrayList with elementData == EMPTY_ELEMENTDATA will be expanded to
* DEFAULT_CAPACITY when the first element is added.
*/
- private transient Object[] elementData;
+ transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
@@ -857,6 +861,27 @@
}
}
+ @Override
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super E> consumer) {
+ Objects.requireNonNull(consumer);
+ final int size = ArrayList.this.size;
+ int i = cursor;
+ if (i >= size) {
+ return;
+ }
+ final Object[] elementData = ArrayList.this.elementData;
+ if (i >= elementData.length) {
+ throw new ConcurrentModificationException();
+ }
+ while (i != size && modCount == expectedModCount) {
+ consumer.accept((E) elementData[i++]);
+ }
+ // update once at end of iteration to reduce heap write traffic
+ lastRet = cursor = i;
+ checkForComodification();
+ }
+
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
@@ -1092,6 +1117,26 @@
return (E) elementData[offset + (lastRet = i)];
}
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super E> consumer) {
+ Objects.requireNonNull(consumer);
+ final int size = SubList.this.size;
+ int i = cursor;
+ if (i >= size) {
+ return;
+ }
+ final Object[] elementData = ArrayList.this.elementData;
+ if (offset + i >= elementData.length) {
+ throw new ConcurrentModificationException();
+ }
+ while (i != size && modCount == expectedModCount) {
+ consumer.accept((E) elementData[offset + (i++)]);
+ }
+ // update once at end of iteration to reduce heap write traffic
+ lastRet = cursor = i;
+ checkForComodification();
+ }
+
public int nextIndex() {
return cursor;
}
@@ -1171,6 +1216,12 @@
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
+
+ public Spliterator<E> spliterator() {
+ checkForComodification();
+ return new ArrayListSpliterator<E>(ArrayList.this, offset,
+ offset + this.size, this.modCount);
+ }
}
@Override
@@ -1188,6 +1239,128 @@
}
}
+ public Spliterator<E> spliterator() {
+ return new ArrayListSpliterator<>(this, 0, -1, 0);
+ }
+
+ /** Index-based split-by-two, lazily initialized Spliterator */
+ static final class ArrayListSpliterator<E> implements Spliterator<E> {
+
+ /*
+ * If ArrayLists were immutable, or structurally immutable (no
+ * adds, removes, etc), we could implement their spliterators
+ * with Arrays.spliterator. Instead we detect as much
+ * interference during traversal as practical without
+ * sacrificing much performance. We rely primarily on
+ * modCounts. These are not guaranteed to detect concurrency
+ * violations, and are sometimes overly conservative about
+ * within-thread interference, but detect enough problems to
+ * be worthwhile in practice. To carry this out, we (1) lazily
+ * initialize fence and expectedModCount until the latest
+ * point that we need to commit to the state we are checking
+ * against; thus improving precision. (This doesn't apply to
+ * SubLists, that create spliterators with current non-lazy
+ * values). (2) We perform only a single
+ * ConcurrentModificationException check at the end of forEach
+ * (the most performance-sensitive method). When using forEach
+ * (as opposed to iterators), we can normally only detect
+ * interference after actions, not before. Further
+ * CME-triggering checks apply to all other possible
+ * violations of assumptions for example null or too-small
+ * elementData array given its size(), that could only have
+ * occurred due to interference. This allows the inner loop
+ * of forEach to run without any further checks, and
+ * simplifies lambda-resolution. While this does entail a
+ * number of checks, note that in the common case of
+ * list.stream().forEach(a), no checks or other computation
+ * occur anywhere other than inside forEach itself. The other
+ * less-often-used methods cannot take advantage of most of
+ * these streamlinings.
+ */
+
+ private final ArrayList<E> list;
+ private int index; // current index, modified on advance/split
+ private int fence; // -1 until used; then one past last index
+ private int expectedModCount; // initialized when fence set
+
+ /** Create new spliterator covering the given range */
+ ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
+ int expectedModCount) {
+ this.list = list; // OK if null unless traversed
+ this.index = origin;
+ this.fence = fence;
+ this.expectedModCount = expectedModCount;
+ }
+
+ private int getFence() { // initialize fence to size on first use
+ int hi; // (a specialized variant appears in method forEach)
+ ArrayList<E> lst;
+ if ((hi = fence) < 0) {
+ if ((lst = list) == null)
+ hi = fence = 0;
+ else {
+ expectedModCount = lst.modCount;
+ hi = fence = lst.size;
+ }
+ }
+ return hi;
+ }
+
+ public ArrayListSpliterator<E> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid) ? null : // divide range in half unless too small
+ new ArrayListSpliterator<E>(list, lo, index = mid,
+ expectedModCount);
+ }
+
+ public boolean tryAdvance(Consumer<? super E> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int hi = getFence(), i = index;
+ if (i < hi) {
+ index = i + 1;
+ @SuppressWarnings("unchecked") E e = (E)list.elementData[i];
+ action.accept(e);
+ if (list.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ return false;
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ int i, hi, mc; // hoist accesses and checks from loop
+ ArrayList<E> lst; Object[] a;
+ if (action == null)
+ throw new NullPointerException();
+ if ((lst = list) != null && (a = lst.elementData) != null) {
+ if ((hi = fence) < 0) {
+ mc = lst.modCount;
+ hi = lst.size;
+ }
+ else
+ mc = expectedModCount;
+ if ((i = index) >= 0 && (index = hi) <= a.length) {
+ for (; i < hi; ++i) {
+ @SuppressWarnings("unchecked") E e = (E) a[i];
+ action.accept(e);
+ }
+ if (lst.modCount == mc)
+ return;
+ }
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ public long estimateSize() {
+ return (long) (getFence() - index);
+ }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
+ }
+ }
+
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
--- a/jdk/src/share/classes/java/util/Collections.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/Collections.java Wed Apr 17 11:34:31 2013 +0200
@@ -1088,6 +1088,11 @@
public void remove() {
throw new UnsupportedOperationException();
}
+ @Override
+ public void forEachRemaining(Consumer<? super E> action) {
+ // Use backing collection version
+ i.forEachRemaining(action);
+ }
};
}
@@ -1114,6 +1119,7 @@
throw new UnsupportedOperationException();
}
+ // Override default methods in Collection
@Override
public void forEach(Consumer<? super E> action) {
c.forEach(action);
@@ -1122,6 +1128,11 @@
public boolean removeIf(Predicate<? super E> filter) {
throw new UnsupportedOperationException();
}
+ @Override
+ public Spliterator<E> spliterator() {
+ return (Spliterator<E>)c.spliterator();
+ }
+
}
/**
@@ -1285,6 +1296,11 @@
public void add(E e) {
throw new UnsupportedOperationException();
}
+
+ @Override
+ public void forEachRemaining(Consumer<? super E> action) {
+ i.forEachRemaining(action);
+ }
};
}
@@ -1664,7 +1680,8 @@
* through the returned collection.<p>
*
* It is imperative that the user manually synchronize on the returned
- * collection when iterating over it:
+ * collection when traversing it via {@link Iterator} or
+ * {@link Spliterator}:
* <pre>
* Collection c = Collections.synchronizedCollection(myCollection);
* ...
@@ -1761,18 +1778,22 @@
public String toString() {
synchronized (mutex) {return c.toString();}
}
- private void writeObject(ObjectOutputStream s) throws IOException {
- synchronized (mutex) {s.defaultWriteObject();}
- }
-
+ // Override default methods in Collection
@Override
- public void forEach(Consumer<? super E> action) {
- synchronized (mutex) {c.forEach(action);}
+ public void forEach(Consumer<? super E> consumer) {
+ synchronized (mutex) {c.forEach(consumer);}
}
@Override
public boolean removeIf(Predicate<? super E> filter) {
synchronized (mutex) {return c.removeIf(filter);}
}
+ @Override
+ public Spliterator<E> spliterator() {
+ return c.spliterator(); // Must be manually synched by user!
+ }
+ private void writeObject(ObjectOutputStream s) throws IOException {
+ synchronized (mutex) {s.defaultWriteObject();}
+ }
}
/**
@@ -2533,14 +2554,15 @@
return c.addAll(checkedCopyOf(coll));
}
+ // Override default methods in Collection
@Override
- public void forEach(Consumer<? super E> action) {
- c.forEach(action);
- }
+ public void forEach(Consumer<? super E> action) {c.forEach(action);}
@Override
public boolean removeIf(Predicate<? super E> filter) {
return c.removeIf(filter);
}
+ @Override
+ public Spliterator<E> spliterator() {return c.spliterator();}
}
/**
@@ -2796,6 +2818,11 @@
typeCheck(e);
i.add(e);
}
+
+ @Override
+ public void forEachRemaining(Consumer<? super E> action) {
+ i.forEachRemaining(action);
+ }
};
}
@@ -3334,6 +3361,10 @@
public boolean hasNext() { return false; }
public E next() { throw new NoSuchElementException(); }
public void remove() { throw new IllegalStateException(); }
+ @Override
+ public void forEachRemaining(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ }
}
/**
@@ -3474,6 +3505,7 @@
return a;
}
+ // Override default methods in Collection
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
@@ -3483,6 +3515,8 @@
Objects.requireNonNull(filter);
return false;
}
+ @Override
+ public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
// Preserves singleton property
private Object readResolve() {
@@ -3592,15 +3626,20 @@
throw new NoSuchElementException();
}
+ // Override default methods in Collection
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
}
+
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
return false;
}
+
+ @Override
+ public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
}
/**
@@ -3671,10 +3710,6 @@
public int hashCode() { return 1; }
@Override
- public void forEach(Consumer<? super E> action) {
- Objects.requireNonNull(action);
- }
- @Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
return false;
@@ -3688,6 +3723,15 @@
Objects.requireNonNull(c);
}
+ // Override default methods in Collection
+ @Override
+ public void forEach(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ }
+
+ @Override
+ public Spliterator<E> spliterator() { return Spliterators.emptySpliterator(); }
+
// Preserves singleton property
private Object readResolve() {
return EMPTY_LIST;
@@ -3843,6 +3887,60 @@
public void remove() {
throw new UnsupportedOperationException();
}
+ @Override
+ public void forEachRemaining(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ if (hasNext) {
+ action.accept(e);
+ hasNext = false;
+ }
+ }
+ };
+ }
+
+ /**
+ * Creates a {@code Spliterator} with only the specified element
+ *
+ * @param <T> Type of elements
+ * @return A singleton {@code Spliterator}
+ */
+ static <T> Spliterator<T> singletonSpliterator(final T element) {
+ return new Spliterator<T>() {
+ long est = 1;
+
+ @Override
+ public Spliterator<T> trySplit() {
+ return null;
+ }
+
+ @Override
+ public boolean tryAdvance(Consumer<? super T> consumer) {
+ Objects.requireNonNull(consumer);
+ if (est > 0) {
+ est--;
+ consumer.accept(element);
+ return true;
+ }
+ return false;
+ }
+
+ @Override
+ public void forEachRemaining(Consumer<? super T> consumer) {
+ tryAdvance(consumer);
+ }
+
+ @Override
+ public long estimateSize() {
+ return est;
+ }
+
+ @Override
+ public int characteristics() {
+ int value = (element != null) ? Spliterator.NONNULL : 0;
+
+ return value | Spliterator.SIZED | Spliterator.SUBSIZED | Spliterator.IMMUTABLE |
+ Spliterator.DISTINCT | Spliterator.ORDERED;
+ }
};
}
@@ -3867,11 +3965,16 @@
public boolean contains(Object o) {return eq(o, element);}
+ // Override default methods for Collection
@Override
public void forEach(Consumer<? super E> action) {
action.accept(element);
}
@Override
+ public Spliterator<E> spliterator() {
+ return singletonSpliterator(element);
+ }
+ @Override
public boolean removeIf(Predicate<? super E> filter) {
throw new UnsupportedOperationException();
}
@@ -3916,6 +4019,7 @@
return element;
}
+ // Override default methods for Collection
@Override
public void forEach(Consumer<? super E> action) {
action.accept(element);
@@ -3931,6 +4035,10 @@
@Override
public void sort(Comparator<? super E> c) {
}
+ @Override
+ public Spliterator<E> spliterator() {
+ return singletonSpliterator(element);
+ }
}
/**
@@ -4529,6 +4637,7 @@
public boolean retainAll(Collection<?> c) {return s.retainAll(c);}
// addAll is the only inherited implementation
+ // Override default methods in Collection
@Override
public void forEach(Consumer<? super E> action) {
s.forEach(action);
@@ -4538,6 +4647,9 @@
return s.removeIf(filter);
}
+ @Override
+ public Spliterator<E> spliterator() {return s.spliterator();}
+
private static final long serialVersionUID = 2454657854757543876L;
private void readObject(java.io.ObjectInputStream stream)
@@ -4597,10 +4709,11 @@
public boolean retainAll(Collection<?> c) {return q.retainAll(c);}
// We use inherited addAll; forwarding addAll would be wrong
+ // Override default methods in Collection
@Override
- public void forEach(Consumer<? super E> action) {
- q.forEach(action);
- }
+ public void forEach(Consumer<? super E> action) {q.forEach(action);}
+ @Override
+ public Spliterator<E> spliterator() {return q.spliterator();}
@Override
public boolean removeIf(Predicate<? super E> filter) {
return q.removeIf(filter);
--- a/jdk/src/share/classes/java/util/HashMap.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/HashMap.java Wed Apr 17 11:34:31 2013 +0200
@@ -1230,6 +1230,14 @@
public void clear() {
HashMap.this.clear();
}
+
+ public Spliterator<K> spliterator() {
+ if (HashMap.this.getClass() == HashMap.class)
+ return new KeySpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
+ else
+ return Spliterators.spliterator
+ (this, Spliterator.SIZED | Spliterator.DISTINCT);
+ }
}
/**
@@ -1263,6 +1271,14 @@
public void clear() {
HashMap.this.clear();
}
+
+ public Spliterator<V> spliterator() {
+ if (HashMap.this.getClass() == HashMap.class)
+ return new ValueSpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
+ else
+ return Spliterators.spliterator
+ (this, Spliterator.SIZED);
+ }
}
/**
@@ -1310,6 +1326,14 @@
public void clear() {
HashMap.this.clear();
}
+
+ public Spliterator<Map.Entry<K,V>> spliterator() {
+ if (HashMap.this.getClass() == HashMap.class)
+ return new EntrySpliterator<K,V>(HashMap.this, 0, -1, 0, 0);
+ else
+ return Spliterators.spliterator
+ (this, Spliterator.SIZED | Spliterator.DISTINCT);
+ }
}
/**
@@ -1406,4 +1430,257 @@
// These methods are used when serializing HashSets
int capacity() { return table.length; }
float loadFactor() { return loadFactor; }
+
+ /**
+ * Standin until HM overhaul; based loosely on Weak and Identity HM.
+ */
+ static class HashMapSpliterator<K,V> {
+ final HashMap<K,V> map;
+ HashMap.Entry<K,V> current; // current node
+ int index; // current index, modified on advance/split
+ int fence; // one past last index
+ int est; // size estimate
+ int expectedModCount; // for comodification checks
+
+ HashMapSpliterator(HashMap<K,V> m, int origin,
+ int fence, int est,
+ int expectedModCount) {
+ this.map = m;
+ this.index = origin;
+ this.fence = fence;
+ this.est = est;
+ this.expectedModCount = expectedModCount;
+ }
+
+ final int getFence() { // initialize fence and size on first use
+ int hi;
+ if ((hi = fence) < 0) {
+ HashMap<K,V> m = map;
+ est = m.size;
+ expectedModCount = m.modCount;
+ hi = fence = m.table.length;
+ }
+ return hi;
+ }
+
+ public final long estimateSize() {
+ getFence(); // force init
+ return (long) est;
+ }
+ }
+
+ static final class KeySpliterator<K,V>
+ extends HashMapSpliterator<K,V>
+ implements Spliterator<K> {
+ KeySpliterator(HashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public KeySpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid || current != null) ? null :
+ new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super K> action) {
+ int i, hi, mc;
+ if (action == null)
+ throw new NullPointerException();
+ HashMap<K,V> m = map;
+ HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+ if ((hi = fence) < 0) {
+ mc = expectedModCount = m.modCount;
+ hi = fence = tab.length;
+ }
+ else
+ mc = expectedModCount;
+ if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
+ HashMap.Entry<K,V> p = current;
+ do {
+ if (p == null)
+ p = tab[i++];
+ else {
+ action.accept(p.getKey());
+ p = p.next;
+ }
+ } while (p != null || i < hi);
+ if (m.modCount != mc)
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public boolean tryAdvance(Consumer<? super K> action) {
+ int hi;
+ if (action == null)
+ throw new NullPointerException();
+ HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
+ if (tab.length >= (hi = getFence()) && index >= 0) {
+ while (current != null || index < hi) {
+ if (current == null)
+ current = tab[index++];
+ else {
+ K k = current.getKey();
+ current = current.next;
+ action.accept(k);
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
+ Spliterator.DISTINCT;
+ }
+ }
+
+ static final class ValueSpliterator<K,V>
+ extends HashMapSpliterator<K,V>
+ implements Spliterator<V> {
+ ValueSpliterator(HashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public ValueSpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid || current != null) ? null :
+ new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super V> action) {
+ int i, hi, mc;
+ if (action == null)
+ throw new NullPointerException();
+ HashMap<K,V> m = map;
+ HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+ if ((hi = fence) < 0) {
+ mc = expectedModCount = m.modCount;
+ hi = fence = tab.length;
+ }
+ else
+ mc = expectedModCount;
+ if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
+ HashMap.Entry<K,V> p = current;
+ do {
+ if (p == null)
+ p = tab[i++];
+ else {
+ action.accept(p.getValue());
+ p = p.next;
+ }
+ } while (p != null || i < hi);
+ if (m.modCount != mc)
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public boolean tryAdvance(Consumer<? super V> action) {
+ int hi;
+ if (action == null)
+ throw new NullPointerException();
+ HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
+ if (tab.length >= (hi = getFence()) && index >= 0) {
+ while (current != null || index < hi) {
+ if (current == null)
+ current = tab[index++];
+ else {
+ V v = current.getValue();
+ current = current.next;
+ action.accept(v);
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? Spliterator.SIZED : 0);
+ }
+ }
+
+ static final class EntrySpliterator<K,V>
+ extends HashMapSpliterator<K,V>
+ implements Spliterator<Map.Entry<K,V>> {
+ EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public EntrySpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid || current != null) ? null :
+ new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
+ int i, hi, mc;
+ if (action == null)
+ throw new NullPointerException();
+ HashMap<K,V> m = map;
+ HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])m.table;
+ if ((hi = fence) < 0) {
+ mc = expectedModCount = m.modCount;
+ hi = fence = tab.length;
+ }
+ else
+ mc = expectedModCount;
+ if (tab.length >= hi && (i = index) >= 0 && i < (index = hi)) {
+ HashMap.Entry<K,V> p = current;
+ do {
+ if (p == null)
+ p = tab[i++];
+ else {
+ action.accept(p);
+ p = p.next;
+ }
+ } while (p != null || i < hi);
+ if (m.modCount != mc)
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ @SuppressWarnings("unchecked")
+ public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+ int hi;
+ if (action == null)
+ throw new NullPointerException();
+ HashMap.Entry<K,V>[] tab = (HashMap.Entry<K,V>[])map.table;
+ if (tab.length >= (hi = getFence()) && index >= 0) {
+ while (current != null || index < hi) {
+ if (current == null)
+ current = tab[index++];
+ else {
+ HashMap.Entry<K,V> e = current;
+ current = current.next;
+ action.accept(e);
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
+ Spliterator.DISTINCT;
+ }
+ }
}
--- a/jdk/src/share/classes/java/util/HashSet.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/HashSet.java Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 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
@@ -311,4 +311,8 @@
map.put(e, PRESENT);
}
}
+
+ public Spliterator<E> spliterator() {
+ return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
+ }
}
--- a/jdk/src/share/classes/java/util/IdentityHashMap.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/IdentityHashMap.java Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2000, 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,8 +24,10 @@
*/
package java.util;
+
import java.io.*;
import java.lang.reflect.Array;
+import java.util.function.Consumer;
/**
* This class implements the <tt>Map</tt> interface with a hash table, using
@@ -162,19 +164,19 @@
/**
* The table, resized as necessary. Length MUST always be a power of two.
*/
- private transient Object[] table;
+ transient Object[] table; // non-private to simplify nested class access
/**
* The number of key-value mappings contained in this identity hash map.
*
* @serial
*/
- private int size;
+ int size;
/**
* The number of modifications, to support fast-fail iterators
*/
- private transient int modCount;
+ transient int modCount;
/**
* The next size value at which to resize (capacity * load factor).
@@ -184,7 +186,7 @@
/**
* Value representing null keys inside tables.
*/
- private static final Object NULL_KEY = new Object();
+ static final Object NULL_KEY = new Object();
/**
* Use NULL_KEY for key if it is null.
@@ -196,7 +198,7 @@
/**
* Returns internal representation of null key back to caller as null.
*/
- private static Object unmaskNull(Object key) {
+ static final Object unmaskNull(Object key) {
return (key == NULL_KEY ? null : key);
}
@@ -1012,7 +1014,7 @@
return result;
}
public Object[] toArray() {
- return toArray(new Object[size()]);
+ return toArray(new Object[0]);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
@@ -1042,6 +1044,10 @@
}
return a;
}
+
+ public Spliterator<K> spliterator() {
+ return new KeySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+ }
}
/**
@@ -1095,7 +1101,7 @@
IdentityHashMap.this.clear();
}
public Object[] toArray() {
- return toArray(new Object[size()]);
+ return toArray(new Object[0]);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
@@ -1124,6 +1130,10 @@
}
return a;
}
+
+ public Spliterator<V> spliterator() {
+ return new ValueSpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+ }
}
/**
@@ -1211,7 +1221,7 @@
}
public Object[] toArray() {
- return toArray(new Object[size()]);
+ return toArray(new Object[0]);
}
@SuppressWarnings("unchecked")
@@ -1242,6 +1252,10 @@
}
return a;
}
+
+ public Spliterator<Map.Entry<K,V>> spliterator() {
+ return new EntrySpliterator<>(IdentityHashMap.this, 0, -1, 0, 0);
+ }
}
@@ -1322,4 +1336,223 @@
tab[i] = k;
tab[i + 1] = value;
}
+
+ /**
+ * Similar form as array-based Spliterators, but skips blank elements,
+ * and guestimates size as decreasing by half per split.
+ */
+ static class IdentityHashMapSpliterator<K,V> {
+ final IdentityHashMap<K,V> map;
+ int index; // current index, modified on advance/split
+ int fence; // -1 until first use; then one past last index
+ int est; // size estimate
+ int expectedModCount; // initialized when fence set
+
+ IdentityHashMapSpliterator(IdentityHashMap<K,V> map, int origin,
+ int fence, int est, int expectedModCount) {
+ this.map = map;
+ this.index = origin;
+ this.fence = fence;
+ this.est = est;
+ this.expectedModCount = expectedModCount;
+ }
+
+ final int getFence() { // initialize fence and size on first use
+ int hi;
+ if ((hi = fence) < 0) {
+ est = map.size;
+ expectedModCount = map.modCount;
+ hi = fence = map.table.length;
+ }
+ return hi;
+ }
+
+ public final long estimateSize() {
+ getFence(); // force init
+ return (long) est;
+ }
+ }
+
+ static final class KeySpliterator<K,V>
+ extends IdentityHashMapSpliterator<K,V>
+ implements Spliterator<K> {
+ KeySpliterator(IdentityHashMap<K,V> map, int origin, int fence, int est,
+ int expectedModCount) {
+ super(map, origin, fence, est, expectedModCount);
+ }
+
+ public KeySpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+ return (lo >= mid) ? null :
+ new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super K> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int i, hi, mc; Object key;
+ IdentityHashMap<K,V> m; Object[] a;
+ if ((m = map) != null && (a = m.table) != null &&
+ (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+ for (; i < hi; i += 2) {
+ if ((key = a[i]) != null)
+ action.accept((K)unmaskNull(key));
+ }
+ if (m.modCount == expectedModCount)
+ return;
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ @SuppressWarnings("unchecked")
+ public boolean tryAdvance(Consumer<? super K> action) {
+ if (action == null)
+ throw new NullPointerException();
+ Object[] a = map.table;
+ int hi = getFence();
+ while (index < hi) {
+ Object key = a[index];
+ index += 2;
+ if (key != null) {
+ action.accept((K)unmaskNull(key));
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
+ }
+ }
+
+ static final class ValueSpliterator<K,V>
+ extends IdentityHashMapSpliterator<K,V>
+ implements Spliterator<V> {
+ ValueSpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public ValueSpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+ return (lo >= mid) ? null :
+ new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ public void forEachRemaining(Consumer<? super V> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int i, hi, mc;
+ IdentityHashMap<K,V> m; Object[] a;
+ if ((m = map) != null && (a = m.table) != null &&
+ (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+ for (; i < hi; i += 2) {
+ if (a[i] != null) {
+ @SuppressWarnings("unchecked") V v = (V)a[i+1];
+ action.accept(v);
+ }
+ }
+ if (m.modCount == expectedModCount)
+ return;
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean tryAdvance(Consumer<? super V> action) {
+ if (action == null)
+ throw new NullPointerException();
+ Object[] a = map.table;
+ int hi = getFence();
+ while (index < hi) {
+ Object key = a[index];
+ @SuppressWarnings("unchecked") V v = (V)a[index+1];
+ index += 2;
+ if (key != null) {
+ action.accept(v);
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? SIZED : 0);
+ }
+
+ }
+
+ static final class EntrySpliterator<K,V>
+ extends IdentityHashMapSpliterator<K,V>
+ implements Spliterator<Map.Entry<K,V>> {
+ EntrySpliterator(IdentityHashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public EntrySpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = ((lo + hi) >>> 1) & ~1;
+ return (lo >= mid) ? null :
+ new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
+ if (action == null)
+ throw new NullPointerException();
+ int i, hi, mc;
+ IdentityHashMap<K,V> m; Object[] a;
+ if ((m = map) != null && (a = m.table) != null &&
+ (i = index) >= 0 && (index = hi = getFence()) <= a.length) {
+ for (; i < hi; i += 2) {
+ Object key = a[i];
+ if (key != null) {
+ @SuppressWarnings("unchecked") K k =
+ (K)unmaskNull(key);
+ @SuppressWarnings("unchecked") V v = (V)a[i+1];
+ action.accept
+ (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+
+ }
+ }
+ if (m.modCount == expectedModCount)
+ return;
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+ if (action == null)
+ throw new NullPointerException();
+ Object[] a = map.table;
+ int hi = getFence();
+ while (index < hi) {
+ Object key = a[index];
+ @SuppressWarnings("unchecked") V v = (V)a[index+1];
+ index += 2;
+ if (key != null) {
+ @SuppressWarnings("unchecked") K k =
+ (K)unmaskNull(key);
+ action.accept
+ (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return (fence < 0 || est == map.size ? SIZED : 0) | Spliterator.DISTINCT;
+ }
+ }
+
}
--- a/jdk/src/share/classes/java/util/LinkedHashSet.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/LinkedHashSet.java Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 2000, 2006, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 2000, 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
@@ -168,4 +168,18 @@
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
+
+ /**
+ * Creates a {@code Spliterator}, over the elements in this set, that
+ * reports {@code SIZED}, {@code DISTINCT} and {@code ORDERED}.
+ * Overriding implementations are expected to document if the
+ * {@code Spliterator} reports any additional and relevant characteristic
+ * values.
+ *
+ * @return a {@code Spliterator} over the elements in this set
+ */
+ @Override
+ public Spliterator<E> spliterator() {
+ return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
+ }
}
--- a/jdk/src/share/classes/java/util/LinkedList.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/LinkedList.java Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 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
@@ -25,6 +25,8 @@
package java.util;
+import java.util.function.Consumer;
+
/**
* Doubly-linked list implementation of the {@code List} and {@code Deque}
* interfaces. Implements all optional list operations, and permits all
@@ -948,6 +950,16 @@
expectedModCount++;
}
+ public void forEachRemaining(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ while (modCount == expectedModCount && nextIndex < size) {
+ action.accept(next.item);
+ next = next.next;
+ nextIndex++;
+ }
+ checkForComodification();
+ }
+
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
@@ -1135,4 +1147,103 @@
for (int i = 0; i < size; i++)
linkLast((E)s.readObject());
}
+
+ public Spliterator<E> spliterator() {
+ return new LLSpliterator<E>(this, -1, 0);
+ }
+
+ /** A customized variant of Spliterators.IteratorSpliterator */
+ static final class LLSpliterator<E> implements Spliterator<E> {
+ static final int BATCH_UNIT = 1 << 10; // batch array size increment
+ static final int MAX_BATCH = 1 << 25; // max batch array size;
+ final LinkedList<E> list; // null OK unless traversed
+ Node<E> current; // current node; null until initialized
+ int est; // size estimate; -1 until first needed
+ int expectedModCount; // initialized when est set
+ int batch; // batch size for splits
+
+ LLSpliterator(LinkedList<E> list, int est, int expectedModCount) {
+ this.list = list;
+ this.est = est;
+ this.expectedModCount = expectedModCount;
+ }
+
+ final int getEst() {
+ int s; // force initialization
+ final LinkedList<E> lst;
+ if ((s = est) < 0) {
+ if ((lst = list) == null)
+ s = est = 0;
+ else {
+ expectedModCount = lst.modCount;
+ current = lst.first;
+ s = est = lst.size;
+ }
+ }
+ return s;
+ }
+
+ public long estimateSize() { return (long) getEst(); }
+
+ public Spliterator<E> trySplit() {
+ Node<E> p;
+ int s = getEst();
+ if (s > 1 && (p = current) != null) {
+ int n = batch + BATCH_UNIT;
+ if (n > s)
+ n = s;
+ if (n > MAX_BATCH)
+ n = MAX_BATCH;
+ Object[] a;
+ try {
+ a = new Object[n];
+ } catch (OutOfMemoryError oome) {
+ return null;
+ }
+ int j = 0;
+ do { a[j++] = p.item; } while ((p = p.next) != null && j < n);
+ current = p;
+ batch = j;
+ est = s - j;
+ return Spliterators.spliterator(a, 0, j, Spliterator.ORDERED);
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super E> action) {
+ Node<E> p; int n;
+ if (action == null) throw new NullPointerException();
+ if ((n = getEst()) > 0 && (p = current) != null) {
+ current = null;
+ est = 0;
+ do {
+ E e = p.item;
+ p = p.next;
+ action.accept(e);
+ } while (p != null && --n > 0);
+ }
+ if (list.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean tryAdvance(Consumer<? super E> action) {
+ Node<E> p;
+ if (action == null) throw new NullPointerException();
+ if (getEst() > 0 && (p = current) != null) {
+ --est;
+ E e = p.item;
+ current = p.next;
+ action.accept(e);
+ if (list.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
+ }
+ }
+
}
--- a/jdk/src/share/classes/java/util/PriorityQueue.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/PriorityQueue.java Wed Apr 17 11:34:31 2013 +0200
@@ -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
@@ -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
@@ -56,7 +58,7 @@
* the priority queue in any particular order. If you need ordered
* traversal, consider using {@code Arrays.sort(pq.toArray())}.
*
- * <p> <strong>Note that this implementation is not synchronized.</strong>
+ * <p><strong>Note that this implementation is not synchronized.</strong>
* Multiple threads should not access a {@code PriorityQueue}
* instance concurrently if any of the threads modifies the queue.
* Instead, use the thread-safe {@link
@@ -92,7 +94,7 @@
* 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.
@@ -109,7 +111,7 @@
* The number of times this priority queue has been
* <i>structurally modified</i>. 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
@@ -332,9 +334,7 @@
@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) {
@@ -431,15 +431,14 @@
* precise control over the runtime type of the output array, and may,
* under certain circumstances, be used to save allocation costs.
*
- * <p>Suppose <tt>x</tt> is a queue known to contain only strings.
+ * <p>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 <tt>String</tt>:
+ * allocated array of {@code String}:
*
- * <pre>
- * String[] y = x.toArray(new String[0]);</pre>
+ * <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
*
- * Note that <tt>toArray(new Object[0])</tt> is identical in function to
- * <tt>toArray()</tt>.
+ * 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
@@ -452,6 +451,7 @@
*/
@SuppressWarnings("unchecked")
public <T> 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());
@@ -569,15 +569,14 @@
size = 0;
}
+ @SuppressWarnings("unchecked")
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
- @SuppressWarnings("unchecked")
- E result = (E) queue[0];
- @SuppressWarnings("unchecked")
- E x = (E) queue[s];
+ E result = (E) queue[0];
+ E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
@@ -596,15 +595,15 @@
* 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
queue[i] = null;
else {
- @SuppressWarnings("unchecked")
- E moved = (E) queue[s];
+ E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
@@ -649,12 +648,12 @@
queue[k] = key;
}
+ @SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
- @SuppressWarnings("unchecked")
- E e = (E) queue[parent];
- if (comparator.compare(x, e) >= 0)
+ Object e = queue[parent];
+ if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e;
k = parent;
@@ -738,8 +737,7 @@
}
/**
- * 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
@@ -747,7 +745,7 @@
* @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();
@@ -783,4 +781,99 @@
// spec has never explained what that might be.
heapify();
}
+
+ public final Spliterator<E> spliterator() {
+ return new PriorityQueueSpliterator<E>(this, 0, -1, 0);
+ }
+
+ static final class PriorityQueueSpliterator<E> implements Spliterator<E> {
+ /*
+ * This is very similar to ArrayList Spliterator, except for
+ * extra null checks.
+ */
+ private final PriorityQueue<E> 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<E> 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<E> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid) ? null :
+ new PriorityQueueSpliterator<E>(pq, lo, index = mid,
+ expectedModCount);
+ }
+
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super E> action) {
+ int i, hi, mc; // hoist accesses and checks from loop
+ PriorityQueue<E> 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<? super E> 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;
+ }
+ }
}
--- a/jdk/src/share/classes/java/util/TreeMap.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/TreeMap.java Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1997, 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
@@ -25,6 +25,8 @@
package java.util;
+import java.util.function.Consumer;
+
/**
* A Red-Black tree based {@link NavigableMap} implementation.
* The map is sorted according to the {@linkplain Comparable natural
@@ -971,6 +973,10 @@
public void clear() {
TreeMap.this.clear();
}
+
+ public Spliterator<V> spliterator() {
+ return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
+ }
}
class EntrySet extends AbstractSet<Map.Entry<K,V>> {
@@ -1007,6 +1013,10 @@
public void clear() {
TreeMap.this.clear();
}
+
+ public Spliterator<Map.Entry<K,V>> spliterator() {
+ return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
+ }
}
/*
@@ -1090,6 +1100,10 @@
public NavigableSet<E> descendingSet() {
return new KeySet<>(m.descendingMap());
}
+
+ public Spliterator<E> spliterator() {
+ return keySpliteratorFor(m);
+ }
}
/**
@@ -1389,6 +1403,8 @@
/** Returns ascending iterator from the perspective of this submap */
abstract Iterator<K> keyIterator();
+ abstract Spliterator<K> keySpliterator();
+
/** Returns descending iterator from the perspective of this submap */
abstract Iterator<K> descendingKeyIterator();
@@ -1650,19 +1666,6 @@
}
}
- final class SubMapKeyIterator extends SubMapIterator<K> {
- SubMapKeyIterator(TreeMap.Entry<K,V> first,
- TreeMap.Entry<K,V> fence) {
- super(first, fence);
- }
- public K next() {
- return nextEntry().key;
- }
- public void remove() {
- removeAscending();
- }
- }
-
final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
TreeMap.Entry<K,V> fence) {
@@ -1677,7 +1680,47 @@
}
}
- final class DescendingSubMapKeyIterator extends SubMapIterator<K> {
+ // Implement minimal Spliterator as KeySpliterator backup
+ final class SubMapKeyIterator extends SubMapIterator<K>
+ implements Spliterator<K> {
+ SubMapKeyIterator(TreeMap.Entry<K,V> first,
+ TreeMap.Entry<K,V> fence) {
+ super(first, fence);
+ }
+ public K next() {
+ return nextEntry().key;
+ }
+ public void remove() {
+ removeAscending();
+ }
+ public Spliterator<K> trySplit() {
+ return null;
+ }
+ public void forEachRemaining(Consumer<? super K> action) {
+ while (hasNext())
+ action.accept(next());
+ }
+ public boolean tryAdvance(Consumer<? super K> action) {
+ if (hasNext()) {
+ action.accept(next());
+ return true;
+ }
+ return false;
+ }
+ public long estimateSize() {
+ return Long.MAX_VALUE;
+ }
+ public int characteristics() {
+ return Spliterator.DISTINCT | Spliterator.ORDERED |
+ Spliterator.SORTED;
+ }
+ public final Comparator<? super K> getComparator() {
+ return NavigableSubMap.this.comparator();
+ }
+ }
+
+ final class DescendingSubMapKeyIterator extends SubMapIterator<K>
+ implements Spliterator<K> {
DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
TreeMap.Entry<K,V> fence) {
super(last, fence);
@@ -1688,6 +1731,26 @@
public void remove() {
removeDescending();
}
+ public Spliterator<K> trySplit() {
+ return null;
+ }
+ public void forEachRemaining(Consumer<? super K> action) {
+ while (hasNext())
+ action.accept(next());
+ }
+ public boolean tryAdvance(Consumer<? super K> action) {
+ if (hasNext()) {
+ action.accept(next());
+ return true;
+ }
+ return false;
+ }
+ public long estimateSize() {
+ return Long.MAX_VALUE;
+ }
+ public int characteristics() {
+ return Spliterator.DISTINCT | Spliterator.ORDERED;
+ }
}
}
@@ -1747,6 +1810,10 @@
return new SubMapKeyIterator(absLowest(), absHighFence());
}
+ Spliterator<K> keySpliterator() {
+ return new SubMapKeyIterator(absLowest(), absHighFence());
+ }
+
Iterator<K> descendingKeyIterator() {
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
@@ -1828,6 +1895,10 @@
return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
}
+ Spliterator<K> keySpliterator() {
+ return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
+ }
+
Iterator<K> descendingKeyIterator() {
return new SubMapKeyIterator(absLowest(), absHighFence());
}
@@ -2444,4 +2515,407 @@
level++;
return level;
}
+
+ /**
+ * Currently, we support Spliterator-based versions only for the
+ * full map, in either plain of descending form, otherwise relying
+ * on defaults because size estimation for submaps would dominate
+ * costs. The type tests needed to check these for key views are
+ * not very nice but avoid disrupting existing class
+ * structures. Callers must use plain default spliterators if this
+ * returns null.
+ */
+ static <K> Spliterator<K> keySpliteratorFor(NavigableMap<K,?> m) {
+ if (m instanceof TreeMap) {
+ @SuppressWarnings("unchecked") TreeMap<K,Object> t =
+ (TreeMap<K,Object>) m;
+ return t.keySpliterator();
+ }
+ if (m instanceof DescendingSubMap) {
+ @SuppressWarnings("unchecked") DescendingSubMap<K,?> dm =
+ (DescendingSubMap<K,?>) m;
+ TreeMap<K,?> tm = dm.m;
+ if (dm == tm.descendingMap) {
+ @SuppressWarnings("unchecked") TreeMap<K,Object> t =
+ (TreeMap<K,Object>) tm;
+ return t.descendingKeySpliterator();
+ }
+ }
+ @SuppressWarnings("unchecked") NavigableSubMap<K,?> sm =
+ (NavigableSubMap<K,?>) m;
+ return sm.keySpliterator();
+ }
+
+ final Spliterator<K> keySpliterator() {
+ return new KeySpliterator<K,V>(this, null, null, 0, -1, 0);
+ }
+
+ final Spliterator<K> descendingKeySpliterator() {
+ return new DescendingKeySpliterator<K,V>(this, null, null, 0, -2, 0);
+ }
+
+ /**
+ * Base class for spliterators. Iteration starts at a given
+ * origin and continues up to but not including a given fence (or
+ * null for end). At top-level, for ascending cases, the first
+ * split uses the root as left-fence/right-origin. From there,
+ * right-hand splits replace the current fence with its left
+ * child, also serving as origin for the split-off spliterator.
+ * Left-hands are symmetric. Descending versions place the origin
+ * at the end and invert ascending split rules. This base class
+ * is non-commital about directionality, or whether the top-level
+ * spliterator covers the whole tree. This means that the actual
+ * split mechanics are located in subclasses. Some of the subclass
+ * trySplit methods are identical (except for return types), but
+ * not nicely factorable.
+ *
+ * Currently, subclass versions exist only for the full map
+ * (including descending keys via its descendingMap). Others are
+ * possible but currently not worthwhile because submaps require
+ * O(n) computations to determine size, which substantially limits
+ * potential speed-ups of using custom Spliterators versus default
+ * mechanics.
+ *
+ * To boostrap initialization, external constructors use
+ * negative size estimates: -1 for ascend, -2 for descend.
+ */
+ static class TreeMapSpliterator<K,V> {
+ final TreeMap<K,V> tree;
+ TreeMap.Entry<K,V> current; // traverser; initially first node in range
+ TreeMap.Entry<K,V> fence; // one past last, or null
+ int side; // 0: top, -1: is a left split, +1: right
+ int est; // size estimate (exact only for top-level)
+ int expectedModCount; // for CME checks
+
+ TreeMapSpliterator(TreeMap<K,V> tree,
+ TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+ int side, int est, int expectedModCount) {
+ this.tree = tree;
+ this.current = origin;
+ this.fence = fence;
+ this.side = side;
+ this.est = est;
+ this.expectedModCount = expectedModCount;
+ }
+
+ final int getEstimate() { // force initialization
+ int s; TreeMap<K,V> t;
+ if ((s = est) < 0) {
+ if ((t = tree) != null) {
+ current = (s == -1) ? t.getFirstEntry() : t.getLastEntry();
+ s = est = t.size;
+ expectedModCount = t.modCount;
+ }
+ else
+ s = est = 0;
+ }
+ return s;
+ }
+
+ public final long estimateSize() {
+ return (long)getEstimate();
+ }
+ }
+
+ static final class KeySpliterator<K,V>
+ extends TreeMapSpliterator<K,V>
+ implements Spliterator<K> {
+ KeySpliterator(TreeMap<K,V> tree,
+ TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+ int side, int est, int expectedModCount) {
+ super(tree, origin, fence, side, est, expectedModCount);
+ }
+
+ public KeySpliterator<K,V> trySplit() {
+ if (est < 0)
+ getEstimate(); // force initialization
+ int d = side;
+ TreeMap.Entry<K,V> e = current, f = fence,
+ s = ((e == null || e == f) ? null : // empty
+ (d == 0) ? tree.root : // was top
+ (d > 0) ? e.right : // was right
+ (d < 0 && f != null) ? f.left : // was left
+ null);
+ if (s != null && s != e && s != f &&
+ tree.compare(e.key, s.key) < 0) { // e not already past s
+ side = 1;
+ return new KeySpliterator<>
+ (tree, e, current = s, -1, est >>>= 1, expectedModCount);
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super K> action) {
+ if (action == null)
+ throw new NullPointerException();
+ if (est < 0)
+ getEstimate(); // force initialization
+ TreeMap.Entry<K,V> f = fence, e, p, pl;
+ if ((e = current) != null && e != f) {
+ current = f; // exhaust
+ do {
+ action.accept(e.key);
+ if ((p = e.right) != null) {
+ while ((pl = p.left) != null)
+ p = pl;
+ }
+ else {
+ while ((p = e.parent) != null && e == p.right)
+ e = p;
+ }
+ } while ((e = p) != null && e != f);
+ if (tree.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super K> action) {
+ TreeMap.Entry<K,V> e;
+ if (action == null)
+ throw new NullPointerException();
+ if (est < 0)
+ getEstimate(); // force initialization
+ if ((e = current) == null || e == fence)
+ return false;
+ current = successor(e);
+ action.accept(e.key);
+ if (tree.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+
+ public int characteristics() {
+ return (side == 0 ? Spliterator.SIZED : 0) |
+ Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
+ }
+
+ public final Comparator<? super K> getComparator() {
+ return tree.comparator;
+ }
+
+ }
+
+ static final class DescendingKeySpliterator<K,V>
+ extends TreeMapSpliterator<K,V>
+ implements Spliterator<K> {
+ DescendingKeySpliterator(TreeMap<K,V> tree,
+ TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+ int side, int est, int expectedModCount) {
+ super(tree, origin, fence, side, est, expectedModCount);
+ }
+
+ public DescendingKeySpliterator<K,V> trySplit() {
+ if (est < 0)
+ getEstimate(); // force initialization
+ int d = side;
+ TreeMap.Entry<K,V> e = current, f = fence,
+ s = ((e == null || e == f) ? null : // empty
+ (d == 0) ? tree.root : // was top
+ (d < 0) ? e.left : // was left
+ (d > 0 && f != null) ? f.right : // was right
+ null);
+ if (s != null && s != e && s != f &&
+ tree.compare(e.key, s.key) > 0) { // e not already past s
+ side = 1;
+ return new DescendingKeySpliterator<>
+ (tree, e, current = s, -1, est >>>= 1, expectedModCount);
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super K> action) {
+ if (action == null)
+ throw new NullPointerException();
+ if (est < 0)
+ getEstimate(); // force initialization
+ TreeMap.Entry<K,V> f = fence, e, p, pr;
+ if ((e = current) != null && e != f) {
+ current = f; // exhaust
+ do {
+ action.accept(e.key);
+ if ((p = e.left) != null) {
+ while ((pr = p.right) != null)
+ p = pr;
+ }
+ else {
+ while ((p = e.parent) != null && e == p.left)
+ e = p;
+ }
+ } while ((e = p) != null && e != f);
+ if (tree.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super K> action) {
+ TreeMap.Entry<K,V> e;
+ if (action == null)
+ throw new NullPointerException();
+ if (est < 0)
+ getEstimate(); // force initialization
+ if ((e = current) == null || e == fence)
+ return false;
+ current = predecessor(e);
+ action.accept(e.key);
+ if (tree.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+
+ public int characteristics() {
+ return (side == 0 ? Spliterator.SIZED : 0) |
+ Spliterator.DISTINCT | Spliterator.ORDERED;
+ }
+ }
+
+ static final class ValueSpliterator<K,V>
+ extends TreeMapSpliterator<K,V>
+ implements Spliterator<V> {
+ ValueSpliterator(TreeMap<K,V> tree,
+ TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+ int side, int est, int expectedModCount) {
+ super(tree, origin, fence, side, est, expectedModCount);
+ }
+
+ public ValueSpliterator<K,V> trySplit() {
+ if (est < 0)
+ getEstimate(); // force initialization
+ int d = side;
+ TreeMap.Entry<K,V> e = current, f = fence,
+ s = ((e == null || e == f) ? null : // empty
+ (d == 0) ? tree.root : // was top
+ (d > 0) ? e.right : // was right
+ (d < 0 && f != null) ? f.left : // was left
+ null);
+ if (s != null && s != e && s != f &&
+ tree.compare(e.key, s.key) < 0) { // e not already past s
+ side = 1;
+ return new ValueSpliterator<>
+ (tree, e, current = s, -1, est >>>= 1, expectedModCount);
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super V> action) {
+ if (action == null)
+ throw new NullPointerException();
+ if (est < 0)
+ getEstimate(); // force initialization
+ TreeMap.Entry<K,V> f = fence, e, p, pl;
+ if ((e = current) != null && e != f) {
+ current = f; // exhaust
+ do {
+ action.accept(e.value);
+ if ((p = e.right) != null) {
+ while ((pl = p.left) != null)
+ p = pl;
+ }
+ else {
+ while ((p = e.parent) != null && e == p.right)
+ e = p;
+ }
+ } while ((e = p) != null && e != f);
+ if (tree.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super V> action) {
+ TreeMap.Entry<K,V> e;
+ if (action == null)
+ throw new NullPointerException();
+ if (est < 0)
+ getEstimate(); // force initialization
+ if ((e = current) == null || e == fence)
+ return false;
+ current = successor(e);
+ action.accept(e.value);
+ if (tree.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+
+ public int characteristics() {
+ return (side == 0 ? Spliterator.SIZED : 0);
+ }
+ }
+
+ static final class EntrySpliterator<K,V>
+ extends TreeMapSpliterator<K,V>
+ implements Spliterator<Map.Entry<K,V>> {
+ EntrySpliterator(TreeMap<K,V> tree,
+ TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
+ int side, int est, int expectedModCount) {
+ super(tree, origin, fence, side, est, expectedModCount);
+ }
+
+ public EntrySpliterator<K,V> trySplit() {
+ if (est < 0)
+ getEstimate(); // force initialization
+ int d = side;
+ TreeMap.Entry<K,V> e = current, f = fence,
+ s = ((e == null || e == f) ? null : // empty
+ (d == 0) ? tree.root : // was top
+ (d > 0) ? e.right : // was right
+ (d < 0 && f != null) ? f.left : // was left
+ null);
+ if (s != null && s != e && s != f &&
+ tree.compare(e.key, s.key) < 0) { // e not already past s
+ side = 1;
+ return new EntrySpliterator<>
+ (tree, e, current = s, -1, est >>>= 1, expectedModCount);
+ }
+ return null;
+ }
+
+ public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
+ if (action == null)
+ throw new NullPointerException();
+ if (est < 0)
+ getEstimate(); // force initialization
+ TreeMap.Entry<K,V> f = fence, e, p, pl;
+ if ((e = current) != null && e != f) {
+ current = f; // exhaust
+ do {
+ action.accept(e);
+ if ((p = e.right) != null) {
+ while ((pl = p.left) != null)
+ p = pl;
+ }
+ else {
+ while ((p = e.parent) != null && e == p.right)
+ e = p;
+ }
+ } while ((e = p) != null && e != f);
+ if (tree.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ }
+ }
+
+ public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+ TreeMap.Entry<K,V> e;
+ if (action == null)
+ throw new NullPointerException();
+ if (est < 0)
+ getEstimate(); // force initialization
+ if ((e = current) == null || e == fence)
+ return false;
+ current = successor(e);
+ action.accept(e);
+ if (tree.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+
+ public int characteristics() {
+ return (side == 0 ? Spliterator.SIZED : 0) |
+ Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
+ }
+
+ @Override
+ public Comparator<? super Map.Entry<K, V>> getComparator() {
+ return tree.comparator != null ?
+ Comparators.byKey(tree.comparator) : null;
+ }
+ }
}
--- a/jdk/src/share/classes/java/util/TreeSet.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/TreeSet.java Wed Apr 17 11:34:31 2013 +0200
@@ -533,5 +533,9 @@
tm.readTreeSet(size, s, PRESENT);
}
+ public Spliterator<E> spliterator() {
+ return TreeMap.keySpliteratorFor(m);
+ }
+
private static final long serialVersionUID = -2479143000061671589L;
}
--- a/jdk/src/share/classes/java/util/Vector.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/Vector.java Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1994, 2011, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1994, 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
@@ -29,6 +29,8 @@
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
+import java.util.function.Consumer;
+
/**
* The {@code Vector} class implements a growable array of
* objects. Like an array, it contains components that can be
@@ -1155,6 +1157,28 @@
lastRet = -1;
}
+ @Override
+ public void forEachRemaining(Consumer<? super E> action) {
+ Objects.requireNonNull(action);
+ synchronized (Vector.this) {
+ final int size = Vector.this.elementCount;
+ int i = cursor;
+ if (i >= size) {
+ return;
+ }
+ final Object[] elementData = Vector.this.elementData;
+ if (i >= elementData.length) {
+ throw new ConcurrentModificationException();
+ }
+ while (i != size && modCount == expectedModCount) {
+ action.accept((E) elementData[i++]);
+ }
+ // update once at end of iteration to reduce heap write traffic
+ lastRet = cursor = i;
+ checkForComodification();
+ }
+ }
+
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
@@ -1298,4 +1322,96 @@
}
modCount++;
}
+
+ @Override
+ public Spliterator<E> spliterator() {
+ return new VectorSpliterator<>(this, null, 0, -1, 0);
+ }
+
+ /** Similar to ArrayList Spliterator */
+ static final class VectorSpliterator<E> implements Spliterator<E> {
+ private final Vector<E> list;
+ private Object[] array;
+ private int index; // current index, modified on advance/split
+ private int fence; // -1 until used; then one past last index
+ private int expectedModCount; // initialized when fence set
+
+ /** Create new spliterator covering the given range */
+ VectorSpliterator(Vector<E> list, Object[] array, int origin, int fence,
+ int expectedModCount) {
+ this.list = list;
+ this.array = array;
+ this.index = origin;
+ this.fence = fence;
+ this.expectedModCount = expectedModCount;
+ }
+
+ private int getFence() { // initialize on first use
+ int hi;
+ if ((hi = fence) < 0) {
+ synchronized(list) {
+ array = list.elementData;
+ expectedModCount = list.modCount;
+ hi = fence = list.elementCount;
+ }
+ }
+ return hi;
+ }
+
+ public Spliterator<E> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid) ? null :
+ new VectorSpliterator<E>(list, array, lo, index = mid,
+ expectedModCount);
+ }
+
+ @SuppressWarnings("unchecked")
+ public boolean tryAdvance(Consumer<? super E> action) {
+ int i;
+ if (action == null)
+ throw new NullPointerException();
+ if (getFence() > (i = index)) {
+ index = i + 1;
+ action.accept((E)array[i]);
+ if (list.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ return false;
+ }
+
+ @SuppressWarnings("unchecked")
+ public void forEachRemaining(Consumer<? super E> action) {
+ int i, hi; // hoist accesses and checks from loop
+ Vector<E> lst; Object[] a;
+ if (action == null)
+ throw new NullPointerException();
+ if ((lst = list) != null) {
+ if ((hi = fence) < 0) {
+ synchronized(lst) {
+ expectedModCount = lst.modCount;
+ a = array = lst.elementData;
+ hi = fence = lst.elementCount;
+ }
+ }
+ else
+ a = array;
+ if (a != null && (i = index) >= 0 && (index = hi) <= a.length) {
+ while (i < hi)
+ action.accept((E) a[i++]);
+ if (lst.modCount == expectedModCount)
+ return;
+ }
+ }
+ throw new ConcurrentModificationException();
+ }
+
+ public long estimateSize() {
+ return (long) (getFence() - index);
+ }
+
+ public int characteristics() {
+ return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
+ }
+ }
}
--- a/jdk/src/share/classes/java/util/WeakHashMap.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/src/share/classes/java/util/WeakHashMap.java Wed Apr 17 11:34:31 2013 +0200
@@ -1,5 +1,5 @@
/*
- * Copyright (c) 1998, 2012, Oracle and/or its affiliates. All rights reserved.
+ * Copyright (c) 1998, 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,8 +24,10 @@
*/
package java.util;
+
import java.lang.ref.WeakReference;
import java.lang.ref.ReferenceQueue;
+import java.util.function.Consumer;
/**
@@ -898,6 +900,10 @@
public void clear() {
WeakHashMap.this.clear();
}
+
+ public Spliterator<K> spliterator() {
+ return new KeySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
+ }
}
/**
@@ -934,6 +940,10 @@
public void clear() {
WeakHashMap.this.clear();
}
+
+ public Spliterator<V> spliterator() {
+ return new ValueSpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
+ }
}
/**
@@ -994,5 +1004,288 @@
public <T> T[] toArray(T[] a) {
return deepCopy().toArray(a);
}
+
+ public Spliterator<Map.Entry<K,V>> spliterator() {
+ return new EntrySpliterator<>(WeakHashMap.this, 0, -1, 0, 0);
+ }
}
+
+ /**
+ * Similar form as other hash Spliterators, but skips dead
+ * elements.
+ */
+ static class WeakHashMapSpliterator<K,V> {
+ final WeakHashMap<K,V> map;
+ WeakHashMap.Entry<K,V> current; // current node
+ int index; // current index, modified on advance/split
+ int fence; // -1 until first use; then one past last index
+ int est; // size estimate
+ int expectedModCount; // for comodification checks
+
+ WeakHashMapSpliterator(WeakHashMap<K,V> m, int origin,
+ int fence, int est,
+ int expectedModCount) {
+ this.map = m;
+ this.index = origin;
+ this.fence = fence;
+ this.est = est;
+ this.expectedModCount = expectedModCount;
+ }
+
+ final int getFence() { // initialize fence and size on first use
+ int hi;
+ if ((hi = fence) < 0) {
+ WeakHashMap<K,V> m = map;
+ est = m.size();
+ expectedModCount = m.modCount;
+ hi = fence = m.table.length;
+ }
+ return hi;
+ }
+
+ public final long estimateSize() {
+ getFence(); // force init
+ return (long) est;
+ }
+ }
+
+ static final class KeySpliterator<K,V>
+ extends WeakHashMapSpliterator<K,V>
+ implements Spliterator<K> {
+ KeySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public KeySpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid) ? null :
+ new KeySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ public void forEachRemaining(Consumer<? super K> action) {
+ int i, hi, mc;
+ if (action == null)
+ throw new NullPointerException();
+ WeakHashMap<K,V> m = map;
+ WeakHashMap.Entry<K,V>[] tab = m.table;
+ if ((hi = fence) < 0) {
+ mc = expectedModCount = m.modCount;
+ hi = fence = tab.length;
+ }
+ else
+ mc = expectedModCount;
+ if (tab.length >= hi && (i = index) >= 0 && i < hi) {
+ index = hi;
+ WeakHashMap.Entry<K,V> p = current;
+ do {
+ if (p == null)
+ p = tab[i++];
+ else {
+ Object x = p.get();
+ p = p.next;
+ if (x != null) {
+ @SuppressWarnings("unchecked") K k =
+ (K) WeakHashMap.unmaskNull(x);
+ action.accept(k);
+ }
+ }
+ } while (p != null || i < hi);
+ }
+ if (m.modCount != mc)
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean tryAdvance(Consumer<? super K> action) {
+ int hi;
+ if (action == null)
+ throw new NullPointerException();
+ WeakHashMap.Entry<K,V>[] tab = map.table;
+ if (tab.length >= (hi = getFence()) && index >= 0) {
+ while (current != null || index < hi) {
+ if (current == null)
+ current = tab[index++];
+ else {
+ Object x = current.get();
+ current = current.next;
+ if (x != null) {
+ @SuppressWarnings("unchecked") K k =
+ (K) WeakHashMap.unmaskNull(x);
+ action.accept(k);
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return Spliterator.DISTINCT;
+ }
+ }
+
+ static final class ValueSpliterator<K,V>
+ extends WeakHashMapSpliterator<K,V>
+ implements Spliterator<V> {
+ ValueSpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public ValueSpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid) ? null :
+ new ValueSpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+ public void forEachRemaining(Consumer<? super V> action) {
+ int i, hi, mc;
+ if (action == null)
+ throw new NullPointerException();
+ WeakHashMap<K,V> m = map;
+ WeakHashMap.Entry<K,V>[] tab = m.table;
+ if ((hi = fence) < 0) {
+ mc = expectedModCount = m.modCount;
+ hi = fence = tab.length;
+ }
+ else
+ mc = expectedModCount;
+ if (tab.length >= hi && (i = index) >= 0 && i < hi) {
+ index = hi;
+ WeakHashMap.Entry<K,V> p = current;
+ do {
+ if (p == null)
+ p = tab[i++];
+ else {
+ Object x = p.get();
+ V v = p.value;
+ p = p.next;
+ if (x != null)
+ action.accept(v);
+ }
+ } while (p != null || i < hi);
+ }
+ if (m.modCount != mc)
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean tryAdvance(Consumer<? super V> action) {
+ int hi;
+ if (action == null)
+ throw new NullPointerException();
+ WeakHashMap.Entry<K,V>[] tab = map.table;
+ if (tab.length >= (hi = getFence()) && index >= 0) {
+ while (current != null || index < hi) {
+ if (current == null)
+ current = tab[index++];
+ else {
+ Object x = current.get();
+ V v = current.value;
+ current = current.next;
+ if (x != null) {
+ action.accept(v);
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return 0;
+ }
+ }
+
+ static final class EntrySpliterator<K,V>
+ extends WeakHashMapSpliterator<K,V>
+ implements Spliterator<Map.Entry<K,V>> {
+ EntrySpliterator(WeakHashMap<K,V> m, int origin, int fence, int est,
+ int expectedModCount) {
+ super(m, origin, fence, est, expectedModCount);
+ }
+
+ public EntrySpliterator<K,V> trySplit() {
+ int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
+ return (lo >= mid) ? null :
+ new EntrySpliterator<K,V>(map, lo, index = mid, est >>>= 1,
+ expectedModCount);
+ }
+
+
+ public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
+ int i, hi, mc;
+ if (action == null)
+ throw new NullPointerException();
+ WeakHashMap<K,V> m = map;
+ WeakHashMap.Entry<K,V>[] tab = m.table;
+ if ((hi = fence) < 0) {
+ mc = expectedModCount = m.modCount;
+ hi = fence = tab.length;
+ }
+ else
+ mc = expectedModCount;
+ if (tab.length >= hi && (i = index) >= 0 && i < hi) {
+ index = hi;
+ WeakHashMap.Entry<K,V> p = current;
+ do {
+ if (p == null)
+ p = tab[i++];
+ else {
+ Object x = p.get();
+ V v = p.value;
+ p = p.next;
+ if (x != null) {
+ @SuppressWarnings("unchecked") K k =
+ (K) WeakHashMap.unmaskNull(x);
+ action.accept
+ (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+ }
+ }
+ } while (p != null || i < hi);
+ }
+ if (m.modCount != mc)
+ throw new ConcurrentModificationException();
+ }
+
+ public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
+ int hi;
+ if (action == null)
+ throw new NullPointerException();
+ WeakHashMap.Entry<K,V>[] tab = map.table;
+ if (tab.length >= (hi = getFence()) && index >= 0) {
+ while (current != null || index < hi) {
+ if (current == null)
+ current = tab[index++];
+ else {
+ Object x = current.get();
+ V v = current.value;
+ current = current.next;
+ if (x != null) {
+ @SuppressWarnings("unchecked") K k =
+ (K) WeakHashMap.unmaskNull(x);
+ action.accept
+ (new AbstractMap.SimpleImmutableEntry<K,V>(k, v));
+ if (map.modCount != expectedModCount)
+ throw new ConcurrentModificationException();
+ return true;
+ }
+ }
+ }
+ }
+ return false;
+ }
+
+ public int characteristics() {
+ return Spliterator.DISTINCT;
+ }
+ }
+
}
--- a/jdk/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java Wed Apr 17 14:39:04 2013 -0400
+++ b/jdk/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java Wed Apr 17 11:34:31 2013 +0200
@@ -184,6 +184,8 @@
@Override
public boolean tryAdvance(Consumer<? super Integer> action) {
+ if (action == null)
+ throw new NullPointerException();
if (it.hasNext()) {
action.accept(it.next());
return true;
@@ -193,7 +195,7 @@
}
}
}
- db.add("new Spliterators.AbstractAdvancingSpliterator()",
+ db.add("new Spliterators.AbstractSpliterator()",
() -> new SpliteratorFromIterator(exp.iterator(), exp.size()));
// Collections
@@ -370,7 +372,28 @@
db.addCollection(c -> Collections.singletonList(exp.get(0)));
}
- // @@@ Collections.synchronized/unmodifiable/checked wrappers
+ // Collections.synchronized/unmodifiable/checked wrappers
+ db.addCollection(Collections::unmodifiableCollection);
+ db.addCollection(c -> Collections.unmodifiableSet(new HashSet<>(c)));
+ db.addCollection(c -> Collections.unmodifiableSortedSet(new TreeSet<>(c)));
+ db.addList(c -> Collections.unmodifiableList(new ArrayList<>(c)));
+ db.addMap(Collections::unmodifiableMap);
+ db.addMap(m -> Collections.unmodifiableSortedMap(new TreeMap<>(m)));
+
+ db.addCollection(Collections::synchronizedCollection);
+ db.addCollection(c -> Collections.synchronizedSet(new HashSet<>(c)));
+ db.addCollection(c -> Collections.synchronizedSortedSet(new TreeSet<>(c)));
+ db.addList(c -> Collections.synchronizedList(new ArrayList<>(c)));
+ db.addMap(Collections::synchronizedMap);
+ db.addMap(m -> Collections.synchronizedSortedMap(new TreeMap<>(m)));
+
+ db.addCollection(c -> Collections.checkedCollection(c, Integer.class));
+ db.addCollection(c -> Collections.checkedQueue(new ArrayDeque<>(c), Integer.class));
+ db.addCollection(c -> Collections.checkedSet(new HashSet<>(c), Integer.class));
+ db.addCollection(c -> Collections.checkedSortedSet(new TreeSet<>(c), Integer.class));
+ db.addList(c -> Collections.checkedList(new ArrayList<>(c), Integer.class));
+ db.addMap(c -> Collections.checkedMap(c, Integer.class, Integer.class));
+ db.addMap(m -> Collections.checkedSortedMap(new TreeMap<>(m), Integer.class, Integer.class));
// Maps
@@ -402,6 +425,13 @@
@Test(dataProvider = "Spliterator<Integer>")
@SuppressWarnings({"unchecked", "rawtypes"})
+ public void testNullPointerException(String description, Collection exp, Supplier<Spliterator> s) {
+ executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining(null));
+ executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance(null));
+ }
+
+ @Test(dataProvider = "Spliterator<Integer>")
+ @SuppressWarnings({"unchecked", "rawtypes"})
public void testForEach(String description, Collection exp, Supplier<Spliterator> s) {
testForEach(exp, s, (Consumer<Object> b) -> b);
}
@@ -507,6 +537,8 @@
@Override
public boolean tryAdvance(IntConsumer action) {
+ if (action == null)
+ throw new NullPointerException();
if (index < a.length) {
action.accept(a[index++]);
return true;
@@ -553,6 +585,12 @@
}
@Test(dataProvider = "Spliterator.OfInt")
+ public void testIntNullPointerException(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
+ executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining((IntConsumer) null));
+ executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance((IntConsumer) null));
+ }
+
+ @Test(dataProvider = "Spliterator.OfInt")
public void testIntForEach(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) {
testForEach(exp, s, intBoxingConsumer());
}
@@ -652,6 +690,8 @@
@Override
public boolean tryAdvance(LongConsumer action) {
+ if (action == null)
+ throw new NullPointerException();
if (index < a.length) {
action.accept(a[index++]);
return true;
@@ -705,6 +745,12 @@
}
@Test(dataProvider = "Spliterator.OfLong")
+ public void testLongNullPointerException(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
+ executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining((LongConsumer) null));
+ executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance((LongConsumer) null));
+ }
+
+ @Test(dataProvider = "Spliterator.OfLong")
public void testLongForEach(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) {
testForEach(exp, s, longBoxingConsumer());
}
@@ -804,6 +850,8 @@
@Override
public boolean tryAdvance(DoubleConsumer action) {
+ if (action == null)
+ throw new NullPointerException();
if (index < a.length) {
action.accept(a[index++]);
return true;
@@ -857,6 +905,12 @@
}
@Test(dataProvider = "Spliterator.OfDouble")
+ public void testDoubleNullPointerException(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
+ executeAndCatch(NullPointerException.class, () -> s.get().forEachRemaining((DoubleConsumer) null));
+ executeAndCatch(NullPointerException.class, () -> s.get().tryAdvance((DoubleConsumer) null));
+ }
+
+ @Test(dataProvider = "Spliterator.OfDouble")
public void testDoubleForEach(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) {
testForEach(exp, s, doubleBoxingConsumer());
}
@@ -1057,8 +1111,8 @@
}
private static <T, S extends Spliterator<T>> void visit(int depth, int curLevel,
- List<T> dest, S spliterator, UnaryOperator<Consumer<T>> boxingAdapter,
- int rootCharacteristics, boolean useTryAdvance) {
+ List<T> dest, S spliterator, UnaryOperator<Consumer<T>> boxingAdapter,
+ int rootCharacteristics, boolean useTryAdvance) {
if (curLevel < depth) {
long beforeSize = spliterator.getExactSizeIfKnown();
Spliterator<T> split = spliterator.trySplit();
@@ -1187,13 +1241,13 @@
assertTrue(leftSplit.estimateSize() < parentEstimateSize,
String.format("Left split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
assertTrue(parentAndRightSplit.estimateSize() < parentEstimateSize,
- String.format("Right split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
+ String.format("Right split size estimate %d >= parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
}
else {
assertTrue(leftSplit.estimateSize() <= parentEstimateSize,
- String.format("Left split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
+ String.format("Left split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
assertTrue(parentAndRightSplit.estimateSize() <= parentEstimateSize,
- String.format("Right split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
+ String.format("Right split size estimate %d > parent split size estimate %d", leftSplit.estimateSize(), parentEstimateSize));
}
long leftSize = leftSplit.getExactSizeIfKnown();
@@ -1254,4 +1308,22 @@
});
return result;
}
+
+ private void executeAndCatch(Class<? extends Exception> expected, Runnable r) {
+ Exception caught = null;
+ try {
+ r.run();
+ }
+ catch (Exception e) {
+ caught = e;
+ }
+
+ assertNotNull(caught,
+ String.format("No Exception was thrown, expected an Exception of %s to be thrown",
+ expected.getName()));
+ assertTrue(expected.isInstance(caught),
+ String.format("Exception thrown %s not an instance of %s",
+ caught.getClass().getName(), expected.getName()));
+ }
+
}