Source code

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 com.google.common.testing.SerializableTester.reserialize;
023import static java.util.Collections.singleton;
024
025import com.google.common.annotations.GwtIncompatible;
026import com.google.common.collect.ImmutableList;
027import com.google.common.collect.ImmutableMultimap;
028import com.google.common.collect.Multimap;
029import com.google.common.collect.Multiset;
030import com.google.common.collect.testing.AbstractTester;
031import com.google.common.collect.testing.CollectionTestSuiteBuilder;
032import com.google.common.collect.testing.DerivedGenerator;
033import com.google.common.collect.testing.FeatureSpecificTestSuiteBuilder;
034import com.google.common.collect.testing.MapTestSuiteBuilder;
035import com.google.common.collect.testing.OneSizeTestContainerGenerator;
036import com.google.common.collect.testing.PerCollectionSizeTestSuiteBuilder;
037import com.google.common.collect.testing.SampleElements;
038import com.google.common.collect.testing.TestCollectionGenerator;
039import com.google.common.collect.testing.TestMapGenerator;
040import com.google.common.collect.testing.TestSubjectGenerator;
041import com.google.common.collect.testing.features.CollectionFeature;
042import com.google.common.collect.testing.features.CollectionSize;
043import com.google.common.collect.testing.features.Feature;
044import com.google.common.collect.testing.features.ListFeature;
045import com.google.common.collect.testing.features.MapFeature;
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.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          using(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 = 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 = 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 = 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 = 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 = copyToSet(computeMultimapGetFeatures(multimapFeatures));
306    if (derivedFeatures.remove(CollectionSize.ANY)) {
307      derivedFeatures.addAll(CollectionSize.ANY.getImpliedFeatures());
308    }
309    derivedFeatures.remove(CollectionSize.ZERO);
310    return derivedFeatures;
311  }
312
313  private static final class AsMapGenerator<K, V, M extends Multimap<K, V>>
314      implements TestMapGenerator<K, Collection<V>>, DerivedGenerator {
315    private final OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator;
316
317    AsMapGenerator(OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
318      this.multimapGenerator = multimapGenerator;
319    }
320
321    @Override
322    public TestSubjectGenerator<?> getInnerGenerator() {
323      return multimapGenerator;
324    }
325
326    private Collection<V> createCollection(V v) {
327      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
328          .createCollection(singleton(v));
329    }
330
331    @Override
332    public SampleElements<Entry<K, Collection<V>>> samples() {
333      SampleElements<K> sampleKeys =
334          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleKeys();
335      SampleElements<V> sampleValues =
336          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleValues();
337      return new SampleElements<>(
338          mapEntry(sampleKeys.e0(), createCollection(sampleValues.e0())),
339          mapEntry(sampleKeys.e1(), createCollection(sampleValues.e1())),
340          mapEntry(sampleKeys.e2(), createCollection(sampleValues.e2())),
341          mapEntry(sampleKeys.e3(), createCollection(sampleValues.e3())),
342          mapEntry(sampleKeys.e4(), createCollection(sampleValues.e4())));
343    }
344
345    @Override
346    public Map<K, Collection<V>> create(Object... elements) {
347      Set<K> keySet = new HashSet<>();
348      List<Entry<K, V>> builder = new ArrayList<>();
349      for (Object o : elements) {
350        Entry<?, ?> entry = (Entry<?, ?>) o;
351        // These come from Entry<K, Collection<V>>> objects somewhere.
352        @SuppressWarnings("unchecked")
353        K key = (K) entry.getKey();
354        keySet.add(key);
355        for (Object v : (Collection<?>) entry.getValue()) {
356          // These come from Entry<K, Collection<V>>> objects somewhere.
357          @SuppressWarnings("unchecked")
358          V value = (V) v;
359          builder.add(mapEntry(key, value));
360        }
361      }
362      checkArgument(keySet.size() == elements.length, "Duplicate keys");
363      return multimapGenerator.create(builder.toArray()).asMap();
364    }
365
366    @SuppressWarnings("unchecked")
367    @Override
368    public Entry<K, Collection<V>>[] createArray(int length) {
369      return (Entry<K, Collection<V>>[]) new Entry<?, ?>[length];
370    }
371
372    @Override
373    public Iterable<Entry<K, Collection<V>>> order(List<Entry<K, Collection<V>>> insertionOrder) {
374      Map<K, Collection<V>> map = new HashMap<>();
375      List<Entry<K, V>> builder = new ArrayList<>();
376      for (Entry<K, Collection<V>> entry : insertionOrder) {
377        for (V v : entry.getValue()) {
378          builder.add(mapEntry(entry.getKey(), v));
379        }
380        map.put(entry.getKey(), entry.getValue());
381      }
382      Iterable<Entry<K, V>> ordered = multimapGenerator.order(builder);
383      LinkedHashMap<K, Collection<V>> orderedMap = new LinkedHashMap<>();
384      for (Entry<K, V> entry : ordered) {
385        orderedMap.put(entry.getKey(), map.get(entry.getKey()));
386      }
387      return orderedMap.entrySet();
388    }
389
390    @Override
391    public K[] createKeyArray(int length) {
392      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
393          .createKeyArray(length);
394    }
395
396    @SuppressWarnings("unchecked")
397    @Override
398    public Collection<V>[] createValueArray(int length) {
399      return (Collection<V>[]) new Collection<?>[length];
400    }
401  }
402
403  static class EntriesGenerator<K, V, M extends Multimap<K, V>>
404      implements TestCollectionGenerator<Entry<K, V>>, DerivedGenerator {
405    private final OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator;
406
407    public EntriesGenerator(OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
408      this.multimapGenerator = multimapGenerator;
409    }
410
411    @Override
412    public TestSubjectGenerator<?> getInnerGenerator() {
413      return multimapGenerator;
414    }
415
416    @Override
417    public SampleElements<Entry<K, V>> samples() {
418      return multimapGenerator.samples();
419    }
420
421    @Override
422    public Collection<Entry<K, V>> create(Object... elements) {
423      return multimapGenerator.create(elements).entries();
424    }
425
426    @SuppressWarnings("unchecked")
427    @Override
428    public Entry<K, V>[] createArray(int length) {
429      return (Entry<K, V>[]) new Entry<?, ?>[length];
430    }
431
432    @Override
433    public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
434      return multimapGenerator.order(insertionOrder);
435    }
436  }
437
438  private static final class ValuesGenerator<K, V, M extends Multimap<K, V>>
439      implements TestCollectionGenerator<V> {
440    private final OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator;
441
442    ValuesGenerator(OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
443      this.multimapGenerator = multimapGenerator;
444    }
445
446    @Override
447    public SampleElements<V> samples() {
448      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
449          .sampleValues();
450    }
451
452    @Override
453    public Collection<V> create(Object... elements) {
454      K k =
455          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
456              .sampleKeys()
457              .e0();
458      Object[] entries = new Object[elements.length];
459      for (int i = 0; i < elements.length; i++) {
460        @SuppressWarnings("unchecked") // These come from Entry<K, V> objects somewhere.
461        V value = (V) elements[i];
462        entries[i] = mapEntry(k, value);
463      }
464      return multimapGenerator.create(entries).values();
465    }
466
467    @Override
468    public V[] createArray(int length) {
469      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
470          .createValueArray(length);
471    }
472
473    @Override
474    public Iterable<V> order(List<V> insertionOrder) {
475      K k =
476          ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
477              .sampleKeys()
478              .e0();
479      List<Entry<K, V>> entries = new ArrayList<>();
480      for (V v : insertionOrder) {
481        entries.add(mapEntry(k, v));
482      }
483      Iterable<Entry<K, V>> ordered = multimapGenerator.order(entries);
484      List<V> orderedValues = new ArrayList<>();
485      for (Entry<K, V> entry : ordered) {
486        orderedValues.add(entry.getValue());
487      }
488      return orderedValues;
489    }
490  }
491
492  private static final class KeysGenerator<K, V, M extends Multimap<K, V>>
493      implements TestMultisetGenerator<K>, DerivedGenerator {
494    private final OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator;
495
496    KeysGenerator(OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
497      this.multimapGenerator = multimapGenerator;
498    }
499
500    @Override
501    public TestSubjectGenerator<?> getInnerGenerator() {
502      return multimapGenerator;
503    }
504
505    @Override
506    public SampleElements<K> samples() {
507      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleKeys();
508    }
509
510    @Override
511    public Multiset<K> create(Object... elements) {
512      /*
513       * This is nasty and complicated, but it's the only way to make sure keys get mapped to enough
514       * distinct values.
515       */
516      Entry<?, ?>[] entries = new Entry<?, ?>[elements.length];
517      Map<K, Iterator<V>> valueIterators = new HashMap<>();
518      for (int i = 0; i < elements.length; i++) {
519        @SuppressWarnings("unchecked") // These come from Entry<K, V> objects somewhere.
520        K key = (K) elements[i];
521
522        Iterator<V> valueItr = valueIterators.get(key);
523        if (valueItr == null) {
524          valueItr = sampleValuesIterator();
525          valueIterators.put(key, valueItr);
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 final 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    ReserializedMultimapGenerator(OneSizeTestContainerGenerator<M, Entry<K, V>> multimapGenerator) {
643      this.multimapGenerator = multimapGenerator;
644    }
645
646    @Override
647    public SampleElements<Entry<K, V>> samples() {
648      return multimapGenerator.samples();
649    }
650
651    @Override
652    public Entry<K, V>[] createArray(int length) {
653      return multimapGenerator.createArray(length);
654    }
655
656    @Override
657    public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
658      return multimapGenerator.order(insertionOrder);
659    }
660
661    @Override
662    public M create(Object... elements) {
663      return reserialize(multimapGenerator.getInnerGenerator().create(elements));
664    }
665
666    @Override
667    public K[] createKeyArray(int length) {
668      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
669          .createKeyArray(length);
670    }
671
672    @Override
673    public V[] createValueArray(int length) {
674      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
675          .createValueArray(length);
676    }
677
678    @Override
679    public SampleElements<K> sampleKeys() {
680      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator()).sampleKeys();
681    }
682
683    @Override
684    public SampleElements<V> sampleValues() {
685      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
686          .sampleValues();
687    }
688
689    @Override
690    public Collection<V> createCollection(Iterable<? extends V> values) {
691      return ((TestMultimapGenerator<K, V, M>) multimapGenerator.getInnerGenerator())
692          .createCollection(values);
693    }
694  }
695}