PrependAll now only allocates a single Iterable

jnape · jnape · commit 36ecd533f80b · 2017-11-10T19:35:08.000-06:00
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -6,6 +6,7 @@ The format is based on [Keep a Changelog](http://keepachangelog.com/).
 ## [Unreleased]
 ### Fixed
 - `CoProductN#embed` no longer eagerly invokes functions
+- `PrependAll` now only creates `O(1)` `Iterable`s instead of `O(3n + 1)` 
 
 ### Added
 - `Monad` arrives. The following `Applicative`s are now also `Monad`:
diff --git a/src/main/java/com/jnape/palatable/lambda/functions/builtin/fn2/PrependAll.java b/src/main/java/com/jnape/palatable/lambda/functions/builtin/fn2/PrependAll.java
@@ -2,11 +2,7 @@
 
 import com.jnape.palatable.lambda.functions.Fn1;
 import com.jnape.palatable.lambda.functions.Fn2;
-
-import static com.jnape.palatable.lambda.functions.builtin.fn1.Head.head;
-import static com.jnape.palatable.lambda.functions.builtin.fn1.Tail.tail;
-import static com.jnape.palatable.lambda.functions.builtin.fn2.Cons.cons;
-import static java.util.Collections.emptyList;
+import com.jnape.palatable.lambda.iterators.PrependingIterator;
 
 /**
  * Lazily prepend each value with of the <code>Iterable</code> with the supplied separator value. An empty
@@ -24,7 +20,7 @@ private PrependAll() {
 
     @Override
     public Iterable<A> apply(A a, Iterable<A> as) {
-        return () -> head(as).fmap(head -> cons(a, cons(head, prependAll(a, tail(as))))).orElse(emptyList()).iterator();
+        return () -> new PrependingIterator<>(a, as.iterator());
     }
 
     @SuppressWarnings("unchecked")
diff --git a/src/main/java/com/jnape/palatable/lambda/iterators/PrependingIterator.java b/src/main/java/com/jnape/palatable/lambda/iterators/PrependingIterator.java
@@ -0,0 +1,30 @@
+package com.jnape.palatable.lambda.iterators;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+public final class PrependingIterator<A> extends ImmutableIterator<A> {
+
+    private final A           antecedent;
+    private final Iterator<A> iterator;
+    private       boolean     prependNext;
+
+    public PrependingIterator(A antecedent, Iterator<A> iterator) {
+        this.antecedent = antecedent;
+        this.iterator = iterator;
+        prependNext = true;
+    }
+
+    @Override
+    public boolean hasNext() {
+        return iterator.hasNext();
+    }
+
+    @Override
+    public A next() {
+        if (!iterator.hasNext())
+            throw new NoSuchElementException();
+
+        return (prependNext = !prependNext) ? iterator.next() : antecedent;
+    }
+}
diff --git a/src/test/java/com/jnape/palatable/lambda/iterators/PrependingIteratorTest.java b/src/test/java/com/jnape/palatable/lambda/iterators/PrependingIteratorTest.java
@@ -0,0 +1,46 @@
+package com.jnape.palatable.lambda.iterators;
+
+import org.junit.Rule;
+import org.junit.Test;
+import org.junit.rules.ExpectedException;
+
+import java.util.NoSuchElementException;
+
+import static java.util.Arrays.asList;
+import static java.util.Collections.emptyIterator;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+public class PrependingIteratorTest {
+
+    @Rule public ExpectedException thrown = ExpectedException.none();
+
+    @Test
+    public void empty() {
+        PrependingIterator<Integer> iterator = new PrependingIterator<>(0, emptyIterator());
+        assertFalse(iterator.hasNext());
+
+        thrown.expect(NoSuchElementException.class);
+        iterator.next();
+    }
+
+    @Test
+    public void nonEmpty() {
+        PrependingIterator<Integer> iterator = new PrependingIterator<>(0, asList(1, 2, 3).iterator());
+
+        assertTrue(iterator.hasNext());
+        assertEquals((Integer) 0, iterator.next());
+        assertTrue(iterator.hasNext());
+        assertEquals((Integer) 1, iterator.next());
+        assertTrue(iterator.hasNext());
+        assertEquals((Integer) 0, iterator.next());
+        assertTrue(iterator.hasNext());
+        assertEquals((Integer) 2, iterator.next());
+        assertTrue(iterator.hasNext());
+        assertEquals((Integer) 0, iterator.next());
+        assertTrue(iterator.hasNext());
+        assertEquals((Integer) 3, iterator.next());
+        assertFalse(iterator.hasNext());
+    }
+}
