From 7b1a783b749ab04ab8219ef28f9b1abb0ded6ca4 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Wed, 3 Jun 2015 14:32:07 +1000 Subject: Rename RoseTree to ShrinkTree (less confusing and more specific) --- .../java/au/id/zancanaro/javacheck/Generator.java | 24 ++-- .../java/au/id/zancanaro/javacheck/Generators.java | 18 +-- .../java/au/id/zancanaro/javacheck/RoseTree.java | 128 --------------------- .../java/au/id/zancanaro/javacheck/ShrinkTree.java | 128 +++++++++++++++++++++ .../id/zancanaro/javacheck/junit/Properties.java | 12 +- 5 files changed, 155 insertions(+), 155 deletions(-) delete mode 100644 src/main/java/au/id/zancanaro/javacheck/RoseTree.java create mode 100644 src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java (limited to 'src/main/java/au/id/zancanaro') diff --git a/src/main/java/au/id/zancanaro/javacheck/Generator.java b/src/main/java/au/id/zancanaro/javacheck/Generator.java index 557cf97..9d88020 100644 --- a/src/main/java/au/id/zancanaro/javacheck/Generator.java +++ b/src/main/java/au/id/zancanaro/javacheck/Generator.java @@ -10,7 +10,7 @@ import java.util.function.Function; * trees in a controlled and deterministic way. * * A generator must implement one method: {@link #generate(Random, int)}. The - * {@link RoseTree} it produces defines both the value to be returned, as well + * {@link ShrinkTree} it produces defines both the value to be returned, as well * as the shrink tree for that value. * * Generators form a "monad", and hence have the {@link #map(Function)} and @@ -23,7 +23,7 @@ import java.util.function.Function; @SuppressWarnings("unused") public interface Generator { /** - * Return a {@link RoseTree} containing a new random value of the required + * Return a {@link ShrinkTree} containing a new random value of the required * type, as well as its associated shrink tree. * * Generators also have an abstract notion of "size". Represented by an @@ -33,10 +33,10 @@ public interface Generator { * * @param random The random source for generation purposes * @param size An integer specifying how "big" a thing to produce - * @return The {@link RoseTree} specifying the generated thing and its + * @return The {@link ShrinkTree} specifying the generated thing and its * shrink tree */ - RoseTree generate(Random random, int size); + ShrinkTree generate(Random random, int size); /** * A generator which simply generates the provided value. Does not shrink. @@ -46,7 +46,7 @@ public interface Generator { * @return A {@link Generator} which generates the provided value */ static Generator pure(T value) { - return (random, size) -> RoseTree.pure(value); + return (random, size) -> ShrinkTree.pure(value); } /** @@ -66,12 +66,12 @@ public interface Generator { static Generator> tuple(Generator... generators) { return (random, size) -> { @SuppressWarnings("unchecked") - RoseTree[] result = (RoseTree[]) new RoseTree[generators.length]; + ShrinkTree[] result = (ShrinkTree[]) new ShrinkTree[generators.length]; int index = 0; for (Generator generator : generators) { result[index++] = generator.generate(random, size); } - return RoseTree.zip(Function.identity(), result); + return ShrinkTree.zip(Function.identity(), result); }; } @@ -81,8 +81,8 @@ public interface Generator { * * Shrinking for this type involves attempting to remove terms and shrink * each subtree in turn, recursively. (If the length must remain fixed then - * the {@link RoseTree} produced by this generator should be filtered with - * {@link RoseTree#filter(java.util.function.Predicate)}. + * the {@link ShrinkTree} produced by this generator should be filtered with + * {@link ShrinkTree#filter(java.util.function.Predicate)}. * * @param count The length of the list to generate * @param generator The generator to use for each term in the generated @@ -93,11 +93,11 @@ public interface Generator { static Generator> list(int count, Generator generator) { return (random, size) -> { @SuppressWarnings("unchecked") - RoseTree[] result = (RoseTree[]) new RoseTree[count]; + ShrinkTree[] result = (ShrinkTree[]) new ShrinkTree[count]; for (int i = 0; i < count; ++i) { result[i] = generator.generate(random, size); } - return RoseTree.shrink(Function.identity(), result); + return ShrinkTree.shrink(Function.identity(), result); }; } @@ -127,7 +127,7 @@ public interface Generator { * result of this */ default Generator flatMap(Function> action) { - return (random, size) -> RoseTree.join(this.generate(random, size).map(action).map(g -> g.generate(random, size))); + return (random, size) -> ShrinkTree.join(this.generate(random, size).map(action).map(g -> g.generate(random, size))); } default Iterator sample(Random random, int maxSize) { diff --git a/src/main/java/au/id/zancanaro/javacheck/Generators.java b/src/main/java/au/id/zancanaro/javacheck/Generators.java index 4049149..5dee924 100644 --- a/src/main/java/au/id/zancanaro/javacheck/Generators.java +++ b/src/main/java/au/id/zancanaro/javacheck/Generators.java @@ -18,7 +18,7 @@ public final class Generators { public static Generator suchThat(Generator gen, Predicate predicate) { return (random, size) -> { - RoseTree result = gen.generate(random, size); + ShrinkTree result = gen.generate(random, size); if (predicate.test(result.getValue())) { return result.filter(predicate); } else { @@ -28,7 +28,7 @@ public final class Generators { } public static Generator noShrink(Generator gen) { - return (random, size) -> new RoseTree<>( + return (random, size) -> new ShrinkTree<>( gen.generate(random, size).getValue(), Collections.emptyList()); } @@ -49,15 +49,15 @@ public final class Generators { public static Generator bool() { return (random, size) -> random.nextBoolean() ? - new RoseTree<>(true, Collections.singletonList(new RoseTree<>(false, Collections.emptyList()))) : - new RoseTree<>(false, Collections.emptyList()); + new ShrinkTree<>(true, Collections.singletonList(new ShrinkTree<>(false, Collections.emptyList()))) : + new ShrinkTree<>(false, Collections.emptyList()); } public static Generator integer(int lower, int upper) { return (random, size) -> { int value = lower + random.nextInt(upper - lower); int bound = lower > 0 ? lower : (upper < 0 ? upper : 0); - return new RoseTree<>(value, intShrinkingIterable(value, bound)); + return new ShrinkTree<>(value, intShrinkingIterable(value, bound)); }; } @@ -69,8 +69,8 @@ public final class Generators { return sized(size -> integer(0, size)); } - private static Iterable> intShrinkingIterable(final int value, final int bound) { - return () -> new Iterator>() { + private static Iterable> intShrinkingIterable(final int value, final int bound) { + return () -> new Iterator>() { int curr = value - bound; @Override @@ -79,10 +79,10 @@ public final class Generators { } @Override - public RoseTree next() { + public ShrinkTree next() { int prevCurr = curr; curr = curr / 2; - return new RoseTree<>(value - prevCurr, intShrinkingIterable(value - prevCurr, bound)); + return new ShrinkTree<>(value - prevCurr, intShrinkingIterable(value - prevCurr, bound)); } }; } diff --git a/src/main/java/au/id/zancanaro/javacheck/RoseTree.java b/src/main/java/au/id/zancanaro/javacheck/RoseTree.java deleted file mode 100644 index c735b46..0000000 --- a/src/main/java/au/id/zancanaro/javacheck/RoseTree.java +++ /dev/null @@ -1,128 +0,0 @@ -package au.id.zancanaro.javacheck; - -import java.io.IOException; -import java.io.Writer; -import java.util.*; -import java.util.function.Function; -import java.util.function.Predicate; - -@SuppressWarnings("unused") -public class RoseTree { - private final T value; - private final Iterable> children; - - public RoseTree(T value, Iterable> children) { - this.value = value; - this.children = children; - } - - public T getValue() { - return value; - } - - public Iterator> getChildren() { - return children.iterator(); - } - - public static RoseTree pure(T value) { - return new RoseTree<>(value, Collections.emptyList()); - } - - public static RoseTree join(RoseTree> tree) { - return new RoseTree<>( - tree.getValue().getValue(), - () -> Iterators.concat( - Iterators.mappingIterator(RoseTree::join, tree.children.iterator()), - tree.getValue().children.iterator())); - } - - private static Iterator[]> permutations(RoseTree[] trees) { - return Iterators.flatten( - Iterators.rangeIterator(trees.length, - index -> Iterators.mappingIterator(child -> { - @SuppressWarnings("unchecked") - RoseTree[] result = (RoseTree[]) new RoseTree[trees.length]; - for (int i = 0; i < trees.length; ++i) { - result[i] = (i == index ? child : trees[i]); - } - return result; - }, trees[index].getChildren()) - )); - } - - private static List makeHeadList(RoseTree[] trees) { - List heads = new ArrayList<>(trees.length); - for (RoseTree tree : trees) { - heads.add(tree.getValue()); - } - return heads; - } - - public static RoseTree zip(Function, R> fn, RoseTree[] trees) { - return new RoseTree<>( - fn.apply(makeHeadList(trees)), - () -> Iterators.mappingIterator( - roses -> RoseTree.zip(fn, roses), - RoseTree.permutations(trees))); - } - - private static Iterator[]> removeEach(RoseTree[] trees) { - return Iterators.concat( - Iterators.rangeIterator(trees.length, index -> { - @SuppressWarnings("unchecked") - RoseTree[] result = (RoseTree[]) new RoseTree[trees.length - 1]; - for (int i = 0; i < trees.length - 1; ++i) { - result[i] = trees[(i >= index ? i + 1 : i)]; - } - return result; - }), - permutations(trees)); - } - - public static RoseTree shrink(Function, R> fn, RoseTree[] trees) { - return new RoseTree<>( - fn.apply(makeHeadList(trees)), - () -> Iterators.mappingIterator( - roses -> RoseTree.shrink(fn, roses), - RoseTree.removeEach(trees))); - } - - public RoseTree map(Function f) { - return new RoseTree<>( - f.apply(this.value), - () -> Iterators.mappingIterator(tree -> tree.map(f), this.children.iterator())); - } - - public RoseTree flatMap(Function> f) { - return RoseTree.join(this.map(f)); - } - - public RoseTree filter(Predicate predicate) { - if (predicate.test(this.getValue())) { - return new RoseTree<>( - this.getValue(), - () -> Iterators.mappingIterator(tree -> tree.filter(predicate), - Iterators.filteringIterator( - tree -> predicate.test(tree.getValue()), - this.getChildren()))); - } else { - throw new IllegalArgumentException("Current value doesn't match predicate: whoops!"); - } - } - - @SuppressWarnings("unused") - public void print(Writer output) throws IOException { - print(output, Object::toString); - } - - @SuppressWarnings("unused") - public void print(Writer output, Function toString) throws IOException { - output.write(toString.apply(this.getValue())); - output.write('['); - for (RoseTree child : children) { - child.print(output, toString); - } - output.write(']'); - output.flush(); - } -} diff --git a/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java b/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java new file mode 100644 index 0000000..a424806 --- /dev/null +++ b/src/main/java/au/id/zancanaro/javacheck/ShrinkTree.java @@ -0,0 +1,128 @@ +package au.id.zancanaro.javacheck; + +import java.io.IOException; +import java.io.Writer; +import java.util.*; +import java.util.function.Function; +import java.util.function.Predicate; + +@SuppressWarnings("unused") +public class ShrinkTree { + private final T value; + private final Iterable> children; + + public ShrinkTree(T value, Iterable> children) { + this.value = value; + this.children = children; + } + + public T getValue() { + return value; + } + + public Iterator> getChildren() { + return children.iterator(); + } + + public static ShrinkTree pure(T value) { + return new ShrinkTree<>(value, Collections.emptyList()); + } + + public static ShrinkTree join(ShrinkTree> tree) { + return new ShrinkTree<>( + tree.getValue().getValue(), + () -> Iterators.concat( + Iterators.mappingIterator(ShrinkTree::join, tree.children.iterator()), + tree.getValue().children.iterator())); + } + + private static Iterator[]> permutations(ShrinkTree[] trees) { + return Iterators.flatten( + Iterators.rangeIterator(trees.length, + index -> Iterators.mappingIterator(child -> { + @SuppressWarnings("unchecked") + ShrinkTree[] result = (ShrinkTree[]) new ShrinkTree[trees.length]; + for (int i = 0; i < trees.length; ++i) { + result[i] = (i == index ? child : trees[i]); + } + return result; + }, trees[index].getChildren()) + )); + } + + private static List makeHeadList(ShrinkTree[] trees) { + List heads = new ArrayList<>(trees.length); + for (ShrinkTree tree : trees) { + heads.add(tree.getValue()); + } + return heads; + } + + public static ShrinkTree zip(Function, R> fn, ShrinkTree[] trees) { + return new ShrinkTree<>( + fn.apply(makeHeadList(trees)), + () -> Iterators.mappingIterator( + shrinks -> ShrinkTree.zip(fn, shrinks), + ShrinkTree.permutations(trees))); + } + + private static Iterator[]> removeEach(ShrinkTree[] trees) { + return Iterators.concat( + Iterators.rangeIterator(trees.length, index -> { + @SuppressWarnings("unchecked") + ShrinkTree[] result = (ShrinkTree[]) new ShrinkTree[trees.length - 1]; + for (int i = 0; i < trees.length - 1; ++i) { + result[i] = trees[(i >= index ? i + 1 : i)]; + } + return result; + }), + permutations(trees)); + } + + public static ShrinkTree shrink(Function, R> fn, ShrinkTree[] trees) { + return new ShrinkTree<>( + fn.apply(makeHeadList(trees)), + () -> Iterators.mappingIterator( + shrinks -> ShrinkTree.shrink(fn, shrinks), + ShrinkTree.removeEach(trees))); + } + + public ShrinkTree map(Function f) { + return new ShrinkTree<>( + f.apply(this.value), + () -> Iterators.mappingIterator(tree -> tree.map(f), this.children.iterator())); + } + + public ShrinkTree flatMap(Function> f) { + return ShrinkTree.join(this.map(f)); + } + + public ShrinkTree filter(Predicate predicate) { + if (predicate.test(this.getValue())) { + return new ShrinkTree<>( + this.getValue(), + () -> Iterators.mappingIterator(tree -> tree.filter(predicate), + Iterators.filteringIterator( + tree -> predicate.test(tree.getValue()), + this.getChildren()))); + } else { + throw new IllegalArgumentException("Current value doesn't match predicate: whoops!"); + } + } + + @SuppressWarnings("unused") + public void print(Writer output) throws IOException { + print(output, Object::toString); + } + + @SuppressWarnings("unused") + public void print(Writer output, Function toString) throws IOException { + output.write(toString.apply(this.getValue())); + output.write('['); + for (ShrinkTree child : children) { + child.print(output, toString); + } + output.write(']'); + output.flush(); + } +} 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 1e3f502..b1cb375 100644 --- a/src/main/java/au/id/zancanaro/javacheck/junit/Properties.java +++ b/src/main/java/au/id/zancanaro/javacheck/junit/Properties.java @@ -1,7 +1,7 @@ package au.id.zancanaro.javacheck.junit; import au.id.zancanaro.javacheck.Generator; -import au.id.zancanaro.javacheck.RoseTree; +import au.id.zancanaro.javacheck.ShrinkTree; import au.id.zancanaro.javacheck.ShrinkResult; import au.id.zancanaro.javacheck.annotations.DataSource; import au.id.zancanaro.javacheck.annotations.Property; @@ -208,7 +208,7 @@ public class Properties extends BlockJUnit4ClassRunner { int numTests = property.runs(); for (int i = 0; i < numTests; ++i) { int size = Math.min(i + 1, maxSize); - RoseTree tree = generator.generate(random, size); + ShrinkTree tree = generator.generate(random, size); try { runTest(tree.getValue()); assumptionsViolated = 0; @@ -225,7 +225,7 @@ public class Properties extends BlockJUnit4ClassRunner { } } - private ShrinkResult shrink(RoseTree failed, Throwable originalEx) { + private ShrinkResult shrink(ShrinkTree failed, Throwable originalEx) { // this array is a mutable container so the shutdown handler can see the new version ShrinkResult[] smallest = new ShrinkResult[]{ new ShrinkResult(failed.getValue(), originalEx)}; @@ -233,10 +233,10 @@ public class Properties extends BlockJUnit4ClassRunner { Thread shutdownHandler = makeShutdownHandler(smallest, originalEx); Runtime.getRuntime().addShutdownHook(shutdownHandler); - Iterator> trees = failed.getChildren(); + Iterator> trees = failed.getChildren(); Set> seenArgs = new HashSet<>(); while (trees.hasNext()) { - RoseTree tree = trees.next(); + ShrinkTree tree = trees.next(); if (seenArgs.add(Arrays.asList(tree.getValue()))) { try { runTest(tree.getValue()); @@ -244,7 +244,7 @@ public class Properties extends BlockJUnit4ClassRunner { // ignore, because it's not useful } catch (Throwable ex) { smallest[0] = new ShrinkResult(tree.getValue(), ex); - Iterator> children = tree.getChildren(); + Iterator> children = tree.getChildren(); if (children.hasNext()) { trees = children; } else { -- cgit v1.2.3