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