DerivedCollectionGenerators.java revision 7dd252788645e940eada959bdde927426e2531c9
1/* 2 * Copyright (C) 2008 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 17package com.google.common.collect.testing; 18 19import static com.google.common.collect.testing.Helpers.castOrCopyToList; 20import static com.google.common.collect.testing.Helpers.equal; 21import static com.google.common.collect.testing.Helpers.mapEntry; 22import static java.util.Collections.sort; 23 24import com.google.common.annotations.GwtCompatible; 25 26import java.util.ArrayList; 27import java.util.Arrays; 28import java.util.Collection; 29import java.util.Collections; 30import java.util.Comparator; 31import java.util.List; 32import java.util.Map; 33import java.util.Map.Entry; 34import java.util.Set; 35import java.util.SortedMap; 36 37/** 38 * Derived suite generators, split out of the suite builders so that they are available to GWT. 39 * 40 * @author George van den Driessche 41 */ 42@GwtCompatible 43public final class DerivedCollectionGenerators { 44 public static class MapEntrySetGenerator<K, V> 45 implements TestSetGenerator<Map.Entry<K, V>>, DerivedGenerator { 46 private final OneSizeTestContainerGenerator<Map<K, V>, Map.Entry<K, V>> 47 mapGenerator; 48 49 public MapEntrySetGenerator( 50 OneSizeTestContainerGenerator< 51 Map<K, V>, Map.Entry<K, V>> mapGenerator) { 52 this.mapGenerator = mapGenerator; 53 } 54 55 @Override 56 public SampleElements<Map.Entry<K, V>> samples() { 57 return mapGenerator.samples(); 58 } 59 60 @Override 61 public Set<Map.Entry<K, V>> create(Object... elements) { 62 return mapGenerator.create(elements).entrySet(); 63 } 64 65 @Override 66 public Map.Entry<K, V>[] createArray(int length) { 67 return mapGenerator.createArray(length); 68 } 69 70 @Override 71 public Iterable<Map.Entry<K, V>> order( 72 List<Map.Entry<K, V>> insertionOrder) { 73 return mapGenerator.order(insertionOrder); 74 } 75 76 public OneSizeTestContainerGenerator<Map<K, V>, Map.Entry<K, V>> getInnerGenerator() { 77 return mapGenerator; 78 } 79 } 80 81 // TODO: investigate some API changes to SampleElements that would tidy up 82 // parts of the following classes. 83 84 public static class MapKeySetGenerator<K, V> 85 implements TestSetGenerator<K>, DerivedGenerator { 86 private final OneSizeTestContainerGenerator<Map<K, V>, Map.Entry<K, V>> 87 mapGenerator; 88 private final SampleElements<K> samples; 89 90 public MapKeySetGenerator( 91 OneSizeTestContainerGenerator<Map<K, V>, Map.Entry<K, V>> 92 mapGenerator) { 93 this.mapGenerator = mapGenerator; 94 final SampleElements<Map.Entry<K, V>> mapSamples = 95 this.mapGenerator.samples(); 96 this.samples = new SampleElements<K>( 97 mapSamples.e0.getKey(), 98 mapSamples.e1.getKey(), 99 mapSamples.e2.getKey(), 100 mapSamples.e3.getKey(), 101 mapSamples.e4.getKey()); 102 } 103 104 @Override 105 public SampleElements<K> samples() { 106 return samples; 107 } 108 109 @Override 110 public Set<K> create(Object... elements) { 111 @SuppressWarnings("unchecked") 112 K[] keysArray = (K[]) elements; 113 114 // Start with a suitably shaped collection of entries 115 Collection<Map.Entry<K, V>> originalEntries = 116 mapGenerator.getSampleElements(elements.length); 117 118 // Create a copy of that, with the desired value for each key 119 Collection<Map.Entry<K, V>> entries = 120 new ArrayList<Entry<K, V>>(elements.length); 121 int i = 0; 122 for (Map.Entry<K, V> entry : originalEntries) { 123 entries.add(Helpers.mapEntry(keysArray[i++], entry.getValue())); 124 } 125 126 return mapGenerator.create(entries.toArray()).keySet(); 127 } 128 129 @Override 130 public K[] createArray(int length) { 131 // TODO: with appropriate refactoring of OneSizeGenerator, we can perhaps 132 // tidy this up and get rid of the casts here and in 133 // MapValueCollectionGenerator. 134 135 return ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()) 136 .createKeyArray(length); 137 } 138 139 @Override 140 public Iterable<K> order(List<K> insertionOrder) { 141 V v = ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).samples().e0.getValue(); 142 List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>(); 143 for (K element : insertionOrder) { 144 entries.add(mapEntry(element, v)); 145 } 146 147 List<K> keys = new ArrayList<K>(); 148 for (Entry<K, V> entry : mapGenerator.order(entries)) { 149 keys.add(entry.getKey()); 150 } 151 return keys; 152 } 153 154 public OneSizeTestContainerGenerator<Map<K, V>, Map.Entry<K, V>> getInnerGenerator() { 155 return mapGenerator; 156 } 157 } 158 159 public static class MapValueCollectionGenerator<K, V> 160 implements TestCollectionGenerator<V>, DerivedGenerator { 161 private final OneSizeTestContainerGenerator<Map<K, V>, Map.Entry<K, V>> 162 mapGenerator; 163 private final SampleElements<V> samples; 164 165 public MapValueCollectionGenerator( 166 OneSizeTestContainerGenerator< 167 Map<K, V>, Map.Entry<K, V>> mapGenerator) { 168 this.mapGenerator = mapGenerator; 169 final SampleElements<Map.Entry<K, V>> mapSamples = 170 this.mapGenerator.samples(); 171 this.samples = new SampleElements<V>( 172 mapSamples.e0.getValue(), 173 mapSamples.e1.getValue(), 174 mapSamples.e2.getValue(), 175 mapSamples.e3.getValue(), 176 mapSamples.e4.getValue()); 177 } 178 179 @Override 180 public SampleElements<V> samples() { 181 return samples; 182 } 183 184 @Override 185 public Collection<V> create(Object... elements) { 186 @SuppressWarnings("unchecked") 187 V[] valuesArray = (V[]) elements; 188 189 // Start with a suitably shaped collection of entries 190 Collection<Map.Entry<K, V>> originalEntries = 191 mapGenerator.getSampleElements(elements.length); 192 193 // Create a copy of that, with the desired value for each value 194 Collection<Map.Entry<K, V>> entries = 195 new ArrayList<Entry<K, V>>(elements.length); 196 int i = 0; 197 for (Map.Entry<K, V> entry : originalEntries) { 198 entries.add(Helpers.mapEntry(entry.getKey(), valuesArray[i++])); 199 } 200 201 return mapGenerator.create(entries.toArray()).values(); 202 } 203 204 @Override 205 public V[] createArray(int length) { 206 //noinspection UnnecessaryLocalVariable 207 final V[] vs = ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()) 208 .createValueArray(length); 209 return vs; 210 } 211 212 @Override 213 public Iterable<V> order(List<V> insertionOrder) { 214 final List<Entry<K, V>> orderedEntries = 215 castOrCopyToList(mapGenerator.order(castOrCopyToList( 216 mapGenerator.getSampleElements(5)))); 217 sort(insertionOrder, new Comparator<V>() { 218 @Override public int compare(V left, V right) { 219 // The indexes are small enough for the subtraction trick to be safe. 220 return indexOfEntryWithValue(left) - indexOfEntryWithValue(right); 221 } 222 223 int indexOfEntryWithValue(V value) { 224 for (int i = 0; i < orderedEntries.size(); i++) { 225 if (equal(orderedEntries.get(i).getValue(), value)) { 226 return i; 227 } 228 } 229 throw new IllegalArgumentException("Map.values generator can order only sample values"); 230 } 231 }); 232 return insertionOrder; 233 } 234 235 public OneSizeTestContainerGenerator<Map<K, V>, Map.Entry<K, V>> getInnerGenerator() { 236 return mapGenerator; 237 } 238 } 239 240 // TODO(cpovirk): could something like this be used elsewhere, e.g., ReserializedListGenerator? 241 static class ForwardingTestMapGenerator<K, V> implements TestMapGenerator<K, V> { 242 TestMapGenerator<K, V> delegate; 243 244 ForwardingTestMapGenerator(TestMapGenerator<K, V> delegate) { 245 this.delegate = delegate; 246 } 247 248 @Override 249 public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) { 250 return delegate.order(insertionOrder); 251 } 252 253 @Override 254 public K[] createKeyArray(int length) { 255 return delegate.createKeyArray(length); 256 } 257 258 @Override 259 public V[] createValueArray(int length) { 260 return delegate.createValueArray(length); 261 } 262 263 @Override 264 public SampleElements<Entry<K, V>> samples() { 265 return delegate.samples(); 266 } 267 268 @Override 269 public Map<K, V> create(Object... elements) { 270 return delegate.create(elements); 271 } 272 273 @Override 274 public Entry<K, V>[] createArray(int length) { 275 return delegate.createArray(length); 276 } 277 } 278 279 /** 280 * Two bounds (from and to) define how to build a subMap. 281 */ 282 public enum Bound { 283 INCLUSIVE, 284 EXCLUSIVE, 285 NO_BOUND; 286 } 287 288 /* 289 * TODO(cpovirk): surely we can find a less ugly solution than a class that accepts 3 parameters, 290 * exposes as many getters, does work in the constructor, and has both a superclass and a subclass 291 */ 292 public static class SortedMapSubmapTestMapGenerator<K, V> 293 extends ForwardingTestMapGenerator<K, V> implements TestSortedMapGenerator<K, V> { 294 final Bound to; 295 final Bound from; 296 final K firstInclusive; 297 final K lastInclusive; 298 private final Comparator<Entry<K, V>> entryComparator; 299 300 public SortedMapSubmapTestMapGenerator( 301 TestSortedMapGenerator<K, V> delegate, Bound to, Bound from) { 302 super(delegate); 303 this.to = to; 304 this.from = from; 305 306 SortedMap<K, V> emptyMap = delegate.create(); 307 this.entryComparator = Helpers.entryComparator(emptyMap.comparator()); 308 309 // derive values for inclusive filtering from the input samples 310 SampleElements<Entry<K, V>> samples = delegate.samples(); 311 @SuppressWarnings("unchecked") // no elements are inserted into the array 312 List<Entry<K, V>> samplesList = Arrays.asList( 313 samples.e0, samples.e1, samples.e2, samples.e3, samples.e4); 314 Collections.sort(samplesList, entryComparator); 315 this.firstInclusive = samplesList.get(0).getKey(); 316 this.lastInclusive = samplesList.get(samplesList.size() - 1).getKey(); 317 } 318 319 @Override public SortedMap<K, V> create(Object... entries) { 320 @SuppressWarnings("unchecked") // map generators must past entry objects 321 List<Entry<K, V>> normalValues = (List) Arrays.asList(entries); 322 List<Entry<K, V>> extremeValues = new ArrayList<Entry<K, V>>(); 323 324 // prepare extreme values to be filtered out of view 325 K firstExclusive = getInnerGenerator().belowSamplesGreater().getKey(); 326 K lastExclusive = getInnerGenerator().aboveSamplesLesser().getKey(); 327 if (from != Bound.NO_BOUND) { 328 extremeValues.add(getInnerGenerator().belowSamplesLesser()); 329 extremeValues.add(getInnerGenerator().belowSamplesGreater()); 330 } 331 if (to != Bound.NO_BOUND) { 332 extremeValues.add(getInnerGenerator().aboveSamplesLesser()); 333 extremeValues.add(getInnerGenerator().aboveSamplesGreater()); 334 } 335 336 // the regular values should be visible after filtering 337 List<Entry<K, V>> allEntries = new ArrayList<Entry<K, V>>(); 338 allEntries.addAll(extremeValues); 339 allEntries.addAll(normalValues); 340 SortedMap<K, V> map = (SortedMap<K, V>) 341 delegate.create((Object[]) 342 allEntries.toArray(new Entry[allEntries.size()])); 343 344 return createSubMap(map, firstExclusive, lastExclusive); 345 } 346 347 /** 348 * Calls the smallest subMap overload that filters out the extreme values. This method is 349 * overridden in NavigableMapTestSuiteBuilder. 350 */ 351 SortedMap<K, V> createSubMap(SortedMap<K, V> map, K firstExclusive, K lastExclusive) { 352 if (from == Bound.NO_BOUND && to == Bound.EXCLUSIVE) { 353 return map.headMap(lastExclusive); 354 } else if (from == Bound.INCLUSIVE && to == Bound.NO_BOUND) { 355 return map.tailMap(firstInclusive); 356 } else if (from == Bound.INCLUSIVE && to == Bound.EXCLUSIVE) { 357 return map.subMap(firstInclusive, lastExclusive); 358 } else { 359 throw new IllegalArgumentException(); 360 } 361 } 362 363 public final Bound getTo() { 364 return to; 365 } 366 367 public final Bound getFrom() { 368 return from; 369 } 370 371 public final TestSortedMapGenerator<K, V> getInnerGenerator() { 372 return (TestSortedMapGenerator<K, V>) delegate; 373 } 374 375 @Override 376 public Entry<K, V> belowSamplesLesser() { 377 // should never reach here! 378 throw new UnsupportedOperationException(); 379 } 380 381 @Override 382 public Entry<K, V> belowSamplesGreater() { 383 // should never reach here! 384 throw new UnsupportedOperationException(); 385 } 386 387 @Override 388 public Entry<K, V> aboveSamplesLesser() { 389 // should never reach here! 390 throw new UnsupportedOperationException(); 391 } 392 393 @Override 394 public Entry<K, V> aboveSamplesGreater() { 395 // should never reach here! 396 throw new UnsupportedOperationException(); 397 } 398 } 399 400 private DerivedCollectionGenerators() {} 401} 402