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