Change shrinking a bit, add more generators, fix some types, moved suchThat

Shrinking is now done using a "ShrinkStrategy". It's pretty similar to what it
used to be in the end, but instead of generating new ShrinkTree<T>s yourself,
you just generate smaller <T>s, and the generator framework will re-call your
strategy to shrink smaller elements. (So, essentially, ShrinkStrategy.shrink(T
obj) returns an Iterator<T> which then has smaller trees calculated from it.)

Added some more generators. In particular: longs and doubles.

Fixed some types, so now Generator.tuple(integer(), string()) will work. Yay!

Move suchThat to Generator, so now integer().suchThat(x -> x < 10) will work
instead of the old Generators.suchThat(x -> x < 10, integer()), which felt a
bit weird.

6 files changed, 183 insertions, 55 deletions

diff --git a/src/main/java/au/id/zancanaro/javacheck/Generator.java b/src/main/java/au/id/zancanaro/javacheck/Generator.java
index 9d88020..103bc69 100644
--- a/src/main/java/au/id/zancanaro/javacheck/Generator.java
+++ b/src/main/java/au/id/zancanaro/javacheck/Generator.java
@@ -4,6 +4,7 @@ import java.util.Iterator;
 import java.util.List;
 import java.util.Random;
 import java.util.function.Function;
+import java.util.function.Predicate;
 
 /**
  * Generators are a way of producing random objects and their associated shrink
@@ -63,13 +64,13 @@ public interface Generator<T> {
      * @return A {@link Generator} returning a {@link List}
      */
     @SafeVarargs
