001    package fj.test;
002    
003    import static fj.Bottom.error;
004    import fj.Effect;
005    import fj.F;
006    import fj.Function;
007    import static fj.Function.flip;
008    import static fj.Function.curry;
009    import fj.P2;
010    import static fj.P2.__1;
011    import fj.Unit;
012    import fj.F2;
013    import static fj.data.Array.array;
014    import fj.data.List;
015    import static fj.data.List.nil;
016    import static fj.data.List.replicate;
017    import fj.data.Option;
018    import static fj.pre.Monoid.intAdditionMonoid;
019    import static fj.pre.Ord.intOrd;
020    
021    import static java.lang.Math.max;
022    import static java.lang.Math.min;
023    
024    /**
025     * <p> A generator for values of the type of the given type parameter (<code>A</code>). Generation
026     * of a value accepts a general 'size' argument (integer), a {@link Rand random generator} and
027     * returns an {@link Option optional value} of the type parameter. Several generators are provided,
028     * allowing various forms of composition of generators. </p> <p> A user typically creates an {@link
029     * Arbitrary arbitrary} to return a generator using the 'combinator methods' below. For example,
030     * suppose a <code>class Person</code>:
031    <pre>
032    class Person {
033      final int age;
034      final String name;
035      final boolean male;
036    
037      Person(final int age, final String name, final boolean male) {
038        this.age = age;
039        this.name = name;
040        this.male = male;
041      }
042    }
043    </pre>
044     * </p> <p> In a case like this one, a user may create a generator over <code>Person</code> by
045     * invoking the {@link #bind(F)}  methods &mdash; in this case, {@link #bind(Gen , Gen , F)} the one
046     * that takes two generator arguments}, since the class has one more than two fields (the bind
047     * method is invoked on a generator adding the extra one to the count as they are composed). The
048     * class fields are of types for which there exist generators (on {@link Arbitrary} so those can be
049     * used to compose a generator for <code>Person</code>: </p>
050    <pre>
051    static Arbitrary&lt;Person&gt; personArbitrary() {
052      final Gen&lt;Person&gt; personGenerator = arbInteger.gen.bind(arbString().gen, arbBoolean().gen,
053          // compose the generators
054          {int age =&gt; {String name =&gt; {boolean male =&gt; new Person(age, name, male)}}};
055      return arbitrary(personGenerator);
056    }
057    </pre>
058     * <p/>
059     * The example above uses Java 7 closure syntax. Here is the same example using objects instead:
060    <pre>
061    static Arbitrary&lt;Person&gt; personArbitrary() {
062      final Gen&lt;Person&gt; personGenerator = arbInteger.gen.bind(arbString.gen, arbBoolean.gen,
063          // compose the generators
064          new F&lt;Integer, F&lt;String, F&lt;Boolean, Person&gt;&gt;&gt;() {
065            public F&lt;String, F&lt;Boolean, Person&gt;&gt; f(final Integer age) {
066              return new F&lt;String, F&lt;Boolean, Person&gt;&gt;() {
067                public F&lt;Boolean, Person&gt; f(final String name) {
068                  return new F&lt;Boolean, Person&gt;() {
069                    public Person f(final Boolean male) {
070                      return new Person(age, name, male);
071                    }
072                  };
073                }
074              };
075            }
076          });
077      return arbitrary(personGenerator);
078    }
079    </pre>
080     *
081     * @version %build.number%<br>
082     *          <ul>
083     *          <li>$LastChangedRevision: 286 $</li>
084     *          <li>$LastChangedDate: 2009-10-01 23:41:37 +1000 (Thu, 01 Oct 2009) $</li>
085     *          <li>$LastChangedBy: tonymorris $</li>
086     *          </ul>
087     */
088    public final class Gen<A> {
089      private final F<Integer, F<Rand, A>> f;
090    
091      private Gen(final F<Integer, F<Rand, A>> f) {
092        this.f = f;
093      }
094    
095      /**
096       * Applies the given size and random generator to produce a value.
097       *
098       * @param i The size to use to produce the value.
099       * @param r The random generator to use to produce the value..
100       * @return A generated value.
101       */
102      public A gen(final int i, final Rand r) {
103        return f.f(i).f(r);
104      }
105    
106      /**
107       * Maps the given function across this generator.
108       *
109       * @param f The function to map across this generator.
110       * @return A new generator after applying the mapping function.
111       */
112      public <B> Gen<B> map(final F<A, B> f) {
113        return new Gen<B>(new F<Integer, F<Rand, B>>() {
114          public F<Rand, B> f(final Integer i) {
115            return new F<Rand, B>() {
116              public B f(final Rand r) {
117                return f.f(gen(i, r));
118              }
119            };
120          }
121        });
122      }
123    
124      /**
125       * Returns a generator that produces values that meet the given predicate.
126       *
127       * @param f The predicate to meet for the values produced by the generator.
128       * @return A generator that produces values that meet the given predicate.
129       */
130      public Gen<A> filter(final F<A, Boolean> f) {
131        return gen(curry(new F2<Integer, Rand, A>() {
132          public A f(final Integer i, final Rand r) {
133            A a;
134    
135            do {
136              a = gen(i, r);
137            } while(!f.f(a));
138    
139            return a;
140          }
141        }));
142      }
143    
144      /**
145       * Executes a side-effect for each generated result using the given arguments.
146       *
147       * @param i The size to generate the result to apply the side-effect to.
148       * @param r The random generator to generate the result to apply the side-effect to.
149       * @param f The side-effect to execute on the generated value.
150       * @return The unit value.
151       */
152      public Unit foreach(final Integer i, final Rand r, final F<A, Unit> f) {
153        return f.f(this.f.f(i).f(r));
154      }
155    
156      /**
157       * Executes a side-effect for each generated result using the given arguments.
158       *
159       * @param i The size to generate the result to apply the side-effect to.
160       * @param r The random generator to generate the result to apply the side-effect to.
161       * @param f The side-effect to execute on the generated value.
162       */
163      public void foreach(final Integer i, final Rand r, final Effect<A> f) {
164        f.e(this.f.f(i).f(r));
165      }
166    
167      /**
168       * Binds the given function across this generator to produce a new generator.
169       *
170       * @param f The function to bind across this generator.
171       * @return A new generator after binding the given function.
172       */
173      public <B> Gen<B> bind(final F<A, Gen<B>> f) {
174        return new Gen<B>(new F<Integer, F<Rand, B>>() {
175          public F<Rand, B> f(final Integer i) {
176            return new F<Rand, B>() {
177              public B f(final Rand r) {
178                return f.f(gen(i, r)).f.f(i).f(r);
179              }
180            };
181          }
182        });
183      }
184    
185      /**
186       * Binds the given function across this generator and the given generator to produce a new
187       * generator.
188       *
189       * @param gb The second generator to bind the given function across.
190       * @param f  The function to bind across this generator and the given generator.
191       * @return A new generator after binding the given function.
192       */
193      public <B, C> Gen<C> bind(final Gen<B> gb, final F<A, F<B, C>> f) {
194        return gb.apply(map(f));
195      }
196    
197      /**
198       * Binds the given function across this generator and the given generators to produce a new
199       * generator.
200       *
201       * @param gb The second generator to bind the given function across.
202       * @param gc The third generator to bind the given function across.
203       * @param f  The function to bind across this generator and the given generators.
204       * @return A new generator after binding the given function.
205       */
206      public <B, C, D> Gen<D> bind(final Gen<B> gb, final Gen<C> gc, final F<A, F<B, F<C, D>>> f) {
207        return gc.apply(bind(gb, f));
208      }
209    
210      /**
211       * Binds the given function across this generator and the given generators to produce a new
212       * generator.
213       *
214       * @param gb The second generator to bind the given function across.
215       * @param gc The third generator to bind the given function across.
216       * @param gd The fourth generator to bind the given function across.
217       * @param f  The function to bind across this generator and the given generators.
218       * @return A new generator after binding the given function.
219       */
220      public <B, C, D, E> Gen<E> bind(final Gen<B> gb, final Gen<C> gc, final Gen<D> gd, final F<A, F<B, F<C, F<D, E>>>> f) {
221        return gd.apply(bind(gb, gc, f));
222      }
223    
224      /**
225       * Binds the given function across this generator and the given generators to produce a new
226       * generator.
227       *
228       * @param gb The second generator to bind the given function across.
229       * @param gc The third generator to bind the given function across.
230       * @param gd The fourth generator to bind the given function across.
231       * @param ge The fifth generator to bind the given function across.
232       * @param f  The function to bind across this generator and the given generators.
233       * @return A new generator after binding the given function.
234       */
235      public <B, C, D, E, F$> Gen<F$> bind(final Gen<B> gb, final Gen<C> gc, final Gen<D> gd, final Gen<E> ge, final F<A, F<B, F<C, F<D, F<E, F$>>>>> f) {
236        return ge.apply(bind(gb, gc, gd, f));
237      }
238    
239      /**
240       * Binds the given function across this generator and the given generators to produce a new
241       * generator.
242       *
243       * @param gb The second generator to bind the given function across.
244       * @param gc The third generator to bind the given function across.
245       * @param gd The fourth generator to bind the given function across.
246       * @param ge The fifth generator to bind the given function across.
247       * @param gf The sixth generator to bind the given function across.
248       * @param f  The function to bind across this generator and the given generators.
249       * @return A new generator after binding the given function.
250       */
251      public <B, C, D, E, F$, G> Gen<G> bind(final Gen<B> gb, final Gen<C> gc, final Gen<D> gd, final Gen<E> ge, final Gen<F$> gf, final F<A, F<B, F<C, F<D, F<E, F<F$, G>>>>>> f) {
252        return gf.apply(bind(gb, gc, gd, ge, f));
253      }
254    
255      /**
256       * Binds the given function across this generator and the given generators to produce a new
257       * generator.
258       *
259       * @param gb The second generator to bind the given function across.
260       * @param gc The third generator to bind the given function across.
261       * @param gd The fourth generator to bind the given function across.
262       * @param ge The fifth generator to bind the given function across.
263       * @param gf The sixth generator to bind the given function across.
264       * @param gg The seventh generator to bind the given function across.
265       * @param f  The function to bind across this generator and the given generators.
266       * @return A new generator after binding the given function.
267       */
268      public <B, C, D, E, F$, G, H> Gen<H> bind(final Gen<B> gb, final Gen<C> gc, final Gen<D> gd, final Gen<E> ge, final Gen<F$> gf, final Gen<G> gg, final F<A, F<B, F<C, F<D, F<E, F<F$, F<G, H>>>>>>> f) {
269        return gg.apply(bind(gb, gc, gd, ge, gf, f));
270      }
271    
272      /**
273       * Binds the given function across this generator and the given generators to produce a new
274       * generator.
275       *
276       * @param gb The second generator to bind the given function across.
277       * @param gc The third generator to bind the given function across.
278       * @param gd The fourth generator to bind the given function across.
279       * @param ge The fifth generator to bind the given function across.
280       * @param gf The sixth generator to bind the given function across.
281       * @param gg The seventh generator to bind the given function across.
282       * @param gh The eighth generator to bind the given function across.
283       * @param f  The function to bind across this generator and the given generators.
284       * @return A new generator after binding the given function.
285       */
286      public <B, C, D, E, F$, G, H, I> Gen<I> bind(final Gen<B> gb, final Gen<C> gc, final Gen<D> gd, final Gen<E> ge, final Gen<F$> gf, final Gen<G> gg, final Gen<H> gh, final F<A, F<B, F<C, F<D, F<E, F<F$, F<G, F<H, I>>>>>>>> f) {
287        return gh.apply(bind(gb, gc, gd, ge, gf, gg, f));
288      }
289    
290      /**
291       * Function application within this generator to produce a new generator.
292       *
293       * @param gf The generator over the function to apply to this generator.
294       * @return A new generator after function application.
295       */
296      public <B> Gen<B> apply(final Gen<F<A, B>> gf) {
297        return gf.bind(new F<F<A, B>, Gen<B>>() {
298          public Gen<B> f(final F<A, B> f) {
299            return map(new F<A, B>() {
300              public B f(final A a) {
301                return f.f(a);
302              }
303            });
304          }
305        });
306      }
307    
308      /**
309       * Resizes this generator with the given size.
310       *
311       * @param s The new size of the generator.
312       * @return A new generator that uses the given size.
313       */
314      public Gen<A> resize(final int s) {
315        return new Gen<A>(new F<Integer, F<Rand, A>>() {
316          public F<Rand, A> f(final Integer i) {
317            return new F<Rand, A>() {
318              public A f(final Rand r) {
319                return f.f(s).f(r);
320              }
321            };
322          }
323        });
324      }
325    
326      /**
327       * Returns a generator that uses the given function.
328       *
329       * @param f The function to use for this generator.
330       * @return A new generator that uses the given function.
331       */
332      public static <A> Gen<A> gen(final F<Integer, F<Rand, A>> f) {
333        return new Gen<A>(f);
334      }
335    
336      /**
337       * Sequence the given generators through a {@link #bind(F)} operation.
338       *
339       * @param gs The generators to sequence.
340       * @return A generator of lists after sequencing the given generators.
341       */
342      public static <A> Gen<List<A>> sequence(final List<Gen<A>> gs) {
343        return gs.foldRight(new F<Gen<A>, F<Gen<List<A>>, Gen<List<A>>>>() {
344          public F<Gen<List<A>>, Gen<List<A>>> f(final Gen<A> ga) {
345            return new F<Gen<List<A>>, Gen<List<A>>>() {
346              public Gen<List<A>> f(final Gen<List<A>> gas) {
347                return ga.bind(gas, List.<A>cons());
348              }
349            };
350          }
351        }, value(List.<A>nil()));
352      }
353    
354      /**
355       * Sequences the given generator the given number of times through a {@link #bind(F)} operation.
356       *
357       * @param n The number of times to sequence the given generator.
358       * @param g The generator sequence.
359       * @return A generator of lists after sequencing the given generator.
360       */
361      public static <A> Gen<List<A>> sequenceN(final int n, final Gen<A> g) {
362        return sequence(replicate(n, g));
363      }
364    
365      /**
366       * Constructs a generator that can access its construction arguments &mdash; size and random
367       * generator.
368       *
369       * @param f The function that constructs the generator with its arguments.
370       * @return A new generator.
371       */
372      public static <A> Gen<A> parameterised(final F<Integer, F<Rand, Gen<A>>> f) {
373        return new Gen<A>(curry(new F2<Integer, Rand, A>() {
374          public A f(final Integer i, Rand r) {
375            return f.f(i).f(r).gen(i, r);
376          }
377        }));
378      }
379    
380      /**
381       * Constructs a generator that can access its size construction arguments.
382       *
383       * @param f The function that constructs the generator with its size argument.
384       * @return A new generator.
385       */
386      public static <A> Gen<A> sized(final F<Integer, Gen<A>> f) {
387        return parameterised(flip(Function.<Rand, F<Integer, Gen<A>>>constant(f)));
388      }
389    
390      /**
391       * Returns a generator that always produces the given value.
392       *
393       * @param a The value to always produce.
394       * @return A generator that always produces the given value.
395       */
396      public static <A> Gen<A> value(final A a) {
397        return new Gen<A>(new F<Integer, F<Rand, A>>() {
398          public F<Rand, A> f(final Integer i) {
399            return new F<Rand, A>() {
400              public A f(final Rand r) {
401                return a;
402              }
403            };
404          }
405        });
406      }
407    
408      /**
409       * Returns a generator that produces values between the given range (inclusive).
410       *
411       * @param from The value for the generator to produce values from.
412       * @param to   The value for the generator to produce values from.
413       * @return A generator that produces values between the given range (inclusive).
414       */
415      public static Gen<Integer> choose(final int from, final int to) {
416        final int f = min(from, to);
417        final int t = max(from, to);
418        return parameterised(curry(new F2<Integer, Rand, Gen<Integer>>() {
419          public Gen<Integer> f(final Integer i, final Rand r) {
420            return value(r.choose(f, t));
421          }
422        }));
423      }
424    
425      /**
426       * Returns a generator that produces values between the given range (inclusive).
427       *
428       * @param from The value for the generator to produce values from.
429       * @param to   The value for the generator to produce values from.
430       * @return A generator that produces v
431       */
432      public static Gen<Double> choose(final double from, final double to) {
433        final double f = min(from, to);
434        final double t = max(from, to);
435        return parameterised(new F<Integer, F<Rand, Gen<Double>>>() {
436          public F<Rand, Gen<Double>> f(final Integer i) {
437            return new F<Rand, Gen<Double>>() {
438              public Gen<Double> f(final Rand r) {
439                return value(r.choose(f, t));
440              }
441            };
442          }
443        });
444      }
445    
446      /**
447       * Returns a generator that never returns a value.
448       *
449       * @return A generator that never returns a value.
450       */
451      public static <A> Gen<A> fail() {
452        return new Gen<A>(new F<Integer, F<Rand, A>>() {
453          public F<Rand, A> f(final Integer i) {
454            return new F<Rand, A>() {
455              public A f(final Rand r) {
456                throw error("Failing generator");
457              }
458            };
459          }
460        });
461      }
462    
463      /**
464       * Joins the generator of generators through a {@link #bind(F)} operation.
465       *
466       * @param g The generator of generators to join.
467       * @return A new generator after joining the given generator.
468       */
469      public static <A> Gen<A> join(final Gen<Gen<A>> g) {
470        return g.bind(Function.<Gen<A>>identity());
471      }
472    
473      /**
474       * Returns a generator that uses values from the given frequency and generator pairs. The returned
475       * generator will produce values from the generator in a pair with a higher frequency than a lower
476       * frequency generator.
477       *
478       * @param gs The pairs of frequency and generator from which to return values in the returned
479       *           generator.
480       * @return A new generator that uses the given pairs of frequency and generator.
481       */
482      public static <A> Gen<A> frequency(final List<P2<Integer, Gen<A>>> gs) {
483        final class Pick {
484          <A> Gen<A> pick(final int n, final List<P2<Integer, Gen<A>>> gs) {
485            if(gs.isEmpty())
486              return fail();
487            else {
488              final int k = gs.head()._1();
489              return n <= k ? gs.head()._2() : pick(n - k, gs.tail());
490            }
491          }
492        }
493    
494        final F<P2<Integer, Gen<A>>, Integer> f = __1();
495    
496        return choose(1, intAdditionMonoid.sumLeft(gs.map(f))).bind(new F<Integer, Gen<A>>() {
497          public Gen<A> f(final Integer i) {
498            return new Pick().pick(i, gs);
499          }
500        });
501      }
502    
503      /**
504       * Returns a generator that produces values from the given frequency and value pairs. The returned
505       * generator will produce the value with a higher frequency than a lower one.
506       *
507       * @param as The pairs of frequency and value from which to produce values.
508       * @return A new generator that uses the given pairs of frequency and value.
509       */
510      public static <A> Gen<A> elemFrequency(final List<P2<Integer, A>> as) {
511        return frequency(as.map(new F<P2<Integer, A>, P2<Integer, Gen<A>>>() {
512          public P2<Integer, Gen<A>> f(final P2<Integer, A> p) {
513            return p.map2(new F<A, Gen<A>>() {
514              public Gen<A> f(final A a) {
515                return value(a);
516              }
517            });
518          }
519        }));
520      }
521    
522      /**
523       * Returns a generator that produces values from the given arguments.
524       *
525       * @param as The values that the returned generator may produce.
526       * @return A generator that produces values from the given arguments.
527       */
528      public static <A> Gen<A> elements(final A... as) {
529        return array(as).isEmpty() ? Gen.<A>fail() : choose(0, as.length - 1).map(new F<Integer, A>() {
530          public A f(final Integer i) {
531            return as[i];
532          }
533        });
534      }
535    
536      /**
537       * Returns a generator that produces values from one of the given generators on subsequent
538       * requests.
539       *
540       * @param gs The list of generators to produce a value from.
541       * @return A generator that produces values from one of the given generators on subsequent
542       *         requests.
543       */
544      public static <A> Gen<A> oneOf(final List<Gen<A>> gs) {
545        return gs.isEmpty() ? Gen.<A>fail() : choose(0, gs.length() - 1).bind(new F<Integer, Gen<A>>() {
546          public Gen<A> f(final Integer i) {
547            return gs.index(i);
548          }
549        });
550      }
551    
552      /**
553       * Returns a generator of lists whose values come from the given generator.
554       *
555       * @param g The generator to produce values from for the returned generator.
556       * @param x An adjuster of size to apply to the given generator when producing values.
557       * @return A generator of lists whose values come from the given generator.
558       */
559      public static <A> Gen<List<A>> listOf(final Gen<A> g, final int x) {
560        return sized(new F<Integer, Gen<List<A>>>() {
561          public Gen<List<A>> f(final Integer size) {
562            return choose(x, size).bind(new F<Integer, Gen<List<A>>>() {
563              public Gen<List<A>> f(final Integer n) {
564                return sequenceN(n, g);
565              }
566            });
567          }
568        });
569      }
570    
571      /**
572       * Returns a generator of lists whose values come from the given generator.
573       *
574       * @param g The generator to produce values from for the returned generator.
575       * @return A generator of lists whose values come from the given generator.
576       */
577      public static <A> Gen<List<A>> listOf(final Gen<A> g) {
578        return listOf(g, 0);
579      }
580    
581      /**
582       * Returns a generator of lists whose values come from the given generator.
583       *
584       * @param g The generator to produce values from for the returned generator.
585       * @return A generator of lists whose values come from the given generator.
586       */
587      public static <A> Gen<List<A>> listOf1(final Gen<A> g) {
588        return listOf(g, 1);
589      }
590    
591      /**
592       * Returns a generator of lists that picks the given number of elements from the given list. If
593       * the given number is less than zero or greater than the length of the given list, then the
594       * returned generator will never produce a value.
595       *
596       * @param n  The number of elements to pick from the given list.
597       * @param as The list from which to pick elements.
598       * @return A generator of lists that picks the given number of elements from the given list.
599       */
600      public static <A> Gen<List<A>> pick(final int n, final List<A> as) {
601        return n < 0 || n > as.length() ? Gen.<List<A>>fail() : sequenceN(n, choose(0, as.length() - 1)).map(new F<List<Integer>, List<A>>() {
602          public List<A> f(final List<Integer> is) {
603            List<A> r = nil();
604    
605            List<Integer> iis = is.sort(intOrd);
606            List<P2<A, Integer>> aas = as.zipIndex();
607    
608            //noinspection ForLoopWithMissingComponent
609            for(; iis.isNotEmpty() && aas.isNotEmpty(); aas = aas.tail())
610              if(iis.head().equals(aas.head()._2()))
611                iis = iis.tail();
612              else
613                r = r.snoc(aas.head()._1());
614    
615            return r;
616          }
617        });
618      }
619    
620      /**
621       * Returns a generator of lists that produces some of the values of the given list.
622       *
623       * @param as The list from which to pick values.
624       * @return A generator of lists that produces some of the values of the given list.
625       */
626      public static <A> Gen<List<A>> someOf(final List<A> as) {
627        return choose(0, as.length()).bind(new F<Integer, Gen<List<A>>>() {
628          public Gen<List<A>> f(final Integer i) {
629            return pick(i, as);
630          }
631        });
632      }
633    
634      /**
635       * Promotes the given function to a generator for functions.
636       *
637       * @param f The function to promote to a generator of functions.
638       * @return A generator for functions.
639       */
640      public static <A, B> Gen<F<A, B>> promote(final F<A, Gen<B>> f) {
641        return new Gen<F<A, B>>(new F<Integer, F<Rand, F<A, B>>>() {
642          public F<Rand, F<A, B>> f(final Integer i) {
643            return new F<Rand, F<A, B>>() {
644              public F<A, B> f(final Rand r) {
645                return new F<A, B>() {
646                  public B f(final A a) {
647                    return f.f(a).f.f(i).f(r);
648                  }
649                };
650              }
651            };
652          }
653        });
654      }
655    }