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