Mercurial > hg > openjdk > jigsaw > jdk
changeset 7355:674880648db4
8010096: Initial java.util.Spliterator putback
Reviewed-by: mduigou, alanb, chegar, darcy
Contributed-by: Paul Sandoz <paul.sandoz@oracle.com>, Brian Goetz <brian.goetz@oracle.com>, Doug Lea <dl@cs.oswego.edu>
line wrap: on
line diff
--- a/src/share/classes/com/sun/tools/jdi/EventSetImpl.java Wed Apr 17 12:31:34 2013 -0700 +++ b/src/share/classes/com/sun/tools/jdi/EventSetImpl.java Tue Apr 16 13:51:53 2013 -0400 @@ -851,6 +851,11 @@ } } + @Override + public Spliterator<Event> spliterator() { + return Spliterators.spliterator(this, Spliterator.DISTINCT); + } + /* below make this unmodifiable */ public boolean add(Event o){
--- a/src/share/classes/java/lang/Iterable.java Wed Apr 17 12:31:34 2013 -0700 +++ b/src/share/classes/java/lang/Iterable.java Tue Apr 16 13:51:53 2013 -0400 @@ -22,26 +22,55 @@ * or visit www.oracle.com if you need additional information or have any * questions. */ - package java.lang; import java.util.Iterator; +import java.util.Objects; +import java.util.function.Consumer; /** * Implementing this interface allows an object to be the target of - * the "foreach" statement. + * the "for-each loop" statement. See + * <strong> + * <a href="{@docRoot}/../technotes/guides/language/foreach.html">For-each Loop</a> + * </strong> * * @param <T> the type of elements returned by the iterator * * @since 1.5 + * @jls 14.14.2 The enhanced for statement */ @FunctionalInterface public interface Iterable<T> { - /** - * Returns an iterator over a set of elements of type T. + * Returns an iterator over elements of type {@code T}. * * @return an Iterator. */ Iterator<T> iterator(); + + /** + * Performs the given action on the contents of the {@code Iterable}, in the + * order elements occur when iterating, until all elements have been + * processed or the action throws an exception. Errors or runtime + * exceptions thrown by the action are relayed to the caller. + * + * @implSpec + * <p>The default implementation behaves as if: + * <pre>{@code + * for (T t : this) + * action.accept(t); + * }</pre> + * + * @param action The action to be performed for each element + * @throws NullPointerException if the specified action is null + * @since 1.8 + */ + default void forEach(Consumer<? super T> action) { + Objects.requireNonNull(action); + for (T t : this) { + action.accept(t); + } + } } +
--- a/src/share/classes/java/util/Arrays.java Wed Apr 17 12:31:34 2013 -0700 +++ b/src/share/classes/java/util/Arrays.java Tue Apr 16 13:51:53 2013 -0400 @@ -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 @@ -3518,6 +3518,11 @@ public boolean contains(Object o) { return indexOf(o) != -1; } + + @Override + public Spliterator<E> spliterator() { + return Spliterators.spliterator(a, Spliterator.ORDERED); + } } /** @@ -4300,4 +4305,167 @@ buf.append(']'); dejaVu.remove(a); } + + /** + * Creates a {@link Spliterator} covering all of the specified array. + * + * <p>The spliterator reports {@link Spliterator#SIZED}, + * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and + * {@link Spliterator#IMMUTABLE}. + * + * @param <T> Type of elements + * @param array The array, assumed to be unmodified during use + * @return A spliterator from the array + * @throws NullPointerException if the specified array is {@code null} + * @since 1.8 + */ + public static <T> Spliterator<T> spliterator(T[] array) { + return Spliterators.spliterator(array, + Spliterator.ORDERED | Spliterator.IMMUTABLE); + } + + /** + * Creates a {@link Spliterator} covering the specified range of the + * specified array. + * + * <p>The spliterator reports {@link Spliterator#SIZED}, + * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and + * {@link Spliterator#IMMUTABLE}. + * + * @param <T> Type of elements + * @param array The array, assumed to be unmodified during use + * @param fromIndex The least index (inclusive) to cover + * @param toIndex One past the greatest index to cover + * @return A spliterator from the array + * @throws NullPointerException if the specified array is {@code null} + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex} is negative, + * {@code toIndex} is less than {@code fromIndex}, or + * {@code toIndex} is greater than the array size + * @since 1.8 + */ + public static <T> Spliterator<T> spliterator(T[] array, int fromIndex, int toIndex) { + return Spliterators.spliterator(array, fromIndex, toIndex, + Spliterator.ORDERED | Spliterator.IMMUTABLE); + } + + /** + * Creates a {@link Spliterator.OfInt} covering all of the specified array. + * + * <p>The spliterator reports {@link Spliterator#SIZED}, + * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and + * {@link Spliterator#IMMUTABLE}. + * + * @param array The array, assumed to be unmodified during use + * @return A spliterator from the array + * @throws NullPointerException if the specified array is {@code null} + * @since 1.8 + */ + public static Spliterator.OfInt spliterator(int[] array) { + return Spliterators.spliterator(array, + Spliterator.ORDERED | Spliterator.IMMUTABLE); + } + + /** + * Creates a {@link Spliterator.OfInt} covering the specified range of the + * specified array. + * + * <p>The spliterator reports {@link Spliterator#SIZED}, + * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and + * {@link Spliterator#IMMUTABLE}. + * + * @param array The array, assumed to be unmodified during use + * @param fromIndex The least index (inclusive) to cover + * @param toIndex One past the greatest index to cover + * @return A spliterator from the array + * @throws NullPointerException if the specified array is {@code null} + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex} is negative, + * {@code toIndex} is less than {@code fromIndex}, or + * {@code toIndex} is greater than the array size + * @since 1.8 + */ + public static Spliterator.OfInt spliterator(int[] array, int fromIndex, int toIndex) { + return Spliterators.spliterator(array, fromIndex, toIndex, + Spliterator.ORDERED | Spliterator.IMMUTABLE); + } + + /** + * Creates a {@link Spliterator.OfLong} covering all of the specified array. + * + * <p>The spliterator reports {@link Spliterator#SIZED}, + * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and + * {@link Spliterator#IMMUTABLE}. + * + * @param array The array, assumed to be unmodified during use + * @return A spliterator from the array + * @throws NullPointerException if the specified array is {@code null} + * @since 1.8 + */ + public static Spliterator.OfLong spliterator(long[] array) { + return Spliterators.spliterator(array, + Spliterator.ORDERED | Spliterator.IMMUTABLE); + } + + /** + * Creates a {@link Spliterator.OfLong} covering the specified range of the + * specified array. + * + * <p>The spliterator reports {@link Spliterator#SIZED}, + * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and + * {@link Spliterator#IMMUTABLE}. + * + * @param array The array, assumed to be unmodified during use + * @param fromIndex The least index (inclusive) to cover + * @param toIndex One past the greatest index to cover + * @return A spliterator from the array + * @throws NullPointerException if the specified array is {@code null} + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex} is negative, + * {@code toIndex} is less than {@code fromIndex}, or + * {@code toIndex} is greater than the array size + * @since 1.8 + */ + public static Spliterator.OfLong spliterator(long[] array, int fromIndex, int toIndex) { + return Spliterators.spliterator(array, fromIndex, toIndex, + Spliterator.ORDERED | Spliterator.IMMUTABLE); + } + + /** + * Creates a {@link Spliterator.OfDouble} covering all of the specified + * array. + * + * <p>The spliterator reports {@link Spliterator#SIZED}, + * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and + * {@link Spliterator#IMMUTABLE}. + * + * @param array The array, assumed to be unmodified during use + * @return A spliterator from the array + * @throws NullPointerException if the specified array is {@code null} + * @since 1.8 + */ + public static Spliterator.OfDouble spliterator(double[] array) { + return Spliterators.spliterator(array, + Spliterator.ORDERED | Spliterator.IMMUTABLE); + } + + /** + * Creates a {@link Spliterator.OfDouble} covering the specified range of + * the specified array. + * + * <p>The spliterator reports {@link Spliterator#SIZED}, + * {@link Spliterator#SUBSIZED}, {@link Spliterator#ORDERED}, and + * {@link Spliterator#IMMUTABLE}. + * + * @param array The array, assumed to be unmodified during use + * @param fromIndex The least index (inclusive) to cover + * @param toIndex One past the greatest index to cover + * @return A spliterator from the array + * @throws NullPointerException if the specified array is {@code null} + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex} is negative, + * {@code toIndex} is less than {@code fromIndex}, or + * {@code toIndex} is greater than the array size + * @since 1.8 + */ + public static Spliterator.OfDouble spliterator(double[] array, int fromIndex, int toIndex) { + return Spliterators.spliterator(array, fromIndex, toIndex, + Spliterator.ORDERED | Spliterator.IMMUTABLE); + } }
--- a/src/share/classes/java/util/Collection.java Wed Apr 17 12:31:34 2013 -0700 +++ b/src/share/classes/java/util/Collection.java Tue Apr 16 13:51:53 2013 -0400 @@ -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 @@ -104,6 +104,12 @@ * <a href="{@docRoot}/../technotes/guides/collections/index.html"> * Java Collections Framework</a>. * + * @implSpec + * The default method implementations (inherited or otherwise) do not apply any + * synchronization protocol. If a {@code Collection} implementation has a + * specific synchronization protocol, then it must override default + * implementations to apply that protocol. + * * @param <E> the type of elements in this collection * * @author Josh Bloch @@ -453,4 +459,28 @@ * @see Object#equals(Object) */ int hashCode(); + + /** + * Creates a {@link Spliterator} over the elements in this collection. + * + * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}. + * Implementations should document the reporting of additional + * characteristic values. + * + * @implSpec + * The default implementation creates a + * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator + * from the collections's {@code Iterator}. The spliterator inherits the + * <em>fail-fast</em> properties of the collection's iterator. + * + * @implNote + * The created {@code Spliterator} additionally reports + * {@link Spliterator#SUBSIZED}. + * + * @return a {@code Spliterator} over the elements in this collection + * @since 1.8 + */ + default Spliterator<E> spliterator() { + return Spliterators.spliterator(this, 0); + } }
--- a/src/share/classes/java/util/Iterator.java Wed Apr 17 12:31:34 2013 -0700 +++ b/src/share/classes/java/util/Iterator.java Tue Apr 16 13:51:53 2013 -0400 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1997, 2010, 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; + /** * An iterator over a collection. {@code Iterator} takes the place of * {@link Enumeration} in the Java Collections Framework. Iterators @@ -75,6 +77,10 @@ * iteration is in progress in any way other than by calling this * method. * + * @implSpec + * The default implementation throws an instance of + * {@link UnsupportedOperationException} and performs no other action. + * * @throws UnsupportedOperationException if the {@code remove} * operation is not supported by this iterator * @@ -83,5 +89,30 @@ * been called after the last call to the {@code next} * method */ - void remove(); + default void remove() { + throw new UnsupportedOperationException("remove"); + } + + /** + * Performs the given action for each remaining element, in the order + * elements occur when iterating, until all elements have been processed or + * the action throws an exception. Errors or runtime exceptions thrown by + * the action are relayed to the caller. + * + * @implSpec + * <p>The default implementation behaves as if: + * <pre>{@code + * while (hasNext()) + * action.accept(next()); + * }</pre> + * + * @param action The action to be performed for each element + * @throws NullPointerException if the specified action is null + * @since 1.8 + */ + default void forEachRemaining(Consumer<? super E> action) { + Objects.requireNonNull(action); + while (hasNext()) + action.accept(next()); + } }
--- a/src/share/classes/java/util/List.java Wed Apr 17 12:31:34 2013 -0700 +++ b/src/share/classes/java/util/List.java Tue Apr 16 13:51:53 2013 -0400 @@ -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 @@ -597,4 +597,30 @@ * fromIndex > toIndex</tt>) */ List<E> subList(int fromIndex, int toIndex); + + /** + * Creates a {@link Spliterator} over the elements in this list. + * + * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and + * {@link Spliterator#ORDERED}. Implementations should document the + * reporting of additional characteristic values. + * + * @implSpec + * The default implementation creates a + * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator + * from the list's {@code Iterator}. The spliterator inherits the + * <em>fail-fast</em> properties of the collection's iterator. + * + * @implNote + * The created {@code Spliterator} additionally reports + * {@link Spliterator#SUBSIZED}. + * + * @return a {@code Spliterator} over the elements in this list + * @since 1.8 + */ + @Override + default Spliterator<E> spliterator() { + return Spliterators.spliterator(this, Spliterator.ORDERED); + } } +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/classes/java/util/PrimitiveIterator.java Tue Apr 16 13:51:53 2013 -0400 @@ -0,0 +1,274 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package java.util; + +import java.util.function.Consumer; +import java.util.function.DoubleConsumer; +import java.util.function.IntConsumer; +import java.util.function.LongConsumer; + +/** + * A base type for primitive specializations of {@code Iterator}. Specialized + * subtypes are provided for {@link OfInt int}, {@link OfLong long}, and + * {@link OfDouble double} values. + * + * <p>The specialized subtype default implementations of {@link Iterator#next} + * and {@link Iterator#forEachRemaining(java.util.function.Consumer)} box + * primitive values to instances of their corresponding wrapper class. Such + * boxing may offset any advantages gained when using the primitive + * specializations. To avoid boxing, the corresponding primitive-based methods + * should be used. For example, {@link PrimitiveIterator.OfInt#nextInt()} and + * {@link PrimitiveIterator.OfInt#forEachRemaining(java.util.function.IntConsumer)} + * should be used in preference to {@link PrimitiveIterator.OfInt#next()} and + * {@link PrimitiveIterator.OfInt#forEachRemaining(java.util.function.Consumer)}. + * + * <p>Iteration of primitive values using boxing-based methods + * {@link Iterator#next next()} and + * {@link Iterator#forEachRemaining(java.util.function.Consumer) forEachRemaining()}, + * does not affect the order in which the values, transformed to boxed values, + * are encountered. + * + * @implNote + * If the boolean system property {@code org.openjdk.java.util.stream.tripwire} + * is set to {@code true} then diagnostic warnings are reported if boxing of + * primitive values occur when operating on primitive subtype specializations. + * + * @param <T> the boxed type of the primitive type + * @since 1.8 + */ +public interface PrimitiveIterator<T> extends Iterator<T> { + + /** + * An Iterator specialized for {@code int} values. + * @since 1.8 + */ + public static interface OfInt extends PrimitiveIterator<Integer> { + + /** + * Returns the next {@code int} element in the iteration. + * + * @return the next {@code int} element in the iteration + * @throws NoSuchElementException if the iteration has no more elements + */ + int nextInt(); + + /** + * Performs the given action for each remaining element, in the order + * elements occur when iterating, until all elements have been processed + * or the action throws an exception. Errors or runtime exceptions + * thrown by the action are relayed to the caller. + * + * @implSpec + * <p>The default implementation behaves as if: + * <pre>{@code + * while (hasNext()) + * action.accept(nextInt()); + * }</pre> + * + * @param action The action to be performed for each element + * @throws NullPointerException if the specified action is null + */ + default void forEachRemaining(IntConsumer action) { + while (hasNext()) + action.accept(nextInt()); + } + + /** + * {@inheritDoc} + * @implSpec + * The default implementation boxes the result of calling + * {@link #nextInt()}, and returns that boxed result. + */ + @Override + default Integer next() { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), "{0} calling PrimitiveIterator.OfInt.nextInt()"); + return nextInt(); + } + + /** + * {@inheritDoc} + * @implSpec + * If the action is an instance of {@code IntConsumer} then it is cast + * to {@code IntConsumer} and passed to {@link #forEachRemaining}; + * otherwise the action is adapted to an instance of + * {@code IntConsumer}, by boxing the argument of {@code IntConsumer}, + * and then passed to {@link #forEachRemaining}. + */ + @Override + default void forEachRemaining(Consumer<? super Integer> action) { + if (action instanceof IntConsumer) { + forEachRemaining((IntConsumer) action); + } + else { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), "{0} calling PrimitiveIterator.OfInt.forEachRemainingInt(action::accept)"); + forEachRemaining((IntConsumer) action::accept); + } + } + + } + + /** + * An Iterator specialized for {@code long} values. + * @since 1.8 + */ + public static interface OfLong extends PrimitiveIterator<Long> { + + /** + * Returns the next {@code long} element in the iteration. + * + * @return the next {@code long} element in the iteration + * @throws NoSuchElementException if the iteration has no more elements + */ + long nextLong(); + + /** + * Performs the given action for each remaining element, in the order + * elements occur when iterating, until all elements have been processed + * or the action throws an exception. Errors or runtime exceptions + * thrown by the action are relayed to the caller. + * + * @implSpec + * <p>The default implementation behaves as if: + * <pre>{@code + * while (hasNext()) + * action.accept(nextLong()); + * }</pre> + * + * @param action The action to be performed for each element + * @throws NullPointerException if the specified action is null + */ + default void forEachRemaining(LongConsumer action) { + while (hasNext()) + action.accept(nextLong()); + } + + /** + * {@inheritDoc} + * @implSpec + * The default implementation boxes the result of calling + * {@link #nextLong()}, and returns that boxed result. + */ + @Override + default Long next() { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), "{0} calling PrimitiveIterator.OfLong.nextLong()"); + return nextLong(); + } + + /** + * {@inheritDoc} + * @implSpec + * If the action is an instance of {@code LongConsumer} then it is cast + * to {@code LongConsumer} and passed to {@link #forEachRemaining}; + * otherwise the action is adapted to an instance of + * {@code LongConsumer}, by boxing the argument of {@code LongConsumer}, + * and then passed to {@link #forEachRemaining}. + */ + @Override + default void forEachRemaining(Consumer<? super Long> action) { + if (action instanceof LongConsumer) { + forEachRemaining((LongConsumer) action); + } + else { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), "{0} calling PrimitiveIterator.OfLong.forEachRemainingLong(action::accept)"); + forEachRemaining((LongConsumer) action::accept); + } + } + } + + /** + * An Iterator specialized for {@code double} values. + * @since 1.8 + */ + public static interface OfDouble extends PrimitiveIterator<Double> { + + /** + * Returns the next {@code double} element in the iteration. + * + * @return the next {@code double} element in the iteration + * @throws NoSuchElementException if the iteration has no more elements + */ + double nextDouble(); + + /** + * Performs the given action for each remaining element, in the order + * elements occur when iterating, until all elements have been processed + * or the action throws an exception. Errors or runtime exceptions + * thrown by the action are relayed to the caller. + * + * @implSpec + * <p>The default implementation behaves as if: + * <pre>{@code + * while (hasNext()) + * action.accept(nextDouble()); + * }</pre> + * + * @param action The action to be performed for each element + * @throws NullPointerException if the specified action is null + */ + default void forEachRemaining(DoubleConsumer action) { + while (hasNext()) + action.accept(nextDouble()); + } + + /** + * {@inheritDoc} + * @implSpec + * The default implementation boxes the result of calling + * {@link #nextDouble()}, and returns that boxed result. + */ + @Override + default Double next() { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), "{0} calling PrimitiveIterator.OfDouble.nextLong()"); + return nextDouble(); + } + + /** + * {@inheritDoc} + * @implSpec + * If the action is an instance of {@code DoubleConsumer} then it is + * cast to {@code DoubleConsumer} and passed to + * {@link #forEachRemaining}; otherwise the action is adapted to + * an instance of {@code DoubleConsumer}, by boxing the argument of + * {@code DoubleConsumer}, and then passed to + * {@link #forEachRemaining}. + */ + @Override + default void forEachRemaining(Consumer<? super Double> action) { + if (action instanceof DoubleConsumer) { + forEachRemaining((DoubleConsumer) action); + } + else { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), "{0} calling PrimitiveIterator.OfDouble.forEachRemainingDouble(action::accept)"); + forEachRemaining((DoubleConsumer) action::accept); + } + } + } +}
--- a/src/share/classes/java/util/Set.java Wed Apr 17 12:31:34 2013 -0700 +++ b/src/share/classes/java/util/Set.java Tue Apr 16 13:51:53 2013 -0400 @@ -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 @@ -382,4 +382,29 @@ * @see Set#equals(Object) */ int hashCode(); + + /** + * Creates a {@code Spliterator} over the elements in this set. + * + * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and + * {@link Spliterator#DISTINCT}. Implementations should document the + * reporting of additional characteristic values. + * + * @implSpec + * The default implementation creates a + * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator + * from the set's {@code Iterator}. The spliterator inherits the + * <em>fail-fast</em> properties of the collection's iterator. + * + * @implNote + * The created {@code Spliterator} additionally reports + * {@link Spliterator#SUBSIZED}. + * + * @return a {@code Spliterator} over the elements in this set + * @since 1.8 + */ + @Override + default Spliterator<E> spliterator() { + return Spliterators.spliterator(this, Spliterator.DISTINCT); + } }
--- a/src/share/classes/java/util/SortedSet.java Wed Apr 17 12:31:34 2013 -0700 +++ b/src/share/classes/java/util/SortedSet.java Tue Apr 16 13:51:53 2013 -0400 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1998, 2006, 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 @@ -219,4 +219,43 @@ * @throws NoSuchElementException if this set is empty */ E last(); + + /** + * Creates a {@code Spliterator} over the elements in this sorted set. + * + * <p>The {@code Spliterator} reports {@link Spliterator#SIZED}, + * {@link Spliterator#DISTINCT}, {@link Spliterator#SORTED} and + * {@link Spliterator#ORDERED}. Implementations should document the + * reporting of additional characteristic values. + * + * <p>The spliterator's comparator (see + * {@link java.util.Spliterator#getComparator()}) must be {@code null} if + * the sorted set's comparator (see {@link #comparator()}) is {@code null}. + * Otherwise, the spliterator's comparator must be the same as or impose the + * same total ordering as the sorted set's comparator. + * + * @implSpec + * The default implementation creates a + * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator + * from the sorted set's {@code Iterator}. The spliterator inherits the + * <em>fail-fast</em> properties of the collection's iterator. The + * spliterator's comparator is the same as the sorted set's comparator. + * + * @implNote + * The created {@code Spliterator} additionally reports + * {@link Spliterator#SUBSIZED}. + * + * @return a {@code Spliterator} over the elements in this sorted set + * @since 1.8 + */ + @Override + default Spliterator<E> spliterator() { + return new Spliterators.IteratorSpliterator<E>( + this, Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED) { + @Override + public Comparator<? super E> getComparator() { + return SortedSet.this.comparator(); + } + }; + } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/classes/java/util/Spliterator.java Tue Apr 16 13:51:53 2013 -0400 @@ -0,0 +1,835 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package java.util; + +import java.util.function.Consumer; +import java.util.function.DoubleConsumer; +import java.util.function.IntConsumer; +import java.util.function.LongConsumer; + +/** + * An object for traversing and partitioning elements of a source. The source + * of elements covered by a Spliterator could be, for example, an array, a + * {@link Collection}, an IO channel, or a generator function. + * + * <p>A Spliterator may traverse elements individually ({@link + * #tryAdvance tryAdvance()}) or sequentially in bulk + * ({@link #forEachRemaining forEachRemaining()}). + * + * <p>A Spliterator may also partition off some of its elements (using + * {@link #trySplit}) as another Spliterator, to be used in + * possibly-parallel operations. Operations using a Spliterator that + * cannot split, or does so in a highly imbalanced or inefficient + * manner, are unlikely to benefit from parallelism. Traversal + * and splitting exhaust elements; each Spliterator is useful for only a single + * bulk computation. + * + * <p>A Spliterator also reports a set of {@link #characteristics()} of its + * structure, source, and elements from among {@link #ORDERED}, + * {@link #DISTINCT}, {@link #SORTED}, {@link #SIZED}, {@link #NONNULL}, + * {@link #IMMUTABLE}, {@link #CONCURRENT}, and {@link #SUBSIZED}. These may + * be employed by Spliterator clients to control, specialize or simplify + * computation. For example, a Spliterator for a {@link Collection} would + * report {@code SIZED}, a Spliterator for a {@link Set} would report + * {@code DISTINCT}, and a Spliterator for a {@link SortedSet} would also + * report {@code SORTED}. Characteristics are reported as a simple unioned bit + * set. + * + * Some characteristics additionally constrain method behavior; for example if + * {@code ORDERED}, traversal methods must conform to their documented ordering. + * New characteristics may be defined in the future, so implementors should not + * assign meanings to unlisted values. + * + * <p><a name="binding"/>A Spliterator that does not report {@code IMMUTABLE} or + * {@code CONCURRENT} is expected to have a documented policy concerning: + * when the spliterator <em>binds</em> to the element source; and detection of + * structural interference of the element source detected after binding. A + * <em>late-binding</em> Spliterator binds to the source of elements at the + * point of first traversal, first split, or first query for estimated size, + * rather than at the time the Spliterator is created. A Spliterator that is + * not <em>late-binding</em> binds to the source of elements at the point of + * construction or first invocation of any method. Modifications made to the + * source prior to binding are reflected when the Spliterator is traversed. + * After binding a Spliterator should, on a best-effort basis, throw + * {@link ConcurrentModificationException} if structural interference is + * detected. Spliterators that do this are called <em>fail-fast</em>. + * + * <p>Spliterators can provide an estimate of the number of remaining elements + * via the {@link #estimateSize} method. Ideally, as reflected in characteristic + * {@link #SIZED}, this value corresponds exactly to the number of elements + * that would be encountered in a successful traversal. However, even when not + * exactly known, an estimated value value may still be useful to operations + * being performed on the source, such as helping to determine whether it is + * preferable to split further or traverse the remaining elements sequentially. + * + * <p>Despite their obvious utility in parallel algorithms, spliterators are not + * expected to be thread-safe; instead, implementations of parallel algorithms + * using spliterators should ensure that the spliterator is only used by one + * thread at a time. This is generally easy to attain via <em>serial + * thread-confinement</em>, which often is a natural consequence of typical + * parallel algorithms that work by recursive decomposition. A thread calling + * {@link #trySplit()} may hand over the returned Spliterator to another thread, + * which in turn may traverse or further split that Spliterator. The behaviour + * of splitting and traversal is undefined if two or more threads operate + * concurrently on the same spliterator. If the original thread hands a + * spliterator off to another thread for processing, it is best if that handoff + * occurs before any elements are consumed with {@link #tryAdvance(Consumer) + * tryAdvance()}, as certain guarantees (such as the accuracy of + * {@link #estimateSize()} for {@code SIZED} spliterators) are only valid before + * traversal has begun. + * + * <p>Primitive subtype specializations of {@code Spliterator} are provided for + * {@link OfInt int}, {@link OfLong long}, and {@link OfDouble double} values. + * The subtype default implementations of + * {@link Spliterator#tryAdvance(java.util.function.Consumer)} + * and {@link Spliterator#forEachRemaining(java.util.function.Consumer)} box + * primitive values to instances of their corresponding wrapper class. Such + * boxing may undermine any performance advantages gained by using the primitive + * specializations. To avoid boxing, the corresponding primitive-based methods + * should be used. For example, + * {@link Spliterator.OfInt#tryAdvance(java.util.function.IntConsumer)} + * and {@link Spliterator.OfInt#forEachRemaining(java.util.function.IntConsumer)} + * should be used in preference to + * {@link Spliterator.OfInt#tryAdvance(java.util.function.Consumer)} and + * {@link Spliterator.OfInt#forEachRemaining(java.util.function.Consumer)}. + * Traversal of primitive values using boxing-based methods + * {@link #tryAdvance tryAdvance()} and + * {@link #forEachRemaining(java.util.function.Consumer) forEachRemaining()} + * does not affect the order in which the values, transformed to boxed values, + * are encountered. + * + * @apiNote + * <p>Spliterators, like {@code Iterators}s, are for traversing the elements of + * a source. The {@code Spliterator} API was designed to support efficient + * parallel traversal in addition to sequential traversal, by supporting + * decomposition as well as single-element iteration. In addition, the + * protocol for accessing elements via a Spliterator is designed to impose + * smaller per-element overhead than {@code Iterator}, and to avoid the inherent + * race involved in having separate methods for {@code hasNext()} and + * {@code next()}. + * + * <p>For mutable sources, arbitrary and non-deterministic behavior may occur if + * the source is structurally interfered with (elements added, replaced, or + * removed) between the time that the Spliterator binds to its data source and + * the end of traversal. For example, such interference will produce arbitrary, + * non-deterministic results when using the {@code java.util.stream} framework. + * + * <p>Structural interference of a source can be managed in the following ways + * (in approximate order of decreasing desirability): + * <ul> + * <li>The source cannot be structurally interfered with. + * </br>For example, an instance of + * {@link java.util.concurrent.CopyOnWriteArrayList} is an immutable source. + * A Spliterator created from the source reports a characteristic of + * {@code IMMUTABLE}.</li> + * <li>The source manages concurrent modifications. + * </br>For example, a key set of a {@link java.util.concurrent.ConcurrentHashMap} + * is a concurrent source. A Spliterator created from the source reports a + * characteristic of {@code CONCURRENT}.</li> + * <li>The mutable source provides a late-binding and fail-fast Spliterator. + * </br>Late binding narrows the window during which interference can affect + * the calculation; fail-fast detects, on a best-effort basis, that structural + * interference has occurred after traversal has commenced and throws + * {@link ConcurrentModificationException}. For example, {@link ArrayList}, + * and many other non-concurrent {@code Collection} classes in the JDK, provide + * a late-binding, fail-fast spliterator.</li> + * <li>The mutable source provides a non-late-binding but fail-fast Spliterator. + * </br>The source increases the likelihood of throwing + * {@code ConcurrentModificationException} since the window of potential + * interference is larger.</li> + * <li>The mutable source provides a late-binding and non-fail-fast Spliterator. + * </br>The source risks arbitrary, non-deterministic behavior after traversal + * has commenced since interference is not detected. + * </li> + * <li>The mutable source provides a non-late-binding and non-fail-fast + * Spliterator. + * </br>The source increases the risk of arbitrary, non-deterministic behavior + * since non-detected interference may occur after construction. + * </li> + * </ul> + * + * <p><b>Example.</b> Here is a class (not a very useful one, except + * for illustration) that maintains an array in which the actual data + * are held in even locations, and unrelated tag data are held in odd + * locations. Its Spliterator ignores the tags. + * + * <pre> {@code + * class TaggedArray<T> { + * private final Object[] elements; // immutable after construction + * TaggedArray(T[] data, Object[] tags) { + * int size = data.length; + * if (tags.length != size) throw new IllegalArgumentException(); + * this.elements = new Object[2 * size]; + * for (int i = 0, j = 0; i < size; ++i) { + * elements[j++] = data[i]; + * elements[j++] = tags[i]; + * } + * } + * + * public Spliterator<T> spliterator() { + * return new TaggedArraySpliterator<>(elements, 0, elements.length); + * } + * + * static class TaggedArraySpliterator<T> implements Spliterator<T> { + * private final Object[] array; + * private int origin; // current index, advanced on split or traversal + * private final int fence; // one past the greatest index + * + * TaggedArraySpliterator(Object[] array, int origin, int fence) { + * this.array = array; this.origin = origin; this.fence = fence; + * } + * + * public void forEachRemaining(Consumer<? super T> action) { + * for (; origin < fence; origin += 2) + * action.accept((T) array[origin]); + * } + * + * public boolean tryAdvance(Consumer<? super T> action) { + * if (origin < fence) { + * action.accept((T) array[origin]); + * origin += 2; + * return true; + * } + * else // cannot advance + * return false; + * } + * + * public Spliterator<T> trySplit() { + * int lo = origin; // divide range in half + * int mid = ((lo + fence) >>> 1) & ~1; // force midpoint to be even + * if (lo < mid) { // split out left half + * origin = mid; // reset this Spliterator's origin + * return new TaggedArraySpliterator<>(array, lo, mid); + * } + * else // too small to split + * return null; + * } + * + * public long estimateSize() { + * return (long)((fence - origin) / 2); + * } + * + * public int characteristics() { + * return ORDERED | SIZED | IMMUTABLE | SUBSIZED; + * } + * } + * }}</pre> + * + * <p>As an example how a parallel computation framework, such as the + * {@code java.util.stream} package, would use Spliterator in a parallel + * computation, here is one way to implement an associated parallel forEach, + * that illustrates the primary usage idiom of splitting off subtasks until + * the estimated amount of work is small enough to perform + * sequentially. Here we assume that the order of processing across + * subtasks doesn't matter; different (forked) tasks may further split + * and process elements concurrently in undetermined order. This + * example uses a {@link java.util.concurrent.CountedCompleter}; + * similar usages apply to other parallel task constructions. + * + * <pre>{@code + * static <T> void parEach(TaggedArray<T> a, Consumer<T> action) { + * Spliterator<T> s = a.spliterator(); + * long targetBatchSize = s.estimateSize() / (ForkJoinPool.getCommonPoolParallelism() * 8); + * new ParEach(null, s, action, targetBatchSize).invoke(); + * } + * + * static class ParEach<T> extends CountedCompleter<Void> { + * final Spliterator<T> spliterator; + * final Consumer<T> action; + * final long targetBatchSize; + * + * ParEach(ParEach<T> parent, Spliterator<T> spliterator, + * Consumer<T> action, long targetBatchSize) { + * super(parent); + * this.spliterator = spliterator; this.action = action; + * this.targetBatchSize = targetBatchSize; + * } + * + * public void compute() { + * Spliterator<T> sub; + * while (spliterator.estimateSize() > targetBatchSize && + * (sub = spliterator.trySplit()) != null) { + * addToPendingCount(1); + * new ParEach<>(this, sub, action, targetBatchSize).fork(); + * } + * spliterator.forEachRemaining(action); + * propagateCompletion(); + * } + * }}</pre> + * + * @implNote + * If the boolean system property {@code org.openjdk.java.util.stream.tripwire} + * is set to {@code true} then diagnostic warnings are reported if boxing of + * primitive values occur when operating on primitive subtype specializations. + * + * @see Collection + * @since 1.8 + */ +public interface Spliterator<T> { + /** + * If a remaining element exists, performs the given action on it, + * returning {@code true}; else returns {@code false}. If this + * Spliterator is {@link #ORDERED} the action is performed on the + * next element in encounter order. Exceptions thrown by the + * action are relayed to the caller. + * + * @param action The action + * @return {@code false} if no remaining elements existed + * upon entry to this method, else {@code true}. + * @throws NullPointerException if the specified action is null + */ + boolean tryAdvance(Consumer<? super T> action); + + /** + * Performs the given action for each remaining element, sequentially in + * the current thread, until all elements have been processed or the action + * throws an exception. If this Spliterator is {@link #ORDERED}, actions + * are performed in encounter order. Exceptions thrown by the action + * are relayed to the caller. + * + * @implSpec + * The default implementation repeatedly invokes {@link #tryAdvance} until + * it returns {@code false}. It should be overridden whenever possible. + * + * @param action The action + * @throws NullPointerException if the specified action is null + */ + default void forEachRemaining(Consumer<? super T> action) { + do { } while (tryAdvance(action)); + } + + /** + * If this spliterator can be partitioned, returns a Spliterator + * covering elements, that will, upon return from this method, not + * be covered by this Spliterator. + * + * <p>If this Spliterator is {@link #ORDERED}, the returned Spliterator + * must cover a strict prefix of the elements. + * + * <p>Unless this Spliterator covers an infinite number of elements, + * repeated calls to {@code trySplit()} must eventually return {@code null}. + * Upon non-null return: + * <ul> + * <li>the value reported for {@code estimateSize()} before splitting, + * if not already zero or {@code Long.MAX_VALUE}, must, after splitting, be + * greater than {@code estimateSize()} for this and the returned + * Spliterator; and</li> + * <li>if this Spliterator is {@code SUBSIZED}, then {@code estimateSize()} + * for this spliterator before splitting must be equal to the sum of + * {@code estimateSize()} for this and the returned Spliterator after + * splitting.</li> + * </ul> + * + * <p>This method may return {@code null} for any reason, + * including emptiness, inability to split after traversal has + * commenced, data structure constraints, and efficiency + * considerations. + * + * @apiNote + * An ideal {@code trySplit} method efficiently (without + * traversal) divides its elements exactly in half, allowing + * balanced parallel computation. Many departures from this ideal + * remain highly effective; for example, only approximately + * splitting an approximately balanced tree, or for a tree in + * which leaf nodes may contain either one or two elements, + * failing to further split these nodes. However, large + * deviations in balance and/or overly inefficient {@code + * trySplit} mechanics typically result in poor parallel + * performance. + * + * @return a {@code Spliterator} covering some portion of the + * elements, or {@code null} if this spliterator cannot be split + */ + Spliterator<T> trySplit(); + + /** + * Returns an estimate of the number of elements that would be + * encountered by a {@link #forEachRemaining} traversal, or returns {@link + * Long#MAX_VALUE} if infinite, unknown, or too expensive to compute. + * + * <p>If this Spliterator is {@link #SIZED} and has not yet been partially + * traversed or split, or this Spliterator is {@link #SUBSIZED} and has + * not yet been partially traversed, this estimate must be an accurate + * count of elements that would be encountered by a complete traversal. + * Otherwise, this estimate may be arbitrarily inaccurate, but must decrease + * as specified across invocations of {@link #trySplit}. + * + * @apiNote + * Even an inexact estimate is often useful and inexpensive to compute. + * For example, a sub-spliterator of an approximately balanced binary tree + * may return a value that estimates the number of elements to be half of + * that of its parent; if the root Spliterator does not maintain an + * accurate count, it could estimate size to be the power of two + * corresponding to its maximum depth. + * + * @return the estimated size, or {@code Long.MAX_VALUE} if infinite, + * unknown, or too expensive to compute. + */ + long estimateSize(); + + /** + * Convenience method that returns {@link #estimateSize()} if this + * Spliterator is {@link #SIZED}, else {@code -1}. + * @implSpec + * The default returns the result of {@code estimateSize()} if the + * Spliterator reports a characteristic of {@code SIZED}, and {@code -1} + * otherwise. + * + * @return the exact size, if known, else {@code -1}. + */ + default long getExactSizeIfKnown() { + return (characteristics() & SIZED) == 0 ? -1L : estimateSize(); + } + + /** + * Returns a set of characteristics of this Spliterator and its + * elements. The result is represented as ORed values from {@link + * #ORDERED}, {@link #DISTINCT}, {@link #SORTED}, {@link #SIZED}, + * {@link #NONNULL}, {@link #IMMUTABLE}, {@link #CONCURRENT}, + * {@link #SUBSIZED}. Repeated calls to {@code characteristics()} on + * a given spliterator should always return the same result. + * + * <p>If a Spliterator reports an inconsistent set of + * characteristics (either those returned from a single invocation + * or across multiple invocations), no guarantees can be made + * about any computation using this Spliterator. + * + * @return a representation of characteristics + */ + int characteristics(); + + /** + * Returns {@code true} if this Spliterator's {@link + * #characteristics} contain all of the given characteristics. + * + * @implSpec + * The default implementation returns true if the corresponding bits + * of the given characteristics are set. + * + * @return {@code true} if all the specified characteristics are present, + * else {@code false} + */ + default boolean hasCharacteristics(int characteristics) { + return (characteristics() & characteristics) == characteristics; + } + + /** + * If this Spliterator's source is {@link #SORTED} by a {@link Comparator}, + * returns that {@code Comparator}. If the source is {@code SORTED} in + * {@linkplain Comparable natural order, returns {@code null}. Otherwise, + * if the source is not {@code SORTED}, throws {@link IllegalStateException}. + * + * @implSpec + * The default implementation always throws {@link IllegalStateException}. + * + * @return a Comparator, or {@code null} if the elements are sorted in the + * natural order. + * @throws IllegalStateException if the spliterator does not report + * a characteristic of {@code SORTED}. + */ + default Comparator<? super T> getComparator() { + throw new IllegalStateException(); + } + + /** + * Characteristic value signifying that an encounter order is defined for + * elements. If so, this Spliterator guarantees that method + * {@link #trySplit} splits a strict prefix of elements, that method + * {@link #tryAdvance} steps by one element in prefix order, and that + * {@link #forEachRemaining} performs actions in encounter order. + * + * <p>A {@link Collection} has an encounter order if the corresponding + * {@link Collection#iterator} documents an order. If so, the encounter + * order is the same as the documented order. Otherwise, a collection does + * not have an encounter order. + * + * @apiNote Encounter order is guaranteed to be ascending index order for + * any {@link List}. But no order is guaranteed for hash-based collections + * such as {@link HashSet}. Clients of a Spliterator that reports + * {@code ORDERED} are expected to preserve ordering constraints in + * non-commutative parallel computations. + */ + public static final int ORDERED = 0x00000010; + + /** + * Characteristic value signifying that, for each pair of + * encountered elements {@code x, y}, {@code !x.equals(y)}. This + * applies for example, to a Spliterator based on a {@link Set}. + */ + public static final int DISTINCT = 0x00000001; + + /** + * Characteristic value signifying that encounter order follows a defined + * sort order. If so, method {@link #getComparator()} returns the associated + * Comparator, or {@code null} if all elements are {@link Comparable} and + * are sorted by their natural ordering. + * + * <p>A Spliterator that reports {@code SORTED} must also report + * {@code ORDERED}. + * + * @apiNote The spliterators for {@code Collection} classes in the JDK that + * implement {@link NavigableSet} or {@link SortedSet} report {@code SORTED}. + */ + public static final int SORTED = 0x00000004; + + /** + * Characteristic value signifying that the value returned from + * {@code estimateSize()} prior to traversal or splitting represents a + * finite size that, in the absence of structural source modification, + * represents an exact count of the number of elements that would be + * encountered by a complete traversal. + * + * @apiNote Most Spliterators for Collections, that cover all elements of a + * {@code Collection} report this characteristic. Sub-spliterators, such as + * those for {@link HashSet}, that cover a sub-set of elements and + * approximate their reported size do not. + */ + public static final int SIZED = 0x00000040; + + /** + * Characteristic value signifying that the source guarantees that + * encountered elements will not be {@code null}. (This applies, + * for example, to most concurrent collections, queues, and maps.) + */ + public static final int NONNULL = 0x00000100; + + /** + * Characteristic value signifying that the element source cannot be + * structurally modified; that is, elements cannot be added, replaced, or + * removed, so such changes cannot occur during traversal. A Spliterator + * that does not report {@code IMMUTABLE} or {@code CONCURRENT} is expected + * to have a documented policy (for example throwing + * {@link ConcurrentModificationException}) concerning structural + * interference detected during traversal. + */ + public static final int IMMUTABLE = 0x00000400; + + /** + * Characteristic value signifying that the element source may be safely + * concurrently modified (allowing additions, replacements, and/or removals) + * by multiple threads without external synchronization. If so, the + * Spliterator is expected to have a documented policy concerning the impact + * of modifications during traversal. + * + * <p>A top-level Spliterator should not report {@code CONCURRENT} and + * {@code SIZED}, since the finite size, if known, may change if the source + * is concurrently modified during traversal. Such a Spliterator is + * inconsistent and no guarantees can be made about any computation using + * that Spliterator. Sub-spliterators may report {@code SIZED} if the + * sub-split size is known and additions or removals to the source are not + * reflected when traversing. + * + * @apiNote Most concurrent collections maintain a consistency policy + * guaranteeing accuracy with respect to elements present at the point of + * Spliterator construction, but possibly not reflecting subsequent + * additions or removals. + */ + public static final int CONCURRENT = 0x00001000; + + /** + * Characteristic value signifying that all Spliterators resulting from + * {@code trySplit()} will be both {@link #SIZED} and {@link #SUBSIZED}. + * (This means that all child Spliterators, whether direct or indirect, will + * be {@code SIZED}.) + * + * <p>A Spliterator that does not report {@code SIZED} as required by + * {@code SUBSIZED} is inconsistent and no guarantees can be made about any + * computation using that Spliterator. + * + * @apiNote Some spliterators, such as the top-level spliterator for an + * approximately balanced binary tree, will report {@code SIZED} but not + * {@code SUBSIZED}, since it is common to know the size of the entire tree + * but not the exact sizes of subtrees. + */ + public static final int SUBSIZED = 0x00004000; + + /** + * A Spliterator specialized for {@code int} values. + * @since 1.8 + */ + public interface OfInt extends Spliterator<Integer> { + + @Override + OfInt trySplit(); + + /** + * If a remaining element exists, performs the given action on it, + * returning {@code true}; else returns {@code false}. If this + * Spliterator is {@link #ORDERED} the action is performed on the + * next element in encounter order. Exceptions thrown by the + * action are relayed to the caller. + * + * @param action The action + * @return {@code false} if no remaining elements existed + * upon entry to this method, else {@code true}. + * @throws NullPointerException if the specified action is null + */ + boolean tryAdvance(IntConsumer action); + + /** + * Performs the given action for each remaining element, sequentially in + * the current thread, until all elements have been processed or the + * action throws an exception. If this Spliterator is {@link #ORDERED}, + * actions are performed in encounter order. Exceptions thrown by the + * action are relayed to the caller. + * + * @implSpec + * The default implementation repeatedly invokes {@link #tryAdvance} + * until it returns {@code false}. It should be overridden whenever + * possible. + * + * @param action The action + * @throws NullPointerException if the specified action is null + */ + default void forEachRemaining(IntConsumer action) { + do { } while (tryAdvance(action)); + } + + /** + * {@inheritDoc} + * @implSpec + * If the action is an instance of {@code IntConsumer} then it is cast + * to {@code IntConsumer} and passed to + * {@link #tryAdvance(java.util.function.IntConsumer)}; otherwise + * the action is adapted to an instance of {@code IntConsumer}, by + * boxing the argument of {@code IntConsumer}, and then passed to + * {@link #tryAdvance(java.util.function.IntConsumer)}. + */ + @Override + default boolean tryAdvance(Consumer<? super Integer> action) { + if (action instanceof IntConsumer) { + return tryAdvance((IntConsumer) action); + } + else { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), + "{0} calling Spliterator.OfInt.tryAdvance((IntConsumer) action::accept)"); + return tryAdvance((IntConsumer) action::accept); + } + } + + /** + * {@inheritDoc} + * @implSpec + * If the action is an instance of {@code IntConsumer} then it is cast + * to {@code IntConsumer} and passed to + * {@link #forEachRemaining(java.util.function.IntConsumer)}; otherwise + * the action is adapted to an instance of {@code IntConsumer}, by + * boxing the argument of {@code IntConsumer}, and then passed to + * {@link #forEachRemaining(java.util.function.IntConsumer)}. + */ + @Override + default void forEachRemaining(Consumer<? super Integer> action) { + if (action instanceof IntConsumer) { + forEachRemaining((IntConsumer) action); + } + else { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), + "{0} calling Spliterator.OfInt.forEachRemaining((IntConsumer) action::accept)"); + forEachRemaining((IntConsumer) action::accept); + } + } + } + + /** + * A Spliterator specialized for {@code long} values. + * @since 1.8 + */ + public interface OfLong extends Spliterator<Long> { + + @Override + OfLong trySplit(); + + /** + * If a remaining element exists, performs the given action on it, + * returning {@code true}; else returns {@code false}. If this + * Spliterator is {@link #ORDERED} the action is performed on the + * next element in encounter order. Exceptions thrown by the + * action are relayed to the caller. + * + * @param action The action + * @return {@code false} if no remaining elements existed + * upon entry to this method, else {@code true}. + * @throws NullPointerException if the specified action is null + */ + boolean tryAdvance(LongConsumer action); + + /** + * Performs the given action for each remaining element, sequentially in + * the current thread, until all elements have been processed or the + * action throws an exception. If this Spliterator is {@link #ORDERED}, + * actions are performed in encounter order. Exceptions thrown by the + * action are relayed to the caller. + * + * @implSpec + * The default implementation repeatedly invokes {@link #tryAdvance} + * until it returns {@code false}. It should be overridden whenever + * possible. + * + * @param action The action + * @throws NullPointerException if the specified action is null + */ + default void forEachRemaining(LongConsumer action) { + do { } while (tryAdvance(action)); + } + + /** + * {@inheritDoc} + * @implSpec + * If the action is an instance of {@code LongConsumer} then it is cast + * to {@code LongConsumer} and passed to + * {@link #tryAdvance(java.util.function.LongConsumer)}; otherwise + * the action is adapted to an instance of {@code LongConsumer}, by + * boxing the argument of {@code LongConsumer}, and then passed to + * {@link #tryAdvance(java.util.function.LongConsumer)}. + */ + @Override + default boolean tryAdvance(Consumer<? super Long> action) { + if (action instanceof LongConsumer) { + return tryAdvance((LongConsumer) action); + } + else { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), + "{0} calling Spliterator.OfLong.tryAdvance((LongConsumer) action::accept)"); + return tryAdvance((LongConsumer) action::accept); + } + } + + /** + * {@inheritDoc} + * @implSpec + * If the action is an instance of {@code LongConsumer} then it is cast + * to {@code LongConsumer} and passed to + * {@link #forEachRemaining(java.util.function.LongConsumer)}; otherwise + * the action is adapted to an instance of {@code LongConsumer}, by + * boxing the argument of {@code LongConsumer}, and then passed to + * {@link #forEachRemaining(java.util.function.LongConsumer)}. + */ + @Override + default void forEachRemaining(Consumer<? super Long> action) { + if (action instanceof LongConsumer) { + forEachRemaining((LongConsumer) action); + } + else { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), + "{0} calling Spliterator.OfLong.forEachRemaining((LongConsumer) action::accept)"); + forEachRemaining((LongConsumer) action::accept); + } + } + } + + /** + * A Spliterator specialized for {@code double} values. + * @since 1.8 + */ + public interface OfDouble extends Spliterator<Double> { + + @Override + OfDouble trySplit(); + + /** + * If a remaining element exists, performs the given action on it, + * returning {@code true}; else returns {@code false}. If this + * Spliterator is {@link #ORDERED} the action is performed on the + * next element in encounter order. Exceptions thrown by the + * action are relayed to the caller. + * + * @param action The action + * @return {@code false} if no remaining elements existed + * upon entry to this method, else {@code true}. + * @throws NullPointerException if the specified action is null + */ + boolean tryAdvance(DoubleConsumer action); + + /** + * Performs the given action for each remaining element, sequentially in + * the current thread, until all elements have been processed or the + * action throws an exception. If this Spliterator is {@link #ORDERED}, + * actions are performed in encounter order. Exceptions thrown by the + * action are relayed to the caller. + * + * @implSpec + * The default implementation repeatedly invokes {@link #tryAdvance} + * until it returns {@code false}. It should be overridden whenever + * possible. + * + * @param action The action + * @throws NullPointerException if the specified action is null + */ + default void forEachRemaining(DoubleConsumer action) { + do { } while (tryAdvance(action)); + } + + /** + * {@inheritDoc} + * @implSpec + * If the action is an instance of {@code DoubleConsumer} then it is + * cast to {@code DoubleConsumer} and passed to + * {@link #tryAdvance(java.util.function.DoubleConsumer)}; otherwise + * the action is adapted to an instance of {@code DoubleConsumer}, by + * boxing the argument of {@code DoubleConsumer}, and then passed to + * {@link #tryAdvance(java.util.function.DoubleConsumer)}. + */ + @Override + default boolean tryAdvance(Consumer<? super Double> action) { + if (action instanceof DoubleConsumer) { + return tryAdvance((DoubleConsumer) action); + } + else { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), + "{0} calling Spliterator.OfDouble.tryAdvance((DoubleConsumer) action::accept)"); + return tryAdvance((DoubleConsumer) action::accept); + } + } + + /** + * {@inheritDoc} + * @implSpec + * If the action is an instance of {@code DoubleConsumer} then it is + * cast to {@code DoubleConsumer} and passed to + * {@link #forEachRemaining(java.util.function.DoubleConsumer)}; + * otherwise the action is adapted to an instance of + * {@code DoubleConsumer}, by boxing the argument of + * {@code DoubleConsumer}, and then passed to + * {@link #forEachRemaining(java.util.function.DoubleConsumer)}. + */ + @Override + default void forEachRemaining(Consumer<? super Double> action) { + if (action instanceof DoubleConsumer) { + forEachRemaining((DoubleConsumer) action); + } + else { + if (Tripwire.ENABLED) + Tripwire.trip(getClass(), + "{0} calling Spliterator.OfDouble.forEachRemaining((DoubleConsumer) action::accept)"); + forEachRemaining((DoubleConsumer) action::accept); + } + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/classes/java/util/Spliterators.java Tue Apr 16 13:51:53 2013 -0400 @@ -0,0 +1,2154 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package java.util; + +import java.util.function.Consumer; +import java.util.function.DoubleConsumer; +import java.util.function.IntConsumer; +import java.util.function.LongConsumer; + +/** + * Static classes and methods for operating on or creating instances of + * {@link Spliterator} and its primitive specializations + * {@link Spliterator.OfInt}, {@link Spliterator.OfLong}, and + * {@link Spliterator.OfDouble}. + * + * @see Spliterator + * @since 1.8 + */ +public final class Spliterators { + + // Suppresses default constructor, ensuring non-instantiability. + private Spliterators() {} + + // Empty spliterators + + /** + * Creates an empty {@code Spliterator} + * + * <p>The empty spliterator reports {@link Spliterator#SIZED} and + * {@link Spliterator#SUBSIZED}. Calls to + * {@link java.util.Spliterator#trySplit()} always return {@code null}. + * + * @param <T> Type of elements + * @return An empty spliterator + */ + @SuppressWarnings("unchecked") + public static <T> Spliterator<T> emptySpliterator() { + return (Spliterator<T>) EMPTY_SPLITERATOR; + } + + private static final Spliterator<Object> EMPTY_SPLITERATOR = + new EmptySpliterator.OfRef<>(); + + /** + * Creates an empty {@code Spliterator.OfInt} + * + * <p>The empty spliterator reports {@link Spliterator#SIZED} and + * {@link Spliterator#SUBSIZED}. Calls to + * {@link java.util.Spliterator#trySplit()} always return {@code null}. + * + * @return An empty spliterator + */ + public static Spliterator.OfInt emptyIntSpliterator() { + return EMPTY_INT_SPLITERATOR; + } + + private static final Spliterator.OfInt EMPTY_INT_SPLITERATOR = + new EmptySpliterator.OfInt(); + + /** + * Creates an empty {@code Spliterator.OfLong} + * + * <p>The empty spliterator reports {@link Spliterator#SIZED} and + * {@link Spliterator#SUBSIZED}. Calls to + * {@link java.util.Spliterator#trySplit()} always return {@code null}. + * + * @return An empty spliterator + */ + public static Spliterator.OfLong emptyLongSpliterator() { + return EMPTY_LONG_SPLITERATOR; + } + + private static final Spliterator.OfLong EMPTY_LONG_SPLITERATOR = + new EmptySpliterator.OfLong(); + + /** + * Creates an empty {@code Spliterator.OfDouble} + * + * <p>The empty spliterator reports {@link Spliterator#SIZED} and + * {@link Spliterator#SUBSIZED}. Calls to + * {@link java.util.Spliterator#trySplit()} always return {@code null}. + * + * @return An empty spliterator + */ + public static Spliterator.OfDouble emptyDoubleSpliterator() { + return EMPTY_DOUBLE_SPLITERATOR; + } + + private static final Spliterator.OfDouble EMPTY_DOUBLE_SPLITERATOR = + new EmptySpliterator.OfDouble(); + + // Array-based spliterators + + /** + * Creates a {@code Spliterator} covering the elements of a given array, + * using a customized set of spliterator characteristics. + * + * <p>This method is provided as an implementation convenience for + * Spliterators which store portions of their elements in arrays, and need + * fine control over Spliterator characteristics. Most other situations in + * which a Spliterator for an array is needed should use + * {@link Arrays#spliterator(Object[])}. + * + * <p>The returned spliterator always reports the characteristics + * {@code SIZED} and {@code SUBSIZED}. The caller may provide additional + * characteristics for the spliterator to report; it is common to + * additionally specify {@code IMMUTABLE} and {@code ORDERED}. + * + * @param <T> Type of elements + * @param array The array, assumed to be unmodified during use + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator for an array + * @throws NullPointerException if the given array is {@code null} + * @see Arrays#spliterator(Object[]) + */ + public static <T> Spliterator<T> spliterator(Object[] array, + int additionalCharacteristics) { + return new ArraySpliterator<>(Objects.requireNonNull(array), + additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator} covering a range of elements of a given + * array, using a customized set of spliterator characteristics. + * + * <p>This method is provided as an implementation convenience for + * Spliterators which store portions of their elements in arrays, and need + * fine control over Spliterator characteristics. Most other situations in + * which a Spliterator for an array is needed should use + * {@link Arrays#spliterator(Object[])}. + * + * <p>The returned spliterator always reports the characteristics + * {@code SIZED} and {@code SUBSIZED}. The caller may provide additional + * characteristics for the spliterator to report; it is common to + * additionally specify {@code IMMUTABLE} and {@code ORDERED}. + * + * @param <T> Type of elements + * @param array The array, assumed to be unmodified during use + * @param fromIndex The least index (inclusive) to cover + * @param toIndex One past the greatest index to cover + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator for an array + * @throws NullPointerException if the given array is {@code null} + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex} is negative, + * {@code toIndex} is less than {@code fromIndex}, or + * {@code toIndex} is greater than the array size + * @see Arrays#spliterator(Object[], int, int) + */ + public static <T> Spliterator<T> spliterator(Object[] array, int fromIndex, int toIndex, + int additionalCharacteristics) { + checkFromToBounds(Objects.requireNonNull(array).length, fromIndex, toIndex); + return new ArraySpliterator<>(array, fromIndex, toIndex, additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator.OfInt} covering the elements of a given array, + * using a customized set of spliterator characteristics. + * + * <p>This method is provided as an implementation convenience for + * Spliterators which store portions of their elements in arrays, and need + * fine control over Spliterator characteristics. Most other situations in + * which a Spliterator for an array is needed should use + * {@link Arrays#spliterator(int[])}. + * + * <p>The returned spliterator always reports the characteristics + * {@code SIZED} and {@code SUBSIZED}. The caller may provide additional + * characteristics for the spliterator to report; it is common to + * additionally specify {@code IMMUTABLE} and {@code ORDERED}. + * + * @param array The array, assumed to be unmodified during use + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator for an array + * @throws NullPointerException if the given array is {@code null} + * @see Arrays#spliterator(int[]) + */ + public static Spliterator.OfInt spliterator(int[] array, + int additionalCharacteristics) { + return new IntArraySpliterator(Objects.requireNonNull(array), additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator.OfInt} covering a range of elements of a + * given array, using a customized set of spliterator characteristics. + * + * <p>This method is provided as an implementation convenience for + * Spliterators which store portions of their elements in arrays, and need + * fine control over Spliterator characteristics. Most other situations in + * which a Spliterator for an array is needed should use + * {@link Arrays#spliterator(int[], int, int)}. + * + * <p>The returned spliterator always reports the characteristics + * {@code SIZED} and {@code SUBSIZED}. The caller may provide additional + * characteristics for the spliterator to report; it is common to + * additionally specify {@code IMMUTABLE} and {@code ORDERED}. + * + * @param array The array, assumed to be unmodified during use + * @param fromIndex The least index (inclusive) to cover + * @param toIndex One past the greatest index to cover + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator for an array + * @throws NullPointerException if the given array is {@code null} + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex} is negative, + * {@code toIndex} is less than {@code fromIndex}, or + * {@code toIndex} is greater than the array size + * @see Arrays#spliterator(int[], int, int) + */ + public static Spliterator.OfInt spliterator(int[] array, int fromIndex, int toIndex, + int additionalCharacteristics) { + checkFromToBounds(Objects.requireNonNull(array).length, fromIndex, toIndex); + return new IntArraySpliterator(array, fromIndex, toIndex, additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator.OfLong} covering the elements of a given array, + * using a customized set of spliterator characteristics. + * + * <p>This method is provided as an implementation convenience for + * Spliterators which store portions of their elements in arrays, and need + * fine control over Spliterator characteristics. Most other situations in + * which a Spliterator for an array is needed should use + * {@link Arrays#spliterator(long[])}. + * + * <p>The returned spliterator always reports the characteristics + * {@code SIZED} and {@code SUBSIZED}. The caller may provide additional + * characteristics for the spliterator to report; it is common to + * additionally specify {@code IMMUTABLE} and {@code ORDERED}. + * + * @param array The array, assumed to be unmodified during use + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator for an array + * @throws NullPointerException if the given array is {@code null} + * @see Arrays#spliterator(long[]) + */ + public static Spliterator.OfLong spliterator(long[] array, + int additionalCharacteristics) { + return new LongArraySpliterator(Objects.requireNonNull(array), additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator.OfLong} covering a range of elements of a + * given array, using a customized set of spliterator characteristics. + * + * <p>This method is provided as an implementation convenience for + * Spliterators which store portions of their elements in arrays, and need + * fine control over Spliterator characteristics. Most other situations in + * which a Spliterator for an array is needed should use + * {@link Arrays#spliterator(long[], int, int)}. + * + * <p>The returned spliterator always reports the characteristics + * {@code SIZED} and {@code SUBSIZED}. The caller may provide additional + * characteristics for the spliterator to report. (For example, if it is + * known the array will not be further modified, specify {@code IMMUTABLE}; + * if the array data is considered to have an an encounter order, specify + * {@code ORDERED}). The method {@link Arrays#spliterator(long[], int, int)} can + * often be used instead, which returns a spliterator that reports + * {@code SIZED}, {@code SUBSIZED}, {@code IMMUTABLE}, and {@code ORDERED}. + * + * @param array The array, assumed to be unmodified during use + * @param fromIndex The least index (inclusive) to cover + * @param toIndex One past the greatest index to cover + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator for an array + * @throws NullPointerException if the given array is {@code null} + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex} is negative, + * {@code toIndex} is less than {@code fromIndex}, or + * {@code toIndex} is greater than the array size + * @see Arrays#spliterator(long[], int, int) + */ + public static Spliterator.OfLong spliterator(long[] array, int fromIndex, int toIndex, + int additionalCharacteristics) { + checkFromToBounds(Objects.requireNonNull(array).length, fromIndex, toIndex); + return new LongArraySpliterator(array, fromIndex, toIndex, additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator.OfDouble} covering the elements of a given array, + * using a customized set of spliterator characteristics. + * + * <p>This method is provided as an implementation convenience for + * Spliterators which store portions of their elements in arrays, and need + * fine control over Spliterator characteristics. Most other situations in + * which a Spliterator for an array is needed should use + * {@link Arrays#spliterator(double[])}. + * + * <p>The returned spliterator always reports the characteristics + * {@code SIZED} and {@code SUBSIZED}. The caller may provide additional + * characteristics for the spliterator to report; it is common to + * additionally specify {@code IMMUTABLE} and {@code ORDERED}. + * + * @param array The array, assumed to be unmodified during use + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator for an array + * @throws NullPointerException if the given array is {@code null} + * @see Arrays#spliterator(double[]) + */ + public static Spliterator.OfDouble spliterator(double[] array, + int additionalCharacteristics) { + return new DoubleArraySpliterator(Objects.requireNonNull(array), additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator.OfDouble} covering a range of elements of a + * given array, using a customized set of spliterator characteristics. + * + * <p>This method is provided as an implementation convenience for + * Spliterators which store portions of their elements in arrays, and need + * fine control over Spliterator characteristics. Most other situations in + * which a Spliterator for an array is needed should use + * {@link Arrays#spliterator(double[], int, int)}. + * + * <p>The returned spliterator always reports the characteristics + * {@code SIZED} and {@code SUBSIZED}. The caller may provide additional + * characteristics for the spliterator to report. (For example, if it is + * known the array will not be further modified, specify {@code IMMUTABLE}; + * if the array data is considered to have an an encounter order, specify + * {@code ORDERED}). The method {@link Arrays#spliterator(long[], int, int)} can + * often be used instead, which returns a spliterator that reports + * {@code SIZED}, {@code SUBSIZED}, {@code IMMUTABLE}, and {@code ORDERED}. + * + * @param array The array, assumed to be unmodified during use + * @param fromIndex The least index (inclusive) to cover + * @param toIndex One past the greatest index to cover + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator for an array + * @throws NullPointerException if the given array is {@code null} + * @throws ArrayIndexOutOfBoundsException if {@code fromIndex} is negative, + * {@code toIndex} is less than {@code fromIndex}, or + * {@code toIndex} is greater than the array size + * @see Arrays#spliterator(double[], int, int) + */ + public static Spliterator.OfDouble spliterator(double[] array, int fromIndex, int toIndex, + int additionalCharacteristics) { + checkFromToBounds(Objects.requireNonNull(array).length, fromIndex, toIndex); + return new DoubleArraySpliterator(array, fromIndex, toIndex, additionalCharacteristics); + } + + /** + * Validate inclusive start index and exclusive end index against the length + * of an array. + * @param arrayLength The length of the array + * @param origin The inclusive start index + * @param fence The exclusive end index + * @throws ArrayIndexOutOfBoundsException if the start index is greater than + * the end index, if the start index is negative, or the end index is + * greater than the array length + */ + private static void checkFromToBounds(int arrayLength, int origin, int fence) { + if (origin > fence) { + throw new IllegalArgumentException( + "origin(" + origin + ") > fence(" + fence + ")"); + } + if (origin < 0) { + throw new ArrayIndexOutOfBoundsException(origin); + } + if (fence > arrayLength) { + throw new ArrayIndexOutOfBoundsException(fence); + } + } + + // Iterator-based spliterators + + /** + * Creates a {@code Spliterator} using the given collection's + * {@link java.util.Collection#iterator()} as the source of elements, and + * reporting its {@link java.util.Collection#size()} as its initial size. + * + * <p>The spliterator is + * <em><a href="Spliterator.html#binding">late-binding</a></em>, inherits + * the <em>fail-fast</em> properties of the collection's iterator, and + * implements {@code trySplit} to permit limited parallelism. + * + * @param <T> Type of elements + * @param c The collection + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator from an iterator + * @throws NullPointerException if the given collection is {@code null} + */ + public static <T> Spliterator<T> spliterator(Collection<? extends T> c, + int additionalCharacteristics) { + return new IteratorSpliterator<>(Objects.requireNonNull(c), + additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator} using a given {@code Iterator} + * as the source of elements, and with a given initially reported size. + * + * <p>The spliterator is not + * <em><a href="Spliterator.html#binding">late-binding</a></em>, inherits + * the <em>fail-fast</em> properties of the iterator, and implements + * {@code trySplit} to permit limited parallelism. + * + * <p>Traversal of elements should be accomplished through the spliterator. + * The behaviour of splitting and traversal is undefined if the iterator is + * operated on after the spliterator is returned, or the initially reported + * size is not equal to the actual number of elements in the source. + * + * @param <T> Type of elements + * @param iterator The iterator for the source + * @param size The number of elements in the source, to be reported as + * initial {@code estimateSize} + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator from an iterator + * @throws NullPointerException if the given iterator is {@code null} + */ + public static <T> Spliterator<T> spliterator(Iterator<? extends T> iterator, + long size, + int additionalCharacteristics) { + return new IteratorSpliterator<>(Objects.requireNonNull(iterator), size, + additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator} using a given {@code Iterator} + * as the source of elements, with no initial size estimate. + * + * <p>The spliterator is not + * <em><a href="Spliterator.html#binding">late-binding</a></em>, inherits + * the <em>fail-fast</em> properties of the iterator, and implements + * {@code trySplit} to permit limited parallelism. + * + * <p>Traversal of elements should be accomplished through the spliterator. + * The behaviour of splitting and traversal is undefined if the iterator is + * operated on after the spliterator is returned. + * + * @param <T> Type of elements + * @param iterator The iterator for the source + * @param characteristics Properties of this spliterator's source + * or elements ({@code SIZED} and {@code SUBSIZED}, if supplied, are + * ignored and are not reported.) + * @return A spliterator from an iterator + * @throws NullPointerException if the given iterator is {@code null} + */ + public static <T> Spliterator<T> spliteratorUnknownSize(Iterator<? extends T> iterator, + int characteristics) { + return new IteratorSpliterator<>(Objects.requireNonNull(iterator), characteristics); + } + + /** + * Creates a {@code Spliterator.OfInt} using a given + * {@code IntStream.IntIterator} as the source of elements, and with a given + * initially reported size. + * + * <p>The spliterator is not + * <em><a href="Spliterator.html#binding">late-binding</a></em>, inherits + * the <em>fail-fast</em> properties of the iterator, and implements + * {@code trySplit} to permit limited parallelism. + * + * <p>Traversal of elements should be accomplished through the spliterator. + * The behaviour of splitting and traversal is undefined if the iterator is + * operated on after the spliterator is returned, or the initially reported + * size is not equal to the actual number of elements in the source. + * + * @param iterator The iterator for the source + * @param size The number of elements in the source, to be reported as + * initial {@code estimateSize}. + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator from an iterator + * @throws NullPointerException if the given iterator is {@code null} + */ + public static Spliterator.OfInt spliterator(PrimitiveIterator.OfInt iterator, + long size, + int additionalCharacteristics) { + return new IntIteratorSpliterator(Objects.requireNonNull(iterator), + size, additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator.OfInt} using a given + * {@code IntStream.IntIterator} as the source of elements, with no initial + * size estimate. + * + * <p>The spliterator is not + * <em><a href="Spliterator.html#binding">late-binding</a></em>, inherits + * the <em>fail-fast</em> properties of the iterator, and implements + * {@code trySplit} to permit limited parallelism. + * + * <p>Traversal of elements should be accomplished through the spliterator. + * The behaviour of splitting and traversal is undefined if the iterator is + * operated on after the spliterator is returned. + * + * @param iterator The iterator for the source + * @param characteristics Properties of this spliterator's source + * or elements ({@code SIZED} and {@code SUBSIZED}, if supplied, are + * ignored and are not reported.) + * @return A spliterator from an iterator + * @throws NullPointerException if the given iterator is {@code null} + */ + public static Spliterator.OfInt spliteratorUnknownSize(PrimitiveIterator.OfInt iterator, + int characteristics) { + return new IntIteratorSpliterator(Objects.requireNonNull(iterator), characteristics); + } + + /** + * Creates a {@code Spliterator.OfLong} using a given + * {@code LongStream.LongIterator} as the source of elements, and with a + * given initially reported size. + * + * <p>The spliterator is not + * <em><a href="Spliterator.html#binding">late-binding</a></em>, inherits + * the <em>fail-fast</em> properties of the iterator, and implements + * {@code trySplit} to permit limited parallelism. + * + * <p>Traversal of elements should be accomplished through the spliterator. + * The behaviour of splitting and traversal is undefined if the iterator is + * operated on after the spliterator is returned, or the initially reported + * size is not equal to the actual number of elements in the source. + * + * @param iterator The iterator for the source + * @param size The number of elements in the source, to be reported as + * initial {@code estimateSize}. + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator from an iterator + * @throws NullPointerException if the given iterator is {@code null} + */ + public static Spliterator.OfLong spliterator(PrimitiveIterator.OfLong iterator, + long size, + int additionalCharacteristics) { + return new LongIteratorSpliterator(Objects.requireNonNull(iterator), + size, additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator.OfLong} using a given + * {@code LongStream.LongIterator} as the source of elements, with no + * initial size estimate. + * + * <p>The spliterator is not + * <em><a href="Spliterator.html#binding">late-binding</a></em>, inherits + * the <em>fail-fast</em> properties of the iterator, and implements + * {@code trySplit} to permit limited parallelism. + * + * <p>Traversal of elements should be accomplished through the spliterator. + * The behaviour of splitting and traversal is undefined if the iterator is + * operated on after the spliterator is returned. + * + * @param iterator The iterator for the source + * @param characteristics Properties of this spliterator's source + * or elements ({@code SIZED} and {@code SUBSIZED}, if supplied, are + * ignored and are not reported.) + * @return A spliterator from an iterator + * @throws NullPointerException if the given iterator is {@code null} + */ + public static Spliterator.OfLong spliteratorUnknownSize(PrimitiveIterator.OfLong iterator, + int characteristics) { + return new LongIteratorSpliterator(Objects.requireNonNull(iterator), characteristics); + } + + /** + * Creates a {@code Spliterator.OfDouble} using a given + * {@code DoubleStream.DoubleIterator} as the source of elements, and with a + * given initially reported size. + * + * <p>The spliterator is not + * <em><a href="Spliterator.html#binding">late-binding</a></em>, inherits + * the <em>fail-fast</em> properties of the iterator, and implements + * {@code trySplit} to permit limited parallelism. + * + * <p>Traversal of elements should be accomplished through the spliterator. + * The behaviour of splitting and traversal is undefined if the iterator is + * operated on after the spliterator is returned, or the initially reported + * size is not equal to the actual number of elements in the source. + * + * @param iterator The iterator for the source + * @param size The number of elements in the source, to be reported as + * initial {@code estimateSize} + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + * @return A spliterator from an iterator + * @throws NullPointerException if the given iterator is {@code null} + */ + public static Spliterator.OfDouble spliterator(PrimitiveIterator.OfDouble iterator, + long size, + int additionalCharacteristics) { + return new DoubleIteratorSpliterator(Objects.requireNonNull(iterator), + size, additionalCharacteristics); + } + + /** + * Creates a {@code Spliterator.OfDouble} using a given + * {@code DoubleStream.DoubleIterator} as the source of elements, with no + * initial size estimate. + * + * <p>The spliterator is not + * <em><a href="Spliterator.html#binding">late-binding</a></em>, inherits + * the <em>fail-fast</em> properties of the iterator, and implements + * {@code trySplit} to permit limited parallelism. + * + * <p>Traversal of elements should be accomplished through the spliterator. + * The behaviour of splitting and traversal is undefined if the iterator is + * operated on after the spliterator is returned. + * + * @param iterator The iterator for the source + * @param characteristics Properties of this spliterator's source + * or elements ({@code SIZED} and {@code SUBSIZED}, if supplied, are + * ignored and are not reported.) + * @return A spliterator from an iterator + * @throws NullPointerException if the given iterator is {@code null} + */ + public static Spliterator.OfDouble spliteratorUnknownSize(PrimitiveIterator.OfDouble iterator, + int characteristics) { + return new DoubleIteratorSpliterator(Objects.requireNonNull(iterator), characteristics); + } + + // Iterators from Spliterators + + /** + * Creates an {@code Iterator} from a {@code Spliterator}. + * + * <p>Traversal of elements should be accomplished through the iterator. + * The behaviour of traversal is undefined if the spliterator is operated + * after the iterator is returned. + * + * @param <T> Type of elements + * @param spliterator The spliterator + * @return An iterator + * @throws NullPointerException if the given spliterator is {@code null} + */ + public static<T> Iterator<T> iteratorFromSpliterator(Spliterator<? extends T> spliterator) { + Objects.requireNonNull(spliterator); + class Adapter implements Iterator<T>, Consumer<T> { + boolean valueReady = false; + T nextElement; + + @Override + public void accept(T t) { + valueReady = true; + nextElement = t; + } + + @Override + public boolean hasNext() { + if (!valueReady) + spliterator.tryAdvance(this); + return valueReady; + } + + @Override + public T next() { + if (!valueReady && !hasNext()) + throw new NoSuchElementException(); + else { + valueReady = false; + return nextElement; + } + } + } + + return new Adapter(); + } + + /** + * Creates an {@code PrimitiveIterator.OfInt} from a + * {@code Spliterator.OfInt}. + * + * <p>Traversal of elements should be accomplished through the iterator. + * The behaviour of traversal is undefined if the spliterator is operated + * after the iterator is returned. + * + * @param spliterator The spliterator + * @return An iterator + * @throws NullPointerException if the given spliterator is {@code null} + */ + public static PrimitiveIterator.OfInt iteratorFromSpliterator(Spliterator.OfInt spliterator) { + Objects.requireNonNull(spliterator); + class Adapter implements PrimitiveIterator.OfInt, IntConsumer { + boolean valueReady = false; + int nextElement; + + @Override + public void accept(int t) { + valueReady = true; + nextElement = t; + } + + @Override + public boolean hasNext() { + if (!valueReady) + spliterator.tryAdvance(this); + return valueReady; + } + + @Override + public int nextInt() { + if (!valueReady && !hasNext()) + throw new NoSuchElementException(); + else { + valueReady = false; + return nextElement; + } + } + } + + return new Adapter(); + } + + /** + * Creates an {@code PrimitiveIterator.OfLong} from a + * {@code Spliterator.OfLong}. + * + * <p>Traversal of elements should be accomplished through the iterator. + * The behaviour of traversal is undefined if the spliterator is operated + * after the iterator is returned. + * + * @param spliterator The spliterator + * @return An iterator + * @throws NullPointerException if the given spliterator is {@code null} + */ + public static PrimitiveIterator.OfLong iteratorFromSpliterator(Spliterator.OfLong spliterator) { + Objects.requireNonNull(spliterator); + class Adapter implements PrimitiveIterator.OfLong, LongConsumer { + boolean valueReady = false; + long nextElement; + + @Override + public void accept(long t) { + valueReady = true; + nextElement = t; + } + + @Override + public boolean hasNext() { + if (!valueReady) + spliterator.tryAdvance(this); + return valueReady; + } + + @Override + public long nextLong() { + if (!valueReady && !hasNext()) + throw new NoSuchElementException(); + else { + valueReady = false; + return nextElement; + } + } + } + + return new Adapter(); + } + + /** + * Creates an {@code PrimitiveIterator.OfDouble} from a + * {@code Spliterator.OfDouble}. + * + * <p>Traversal of elements should be accomplished through the iterator. + * The behaviour of traversal is undefined if the spliterator is operated + * after the iterator is returned. + * + * @param spliterator The spliterator + * @return An iterator + * @throws NullPointerException if the given spliterator is {@code null} + */ + public static PrimitiveIterator.OfDouble iteratorFromSpliterator(Spliterator.OfDouble spliterator) { + Objects.requireNonNull(spliterator); + class Adapter implements PrimitiveIterator.OfDouble, DoubleConsumer { + boolean valueReady = false; + double nextElement; + + @Override + public void accept(double t) { + valueReady = true; + nextElement = t; + } + + @Override + public boolean hasNext() { + if (!valueReady) + spliterator.tryAdvance(this); + return valueReady; + } + + @Override + public double nextDouble() { + if (!valueReady && !hasNext()) + throw new NoSuchElementException(); + else { + valueReady = false; + return nextElement; + } + } + } + + return new Adapter(); + } + + // Implementations + + private static abstract class EmptySpliterator<T, S extends Spliterator<T>, C> { + + EmptySpliterator() { } + + public S trySplit() { + return null; + } + + public boolean tryAdvance(C consumer) { + Objects.requireNonNull(consumer); + return false; + } + + public void forEachRemaining(C consumer) { + Objects.requireNonNull(consumer); + } + + public long estimateSize() { + return 0; + } + + public int characteristics() { + return Spliterator.SIZED | Spliterator.SUBSIZED; + } + + private static final class OfRef<T> + extends EmptySpliterator<T, Spliterator<T>, Consumer<? super T>> + implements Spliterator<T> { + OfRef() { } + } + + private static final class OfInt + extends EmptySpliterator<Integer, Spliterator.OfInt, IntConsumer> + implements Spliterator.OfInt { + OfInt() { } + } + + private static final class OfLong + extends EmptySpliterator<Long, Spliterator.OfLong, LongConsumer> + implements Spliterator.OfLong { + OfLong() { } + } + + private static final class OfDouble + extends EmptySpliterator<Double, Spliterator.OfDouble, DoubleConsumer> + implements Spliterator.OfDouble { + OfDouble() { } + } + } + + // Array-based spliterators + + /** + * A Spliterator designed for use by sources that traverse and split + * elements maintained in an unmodifiable {@code Object[]} array. + */ + static final class ArraySpliterator<T> implements Spliterator<T> { + /** + * The array, explicitly typed as Object[]. Unlike in some other + * classes (see for example CR 6260652), we do not need to + * screen arguments to ensure they are exactly of type Object[] + * so long as no methods write into the array or serialize it, + * which we ensure here by defining this class as final. + */ + private final Object[] array; + private int index; // current index, modified on advance/split + private final int fence; // one past last index + private final int characteristics; + + /** + * Creates a spliterator covering all of the given array. + * @param array the array, assumed to be unmodified during use + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + */ + public ArraySpliterator(Object[] array, int additionalCharacteristics) { + this(array, 0, array.length, additionalCharacteristics); + } + + /** + * Creates a spliterator covering the given array and range + * @param array the array, assumed to be unmodified during use + * @param origin the least index (inclusive) to cover + * @param fence one past the greatest index to cover + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + */ + public ArraySpliterator(Object[] array, int origin, int fence, int additionalCharacteristics) { + this.array = array; + this.index = origin; + this.fence = fence; + this.characteristics = additionalCharacteristics | Spliterator.SIZED | Spliterator.SUBSIZED; + } + + @Override + public Spliterator<T> trySplit() { + int lo = index, mid = (lo + fence) >>> 1; + return (lo >= mid) + ? null + : new ArraySpliterator<>(array, lo, index = mid, characteristics); + } + + @SuppressWarnings("unchecked") + @Override + public void forEachRemaining(Consumer<? super T> action) { + Object[] a; int i, hi; // hoist accesses and checks from loop + if (action == null) + throw new NullPointerException(); + if ((a = array).length >= (hi = fence) && + (i = index) >= 0 && i < (index = hi)) { + do { action.accept((T)a[i]); } while (++i < hi); + } + } + + @Override + public boolean tryAdvance(Consumer<? super T> action) { + if (action == null) + throw new NullPointerException(); + if (index >= 0 && index < fence) { + @SuppressWarnings("unchecked") T e = (T) array[index++]; + action.accept(e); + return true; + } + return false; + } + + @Override + public long estimateSize() { return (long)(fence - index); } + + @Override + public int characteristics() { + return characteristics; + } + + @Override + public Comparator<? super T> getComparator() { + if (hasCharacteristics(Spliterator.SORTED)) + return null; + throw new IllegalStateException(); + } + } + + /** + * A Spliterator.OfInt designed for use by sources that traverse and split + * elements maintained in an unmodifiable {@code int[]} array. + */ + static final class IntArraySpliterator implements Spliterator.OfInt { + private final int[] array; + private int index; // current index, modified on advance/split + private final int fence; // one past last index + private final int characteristics; + + /** + * Creates a spliterator covering all of the given array. + * @param array the array, assumed to be unmodified during use + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + */ + public IntArraySpliterator(int[] array, int additionalCharacteristics) { + this(array, 0, array.length, additionalCharacteristics); + } + + /** + * Creates a spliterator covering the given array and range + * @param array the array, assumed to be unmodified during use + * @param origin the least index (inclusive) to cover + * @param fence one past the greatest index to cover + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + */ + public IntArraySpliterator(int[] array, int origin, int fence, int additionalCharacteristics) { + this.array = array; + this.index = origin; + this.fence = fence; + this.characteristics = additionalCharacteristics | Spliterator.SIZED | Spliterator.SUBSIZED; + } + + @Override + public OfInt trySplit() { + int lo = index, mid = (lo + fence) >>> 1; + return (lo >= mid) + ? null + : new IntArraySpliterator(array, lo, index = mid, characteristics); + } + + @Override + public void forEachRemaining(IntConsumer action) { + int[] a; int i, hi; // hoist accesses and checks from loop + if (action == null) + throw new NullPointerException(); + if ((a = array).length >= (hi = fence) && + (i = index) >= 0 && i < (index = hi)) { + do { action.accept(a[i]); } while (++i < hi); + } + } + + @Override + public boolean tryAdvance(IntConsumer action) { + if (action == null) + throw new NullPointerException(); + if (index >= 0 && index < fence) { + action.accept(array[index++]); + return true; + } + return false; + } + + @Override + public long estimateSize() { return (long)(fence - index); } + + @Override + public int characteristics() { + return characteristics; + } + + @Override + public Comparator<? super Integer> getComparator() { + if (hasCharacteristics(Spliterator.SORTED)) + return null; + throw new IllegalStateException(); + } + } + + /** + * A Spliterator.OfLong designed for use by sources that traverse and split + * elements maintained in an unmodifiable {@code int[]} array. + */ + static final class LongArraySpliterator implements Spliterator.OfLong { + private final long[] array; + private int index; // current index, modified on advance/split + private final int fence; // one past last index + private final int characteristics; + + /** + * Creates a spliterator covering all of the given array. + * @param array the array, assumed to be unmodified during use + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + */ + public LongArraySpliterator(long[] array, int additionalCharacteristics) { + this(array, 0, array.length, additionalCharacteristics); + } + + /** + * Creates a spliterator covering the given array and range + * @param array the array, assumed to be unmodified during use + * @param origin the least index (inclusive) to cover + * @param fence one past the greatest index to cover + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + */ + public LongArraySpliterator(long[] array, int origin, int fence, int additionalCharacteristics) { + this.array = array; + this.index = origin; + this.fence = fence; + this.characteristics = additionalCharacteristics | Spliterator.SIZED | Spliterator.SUBSIZED; + } + + @Override + public OfLong trySplit() { + int lo = index, mid = (lo + fence) >>> 1; + return (lo >= mid) + ? null + : new LongArraySpliterator(array, lo, index = mid, characteristics); + } + + @Override + public void forEachRemaining(LongConsumer action) { + long[] a; int i, hi; // hoist accesses and checks from loop + if (action == null) + throw new NullPointerException(); + if ((a = array).length >= (hi = fence) && + (i = index) >= 0 && i < (index = hi)) { + do { action.accept(a[i]); } while (++i < hi); + } + } + + @Override + public boolean tryAdvance(LongConsumer action) { + if (action == null) + throw new NullPointerException(); + if (index >= 0 && index < fence) { + action.accept(array[index++]); + return true; + } + return false; + } + + @Override + public long estimateSize() { return (long)(fence - index); } + + @Override + public int characteristics() { + return characteristics; + } + + @Override + public Comparator<? super Long> getComparator() { + if (hasCharacteristics(Spliterator.SORTED)) + return null; + throw new IllegalStateException(); + } + } + + /** + * A Spliterator.OfDouble designed for use by sources that traverse and split + * elements maintained in an unmodifiable {@code int[]} array. + */ + static final class DoubleArraySpliterator implements Spliterator.OfDouble { + private final double[] array; + private int index; // current index, modified on advance/split + private final int fence; // one past last index + private final int characteristics; + + /** + * Creates a spliterator covering all of the given array. + * @param array the array, assumed to be unmodified during use + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + */ + public DoubleArraySpliterator(double[] array, int additionalCharacteristics) { + this(array, 0, array.length, additionalCharacteristics); + } + + /** + * Creates a spliterator covering the given array and range + * @param array the array, assumed to be unmodified during use + * @param origin the least index (inclusive) to cover + * @param fence one past the greatest index to cover + * @param additionalCharacteristics Additional spliterator characteristics + * of this spliterator's source or elements beyond {@code SIZED} and + * {@code SUBSIZED} which are are always reported + */ + public DoubleArraySpliterator(double[] array, int origin, int fence, int additionalCharacteristics) { + this.array = array; + this.index = origin; + this.fence = fence; + this.characteristics = additionalCharacteristics | Spliterator.SIZED | Spliterator.SUBSIZED; + } + + @Override + public OfDouble trySplit() { + int lo = index, mid = (lo + fence) >>> 1; + return (lo >= mid) + ? null + : new DoubleArraySpliterator(array, lo, index = mid, characteristics); + } + + @Override + public void forEachRemaining(DoubleConsumer action) { + double[] a; int i, hi; // hoist accesses and checks from loop + if (action == null) + throw new NullPointerException(); + if ((a = array).length >= (hi = fence) && + (i = index) >= 0 && i < (index = hi)) { + do { action.accept(a[i]); } while (++i < hi); + } + } + + @Override + public boolean tryAdvance(DoubleConsumer action) { + if (action == null) + throw new NullPointerException(); + if (index >= 0 && index < fence) { + action.accept(array[index++]); + return true; + } + return false; + } + + @Override + public long estimateSize() { return (long)(fence - index); } + + @Override + public int characteristics() { + return characteristics; + } + + @Override + public Comparator<? super Double> getComparator() { + if (hasCharacteristics(Spliterator.SORTED)) + return null; + throw new IllegalStateException(); + } + } + + // + + /** + * An abstract {@code Spliterator} that implements {@code trySplit} to + * permit limited parallelism. + * + * <p>An extending class need only + * implement {@link #tryAdvance(java.util.function.Consumer) tryAdvance}. + * The extending class should override + * {@link #forEachRemaining(java.util.function.Consumer) forEach} if it can + * provide a more performant implementation. + * + * @apiNote + * This class is a useful aid for creating a spliterator when it is not + * possible or difficult to efficiently partition elements in a manner + * allowing balanced parallel computation. + * + * <p>An alternative to using this class, that also permits limited + * parallelism, is to create a spliterator from an iterator + * (see {@link #spliterator(Iterator, long, int)}. Depending on the + * circumstances using an iterator may be easier or more convenient than + * extending this class, such as when there is already an iterator + * available to use. + * + * @see #spliterator(Iterator, long, int) + * @since 1.8 + */ + public static abstract class AbstractSpliterator<T> implements Spliterator<T> { + static final int BATCH_UNIT = 1 << 10; // batch array size increment + static final int MAX_BATCH = 1 << 25; // max batch array size; + private final int characteristics; + private long est; // size estimate + private int batch; // batch size for splits + + /** + * Creates a spliterator reporting the given estimated size and + * additionalCharacteristics. + * + * @param est the estimated size of this spliterator if known, otherwise + * {@code Long.MAX_VALUE}. + * @param additionalCharacteristics properties of this spliterator's + * source or elements. If {@code SIZED} is reported then this + * spliterator will additionally report {@code SUBSIZED}. + */ + protected AbstractSpliterator(long est, int additionalCharacteristics) { + this.est = est; + this.characteristics = ((additionalCharacteristics & Spliterator.SIZED) != 0) + ? additionalCharacteristics | Spliterator.SUBSIZED + : additionalCharacteristics; + } + + static final class HoldingConsumer<T> implements Consumer<T> { + Object value; + + @Override + public void accept(T value) { + this.value = value; + } + } + + /** + * {@inheritDoc} + * + * This implementation permits limited parallelism. + */ + @Override + public Spliterator<T> trySplit() { + /* + * Split into arrays of arithmetically increasing batch + * sizes. This will only improve parallel performance if + * per-element Consumer actions are more costly than + * transferring them into an array. The use of an + * arithmetic progression in split sizes provides overhead + * vs parallelism bounds that do not particularly favor or + * penalize cases of lightweight vs heavyweight element + * operations, across combinations of #elements vs #cores, + * whether or not either are known. We generate + * O(sqrt(#elements)) splits, allowing O(sqrt(#cores)) + * potential speedup. + */ + HoldingConsumer<T> holder = new HoldingConsumer<>(); + long s = est; + if (s > 1 && tryAdvance(holder)) { + int n = batch + BATCH_UNIT; + if (n > s) + n = (int) 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] = holder.value; } while (++j < n && tryAdvance(holder)); + batch = j; + if (est != Long.MAX_VALUE) + est -= j; + return new ArraySpliterator<>(a, 0, j, characteristics()); + } + return null; + } + + /** + * {@inheritDoc} + * + * @implSpec + * This implementation returns the estimated size as reported when + * created and, if the estimate size is known, decreases in size when + * split. + */ + @Override + public long estimateSize() { + return est; + } + + /** + * {@inheritDoc} + * + * @implSpec + * This implementation returns the characteristics as reported when + * created. + */ + @Override + public int characteristics() { + return characteristics; + } + } + + /** + * An abstract {@code Spliterator.OfInt} that implements {@code trySplit} to + * permit limited parallelism. + * + * <p>To implement a spliterator an extending class need only + * implement {@link #tryAdvance(java.util.function.IntConsumer)} + * tryAdvance}. The extending class should override + * {@link #forEachRemaining(java.util.function.IntConsumer)} forEach} if it + * can provide a more performant implementation. + * + * @apiNote + * This class is a useful aid for creating a spliterator when it is not + * possible or difficult to efficiently partition elements in a manner + * allowing balanced parallel computation. + * + * <p>An alternative to using this class, that also permits limited + * parallelism, is to create a spliterator from an iterator + * (see {@link #spliterator(java.util.PrimitiveIterator.OfInt, long, int)}. + * Depending on the circumstances using an iterator may be easier or more + * convenient than extending this class. For example, if there is already an + * iterator available to use then there is no need to extend this class. + * + * @see #spliterator(java.util.PrimitiveIterator.OfInt, long, int) + * @since 1.8 + */ + public static abstract class AbstractIntSpliterator implements Spliterator.OfInt { + static final int MAX_BATCH = AbstractSpliterator.MAX_BATCH; + static final int BATCH_UNIT = AbstractSpliterator.BATCH_UNIT; + private final int characteristics; + private long est; // size estimate + private int batch; // batch size for splits + + /** + * Creates a spliterator reporting the given estimated size and + * characteristics. + * + * @param est the estimated size of this spliterator if known, otherwise + * {@code Long.MAX_VALUE}. + * @param additionalCharacteristics properties of this spliterator's + * source or elements. If {@code SIZED} is reported then this + * spliterator will additionally report {@code SUBSIZED}. + */ + protected AbstractIntSpliterator(long est, int additionalCharacteristics) { + this.est = est; + this.characteristics = ((additionalCharacteristics & Spliterator.SIZED) != 0) + ? additionalCharacteristics | Spliterator.SUBSIZED + : additionalCharacteristics; + } + + static final class HoldingIntConsumer implements IntConsumer { + int value; + + @Override + public void accept(int value) { + this.value = value; + } + } + + /** + * {@inheritDoc} + * + * This implementation permits limited parallelism. + */ + @Override + public Spliterator.OfInt trySplit() { + HoldingIntConsumer holder = new HoldingIntConsumer(); + long s = est; + if (s > 1 && tryAdvance(holder)) { + int n = batch + BATCH_UNIT; + if (n > s) + n = (int) s; + if (n > MAX_BATCH) + n = MAX_BATCH; + int[] a; + try { + a = new int[n]; + } catch (OutOfMemoryError oome) { + return null; + } + int j = 0; + do { a[j] = holder.value; } while (++j < n && tryAdvance(holder)); + batch = j; + if (est != Long.MAX_VALUE) + est -= j; + return new IntArraySpliterator(a, 0, j, characteristics()); + } + return null; + } + + /** + * {@inheritDoc} + * + * @implSpec + * This implementation returns the estimated size as reported when + * created and, if the estimate size is known, decreases in size when + * split. + */ + @Override + public long estimateSize() { + return est; + } + + /** + * {@inheritDoc} + * + * @implSpec + * This implementation returns the characteristics as reported when + * created. + */ + @Override + public int characteristics() { + return characteristics; + } + } + + /** + * An abstract {@code Spliterator.OfLong} that implements {@code trySplit} + * to permit limited parallelism. + * + * <p>To implement a spliterator an extending class need only + * implement {@link #tryAdvance(java.util.function.LongConsumer)} + * tryAdvance}. The extending class should override + * {@link #forEachRemaining(java.util.function.LongConsumer)} forEach} if it + * can provide a more performant implementation. + * + * @apiNote + * This class is a useful aid for creating a spliterator when it is not + * possible or difficult to efficiently partition elements in a manner + * allowing balanced parallel computation. + * + * <p>An alternative to using this class, that also permits limited + * parallelism, is to create a spliterator from an iterator + * (see {@link #spliterator(java.util.PrimitiveIterator.OfLong, long, int)}. + * Depending on the circumstances using an iterator may be easier or more + * convenient than extending this class. For example, if there is already an + * iterator available to use then there is no need to extend this class. + * + * @see #spliterator(java.util.PrimitiveIterator.OfLong, long, int) + * @since 1.8 + */ + public static abstract class AbstractLongSpliterator implements Spliterator.OfLong { + static final int MAX_BATCH = AbstractSpliterator.MAX_BATCH; + static final int BATCH_UNIT = AbstractSpliterator.BATCH_UNIT; + private final int characteristics; + private long est; // size estimate + private int batch; // batch size for splits + + /** + * Creates a spliterator reporting the given estimated size and + * characteristics. + * + * @param est the estimated size of this spliterator if known, otherwise + * {@code Long.MAX_VALUE}. + * @param additionalCharacteristics properties of this spliterator's + * source or elements. If {@code SIZED} is reported then this + * spliterator will additionally report {@code SUBSIZED}. + */ + protected AbstractLongSpliterator(long est, int additionalCharacteristics) { + this.est = est; + this.characteristics = ((additionalCharacteristics & Spliterator.SIZED) != 0) + ? additionalCharacteristics | Spliterator.SUBSIZED + : additionalCharacteristics; + } + + static final class HoldingLongConsumer implements LongConsumer { + long value; + + @Override + public void accept(long value) { + this.value = value; + } + } + + /** + * {@inheritDoc} + * + * This implementation permits limited parallelism. + */ + @Override + public Spliterator.OfLong trySplit() { + HoldingLongConsumer holder = new HoldingLongConsumer(); + long s = est; + if (s > 1 && tryAdvance(holder)) { + int n = batch + BATCH_UNIT; + if (n > s) + n = (int) s; + if (n > MAX_BATCH) + n = MAX_BATCH; + long[] a; + try { + a = new long[n]; + } catch (OutOfMemoryError oome) { + return null; + } + int j = 0; + do { a[j] = holder.value; } while (++j < n && tryAdvance(holder)); + batch = j; + if (est != Long.MAX_VALUE) + est -= j; + return new LongArraySpliterator(a, 0, j, characteristics()); + } + return null; + } + + /** + * {@inheritDoc} + * + * @implSpec + * This implementation returns the estimated size as reported when + * created and, if the estimate size is known, decreases in size when + * split. + */ + @Override + public long estimateSize() { + return est; + } + + /** + * {@inheritDoc} + * + * @implSpec + * This implementation returns the characteristics as reported when + * created. + */ + @Override + public int characteristics() { + return characteristics; + } + } + + /** + * An abstract {@code Spliterator.OfDouble} that implements + * {@code trySplit} to permit limited parallelism. + * + * <p>To implement a spliterator an extending class need only + * implement {@link #tryAdvance(java.util.function.DoubleConsumer)} + * tryAdvance}. The extending class should override + * {@link #forEachRemaining(java.util.function.DoubleConsumer)} forEach} if + * it can provide a more performant implementation. + * + * @apiNote + * This class is a useful aid for creating a spliterator when it is not + * possible or difficult to efficiently partition elements in a manner + * allowing balanced parallel computation. + * + * <p>An alternative to using this class, that also permits limited + * parallelism, is to create a spliterator from an iterator + * (see {@link #spliterator(java.util.PrimitiveIterator.OfDouble, long, int)}. + * Depending on the circumstances using an iterator may be easier or more + * convenient than extending this class. For example, if there is already an + * iterator available to use then there is no need to extend this class. + * + * @see #spliterator(java.util.PrimitiveIterator.OfDouble, long, int) + * @since 1.8 + */ + public static abstract class AbstractDoubleSpliterator implements Spliterator.OfDouble { + static final int MAX_BATCH = AbstractSpliterator.MAX_BATCH; + static final int BATCH_UNIT = AbstractSpliterator.BATCH_UNIT; + private final int characteristics; + private long est; // size estimate + private int batch; // batch size for splits + + /** + * Creates a spliterator reporting the given estimated size and + * characteristics. + * + * @param est the estimated size of this spliterator if known, otherwise + * {@code Long.MAX_VALUE}. + * @param additionalCharacteristics properties of this spliterator's + * source or elements. If {@code SIZED} is reported then this + * spliterator will additionally report {@code SUBSIZED}. + */ + protected AbstractDoubleSpliterator(long est, int additionalCharacteristics) { + this.est = est; + this.characteristics = ((additionalCharacteristics & Spliterator.SIZED) != 0) + ? additionalCharacteristics | Spliterator.SUBSIZED + : additionalCharacteristics; + } + + static final class HoldingDoubleConsumer implements DoubleConsumer { + double value; + + @Override + public void accept(double value) { + this.value = value; + } + } + + /** + * {@inheritDoc} + * + * This implementation permits limited parallelism. + */ + @Override + public Spliterator.OfDouble trySplit() { + HoldingDoubleConsumer holder = new HoldingDoubleConsumer(); + long s = est; + if (s > 1 && tryAdvance(holder)) { + int n = batch + BATCH_UNIT; + if (n > s) + n = (int) s; + if (n > MAX_BATCH) + n = MAX_BATCH; + double[] a; + try { + a = new double[n]; + } catch (OutOfMemoryError oome) { + return null; + } + int j = 0; + do { a[j] = holder.value; } while (++j < n && tryAdvance(holder)); + batch = j; + if (est != Long.MAX_VALUE) + est -= j; + return new DoubleArraySpliterator(a, 0, j, characteristics()); + } + return null; + } + + /** + * {@inheritDoc} + * + * @implSpec + * This implementation returns the estimated size as reported when + * created and, if the estimate size is known, decreases in size when + * split. + */ + @Override + public long estimateSize() { + return est; + } + + /** + * {@inheritDoc} + * + * @implSpec + * This implementation returns the characteristics as reported when + * created. + */ + @Override + public int characteristics() { + return characteristics; + } + } + + // Iterator-based Spliterators + + /** + * A Spliterator using a given Iterator for element + * operations. The spliterator implements {@code trySplit} to + * permit limited parallelism. + */ + static class IteratorSpliterator<T> implements Spliterator<T> { + static final int BATCH_UNIT = 1 << 10; // batch array size increment + static final int MAX_BATCH = 1 << 25; // max batch array size; + private final Collection<? extends T> collection; // null OK + private Iterator<? extends T> it; + private final int characteristics; + private long est; // size estimate + private int batch; // batch size for splits + + /** + * Creates a spliterator using the given given + * collection's {@link java.util.Collection#iterator()) for traversal, + * and reporting its {@link java.util.Collection#size()) as its initial + * size. + * + * @param c the collection + * @param characteristics properties of this spliterator's + * source or elements. + */ + public IteratorSpliterator(Collection<? extends T> collection, int characteristics) { + this.collection = collection; + this.it = null; + this.characteristics = characteristics | Spliterator.SIZED | Spliterator.SUBSIZED; + } + + /** + * Creates a spliterator using the given iterator + * for traversal, and reporting the given initial size + * and characteristics. + * + * @param iterator the iterator for the source + * @param size the number of elements in the source + * @param characteristics properties of this spliterator's + * source or elements. + */ + public IteratorSpliterator(Iterator<? extends T> iterator, long size, int characteristics) { + this.collection = null; + this.it = iterator; + this.est = size; + this.characteristics = characteristics | Spliterator.SIZED | Spliterator.SUBSIZED; + } + + /** + * Creates a spliterator using the given iterator + * for traversal, and reporting the given initial size + * and characteristics. + * + * @param iterator the iterator for the source + * @param characteristics properties of this spliterator's + * source or elements. + */ + public IteratorSpliterator(Iterator<? extends T> iterator, int characteristics) { + this.collection = null; + this.it = iterator; + this.est = Long.MAX_VALUE; + this.characteristics = characteristics & ~(Spliterator.SIZED | Spliterator.SUBSIZED); + } + + @Override + public Spliterator<T> trySplit() { + /* + * Split into arrays of arithmetically increasing batch + * sizes. This will only improve parallel performance if + * per-element Consumer actions are more costly than + * transferring them into an array. The use of an + * arithmetic progression in split sizes provides overhead + * vs parallelism bounds that do not particularly favor or + * penalize cases of lightweight vs heavyweight element + * operations, across combinations of #elements vs #cores, + * whether or not either are known. We generate + * O(sqrt(#elements)) splits, allowing O(sqrt(#cores)) + * potential speedup. + */ + Iterator<? extends T> i; + long s; + if ((i = it) == null) { + i = it = collection.iterator(); + s = est = (long) collection.size(); + } + else + s = est; + if (s > 1 && i.hasNext()) { + int n = batch + BATCH_UNIT; + if (n > s) + n = (int) 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] = i.next(); } while (++j < n && i.hasNext()); + batch = j; + if (est != Long.MAX_VALUE) + est -= j; + return new ArraySpliterator<>(a, 0, j, characteristics); + } + return null; + } + + @Override + public void forEachRemaining(Consumer<? super T> action) { + if (action == null) throw new NullPointerException(); + Iterator<? extends T> i; + if ((i = it) == null) { + i = it = collection.iterator(); + est = (long)collection.size(); + } + i.forEachRemaining(action); + } + + @Override + public boolean tryAdvance(Consumer<? super T> action) { + if (action == null) throw new NullPointerException(); + if (it == null) { + it = collection.iterator(); + est = (long) collection.size(); + } + if (it.hasNext()) { + action.accept(it.next()); + return true; + } + return false; + } + + @Override + public long estimateSize() { + if (it == null) { + it = collection.iterator(); + return est = (long)collection.size(); + } + return est; + } + + @Override + public int characteristics() { return characteristics; } + + @Override + public Comparator<? super T> getComparator() { + if (hasCharacteristics(Spliterator.SORTED)) + return null; + throw new IllegalStateException(); + } + } + + /** + * A Spliterator.OfInt using a given IntStream.IntIterator for element + * operations. The spliterator implements {@code trySplit} to + * permit limited parallelism. + */ + static final class IntIteratorSpliterator implements Spliterator.OfInt { + static final int BATCH_UNIT = IteratorSpliterator.BATCH_UNIT; + static final int MAX_BATCH = IteratorSpliterator.MAX_BATCH; + private PrimitiveIterator.OfInt it; + private final int characteristics; + private long est; // size estimate + private int batch; // batch size for splits + + /** + * Creates a spliterator using the given iterator + * for traversal, and reporting the given initial size + * and characteristics. + * + * @param iterator the iterator for the source + * @param size the number of elements in the source + * @param characteristics properties of this spliterator's + * source or elements. + */ + public IntIteratorSpliterator(PrimitiveIterator.OfInt iterator, long size, int characteristics) { + this.it = iterator; + this.est = size; + this.characteristics = characteristics | Spliterator.SIZED | Spliterator.SUBSIZED; + } + + /** + * Creates a spliterator using the given iterator for a + * source of unknown size, reporting the given + * characteristics. + * + * @param iterator the iterator for the source + * @param characteristics properties of this spliterator's + * source or elements. + */ + public IntIteratorSpliterator(PrimitiveIterator.OfInt iterator, int characteristics) { + this.it = iterator; + this.est = Long.MAX_VALUE; + this.characteristics = characteristics & ~(Spliterator.SIZED | Spliterator.SUBSIZED); + } + + @Override + public OfInt trySplit() { + PrimitiveIterator.OfInt i = it; + long s = est; + if (s > 1 && i.hasNext()) { + int n = batch + BATCH_UNIT; + if (n > s) + n = (int) s; + if (n > MAX_BATCH) + n = MAX_BATCH; + int[] a; + try { + a = new int[n]; + } catch (OutOfMemoryError oome) { + return null; + } + int j = 0; + do { a[j] = i.nextInt(); } while (++j < n && i.hasNext()); + batch = j; + if (est != Long.MAX_VALUE) + est -= j; + return new IntArraySpliterator(a, 0, j, characteristics); + } + return null; + } + + @Override + public void forEachRemaining(IntConsumer action) { + if (action == null) throw new NullPointerException(); + it.forEachRemaining(action); + } + + @Override + public boolean tryAdvance(IntConsumer action) { + if (action == null) throw new NullPointerException(); + if (it.hasNext()) { + action.accept(it.nextInt()); + return true; + } + return false; + } + + @Override + public long estimateSize() { + return est; + } + + @Override + public int characteristics() { return characteristics; } + + @Override + public Comparator<? super Integer> getComparator() { + if (hasCharacteristics(Spliterator.SORTED)) + return null; + throw new IllegalStateException(); + } + } + + static final class LongIteratorSpliterator implements Spliterator.OfLong { + static final int BATCH_UNIT = IteratorSpliterator.BATCH_UNIT; + static final int MAX_BATCH = IteratorSpliterator.MAX_BATCH; + private PrimitiveIterator.OfLong it; + private final int characteristics; + private long est; // size estimate + private int batch; // batch size for splits + + /** + * Creates a spliterator using the given iterator + * for traversal, and reporting the given initial size + * and characteristics. + * + * @param iterator the iterator for the source + * @param size the number of elements in the source + * @param characteristics properties of this spliterator's + * source or elements. + */ + public LongIteratorSpliterator(PrimitiveIterator.OfLong iterator, long size, int characteristics) { + this.it = iterator; + this.est = size; + this.characteristics = characteristics | Spliterator.SIZED | Spliterator.SUBSIZED; + } + + /** + * Creates a spliterator using the given iterator for a + * source of unknown size, reporting the given + * characteristics. + * + * @param iterator the iterator for the source + * @param characteristics properties of this spliterator's + * source or elements. + */ + public LongIteratorSpliterator(PrimitiveIterator.OfLong iterator, int characteristics) { + this.it = iterator; + this.est = Long.MAX_VALUE; + this.characteristics = characteristics & ~(Spliterator.SIZED | Spliterator.SUBSIZED); + } + + @Override + public OfLong trySplit() { + PrimitiveIterator.OfLong i = it; + long s = est; + if (s > 1 && i.hasNext()) { + int n = batch + BATCH_UNIT; + if (n > s) + n = (int) s; + if (n > MAX_BATCH) + n = MAX_BATCH; + long[] a; + try { + a = new long[n]; + } catch (OutOfMemoryError oome) { + return null; + } + int j = 0; + do { a[j] = i.nextLong(); } while (++j < n && i.hasNext()); + batch = j; + if (est != Long.MAX_VALUE) + est -= j; + return new LongArraySpliterator(a, 0, j, characteristics); + } + return null; + } + + @Override + public void forEachRemaining(LongConsumer action) { + if (action == null) throw new NullPointerException(); + it.forEachRemaining(action); + } + + @Override + public boolean tryAdvance(LongConsumer action) { + if (action == null) throw new NullPointerException(); + if (it.hasNext()) { + action.accept(it.nextLong()); + return true; + } + return false; + } + + @Override + public long estimateSize() { + return est; + } + + @Override + public int characteristics() { return characteristics; } + + @Override + public Comparator<? super Long> getComparator() { + if (hasCharacteristics(Spliterator.SORTED)) + return null; + throw new IllegalStateException(); + } + } + + static final class DoubleIteratorSpliterator implements Spliterator.OfDouble { + static final int BATCH_UNIT = IteratorSpliterator.BATCH_UNIT; + static final int MAX_BATCH = IteratorSpliterator.MAX_BATCH; + private PrimitiveIterator.OfDouble it; + private final int characteristics; + private long est; // size estimate + private int batch; // batch size for splits + + /** + * Creates a spliterator using the given iterator + * for traversal, and reporting the given initial size + * and characteristics. + * + * @param iterator the iterator for the source + * @param size the number of elements in the source + * @param characteristics properties of this spliterator's + * source or elements. + */ + public DoubleIteratorSpliterator(PrimitiveIterator.OfDouble iterator, long size, int characteristics) { + this.it = iterator; + this.est = size; + this.characteristics = characteristics | Spliterator.SIZED | Spliterator.SUBSIZED; + } + + /** + * Creates a spliterator using the given iterator for a + * source of unknown size, reporting the given + * characteristics. + * + * @param iterator the iterator for the source + * @param characteristics properties of this spliterator's + * source or elements. + */ + public DoubleIteratorSpliterator(PrimitiveIterator.OfDouble iterator, int characteristics) { + this.it = iterator; + this.est = Long.MAX_VALUE; + this.characteristics = characteristics & ~(Spliterator.SIZED | Spliterator.SUBSIZED); + } + + @Override + public OfDouble trySplit() { + PrimitiveIterator.OfDouble i = it; + long s = est; + if (s > 1 && i.hasNext()) { + int n = batch + BATCH_UNIT; + if (n > s) + n = (int) s; + if (n > MAX_BATCH) + n = MAX_BATCH; + double[] a; + try { + a = new double[n]; + } catch (OutOfMemoryError oome) { + return null; + } + int j = 0; + do { a[j] = i.nextDouble(); } while (++j < n && i.hasNext()); + batch = j; + if (est != Long.MAX_VALUE) + est -= j; + return new DoubleArraySpliterator(a, 0, j, characteristics); + } + return null; + } + + @Override + public void forEachRemaining(DoubleConsumer action) { + if (action == null) throw new NullPointerException(); + it.forEachRemaining(action); + } + + @Override + public boolean tryAdvance(DoubleConsumer action) { + if (action == null) throw new NullPointerException(); + if (it.hasNext()) { + action.accept(it.nextDouble()); + return true; + } + return false; + } + + @Override + public long estimateSize() { + return est; + } + + @Override + public int characteristics() { return characteristics; } + + @Override + public Comparator<? super Double> getComparator() { + if (hasCharacteristics(Spliterator.SORTED)) + return null; + throw new IllegalStateException(); + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/classes/java/util/Tripwire.java Tue Apr 16 13:51:53 2013 -0400 @@ -0,0 +1,69 @@ +/* + * Copyright (c) 2012, 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. Oracle designates this + * particular file as subject to the "Classpath" exception as provided + * by Oracle in the LICENSE file that accompanied this code. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package java.util; + +import sun.util.logging.PlatformLogger; + +import java.security.AccessController; +import java.security.PrivilegedAction; + +/** + * Utility class for detecting inadvertent uses of boxing in + * {@code java.util} classes. The detection is turned on or off based on + * whether the system property {@code org.openjdk.java.util.stream.tripwire} is + * considered {@code true} according to {@link Boolean#getBoolean(String)}. + * This should normally be turned off for production use. + * + * @apiNote + * Typical usage would be for boxing code to do: + * <pre>{@code + * if (Tripwire.ENABLED) + * Tripwire.trip(getClass(), "{0} calling PrimitiveIterator.OfInt.nextInt()"); + * }</pre> + * + * @since 1.8 + */ +final class Tripwire { + private static final String TRIPWIRE_PROPERTY = "org.openjdk.java.util.stream.tripwire"; + + /** Should debugging checks be enabled? */ + static final boolean ENABLED = AccessController.doPrivileged( + (PrivilegedAction<Boolean>) () -> Boolean.getBoolean(TRIPWIRE_PROPERTY)); + + private Tripwire() { } + + /** + * Produces a log warning, using {@code PlatformLogger.getLogger(className)}, + * using the supplied message. The class name of {@code trippingClass} will + * be used as the first parameter to the message. + * + * @param trippingClass Name of the class generating the message + * @param msg A message format string of the type expected by + * {@link PlatformLogger} + */ + static void trip(Class<?> trippingClass, String msg) { + PlatformLogger.getLogger(trippingClass.getName()).warning(msg, trippingClass.getName()); + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/Spliterator/SpliteratorLateBindingFailFastTest.java Tue Apr 16 13:51:53 2013 -0400 @@ -0,0 +1,357 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +import org.testng.annotations.DataProvider; +import org.testng.annotations.Test; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.ConcurrentModificationException; +import java.util.HashMap; +import java.util.HashSet; +import java.util.LinkedHashMap; +import java.util.LinkedHashSet; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.PriorityQueue; +import java.util.Set; +import java.util.Spliterator; +import java.util.Stack; +import java.util.TreeMap; +import java.util.TreeSet; +import java.util.Vector; +import java.util.WeakHashMap; +import java.util.function.Consumer; +import java.util.function.Function; +import java.util.function.Supplier; + +import static org.testng.Assert.*; + +/** + * @test + * @summary Spliterator last-binding and fail-fast tests + * @run testng SpliteratorLateBindingFailFastTest + */ + +@Test +public class SpliteratorLateBindingFailFastTest { + + private interface Source<T> { + Collection<T> asCollection(); + void update(); + } + + private static class SpliteratorDataBuilder<T> { + final List<Object[]> data; + + final T newValue; + + final List<T> exp; + + final Map<T, T> mExp; + + SpliteratorDataBuilder(List<Object[]> data, T newValue, List<T> exp) { + this.data = data; + this.newValue = newValue; + this.exp = exp; + this.mExp = createMap(exp); + } + + Map<T, T> createMap(List<T> l) { + Map<T, T> m = new LinkedHashMap<>(); + for (T t : l) { + m.put(t, t); + } + return m; + } + + void add(String description, Supplier<Source<?>> s) { + description = joiner(description).toString(); + data.add(new Object[]{description, s}); + } + + void addCollection(Function<Collection<T>, ? extends Collection<T>> f) { + class CollectionSource implements Source<T> { + final Collection<T> c = f.apply(exp); + + final Consumer<Collection<T>> updater; + + CollectionSource(Consumer<Collection<T>> updater) { + this.updater = updater; + } + + @Override + public Collection<T> asCollection() { + return c; + } + + @Override + public void update() { + updater.accept(c); + } + } + + String description = "new " + f.apply(Collections.<T>emptyList()).getClass().getName() + ".spliterator() "; + add(description + "ADD", () -> new CollectionSource(c -> c.add(newValue))); + add(description + "REMOVE", () -> new CollectionSource(c -> c.remove(c.iterator().next()))); + } + + void addList(Function<Collection<T>, ? extends List<T>> l) { + // @@@ If collection is instance of List then add sub-list tests + addCollection(l); + } + + void addMap(Function<Map<T, T>, ? extends Map<T, T>> mapConstructor) { + class MapSource<U> implements Source<U> { + final Map<T, T> m = mapConstructor.apply(mExp); + + final Collection<U> c; + + final Consumer<Map<T, T>> updater; + + MapSource(Function<Map<T, T>, Collection<U>> f, Consumer<Map<T, T>> updater) { + this.c = f.apply(m); + this.updater = updater; + } + + @Override + public Collection<U> asCollection() { + return c; + } + + @Override + public void update() { + updater.accept(m); + } + } + + Map<String, Consumer<Map<T, T>>> actions = new HashMap<>(); + actions.put("ADD", m -> m.put(newValue, newValue)); + actions.put("REMOVE", m -> m.remove(m.keySet().iterator().next())); + + String description = "new " + mapConstructor.apply(Collections.<T, T>emptyMap()).getClass().getName(); + for (Map.Entry<String, Consumer<Map<T, T>>> e : actions.entrySet()) { + add(description + ".keySet().spliterator() " + e.getKey(), + () -> new MapSource<T>(m -> m.keySet(), e.getValue())); + add(description + ".values().spliterator() " + e.getKey(), + () -> new MapSource<T>(m -> m.values(), e.getValue())); + add(description + ".entrySet().spliterator() " + e.getKey(), + () -> new MapSource<Map.Entry<T, T>>(m -> m.entrySet(), e.getValue())); + } + } + + StringBuilder joiner(String description) { + return new StringBuilder(description). + append(" {"). + append("size=").append(exp.size()). + append("}"); + } + } + + static Object[][] spliteratorDataProvider; + + @DataProvider(name = "Source") + public static Object[][] spliteratorDataProvider() { + if (spliteratorDataProvider != null) { + return spliteratorDataProvider; + } + + List<Object[]> data = new ArrayList<>(); + SpliteratorDataBuilder<Integer> db = new SpliteratorDataBuilder<>(data, 5, Arrays.asList(1, 2, 3, 4)); + + // Collections + + db.addList(ArrayList::new); + + db.addList(LinkedList::new); + + db.addList(Vector::new); + + + db.addCollection(HashSet::new); + + db.addCollection(LinkedHashSet::new); + + db.addCollection(TreeSet::new); + + + db.addCollection(c -> { Stack<Integer> s = new Stack<>(); s.addAll(c); return s;}); + + db.addCollection(PriorityQueue::new); + + // ArrayDeque fails some tests since it's fail-fast support is weaker + // than other collections and limited to detecting most, but not all, + // removals. It probably requires it's own test since it is difficult + // to abstract out the conditions under which it fails-fast. +// db.addCollection(ArrayDeque::new); + + // Maps + + db.addMap(HashMap::new); + + db.addMap(LinkedHashMap::new); + + // This fails when run through jrteg but passes when run though + // ant +// db.addMap(IdentityHashMap::new); + + db.addMap(WeakHashMap::new); + + // @@@ Descending maps etc + db.addMap(TreeMap::new); + + return spliteratorDataProvider = data.toArray(new Object[0][]); + } + + @Test(dataProvider = "Source") + public <T> void lateBindingTestWithForEach(String description, Supplier<Source<T>> ss) { + Source<T> source = ss.get(); + Collection<T> c = source.asCollection(); + Spliterator<T> s = c.spliterator(); + + source.update(); + + Set<T> r = new HashSet<>(); + s.forEachRemaining(r::add); + + assertEquals(r, new HashSet<>(c)); + } + + @Test(dataProvider = "Source") + public <T> void lateBindingTestWithTryAdvance(String description, Supplier<Source<T>> ss) { + Source<T> source = ss.get(); + Collection<T> c = source.asCollection(); + Spliterator<T> s = c.spliterator(); + + source.update(); + + Set<T> r = new HashSet<>(); + while (s.tryAdvance(r::add)) { } + + assertEquals(r, new HashSet<>(c)); + } + + @Test(dataProvider = "Source") + public <T> void lateBindingTestWithCharacteritics(String description, Supplier<Source<T>> ss) { + Source<T> source = ss.get(); + Collection<T> c = source.asCollection(); + Spliterator<T> s = c.spliterator(); + s.characteristics(); + + Set<T> r = new HashSet<>(); + s.forEachRemaining(r::add); + + assertEquals(r, new HashSet<>(c)); + } + + + @Test(dataProvider = "Source") + public <T> void testFailFastTestWithTryAdvance(String description, Supplier<Source<T>> ss) { + { + Source<T> source = ss.get(); + Collection<T> c = source.asCollection(); + Spliterator<T> s = c.spliterator(); + + s.tryAdvance(e -> { + }); + source.update(); + + executeAndCatch(() -> s.tryAdvance(e -> { })); + } + + { + Source<T> source = ss.get(); + Collection<T> c = source.asCollection(); + Spliterator<T> s = c.spliterator(); + + s.tryAdvance(e -> { + }); + source.update(); + + executeAndCatch(() -> s.forEachRemaining(e -> { + })); + } + } + + @Test(dataProvider = "Source") + public <T> void testFailFastTestWithForEach(String description, Supplier<Source<T>> ss) { + Source<T> source = ss.get(); + Collection<T> c = source.asCollection(); + Spliterator<T> s = c.spliterator(); + + executeAndCatch(() -> s.forEachRemaining(e -> { + source.update(); + })); + } + + @Test(dataProvider = "Source") + public <T> void testFailFastTestWithEstimateSize(String description, Supplier<Source<T>> ss) { + { + Source<T> source = ss.get(); + Collection<T> c = source.asCollection(); + Spliterator<T> s = c.spliterator(); + + s.estimateSize(); + source.update(); + + executeAndCatch(() -> s.tryAdvance(e -> { })); + } + + { + Source<T> source = ss.get(); + Collection<T> c = source.asCollection(); + Spliterator<T> s = c.spliterator(); + + s.estimateSize(); + source.update(); + + executeAndCatch(() -> s.forEachRemaining(e -> { + })); + } + } + + private void executeAndCatch(Runnable r) { + executeAndCatch(ConcurrentModificationException.class, r); + } + + 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())); + } + +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/util/Spliterator/SpliteratorTraversingAndSplittingTest.java Tue Apr 16 13:51:53 2013 -0400 @@ -0,0 +1,1257 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +/** + * @test + * @summary Spliterator traversing and splitting tests + * @run testng SpliteratorTraversingAndSplittingTest + */ + +import org.testng.annotations.DataProvider; +import org.testng.annotations.Test; + +import java.util.AbstractCollection; +import java.util.AbstractList; +import java.util.AbstractSet; +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collection; +import java.util.Collections; +import java.util.Comparator; +import java.util.Deque; +import java.util.HashMap; +import java.util.HashSet; +import java.util.IdentityHashMap; +import java.util.Iterator; +import java.util.LinkedHashMap; +import java.util.LinkedHashSet; +import java.util.LinkedList; +import java.util.List; +import java.util.Map; +import java.util.PriorityQueue; +import java.util.Set; +import java.util.SortedSet; +import java.util.Spliterator; +import java.util.Spliterators; +import java.util.Stack; +import java.util.TreeMap; +import java.util.TreeSet; +import java.util.Vector; +import java.util.WeakHashMap; +import java.util.concurrent.ArrayBlockingQueue; +import java.util.concurrent.ConcurrentHashMap; +import java.util.concurrent.ConcurrentLinkedQueue; +import java.util.concurrent.ConcurrentSkipListMap; +import java.util.concurrent.ConcurrentSkipListSet; +import java.util.concurrent.CopyOnWriteArrayList; +import java.util.concurrent.CopyOnWriteArraySet; +import java.util.concurrent.LinkedBlockingDeque; +import java.util.concurrent.LinkedBlockingQueue; +import java.util.concurrent.LinkedTransferQueue; +import java.util.concurrent.PriorityBlockingQueue; +import java.util.function.Consumer; +import java.util.function.DoubleConsumer; +import java.util.function.Function; +import java.util.function.IntConsumer; +import java.util.function.LongConsumer; +import java.util.function.Supplier; +import java.util.function.UnaryOperator; + +import static org.testng.Assert.*; +import static org.testng.Assert.assertEquals; + +@Test +public class SpliteratorTraversingAndSplittingTest { + + private static List<Integer> SIZES = Arrays.asList(0, 1, 10, 100, 1000); + + private static class SpliteratorDataBuilder<T> { + List<Object[]> data; + + List<T> exp; + + Map<T, T> mExp; + + SpliteratorDataBuilder(List<Object[]> data, List<T> exp) { + this.data = data; + this.exp = exp; + this.mExp = createMap(exp); + } + + Map<T, T> createMap(List<T> l) { + Map<T, T> m = new LinkedHashMap<>(); + for (T t : l) { + m.put(t, t); + } + return m; + } + + void add(String description, Collection<?> expected, Supplier<Spliterator<?>> s) { + description = joiner(description).toString(); + data.add(new Object[]{description, expected, s}); + } + + void add(String description, Supplier<Spliterator<?>> s) { + add(description, exp, s); + } + + void addCollection(Function<Collection<T>, ? extends Collection<T>> c) { + add("new " + c.apply(Collections.<T>emptyList()).getClass().getName() + ".spliterator()", + () -> c.apply(exp).spliterator()); + } + + void addList(Function<Collection<T>, ? extends List<T>> l) { + // @@@ If collection is instance of List then add sub-list tests + addCollection(l); + } + + void addMap(Function<Map<T, T>, ? extends Map<T, T>> m) { + String description = "new " + m.apply(Collections.<T, T>emptyMap()).getClass().getName(); + add(description + ".keySet().spliterator()", () -> m.apply(mExp).keySet().spliterator()); + add(description + ".values().spliterator()", () -> m.apply(mExp).values().spliterator()); + add(description + ".entrySet().spliterator()", mExp.entrySet(), () -> m.apply(mExp).entrySet().spliterator()); + } + + StringBuilder joiner(String description) { + return new StringBuilder(description). + append(" {"). + append("size=").append(exp.size()). + append("}"); + } + } + + static Object[][] spliteratorDataProvider; + + @DataProvider(name = "Spliterator<Integer>") + public static Object[][] spliteratorDataProvider() { + if (spliteratorDataProvider != null) { + return spliteratorDataProvider; + } + + List<Object[]> data = new ArrayList<>(); + for (int size : SIZES) { + List<Integer> exp = listIntRange(size); + SpliteratorDataBuilder<Integer> db = new SpliteratorDataBuilder<>(data, exp); + + // Direct spliterator methods + + db.add("Spliterators.spliterator(Collection, ...)", + () -> Spliterators.spliterator(exp, 0)); + + db.add("Spliterators.spliterator(Iterator, ...)", + () -> Spliterators.spliterator(exp.iterator(), exp.size(), 0)); + + db.add("Spliterators.spliteratorUnknownSize(Iterator, ...)", + () -> Spliterators.spliteratorUnknownSize(exp.iterator(), 0)); + + db.add("Spliterators.spliterator(Spliterators.iteratorFromSpliterator(Spliterator ), ...)", + () -> Spliterators.spliterator(Spliterators.iteratorFromSpliterator(exp.spliterator()), exp.size(), 0)); + + db.add("Spliterators.spliterator(T[], ...)", + () -> Spliterators.spliterator(exp.toArray(new Integer[0]), 0)); + + db.add("Arrays.spliterator(T[], ...)", + () -> Arrays.spliterator(exp.toArray(new Integer[0]))); + + class SpliteratorFromIterator extends Spliterators.AbstractSpliterator<Integer> { + Iterator<Integer> it; + + SpliteratorFromIterator(Iterator<Integer> it, long est) { + super(est, Spliterator.SIZED); + this.it = it; + } + + @Override + public boolean tryAdvance(Consumer<? super Integer> action) { + if (it.hasNext()) { + action.accept(it.next()); + return true; + } + else { + return false; + } + } + } + db.add("new Spliterators.AbstractAdvancingSpliterator()", + () -> new SpliteratorFromIterator(exp.iterator(), exp.size())); + + // Collections + + // default method implementations + + class AbstractCollectionImpl extends AbstractCollection<Integer> { + Collection<Integer> c; + + AbstractCollectionImpl(Collection<Integer> c) { + this.c = c; + } + + @Override + public Iterator<Integer> iterator() { + return c.iterator(); + } + + @Override + public int size() { + return c.size(); + } + } + db.addCollection( + c -> new AbstractCollectionImpl(c)); + + class AbstractListImpl extends AbstractList<Integer> { + List<Integer> l; + + AbstractListImpl(Collection<Integer> c) { + this.l = new ArrayList<>(c); + } + + @Override + public Integer get(int index) { + return l.get(index); + } + + @Override + public int size() { + return l.size(); + } + } + db.addCollection( + c -> new AbstractListImpl(c)); + + class AbstractSetImpl extends AbstractSet<Integer> { + Set<Integer> s; + + AbstractSetImpl(Collection<Integer> c) { + this.s = new HashSet<>(c); + } + + @Override + public Iterator<Integer> iterator() { + return s.iterator(); + } + + @Override + public int size() { + return s.size(); + } + } + db.addCollection( + c -> new AbstractSetImpl(c)); + + class AbstractSortedSetImpl extends AbstractSet<Integer> implements SortedSet<Integer> { + SortedSet<Integer> s; + + AbstractSortedSetImpl(Collection<Integer> c) { + this.s = new TreeSet<>(c); + } + + @Override + public Iterator<Integer> iterator() { + return s.iterator(); + } + + @Override + public int size() { + return s.size(); + } + + @Override + public Comparator<? super Integer> comparator() { + return s.comparator(); + } + + @Override + public SortedSet<Integer> subSet(Integer fromElement, Integer toElement) { + return s.subSet(fromElement, toElement); + } + + @Override + public SortedSet<Integer> headSet(Integer toElement) { + return s.headSet(toElement); + } + + @Override + public SortedSet<Integer> tailSet(Integer fromElement) { + return s.tailSet(fromElement); + } + + @Override + public Integer first() { + return s.first(); + } + + @Override + public Integer last() { + return s.last(); + } + + @Override + public Spliterator<Integer> spliterator() { + return SortedSet.super.spliterator(); + } + } + db.addCollection( + c -> new AbstractSortedSetImpl(c)); + + // + + db.add("Arrays.asList().spliterator()", + () -> Spliterators.spliterator(Arrays.asList(exp.toArray(new Integer[0])), 0)); + + db.addList(ArrayList::new); + + db.addList(LinkedList::new); + + db.addList(Vector::new); + + + db.addCollection(HashSet::new); + + db.addCollection(LinkedHashSet::new); + + db.addCollection(TreeSet::new); + + + db.addCollection(c -> { Stack<Integer> s = new Stack<>(); s.addAll(c); return s;}); + + db.addCollection(PriorityQueue::new); + + db.addCollection(ArrayDeque::new); + + + db.addCollection(ConcurrentSkipListSet::new); + + if (size > 0) { + db.addCollection(c -> { + ArrayBlockingQueue<Integer> abq = new ArrayBlockingQueue<>(size); + abq.addAll(c); + return abq; + }); + } + + db.addCollection(PriorityBlockingQueue::new); + + db.addCollection(LinkedBlockingQueue::new); + + db.addCollection(LinkedTransferQueue::new); + + db.addCollection(ConcurrentLinkedQueue::new); + + db.addCollection(LinkedBlockingDeque::new); + + db.addCollection(CopyOnWriteArrayList::new); + + db.addCollection(CopyOnWriteArraySet::new); + + if (size == 1) { + db.addCollection(c -> Collections.singleton(exp.get(0))); + db.addCollection(c -> Collections.singletonList(exp.get(0))); + } + + // @@@ Collections.synchronized/unmodifiable/checked wrappers + + // Maps + + db.addMap(HashMap::new); + + db.addMap(LinkedHashMap::new); + + db.addMap(IdentityHashMap::new); + + db.addMap(WeakHashMap::new); + + // @@@ Descending maps etc + db.addMap(TreeMap::new); + + db.addMap(ConcurrentHashMap::new); + + db.addMap(ConcurrentSkipListMap::new); + } + + return spliteratorDataProvider = data.toArray(new Object[0][]); + } + + private static List<Integer> listIntRange(int upTo) { + List<Integer> exp = new ArrayList<>(); + for (int i = 0; i < upTo; i++) + exp.add(i); + return Collections.unmodifiableList(exp); + } + + @Test(dataProvider = "Spliterator<Integer>") + @SuppressWarnings({"unchecked", "rawtypes"}) + public void testForEach(String description, Collection exp, Supplier<Spliterator> s) { + testForEach(exp, s, (Consumer<Object> b) -> b); + } + + @Test(dataProvider = "Spliterator<Integer>") + @SuppressWarnings({"unchecked", "rawtypes"}) + public void testTryAdvance(String description, Collection exp, Supplier<Spliterator> s) { + testTryAdvance(exp, s, (Consumer<Object> b) -> b); + } + + @Test(dataProvider = "Spliterator<Integer>") + @SuppressWarnings({"unchecked", "rawtypes"}) + public void testMixedTryAdvanceForEach(String description, Collection exp, Supplier<Spliterator> s) { + testMixedTryAdvanceForEach(exp, s, (Consumer<Object> b) -> b); + } + + @Test(dataProvider = "Spliterator<Integer>") + @SuppressWarnings({"unchecked", "rawtypes"}) + public void testSplitAfterFullTraversal(String description, Collection exp, Supplier<Spliterator> s) { + testSplitAfterFullTraversal(s, (Consumer<Object> b) -> b); + } + + @Test(dataProvider = "Spliterator<Integer>") + @SuppressWarnings({"unchecked", "rawtypes"}) + public void testSplitOnce(String description, Collection exp, Supplier<Spliterator> s) { + testSplitOnce(exp, s, (Consumer<Object> b) -> b); + } + + @Test(dataProvider = "Spliterator<Integer>") + @SuppressWarnings({"unchecked", "rawtypes"}) + public void testSplitSixDeep(String description, Collection exp, Supplier<Spliterator> s) { + testSplitSixDeep(exp, s, (Consumer<Object> b) -> b); + } + + @Test(dataProvider = "Spliterator<Integer>") + @SuppressWarnings({"unchecked", "rawtypes"}) + public void testSplitUntilNull(String description, Collection exp, Supplier<Spliterator> s) { + testSplitUntilNull(exp, s, (Consumer<Object> b) -> b); + } + + // + + private static class SpliteratorOfIntDataBuilder { + List<Object[]> data; + + List<Integer> exp; + + SpliteratorOfIntDataBuilder(List<Object[]> data, List<Integer> exp) { + this.data = data; + this.exp = exp; + } + + void add(String description, List<Integer> expected, Supplier<Spliterator.OfInt> s) { + description = joiner(description).toString(); + data.add(new Object[]{description, expected, s}); + } + + void add(String description, Supplier<Spliterator.OfInt> s) { + add(description, exp, s); + } + + StringBuilder joiner(String description) { + return new StringBuilder(description). + append(" {"). + append("size=").append(exp.size()). + append("}"); + } + } + + static Object[][] spliteratorOfIntDataProvider; + + @DataProvider(name = "Spliterator.OfInt") + public static Object[][] spliteratorOfIntDataProvider() { + if (spliteratorOfIntDataProvider != null) { + return spliteratorOfIntDataProvider; + } + + List<Object[]> data = new ArrayList<>(); + for (int size : SIZES) { + int exp[] = arrayIntRange(size); + SpliteratorOfIntDataBuilder db = new SpliteratorOfIntDataBuilder(data, listIntRange(size)); + + db.add("Spliterators.spliterator(int[], ...)", + () -> Spliterators.spliterator(exp, 0)); + + db.add("Arrays.spliterator(int[], ...)", + () -> Arrays.spliterator(exp)); + + db.add("Spliterators.spliterator(PrimitiveIterator.OfInt, ...)", + () -> Spliterators.spliterator(Spliterators.iteratorFromSpliterator(Arrays.spliterator(exp)), exp.length, 0)); + + db.add("Spliterators.spliteratorUnknownSize(PrimitiveIterator.OfInt, ...)", + () -> Spliterators.spliteratorUnknownSize(Spliterators.iteratorFromSpliterator(Arrays.spliterator(exp)), 0)); + + class IntSpliteratorFromArray extends Spliterators.AbstractIntSpliterator { + int[] a; + int index = 0; + + IntSpliteratorFromArray(int[] a) { + super(a.length, Spliterator.SIZED); + this.a = a; + } + + @Override + public boolean tryAdvance(IntConsumer action) { + if (index < a.length) { + action.accept(a[index++]); + return true; + } + else { + return false; + } + } + } + db.add("new Spliterators.AbstractIntAdvancingSpliterator()", + () -> new IntSpliteratorFromArray(exp)); + } + + return spliteratorOfIntDataProvider = data.toArray(new Object[0][]); + } + + private static int[] arrayIntRange(int upTo) { + int[] exp = new int[upTo]; + for (int i = 0; i < upTo; i++) + exp[i] = i; + return exp; + } + + private static UnaryOperator<Consumer<Integer>> intBoxingConsumer() { + class BoxingAdapter implements Consumer<Integer>, IntConsumer { + private final Consumer<Integer> b; + + BoxingAdapter(Consumer<Integer> b) { + this.b = b; + } + + @Override + public void accept(Integer value) { + throw new IllegalStateException(); + } + + @Override + public void accept(int value) { + b.accept(value); + } + } + + return b -> new BoxingAdapter(b); + } + + @Test(dataProvider = "Spliterator.OfInt") + public void testIntForEach(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) { + testForEach(exp, s, intBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfInt") + public void testIntTryAdvance(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) { + testTryAdvance(exp, s, intBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfInt") + public void testIntMixedTryAdvanceForEach(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) { + testMixedTryAdvanceForEach(exp, s, intBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfInt") + public void testIntSplitAfterFullTraversal(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) { + testSplitAfterFullTraversal(s, intBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfInt") + public void testIntSplitOnce(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) { + testSplitOnce(exp, s, intBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfInt") + public void testIntSplitSixDeep(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) { + testSplitSixDeep(exp, s, intBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfInt") + public void testIntSplitUntilNull(String description, Collection<Integer> exp, Supplier<Spliterator.OfInt> s) { + testSplitUntilNull(exp, s, intBoxingConsumer()); + } + + // + + private static class SpliteratorOfLongDataBuilder { + List<Object[]> data; + + List<Long> exp; + + SpliteratorOfLongDataBuilder(List<Object[]> data, List<Long> exp) { + this.data = data; + this.exp = exp; + } + + void add(String description, List<Long> expected, Supplier<Spliterator.OfLong> s) { + description = joiner(description).toString(); + data.add(new Object[]{description, expected, s}); + } + + void add(String description, Supplier<Spliterator.OfLong> s) { + add(description, exp, s); + } + + StringBuilder joiner(String description) { + return new StringBuilder(description). + append(" {"). + append("size=").append(exp.size()). + append("}"); + } + } + + static Object[][] spliteratorOfLongDataProvider; + + @DataProvider(name = "Spliterator.OfLong") + public static Object[][] spliteratorOfLongDataProvider() { + if (spliteratorOfLongDataProvider != null) { + return spliteratorOfLongDataProvider; + } + + List<Object[]> data = new ArrayList<>(); + for (int size : SIZES) { + long exp[] = arrayLongRange(size); + SpliteratorOfLongDataBuilder db = new SpliteratorOfLongDataBuilder(data, listLongRange(size)); + + db.add("Spliterators.spliterator(long[], ...)", + () -> Spliterators.spliterator(exp, 0)); + + db.add("Arrays.spliterator(long[], ...)", + () -> Arrays.spliterator(exp)); + + db.add("Spliterators.spliterator(PrimitiveIterator.OfLong, ...)", + () -> Spliterators.spliterator(Spliterators.iteratorFromSpliterator(Arrays.spliterator(exp)), exp.length, 0)); + + db.add("Spliterators.spliteratorUnknownSize(PrimitiveIterator.OfLong, ...)", + () -> Spliterators.spliteratorUnknownSize(Spliterators.iteratorFromSpliterator(Arrays.spliterator(exp)), 0)); + + class LongSpliteratorFromArray extends Spliterators.AbstractLongSpliterator { + long[] a; + int index = 0; + + LongSpliteratorFromArray(long[] a) { + super(a.length, Spliterator.SIZED); + this.a = a; + } + + @Override + public boolean tryAdvance(LongConsumer action) { + if (index < a.length) { + action.accept(a[index++]); + return true; + } + else { + return false; + } + } + } + db.add("new Spliterators.AbstractLongAdvancingSpliterator()", + () -> new LongSpliteratorFromArray(exp)); + } + + return spliteratorOfLongDataProvider = data.toArray(new Object[0][]); + } + + private static List<Long> listLongRange(int upTo) { + List<Long> exp = new ArrayList<>(); + for (long i = 0; i < upTo; i++) + exp.add(i); + return Collections.unmodifiableList(exp); + } + + private static long[] arrayLongRange(int upTo) { + long[] exp = new long[upTo]; + for (int i = 0; i < upTo; i++) + exp[i] = i; + return exp; + } + + private static UnaryOperator<Consumer<Long>> longBoxingConsumer() { + class BoxingAdapter implements Consumer<Long>, LongConsumer { + private final Consumer<Long> b; + + BoxingAdapter(Consumer<Long> b) { + this.b = b; + } + + @Override + public void accept(Long value) { + throw new IllegalStateException(); + } + + @Override + public void accept(long value) { + b.accept(value); + } + } + + return b -> new BoxingAdapter(b); + } + + @Test(dataProvider = "Spliterator.OfLong") + public void testLongForEach(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) { + testForEach(exp, s, longBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfLong") + public void testLongTryAdvance(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) { + testTryAdvance(exp, s, longBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfLong") + public void testLongMixedTryAdvanceForEach(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) { + testMixedTryAdvanceForEach(exp, s, longBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfLong") + public void testLongSplitAfterFullTraversal(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) { + testSplitAfterFullTraversal(s, longBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfLong") + public void testLongSplitOnce(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) { + testSplitOnce(exp, s, longBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfLong") + public void testLongSplitSixDeep(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) { + testSplitSixDeep(exp, s, longBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfLong") + public void testLongSplitUntilNull(String description, Collection<Long> exp, Supplier<Spliterator.OfLong> s) { + testSplitUntilNull(exp, s, longBoxingConsumer()); + } + + // + + private static class SpliteratorOfDoubleDataBuilder { + List<Object[]> data; + + List<Double> exp; + + SpliteratorOfDoubleDataBuilder(List<Object[]> data, List<Double> exp) { + this.data = data; + this.exp = exp; + } + + void add(String description, List<Double> expected, Supplier<Spliterator.OfDouble> s) { + description = joiner(description).toString(); + data.add(new Object[]{description, expected, s}); + } + + void add(String description, Supplier<Spliterator.OfDouble> s) { + add(description, exp, s); + } + + StringBuilder joiner(String description) { + return new StringBuilder(description). + append(" {"). + append("size=").append(exp.size()). + append("}"); + } + } + + static Object[][] spliteratorOfDoubleDataProvider; + + @DataProvider(name = "Spliterator.OfDouble") + public static Object[][] spliteratorOfDoubleDataProvider() { + if (spliteratorOfDoubleDataProvider != null) { + return spliteratorOfDoubleDataProvider; + } + + List<Object[]> data = new ArrayList<>(); + for (int size : SIZES) { + double exp[] = arrayDoubleRange(size); + SpliteratorOfDoubleDataBuilder db = new SpliteratorOfDoubleDataBuilder(data, listDoubleRange(size)); + + db.add("Spliterators.spliterator(double[], ...)", + () -> Spliterators.spliterator(exp, 0)); + + db.add("Arrays.spliterator(double[], ...)", + () -> Arrays.spliterator(exp)); + + db.add("Spliterators.spliterator(PrimitiveIterator.OfDouble, ...)", + () -> Spliterators.spliterator(Spliterators.iteratorFromSpliterator(Arrays.spliterator(exp)), exp.length, 0)); + + db.add("Spliterators.spliteratorUnknownSize(PrimitiveIterator.OfDouble, ...)", + () -> Spliterators.spliteratorUnknownSize(Spliterators.iteratorFromSpliterator(Arrays.spliterator(exp)), 0)); + + class DoubleSpliteratorFromArray extends Spliterators.AbstractDoubleSpliterator { + double[] a; + int index = 0; + + DoubleSpliteratorFromArray(double[] a) { + super(a.length, Spliterator.SIZED); + this.a = a; + } + + @Override + public boolean tryAdvance(DoubleConsumer action) { + if (index < a.length) { + action.accept(a[index++]); + return true; + } + else { + return false; + } + } + } + db.add("new Spliterators.AbstractDoubleAdvancingSpliterator()", + () -> new DoubleSpliteratorFromArray(exp)); + } + + return spliteratorOfDoubleDataProvider = data.toArray(new Object[0][]); + } + + private static List<Double> listDoubleRange(int upTo) { + List<Double> exp = new ArrayList<>(); + for (double i = 0; i < upTo; i++) + exp.add(i); + return Collections.unmodifiableList(exp); + } + + private static double[] arrayDoubleRange(int upTo) { + double[] exp = new double[upTo]; + for (int i = 0; i < upTo; i++) + exp[i] = i; + return exp; + } + + private static UnaryOperator<Consumer<Double>> doubleBoxingConsumer() { + class BoxingAdapter implements Consumer<Double>, DoubleConsumer { + private final Consumer<Double> b; + + BoxingAdapter(Consumer<Double> b) { + this.b = b; + } + + @Override + public void accept(Double value) { + throw new IllegalStateException(); + } + + @Override + public void accept(double value) { + b.accept(value); + } + } + + return b -> new BoxingAdapter(b); + } + + @Test(dataProvider = "Spliterator.OfDouble") + public void testDoubleForEach(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) { + testForEach(exp, s, doubleBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfDouble") + public void testDoubleTryAdvance(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) { + testTryAdvance(exp, s, doubleBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfDouble") + public void testDoubleMixedTryAdvanceForEach(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) { + testMixedTryAdvanceForEach(exp, s, doubleBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfDouble") + public void testDoubleSplitAfterFullTraversal(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) { + testSplitAfterFullTraversal(s, doubleBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfDouble") + public void testDoubleSplitOnce(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) { + testSplitOnce(exp, s, doubleBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfDouble") + public void testDoubleSplitSixDeep(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) { + testSplitSixDeep(exp, s, doubleBoxingConsumer()); + } + + @Test(dataProvider = "Spliterator.OfDouble") + public void testDoubleSplitUntilNull(String description, Collection<Double> exp, Supplier<Spliterator.OfDouble> s) { + testSplitUntilNull(exp, s, doubleBoxingConsumer()); + } + + // + + private static <T, S extends Spliterator<T>> void testForEach( + Collection<T> exp, + Supplier<S> supplier, + UnaryOperator<Consumer<T>> boxingAdapter) { + S spliterator = supplier.get(); + long sizeIfKnown = spliterator.getExactSizeIfKnown(); + boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED); + + ArrayList<T> fromForEach = new ArrayList<>(); + spliterator = supplier.get(); + Consumer<T> addToFromForEach = boxingAdapter.apply(fromForEach::add); + spliterator.forEachRemaining(addToFromForEach); + + // Assert that forEach now produces no elements + spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e))); + // Assert that tryAdvance now produce no elements + spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e))); + + // assert that size, tryAdvance, and forEach are consistent + if (sizeIfKnown >= 0) { + assertEquals(sizeIfKnown, exp.size()); + } + assertEquals(fromForEach.size(), exp.size()); + + assertContents(fromForEach, exp, isOrdered); + } + + private static <T, S extends Spliterator<T>> void testTryAdvance( + Collection<T> exp, + Supplier<S> supplier, + UnaryOperator<Consumer<T>> boxingAdapter) { + S spliterator = supplier.get(); + long sizeIfKnown = spliterator.getExactSizeIfKnown(); + boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED); + + spliterator = supplier.get(); + ArrayList<T> fromTryAdvance = new ArrayList<>(); + Consumer<T> addToFromTryAdvance = boxingAdapter.apply(fromTryAdvance::add); + while (spliterator.tryAdvance(addToFromTryAdvance)) { } + + // Assert that forEach now produces no elements + spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e))); + // Assert that tryAdvance now produce no elements + spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e))); + + // assert that size, tryAdvance, and forEach are consistent + if (sizeIfKnown >= 0) { + assertEquals(sizeIfKnown, exp.size()); + } + assertEquals(fromTryAdvance.size(), exp.size()); + + assertContents(fromTryAdvance, exp, isOrdered); + } + + private static <T, S extends Spliterator<T>> void testMixedTryAdvanceForEach( + Collection<T> exp, + Supplier<S> supplier, + UnaryOperator<Consumer<T>> boxingAdapter) { + S spliterator = supplier.get(); + long sizeIfKnown = spliterator.getExactSizeIfKnown(); + boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED); + + // tryAdvance first few elements, then forEach rest + ArrayList<T> dest = new ArrayList<>(); + spliterator = supplier.get(); + Consumer<T> addToDest = boxingAdapter.apply(dest::add); + for (int i = 0; i < 10 && spliterator.tryAdvance(addToDest); i++) { } + spliterator.forEachRemaining(addToDest); + + // Assert that forEach now produces no elements + spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e))); + // Assert that tryAdvance now produce no elements + spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e))); + + if (sizeIfKnown >= 0) { + assertEquals(sizeIfKnown, dest.size()); + } + assertEquals(dest.size(), exp.size()); + + if (isOrdered) { + assertEquals(dest, exp); + } + else { + assertContentsUnordered(dest, exp); + } + } + + private static <T, S extends Spliterator<T>> void testSplitAfterFullTraversal( + Supplier<S> supplier, + UnaryOperator<Consumer<T>> boxingAdapter) { + // Full traversal using tryAdvance + Spliterator<T> spliterator = supplier.get(); + while (spliterator.tryAdvance(boxingAdapter.apply(e -> { }))) { } + Spliterator<T> split = spliterator.trySplit(); + assertNull(split); + + // Full traversal using forEach + spliterator = supplier.get(); + spliterator.forEachRemaining(boxingAdapter.apply(e -> { + })); + split = spliterator.trySplit(); + assertNull(split); + + // Full traversal using tryAdvance then forEach + spliterator = supplier.get(); + spliterator.tryAdvance(boxingAdapter.apply(e -> { })); + spliterator.forEachRemaining(boxingAdapter.apply(e -> { + })); + split = spliterator.trySplit(); + assertNull(split); + } + + private static <T, S extends Spliterator<T>> void testSplitOnce( + Collection<T> exp, + Supplier<S> supplier, + UnaryOperator<Consumer<T>> boxingAdapter) { + S spliterator = supplier.get(); + long sizeIfKnown = spliterator.getExactSizeIfKnown(); + boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED); + + ArrayList<T> fromSplit = new ArrayList<>(); + Spliterator<T> s1 = supplier.get(); + Spliterator<T> s2 = s1.trySplit(); + long s1Size = s1.getExactSizeIfKnown(); + long s2Size = (s2 != null) ? s2.getExactSizeIfKnown() : 0; + Consumer<T> addToFromSplit = boxingAdapter.apply(fromSplit::add); + if (s2 != null) + s2.forEachRemaining(addToFromSplit); + s1.forEachRemaining(addToFromSplit); + + if (sizeIfKnown >= 0) { + assertEquals(sizeIfKnown, fromSplit.size()); + if (s1Size >= 0 && s2Size >= 0) + assertEquals(sizeIfKnown, s1Size + s2Size); + } + assertContents(fromSplit, exp, isOrdered); + } + + private static <T, S extends Spliterator<T>> void testSplitSixDeep( + Collection<T> exp, + Supplier<S> supplier, + UnaryOperator<Consumer<T>> boxingAdapter) { + S spliterator = supplier.get(); + boolean isOrdered = spliterator.hasCharacteristics(Spliterator.ORDERED); + + for (int depth=0; depth < 6; depth++) { + List<T> dest = new ArrayList<>(); + spliterator = supplier.get(); + + assertSpliterator(spliterator); + + // verify splitting with forEach + visit(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), false); + assertContents(dest, exp, isOrdered); + + // verify splitting with tryAdvance + dest.clear(); + spliterator = supplier.get(); + visit(depth, 0, dest, spliterator, boxingAdapter, spliterator.characteristics(), true); + assertContents(dest, exp, isOrdered); + } + } + + 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) { + if (curLevel < depth) { + long beforeSize = spliterator.getExactSizeIfKnown(); + Spliterator<T> split = spliterator.trySplit(); + if (split != null) { + assertSpliterator(split, rootCharacteristics); + assertSpliterator(spliterator, rootCharacteristics); + + if ((rootCharacteristics & Spliterator.SUBSIZED) != 0 && + (rootCharacteristics & Spliterator.SIZED) != 0) { + assertEquals(beforeSize, split.estimateSize() + spliterator.estimateSize()); + } + visit(depth, curLevel + 1, dest, split, boxingAdapter, rootCharacteristics, useTryAdvance); + } + visit(depth, curLevel + 1, dest, spliterator, boxingAdapter, rootCharacteristics, useTryAdvance); + } + else { + long sizeIfKnown = spliterator.getExactSizeIfKnown(); + if (useTryAdvance) { + Consumer<T> addToDest = boxingAdapter.apply(dest::add); + int count = 0; + while (spliterator.tryAdvance(addToDest)) { + ++count; + } + + if (sizeIfKnown >= 0) + assertEquals(sizeIfKnown, count); + + // Assert that forEach now produces no elements + spliterator.forEachRemaining(boxingAdapter.apply(e -> fail("Spliterator.forEach produced an element after spliterator exhausted: " + e))); + + Spliterator<T> split = spliterator.trySplit(); + assertNull(split); + } + else { + List<T> leafDest = new ArrayList<>(); + Consumer<T> addToLeafDest = boxingAdapter.apply(leafDest::add); + spliterator.forEachRemaining(addToLeafDest); + + if (sizeIfKnown >= 0) + assertEquals(sizeIfKnown, leafDest.size()); + + // Assert that forEach now produces no elements + spliterator.tryAdvance(boxingAdapter.apply(e -> fail("Spliterator.tryAdvance produced an element after spliterator exhausted: " + e))); + + Spliterator<T> split = spliterator.trySplit(); + assertNull(split); + + dest.addAll(leafDest); + } + } + } + + private static <T, S extends Spliterator<T>> void testSplitUntilNull( + Collection<T> exp, + Supplier<S> supplier, + UnaryOperator<Consumer<T>> boxingAdapter) { + Spliterator<T> s = supplier.get(); + boolean isOrdered = s.hasCharacteristics(Spliterator.ORDERED); + assertSpliterator(s); + + List<T> splits = new ArrayList<>(); + Consumer<T> c = boxingAdapter.apply(splits::add); + + testSplitUntilNull(new SplitNode<T>(c, s)); + assertContents(splits, exp, isOrdered); + } + + private static class SplitNode<T> { + // Constant for every node + final Consumer<T> c; + final int rootCharacteristics; + + final Spliterator<T> s; + + SplitNode(Consumer<T> c, Spliterator<T> s) { + this(c, s.characteristics(), s); + } + + private SplitNode(Consumer<T> c, int rootCharacteristics, Spliterator<T> s) { + this.c = c; + this.rootCharacteristics = rootCharacteristics; + this.s = s; + } + + SplitNode<T> fromSplit(Spliterator<T> split) { + return new SplitNode<>(c, rootCharacteristics, split); + } + } + + /** + * Set the maximum stack capacity to 0.25MB. This should be more than enough to detect a bad spliterator + * while not unduly disrupting test infrastructure given the test data sizes that are used are small. + * Note that j.u.c.ForkJoinPool sets the max queue size to 64M (1 << 26). + */ + private static final int MAXIMUM_STACK_CAPACITY = 1 << 18; // 0.25MB + + private static <T> void testSplitUntilNull(SplitNode<T> e) { + // Use an explicit stack to avoid a StackOverflowException when testing a Spliterator + // that when repeatedly split produces a right-balanced (and maybe degenerate) tree, or + // for a spliterator that is badly behaved. + Deque<SplitNode<T>> stack = new ArrayDeque<>(); + stack.push(e); + + int iteration = 0; + while (!stack.isEmpty()) { + assertTrue(iteration++ < MAXIMUM_STACK_CAPACITY, "Exceeded maximum stack modification count of 1 << 18"); + + e = stack.pop(); + Spliterator<T> parentAndRightSplit = e.s; + + long parentEstimateSize = parentAndRightSplit.estimateSize(); + assertTrue(parentEstimateSize >= 0, + String.format("Split size estimate %d < 0", parentEstimateSize)); + + long parentSize = parentAndRightSplit.getExactSizeIfKnown(); + Spliterator<T> leftSplit = parentAndRightSplit.trySplit(); + if (leftSplit == null) { + parentAndRightSplit.forEachRemaining(e.c); + continue; + } + + assertSpliterator(leftSplit, e.rootCharacteristics); + assertSpliterator(parentAndRightSplit, e.rootCharacteristics); + + if (parentEstimateSize != Long.MAX_VALUE && leftSplit.estimateSize() > 0 && parentAndRightSplit.estimateSize() > 0) { + 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)); + } + else { + 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)); + } + + long leftSize = leftSplit.getExactSizeIfKnown(); + long rightSize = parentAndRightSplit.getExactSizeIfKnown(); + if (parentSize >= 0 && leftSize >= 0 && rightSize >= 0) + assertEquals(parentSize, leftSize + rightSize, + String.format("exact left split size %d + exact right split size %d != parent exact split size %d", + leftSize, rightSize, parentSize)); + + // Add right side to stack first so left side is popped off first + stack.push(e.fromSplit(parentAndRightSplit)); + stack.push(e.fromSplit(leftSplit)); + } + } + + private static void assertSpliterator(Spliterator<?> s, int rootCharacteristics) { + if ((rootCharacteristics & Spliterator.SUBSIZED) != 0) { + assertTrue(s.hasCharacteristics(Spliterator.SUBSIZED), + "Child split is not SUBSIZED when root split is SUBSIZED"); + } + assertSpliterator(s); + } + + private static void assertSpliterator(Spliterator<?> s) { + if (s.hasCharacteristics(Spliterator.SUBSIZED)) { + assertTrue(s.hasCharacteristics(Spliterator.SIZED)); + } + if (s.hasCharacteristics(Spliterator.SIZED)) { + assertTrue(s.estimateSize() != Long.MAX_VALUE); + assertTrue(s.getExactSizeIfKnown() >= 0); + } + try { + s.getComparator(); + assertTrue(s.hasCharacteristics(Spliterator.SORTED)); + } catch (IllegalStateException e) { + assertFalse(s.hasCharacteristics(Spliterator.SORTED)); + } + } + + private static<T> void assertContents(Collection<T> actual, Collection<T> expected, boolean isOrdered) { + if (isOrdered) { + assertEquals(actual, expected); + } + else { + assertContentsUnordered(actual, expected); + } + } + + private static<T> void assertContentsUnordered(Iterable<T> actual, Iterable<T> expected) { + assertEquals(toBoxedMultiset(actual), toBoxedMultiset(expected)); + } + + private static <T> Map<T, Integer> toBoxedMultiset(Iterable<T> c) { + Map<T, Integer> result = new HashMap<>(); + c.forEach(e -> { + if (result.containsKey(e)) result.put(e, result.get(e) + 1); + else result.put(e, 1); + }); + return result; + } +}