changeset 4720:a1a106adff5f

Add Iterable.get{First,Any,Only}; make ParallelIterable.into actually parallel; add Iterable.cumulate
author briangoetz
date Fri, 06 Jan 2012 19:14:40 -0500
parents 7e592a11b492
children 78684ee5be2c
files src/share/classes/java/lang/Iterable.java src/share/classes/java/util/Iterables.java src/share/classes/java/util/Iterators.java src/share/classes/java/util/ParallelIterable.java src/share/classes/java/util/ParallelIterables.java test-ng/tests/java/util/IterableTest.java test-ng/tests/java/util/IterablesTest.java test-ng/tests/java/util/LambdaTestHelpers.java test-ng/tests/java/util/ParallelIterableTest.java
diffstat 9 files changed, 207 insertions(+), 18 deletions(-) [+]
line wrap: on
line diff
--- a/src/share/classes/java/lang/Iterable.java	Fri Dec 30 18:16:05 2011 -0500
+++ b/src/share/classes/java/lang/Iterable.java	Fri Jan 06 19:14:40 2012 -0500
@@ -42,7 +42,6 @@
  * @since 1.5
  */
 public interface Iterable<T> {
-
     /**
      * Returns an iterator over elements of type {@code T}.
      *
@@ -59,6 +58,18 @@
      */
     boolean isEmpty() default { return Iterables.isEmpty(this); };
 
+    T getFirst() default {
+        return Iterables.getFirst(this);
+    }
+
+    T getOnly() default {
+        return Iterables.getOnly(this);
+    }
+
+    T getAny() default {
+        return getFirst();
+    }
+
     /**
      * Filter elements according to the provided {@code predicate} and return a
      * an Iterable view of the filtered elements. The filtered view will reflect
@@ -137,10 +148,13 @@
         return Iterables.mapReduce(this, mapper, base, reducer);
     }
 
-     <U> U filterMapReduce(Predicate<? super T> predicate, Mapper<? super T, ? extends U> mapper,U base, Operator<U> reducer) default {
-         return Iterables.filterMapReduce(this, predicate, mapper, base, reducer);
-     }
+    <U> U filterMapReduce(Predicate<? super T> predicate, Mapper<? super T, ? extends U> mapper,U base, Operator<U> reducer) default {
+        return Iterables.filterMapReduce(this, predicate, mapper, base, reducer);
+    }
 
+    Iterable<T> cumulate(Operator<T> op) default {
+        return Iterables.cumulate(this, op);
+    }
 
     /**
      * All elements are added to the specified collection.
--- a/src/share/classes/java/util/Iterables.java	Fri Dec 30 18:16:05 2011 -0500
+++ b/src/share/classes/java/util/Iterables.java	Fri Jan 06 19:14:40 2012 -0500
@@ -57,9 +57,14 @@
             return Iterators.count(iterable.iterator());
     }
 
-    public static <T> T first(Iterable<T> iterable) {
+    public static <T> T getFirst(Iterable<T> iterable) {
         Objects.requireNonNull(iterable);
-        return iterable.iterator().next();
+        return Iterators.getFirst(iterable.iterator());
+    }
+
+    public static <T> T getOnly(Iterable<T> iterable) {
+        Objects.requireNonNull(iterable);
+        return Iterators.getOnly(iterable.iterator());
     }
 
     // @@@ Mostly for debugging
@@ -258,6 +263,17 @@
         Objects.requireNonNull(operator);
         return Iterators.mapReduce(iterable.iterator(), mapper, base, operator);
     }
+    
+    public static<T> Iterable<T> cumulate(final Iterable<? extends T> iterable, final Operator<T> op) {
+        Objects.requireNonNull(iterable);
+        Objects.requireNonNull(op);
+        return new BaseIterable<T>() {
+            @Override
+            public Iterator<T> iterator() {
+                return Iterators.cumulate(iterable.iterator(), op);
+            }
+        };
+    }
 
     /**
      * All elements of the Iterable are added to the specified container.
--- a/src/share/classes/java/util/Iterators.java	Fri Dec 30 18:16:05 2011 -0500
+++ b/src/share/classes/java/util/Iterators.java	Fri Jan 06 19:14:40 2012 -0500
@@ -39,8 +39,29 @@
         throw new Error("No instances for you!");
     }
 
-    public static <T> void removeUnsupported(Iterator<T> t) {
-        throw new UnsupportedOperationException("remove");
+    public static<T> T getFirst(Iterator<? extends T> iterator) {
+        if (!iterator.hasNext())
+            return null;
+
+        T next = iterator.next();
+        if (next == null)
+            throw new NullPointerException();
+        else
+            return next;
+    }
+
+    public static<T> T getOnly(Iterator<? extends T> iterator) {
+        if (!iterator.hasNext())
+            throw new NoSuchElementException();
+
+        T next = iterator.next();
+        if (next == null)
+            throw new NullPointerException();
+
+        if (iterator.hasNext())
+            throw new IllegalStateException();
+
+        return next;
     }
 
     public static <T> long count(Iterator<? extends T> iterator) {
@@ -226,6 +247,31 @@
         return true;
     }
 
+    public static<T> Iterator<T> cumulate(final Iterator<? extends T> iterator, final Operator<T> op) {
+        Objects.requireNonNull(iterator);
+        Objects.requireNonNull(op);
+        return new Iterator<T>() {
+            boolean first = true;
+            T value;
+
+            @Override
+            public boolean hasNext() {
+                return iterator.hasNext();
+            }
+
+            @Override
+            public T next() {
+                if (first) {
+                    value = iterator.next();
+                    first = false;
+                }
+                else
+                    value = op.eval(value, iterator.next());
+                return value;
+            }
+        };
+    }
+
     public static <T> Iterator<T> sorted(Iterator<? extends T> iterator) {
         Objects.requireNonNull(iterator);
         final PriorityQueue<T> pq = new PriorityQueue<>();
--- a/src/share/classes/java/util/ParallelIterable.java	Fri Dec 30 18:16:05 2011 -0500
+++ b/src/share/classes/java/util/ParallelIterable.java	Fri Jan 06 19:14:40 2012 -0500
@@ -20,6 +20,18 @@
         return ParallelIterables.isEmpty(this);
     }
 
+    T getFirst() default {
+        return ParallelIterables.getFirst(this);
+    }
+
+    T getAny() default {
+        return ParallelIterables.getAny(this);
+    }
+
+    T getOnly() default {
+        return ParallelIterables.getOnly(this);
+    }
+
     /**
      * Filter elements according to the provided {@code predicate} and return a
      * an Iterable view of the filtered elements. The filtered view will reflect
--- a/src/share/classes/java/util/ParallelIterables.java	Fri Dec 30 18:16:05 2011 -0500
+++ b/src/share/classes/java/util/ParallelIterables.java	Fri Jan 06 19:14:40 2012 -0500
@@ -37,6 +37,22 @@
         return d;
     }
 
+    public static<T> T getFirst(ParallelIterable<T> iterable) {
+        Objects.requireNonNull(iterable);
+        // @@@ don't forget cancellation of remaining tasks after getting the first one
+        return iterable.sequential().getFirst();
+    }
+
+    public static<T> T getAny(ParallelIterable<T> iterable) {
+        Objects.requireNonNull(iterable);
+        throw new UnsupportedOperationException();
+    }
+
+    public static<T> T getOnly(ParallelIterable<T> iterable) {
+        Objects.requireNonNull(iterable);
+        return iterable.sequential().getOnly();
+    }
+
     private static abstract class BaseTask<T, S extends BaseTask<T, S>> extends RecursiveAction {
         public final int depth;
         public final ParallelIterable<T> coll;
@@ -555,14 +571,36 @@
      * @param target The collection other container into which the elements are added.
      * @return The provided container.
      */
-    public static <T, A extends Fillable<? super T>> A into(ParallelIterable<T> pi, A target) {
-        // Current implementation is sequential, pending more analysis on encounter-order-preservation
+    public static <T, A extends Fillable<? super T>> A into(ParallelIterable<T> pi, final A target) {
         Objects.requireNonNull(pi);
         Objects.requireNonNull(target);
-        target.addAll(pi.sequential());
+
+        ForkJoinUtils.defaultFJPool().invoke(new IntoTask<>(calculateDepth(pi.estimateCount()), pi, target));
         return target;
     }
 
+    private static class IntoTask<T> extends BaseTask<T, IntoTask<T>> {
+        private final Fillable<? super T> target;
+        
+        IntoTask(int depth, ParallelIterable<T> coll, Fillable<? super T> target) {
+            super(depth, coll);
+            this.target = target;
+        }
+
+        @Override
+        public void seq() {
+            Iterable<T> it = () -> coll.iterator(); // @@@ compiler bug workaround
+            synchronized (target) {
+                target.addAll(it);
+            }
+        }
+
+        @Override
+        public IntoTask<T> makeTask(int depth, ParallelIterable<T> coll) {
+            return new IntoTask<>(depth, coll, target);
+        }
+    }
+
     // TODO: better short-circuiting
     private static class MatchTask<T> extends BaseTask<T, MatchTask<T>> {
         private static final long serialVersionUID = 1L;
--- a/test-ng/tests/java/util/IterableTest.java	Fri Dec 30 18:16:05 2011 -0500
+++ b/test-ng/tests/java/util/IterableTest.java	Fri Jan 06 19:14:40 2012 -0500
@@ -42,6 +42,27 @@
         assertFalse(countTo(10).isEmpty());
     }
 
+    public void testFirst() {
+        assertEquals(null, countTo(0).getFirst());
+        assertEquals(1, (int) countTo(1).getFirst());
+        assertEquals(null, countTo(0).getAny());
+        assertEquals(1, (int) countTo(1).getAny());
+    }
+
+    @Test(expectedExceptions = NoSuchElementException.class)
+    public void testOnlyEmpty() {
+        Integer i = countTo(0).getOnly();
+    }
+
+    @Test(expectedExceptions = IllegalStateException.class)
+    public void testOnlyTooBig() {
+        Integer i = countTo(10).getOnly();
+    }
+
+    public void testOnly() {
+        assertEquals(1, (int) countTo(1).getOnly());
+    }
+
     public void testFilter() {
         Iterable<Integer> evens = countTo(10).filter(pEven);
         Iterable<Integer> odds = countTo(10).filter(pOdd);
@@ -124,6 +145,12 @@
         assertEquals(0, (int) countTo(0).reduce(0, rPlus));
     }
 
+    public void testCumulate() {
+        assertTrue(countTo(0).cumulate(Math::max).isEmpty());
+        assertContents(countTo(10), countTo(10).cumulate(Math::max));
+        assertContents(countTo(10).cumulate(rPlus), Arrays.asList(1, 3, 6, 10, 15, 21, 28, 36, 45, 55));
+    }
+
     // This test used to fail due to a weaver bug having to do with local variable table offsets in the presence of longs
     // If you find this test failing, you need to update your jsr335-agent.jar
     public void testMapReduce() {
--- a/test-ng/tests/java/util/IterablesTest.java	Fri Dec 30 18:16:05 2011 -0500
+++ b/test-ng/tests/java/util/IterablesTest.java	Fri Jan 06 19:14:40 2012 -0500
@@ -27,7 +27,6 @@
 import org.testng.annotations.Test;
 
 import java.util.concurrent.atomic.AtomicInteger;
-import java.util.functions.Mapper;
 
 import static java.util.LambdaTestHelpers.*;
 import static org.testng.Assert.*;
@@ -51,8 +50,8 @@
     }
 
     public void testFirst() {
-        assertEquals(1, (int) Iterables.first(countTo(1)));
-        assertEquals(1, (int) Iterables.first(countTo(10)));
+        assertEquals(1, (int) Iterables.getFirst(countTo(1)));
+        assertEquals(1, (int) Iterables.getFirst(countTo(10)));
     }
 
     public void testFilter() {
--- a/test-ng/tests/java/util/LambdaTestHelpers.java	Fri Dec 30 18:16:05 2011 -0500
+++ b/test-ng/tests/java/util/LambdaTestHelpers.java	Fri Jan 06 19:14:40 2012 -0500
@@ -76,6 +76,12 @@
         }
     };
 
+    public static List<Integer> nullStream() {
+        ArrayList<Integer> list = new ArrayList<>();
+        list.add(null);
+        return list;
+    }
+
     public static List<Integer> countTo(int n) {
         ArrayList<Integer> list = new ArrayList<>();
         for (int i=1; i<=n; i++) {
@@ -152,6 +158,31 @@
         assertSorted(iter.iterator(), comp);
     }
 
+    static<T> void assertContents(Iterable<T> pi, Iterable<T> list) {
+        Iterator<T> pI = pi.iterator();
+        Iterator<T> lI = list.iterator();
+
+        while (lI.hasNext()) {
+            assertTrue(pI.hasNext());
+            T pT = pI.next();
+            T lT = lI.next();
+            assertEquals(pT, lT);
+        }
+        assertTrue(!pI.hasNext());
+    }
+
+    static<T extends Comparable<? super T>> void assertContentsUnordered(Iterable<T> it, Iterable<T> list) {
+        ArrayList<T> one = new ArrayList<>();
+        for (T t : it)
+            one.add(t);
+        ArrayList<T> two = new ArrayList<>();
+        for (T t : list)
+            two.add(t);
+        Collections.sort(one);
+        Collections.sort(two);
+        assertContents(one, two);
+    }
+
     static<T> void assertContents(ParallelIterable<T> pi, Iterable<T> list) {
         Iterator<T> pI = pi.sequential().iterator();
         Iterator<T> lI = list.iterator();
--- a/test-ng/tests/java/util/ParallelIterableTest.java	Fri Dec 30 18:16:05 2011 -0500
+++ b/test-ng/tests/java/util/ParallelIterableTest.java	Fri Jan 06 19:14:40 2012 -0500
@@ -35,20 +35,20 @@
         for (Predicate<Integer> p : Arrays.asList(pTrue, pFalse, pEven, pOdd)) {
             assertContents(pi.filter(p), list.filter(p));
             assertContents(pi.filter(p), pi.sequential().filter(p));
-            assertEquals(pi.filter(p).into(new ArrayList<>()), list.filter(p).into(new ArrayList<>()));
+            assertEquals(pi.filter(p).sequential().into(new ArrayList<>()), list.filter(p).into(new ArrayList<>()));
         }
 
         assertContents(pi.filter(pEven).filter(pOdd), Collections.<Integer>emptyList());
         assertContents(pi.filter(pEven).filter(pEven), list.filter(pEven));
         assertContents(pi.filter(pOdd).filter(pOdd), list.filter(pOdd));
-        assertEquals(pi.filter(pEven).into(new ArrayList<>()), list.filter(pEven).into(new ArrayList<>()));
+        assertEquals(pi.filter(pEven).sequential().into(new ArrayList<>()), list.filter(pEven).into(new ArrayList<>()));
     }
 
     @Test(dataProvider = "lists")
     public void testMap(List<Integer> list, ParallelIterable<Integer> pi) {
         assertContents(pi.map(mDoubler), list.map(mDoubler));
         assertContents(pi.map(mDoubler), pi.sequential().map(mDoubler));
-        assertEquals(pi.map(mDoubler).into(new ArrayList<>()), list.map(mDoubler).into(new ArrayList<>()));
+        assertEquals(pi.map(mDoubler).sequential().into(new ArrayList<>()), list.map(mDoubler).into(new ArrayList<>()));
     }
 
     @Test(dataProvider = "lists")
@@ -69,7 +69,7 @@
         };
         assertContents(pi.flatMap(mIntToBits), list.flatMap(mIntToBits));
         assertContents(pi.flatMap(mIntToBits), pi.sequential().flatMap(mIntToBits));
-        assertEquals(pi.flatMap(mIntToBits).into(new ArrayList<>()), list.flatMap(mIntToBits).into(new ArrayList<>()));
+        assertEquals(pi.flatMap(mIntToBits).sequential().into(new ArrayList<>()), list.flatMap(mIntToBits).into(new ArrayList<>()));
     }
 
     @Test(dataProvider = "lists")
@@ -90,6 +90,12 @@
     }
 
     @Test(dataProvider = "lists")
+    public void testInto(List<Integer> list, ParallelIterable<Integer> pi) {
+        List<Integer> dumped = pi.into(new ArrayList<Integer>());
+        assertContentsUnordered(list, dumped);
+    }
+
+    @Test(dataProvider = "lists")
     public void testMapReduce(List<Integer> list, ParallelIterable<Integer> pi) {
         assertEquals((int) pi.mapReduce(mDoubler, 0, rPlus), (int) list.mapReduce(mDoubler, 0, rPlus));
         assertEquals((int) pi.mapReduce(mDoubler, Integer.MIN_VALUE, rMax), (int) list.mapReduce(mDoubler, Integer.MIN_VALUE, rMax));