1 /* 2 * Copyright (C) 2010 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of 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, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.collect.testing; 18 19 import com.google.common.collect.testing.features.Feature; 20 import com.google.common.collect.testing.testers.MapNavigationTester; 21 22 import junit.framework.TestSuite; 23 24 import java.util.ArrayList; 25 import java.util.Arrays; 26 import java.util.Collections; 27 import java.util.Comparator; 28 import java.util.List; 29 import java.util.Map; 30 import java.util.Map.Entry; 31 import java.util.NavigableMap; 32 import java.util.Set; 33 34 /** 35 * Creates, based on your criteria, a JUnit test suite that exhaustively tests 36 * a NavigableMap implementation. 37 */ 38 public class NavigableMapTestSuiteBuilder<K, V> extends MapTestSuiteBuilder<K, V> { 39 public static <K, V> NavigableMapTestSuiteBuilder<K, V> using( 40 TestMapGenerator<K, V> generator) { 41 NavigableMapTestSuiteBuilder<K, V> result = new NavigableMapTestSuiteBuilder<K, V>(); 42 result.usingGenerator(generator); 43 return result; 44 } 45 46 @Override protected List<Class<? extends AbstractTester>> getTesters() { 47 List<Class<? extends AbstractTester>> testers = Helpers.copyToList(super.getTesters()); 48 testers.add(MapNavigationTester.class); 49 return testers; 50 } 51 52 @Override List<TestSuite> createDerivedSuites(FeatureSpecificTestSuiteBuilder<?, 53 ? extends OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>>> parentBuilder) { 54 List<TestSuite> derivedSuites = super.createDerivedSuites(parentBuilder); 55 56 if (!parentBuilder.getFeatures().contains(NoRecurse.DESCENDING)) { 57 derivedSuites.add(createDescendingSuite(parentBuilder)); 58 } 59 60 if (!parentBuilder.getFeatures().contains(NoRecurse.SUBMAP)) { 61 derivedSuites.add(createSubmapSuite(parentBuilder, Bound.NO_BOUND, Bound.EXCLUSIVE)); 62 derivedSuites.add(createSubmapSuite(parentBuilder, Bound.NO_BOUND, Bound.INCLUSIVE)); 63 derivedSuites.add(createSubmapSuite(parentBuilder, Bound.EXCLUSIVE, Bound.NO_BOUND)); 64 derivedSuites.add(createSubmapSuite(parentBuilder, Bound.EXCLUSIVE, Bound.EXCLUSIVE)); 65 derivedSuites.add(createSubmapSuite(parentBuilder, Bound.EXCLUSIVE, Bound.INCLUSIVE)); 66 derivedSuites.add(createSubmapSuite(parentBuilder, Bound.INCLUSIVE, Bound.NO_BOUND)); 67 derivedSuites.add(createSubmapSuite(parentBuilder, Bound.INCLUSIVE, Bound.EXCLUSIVE)); 68 derivedSuites.add(createSubmapSuite(parentBuilder, Bound.INCLUSIVE, Bound.INCLUSIVE)); 69 } 70 71 return derivedSuites; 72 } 73 74 @Override protected SetTestSuiteBuilder<K> createDerivedKeySetSuite( 75 TestSetGenerator<K> keySetGenerator) { 76 return NavigableSetTestSuiteBuilder.using(keySetGenerator); 77 } 78 79 /** 80 * To avoid infinite recursion, test suites with these marker features won't 81 * have derived suites created for them. 82 */ 83 enum NoRecurse implements Feature<Void> { 84 SUBMAP, 85 DESCENDING; 86 87 @Override 88 public Set<Feature<? super Void>> getImpliedFeatures() { 89 return Collections.emptySet(); 90 } 91 } 92 93 /** 94 * Two bounds (from and to) define how to build a subMap. 95 */ 96 enum Bound { 97 INCLUSIVE, 98 EXCLUSIVE, 99 NO_BOUND; 100 } 101 102 /** 103 * Creates a suite whose map has some elements filtered out of view. 104 * 105 * <p>Because the map may be ascending or descending, this test must derive 106 * the relative order of these extreme values rather than relying on their 107 * regular sort ordering. 108 */ 109 private TestSuite createSubmapSuite(final FeatureSpecificTestSuiteBuilder<?, 110 ? extends OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>>> 111 parentBuilder, final Bound from, final Bound to) { 112 final TestMapGenerator<K, V> delegate 113 = (TestMapGenerator<K, V>) parentBuilder.getSubjectGenerator().getInnerGenerator(); 114 115 List<Feature<?>> features = new ArrayList<Feature<?>>(); 116 features.add(NoRecurse.SUBMAP); 117 features.addAll(parentBuilder.getFeatures()); 118 119 NavigableMap<K, V> emptyMap = (NavigableMap<K, V>) delegate.create(); 120 final Comparator<Entry<K, V>> entryComparator = Helpers.entryComparator(emptyMap.comparator()); 121 122 // derive values for inclusive filtering from the input samples 123 SampleElements<Entry<K, V>> samples = delegate.samples(); 124 @SuppressWarnings("unchecked") // no elements are inserted into the array 125 List<Entry<K, V>> samplesList = Arrays.asList( 126 samples.e0, samples.e1, samples.e2, samples.e3, samples.e4); 127 Collections.sort(samplesList, entryComparator); 128 final K firstInclusive = samplesList.get(0).getKey(); 129 final K lastInclusive = samplesList.get(samplesList.size() - 1).getKey(); 130 131 return NavigableMapTestSuiteBuilder 132 .using(new ForwardingTestMapGenerator<K, V>(delegate) { 133 @Override public Map<K, V> create(Object... entries) { 134 @SuppressWarnings("unchecked") // we dangerously assume K and V are both strings 135 List<Entry<K, V>> extremeValues = (List) getExtremeValues(); 136 @SuppressWarnings("unchecked") // map generators must past entry objects 137 List<Entry<K, V>> normalValues = (List) Arrays.asList(entries); 138 139 // prepare extreme values to be filtered out of view 140 Collections.sort(extremeValues, entryComparator); 141 K firstExclusive = extremeValues.get(1).getKey(); 142 K lastExclusive = extremeValues.get(2).getKey(); 143 if (from == Bound.NO_BOUND) { 144 extremeValues.remove(0); 145 extremeValues.remove(0); 146 } 147 if (to == Bound.NO_BOUND) { 148 extremeValues.remove(extremeValues.size() - 1); 149 extremeValues.remove(extremeValues.size() - 1); 150 } 151 152 // the regular values should be visible after filtering 153 List<Entry<K, V>> allEntries = new ArrayList<Entry<K, V>>(); 154 allEntries.addAll(extremeValues); 155 allEntries.addAll(normalValues); 156 NavigableMap<K, V> map = (NavigableMap<K, V>) 157 delegate.create((Object[]) 158 allEntries.toArray(new Entry[allEntries.size()])); 159 160 // call the smallest subMap overload that filters out the extreme values 161 if (from == Bound.NO_BOUND && to == Bound.EXCLUSIVE) { 162 return map.headMap(lastExclusive); 163 } else if (from == Bound.NO_BOUND && to == Bound.INCLUSIVE) { 164 return map.headMap(lastInclusive, true); 165 } else if (from == Bound.EXCLUSIVE && to == Bound.NO_BOUND) { 166 return map.tailMap(firstExclusive, false); 167 } else if (from == Bound.EXCLUSIVE && to == Bound.EXCLUSIVE) { 168 return map.subMap(firstExclusive, false, lastExclusive, false); 169 } else if (from == Bound.EXCLUSIVE && to == Bound.INCLUSIVE) { 170 return map.subMap(firstExclusive, false, lastInclusive, true); 171 } else if (from == Bound.INCLUSIVE && to == Bound.NO_BOUND) { 172 return map.tailMap(firstInclusive); 173 } else if (from == Bound.INCLUSIVE && to == Bound.EXCLUSIVE) { 174 return map.subMap(firstInclusive, lastExclusive); 175 } else if (from == Bound.INCLUSIVE && to == Bound.INCLUSIVE) { 176 return map.subMap(firstInclusive, true, lastInclusive, true); 177 } else { 178 throw new IllegalArgumentException(); 179 } 180 } 181 }) 182 .named(parentBuilder.getName() + " subMap " + from + "-" + to) 183 .withFeatures(features) 184 .suppressing(parentBuilder.getSuppressedTests()) 185 .createTestSuite(); 186 } 187 188 /** 189 * Returns an array of four bogus elements that will always be too high or 190 * too low for the display. This includes two values for each extreme. 191 * 192 * <p>This method (dangerously) assume that the strings {@code "!! a"} and 193 * {@code "~~ z"} will work for this purpose, which may cause problems for 194 * navigable maps with non-string or unicode generators. 195 */ 196 private List<Entry<String, String>> getExtremeValues() { 197 List<Entry<String, String>> result = new ArrayList<Entry<String, String>>(); 198 result.add(Helpers.mapEntry("!! a", "below view")); 199 result.add(Helpers.mapEntry("!! b", "below view")); 200 result.add(Helpers.mapEntry("~~ y", "above view")); 201 result.add(Helpers.mapEntry("~~ z", "above view")); 202 return result; 203 } 204 205 /** 206 * Create a suite whose maps are descending views of other maps. 207 */ 208 private TestSuite createDescendingSuite(final FeatureSpecificTestSuiteBuilder<?, 209 ? extends OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>>> parentBuilder) { 210 final TestMapGenerator<K, V> delegate 211 = (TestMapGenerator<K, V>) parentBuilder.getSubjectGenerator().getInnerGenerator(); 212 213 List<Feature<?>> features = new ArrayList<Feature<?>>(); 214 features.add(NoRecurse.DESCENDING); 215 features.addAll(parentBuilder.getFeatures()); 216 217 return NavigableMapTestSuiteBuilder 218 .using(new ForwardingTestMapGenerator<K, V>(delegate) { 219 @Override public Map<K, V> create(Object... entries) { 220 NavigableMap<K, V> map = (NavigableMap<K, V>) delegate.create(entries); 221 return map.descendingMap(); 222 } 223 }) 224 .named(parentBuilder.getName() + " descending") 225 .withFeatures(features) 226 .suppressing(parentBuilder.getSuppressedTests()) 227 .createTestSuite(); 228 } 229 230 static class ForwardingTestMapGenerator<K, V> implements TestMapGenerator<K, V> { 231 private TestMapGenerator<K, V> delegate; 232 233 ForwardingTestMapGenerator(TestMapGenerator<K, V> delegate) { 234 this.delegate = delegate; 235 } 236 237 @Override 238 public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) { 239 return delegate.order(insertionOrder); 240 } 241 242 @Override 243 public K[] createKeyArray(int length) { 244 return delegate.createKeyArray(length); 245 } 246 247 @Override 248 public V[] createValueArray(int length) { 249 return delegate.createValueArray(length); 250 } 251 252 @Override 253 public SampleElements<Entry<K, V>> samples() { 254 return delegate.samples(); 255 } 256 257 @Override 258 public Map<K, V> create(Object... elements) { 259 return delegate.create(elements); 260 } 261 262 @Override 263 public Entry<K, V>[] createArray(int length) { 264 return delegate.createArray(length); 265 } 266 } 267 } 268
