View Javadoc
1   /*
2    * Copyright (C) 2011 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License"); you may not
5    * use this file except in compliance with the License. You may obtain a copy of
6    * 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, WITHOUT
12   * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
13   * License for the specific language governing permissions and limitations under
14   * the License.
15   */
16  
17  package com.google.common.collect.testing.google;
18  
19  import static com.google.common.collect.testing.features.CollectionFeature.KNOWN_ORDER;
20  import static com.google.common.collect.testing.features.CollectionFeature.RESTRICTS_ELEMENTS;
21  import static com.google.common.collect.testing.features.CollectionFeature.SERIALIZABLE;
22  import static com.google.common.collect.testing.features.CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS;
23  
24  import com.google.common.annotations.GwtIncompatible;
25  import com.google.common.collect.BoundType;
26  import com.google.common.collect.ImmutableList;
27  import com.google.common.collect.Lists;
28  import com.google.common.collect.Multiset;
29  import com.google.common.collect.SortedMultiset;
30  import com.google.common.collect.testing.AbstractTester;
31  import com.google.common.collect.testing.FeatureSpecificTestSuiteBuilder;
32  import com.google.common.collect.testing.Helpers;
33  import com.google.common.collect.testing.OneSizeTestContainerGenerator;
34  import com.google.common.collect.testing.SampleElements;
35  import com.google.common.collect.testing.SetTestSuiteBuilder;
36  import com.google.common.collect.testing.features.Feature;
37  import com.google.common.testing.SerializableTester;
38  import java.util.ArrayList;
39  import java.util.Arrays;
40  import java.util.Collection;
41  import java.util.Collections;
42  import java.util.Comparator;
43  import java.util.HashSet;
44  import java.util.List;
45  import java.util.Set;
46  import junit.framework.TestSuite;
47  
48  /**
49   * Creates, based on your criteria, a JUnit test suite that exhaustively tests a
50   * {@code SortedMultiset} implementation.
51   *
52   * <p><b>Warning:</b> expects that {@code E} is a String.
53   *
54   * @author Louis Wasserman
55   */
56  @GwtIncompatible
57  public class SortedMultisetTestSuiteBuilder<E> extends MultisetTestSuiteBuilder<E> {
58    public static <E> SortedMultisetTestSuiteBuilder<E> using(TestMultisetGenerator<E> generator) {
59      SortedMultisetTestSuiteBuilder<E> result = new SortedMultisetTestSuiteBuilder<E>();
60      result.usingGenerator(generator);
61      return result;
62    }
63  
64    @Override
65    public TestSuite createTestSuite() {
66      withFeatures(KNOWN_ORDER);
67      TestSuite suite = super.createTestSuite();
68      for (TestSuite subSuite : createDerivedSuites(this)) {
69        suite.addTest(subSuite);
70      }
71      return suite;
72    }
73  
74    @Override
75    protected List<Class<? extends AbstractTester>> getTesters() {
76      List<Class<? extends AbstractTester>> testers = Helpers.copyToList(super.getTesters());
77      testers.add(MultisetNavigationTester.class);
78      return testers;
79    }
80  
81    @Override
82    TestSuite createElementSetTestSuite(
83        FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<Collection<E>, E>>
84            parentBuilder) {
85      // TODO(lowasser): make a SortedElementSetGenerator
86      return SetTestSuiteBuilder.using(
87              new ElementSetGenerator<E>(parentBuilder.getSubjectGenerator()))
88          .named(getName() + ".elementSet")
89          .withFeatures(computeElementSetFeatures(parentBuilder.getFeatures()))
90          .suppressing(parentBuilder.getSuppressedTests())
91          .createTestSuite();
92    }
93  
94    /**
95     * To avoid infinite recursion, test suites with these marker features won't
96     * have derived suites created for them.
97     */
98    enum NoRecurse implements Feature<Void> {
99      SUBMULTISET,
100     DESCENDING;
101 
102     @Override
103     public Set<Feature<? super Void>> getImpliedFeatures() {
104       return Collections.emptySet();
105     }
106   }
107 
108   /**
109    * Two bounds (from and to) define how to build a subMultiset.
110    */
111   enum Bound {
112     INCLUSIVE,
113     EXCLUSIVE,
114     NO_BOUND;
115   }
116 
117   List<TestSuite> createDerivedSuites(SortedMultisetTestSuiteBuilder<E> parentBuilder) {
118     List<TestSuite> derivedSuites = Lists.newArrayList();
119 
120     if (!parentBuilder.getFeatures().contains(NoRecurse.DESCENDING)) {
121       derivedSuites.add(createDescendingSuite(parentBuilder));
122     }
123 
124     if (parentBuilder.getFeatures().contains(SERIALIZABLE)) {
125       derivedSuites.add(createReserializedSuite(parentBuilder));
126     }
127 
128     if (!parentBuilder.getFeatures().contains(NoRecurse.SUBMULTISET)) {
129       derivedSuites.add(createSubMultisetSuite(parentBuilder, Bound.NO_BOUND, Bound.EXCLUSIVE));
130       derivedSuites.add(createSubMultisetSuite(parentBuilder, Bound.NO_BOUND, Bound.INCLUSIVE));
131       derivedSuites.add(createSubMultisetSuite(parentBuilder, Bound.EXCLUSIVE, Bound.NO_BOUND));
132       derivedSuites.add(createSubMultisetSuite(parentBuilder, Bound.EXCLUSIVE, Bound.EXCLUSIVE));
133       derivedSuites.add(createSubMultisetSuite(parentBuilder, Bound.EXCLUSIVE, Bound.INCLUSIVE));
134       derivedSuites.add(createSubMultisetSuite(parentBuilder, Bound.INCLUSIVE, Bound.NO_BOUND));
135       derivedSuites.add(createSubMultisetSuite(parentBuilder, Bound.INCLUSIVE, Bound.EXCLUSIVE));
136       derivedSuites.add(createSubMultisetSuite(parentBuilder, Bound.INCLUSIVE, Bound.INCLUSIVE));
137     }
138 
139     return derivedSuites;
140   }
141 
142   private TestSuite createSubMultisetSuite(
143       SortedMultisetTestSuiteBuilder<E> parentBuilder, final Bound from, final Bound to) {
144     final TestMultisetGenerator<E> delegate =
145         (TestMultisetGenerator<E>) parentBuilder.getSubjectGenerator();
146 
147     Set<Feature<?>> features = new HashSet<>();
148     features.add(NoRecurse.SUBMULTISET);
149     features.add(RESTRICTS_ELEMENTS);
150     features.addAll(parentBuilder.getFeatures());
151 
152     if (!features.remove(SERIALIZABLE_INCLUDING_VIEWS)) {
153       features.remove(SERIALIZABLE);
154     }
155 
156     SortedMultiset<E> emptyMultiset = (SortedMultiset<E>) delegate.create();
157     final Comparator<? super E> comparator = emptyMultiset.comparator();
158     SampleElements<E> samples = delegate.samples();
159     @SuppressWarnings("unchecked")
160     List<E> samplesList =
161         Arrays.asList(samples.e0(), samples.e1(), samples.e2(), samples.e3(), samples.e4());
162 
163     Collections.sort(samplesList, comparator);
164     final E firstInclusive = samplesList.get(0);
165     final E lastInclusive = samplesList.get(samplesList.size() - 1);
166 
167     return SortedMultisetTestSuiteBuilder.using(
168             new ForwardingTestMultisetGenerator<E>(delegate) {
169               @Override
170               public SortedMultiset<E> create(Object... entries) {
171                 @SuppressWarnings("unchecked")
172                 // we dangerously assume E is a string
173                 List<E> extremeValues = (List) getExtremeValues();
174                 @SuppressWarnings("unchecked")
175                 // map generators must past entry objects
176                 List<E> normalValues = (List) Arrays.asList(entries);
177 
178                 // prepare extreme values to be filtered out of view
179                 Collections.sort(extremeValues, comparator);
180                 E firstExclusive = extremeValues.get(1);
181                 E lastExclusive = extremeValues.get(2);
182                 if (from == Bound.NO_BOUND) {
183                   extremeValues.remove(0);
184                   extremeValues.remove(0);
185                 }
186                 if (to == Bound.NO_BOUND) {
187                   extremeValues.remove(extremeValues.size() - 1);
188                   extremeValues.remove(extremeValues.size() - 1);
189                 }
190 
191                 // the regular values should be visible after filtering
192                 List<E> allEntries = new ArrayList<E>();
193                 allEntries.addAll(extremeValues);
194                 allEntries.addAll(normalValues);
195                 SortedMultiset<E> multiset =
196                     (SortedMultiset<E>) delegate.create(allEntries.toArray());
197 
198                 // call the smallest subMap overload that filters out the extreme
199                 // values
200                 if (from == Bound.INCLUSIVE) {
201                   multiset = multiset.tailMultiset(firstInclusive, BoundType.CLOSED);
202                 } else if (from == Bound.EXCLUSIVE) {
203                   multiset = multiset.tailMultiset(firstExclusive, BoundType.OPEN);
204                 }
205 
206                 if (to == Bound.INCLUSIVE) {
207                   multiset = multiset.headMultiset(lastInclusive, BoundType.CLOSED);
208                 } else if (to == Bound.EXCLUSIVE) {
209                   multiset = multiset.headMultiset(lastExclusive, BoundType.OPEN);
210                 }
211 
212                 return multiset;
213               }
214             })
215         .named(parentBuilder.getName() + " subMultiset " + from + "-" + to)
216         .withFeatures(features)
217         .suppressing(parentBuilder.getSuppressedTests())
218         .createTestSuite();
219   }
220 
221   /**
222    * Returns an array of four bogus elements that will always be too high or too
223    * low for the display. This includes two values for each extreme.
224    *
225    * <p>
226    * This method (dangerously) assume that the strings {@code "!! a"} and
227    * {@code "~~ z"} will work for this purpose, which may cause problems for
228    * navigable maps with non-string or unicode generators.
229    */
230   private List<String> getExtremeValues() {
231     List<String> result = new ArrayList<>();
232     result.add("!! a");
233     result.add("!! b");
234     result.add("~~ y");
235     result.add("~~ z");
236     return result;
237   }
238 
239   private TestSuite createDescendingSuite(SortedMultisetTestSuiteBuilder<E> parentBuilder) {
240     final TestMultisetGenerator<E> delegate =
241         (TestMultisetGenerator<E>) parentBuilder.getSubjectGenerator();
242 
243     Set<Feature<?>> features = new HashSet<>();
244     features.add(NoRecurse.DESCENDING);
245     features.addAll(parentBuilder.getFeatures());
246     if (!features.remove(SERIALIZABLE_INCLUDING_VIEWS)) {
247       features.remove(SERIALIZABLE);
248     }
249 
250     return SortedMultisetTestSuiteBuilder.using(
251             new ForwardingTestMultisetGenerator<E>(delegate) {
252               @Override
253               public SortedMultiset<E> create(Object... entries) {
254                 return ((SortedMultiset<E>) super.create(entries)).descendingMultiset();
255               }
256 
257               @Override
258               public Iterable<E> order(List<E> insertionOrder) {
259                 return ImmutableList.copyOf(super.order(insertionOrder)).reverse();
260               }
261             })
262         .named(parentBuilder.getName() + " descending")
263         .withFeatures(features)
264         .suppressing(parentBuilder.getSuppressedTests())
265         .createTestSuite();
266   }
267 
268   private TestSuite createReserializedSuite(SortedMultisetTestSuiteBuilder<E> parentBuilder) {
269     final TestMultisetGenerator<E> delegate =
270         (TestMultisetGenerator<E>) parentBuilder.getSubjectGenerator();
271 
272     Set<Feature<?>> features = new HashSet<>();
273     features.addAll(parentBuilder.getFeatures());
274     features.remove(SERIALIZABLE);
275     features.remove(SERIALIZABLE_INCLUDING_VIEWS);
276 
277     return SortedMultisetTestSuiteBuilder.using(
278             new ForwardingTestMultisetGenerator<E>(delegate) {
279               @Override
280               public SortedMultiset<E> create(Object... entries) {
281                 return SerializableTester.reserialize(((SortedMultiset<E>) super.create(entries)));
282               }
283             })
284         .named(parentBuilder.getName() + " reserialized")
285         .withFeatures(features)
286         .suppressing(parentBuilder.getSuppressedTests())
287         .createTestSuite();
288   }
289 
290   private static class ForwardingTestMultisetGenerator<E> implements TestMultisetGenerator<E> {
291     private final TestMultisetGenerator<E> delegate;
292 
293     ForwardingTestMultisetGenerator(TestMultisetGenerator<E> delegate) {
294       this.delegate = delegate;
295     }
296 
297     @Override
298     public SampleElements<E> samples() {
299       return delegate.samples();
300     }
301 
302     @Override
303     public E[] createArray(int length) {
304       return delegate.createArray(length);
305     }
306 
307     @Override
308     public Iterable<E> order(List<E> insertionOrder) {
309       return delegate.order(insertionOrder);
310     }
311 
312     @Override
313     public Multiset<E> create(Object... elements) {
314       return delegate.create(elements);
315     }
316   }
317 }