Coverage Summary for Class: DerivedCollectionGenerators (com.google.common.collect.testing)

1 /*
2  * Copyright (C) 2008 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 
17 package com.google.common.collect.testing;
18 
19 import static com.google.common.collect.testing.Helpers.castOrCopyToList;
20 import static com.google.common.collect.testing.Helpers.equal;
21 import static com.google.common.collect.testing.Helpers.mapEntry;
22 import static java.util.Collections.sort;
23 
24 import com.google.common.annotations.GwtCompatible;
25 import java.util.ArrayList;
26 import java.util.Arrays;
27 import java.util.Collection;
28 import java.util.Collections;
29 import java.util.Comparator;
30 import java.util.List;
31 import java.util.Map;
32 import java.util.Map.Entry;
33 import java.util.Set;
34 import java.util.SortedMap;
35 import java.util.SortedSet;
36 
37 /**
38  * Derived suite generators, split out of the suite builders so that they are available to GWT.
39  *
40  * @author George van den Driessche
41  */
42 @GwtCompatible
43 public final class DerivedCollectionGenerators {
44   public static class MapEntrySetGenerator<K, V>
45       implements TestSetGenerator<Entry<K, V>>, DerivedGenerator {
46     private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
47 
48     public MapEntrySetGenerator(
49         OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
50       this.mapGenerator = mapGenerator;
51     }
52 
53     @Override
54     public SampleElements<Entry<K, V>> samples() {
55       return mapGenerator.samples();
56     }
57 
58     @Override
59     public Set<Entry<K, V>> create(Object... elements) {
60       return mapGenerator.create(elements).entrySet();
61     }
62 
63     @Override
64     public Entry<K, V>[] createArray(int length) {
65       return mapGenerator.createArray(length);
66     }
67 
68     @Override
69     public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
70       return mapGenerator.order(insertionOrder);
71     }
72 
73     @Override
74     public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
75       return mapGenerator;
76     }
77   }
78 
79   // TODO: investigate some API changes to SampleElements that would tidy up
80   // parts of the following classes.
81 
82   static <K, V> TestSetGenerator<K> keySetGenerator(
83       OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
84     TestContainerGenerator<Map<K, V>, Entry<K, V>> generator = mapGenerator.getInnerGenerator();
85     if (generator instanceof TestSortedMapGenerator
86         && ((TestSortedMapGenerator<K, V>) generator).create().keySet() instanceof SortedSet) {
87       return new MapSortedKeySetGenerator<>(mapGenerator);
88     } else {
89       return new MapKeySetGenerator<>(mapGenerator);
90     }
91   }
92 
93   public static class MapKeySetGenerator<K, V> implements TestSetGenerator<K>, DerivedGenerator {
94     private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
95     private final SampleElements<K> samples;
96 
97     public MapKeySetGenerator(OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
98       this.mapGenerator = mapGenerator;
99       final SampleElements<Entry<K, V>> mapSamples = this.mapGenerator.samples();
100       this.samples =
101           new SampleElements<K>(
102               mapSamples.e0().getKey(),
103               mapSamples.e1().getKey(),
104               mapSamples.e2().getKey(),
105               mapSamples.e3().getKey(),
106               mapSamples.e4().getKey());
107     }
108 
109     @Override
110     public SampleElements<K> samples() {
111       return samples;
112     }
113 
114     @Override
115     public Set<K> create(Object... elements) {
116       @SuppressWarnings("unchecked")
117       K[] keysArray = (K[]) elements;
118 
119       // Start with a suitably shaped collection of entries
120       Collection<Entry<K, V>> originalEntries = mapGenerator.getSampleElements(elements.length);
121 
122       // Create a copy of that, with the desired value for each key
123       Collection<Entry<K, V>> entries = new ArrayList<>(elements.length);
124       int i = 0;
125       for (Entry<K, V> entry : originalEntries) {
126         entries.add(Helpers.mapEntry(keysArray[i++], entry.getValue()));
127       }
128 
129       return mapGenerator.create(entries.toArray()).keySet();
130     }
131 
132     @Override
133     public K[] createArray(int length) {
134       // TODO: with appropriate refactoring of OneSizeGenerator, we can perhaps
135       // tidy this up and get rid of the casts here and in
136       // MapValueCollectionGenerator.
137 
138       return ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).createKeyArray(length);
139     }
140 
141     @Override
142     public Iterable<K> order(List<K> insertionOrder) {
143       V v = ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).samples().e0().getValue();
144       List<Entry<K, V>> entries = new ArrayList<>();
145       for (K element : insertionOrder) {
146         entries.add(mapEntry(element, v));
147       }
148 
149       List<K> keys = new ArrayList<>();
150       for (Entry<K, V> entry : mapGenerator.order(entries)) {
151         keys.add(entry.getKey());
152       }
153       return keys;
154     }
155 
156     @Override
157     public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
158       return mapGenerator;
159     }
160   }
161 
162   public static class MapSortedKeySetGenerator<K, V> extends MapKeySetGenerator<K, V>
163       implements TestSortedSetGenerator<K>, DerivedGenerator {
164     private final TestSortedMapGenerator<K, V> delegate;
165 
166     public MapSortedKeySetGenerator(
167         OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
168       super(mapGenerator);
169       this.delegate = (TestSortedMapGenerator<K, V>) mapGenerator.getInnerGenerator();
170     }
171 
172     @Override
173     public SortedSet<K> create(Object... elements) {
174       return (SortedSet<K>) super.create(elements);
175     }
176 
177     @Override
178     public K belowSamplesLesser() {
179       return delegate.belowSamplesLesser().getKey();
180     }
181 
182     @Override
183     public K belowSamplesGreater() {
184       return delegate.belowSamplesGreater().getKey();
185     }
186 
187     @Override
188     public K aboveSamplesLesser() {
189       return delegate.aboveSamplesLesser().getKey();
190     }
191 
192     @Override
193     public K aboveSamplesGreater() {
194       return delegate.aboveSamplesGreater().getKey();
195     }
196   }
197 
198   public static class MapValueCollectionGenerator<K, V>
199       implements TestCollectionGenerator<V>, DerivedGenerator {
200     private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
201     private final SampleElements<V> samples;
202 
203     public MapValueCollectionGenerator(
204         OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
205       this.mapGenerator = mapGenerator;
206       final SampleElements<Entry<K, V>> mapSamples = this.mapGenerator.samples();
207       this.samples =
208           new SampleElements<V>(
209               mapSamples.e0().getValue(),
210               mapSamples.e1().getValue(),
211               mapSamples.e2().getValue(),
212               mapSamples.e3().getValue(),
213               mapSamples.e4().getValue());
214     }
215 
216     @Override
217     public SampleElements<V> samples() {
218       return samples;
219     }
220 
221     @Override
222     public Collection<V> create(Object... elements) {
223       @SuppressWarnings("unchecked")
224       V[] valuesArray = (V[]) elements;
225 
226       // Start with a suitably shaped collection of entries
227       Collection<Entry<K, V>> originalEntries = mapGenerator.getSampleElements(elements.length);
228 
229       // Create a copy of that, with the desired value for each value
230       Collection<Entry<K, V>> entries = new ArrayList<>(elements.length);
231       int i = 0;
232       for (Entry<K, V> entry : originalEntries) {
233         entries.add(Helpers.mapEntry(entry.getKey(), valuesArray[i++]));
234       }
235 
236       return mapGenerator.create(entries.toArray()).values();
237     }
238 
239     @Override
240     public V[] createArray(int length) {
241       // noinspection UnnecessaryLocalVariable
242       final V[] vs =
243           ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).createValueArray(length);
244       return vs;
245     }
246 
247     @Override
248     public Iterable<V> order(List<V> insertionOrder) {
249       final List<Entry<K, V>> orderedEntries =
250           castOrCopyToList(mapGenerator.order(castOrCopyToList(mapGenerator.getSampleElements(5))));
251       sort(
252           insertionOrder,
253           new Comparator<V>() {
254             @Override
255             public int compare(V left, V right) {
256               // The indexes are small enough for the subtraction trick to be safe.
257               return indexOfEntryWithValue(left) - indexOfEntryWithValue(right);
258             }
259 
260             int indexOfEntryWithValue(V value) {
261               for (int i = 0; i < orderedEntries.size(); i++) {
262                 if (equal(orderedEntries.get(i).getValue(), value)) {
263                   return i;
264                 }
265               }
266               throw new IllegalArgumentException(
267                   "Map.values generator can order only sample values");
268             }
269           });
270       return insertionOrder;
271     }
272 
273     @Override
274     public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
275       return mapGenerator;
276     }
277   }
278 
279   // TODO(cpovirk): could something like this be used elsewhere, e.g., ReserializedListGenerator?
280   static class ForwardingTestMapGenerator<K, V> implements TestMapGenerator<K, V> {
281     TestMapGenerator<K, V> delegate;
282 
283     ForwardingTestMapGenerator(TestMapGenerator<K, V> delegate) {
284       this.delegate = delegate;
285     }
286 
287     @Override
288     public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
289       return delegate.order(insertionOrder);
290     }
291 
292     @Override
293     public K[] createKeyArray(int length) {
294       return delegate.createKeyArray(length);
295     }
296 
297     @Override
298     public V[] createValueArray(int length) {
299       return delegate.createValueArray(length);
300     }
301 
302     @Override
303     public SampleElements<Entry<K, V>> samples() {
304       return delegate.samples();
305     }
306 
307     @Override
308     public Map<K, V> create(Object... elements) {
309       return delegate.create(elements);
310     }
311 
312     @Override
313     public Entry<K, V>[] createArray(int length) {
314       return delegate.createArray(length);
315     }
316   }
317 
318   /** Two bounds (from and to) define how to build a subMap. */
319   public enum Bound {
320     INCLUSIVE,
321     EXCLUSIVE,
322     NO_BOUND;
323   }
324 
325   public static class SortedSetSubsetTestSetGenerator<E> implements TestSortedSetGenerator<E> {
326     final Bound to;
327     final Bound from;
328     final E firstInclusive;
329     final E lastInclusive;
330     private final Comparator<? super E> comparator;
331     private final TestSortedSetGenerator<E> delegate;
332 
333     public SortedSetSubsetTestSetGenerator(
334         TestSortedSetGenerator<E> delegate, Bound to, Bound from) {
335       this.to = to;
336       this.from = from;
337       this.delegate = delegate;
338 
339       SortedSet<E> emptySet = delegate.create();
340       this.comparator = emptySet.comparator();
341 
342       SampleElements<E> samples = delegate.samples();
343       List<E> samplesList = new ArrayList<>(samples.asList());
344       Collections.sort(samplesList, comparator);
345       this.firstInclusive = samplesList.get(0);
346       this.lastInclusive = samplesList.get(samplesList.size() - 1);
347     }
348 
349     public final TestSortedSetGenerator<E> getInnerGenerator() {
350       return delegate;
351     }
352 
353     public final Bound getTo() {
354       return to;
355     }
356 
357     public final Bound getFrom() {
358       return from;
359     }
360 
361     @Override
362     public SampleElements<E> samples() {
363       return delegate.samples();
364     }
365 
366     @Override
367     public E[] createArray(int length) {
368       return delegate.createArray(length);
369     }
370 
371     @Override
372     public Iterable<E> order(List<E> insertionOrder) {
373       return delegate.order(insertionOrder);
374     }
375 
376     @Override
377     public SortedSet<E> create(Object... elements) {
378       List<?> normalValues = (List<?>) Arrays.asList(elements);
379       List<E> extremeValues = new ArrayList<>();
380 
381       // nulls are usually out of bounds for a subset, so ban them altogether
382       for (Object o : elements) {
383         if (o == null) {
384           throw new NullPointerException();
385         }
386       }
387 
388       // prepare extreme values to be filtered out of view
389       E firstExclusive = delegate.belowSamplesGreater();
390       E lastExclusive = delegate.aboveSamplesLesser();
391       if (from != Bound.NO_BOUND) {
392         extremeValues.add(delegate.belowSamplesLesser());
393         extremeValues.add(delegate.belowSamplesGreater());
394       }
395       if (to != Bound.NO_BOUND) {
396         extremeValues.add(delegate.aboveSamplesLesser());
397         extremeValues.add(delegate.aboveSamplesGreater());
398       }
399 
400       // the regular values should be visible after filtering
401       List<Object> allEntries = new ArrayList<>();
402       allEntries.addAll(extremeValues);
403       allEntries.addAll(normalValues);
404       SortedSet<E> set = delegate.create(allEntries.toArray());
405 
406       return createSubSet(set, firstExclusive, lastExclusive);
407     }
408 
409     /** Calls the smallest subSet overload that filters out the extreme values. */
410     SortedSet<E> createSubSet(SortedSet<E> set, E firstExclusive, E lastExclusive) {
411       if (from == Bound.NO_BOUND && to == Bound.EXCLUSIVE) {
412         return set.headSet(lastExclusive);
413       } else if (from == Bound.INCLUSIVE && to == Bound.NO_BOUND) {
414         return set.tailSet(firstInclusive);
415       } else if (from == Bound.INCLUSIVE && to == Bound.EXCLUSIVE) {
416         return set.subSet(firstInclusive, lastExclusive);
417       } else {
418         throw new IllegalArgumentException();
419       }
420     }
421 
422     @Override
423     public E belowSamplesLesser() {
424       throw new UnsupportedOperationException();
425     }
426 
427     @Override
428     public E belowSamplesGreater() {
429       throw new UnsupportedOperationException();
430     }
431 
432     @Override
433     public E aboveSamplesLesser() {
434       throw new UnsupportedOperationException();
435     }
436 
437     @Override
438     public E aboveSamplesGreater() {
439       throw new UnsupportedOperationException();
440     }
441   }
442 
443   /*
444    * TODO(cpovirk): surely we can find a less ugly solution than a class that accepts 3 parameters,
445    * exposes as many getters, does work in the constructor, and has both a superclass and a subclass
446    */
447   public static class SortedMapSubmapTestMapGenerator<K, V> extends ForwardingTestMapGenerator<K, V>
448       implements TestSortedMapGenerator<K, V> {
449     final Bound to;
450     final Bound from;
451     final K firstInclusive;
452     final K lastInclusive;
453     private final Comparator<Entry<K, V>> entryComparator;
454 
455     public SortedMapSubmapTestMapGenerator(
456         TestSortedMapGenerator<K, V> delegate, Bound to, Bound from) {
457       super(delegate);
458       this.to = to;
459       this.from = from;
460 
461       SortedMap<K, V> emptyMap = delegate.create();
462       this.entryComparator = Helpers.entryComparator(emptyMap.comparator());
463 
464       // derive values for inclusive filtering from the input samples
465       SampleElements<Entry<K, V>> samples = delegate.samples();
466       @SuppressWarnings("unchecked") // no elements are inserted into the array
467       List<Entry<K, V>> samplesList =
468           Arrays.asList(samples.e0(), samples.e1(), samples.e2(), samples.e3(), samples.e4());
469       Collections.sort(samplesList, entryComparator);
470       this.firstInclusive = samplesList.get(0).getKey();
471       this.lastInclusive = samplesList.get(samplesList.size() - 1).getKey();
472     }
473 
474     @Override
475     public SortedMap<K, V> create(Object... entries) {
476       List<Entry<K, V>> extremeValues = new ArrayList<>();
477 
478       // prepare extreme values to be filtered out of view
479       K firstExclusive = getInnerGenerator().belowSamplesGreater().getKey();
480       K lastExclusive = getInnerGenerator().aboveSamplesLesser().getKey();
481       if (from != Bound.NO_BOUND) {
482         extremeValues.add(getInnerGenerator().belowSamplesLesser());
483         extremeValues.add(getInnerGenerator().belowSamplesGreater());
484       }
485       if (to != Bound.NO_BOUND) {
486         extremeValues.add(getInnerGenerator().aboveSamplesLesser());
487         extremeValues.add(getInnerGenerator().aboveSamplesGreater());
488       }
489 
490       // the regular values should be visible after filtering
491       List<Entry<?, ?>> allEntries = new ArrayList<>();
492       allEntries.addAll(extremeValues);
493       for (Object entry : entries) {
494         allEntries.add((Entry<?, ?>) entry);
495       }
496       SortedMap<K, V> map = (SortedMap<K, V>) delegate.create(allEntries.toArray());
497 
498       return createSubMap(map, firstExclusive, lastExclusive);
499     }
500 
501     /**
502      * Calls the smallest subMap overload that filters out the extreme values. This method is
503      * overridden in NavigableMapTestSuiteBuilder.
504      */
505     SortedMap<K, V> createSubMap(SortedMap<K, V> map, K firstExclusive, K lastExclusive) {
506       if (from == Bound.NO_BOUND && to == Bound.EXCLUSIVE) {
507         return map.headMap(lastExclusive);
508       } else if (from == Bound.INCLUSIVE && to == Bound.NO_BOUND) {
509         return map.tailMap(firstInclusive);
510       } else if (from == Bound.INCLUSIVE && to == Bound.EXCLUSIVE) {
511         return map.subMap(firstInclusive, lastExclusive);
512       } else {
513         throw new IllegalArgumentException();
514       }
515     }
516 
517     public final Bound getTo() {
518       return to;
519     }
520 
521     public final Bound getFrom() {
522       return from;
523     }
524 
525     public final TestSortedMapGenerator<K, V> getInnerGenerator() {
526       return (TestSortedMapGenerator<K, V>) delegate;
527     }
528 
529     @Override
530     public Entry<K, V> belowSamplesLesser() {
531       // should never reach here!
532       throw new UnsupportedOperationException();
533     }
534 
535     @Override
536     public Entry<K, V> belowSamplesGreater() {
537       // should never reach here!
538       throw new UnsupportedOperationException();
539     }
540 
541     @Override
542     public Entry<K, V> aboveSamplesLesser() {
543       // should never reach here!
544       throw new UnsupportedOperationException();
545     }
546 
547     @Override
548     public Entry<K, V> aboveSamplesGreater() {
549       // should never reach here!
550       throw new UnsupportedOperationException();
551     }
552   }
553 
554   private DerivedCollectionGenerators() {}
555 }