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}