1/*
2 * Copyright (C) 2012 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect.testing.google;
18
19import static com.google.common.base.Preconditions.checkArgument;
20import static com.google.common.collect.testing.Helpers.mapEntry;
21
22import com.google.common.collect.ImmutableList;
23import com.google.common.collect.ImmutableMultimap;
24import com.google.common.collect.Multimap;
25import com.google.common.collect.Multiset;
26import com.google.common.collect.testing.AbstractTester;
27import com.google.common.collect.testing.CollectionTestSuiteBuilder;
28import com.google.common.collect.testing.DerivedGenerator;
29import com.google.common.collect.testing.FeatureSpecificTestSuiteBuilder;
30import com.google.common.collect.testing.Helpers;
31import com.google.common.collect.testing.MapTestSuiteBuilder;
32import com.google.common.collect.testing.OneSizeTestContainerGenerator;
33import com.google.common.collect.testing.PerCollectionSizeTestSuiteBuilder;
34import com.google.common.collect.testing.SampleElements;
35import com.google.common.collect.testing.TestCollectionGenerator;
36import com.google.common.collect.testing.TestMapGenerator;
37import com.google.common.collect.testing.TestSubjectGenerator;
38import com.google.common.collect.testing.features.CollectionFeature;
39import com.google.common.collect.testing.features.CollectionSize;
40import com.google.common.collect.testing.features.Feature;
41import com.google.common.collect.testing.features.ListFeature;
42import com.google.common.collect.testing.features.MapFeature;
43import com.google.common.testing.SerializableTester;
44
45import junit.framework.TestSuite;
46
47import java.util.ArrayList;
48import java.util.Collection;
49import java.util.Collections;
50import java.util.EnumSet;
51import java.util.HashMap;
52import java.util.HashSet;
53import java.util.Iterator;
54import java.util.LinkedHashMap;
55import java.util.List;
56import java.util.Map;
57import java.util.Map.Entry;
58import java.util.Set;
59
60/**
61 * Creates, based on your criteria, a JUnit test suite that exhaustively tests
62 * a {@code Multimap} implementation.
63 *
64 * @author Louis Wasserman
65 */
66public class MultimapTestSuiteBuilder<K, V, M extends Multimap<K, V>> extends
67    PerCollectionSizeTestSuiteBuilder<
68    MultimapTestSuiteBuilder<K, V, M>,
69    TestMultimapGenerator<K, V, M>, M, Map.Entry<K, V>> {
70
71  public static <K, V, M extends Multimap<K, V>> MultimapTestSuiteBuilder<K, V, M> using(
72      TestMultimapGenerator<K, V, M> generator) {
73    return new MultimapTestSuiteBuilder<K, V, M>().usingGenerator(generator);
74  }
75
76  // Class parameters must be raw.
77  @Override
78  protected List<Class<? extends AbstractTester>> getTesters() {
79    return ImmutableList.<Class<? extends AbstractTester>> of(
80        MultimapAsMapGetTester.class,
81        MultimapAsMapTester.class,
82        MultimapSizeTester.class,
83        MultimapClearTester.class,
84        MultimapContainsKeyTester.class,
85        MultimapContainsValueTester.class,
86        MultimapContainsEntryTester.class,
87        MultimapEntriesTester.class,
88        MultimapEqualsTester.class,
89        MultimapGetTester.class,
90        MultimapKeySetTester.class,
91        MultimapKeysTester.class,
92        MultimapPutTester.class,
93        MultimapPutAllMultimapTester.class,
94        MultimapPutIterableTester.class,
95        MultimapReplaceValuesTester.class,
96        MultimapRemoveEntryTester.class,
97        MultimapRemoveAllTester.class,
98        MultimapToStringTester.class,
99        MultimapValuesTester.class);
100  }
101
102  @Override
103  protected List<TestSuite> createDerivedSuites(
104      FeatureSpecificTestSuiteBuilder<
105      ?,
106      ? extends OneSizeTestContainerGenerator<M, Map.Entry<K, V>>>
107      parentBuilder) {
108    // TODO: Once invariant support is added, supply invariants to each of the
109    // derived suites, to check that mutations to the derived collections are
110    // reflected in the underlying map.
111
112    List<TestSuite> derivedSuites = super.createDerivedSuites(parentBuilder);
113
114    if (parentBuilder.getFeatures().contains(CollectionFeature.SERIALIZABLE)) {
115      derivedSuites.add(MultimapTestSuiteBuilder.using(
116          new ReserializedMultimapGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
117          .withFeatures(computeReserializedMultimapFeatures(parentBuilder.getFeatures()))
118          .named(parentBuilder.getName() + " reserialized")
119          .suppressing(parentBuilder.getSuppressedTests())
120          .createTestSuite());
121    }
122
123    derivedSuites.add(MapTestSuiteBuilder.using(
124        new AsMapGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
125        .withFeatures(computeAsMapFeatures(parentBuilder.getFeatures()))
126        .named(parentBuilder.getName() + ".asMap")
127        .suppressing(parentBuilder.getSuppressedTests())
128        .createTestSuite());
129
130    derivedSuites.add(computeEntriesTestSuite(parentBuilder));
131    derivedSuites.add(computeMultimapGetTestSuite(parentBuilder));
132    derivedSuites.add(computeMultimapAsMapGetTestSuite(parentBuilder));
133    derivedSuites.add(computeKeysTestSuite(parentBuilder));
134    derivedSuites.add(computeValuesTestSuite(parentBuilder));
135
136    return derivedSuites;
137  }
138
139  TestSuite computeValuesTestSuite(
140      FeatureSpecificTestSuiteBuilder<?, ?
141          extends OneSizeTestContainerGenerator<M, Map.Entry<K, V>>> parentBuilder) {
142    return CollectionTestSuiteBuilder.using(
143        new ValuesGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
144        .withFeatures(computeValuesFeatures(parentBuilder.getFeatures()))
145        .named(parentBuilder.getName() + ".values")
146        .suppressing(parentBuilder.getSuppressedTests())
147        .createTestSuite();
148  }
149
150  TestSuite computeEntriesTestSuite(
151      FeatureSpecificTestSuiteBuilder<?, ?
152          extends OneSizeTestContainerGenerator<M, Map.Entry<K, V>>> parentBuilder) {
153    return CollectionTestSuiteBuilder.using(
154        new EntriesGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
155        .withFeatures(computeEntriesFeatures(parentBuilder.getFeatures()))
156        .named(parentBuilder.getName() + ".entries")
157        .suppressing(parentBuilder.getSuppressedTests())
158        .createTestSuite();
159  }
160
161  TestSuite computeMultimapGetTestSuite(
162      FeatureSpecificTestSuiteBuilder<?, ? extends
163          OneSizeTestContainerGenerator<M, Map.Entry<K, V>>> parentBuilder) {
164    return CollectionTestSuiteBuilder.using(
165        new MultimapGetGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
166        .withFeatures(computeMultimapGetFeatures(parentBuilder.getFeatures()))
167        .named(parentBuilder.getName() + ".get[key]")
168        .suppressing(parentBuilder.getSuppressedTests())
169        .createTestSuite();
170  }
171
172  TestSuite computeMultimapAsMapGetTestSuite(
173      FeatureSpecificTestSuiteBuilder<?, ? extends
174          OneSizeTestContainerGenerator<M, Map.Entry<K, V>>> parentBuilder) {
175    Set<Feature<?>> features = computeMultimapAsMapGetFeatures(parentBuilder.getFeatures());
176    if (Collections.disjoint(features, EnumSet.allOf(CollectionSize.class))) {
177      return new TestSuite();
178    } else {
179      return CollectionTestSuiteBuilder.using(
180          new MultimapAsMapGetGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
181          .withFeatures(features)
182          .named(parentBuilder.getName() + ".asMap[].get[key]")
183          .suppressing(parentBuilder.getSuppressedTests())
184          .createTestSuite();
185    }
186  }
187
188  TestSuite computeKeysTestSuite(
189      FeatureSpecificTestSuiteBuilder<?, ? extends
190          OneSizeTestContainerGenerator<M, Map.Entry<K, V>>> parentBuilder) {
191    return MultisetTestSuiteBuilder.using(
192        new KeysGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
193        .withFeatures(computeKeysFeatures(parentBuilder.getFeatures()))
194        .named(parentBuilder.getName() + ".keys")
195        .suppressing(parentBuilder.getSuppressedTests())
196        .createTestSuite();
197  }
198
199  static Set<Feature<?>> computeDerivedCollectionFeatures(Set<Feature<?>> multimapFeatures) {
200    Set<Feature<?>> derivedFeatures = Helpers.copyToSet(multimapFeatures);
201    if (!derivedFeatures.remove(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS)) {
202      derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
203    }
204    if (derivedFeatures.remove(MapFeature.SUPPORTS_REMOVE)) {
205      derivedFeatures.add(CollectionFeature.SUPPORTS_REMOVE);
206    }
207    return derivedFeatures;
208  }
209
210  static Set<Feature<?>> computeEntriesFeatures(
211      Set<Feature<?>> multimapFeatures) {
212    Set<Feature<?>> result = computeDerivedCollectionFeatures(multimapFeatures);
213    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_ENTRY_QUERIES)) {
214      result.add(CollectionFeature.ALLOWS_NULL_QUERIES);
215    }
216    return result;
217  }
218
219  static Set<Feature<?>> computeValuesFeatures(
220      Set<Feature<?>> multimapFeatures) {
221    Set<Feature<?>> result = computeDerivedCollectionFeatures(multimapFeatures);
222    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_VALUES)) {
223      result.add(CollectionFeature.ALLOWS_NULL_VALUES);
224    }
225    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_VALUE_QUERIES)) {
226      result.add(CollectionFeature.ALLOWS_NULL_QUERIES);
227    }
228    return result;
229  }
230
231  static Set<Feature<?>> computeKeysFeatures(
232      Set<Feature<?>> multimapFeatures) {
233    Set<Feature<?>> result = computeDerivedCollectionFeatures(multimapFeatures);
234    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_KEYS)) {
235      result.add(CollectionFeature.ALLOWS_NULL_VALUES);
236    }
237    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_KEY_QUERIES)) {
238      result.add(CollectionFeature.ALLOWS_NULL_QUERIES);
239    }
240    return result;
241  }
242
243  private static Set<Feature<?>> computeReserializedMultimapFeatures(
244      Set<Feature<?>> multimapFeatures) {
245    Set<Feature<?>> derivedFeatures = Helpers.copyToSet(multimapFeatures);
246    derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
247    derivedFeatures.remove(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS);
248    return derivedFeatures;
249  }
250
251  private static Set<Feature<?>> computeAsMapFeatures(
252      Set<Feature<?>> multimapFeatures) {
253    Set<Feature<?>> derivedFeatures = Helpers.copyToSet(multimapFeatures);
254    derivedFeatures.remove(MapFeature.GENERAL_PURPOSE);
255    derivedFeatures.remove(MapFeature.SUPPORTS_PUT);
256    derivedFeatures.remove(MapFeature.ALLOWS_NULL_VALUES);
257    derivedFeatures.add(MapFeature.ALLOWS_NULL_VALUE_QUERIES);
258    derivedFeatures.add(MapFeature.REJECTS_DUPLICATES_AT_CREATION);
259    if (!derivedFeatures.contains(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS)) {
260      derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
261    }
262    return derivedFeatures;
263  }
264
265  private static final Multimap<Feature<?>, Feature<?>> GET_FEATURE_MAP = ImmutableMultimap
266      .<Feature<?>, Feature<?>> builder()
267      .put(
268          MapFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION,
269          CollectionFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION)
270      .put(MapFeature.GENERAL_PURPOSE, ListFeature.SUPPORTS_ADD_WITH_INDEX)
271      .put(MapFeature.GENERAL_PURPOSE, ListFeature.SUPPORTS_REMOVE_WITH_INDEX)
272      .put(MapFeature.GENERAL_PURPOSE, ListFeature.SUPPORTS_SET)
273      .put(MapFeature.ALLOWS_NULL_VALUE_QUERIES,
274          CollectionFeature.ALLOWS_NULL_QUERIES)
275      .put(MapFeature.ALLOWS_NULL_VALUES, CollectionFeature.ALLOWS_NULL_VALUES)
276      .put(MapFeature.SUPPORTS_REMOVE, CollectionFeature.SUPPORTS_REMOVE)
277      .put(MapFeature.SUPPORTS_PUT, CollectionFeature.SUPPORTS_ADD)
278      .build();
279
280  Set<Feature<?>> computeMultimapGetFeatures(
281      Set<Feature<?>> multimapFeatures) {
282    Set<Feature<?>> derivedFeatures = Helpers.copyToSet(multimapFeatures);
283    for (Map.Entry<Feature<?>, Feature<?>> entry : GET_FEATURE_MAP.entries()) {
284      if (derivedFeatures.contains(entry.getKey())) {
285        derivedFeatures.add(entry.getValue());
286      }
287    }
288    if (derivedFeatures.remove(MultimapFeature.VALUE_COLLECTIONS_SUPPORT_ITERATOR_REMOVE)) {
289      derivedFeatures.add(CollectionFeature.SUPPORTS_ITERATOR_REMOVE);
290    }
291    if (!derivedFeatures.contains(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS)) {
292      derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
293    }
294    derivedFeatures.removeAll(GET_FEATURE_MAP.keySet());
295    return derivedFeatures;
296  }
297
298  Set<Feature<?>> computeMultimapAsMapGetFeatures(
299      Set<Feature<?>> multimapFeatures) {
300    Set<Feature<?>> derivedFeatures = Helpers.copyToSet(
301        computeMultimapGetFeatures(multimapFeatures));
302    if (derivedFeatures.remove(CollectionSize.ANY)) {
303      derivedFeatures.addAll(CollectionSize.ANY.getImpliedFeatures());
304    }
305    derivedFeatures.remove(CollectionSize.ZERO);
306    return derivedFeatures;
307  }
308
309  private static class AsMapGenerator<K, V, M extends Multimap<K, V>> implements
310      TestMapGenerator<K, Collection<V>>, DerivedGenerator {
311    private final OneSizeTestContainerGenerator<M, Map.Entry<K, V>> multimapGenerator;
312
313    public AsMapGenerator(
314        OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
315      this.multimapGenerator = multimapGenerator;
316    }
317
318    @Override
319    public TestSubjectGenerator<?> getInnerGenerator() {
320      return multimapGenerator;
321    }
322
323    private Collection<V> createCollection(V v) {
324      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
325          .createCollection(Collections.singleton(v));
326    }
327
328    @Override
329    public SampleElements<Entry<K, Collection<V>>> samples() {
330      SampleElements<K> sampleKeys =
331          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleKeys();
332      SampleElements<V> sampleValues =
333          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleValues();
334      return new SampleElements<Entry<K, Collection<V>>>(
335          mapEntry(sampleKeys.e0, createCollection(sampleValues.e0)),
336          mapEntry(sampleKeys.e1, createCollection(sampleValues.e1)),
337          mapEntry(sampleKeys.e2, createCollection(sampleValues.e2)),
338          mapEntry(sampleKeys.e3, createCollection(sampleValues.e3)),
339          mapEntry(sampleKeys.e4, createCollection(sampleValues.e4)));
340    }
341
342    @Override
343    public Map<K, Collection<V>> create(Object... elements) {
344      Set<K> keySet = new HashSet<K>();
345      List<Map.Entry<K, V>> builder = new ArrayList<Entry<K, V>>();
346      for (Object o : elements) {
347        Map.Entry<K, Collection<V>> entry = (Entry<K, Collection<V>>) o;
348        keySet.add(entry.getKey());
349        for (V v : entry.getValue()) {
350          builder.add(mapEntry(entry.getKey(), v));
351        }
352      }
353      checkArgument(keySet.size() == elements.length, "Duplicate keys");
354      return multimapGenerator.create(builder.toArray()).asMap();
355    }
356
357    @SuppressWarnings("unchecked")
358    @Override
359    public Entry<K, Collection<V>>[] createArray(int length) {
360      return new Entry[length];
361    }
362
363    @Override
364    public Iterable<Entry<K, Collection<V>>> order(List<Entry<K, Collection<V>>> insertionOrder) {
365      Map<K, Collection<V>> map = new HashMap<K, Collection<V>>();
366      List<Map.Entry<K, V>> builder = new ArrayList<Entry<K, V>>();
367      for (Entry<K, Collection<V>> entry : insertionOrder) {
368        for (V v : entry.getValue()) {
369          builder.add(mapEntry(entry.getKey(), v));
370        }
371        map.put(entry.getKey(), entry.getValue());
372      }
373      Iterable<Map.Entry<K, V>> ordered = multimapGenerator.order(builder);
374      LinkedHashMap<K, Collection<V>> orderedMap = new LinkedHashMap<K, Collection<V>>();
375      for (Map.Entry<K, V> entry : ordered) {
376        orderedMap.put(entry.getKey(), map.get(entry.getKey()));
377      }
378      return orderedMap.entrySet();
379    }
380
381    @Override
382    public K[] createKeyArray(int length) {
383      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
384          .createKeyArray(length);
385    }
386
387    @SuppressWarnings("unchecked")
388    @Override
389    public Collection<V>[] createValueArray(int length) {
390      return new Collection[length];
391    }
392  }
393
394  static class EntriesGenerator<K, V, M extends Multimap<K, V>>
395      implements TestCollectionGenerator<Entry<K, V>>, DerivedGenerator {
396    private final OneSizeTestContainerGenerator<M, Map.Entry<K, V>> multimapGenerator;
397
398    public EntriesGenerator(
399        OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
400      this.multimapGenerator = multimapGenerator;
401    }
402
403    @Override
404    public TestSubjectGenerator<?> getInnerGenerator() {
405      return multimapGenerator;
406    }
407
408    @Override
409    public SampleElements<Entry<K, V>> samples() {
410      return multimapGenerator.samples();
411    }
412
413    @Override
414    public Collection<Entry<K, V>> create(Object... elements) {
415      return multimapGenerator.create(elements).entries();
416    }
417
418    @SuppressWarnings("unchecked")
419    @Override
420    public Entry<K, V>[] createArray(int length) {
421      return new Entry[length];
422    }
423
424    @Override
425    public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
426      return multimapGenerator.order(insertionOrder);
427    }
428  }
429
430  static class ValuesGenerator<K, V, M extends Multimap<K, V>>
431      implements TestCollectionGenerator<V> {
432    private final OneSizeTestContainerGenerator<M, Map.Entry<K, V>> multimapGenerator;
433
434    public ValuesGenerator(
435        OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
436      this.multimapGenerator = multimapGenerator;
437    }
438
439    @Override
440    public SampleElements<V> samples() {
441      return
442          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleValues();
443    }
444
445    @Override
446    public Collection<V> create(Object... elements) {
447      K k =
448          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleKeys().e0;
449      Entry<K, V>[] entries = new Entry[elements.length];
450      for (int i = 0; i < elements.length; i++) {
451        entries[i] = mapEntry(k, (V) elements[i]);
452      }
453      return multimapGenerator.create(entries).values();
454    }
455
456    @SuppressWarnings("unchecked")
457    @Override
458    public V[] createArray(int length) {
459      return ((TestMultimapGenerator<K, V, M>)
460          multimapGenerator.getInnerGenerator()).createValueArray(length);
461    }
462
463    @Override
464    public Iterable<V> order(List<V> insertionOrder) {
465      K k =
466          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleKeys().e0;
467      List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>();
468      for (V v : insertionOrder) {
469        entries.add(mapEntry(k, v));
470      }
471      Iterable<Entry<K, V>> ordered = multimapGenerator.order(entries);
472      List<V> orderedValues = new ArrayList<V>();
473      for (Entry<K, V> entry : ordered) {
474        orderedValues.add(entry.getValue());
475      }
476      return orderedValues;
477    }
478  }
479
480  static class KeysGenerator<K, V, M extends Multimap<K, V>> implements
481      TestMultisetGenerator<K>, DerivedGenerator {
482    private final OneSizeTestContainerGenerator<M, Map.Entry<K, V>> multimapGenerator;
483
484    public KeysGenerator(
485        OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
486      this.multimapGenerator = multimapGenerator;
487    }
488
489    @Override
490    public TestSubjectGenerator<?> getInnerGenerator() {
491      return multimapGenerator;
492    }
493
494    @Override
495    public SampleElements<K> samples() {
496      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleKeys();
497    }
498
499    @Override
500    public Multiset<K> create(Object... elements) {
501      /*
502       * This is nasty and complicated, but it's the only way to make sure keys get mapped to enough
503       * distinct values.
504       */
505      Map.Entry[] entries = new Map.Entry[elements.length];
506      Map<K, Iterator<V>> valueIterators = new HashMap<K, Iterator<V>>();
507      for (int i = 0; i < elements.length; i++) {
508        @SuppressWarnings("unchecked")
509        K key = (K) elements[i];
510
511        Iterator<V> valueItr = valueIterators.get(key);
512        if (valueItr == null) {
513          valueIterators.put(key, valueItr = sampleValuesIterator());
514        }
515        entries[i] = mapEntry((K) elements[i], valueItr.next());
516      }
517      return multimapGenerator.create(entries).keys();
518    }
519
520    private Iterator<V> sampleValuesIterator() {
521      return ((TestMultimapGenerator<K, V, M>) multimapGenerator
522          .getInnerGenerator()).sampleValues().iterator();
523    }
524
525    @SuppressWarnings("unchecked")
526    @Override
527    public K[] createArray(int length) {
528      return ((TestMultimapGenerator<K, V, M>)
529          multimapGenerator.getInnerGenerator()).createKeyArray(length);
530    }
531
532    @Override
533    public Iterable<K> order(List<K> insertionOrder) {
534      Iterator<V> valueIter = sampleValuesIterator();
535      List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>();
536      for (K k : insertionOrder) {
537        entries.add(mapEntry(k, valueIter.next()));
538      }
539      Iterable<Entry<K, V>> ordered = multimapGenerator.order(entries);
540      List<K> orderedValues = new ArrayList<K>();
541      for (Entry<K, V> entry : ordered) {
542        orderedValues.add(entry.getKey());
543      }
544      return orderedValues;
545    }
546  }
547
548  static class MultimapGetGenerator<K, V, M extends Multimap<K, V>>
549      implements TestCollectionGenerator<V> {
550    final OneSizeTestContainerGenerator<M, Map.Entry<K, V>> multimapGenerator;
551
552    public MultimapGetGenerator(
553        OneSizeTestContainerGenerator<
554        M, Map.Entry<K, V>> multimapGenerator) {
555      this.multimapGenerator = multimapGenerator;
556    }
557
558    @Override
559    public SampleElements<V> samples() {
560      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
561          .sampleValues();
562    }
563
564    @Override
565    public V[] createArray(int length) {
566      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
567          .createValueArray(length);
568    }
569
570    @Override
571    public Iterable<V> order(List<V> insertionOrder) {
572      K k = ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
573          .sampleKeys().e0;
574      List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>();
575      for (V v : insertionOrder) {
576        entries.add(mapEntry(k, v));
577      }
578      Iterable<Entry<K, V>> orderedEntries = multimapGenerator.order(entries);
579      List<V> values = new ArrayList<V>();
580      for (Entry<K, V> entry : orderedEntries) {
581        values.add(entry.getValue());
582      }
583      return values;
584    }
585
586    @Override
587    public Collection<V> create(Object... elements) {
588      Entry<K, V>[] array = multimapGenerator.createArray(elements.length);
589      K k = ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
590          .sampleKeys().e0;
591      for (int i = 0; i < elements.length; i++) {
592        array[i] = mapEntry(k, (V) elements[i]);
593      }
594      return multimapGenerator.create(array).get(k);
595    }
596  }
597
598  static class MultimapAsMapGetGenerator<K, V, M extends Multimap<K, V>>
599      extends MultimapGetGenerator<K, V, M> {
600
601    public MultimapAsMapGetGenerator(
602        OneSizeTestContainerGenerator<
603        M, Map.Entry<K, V>> multimapGenerator) {
604      super(multimapGenerator);
605    }
606
607    @Override
608    public Collection<V> create(Object... elements) {
609      Entry<K, V>[] array = multimapGenerator.createArray(elements.length);
610      K k = ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
611          .sampleKeys().e0;
612      for (int i = 0; i < elements.length; i++) {
613        array[i] = mapEntry(k, (V) elements[i]);
614      }
615      return multimapGenerator.create(array).asMap().get(k);
616    }
617  }
618
619  private static class ReserializedMultimapGenerator<K, V, M extends Multimap<K, V>>
620      implements TestMultimapGenerator<K, V, M> {
621    private final OneSizeTestContainerGenerator<M, Map.Entry<K, V>> multimapGenerator;
622
623    public ReserializedMultimapGenerator(
624        OneSizeTestContainerGenerator<
625        M, Map.Entry<K, V>> multimapGenerator) {
626      this.multimapGenerator = multimapGenerator;
627    }
628
629    @Override
630    public SampleElements<Map.Entry<K, V>> samples() {
631      return multimapGenerator.samples();
632    }
633
634    @Override
635    public Map.Entry<K, V>[] createArray(int length) {
636      return multimapGenerator.createArray(length);
637    }
638
639    @Override
640    public Iterable<Map.Entry<K, V>> order(
641        List<Map.Entry<K, V>> insertionOrder) {
642      return multimapGenerator.order(insertionOrder);
643    }
644
645    @Override
646    public M create(Object... elements) {
647      return SerializableTester.reserialize(((TestMultimapGenerator<K, V, M>) multimapGenerator
648          .getInnerGenerator()).create(elements));
649    }
650
651    @Override
652    public K[] createKeyArray(int length) {
653      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
654          .createKeyArray(length);
655    }
656
657    @Override
658    public V[] createValueArray(int length) {
659      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
660          .createValueArray(length);
661    }
662
663    @Override
664    public SampleElements<K> sampleKeys() {
665      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
666          .sampleKeys();
667    }
668
669    @Override
670    public SampleElements<V> sampleValues() {
671      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
672          .sampleValues();
673    }
674
675    @Override
676    public Collection<V> createCollection(Iterable<? extends V> values) {
677      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
678          .createCollection(values);
679    }
680  }
681}
682