-    static <T> Generator<List<T>> tuple(Generator<T>... generators) {
+    static <T> Generator<List<T>> tuple(Generator<? extends T>... generators) {
         return (random, size) -> {
             @SuppressWarnings("unchecked")
             ShrinkTree<T>[] result = (ShrinkTree<T>[]) new ShrinkTree[generators.length];
             int index = 0;
-            for (Generator<T> generator : generators) {
-                result[index++] = generator.generate(random, size);
+            for (Generator<? extends T> generator : generators) {
+                result[index++] = generator.generate(random, size).map(x -> (T) x);
             }
             return ShrinkTree.zip(Function.identity(), result);
         };
@@ -130,6 +131,31 @@ public interface Generator<T> {
         return (random, size) -> ShrinkTree.join(this.generate(random, size).map(action).map(g -> g.generate(random, size)));
     }
 
+    /**
+     * Filter the results of this generator to only those matching a given
+     * predicate.
+     *
+     * suchThat will keep trying the generator until either it provides a valid
+     * value, or a stack overflow error occurs.
+     *
+     * <b>Only use this method with predicates which are very likely to
+     * match.</b>
+     *
+     * @param predicate The predicate to match
+     * @return A new generator resulting from filtering this generator to only
+     * terms which match the given predicate
+     */
+    default Generator<T> suchThat(Predicate<T> predicate) {
+        return (random, size) -> {
+            ShrinkTree<T> result = this.generate(random, size);
+            if (predicate.test(result.getValue())) {
+                return result.filter(predicate);
+            } else {
+                return this.suchThat(predicate).generate(random, size);
+            }
+        };
+    }
+
     default Iterator<T> sample(Random random, int maxSize) {
         return new GeneratorSampleIterator<>(this, random, maxSize);
     }
diff --git a/src/main/java/au/id/zancanaro/javacheck/GeneratorSampleIterator.java b/src/main/java/au/id/zancanaro/javacheck/GeneratorSampleIterator.java
index f7d8e17..6101d4a 100644
--- a/src/main/java/au/id/zancanaro/javacheck/GeneratorSampleIterator.java
+++ b/src/main/java/au/id/zancanaro/javacheck/GeneratorSampleIterator.java
@@ -3,7 +3,7 @@ package au.id.zancanaro.javacheck;
 import java.util.Iterator;
 import java.util.Random;
 
-public class GeneratorSampleIterator<T> implements Iterator<T> {
+class GeneratorSampleIterator<T> implements Iterator<T> {
     private final Generator<T> generator;
     private final Random random;
     private final int maxSize;
@@ -24,7 +24,7 @@ public class GeneratorSampleIterator<T> implements Iterator<T> {
     @Override
     public T next() {
         return generator
-                .generate(random, Math.min(size++, maxSize))
+                .generate(random, size = Math.min(size + 1, maxSize))
                 .getValue();
     }
 }
diff --git a/src/main/java/au/id/zancanaro/javacheck/Generators.java b/src/main/java/au/id/zancanaro/javacheck/Generators.java
index 5dee924..e5699ac 100644
--- a/src/main/java/au/id/zancanaro/javacheck/Generators.java
+++ b/src/main/java/au/id/zancanaro/javacheck/Generators.java
@@ -1,41 +1,40 @@
 package au.id.zancanaro.javacheck;
 
-import java.util.Arrays;
-import java.util.Collections;
-import java.util.Iterator;
-import java.util.List;
+import java.util.*;
 import java.util.function.Function;
-import java.util.function.Predicate;
 
-@SuppressWarnings("unused")
+@SuppressWarnings({"unused", "WeakerAccess"})
 public final class Generators {
     private Generators() {
     }
 
+    /**
+     * Create a generator which explicitly depends on the current "size"
+     * parameter.
+     *
+     * @param makeGenerator A function from size to a generator
+     * @param <T>           The static type of the returned generator
+     * @return The generator returned by makeGenerator
+     */
     public static <T> Generator<T> sized(Function<Integer, Generator<T>> makeGenerator) {
         return (random, size) -> makeGenerator.apply(size).generate(random, size);
     }
 
-    public static <T> Generator<T> suchThat(Generator<T> gen, Predicate<T> predicate) {
-        return (random, size) -> {
-            ShrinkTree<T> result = gen.generate(random, size);
-            if (predicate.test(result.getValue())) {
-                return result.filter(predicate);
-            } else {
-                return suchThat(gen, predicate).generate(random, size);
-            }
-        };
-    }
-
+    /**
+     * Remove a generator's shrink tree.
+     *
+     * @param gen The generator
+     * @param <T> The generator's static type
+     * @return A new generator which is the previous generator with shrink tree
+     * removed
+     */
     public static <T> Generator<T> noShrink(Generator<T> gen) {
-        return (random, size) -> new ShrinkTree<>(
-                gen.generate(random, size).getValue(),
-                Collections.emptyList());
+        return (random, size) -> ShrinkTree.pure(gen.generate(random, size).getValue());
     }
 
     @SafeVarargs
-    public static <T> Generator<T> oneOf(Generator<T>... gens) {
-        return integer(0, gens.length).flatMap(index -> gens[index]);
+    public static <T> Generator<T> oneOf(Generator<? extends T>... gens) {
+        return integer(0, gens.length).flatMap(index -> gens[index].map(x -> (T) x));
     }
 
     public static <T> Generator<T> elements(T[] elements) {
@@ -48,16 +47,67 @@ public final class Generators {
 
     public static Generator<Boolean> bool() {
         return (random, size) ->
-                random.nextBoolean() ?
-                        new ShrinkTree<>(true, Collections.singletonList(new ShrinkTree<>(false, Collections.emptyList()))) :
-                        new ShrinkTree<>(false, Collections.emptyList());
+                ShrinkTree.pure(random.nextBoolean())
+                        .withShrinkStrategy(boolShrinkStrategy());
+    }
+
+    private static ShrinkStrategy<Boolean> boolShrinkStrategy() {
+        return value -> new Iterator<Boolean>() {
+            boolean hasMore = value;
+
+            @Override
+            public boolean hasNext() {
+                return hasMore;
+            }
+
+            @Override
+            public Boolean next() {
+                if (hasMore) {
+                    return (hasMore = false);
+                } else {
+                    throw new NoSuchElementException("Boolean shrink tree exhausted");
+                }
+            }
+        };
+    }
+
+    public static Generator<Long> longInteger(long lower, long upper) {
+        return (random, size) -> {
+            long value = random.longs(lower, upper).findFirst().getAsLong();
+            long bound = lower > 0 ? lower : (upper < 0 ? upper : 0);
+            return ShrinkTree.pure(value)
+                    .withShrinkStrategy(longShrinkStrategy(bound));
+        };
+    }
+
+    public static Generator<Long> longInteger() {
+        return sized(size -> longInteger(-size, size));
+    }
+
+    private static ShrinkStrategy<Long> longShrinkStrategy(final long bound) {
+        return value -> new Iterator<Long>() {
+            long curr = value - bound;
+
+            @Override
+            public boolean hasNext() {
+                return curr != 0;
+            }
+
+            @Override
+            public Long next() {
+                long prevCurr = curr;
+                curr = curr / 2;
+                return value - prevCurr;
+            }
+        };
     }
 
     public static Generator<Integer> integer(int lower, int upper) {
         return (random, size) -> {
-            int value = lower + random.nextInt(upper - lower);
+            int value = random.ints(lower, upper).findFirst().getAsInt();
             int bound = lower > 0 ? lower : (upper < 0 ? upper : 0);
-            return new ShrinkTree<>(value, intShrinkingIterable(value, bound));
+            return ShrinkTree.pure(value)
+                    .withShrinkStrategy(intShrinkStrategy(bound));
         };
     }
 
@@ -69,8 +119,8 @@ public final class Generators {
         return sized(size -> integer(0, size));
     }
 
-    private static Iterable<ShrinkTree<Integer>> intShrinkingIterable(final int value, final int bound) {
-        return () -> new Iterator<ShrinkTree<Integer>>() {
+    public static ShrinkStrategy<Integer> intShrinkStrategy(int bound) {
+        return value -> new Iterator<Integer>() {
             int curr = value - bound;
 
             @Override
@@ -79,10 +129,41 @@ public final class Generators {
             }
 
             @Override
-            public ShrinkTree<Integer> next() {
+            public Integer next() {
                 int prevCurr = curr;
                 curr = curr / 2;
-                return new ShrinkTree<>(value - prevCurr, intShrinkingIterable(value - prevCurr, bound));
+                return value - prevCurr;
+            }
+        };
+    }
+
+    public static Generator<Double> doublePrecision(double lower, double upper) {
+        return (random, size) -> {
+            double value = random.doubles(lower, upper).findFirst().getAsDouble();
+            double bound = lower > 0 ? lower : (upper < 0 ? upper : 0);
+            return ShrinkTree.pure(value)
+                    .withShrinkStrategy(doubleShrinkStrategy(bound, Double.MIN_NORMAL /* maybe pick a bigger epsilon? */));
+        };
+    }
+
+    public static Generator<Double> doublePrecision() {
+        return sized(size -> doublePrecision(-size, size));
+    }
+
+    public static ShrinkStrategy<Double> doubleShrinkStrategy(double bound, double epsilon) {
+        return value -> new Iterator<Double>() {
+            double curr = value - bound;
+
+            @Override
+            public boolean hasNext() {
+                return Math.abs(curr) > epsilon;
+            }
+
+            @Override
+            public Double next() {
+                double prevCurr = curr;
+                curr = curr / 2;
+                return value - prevCurr;
             }
         };
     }
@@ -93,9 +174,7 @@ public final class Generators {
             int count = countGen.generate(random, size).getValue();
             return Generator.list(count, gen)
                     .generate(random, size)
-                    .filter(list ->
-                            minElements <= list.size()
-                                    && list.size() < maxElements)
+                    .filter(list -> minElements <= list.size() && list.size() < maxElements)
                     .map(Collections::unmodifiableList);
         };
     }
diff --git a/src/main/java/au/id/zancanaro/javacheck/ShrinkStrategy.java b/src/main/java/au/id/zancanaro/javacheck/ShrinkStrategy.java
new file mode 100644
index 0000000..6bd1eb9
--- /dev/null
+++ b/src/main/java/au/id/zancanaro/javacheck/ShrinkStrategy.java
@@ -0,0 +1,7 @@
+package au.id.zancanaro.javacheck;
+
+import java.util.Iterator;
+
+interface ShrinkStrategy<T> {
+    Iterator<T> shrink(T obj);
+}
diff --git a/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java b/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java
index a424806..7dff917 100644
--- a/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java
+++ b/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java
@@ -2,16 +2,21 @@ package au.id.zancanaro.javacheck;
 
 import java.io.IOException;
 import java.io.Writer;
-import java.util.*;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
 import java.util.function.Function;
 import java.util.function.Predicate;
 
+import static au.id.zancanaro.javacheck.Iterators.*;
+
 @SuppressWarnings("unused")
 public class ShrinkTree<T> {
     private final T value;
     private final Iterable<ShrinkTree<T>> children;
 
-    public ShrinkTree(T value, Iterable<ShrinkTree<T>> children) {
+    private ShrinkTree(T value, Iterable<ShrinkTree<T>> children) {
         this.value = value;
         this.children = children;
     }
@@ -31,15 +36,15 @@ public class ShrinkTree<T> {
     public static <T> ShrinkTree<T> join(ShrinkTree<ShrinkTree<T>> tree) {
         return new ShrinkTree<>(
                 tree.getValue().getValue(),
-                () -> Iterators.concat(
-                        Iterators.mappingIterator(ShrinkTree::join, tree.children.iterator()),
+                () -> concat(
+                        mappingIterator(ShrinkTree::join, tree.children.iterator()),
                         tree.getValue().children.iterator()));
     }
 
     private static <T> Iterator<ShrinkTree<T>[]> permutations(ShrinkTree<T>[] trees) {
-        return Iterators.flatten(
-                Iterators.rangeIterator(trees.length,
-                        index -> Iterators.mappingIterator(child -> {
+        return flatten(
+                rangeIterator(trees.length,
+                        index -> mappingIterator(child -> {
                             @SuppressWarnings("unchecked")
                             ShrinkTree<T>[] result = (ShrinkTree<T>[]) new ShrinkTree[trees.length];
                             for (int i = 0; i < trees.length; ++i) {
@@ -61,14 +66,14 @@ public class ShrinkTree<T> {
     public static <T, R> ShrinkTree<R> zip(Function<List<T>, R> fn, ShrinkTree<T>[] trees) {
         return new ShrinkTree<>(
                 fn.apply(makeHeadList(trees)),
-                () -> Iterators.mappingIterator(
+                () -> mappingIterator(
                         shrinks -> ShrinkTree.zip(fn, shrinks),
                         ShrinkTree.permutations(trees)));
     }
 
     private static <T> Iterator<ShrinkTree<T>[]> removeEach(ShrinkTree<T>[] trees) {
-        return Iterators.concat(
-                Iterators.rangeIterator(trees.length, index -> {
+        return concat(
+                rangeIterator(trees.length, index -> {
                     @SuppressWarnings("unchecked")
                     ShrinkTree<T>[] result = (ShrinkTree<T>[]) new ShrinkTree[trees.length - 1];
                     for (int i = 0; i < trees.length - 1; ++i) {
@@ -82,7 +87,7 @@ public class ShrinkTree<T> {
     public static <T, R> ShrinkTree<R> shrink(Function<List<T>, R> fn, ShrinkTree<T>[] trees) {
         return new ShrinkTree<>(
                 fn.apply(makeHeadList(trees)),
-                () -> Iterators.mappingIterator(
+                () -> mappingIterator(
                         shrinks -> ShrinkTree.shrink(fn, shrinks),
                         ShrinkTree.removeEach(trees)));
     }
@@ -90,7 +95,7 @@ public class ShrinkTree<T> {
     public <R> ShrinkTree<R> map(Function<T, R> f) {
         return new ShrinkTree<>(
                 f.apply(this.value),
-                () -> Iterators.mappingIterator(tree -> tree.map(f), this.children.iterator()));
+                () -> mappingIterator(tree -> tree.map(f), this.children.iterator()));
     }
 
     public <R> ShrinkTree<R> flatMap(Function<T, ShrinkTree<R>> f) {
@@ -101,8 +106,8 @@ public class ShrinkTree<T> {
         if (predicate.test(this.getValue())) {
             return new ShrinkTree<>(
                     this.getValue(),
-                    () -> Iterators.mappingIterator(tree -> tree.filter(predicate),
-                            Iterators.filteringIterator(
+                    () -> mappingIterator(tree -> tree.filter(predicate),
+                            filteringIterator(
                                     tree -> predicate.test(tree.getValue()),
                                     this.getChildren())));
         } else {
@@ -110,6 +115,17 @@ public class ShrinkTree<T> {
         }
     }
 
+    public ShrinkTree<T> withShrinkStrategy(ShrinkStrategy<T> strategy) {
+        return new ShrinkTree<>(this.getValue(), strategyIterable(this.getValue(), strategy));
+    }
+
+    private static <T> Iterable<ShrinkTree<T>> strategyIterable(final T value, final ShrinkStrategy<T> strategy) {
+        return () ->
+                mappingIterator(
+                        v -> new ShrinkTree<>(v, strategyIterable(v, strategy)),
+                        strategy.shrink(value));
+    }
+
     @SuppressWarnings("unused")
     public void print(Writer output) throws IOException {
         print(output, Object::toString);
diff --git a/src/main/java/au/id/zancanaro/javacheck/junit/Properties.java b/src/main/java/au/id/zancanaro/javacheck/junit/Properties.java
index b1cb375..ab56374 100644
--- a/src/main/java/au/id/zancanaro/javacheck/junit/Properties.java
+++ b/src/main/java/au/id/zancanaro/javacheck/junit/Properties.java
@@ -1,8 +1,8 @@
 package au.id.zancanaro.javacheck.junit;
 
 import au.id.zancanaro.javacheck.Generator;
-import au.id.zancanaro.javacheck.ShrinkTree;
 import au.id.zancanaro.javacheck.ShrinkResult;
+import au.id.zancanaro.javacheck.ShrinkTree;
 import au.id.zancanaro.javacheck.annotations.DataSource;
 import au.id.zancanaro.javacheck.annotations.Property;
 import au.id.zancanaro.javacheck.annotations.Seed;
@@ -48,7 +48,7 @@ public class Properties extends BlockJUnit4ClassRunner {
                 }
 
                 Type type = field.getGenericType();
-                ParameterizedType parameterizedType;;
+                ParameterizedType parameterizedType;
                 if (type instanceof ParameterizedType) {
                     parameterizedType = (ParameterizedType) type;
                     if (parameterizedType.getRawType() instanceof Class) {