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