001    package fj.test;
002    
003    import fj.Effect;
004    import fj.F;
005    import static fj.P.p;
006    import static fj.P.p2;
007    import static fj.P.p3;
008    import static fj.P.p4;
009    import static fj.P.p5;
010    import static fj.P.p6;
011    import static fj.P.p7;
012    import static fj.P.p8;
013    import fj.P1;
014    import fj.P2;
015    import fj.P3;
016    import fj.P4;
017    import fj.P5;
018    import fj.P6;
019    import fj.P7;
020    import fj.P8;
021    import static fj.Primitive.Byte_Long;
022    import static fj.Primitive.Character_Long;
023    import static fj.Primitive.Double_Long;
024    import static fj.Primitive.Float_Long;
025    import static fj.Primitive.Integer_Long;
026    import static fj.Primitive.Long_Byte;
027    import static fj.Primitive.Long_Character;
028    import static fj.Primitive.Long_Double;
029    import static fj.Primitive.Long_Float;
030    import static fj.Primitive.Long_Integer;
031    import static fj.Primitive.Long_Short;
032    import static fj.Primitive.Short_Long;
033    import static fj.data.Array.array;
034    import fj.data.Conversions;
035    import static fj.data.List.isNotEmpty_;
036    import fj.data.Array;
037    import fj.data.Either;
038    import fj.data.Java;
039    import fj.data.List;
040    import fj.data.Option;
041    import fj.data.Stream;
042    import static fj.data.Stream.cons;
043    import static fj.data.Stream.iterate;
044    import static fj.data.Stream.nil;
045    
046    import static java.lang.System.arraycopy;
047    import java.math.BigDecimal;
048    import java.math.BigInteger;
049    import java.sql.Time;
050    import java.sql.Timestamp;
051    import java.util.ArrayList;
052    import java.util.BitSet;
053    import java.util.Calendar;
054    import java.util.Date;
055    import java.util.EnumMap;
056    import java.util.EnumSet;
057    import java.util.GregorianCalendar;
058    import java.util.HashMap;
059    import java.util.HashSet;
060    import java.util.Hashtable;
061    import java.util.IdentityHashMap;
062    import java.util.LinkedHashMap;
063    import java.util.LinkedHashSet;
064    import java.util.LinkedList;
065    import java.util.PriorityQueue;
066    import java.util.Properties;
067    import java.util.Stack;
068    import java.util.TreeMap;
069    import java.util.TreeSet;
070    import java.util.Vector;
071    import java.util.WeakHashMap;
072    import java.util.concurrent.ArrayBlockingQueue;
073    import java.util.concurrent.ConcurrentHashMap;
074    import java.util.concurrent.ConcurrentLinkedQueue;
075    import java.util.concurrent.CopyOnWriteArrayList;
076    import java.util.concurrent.CopyOnWriteArraySet;
077    import java.util.concurrent.DelayQueue;
078    import java.util.concurrent.Delayed;
079    import java.util.concurrent.LinkedBlockingQueue;
080    import java.util.concurrent.PriorityBlockingQueue;
081    import java.util.concurrent.SynchronousQueue;
082    
083    /**
084     * Represents a shrinking strategy over the given type parameter if that type can be represented as
085     * a tree structure. This is used in falsification to produce the smallest counter-example, rather
086     * than the first counter-example.
087     *
088     * @version %build.number%<br>
089     *          <ul>
090     *          <li>$LastChangedRevision: 163 $</li>
091     *          <li>$LastChangedDate: 2009-06-02 03:43:12 +1000 (Tue, 02 Jun 2009) $</li>
092     *          <li>$LastChangedBy: runarorama $</li>
093     *          </ul>
094     */
095    public final class Shrink<A> {
096      private final F<A, Stream<A>> f;
097    
098      private Shrink(final F<A, Stream<A>> f) {
099        this.f = f;
100      }
101    
102      /**
103       * Returns a shrink of the given argument.
104       *
105       * @param a The argument to shrink.
106       * @return A shrink of the given argument.
107       */
108      public Stream<A> shrink(final A a) {
109        return f.f(a);
110      }
111    
112      /**
113       * Creates a shrink from this shrink and the given symmetric transformations.
114       *
115       * @param f A transformation from this shrink type to the new shrink type.
116       * @param g A transformation from the new shrink type to this shrink type.
117       * @return A shrink from this shrink and the given symmetric transformations.
118       */
119      public <B> Shrink<B> map(final F<A, B> f, final F<B, A> g) {
120        return new Shrink<B>(new F<B, Stream<B>>() {
121          public Stream<B> f(final B b) {
122            return Shrink.this.f.f(g.f(b)).map(f);
123          }
124        });
125      }
126    
127    
128      /**
129       * Constructs a shrink strategy from the given function that produces a tree of values given a
130       * value.
131       *
132       * @param f A function that produces a tree of values given a value.
133       * @return A shrink strategy from the given function that produces a tree of values given a
134       *         value.
135       */
136      public static <A> Shrink<A> shrink(final F<A, Stream<A>> f) {
137        return new Shrink<A>(f);
138      }
139    
140      /**
141       * Returns a shrink strategy that cannot be reduced further.
142       *
143       * @return A shrink strategy that cannot be reduced further.
144       */
145      public static <A> Shrink<A> empty() {
146        return new Shrink<A>(new F<A, Stream<A>>() {
147          public Stream<A> f(final A a) {
148            return nil();
149          }
150        });
151      }
152    
153      /**
154       * A shrink strategy for longs using 0 as the bottom of the shrink.
155       */
156      public static final Shrink<Long> shrinkLong = new Shrink<Long>(new F<Long, Stream<Long>>() {
157        public Stream<Long> f(final Long i) {
158          if (i == 0L)
159            return nil();
160          else {
161            final Stream<Long> is = cons(0L, new P1<Stream<Long>>() {
162              public Stream<Long> _1() {
163                return iterate(new F<Long, Long>() {
164                  public Long f(final Long x) {
165                    return x / 2L;
166                  }
167                }, i).takeWhile(new F<Long, Boolean>() {
168                  public Boolean f(final Long x) {
169                    return x != 0L;
170                  }
171                }).map(new F<Long, Long>() {
172                  public Long f(final Long x) {
173                    return i - x;
174                  }
175                });
176              }
177            });
178    
179            return i < 0L ? cons(-i, new P1<Stream<Long>>() {
180              public Stream<Long> _1() {
181                return is;
182              }
183            }) : is;
184          }
185        }
186      });
187    
188      /**
189       * A shrink strategy for booleans using false as the bottom of the shrink.
190       */
191      public static final Shrink<Boolean> shrinkBoolean =
192          shrink(fj.Function.<Boolean, Stream<Boolean>>constant(Stream.single(false)));
193    
194      /**
195       * A shrink strategy for integers using 0 as the bottom of the shrink.
196       */
197      public static final Shrink<Integer> shrinkInteger = shrinkLong.map(Long_Integer, Integer_Long);
198    
199      /**
200       * A shrink strategy for bytes using 0 as the bottom of the shrink.
201       */
202      public static final Shrink<Byte> shrinkByte = shrinkLong.map(Long_Byte, Byte_Long);
203    
204      /**
205       * A shrink strategy for characters using 0 as the bottom of the shrink.
206       */
207      public static final Shrink<Character> shrinkCharacter = shrinkLong.map(Long_Character, Character_Long);
208    
209      /**
210       * A shrink strategy for shorts using 0 as the bottom of the shrink.
211       */
212      public static final Shrink<Short> shrinkShort = shrinkLong.map(Long_Short, Short_Long);
213    
214      /**
215       * A shrink strategy for floats using 0 as the bottom of the shrink.
216       */
217      public static final Shrink<Float> shrinkFloat = shrinkLong.map(Long_Float, Float_Long);
218    
219      /**
220       * A shrink strategy for doubles using 0 as the bottom of the shrink.
221       */
222      public static final Shrink<Double> shrinkDouble = shrinkLong.map(Long_Double, Double_Long);
223    
224      /**
225       * Returns a shrink strategy for optional values. A 'no value' is already fully
226       * shrunk, otherwise, the shrinking occurs on the value with the given shrink strategy.
227       *
228       * @param sa The shrink strategy for the potential value.
229       * @return A shrink strategy for optional values.
230       */
231      public static <A> Shrink<Option<A>> shrinkOption(final Shrink<A> sa) {
232        return new Shrink<Option<A>>(new F<Option<A>, Stream<Option<A>>>() {
233          public Stream<Option<A>> f(final Option<A> o) {
234            return o.isNone() ?
235                   Stream.<Option<A>>nil() :
236                   cons(Option.<A>none(), new P1<Stream<Option<A>>>() {
237                     public Stream<Option<A>> _1() {
238                       return sa.shrink(o.some()).map(Option.<A>some_());
239                     }
240                   });
241          }
242        });
243      }
244    
245      /**
246       * Returns a shrink strategy for either values.
247       *
248       * @param sa The shrinking strategy for left values.
249       * @param sb The shrinking strategy for right values.
250       * @return A shrink strategy for either values.
251       */
252      public static <A, B> Shrink<Either<A, B>> shrinkEither(final Shrink<A> sa, final Shrink<B> sb) {
253        return new Shrink<Either<A, B>>(new F<Either<A, B>, Stream<Either<A, B>>>() {
254          public Stream<Either<A, B>> f(final Either<A, B> e) {
255            return e.isLeft() ?
256                   sa.shrink(e.left().value()).map(Either.<A, B>left_()) :
257                   sb.shrink(e.right().value()).map(Either.<A, B>right_());
258          }
259        });
260      }
261    
262      /**
263       * Returns a shrink strategy for lists. An empty list is fully shrunk.
264       *
265       * @param sa The shrink strategy for the elements of the list.
266       * @return A shrink strategy for lists.
267       */
268      public static <A> Shrink<List<A>> shrinkList(final Shrink<A> sa) {
269        final class Util {
270          Stream<List<A>> removeChunks(final int n, final List<A> as) {
271            if (as.isEmpty())
272              return nil();
273            else if (as.tail().isEmpty())
274              return cons(List.<A>nil(), Stream.<List<A>>nil_());
275            else {
276              final int n1 = n / 2;
277              final int n2 = n - n1;
278    
279              final List<A> as1 = as.take(n1);
280              final F<List<A>, Boolean> isNotEmpty = isNotEmpty_();
281              return cons(as1, new P1<Stream<List<A>>>() {
282                public Stream<List<A>> _1() {
283                  final List<A> as2 = as.drop(n1);
284                  return cons(as2, new P1<Stream<List<A>>>() {
285                    public Stream<List<A>> _1() {
286                      return removeChunks(n1, as1).filter(isNotEmpty).map(new F<List<A>, List<A>>() {
287                        public List<A> f(final List<A> aas) {
288                          return aas.append(as2);
289                        }
290                      }).interleave(removeChunks(n2, as2).filter(isNotEmpty).map(new F<List<A>, List<A>>() {
291                        public List<A> f(final List<A> aas) {
292                          return as1.append(aas);
293                        }
294                      }));
295                    }
296                  });
297                }
298              });
299            }
300          }
301    
302          Stream<List<A>> shrinkOne(final List<A> as) {
303            if (as.isEmpty())
304              return nil();
305            else
306              return sa.shrink(as.head()).map(new F<A, List<A>>() {
307                public List<A> f(final A a) {
308                  return as.tail().cons(a);
309                }
310              }).append(shrinkOne(as.tail()).map(new F<List<A>, List<A>>() {
311                public List<A> f(final List<A> aas) {
312                  return aas.cons(as.head());
313                }
314              }));
315          }
316        }
317    
318        return new Shrink<List<A>>(new F<List<A>, Stream<List<A>>>() {
319          public Stream<List<A>> f(final List<A> as) {
320            final Util u = new Util();
321            return u.removeChunks(as.length(), as).append(u.shrinkOne(as));
322          }
323        });
324      }
325    
326      /**
327       * Returns a shrink strategy for arrays. An empty array is fully shrunk.
328       *
329       * @param sa The shrink strategy for the elements of the array.
330       * @return A shrink strategy for arrays.
331       */
332      public static <A> Shrink<Array<A>> shrinkArray(final Shrink<A> sa) {
333        return shrinkList(sa).map(Conversions.<A>List_Array(), Conversions.<A>Array_List());
334      }
335    
336      /**
337       * Returns a shrink strategy for streams. An empty stream is fully shrunk.
338       *
339       * @param sa The shrink strategy for the elements of the stream.
340       * @return A shrink strategy for streams.
341       */
342      public static <A> Shrink<Stream<A>> shrinkStream(final Shrink<A> sa) {
343        return shrinkList(sa).map(Conversions.<A>List_Stream(), Conversions.<A>Stream_List());
344      }
345    
346      /**
347       * A shrink strategy for strings using the empty string as the bottom of the shrink.
348       */
349      public static final Shrink<String> shrinkString =
350          shrinkList(shrinkCharacter).map(Conversions.List_String, Conversions.String_List);
351    
352      /**
353       * A shrink strategy for string buffers using the empty string as the bottom of the shrink.
354       */
355      public static final Shrink<StringBuffer> shrinkStringBuffer =
356          shrinkList(shrinkCharacter).map(Conversions.List_StringBuffer, Conversions.StringBuffer_List);
357    
358      /**
359       * A shrink strategy for string builders using the empty string as the bottom of the shrink.
360       */
361      public static final Shrink<StringBuilder> shrinkStringBuilder =
362          shrinkList(shrinkCharacter).map(Conversions.List_StringBuilder, Conversions.StringBuilder_List);
363    
364      /**
365       * A shrink strategy for throwables.
366       *
367       * @param ss A shrink strategy for throwable messages.
368       * @return A shrink strategy for throwables.
369       */
370      public static Shrink<Throwable> shrinkThrowable(final Shrink<String> ss) {
371        return ss.map(new F<String, Throwable>() {
372          public Throwable f(final String s) {
373            //noinspection ThrowableInstanceNeverThrown
374            return new Throwable(s);
375          }
376        }, new F<Throwable, String>() {
377          public String f(final Throwable t) {
378            return t.getMessage();
379          }
380        });
381      }
382    
383      /**
384       * A shrink strategy for throwables.
385       */
386      public static final Shrink<Throwable> shrinkThrowable = shrinkThrowable(shrinkString);
387    
388      // BEGIN java.util
389    
390      /**
391       * Returns a shrink strategy for array lists. An empty array list is fully shrunk.
392       *
393       * @param sa The shrink strategy for the elements of the array list.
394       * @return A shrink strategy for array lists.
395       */
396      public static <A> Shrink<ArrayList<A>> shrinkArrayList(final Shrink<A> sa) {
397        return shrinkList(sa).map(Java.<A>List_ArrayList(), Java.<A>ArrayList_List());
398      }
399    
400      /**
401       * A shrink strategy for bit sets.
402       */
403      public static final Shrink<BitSet> shrinkBitSet =
404          shrinkList(shrinkBoolean).map(Java.List_BitSet, Java.BitSet_List);
405    
406      /**
407       * A shrink strategy for calendars.
408       */
409      public static final Shrink<Calendar> shrinkCalendar =
410          shrinkLong.map(new F<Long, Calendar>() {
411            public Calendar f(final Long i) {
412              final Calendar c = Calendar.getInstance();
413              c.setTimeInMillis(i);
414              return c;
415            }
416          }, new F<Calendar, Long>() {
417            public Long f(final Calendar c) {
418              return c.getTime().getTime();
419            }
420          });
421    
422      /**
423       * A shrink strategy for dates.
424       */
425      public static final Shrink<Date> shrinkDate =
426          shrinkLong.map(new F<Long, Date>() {
427            public Date f(final Long i) {
428              return new Date(i);
429            }
430          }, new F<Date, Long>() {
431            public Long f(final Date d) {
432              return d.getTime();
433            }
434          });
435    
436      /**
437       * A shrink strategy for enum maps.
438       *
439       * @param sk The shrink strategy for keys.
440       * @param sv The shrink stratgey for values.
441       * @return A shrink strategy for enum maps.
442       */
443      public static <K extends Enum<K>, V> Shrink<EnumMap<K, V>> shrinkEnumMap(final Shrink<K> sk, final Shrink<V> sv) {
444        return shrinkHashtable(sk, sv).map(new F<Hashtable<K, V>, EnumMap<K, V>>() {
445          @SuppressWarnings({"UseOfObsoleteCollectionType"})
446          public EnumMap<K, V> f(final Hashtable<K, V> h) {
447            return new EnumMap<K, V>(h);
448          }
449        }, new F<EnumMap<K, V>, Hashtable<K, V>>() {
450          @SuppressWarnings({"UseOfObsoleteCollectionType"})
451          public Hashtable<K, V> f(final EnumMap<K, V> m) {
452            return new Hashtable<K, V>(m);
453          }
454        });
455      }
456    
457      /**
458       * A shrink strategy for enum sets.
459       *
460       * @param sa The shrink strategy for the elements.
461       * @return A shrink strategy for enum sets.
462       */
463      public static <A extends Enum<A>> Shrink<EnumSet<A>> shrinkEnumSet(final Shrink<A> sa) {
464        return shrinkList(sa).map(Java.<A>List_EnumSet(), Java.<A>EnumSet_List());
465      }
466    
467      /**
468       * A shrink strategy for gregorian calendars.
469       */
470      public static final Shrink<GregorianCalendar> shrinkGregorianCalendar =
471          shrinkLong.map(new F<Long, GregorianCalendar>() {
472            public GregorianCalendar f(final Long i) {
473              final GregorianCalendar c = new GregorianCalendar();
474              c.setTimeInMillis(i);
475              return c;
476            }
477          }, new F<GregorianCalendar, Long>() {
478            public Long f(final GregorianCalendar c) {
479              return c.getTime().getTime();
480            }
481          });
482    
483      /**
484       * A shrink strategy for hash maps.
485       *
486       * @param sk The shrink strategy for keys.
487       * @param sv The shrink stratgey for values.
488       * @return A shrink strategy for hash maps.
489       */
490      public static <K, V> Shrink<HashMap<K, V>> shrinkHashMap(final Shrink<K> sk, final Shrink<V> sv) {
491        return shrinkHashtable(sk, sv).map(new F<Hashtable<K, V>, HashMap<K, V>>() {
492          @SuppressWarnings({"UseOfObsoleteCollectionType"})
493          public HashMap<K, V> f(final Hashtable<K, V> h) {
494            return new HashMap<K, V>(h);
495          }
496        }, new F<HashMap<K, V>, Hashtable<K, V>>() {
497          @SuppressWarnings({"UseOfObsoleteCollectionType"})
498          public Hashtable<K, V> f(final HashMap<K, V> m) {
499            return new Hashtable<K, V>(m);
500          }
501        });
502      }
503    
504      /**
505       * A shrink strategy for hash sets.
506       *
507       * @param sa The shrink strategy for the elements.
508       * @return A shrink strategy for hash sets.
509       */
510      public static <A> Shrink<HashSet<A>> shrinkHashSet(final Shrink<A> sa) {
511        return shrinkList(sa).map(Java.<A>List_HashSet(), Java.<A>HashSet_List());
512      }
513    
514      /**
515       * A shrink strategy for hash tables.
516       *
517       * @param sk The shrink strategy for keys.
518       * @param sv The shrink stratgey for values.
519       * @return A shrink strategy for hash tables.
520       */
521      @SuppressWarnings({"UseOfObsoleteCollectionType"})
522      public static <K, V> Shrink<Hashtable<K, V>> shrinkHashtable(final Shrink<K> sk, final Shrink<V> sv) {
523        return shrinkList(shrinkP2(sk, sv)).map(new F<List<P2<K, V>>, Hashtable<K, V>>() {
524          @SuppressWarnings({"UseOfObsoleteCollectionType"})
525          public Hashtable<K, V> f(final List<P2<K, V>> kvs) {
526            final Hashtable<K, V> h = new Hashtable<K, V>();
527            kvs.foreach(new Effect<P2<K, V>>() {
528              public void e(final P2<K, V> kv) {
529                h.put(kv._1(), kv._2());
530              }
531            });
532            return h;
533          }
534        }, new F<Hashtable<K, V>, List<P2<K, V>>>() {
535          @SuppressWarnings({"UseOfObsoleteCollectionType"})
536          public List<P2<K, V>> f(final Hashtable<K, V> h) {
537            List<P2<K, V>> x = List.nil();
538    
539            for (final K k : h.keySet()) {
540              x = x.snoc(p(k, h.get(k)));
541            }
542    
543            return x;
544          }
545        });
546      }
547    
548      /**
549       * A shrink strategy for identity hash maps.
550       *
551       * @param sk The shrink strategy for keys.
552       * @param sv The shrink stratgey for values.
553       * @return A shrink strategy for identity hash maps.
554       */
555      public static <K, V> Shrink<IdentityHashMap<K, V>> shrinkIdentityHashMap(final Shrink<K> sk, final Shrink<V> sv) {
556        return shrinkHashtable(sk, sv).map(new F<Hashtable<K, V>, IdentityHashMap<K, V>>() {
557          @SuppressWarnings({"UseOfObsoleteCollectionType"})
558          public IdentityHashMap<K, V> f(final Hashtable<K, V> h) {
559            return new IdentityHashMap<K, V>(h);
560          }
561        }, new F<IdentityHashMap<K, V>, Hashtable<K, V>>() {
562          @SuppressWarnings({"UseOfObsoleteCollectionType"})
563          public Hashtable<K, V> f(final IdentityHashMap<K, V> m) {
564            return new Hashtable<K, V>(m);
565          }
566        });
567      }
568    
569      /**
570       * A shrink strategy for linked hash maps.
571       *
572       * @param sk The shrink strategy for keys.
573       * @param sv The shrink stratgey for values.
574       * @return A shrink strategy for linked hash maps.
575       */
576      public static <K, V> Shrink<LinkedHashMap<K, V>> shrinkLinkedHashMap(final Shrink<K> sk, final Shrink<V> sv) {
577        return shrinkHashtable(sk, sv).map(new F<Hashtable<K, V>, LinkedHashMap<K, V>>() {
578          @SuppressWarnings({"UseOfObsoleteCollectionType"})
579          public LinkedHashMap<K, V> f(final Hashtable<K, V> h) {
580            return new LinkedHashMap<K, V>(h);
581          }
582        }, new F<LinkedHashMap<K, V>, Hashtable<K, V>>() {
583          @SuppressWarnings({"UseOfObsoleteCollectionType"})
584          public Hashtable<K, V> f(final LinkedHashMap<K, V> m) {
585            return new Hashtable<K, V>(m);
586          }
587        });
588      }
589    
590      /**
591       * A shrink strategy for linked hash sets.
592       *
593       * @param sa The shrink strategy for the elements.
594       * @return A shrink strategy for linked hash sets.
595       */
596      public static <A> Shrink<LinkedHashSet<A>> shrinkLinkedHashSet(final Shrink<A> sa) {
597        return shrinkList(sa).map(Java.<A>List_LinkedHashSet(), Java.<A>LinkedHashSet_List());
598      }
599    
600      /**
601       * A shrink strategy for linked lists.
602       *
603       * @param sa The shrink strategy for the elements.
604       * @return A shrink strategy for linked lists.
605       */
606      public static <A> Shrink<LinkedList<A>> shrinkLinkedList(final Shrink<A> sa) {
607        return shrinkList(sa).map(Java.<A>List_LinkedList(), Java.<A>LinkedList_List());
608      }
609    
610      /**
611       * A shrink strategy for priority queues.
612       *
613       * @param sa The shrink strategy for the elements.
614       * @return A shrink strategy for priority queues.
615       */
616      public static <A> Shrink<PriorityQueue<A>> shrinkPriorityQueue(final Shrink<A> sa) {
617        return shrinkList(sa).map(Java.<A>List_PriorityQueue(), Java.<A>PriorityQueue_List());
618      }
619    
620      /**
621       * A shrink strategy for properties.
622       */
623      public static final Shrink<Properties> shrinkProperties = shrinkHashtable(shrinkString, shrinkString)
624          .map(new F<Hashtable<String, String>, Properties>() {
625            @SuppressWarnings({"UseOfObsoleteCollectionType"})
626            public Properties f(final Hashtable<String, String> h) {
627              final Properties p = new Properties();
628    
629              for (final String k : h.keySet()) {
630                p.setProperty(k, h.get(k));
631              }
632    
633              return p;
634            }
635          }, new F<Properties, Hashtable<String, String>>() {
636            @SuppressWarnings({"UseOfObsoleteCollectionType"})
637            public Hashtable<String, String> f(final Properties p) {
638              final Hashtable<String, String> t = new Hashtable<String, String>();
639    
640              for (final Object s : p.keySet()) {
641                t.put((String) s, p.getProperty((String) s));
642              }
643    
644              return t;
645            }
646          });
647    
648      /**
649       * A shrink strategy for stacks.
650       *
651       * @param sa The shrink strategy for the elements.
652       * @return A shrink strategy for stacks.
653       */
654      public static <A> Shrink<Stack<A>> shrinkStack(final Shrink<A> sa) {
655        return shrinkList(sa).map(Java.<A>List_Stack(), Java.<A>Stack_List());
656      }
657    
658      /**
659       * A shrink strategy for tree maps.
660       *
661       * @param sk The shrink strategy for keys.
662       * @param sv The shrink stratgey for values.
663       * @return A shrink strategy for tree maps.
664       */
665      public static <K, V> Shrink<TreeMap<K, V>> shrinkTreeMap(final Shrink<K> sk, final Shrink<V> sv) {
666        return shrinkHashtable(sk, sv).map(new F<Hashtable<K, V>, TreeMap<K, V>>() {
667          @SuppressWarnings({"UseOfObsoleteCollectionType"})
668          public TreeMap<K, V> f(final Hashtable<K, V> h) {
669            return new TreeMap<K, V>(h);
670          }
671        }, new F<TreeMap<K, V>, Hashtable<K, V>>() {
672          @SuppressWarnings({"UseOfObsoleteCollectionType"})
673          public Hashtable<K, V> f(final TreeMap<K, V> m) {
674            return new Hashtable<K, V>(m);
675          }
676        });
677      }
678    
679      /**
680       * A shrink strategy for tree sets.
681       *
682       * @param sa The shrink strategy for the elements.
683       * @return A shrink strategy for tree sets.
684       */
685      public static <A> Shrink<TreeSet<A>> shrinkTreeSet(final Shrink<A> sa) {
686        return shrinkList(sa).map(Java.<A>List_TreeSet(), Java.<A>TreeSet_List());
687      }
688    
689      /**
690       * A shrink strategy for vectors.
691       *
692       * @param sa The shrink strategy for the elements.
693       * @return A shrink strategy for vectors.
694       */
695      public static <A> Shrink<Vector<A>> shrinkVector(final Shrink<A> sa) {
696        return shrinkList(sa).map(Java.<A>List_Vector(), Java.<A>Vector_List());
697      }
698    
699      /**
700       * A shrink strategy for weak hash maps.
701       *
702       * @param sk The shrink strategy for keys.
703       * @param sv The shrink stratgey for values.
704       * @return A shrink strategy for weak hash maps.
705       */
706      public static <K, V> Shrink<WeakHashMap<K, V>> shrinkWeakHashMap(final Shrink<K> sk, final Shrink<V> sv) {
707        return shrinkHashtable(sk, sv).map(new F<Hashtable<K, V>, WeakHashMap<K, V>>() {
708          @SuppressWarnings({"UseOfObsoleteCollectionType"})
709          public WeakHashMap<K, V> f(final Hashtable<K, V> h) {
710            return new WeakHashMap<K, V>(h);
711          }
712        }, new F<WeakHashMap<K, V>, Hashtable<K, V>>() {
713          @SuppressWarnings({"UseOfObsoleteCollectionType"})
714          public Hashtable<K, V> f(final WeakHashMap<K, V> m) {
715            return new Hashtable<K, V>(m);
716          }
717        });
718      }
719    
720      // END java.util
721    
722      // BEGIN java.util.concurrent
723    
724      /**
725       * A shrink strategy for array blocking queues.
726       *
727       * @param sa The shrink strategy for the elements.
728       * @return A shrink strategy for array blocking queues.
729       */
730      public static <A> Shrink<ArrayBlockingQueue<A>> shrinkArrayBlockingQueue(final Shrink<A> sa) {
731        return shrinkList(sa).map(Java.<A>List_ArrayBlockingQueue(false), Java.<A>ArrayBlockingQueue_List());
732      }
733    
734      /**
735       * A shrink strategy for concurrent hash maps.
736       *
737       * @param sk The shrink strategy for keys.
738       * @param sv The shrink stratgey for values.
739       * @return A shrink strategy for concurrent hash maps.
740       */
741      public static <K, V> Shrink<ConcurrentHashMap<K, V>> shrinkConcurrentHashMap(final Shrink<K> sk, final Shrink<V> sv) {
742        return shrinkHashtable(sk, sv).map(new F<Hashtable<K, V>, ConcurrentHashMap<K, V>>() {
743          @SuppressWarnings({"UseOfObsoleteCollectionType"})
744          public ConcurrentHashMap<K, V> f(final Hashtable<K, V> h) {
745            return new ConcurrentHashMap<K, V>(h);
746          }
747        }, new F<ConcurrentHashMap<K, V>, Hashtable<K, V>>() {
748          @SuppressWarnings({"UseOfObsoleteCollectionType"})
749          public Hashtable<K, V> f(final ConcurrentHashMap<K, V> m) {
750            return new Hashtable<K, V>(m);
751          }
752        });
753      }
754    
755      /**
756       * A shrink strategy for concurrent linked queues.
757       *
758       * @param sa The shrink strategy for the elements.
759       * @return A shrink strategy for concurrent linked queues.
760       */
761      public static <A> Shrink<ConcurrentLinkedQueue<A>> shrinkConcurrentLinkedQueue(final Shrink<A> sa) {
762        return shrinkList(sa).map(Java.<A>List_ConcurrentLinkedQueue(), Java.<A>ConcurrentLinkedQueue_List());
763      }
764    
765      /**
766       * A shrink strategy for copy on write array lists.
767       *
768       * @param sa The shrink strategy for the elements.
769       * @return A shrink strategy for copy on write array lists.
770       */
771      public static <A> Shrink<CopyOnWriteArrayList<A>> shrinkCopyOnWriteArrayList(final Shrink<A> sa) {
772        return shrinkList(sa).map(Java.<A>List_CopyOnWriteArrayList(), Java.<A>CopyOnWriteArrayList_List());
773      }
774    
775      /**
776       * A shrink strategy for copy on write array sets.
777       *
778       * @param sa The shrink strategy for the elements.
779       * @return A shrink strategy for copy on write array sets.
780       */
781      public static <A> Shrink<CopyOnWriteArraySet<A>> shrinkCopyOnWriteArraySet(final Shrink<A> sa) {
782        return shrinkList(sa).map(Java.<A>List_CopyOnWriteArraySet(), Java.<A>CopyOnWriteArraySet_List());
783      }
784    
785      /**
786       * A shrink strategy for delay queues.
787       *
788       * @param sa The shrink strategy for the elements.
789       * @return A shrink strategy for delay queues.
790       */
791      public static <A extends Delayed> Shrink<DelayQueue<A>> shrinkDelayQueue(final Shrink<A> sa) {
792        return shrinkList(sa).map(Java.<A>List_DelayQueue(), Java.<A>DelayQueue_List());
793      }
794    
795      /**
796       * A shrink strategy for linked blocking queues.
797       *
798       * @param sa The shrink strategy for the elements.
799       * @return A shrink strategy for linked blocking queues.
800       */
801      public static <A> Shrink<LinkedBlockingQueue<A>> shrinkLinkedBlockingQueue(final Shrink<A> sa) {
802        return shrinkList(sa).map(Java.<A>List_LinkedBlockingQueue(), Java.<A>LinkedBlockingQueue_List());
803      }
804    
805      /**
806       * A shrink strategy for priority blocking queues.
807       *
808       * @param sa The shrink strategy for the elements.
809       * @return A shrink strategy for priority blocking queues.
810       */
811      public static <A> Shrink<PriorityBlockingQueue<A>> shrinkPriorityBlockingQueue(final Shrink<A> sa) {
812        return shrinkList(sa).map(Java.<A>List_PriorityBlockingQueue(), Java.<A>PriorityBlockingQueue_List());
813      }
814    
815      /**
816       * A shrink strategy for synchronous queues.
817       *
818       * @param sa The shrink strategy for the elements.
819       * @return A shrink strategy for synchronous queues.
820       */
821      public static <A> Shrink<SynchronousQueue<A>> shrinkSynchronousQueue(final Shrink<A> sa) {
822        return shrinkList(sa).map(Java.<A>List_SynchronousQueue(false), Java.<A>SynchronousQueue_List());
823      }
824    
825      // END java.util.concurrent
826    
827      // BEGIN java.sql
828    
829      /**
830       * A shrink strategy for SQL dates.
831       */
832      public static final Shrink<java.sql.Date> shrinkSQLDate =
833          shrinkLong.map(new F<Long, java.sql.Date>() {
834            public java.sql.Date f(final Long i) {
835              return new java.sql.Date(i);
836            }
837          }, new F<java.sql.Date, Long>() {
838            public Long f(final java.sql.Date c) {
839              return c.getTime();
840            }
841          });
842    
843      /**
844       * A shrink strategy for SQL times.
845       */
846      public static final Shrink<Time> shrinkTime =
847          shrinkLong.map(new F<Long, Time>() {
848            public Time f(final Long i) {
849              return new Time(i);
850            }
851          }, new F<Time, Long>() {
852            public Long f(final Time c) {
853              return c.getTime();
854            }
855          });
856    
857      /**
858       * A shrink strategy for SQL timestamps.
859       */
860      public static final Shrink<Timestamp> shrinkTimestamp =
861          shrinkLong.map(new F<Long, Timestamp>() {
862            public Timestamp f(final Long i) {
863              return new Timestamp(i);
864            }
865          }, new F<Timestamp, Long>() {
866            public Long f(final Timestamp c) {
867              return c.getTime();
868            }
869          });
870    
871      // END java.sql
872    
873      // BEGIN java.math
874    
875      /**
876       * A shrink strategy for big integers.
877       */
878      public static final Shrink<BigInteger> shrinkBigInteger =
879          shrinkP2(shrinkByte, shrinkArray(shrinkByte)).map(new F<P2<Byte, Array<Byte>>, BigInteger>() {
880            public BigInteger f(final P2<Byte, Array<Byte>> bs) {
881              final byte[] x = new byte[bs._2().length() + 1];
882    
883              for (int i = 0; i < bs._2().array().length; i++) {
884                x[i] = bs._2().get(i);
885              }
886    
887              x[bs._2().length()] = bs._1();
888    
889              return new BigInteger(x);
890            }
891          }, new F<BigInteger, P2<Byte, Array<Byte>>>() {
892            public P2<Byte, Array<Byte>> f(final BigInteger i) {
893              final byte[] b = i.toByteArray();
894              final Byte[] x = new Byte[b.length - 1];
895              arraycopy(b, 0, x, 0, b.length - 1);
896              return p(b[0], array(x));
897            }
898          });
899    
900      /**
901       * A shrink strategy for big decimals.
902       */
903      public static final Shrink<BigDecimal> shrinkBigDecimal =
904          shrinkBigInteger.map(new F<BigInteger, BigDecimal>() {
905            public BigDecimal f(final BigInteger i) {
906              return new BigDecimal(i);
907            }
908          }, new F<BigDecimal, BigInteger>() {
909            public BigInteger f(final BigDecimal d) {
910              return d.toBigInteger();
911            }
912          });
913    
914      // END java.math
915    
916      /**
917       * Returns a shrinking strategy for product-1 values.
918       *
919       * @param sa The shrinking strategy for the values.
920       * @return a shrinking strategy for product-1 values.
921       */
922      public static <A> Shrink<P1<A>> shrinkP1(final Shrink<A> sa) {
923        return new Shrink<P1<A>>(new F<P1<A>, Stream<P1<A>>>() {
924          public Stream<P1<A>> f(final P1<A> p) {
925            return sa.shrink(p._1()).map(new F<A, P1<A>>() {
926              public P1<A> f(final A a) {
927                return p(a);
928              }
929            });
930          }
931        });
932      }
933    
934      /**
935       * Returns a shrinking strategy for product-2 values.
936       *
937       * @param sa The shrinking strategy for the values.
938       * @param sb The shrinking strategy for the values.
939       * @return a shrinking strategy for product-2 values.
940       */
941      public static <A, B> Shrink<P2<A, B>> shrinkP2(final Shrink<A> sa, final Shrink<B> sb) {
942        return new Shrink<P2<A, B>>(new F<P2<A, B>, Stream<P2<A, B>>>() {
943          public Stream<P2<A, B>> f(final P2<A, B> p) {
944            final F<A, F<B, P2<A, B>>> p2 = p2();
945            return sa.shrink(p._1()).bind(sb.shrink(p._2()), p2);
946          }
947        });
948      }
949    
950      /**
951       * Returns a shrinking strategy for product-3 values.
952       *
953       * @param sa The shrinking strategy for the values.
954       * @param sb The shrinking strategy for the values.
955       * @param sc The shrinking strategy for the values.
956       * @return a shrinking strategy for product-3 values.
957       */
958      public static <A, B, C> Shrink<P3<A, B, C>> shrinkP3(final Shrink<A> sa, final Shrink<B> sb, final Shrink<C> sc) {
959        return new Shrink<P3<A, B, C>>(new F<P3<A, B, C>, Stream<P3<A, B, C>>>() {
960          public Stream<P3<A, B, C>> f(final P3<A, B, C> p) {
961            final F<A, F<B, F<C, P3<A, B, C>>>> p3 = p3();
962            return sa.shrink(p._1()).bind(sb.shrink(p._2()), sc.shrink(p._3()), p3);
963          }
964        });
965      }
966    
967      /**
968       * Returns a shrinking strategy for product-4 values.
969       *
970       * @param sa The shrinking strategy for the values.
971       * @param sb The shrinking strategy for the values.
972       * @param sc The shrinking strategy for the values.
973       * @param sd The shrinking strategy for the values.
974       * @return a shrinking strategy for product-4 values.
975       */
976      public static <A, B, C, D> Shrink<P4<A, B, C, D>> shrinkP4(final Shrink<A> sa, final Shrink<B> sb, final Shrink<C> sc,
977                                                                 final Shrink<D> sd) {
978        return new Shrink<P4<A, B, C, D>>(new F<P4<A, B, C, D>, Stream<P4<A, B, C, D>>>() {
979          public Stream<P4<A, B, C, D>> f(final P4<A, B, C, D> p) {
980            final F<A, F<B, F<C, F<D, P4<A, B, C, D>>>>> p4 = p4();
981            return sa.shrink(p._1()).bind(sb.shrink(p._2()), sc.shrink(p._3()), sd.shrink(p._4()), p4);
982          }
983        });
984      }
985    
986      /**
987       * Returns a shrinking strategy for product-5 values.
988       *
989       * @param sa The shrinking strategy for the values.
990       * @param sb The shrinking strategy for the values.
991       * @param sc The shrinking strategy for the values.
992       * @param sd The shrinking strategy for the values.
993       * @param se The shrinking strategy for the values.
994       * @return a shrinking strategy for product-5 values.
995       */
996      public static <A, B, C, D, E> Shrink<P5<A, B, C, D, E>> shrinkP5(final Shrink<A> sa, final Shrink<B> sb,
997                                                                       final Shrink<C> sc, final Shrink<D> sd,
998                                                                       final Shrink<E> se) {
999        return new Shrink<P5<A, B, C, D, E>>(new F<P5<A, B, C, D, E>, Stream<P5<A, B, C, D, E>>>() {
1000          public Stream<P5<A, B, C, D, E>> f(final P5<A, B, C, D, E> p) {
1001            final F<A, F<B, F<C, F<D, F<E, P5<A, B, C, D, E>>>>>> p5 = p5();
1002            return sa.shrink(p._1()).bind(sb.shrink(p._2()), sc.shrink(p._3()), sd.shrink(p._4()), se.shrink(p._5()), p5);
1003          }
1004        });
1005      }
1006    
1007      /**
1008       * Returns a shrinking strategy for product-6 values.
1009       *
1010       * @param sa The shrinking strategy for the values.
1011       * @param sb The shrinking strategy for the values.
1012       * @param sc The shrinking strategy for the values.
1013       * @param sd The shrinking strategy for the values.
1014       * @param se The shrinking strategy for the values.
1015       * @param sf The shrinking strategy for the values.
1016       * @return a shrinking strategy for product-6 values.
1017       */
1018      public static <A, B, C, D, E, F$> Shrink<P6<A, B, C, D, E, F$>> shrinkP6(final Shrink<A> sa, final Shrink<B> sb,
1019                                                                               final Shrink<C> sc, final Shrink<D> sd,
1020                                                                               final Shrink<E> se, final Shrink<F$> sf) {
1021        return new Shrink<P6<A, B, C, D, E, F$>>(new F<P6<A, B, C, D, E, F$>, Stream<P6<A, B, C, D, E, F$>>>() {
1022          public Stream<P6<A, B, C, D, E, F$>> f(final P6<A, B, C, D, E, F$> p) {
1023            final F<A, F<B, F<C, F<D, F<E, F<F$, P6<A, B, C, D, E, F$>>>>>>> p6 = p6();
1024            return sa.shrink(p._1())
1025                .bind(sb.shrink(p._2()), sc.shrink(p._3()), sd.shrink(p._4()), se.shrink(p._5()), sf.shrink(p._6()), p6);
1026          }
1027        });
1028      }
1029    
1030      /**
1031       * Returns a shrinking strategy for product-7 values.
1032       *
1033       * @param sa The shrinking strategy for the values.
1034       * @param sb The shrinking strategy for the values.
1035       * @param sc The shrinking strategy for the values.
1036       * @param sd The shrinking strategy for the values.
1037       * @param se The shrinking strategy for the values.
1038       * @param sf The shrinking strategy for the values.
1039       * @param sg The shrinking strategy for the values.
1040       * @return a shrinking strategy for product-7 values.
1041       */
1042      public static <A, B, C, D, E, F$, G> Shrink<P7<A, B, C, D, E, F$, G>> shrinkP7(final Shrink<A> sa, final Shrink<B> sb,
1043                                                                                     final Shrink<C> sc, final Shrink<D> sd,
1044                                                                                     final Shrink<E> se,
1045                                                                                     final Shrink<F$> sf,
1046                                                                                     final Shrink<G> sg) {
1047        return new Shrink<P7<A, B, C, D, E, F$, G>>(new F<P7<A, B, C, D, E, F$, G>, Stream<P7<A, B, C, D, E, F$, G>>>() {
1048          public Stream<P7<A, B, C, D, E, F$, G>> f(final P7<A, B, C, D, E, F$, G> p) {
1049            final F<A, F<B, F<C, F<D, F<E, F<F$, F<G, P7<A, B, C, D, E, F$, G>>>>>>>> p7 = p7();
1050            return sa.shrink(p._1())
1051                .bind(sb.shrink(p._2()), sc.shrink(p._3()), sd.shrink(p._4()), se.shrink(p._5()), sf.shrink(p._6()),
1052                      sg.shrink(p._7()), p7);
1053          }
1054        });
1055      }
1056    
1057      /**
1058       * Returns a shrinking strategy for product-8 values.
1059       *
1060       * @param sa The shrinking strategy for the values.
1061       * @param sb The shrinking strategy for the values.
1062       * @param sc The shrinking strategy for the values.
1063       * @param sd The shrinking strategy for the values.
1064       * @param se The shrinking strategy for the values.
1065       * @param sf The shrinking strategy for the values.
1066       * @param sg The shrinking strategy for the values.
1067       * @param sh The shrinking strategy for the values.
1068       * @return a shrinking strategy for product-8 values.
1069       */
1070      public static <A, B, C, D, E, F$, G, H> Shrink<P8<A, B, C, D, E, F$, G, H>> shrinkP8(final Shrink<A> sa,
1071                                                                                           final Shrink<B> sb,
1072                                                                                           final Shrink<C> sc,
1073                                                                                           final Shrink<D> sd,
1074                                                                                           final Shrink<E> se,
1075                                                                                           final Shrink<F$> sf,
1076                                                                                           final Shrink<G> sg,
1077                                                                                           final Shrink<H> sh) {
1078        return new Shrink<P8<A, B, C, D, E, F$, G, H>>(
1079            new F<P8<A, B, C, D, E, F$, G, H>, Stream<P8<A, B, C, D, E, F$, G, H>>>() {
1080              public Stream<P8<A, B, C, D, E, F$, G, H>> f(final P8<A, B, C, D, E, F$, G, H> p) {
1081                final F<A, F<B, F<C, F<D, F<E, F<F$, F<G, F<H, P8<A, B, C, D, E, F$, G, H>>>>>>>>> p8 = p8();
1082                return sa.shrink(p._1())
1083                    .bind(sb.shrink(p._2()), sc.shrink(p._3()), sd.shrink(p._4()), se.shrink(p._5()), sf.shrink(p._6()),
1084                          sg.shrink(p._7()), sh.shrink(p._8()), p8);
1085              }
1086            });
1087      }
1088    }