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.mapEntry;
021
022import com.google.common.annotations.GwtIncompatible;
023import com.google.common.collect.ImmutableList;
024import com.google.common.collect.ImmutableMultimap;
025import com.google.common.collect.Multimap;
026import com.google.common.collect.Multiset;
027import com.google.common.collect.testing.AbstractTester;
028import com.google.common.collect.testing.CollectionTestSuiteBuilder;
029import com.google.common.collect.testing.DerivedGenerator;
030import com.google.common.collect.testing.FeatureSpecificTestSuiteBuilder;
031import com.google.common.collect.testing.Helpers;
032import com.google.common.collect.testing.MapTestSuiteBuilder;
033import com.google.common.collect.testing.OneSizeTestContainerGenerator;
034import com.google.common.collect.testing.PerCollectionSizeTestSuiteBuilder;
035import com.google.common.collect.testing.SampleElements;
036import com.google.common.collect.testing.TestCollectionGenerator;
037import com.google.common.collect.testing.TestMapGenerator;
038import com.google.common.collect.testing.TestSubjectGenerator;
039import com.google.common.collect.testing.features.CollectionFeature;
040import com.google.common.collect.testing.features.CollectionSize;
041import com.google.common.collect.testing.features.Feature;
042import com.google.common.collect.testing.features.ListFeature;
043import com.google.common.collect.testing.features.MapFeature;
044import com.google.common.testing.SerializableTester;
045import java.util.ArrayList;
046import java.util.Collection;
047import java.util.Collections;
048import java.util.EnumSet;
049import java.util.HashMap;
050import java.util.HashSet;
051import java.util.Iterator;
052import java.util.LinkedHashMap;
053import java.util.List;
054import java.util.Map;
055import java.util.Map.Entry;
056import java.util.Set;
057import junit.framework.TestSuite;
058
059/**
060 * Creates, based on your criteria, a JUnit test suite that exhaustively tests a {@code Multimap}
061 * implementation.
062 *
063 * @author Louis Wasserman
064 */
065@GwtIncompatible
066public class MultimapTestSuiteBuilder<K, V, M extends Multimap<K, V>>
067    extends PerCollectionSizeTestSuiteBuilder<
068        MultimapTestSuiteBuilder<K, V, M>, TestMultimapGenerator<K, V, M>, M, Entry<K, V>> {
069
070  public static <K, V, M extends Multimap<K, V>> MultimapTestSuiteBuilder<K, V, M> using(
071      TestMultimapGenerator<K, V, M> generator) {
072    return new MultimapTestSuiteBuilder<K, V, M>().usingGenerator(generator);
073  }
074
075  // Class parameters must be raw.
076  @SuppressWarnings("rawtypes") // class literals
077  @Override
078  protected List<Class<? extends AbstractTester>> getTesters() {
079    return ImmutableList.<Class<? extends AbstractTester>>of(
080        MultimapAsMapGetTester.class,
081        MultimapAsMapTester.class,
082        MultimapSizeTester.class,
083        MultimapClearTester.class,
084        MultimapContainsKeyTester.class,
085        MultimapContainsValueTester.class,
086        MultimapContainsEntryTester.class,
087        MultimapEntriesTester.class,
088        MultimapEqualsTester.class,
089        MultimapForEachTester.class,
090        MultimapGetTester.class,
091        MultimapKeySetTester.class,
092        MultimapKeysTester.class,
093        MultimapPutTester.class,
094        MultimapPutAllMultimapTester.class,
095        MultimapPutIterableTester.class,
096        MultimapReplaceValuesTester.class,
097        MultimapRemoveEntryTester.class,
098        MultimapRemoveAllTester.class,
099        MultimapToStringTester.class,
100        MultimapValuesTester.class);
101  }
102
103  @Override
104  protected List<TestSuite> createDerivedSuites(
105      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
106          parentBuilder) {
107    // TODO: Once invariant support is added, supply invariants to each of the
108    // derived suites, to check that mutations to the derived collections are
109    // reflected in the underlying map.
110
111    List<TestSuite> derivedSuites = super.createDerivedSuites(parentBuilder);
112
113    if (parentBuilder.getFeatures().contains(CollectionFeature.SERIALIZABLE)) {
114      derivedSuites.add(
115          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              .withSetUp(parentBuilder.getSetUp())
121              .withTearDown(parentBuilder.getTearDown())
122              .createTestSuite());
123    }
124
125    derivedSuites.add(
126        MapTestSuiteBuilder.using(new AsMapGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
127            .withFeatures(computeAsMapFeatures(parentBuilder.getFeatures()))
128            .named(parentBuilder.getName() + ".asMap")
129            .suppressing(parentBuilder.getSuppressedTests())
130            .withSetUp(parentBuilder.getSetUp())
131            .withTearDown(parentBuilder.getTearDown())
132            .createTestSuite());
133
134    derivedSuites.add(computeEntriesTestSuite(parentBuilder));
135    derivedSuites.add(computeMultimapGetTestSuite(parentBuilder));
136    derivedSuites.add(computeMultimapAsMapGetTestSuite(parentBuilder));
137    derivedSuites.add(computeKeysTestSuite(parentBuilder));
138    derivedSuites.add(computeValuesTestSuite(parentBuilder));
139
140    return derivedSuites;
141  }
142
143  TestSuite computeValuesTestSuite(
144      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
145          parentBuilder) {
146    return CollectionTestSuiteBuilder.using(
147            new ValuesGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
148        .withFeatures(computeValuesFeatures(parentBuilder.getFeatures()))
149        .named(parentBuilder.getName() + ".values")
150        .suppressing(parentBuilder.getSuppressedTests())
151        .createTestSuite();
152  }
153
154  TestSuite computeEntriesTestSuite(
155      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
156          parentBuilder) {
157    return CollectionTestSuiteBuilder.using(
158            new EntriesGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
159        .withFeatures(computeEntriesFeatures(parentBuilder.getFeatures()))
160        .named(parentBuilder.getName() + ".entries")
161        .suppressing(parentBuilder.getSuppressedTests())
162        .withSetUp(parentBuilder.getSetUp())
163        .withTearDown(parentBuilder.getTearDown())
164        .createTestSuite();
165  }
166
167  TestSuite computeMultimapGetTestSuite(
168      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
169          parentBuilder) {
170    return CollectionTestSuiteBuilder.using(
171            new MultimapGetGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
172        .withFeatures(computeMultimapGetFeatures(parentBuilder.getFeatures()))
173        .named(parentBuilder.getName() + ".get[key]")
174        .suppressing(parentBuilder.getSuppressedTests())
175        .withSetUp(parentBuilder.getSetUp())
176        .withTearDown(parentBuilder.getTearDown())
177        .createTestSuite();
178  }
179
180  TestSuite computeMultimapAsMapGetTestSuite(
181      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
182          parentBuilder) {
183    Set<Feature<?>> features = computeMultimapAsMapGetFeatures(parentBuilder.getFeatures());
184    if (Collections.disjoint(features, EnumSet.allOf(CollectionSize.class))) {
185      return new TestSuite();
186    } else {
187      return CollectionTestSuiteBuilder.using(
188              new MultimapAsMapGetGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
189          .withFeatures(features)
190          .named(parentBuilder.getName() + ".asMap[].get[key]")
191          .suppressing(parentBuilder.getSuppressedTests())
192          .withSetUp(parentBuilder.getSetUp())
193          .withTearDown(parentBuilder.getTearDown())
194          .createTestSuite();
195    }
196  }
197
198  TestSuite computeKeysTestSuite(
199      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<M, Entry<K, V>>>
200          parentBuilder) {
201    return MultisetTestSuiteBuilder.using(
202            new KeysGenerator<K, V, M>(parentBuilder.getSubjectGenerator()))
203        .withFeatures(computeKeysFeatures(parentBuilder.getFeatures()))
204        .named(parentBuilder.getName() + ".keys")
205        .suppressing(parentBuilder.getSuppressedTests())
206        .withSetUp(parentBuilder.getSetUp())
207        .withTearDown(parentBuilder.getTearDown())
208        .createTestSuite();
209  }
210
211  static Set<Feature<?>> computeDerivedCollectionFeatures(Set<Feature<?>> multimapFeatures) {
212    Set<Feature<?>> derivedFeatures = Helpers.copyToSet(multimapFeatures);
213    if (!derivedFeatures.remove(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS)) {
214      derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
215    }
216    if (derivedFeatures.remove(MapFeature.SUPPORTS_REMOVE)) {
217      derivedFeatures.add(CollectionFeature.SUPPORTS_REMOVE);
218    }
219    return derivedFeatures;
220  }
221
222  static Set<Feature<?>> computeEntriesFeatures(Set<Feature<?>> multimapFeatures) {
223    Set<Feature<?>> result = computeDerivedCollectionFeatures(multimapFeatures);
224    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_ENTRY_QUERIES)) {
225      result.add(CollectionFeature.ALLOWS_NULL_QUERIES);
226    }
227    return result;
228  }
229
230  static Set<Feature<?>> computeValuesFeatures(Set<Feature<?>> multimapFeatures) {
231    Set<Feature<?>> result = computeDerivedCollectionFeatures(multimapFeatures);
232    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_VALUES)) {
233      result.add(CollectionFeature.ALLOWS_NULL_VALUES);
234    }
235    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_VALUE_QUERIES)) {
236      result.add(CollectionFeature.ALLOWS_NULL_QUERIES);
237    }
238    return result;
239  }
240
241  static Set<Feature<?>> computeKeysFeatures(Set<Feature<?>> multimapFeatures) {
242    Set<Feature<?>> result = computeDerivedCollectionFeatures(multimapFeatures);
243    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_KEYS)) {
244      result.add(CollectionFeature.ALLOWS_NULL_VALUES);
245    }
246    if (multimapFeatures.contains(MapFeature.ALLOWS_NULL_KEY_QUERIES)) {
247      result.add(CollectionFeature.ALLOWS_NULL_QUERIES);
248    }
249    return result;
250  }
251
252  private static Set<Feature<?>> computeReserializedMultimapFeatures(
253      Set<Feature<?>> multimapFeatures) {
254    Set<Feature<?>> derivedFeatures = Helpers.copyToSet(multimapFeatures);
255    derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
256    derivedFeatures.remove(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS);
257    return derivedFeatures;
258  }
259
260  private static Set<Feature<?>> computeAsMapFeatures(Set<Feature<?>> multimapFeatures) {
261    Set<Feature<?>> derivedFeatures = Helpers.copyToSet(multimapFeatures);
262    derivedFeatures.remove(MapFeature.GENERAL_PURPOSE);
263    derivedFeatures.remove(MapFeature.SUPPORTS_PUT);
264    derivedFeatures.remove(MapFeature.ALLOWS_NULL_VALUES);
265    derivedFeatures.add(MapFeature.ALLOWS_NULL_VALUE_QUERIES);
266    derivedFeatures.add(MapFeature.REJECTS_DUPLICATES_AT_CREATION);
267    if (!derivedFeatures.contains(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS)) {
268      derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
269    }
270    return derivedFeatures;
271  }
272
273  private static final ImmutableMultimap<Feature<?>, Feature<?>> GET_FEATURE_MAP =
274      ImmutableMultimap.<Feature<?>, Feature<?>>builder()
275          .put(
276              MapFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION,
277              CollectionFeature.FAILS_FAST_ON_CONCURRENT_MODIFICATION)
278          .put(MapFeature.GENERAL_PURPOSE, ListFeature.SUPPORTS_ADD_WITH_INDEX)
279          .put(MapFeature.GENERAL_PURPOSE, ListFeature.SUPPORTS_REMOVE_WITH_INDEX)
280          .put(MapFeature.GENERAL_PURPOSE, ListFeature.SUPPORTS_SET)
281          .put(MapFeature.ALLOWS_NULL_VALUE_QUERIES, CollectionFeature.ALLOWS_NULL_QUERIES)
282          .put(MapFeature.ALLOWS_NULL_VALUES, CollectionFeature.ALLOWS_NULL_VALUES)
283          .put(MapFeature.SUPPORTS_REMOVE, CollectionFeature.SUPPORTS_REMOVE)
284          .put(MapFeature.SUPPORTS_PUT, CollectionFeature.SUPPORTS_ADD)
285          .build();
286
287  Set<Feature<?>> computeMultimapGetFeatures(Set<Feature<?>> multimapFeatures) {
288    Set<Feature<?>> derivedFeatures = Helpers.copyToSet(multimapFeatures);
289    for (Entry<Feature<?>, Feature<?>> entry : GET_FEATURE_MAP.entries()) {
290      if (derivedFeatures.contains(entry.getKey())) {
291        derivedFeatures.add(entry.getValue());
292      }
293    }
294    if (derivedFeatures.remove(MultimapFeature.VALUE_COLLECTIONS_SUPPORT_ITERATOR_REMOVE)) {
295      derivedFeatures.add(CollectionFeature.SUPPORTS_ITERATOR_REMOVE);
296    }
297    if (!derivedFeatures.contains(CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS)) {
298      derivedFeatures.remove(CollectionFeature.SERIALIZABLE);
299    }
300    derivedFeatures.removeAll(GET_FEATURE_MAP.keySet());
301    return derivedFeatures;
302  }
303
304  Set<Feature<?>> computeMultimapAsMapGetFeatures(Set<Feature<?>> multimapFeatures) {
305    Set<Feature<?>> derivedFeatures =
306        Helpers.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(Collections.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}