001/*
002 * Copyright (C) 2011 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
005 * use this file except in compliance with the License. You may obtain a copy of
006 * the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
012 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
013 * License for the specific language governing permissions and limitations under
014 * the License.
015 */
016
017package com.google.common.collect.testing.google;
018
019import static com.google.common.collect.testing.Helpers.copyToList;
020import static com.google.common.collect.testing.features.CollectionFeature.KNOWN_ORDER;
021import static com.google.common.collect.testing.features.CollectionFeature.RESTRICTS_ELEMENTS;
022import static com.google.common.collect.testing.features.CollectionFeature.SERIALIZABLE;
023import static com.google.common.collect.testing.features.CollectionFeature.SERIALIZABLE_INCLUDING_VIEWS;
024import static java.util.Arrays.asList;
025import static java.util.Collections.emptySet;
026import static java.util.Collections.sort;
027
028import com.google.common.annotations.GwtIncompatible;
029import com.google.common.collect.BoundType;
030import com.google.common.collect.ImmutableList;
031import com.google.common.collect.Lists;
032import com.google.common.collect.Multiset;
033import com.google.common.collect.SortedMultiset;
034import com.google.common.collect.testing.AbstractTester;
035import com.google.common.collect.testing.FeatureSpecificTestSuiteBuilder;
036import com.google.common.collect.testing.OneSizeTestContainerGenerator;
037import com.google.common.collect.testing.SampleElements;
038import com.google.common.collect.testing.SetTestSuiteBuilder;
039import com.google.common.collect.testing.features.Feature;
040import com.google.common.testing.SerializableTester;
041import java.util.ArrayList;
042import java.util.Collection;
043import java.util.Comparator;
044import java.util.HashSet;
045import java.util.List;
046import java.util.Set;
047import junit.framework.TestSuite;
048
049/**
050 * Creates, based on your criteria, a JUnit test suite that exhaustively tests a {@code
051 * SortedMultiset} implementation.
052 *
053 * <p><b>Warning:</b> expects that {@code E} is a String.
054 *
055 * @author Louis Wasserman
056 */
057@GwtIncompatible
058public class SortedMultisetTestSuiteBuilder<E> extends MultisetTestSuiteBuilder<E> {
059  public static <E> SortedMultisetTestSuiteBuilder<E> using(TestMultisetGenerator<E> generator) {
060    SortedMultisetTestSuiteBuilder<E> result = new SortedMultisetTestSuiteBuilder<>();
061    result.usingGenerator(generator);
062    return result;
063  }
064
065  @Override
066  public TestSuite createTestSuite() {
067    withFeatures(KNOWN_ORDER);
068    TestSuite suite = super.createTestSuite();
069    for (TestSuite subSuite : createDerivedSuites(this)) {
070      suite.addTest(subSuite);
071    }
072    return suite;
073  }
074
075  @SuppressWarnings("rawtypes") // class literals
076  @Override
077  protected List<Class<? extends AbstractTester>> getTesters() {
078    List<Class<? extends AbstractTester>> testers = copyToList(super.getTesters());
079    testers.add(MultisetNavigationTester.class);
080    return testers;
081  }
082
083  @Override
084  TestSuite createElementSetTestSuite(
085      FeatureSpecificTestSuiteBuilder<?, ? extends OneSizeTestContainerGenerator<Collection<E>, E>>
086          parentBuilder) {
087    // TODO(lowasser): make a SortedElementSetGenerator
088    return SetTestSuiteBuilder.using(
089            new ElementSetGenerator<E>(parentBuilder.getSubjectGenerator()))
090        .named(getName() + ".elementSet")
091        .withFeatures(computeElementSetFeatures(parentBuilder.getFeatures()))
092        .suppressing(parentBuilder.getSuppressedTests())
093        .createTestSuite();
094  }
095
096  /**
097   * To avoid infinite recursion, test suites with these marker features won't have derived suites
098   * created for them.
099   */
100  enum NoRecurse implements Feature<Void> {
101    SUBMULTISET,
102    DESCENDING;
103
104    @Override
105    public Set<Feature<? super Void>> getImpliedFeatures() {
106      return emptySet();
107    }
108  }
109
110  /** Two bounds (from and to) define how to build a subMultiset. */
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, Bound from, Bound to) {
144    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    Comparator<? super E> comparator = emptyMultiset.comparator();
158    SampleElements<E> samples = delegate.samples();
159    List<E> samplesList =
160        asList(samples.e0(), samples.e1(), samples.e2(), samples.e3(), samples.e4());
161
162    sort(samplesList, comparator);
163    E firstInclusive = samplesList.get(0);
164    E lastInclusive = samplesList.get(samplesList.size() - 1);
165
166    return SortedMultisetTestSuiteBuilder.using(
167            new ForwardingTestMultisetGenerator<E>(delegate) {
168              @Override
169              public SortedMultiset<E> create(Object... entries) {
170                @SuppressWarnings("unchecked")
171                // we dangerously assume E is a string
172                List<E> extremeValues = (List<E>) getExtremeValues();
173                @SuppressWarnings("unchecked")
174                // map generators must past entry objects
175                List<E> normalValues = (List<E>) asList(entries);
176
177                // prepare extreme values to be filtered out of view
178                sort(extremeValues, comparator);
179                E firstExclusive = extremeValues.get(1);
180                E lastExclusive = extremeValues.get(2);
181                if (from == Bound.NO_BOUND) {
182                  extremeValues.remove(0);
183                  extremeValues.remove(0);
184                }
185                if (to == Bound.NO_BOUND) {
186                  extremeValues.remove(extremeValues.size() - 1);
187                  extremeValues.remove(extremeValues.size() - 1);
188                }
189
190                // the regular values should be visible after filtering
191                List<E> allEntries = new ArrayList<>();
192                allEntries.addAll(extremeValues);
193                allEntries.addAll(normalValues);
194                SortedMultiset<E> multiset =
195                    (SortedMultiset<E>) delegate.create(allEntries.toArray());
196
197                // call the smallest subMap overload that filters out the extreme
198                // values
199                if (from == Bound.INCLUSIVE) {
200                  multiset = multiset.tailMultiset(firstInclusive, BoundType.CLOSED);
201                } else if (from == Bound.EXCLUSIVE) {
202                  multiset = multiset.tailMultiset(firstExclusive, BoundType.OPEN);
203                }
204
205                if (to == Bound.INCLUSIVE) {
206                  multiset = multiset.headMultiset(lastInclusive, BoundType.CLOSED);
207                } else if (to == Bound.EXCLUSIVE) {
208                  multiset = multiset.headMultiset(lastExclusive, BoundType.OPEN);
209                }
210
211                return multiset;
212              }
213            })
214        .named(parentBuilder.getName() + " subMultiset " + from + "-" + to)
215        .withFeatures(features)
216        .suppressing(parentBuilder.getSuppressedTests())
217        .createTestSuite();
218  }
219
220  /**
221   * Returns an array of four bogus elements that will always be too high or too low for the
222   * display. This includes two values for each extreme.
223   *
224   * <p>This method (dangerously) assume that the strings {@code "!! a"} and {@code "~~ z"} will
225   * work for this purpose, which may cause problems for navigable maps with non-string or unicode
226   * generators.
227   */
228  private List<String> getExtremeValues() {
229    List<String> result = new ArrayList<>();
230    result.add("!! a");
231    result.add("!! b");
232    result.add("~~ y");
233    result.add("~~ z");
234    return result;
235  }
236
237  private TestSuite createDescendingSuite(SortedMultisetTestSuiteBuilder<E> parentBuilder) {
238    TestMultisetGenerator<E> delegate =
239        (TestMultisetGenerator<E>) parentBuilder.getSubjectGenerator();
240
241    Set<Feature<?>> features = new HashSet<>();
242    features.add(NoRecurse.DESCENDING);
243    features.addAll(parentBuilder.getFeatures());
244    if (!features.remove(SERIALIZABLE_INCLUDING_VIEWS)) {
245      features.remove(SERIALIZABLE);
246    }
247
248    return SortedMultisetTestSuiteBuilder.using(
249            new ForwardingTestMultisetGenerator<E>(delegate) {
250              @Override
251              public SortedMultiset<E> create(Object... entries) {
252                return ((SortedMultiset<E>) super.create(entries)).descendingMultiset();
253              }
254
255              @Override
256              public Iterable<E> order(List<E> insertionOrder) {
257                return ImmutableList.copyOf(super.order(insertionOrder)).reverse();
258              }
259            })
260        .named(parentBuilder.getName() + " descending")
261        .withFeatures(features)
262        .suppressing(parentBuilder.getSuppressedTests())
263        .createTestSuite();
264  }
265
266  private TestSuite createReserializedSuite(SortedMultisetTestSuiteBuilder<E> parentBuilder) {
267    TestMultisetGenerator<E> delegate =
268        (TestMultisetGenerator<E>) parentBuilder.getSubjectGenerator();
269
270    Set<Feature<?>> features = new HashSet<>(parentBuilder.getFeatures());
271    features.remove(SERIALIZABLE);
272    features.remove(SERIALIZABLE_INCLUDING_VIEWS);
273
274    return SortedMultisetTestSuiteBuilder.using(
275            new ForwardingTestMultisetGenerator<E>(delegate) {
276              @Override
277              public SortedMultiset<E> create(Object... entries) {
278                return SerializableTester.reserialize(((SortedMultiset<E>) super.create(entries)));
279              }
280            })
281        .named(parentBuilder.getName() + " reserialized")
282        .withFeatures(features)
283        .suppressing(parentBuilder.getSuppressedTests())
284        .createTestSuite();
285  }
286
287  private static class ForwardingTestMultisetGenerator<E> implements TestMultisetGenerator<E> {
288    private final TestMultisetGenerator<E> delegate;
289
290    ForwardingTestMultisetGenerator(TestMultisetGenerator<E> delegate) {
291      this.delegate = delegate;
292    }
293
294    @Override
295    public SampleElements<E> samples() {
296      return delegate.samples();
297    }
298
299    @Override
300    public E[] createArray(int length) {
301      return delegate.createArray(length);
302    }
303
304    @Override
305    public Iterable<E> order(List<E> insertionOrder) {
306      return delegate.order(insertionOrder);
307    }
308
309    @Override
310    public Multiset<E> create(Object... elements) {
311      return delegate.create(elements);
312    }
313  }
314}