001/*
002 * Copyright (C) 2012 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect.testing.google;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.collect.testing.Helpers.copyToSet;
021import static com.google.common.collect.testing.Helpers.mapEntry;
022import static java.util.Collections.singleton;
023
024import com.google.common.annotations.GwtIncompatible;
025import com.google.common.collect.ImmutableList;
026import com.google.common.collect.ImmutableMultimap;
027import com.google.common.collect.Multimap;
028import com.google.common.collect.Multiset;
029import com.google.common.collect.testing.AbstractTester;
030import com.google.common.collect.testing.CollectionTestSuiteBuilder;
031import com.google.common.collect.testing.DerivedGenerator;
032import com.google.common.collect.testing.FeatureSpecificTestSuiteBuilder;
033import com.google.common.collect.testing.MapTestSuiteBuilder;
034import com.google.common.collect.testing.OneSizeTestContainerGenerator;
035import com.google.common.collect.testing.PerCollectionSizeTestSuiteBuilder;
036import com.google.common.collect.testing.SampleElements;
037import com.google.common.collect.testing.TestCollectionGenerator;
038import com.google.common.collect.testing.TestMapGenerator;
039import com.google.common.collect.testing.TestSubjectGenerator;
040import com.google.common.collect.testing.features.CollectionFeature;
041import com.google.common.collect.testing.features.CollectionSize;
042import com.google.common.collect.testing.features.Feature;
043import com.google.common.collect.testing.features.ListFeature;
044import com.google.common.collect.testing.features.MapFeature;
045import com.google.common.testing.SerializableTester;
046import java.util.ArrayList;
047import java.util.Collection;
048import java.util.Collections;
049import java.util.EnumSet;
050import java.util.HashMap;
051import java.util.HashSet;
052import java.util.Iterator;
053import java.util.LinkedHashMap;
054import java.util.List;
055import java.util.Map;
056import java.util.Map.Entry;
057import java.util.Set;
058import junit.framework.TestSuite;
059
060/**
061 * Creates, based on your criteria, a JUnit test suite that exhaustively tests a {@code Multimap}
062 * implementation.
063 *
064 * @author Louis Wasserman
065 */
066@GwtIncompatible
067public class MultimapTestSuiteBuilder<K, V, M extends Multimap<K, V>>
068    extends PerCollectionSizeTestSuiteBuilder<
069        MultimapTestSuiteBuilder<K, V, M>, TestMultimapGenerator<K, V, M>, M, Entry<K, V>> {
070
071  public static <K, V, M extends Multimap<K, V>> MultimapTestSuiteBuilder<K, V, M> using(
072      TestMultimapGenerator<K, V, M> generator) {
073    return new MultimapTestSuiteBuilder<K, V, M>().usingGenerator(generator);
074  }
075
076  // Class parameters must be raw.
077  @SuppressWarnings("rawtypes") // class literals
078  @Override
079  protected List<Class<? extends AbstractTester>> getTesters() {
080    return ImmutableList.<Class<? extends AbstractTester>>of(
081        MultimapAsMapGetTester.class,
082        MultimapAsMapTester.class,
083        MultimapSizeTester.class,
084        MultimapClearTester.class,
085        MultimapContainsKeyTester.class,
086        MultimapContainsValueTester.class,
087        MultimapContainsEntryTester.class,
088        MultimapEntriesTester.class,
089        MultimapEqualsTester.class,
090        MultimapForEachTester.class,
091        MultimapGetTester.class,
092        MultimapKeySetTester.class,
093        MultimapKeysTester.class,
094        MultimapPutTester.class,
095        MultimapPutAllMultimapTester.class,
096        MultimapPutIterableTester.class,
097        MultimapReplaceValuesTester.class,
098        MultimapRemoveEntryTester.class,
099        MultimapRemoveAllTester.class,
100        MultimapToStringTester.class,
101        MultimapValuesTester.class);
102  }
103
104  @Override
105  protected List<TestSuite> createDerivedSuites(
106      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, 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(
116          MultimapTestSuiteBuilder.using(
117                  new ReserializedMultimapGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
118              .withFeatures(computeReserializedMultimapFeatures(parentBuilder.getFeatures()))
119              .named(parentBuilder.getName() + " reserialized")
120              .suppressing(parentBuilder.getSuppressedTests())
121              .withSetUp(parentBuilder.getSetUp())
122              .withTearDown(parentBuilder.getTearDown())
123              .createTestSuite());
124    }
125
126    derivedSuites.add(
127        MapTestSuiteBuilder.using(new AsMapGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
128            .withFeatures(computeAsMapFeatures(parentBuilder.getFeatures()))
129            .named(parentBuilder.getName() + ".asMap")
130            .suppressing(parentBuilder.getSuppressedTests())
131            .withSetUp(parentBuilder.getSetUp())
132            .withTearDown(parentBuilder.getTearDown())
133            .createTestSuite());
134
135    derivedSuites.add(computeEntriesTestSuite(parentBuilder));
136    derivedSuites.add(computeMultimapGetTestSuite(parentBuilder));
137    derivedSuites.add(computeMultimapAsMapGetTestSuite(parentBuilder));
138    derivedSuites.add(computeKeysTestSuite(parentBuilder));
139    derivedSuites.add(computeValuesTestSuite(parentBuilder));
140
141    return derivedSuites;
142  }
143
144  TestSuite computeValuesTestSuite(
145      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
146          parentBuilder) {
147    return CollectionTestSuiteBuilder.using(
148            new ValuesGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
149        .withFeatures(computeValuesFeatures(parentBuilder.getFeatures()))
150        .named(parentBuilder.getName() + ".values")
151        .suppressing(parentBuilder.getSuppressedTests())
152        .createTestSuite();
153  }
154
155  TestSuite computeEntriesTestSuite(
156      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
157          parentBuilder) {
158    return CollectionTestSuiteBuilder.using(
159            new EntriesGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
160        .withFeatures(computeEntriesFeatures(parentBuilder.getFeatures()))
161        .named(parentBuilder.getName() + ".entries")
162        .suppressing(parentBuilder.getSuppressedTests())
163        .withSetUp(parentBuilder.getSetUp())
164        .withTearDown(parentBuilder.getTearDown())
165        .createTestSuite();
166  }
167
168  TestSuite computeMultimapGetTestSuite(
169      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
170          parentBuilder) {
171    return CollectionTestSuiteBuilder.using(
172            new MultimapGetGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
173        .withFeatures(computeMultimapGetFeatures(parentBuilder.getFeatures()))
174        .named(parentBuilder.getName() + ".get[key]")
175        .suppressing(parentBuilder.getSuppressedTests())
176        .withSetUp(parentBuilder.getSetUp())
177        .withTearDown(parentBuilder.getTearDown())
178        .createTestSuite();
179  }
180
181  TestSuite computeMultimapAsMapGetTestSuite(
182      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
183          parentBuilder) {
184    Set<Feature<?>> features = computeMultimapAsMapGetFeatures(parentBuilder.getFeatures());
185    if (Collections.disjoint(features, EnumSet.allOf(CollectionSize.class))) {
186      return new TestSuite();
187    } else {
188      return CollectionTestSuiteBuilder.using(
189              new MultimapAsMapGetGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
190          .withFeatures(features)
191          .named(parentBuilder.getName() + ".asMap[].get[key]")
192          .suppressing(parentBuilder.getSuppressedTests())
193          .withSetUp(parentBuilder.getSetUp())
194          .withTearDown(parentBuilder.getTearDown())
195          .createTestSuite();
196    }
197  }
198
199  TestSuite computeKeysTestSuite(
200      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
201          parentBuilder) {
202    return MultisetTestSuiteBuilder.using(
203            new KeysGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
204        .withFeatures(computeKeysFeatures(parentBuilder.getFeatures()))
205        .named(parentBuilder.getName() + ".keys")
206        .suppressing(parentBuilder.getSuppressedTests())
207        .withSetUp(parentBuilder.getSetUp())
208        .withTearDown(parentBuilder.getTearDown())
209        .createTestSuite();
210  }
211
212  static Set<Feature<?>> computeDerivedCollectionFeatures(Set<Feature<?>> multimapFeatures) {
213    Set<Feature<?>> derivedFeatures = copyToSet(multimapFeatures);
214    if (!derivedFeatures.remove(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS)) {
215      derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
216    }
217    if (derivedFeatures.remove(MapFeature.SUPPORTS_REMOVE)) {
218      derivedFeatures.add(CollectionFeature.SUPPORTS_REMOVE);
219    }
220    return derivedFeatures;
221  }
222
223  static Set<Feature<?>> computeEntriesFeatures(Set<Feature<?>> multimapFeatures) {
224    Set<Feature<?>> result = computeDerivedCollectionFeatures(multimapFeatures);
225    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_ENTRY_QUERIES)) {
226      result.add(CollectionFeature.ALLOWS_NULL_QUERIES);
227    }
228    return result;
229  }
230
231  static Set<Feature<?>> computeValuesFeatures(Set<Feature<?>> multimapFeatures) {
232    Set<Feature<?>> result = computeDerivedCollectionFeatures(multimapFeatures);
233    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_VALUES)) {
234      result.add(CollectionFeature.ALLOWS_NULL_VALUES);
235    }
236    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_VALUE_QUERIES)) {
237      result.add(CollectionFeature.ALLOWS_NULL_QUERIES);
238    }
239    return result;
240  }
241
242  static Set<Feature<?>> computeKeysFeatures(Set<Feature<?>> multimapFeatures) {
243    Set<Feature<?>> result = computeDerivedCollectionFeatures(multimapFeatures);
244    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_KEYS)) {
245      result.add(CollectionFeature.ALLOWS_NULL_VALUES);
246    }
247    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_KEY_QUERIES)) {
248      result.add(CollectionFeature.ALLOWS_NULL_QUERIES);
249    }
250    return result;
251  }
252
253  private static Set<Feature<?>> computeReserializedMultimapFeatures(
254      Set<Feature<?>> multimapFeatures) {
255    Set<Feature<?>> derivedFeatures = copyToSet(multimapFeatures);
256    derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
257    derivedFeatures.remove(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS);
258    return derivedFeatures;
259  }
260
261  private static Set<Feature<?>> computeAsMapFeatures(Set<Feature<?>> multimapFeatures) {
262    Set<Feature<?>> derivedFeatures = copyToSet(multimapFeatures);
263    derivedFeatures.remove(MapFeature.GENERAL_PURPOSE);
264    derivedFeatures.remove(MapFeature.SUPPORTS_PUT);
265    derivedFeatures.remove(MapFeature.ALLOWS_NULL_VALUES);
266    derivedFeatures.add(MapFeature.ALLOWS_NULL_VALUE_QUERIES);
267    derivedFeatures.add(MapFeature.REJECTS_DUPLICATES_AT_CREATION);
268    if (!derivedFeatures.contains(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS)) {
269      derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
270    }
271    return derivedFeatures;
272  }
273
274  private static final ImmutableMultimap<Feature<?>, Feature<?>> GET_FEATURE_MAP =
275      ImmutableMultimap.<Feature<?>, Feature<?>>builder()
276          .put(
277              MapFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION,
278              CollectionFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION)
279          .put(MapFeature.GENERAL_PURPOSE, ListFeature.SUPPORTS_ADD_WITH_INDEX)
280          .put(MapFeature.GENERAL_PURPOSE, ListFeature.SUPPORTS_REMOVE_WITH_INDEX)
281          .put(MapFeature.GENERAL_PURPOSE, ListFeature.SUPPORTS_SET)
282          .put(MapFeature.ALLOWS_NULL_VALUE_QUERIES, CollectionFeature.ALLOWS_NULL_QUERIES)
283          .put(MapFeature.ALLOWS_NULL_VALUES, CollectionFeature.ALLOWS_NULL_VALUES)
284          .put(MapFeature.SUPPORTS_REMOVE, CollectionFeature.SUPPORTS_REMOVE)
285          .put(MapFeature.SUPPORTS_PUT, CollectionFeature.SUPPORTS_ADD)
286          .build();
287
288  Set<Feature<?>> computeMultimapGetFeatures(Set<Feature<?>> multimapFeatures) {
289    Set<Feature<?>> derivedFeatures = copyToSet(multimapFeatures);
290    for (Entry<Feature<?>, Feature<?>> entry : GET_FEATURE_MAP.entries()) {
291      if (derivedFeatures.contains(entry.getKey())) {
292        derivedFeatures.add(entry.getValue());
293      }
294    }
295    if (derivedFeatures.remove(MultimapFeature.VALUE_COLLECTIONS_SUPPORT_ITERATOR_REMOVE)) {
296      derivedFeatures.add(CollectionFeature.SUPPORTS_ITERATOR_REMOVE);
297    }
298    if (!derivedFeatures.contains(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS)) {
299      derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
300    }
301    derivedFeatures.removeAll(GET_FEATURE_MAP.keySet());
302    return derivedFeatures;
303  }
304
305  Set<Feature<?>> computeMultimapAsMapGetFeatures(Set<Feature<?>> multimapFeatures) {
306    Set<Feature<?>> derivedFeatures = copyToSet(computeMultimapGetFeatures(multimapFeatures));
307    if (derivedFeatures.remove(CollectionSize.ANY)) {
308      derivedFeatures.addAll(CollectionSize.ANY.getImpliedFeatures());
309    }
310    derivedFeatures.remove(CollectionSize.ZERO);
311    return derivedFeatures;
312  }
313
314  private static class AsMapGenerator<K, V, M extends Multimap<K, V>>
315      implements TestMapGenerator<K, Collection<V>>, DerivedGenerator {
316    private final OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator;
317
318    public AsMapGenerator(OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
319      this.multimapGenerator = multimapGenerator;
320    }
321
322    @Override
323    public TestSubjectGenerator<?> getInnerGenerator() {
324      return multimapGenerator;
325    }
326
327    private Collection<V> createCollection(V v) {
328      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
329          .createCollection(singleton(v));
330    }
331
332    @Override
333    public SampleElements<Entry<K, Collection<V>>> samples() {
334      SampleElements<K> sampleKeys =
335          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleKeys();
336      SampleElements<V> sampleValues =
337          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleValues();
338      return new SampleElements<>(
339          mapEntry(sampleKeys.e0(), createCollection(sampleValues.e0())),
340          mapEntry(sampleKeys.e1(), createCollection(sampleValues.e1())),
341          mapEntry(sampleKeys.e2(), createCollection(sampleValues.e2())),
342          mapEntry(sampleKeys.e3(), createCollection(sampleValues.e3())),
343          mapEntry(sampleKeys.e4(), createCollection(sampleValues.e4())));
344    }
345
346    @Override
347    public Map<K, Collection<V>> create(Object... elements) {
348      Set<K> keySet = new HashSet<>();
349      List<Entry<K, V>> builder = new ArrayList<>();
350      for (Object o : elements) {
351        Entry<?, ?> entry = (Entry<?, ?>) o;
352        // These come from Entry<K, Collection<V>>> objects somewhere.
353        @SuppressWarnings("unchecked")
354        K key = (K) entry.getKey();
355        keySet.add(key);
356        for (Object v : (Collection<?>) entry.getValue()) {
357          // These come from Entry<K, Collection<V>>> objects somewhere.
358          @SuppressWarnings("unchecked")
359          V value = (V) v;
360          builder.add(mapEntry(key, value));
361        }
362      }
363      checkArgument(keySet.size() == elements.length, "Duplicate keys");
364      return multimapGenerator.create(builder.toArray()).asMap();
365    }
366
367    @SuppressWarnings("unchecked")
368    @Override
369    public Entry<K, Collection<V>>[] createArray(int length) {
370      return (Entry<K, Collection<V>>[]) new Entry<?, ?>[length];
371    }
372
373    @Override
374    public Iterable<Entry<K, Collection<V>>> order(List<Entry<K, Collection<V>>> insertionOrder) {
375      Map<K, Collection<V>> map = new HashMap<>();
376      List<Entry<K, V>> builder = new ArrayList<>();
377      for (Entry<K, Collection<V>> entry : insertionOrder) {
378        for (V v : entry.getValue()) {
379          builder.add(mapEntry(entry.getKey(), v));
380        }
381        map.put(entry.getKey(), entry.getValue());
382      }
383      Iterable<Entry<K, V>> ordered = multimapGenerator.order(builder);
384      LinkedHashMap<K, Collection<V>> orderedMap = new LinkedHashMap<>();
385      for (Entry<K, V> entry : ordered) {
386        orderedMap.put(entry.getKey(), map.get(entry.getKey()));
387      }
388      return orderedMap.entrySet();
389    }
390
391    @Override
392    public K[] createKeyArray(int length) {
393      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
394          .createKeyArray(length);
395    }
396
397    @SuppressWarnings("unchecked")
398    @Override
399    public Collection<V>[] createValueArray(int length) {
400      return (Collection<V>[]) new Collection<?>[length];
401    }
402  }
403
404  static class EntriesGenerator<K, V, M extends Multimap<K, V>>
405      implements TestCollectionGenerator<Entry<K, V>>, DerivedGenerator {
406    private final OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator;
407
408    public EntriesGenerator(OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
409      this.multimapGenerator = multimapGenerator;
410    }
411
412    @Override
413    public TestSubjectGenerator<?> getInnerGenerator() {
414      return multimapGenerator;
415    }
416
417    @Override
418    public SampleElements<Entry<K, V>> samples() {
419      return multimapGenerator.samples();
420    }
421
422    @Override
423    public Collection<Entry<K, V>> create(Object... elements) {
424      return multimapGenerator.create(elements).entries();
425    }
426
427    @SuppressWarnings("unchecked")
428    @Override
429    public Entry<K, V>[] createArray(int length) {
430      return (Entry<K, V>[]) new Entry<?, ?>[length];
431    }
432
433    @Override
434    public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
435      return multimapGenerator.order(insertionOrder);
436    }
437  }
438
439  static class ValuesGenerator<K, V, M extends Multimap<K, V>>
440      implements TestCollectionGenerator<V> {
441    private final OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator;
442
443    public ValuesGenerator(OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
444      this.multimapGenerator = multimapGenerator;
445    }
446
447    @Override
448    public SampleElements<V> samples() {
449      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
450          .sampleValues();
451    }
452
453    @Override
454    public Collection<V> create(Object... elements) {
455      K k =
456          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
457              .sampleKeys()
458              .e0();
459      Object[] entries = new Object[elements.length];
460      for (int i = 0; i < elements.length; i++) {
461        @SuppressWarnings("unchecked") // These come from Entry<K, V> objects somewhere.
462        V value = (V) elements[i];
463        entries[i] = mapEntry(k, value);
464      }
465      return multimapGenerator.create(entries).values();
466    }
467
468    @Override
469    public V[] createArray(int length) {
470      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
471          .createValueArray(length);
472    }
473
474    @Override
475    public Iterable<V> order(List<V> insertionOrder) {
476      K k =
477          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
478              .sampleKeys()
479              .e0();
480      List<Entry<K, V>> entries = new ArrayList<>();
481      for (V v : insertionOrder) {
482        entries.add(mapEntry(k, v));
483      }
484      Iterable<Entry<K, V>> ordered = multimapGenerator.order(entries);
485      List<V> orderedValues = new ArrayList<>();
486      for (Entry<K, V> entry : ordered) {
487        orderedValues.add(entry.getValue());
488      }
489      return orderedValues;
490    }
491  }
492
493  static class KeysGenerator<K, V, M extends Multimap<K, V>>
494      implements TestMultisetGenerator<K>, DerivedGenerator {
495    private final OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator;
496
497    public KeysGenerator(OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
498      this.multimapGenerator = multimapGenerator;
499    }
500
501    @Override
502    public TestSubjectGenerator<?> getInnerGenerator() {
503      return multimapGenerator;
504    }
505
506    @Override
507    public SampleElements<K> samples() {
508      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleKeys();
509    }
510
511    @Override
512    public Multiset<K> create(Object... elements) {
513      /*
514       * This is nasty and complicated, but it's the only way to make sure keys get mapped to enough
515       * distinct values.
516       */
517      Entry<?, ?>[] entries = new Entry<?, ?>[elements.length];
518      Map<K, Iterator<V>> valueIterators = new HashMap<>();
519      for (int i = 0; i < elements.length; i++) {
520        @SuppressWarnings("unchecked") // These come from Entry<K, V> objects somewhere.
521        K key = (K) elements[i];
522
523        Iterator<V> valueItr = valueIterators.get(key);
524        if (valueItr == null) {
525          valueIterators.put(key, valueItr = sampleValuesIterator());
526        }
527        entries[i] = mapEntry(key, valueItr.next());
528      }
529      return multimapGenerator.create((Object[]) entries).keys();
530    }
531
532    private Iterator<V> sampleValuesIterator() {
533      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
534          .sampleValues()
535          .iterator();
536    }
537
538    @Override
539    public K[] createArray(int length) {
540      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
541          .createKeyArray(length);
542    }
543
544    @Override
545    public Iterable<K> order(List<K> insertionOrder) {
546      Iterator<V> valueIter = sampleValuesIterator();
547      List<Entry<K, V>> entries = new ArrayList<>();
548      for (K k : insertionOrder) {
549        entries.add(mapEntry(k, valueIter.next()));
550      }
551      Iterable<Entry<K, V>> ordered = multimapGenerator.order(entries);
552      List<K> orderedValues = new ArrayList<>();
553      for (Entry<K, V> entry : ordered) {
554        orderedValues.add(entry.getKey());
555      }
556      return orderedValues;
557    }
558  }
559
560  static class MultimapGetGenerator<K, V, M extends Multimap<K, V>>
561      implements TestCollectionGenerator<V> {
562    final OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator;
563
564    public MultimapGetGenerator(OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
565      this.multimapGenerator = multimapGenerator;
566    }
567
568    @Override
569    public SampleElements<V> samples() {
570      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
571          .sampleValues();
572    }
573
574    @Override
575    public V[] createArray(int length) {
576      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
577          .createValueArray(length);
578    }
579
580    @Override
581    public Iterable<V> order(List<V> insertionOrder) {
582      K k =
583          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
584              .sampleKeys()
585              .e0();
586      List<Entry<K, V>> entries = new ArrayList<>();
587      for (V v : insertionOrder) {
588        entries.add(mapEntry(k, v));
589      }
590      Iterable<Entry<K, V>> orderedEntries = multimapGenerator.order(entries);
591      List<V> values = new ArrayList<>();
592      for (Entry<K, V> entry : orderedEntries) {
593        values.add(entry.getValue());
594      }
595      return values;
596    }
597
598    @Override
599    public Collection<V> create(Object... elements) {
600      Entry<K, V>[] array = multimapGenerator.createArray(elements.length);
601      K k =
602          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
603              .sampleKeys()
604              .e0();
605      for (int i = 0; i < elements.length; i++) {
606        @SuppressWarnings("unchecked") // These come from Entry<K, V> objects somewhere.
607        V value = (V) elements[i];
608        array[i] = mapEntry(k, value);
609      }
610      return multimapGenerator.create((Object[]) array).get(k);
611    }
612  }
613
614  static class MultimapAsMapGetGenerator<K, V, M extends Multimap<K, V>>
615      extends MultimapGetGenerator<K, V, M> {
616
617    public MultimapAsMapGetGenerator(
618        OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
619      super(multimapGenerator);
620    }
621
622    @Override
623    public Collection<V> create(Object... elements) {
624      Entry<K, V>[] array = multimapGenerator.createArray(elements.length);
625      K k =
626          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
627              .sampleKeys()
628              .e0();
629      for (int i = 0; i < elements.length; i++) {
630        @SuppressWarnings("unchecked") // These come from Entry<K, V> objects somewhere.
631        V value = (V) elements[i];
632        array[i] = mapEntry(k, value);
633      }
634      return multimapGenerator.create((Object[]) array).asMap().get(k);
635    }
636  }
637
638  private static class ReserializedMultimapGenerator<K, V, M extends Multimap<K, V>>
639      implements TestMultimapGenerator<K, V, M> {
640    private final OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator;
641
642    public ReserializedMultimapGenerator(
643        OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
644      this.multimapGenerator = multimapGenerator;
645    }
646
647    @Override
648    public SampleElements<Entry<K, V>> samples() {
649      return multimapGenerator.samples();
650    }
651
652    @Override
653    public Entry<K, V>[] createArray(int length) {
654      return multimapGenerator.createArray(length);
655    }
656
657    @Override
658    public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
659      return multimapGenerator.order(insertionOrder);
660    }
661
662    @Override
663    public M create(Object... elements) {
664      return SerializableTester.reserialize(
665          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
666              .create(elements));
667    }
668
669    @Override
670    public K[] createKeyArray(int length) {
671      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
672          .createKeyArray(length);
673    }
674
675    @Override
676    public V[] createValueArray(int length) {
677      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
678          .createValueArray(length);
679    }
680
681    @Override
682    public SampleElements<K> sampleKeys() {
683      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleKeys();
684    }
685
686    @Override
687    public SampleElements<V> sampleValues() {
688      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
689          .sampleValues();
690    }
691
692    @Override
693    public Collection<V> createCollection(Iterable<? extends V> values) {
694      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
695          .createCollection(values);
696    }
697  }
698}