Debian Codegraph @

guava-testlib/src/com/google/common/collect/testing/DerivedCollectionGenerators.java

raw
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
17 package com.google.common.collect.testing;
18
19 import static com.google.common.collect.testing.Helpers.castOrCopyToList;
20 import static com.google.common.collect.testing.Helpers.equal;
21 import static com.google.common.collect.testing.Helpers.mapEntry;
22 import static java.util.Collections.sort;
23
24 import com.google.common.annotations.GwtCompatible;
25 import java.util.ArrayList;
26 import java.util.Arrays;
27 import java.util.Collection;
28 import java.util.Collections;
29 import java.util.Comparator;
30 import java.util.List;
31 import java.util.Map;
32 import java.util.Map.Entry;
33 import java.util.Set;
34 import java.util.SortedMap;
35 import java.util.SortedSet;
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
43 public final class DerivedCollectionGenerators {
44 public static class MapEntrySetGenerator<K, V>
45 implements TestSetGenerator<Entry<K, V>>, DerivedGenerator {
46 private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
47
48 public MapEntrySetGenerator(
49 OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
50 this.mapGenerator = mapGenerator;
51 }
52
53 @Override
54 public SampleElements<Entry<K, V>> samples() {
55 return mapGenerator.samples();
56 }
57
58 @Override
59 public Set<Entry<K, V>> create(Object... elements) {
60 return mapGenerator.create(elements).entrySet();
61 }
62
63 @Override
64 public Entry<K, V>[] createArray(int length) {
65 return mapGenerator.createArray(length);
66 }
67
68 @Override
69 public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
70 return mapGenerator.order(insertionOrder);
71 }
72
73 @Override
74 public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
75 return mapGenerator;
76 }
77 }
78
79 // TODO: investigate some API changes to SampleElements that would tidy up
80 // parts of the following classes.
81
82 static <K, V> TestSetGenerator<K> keySetGenerator(
83 OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
84 TestContainerGenerator<Map<K, V>, Entry<K, V>> generator = mapGenerator.getInnerGenerator();
85 if (generator instanceof TestSortedMapGenerator
86 && ((TestSortedMapGenerator<K, V>) generator).create().keySet() instanceof SortedSet) {
87 return new MapSortedKeySetGenerator<>(mapGenerator);
88 } else {
89 return new MapKeySetGenerator<>(mapGenerator);
90 }
91 }
92
93 public static class MapKeySetGenerator<K, V> implements TestSetGenerator<K>, DerivedGenerator {
94 private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
95 private final SampleElements<K> samples;
96
97 public MapKeySetGenerator(OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
98 this.mapGenerator = mapGenerator;
99 SampleElements<Entry<K, V>> mapSamples = this.mapGenerator.samples();
100 this.samples =
101 new SampleElements<>(
102 mapSamples.e0().getKey(),
103 mapSamples.e1().getKey(),
104 mapSamples.e2().getKey(),
105 mapSamples.e3().getKey(),
106 mapSamples.e4().getKey());
107 }
108
109 @Override
110 public SampleElements<K> samples() {
111 return samples;
112 }
113
114 @Override
115 public Set<K> create(Object... elements) {
116 @SuppressWarnings("unchecked")
117 K[] keysArray = (K[]) elements;
118
119 // Start with a suitably shaped collection of entries
120 Collection<Entry<K, V>> originalEntries = mapGenerator.getSampleElements(elements.length);
121
122 // Create a copy of that, with the desired value for each key
123 Collection<Entry<K, V>> entries = new ArrayList<>(elements.length);
124 int i = 0;
125 for (Entry<K, V> entry : originalEntries) {
126 entries.add(Helpers.mapEntry(keysArray[i++], entry.getValue()));
127 }
128
129 return mapGenerator.create(entries.toArray()).keySet();
130 }
131
132 @Override
133 public K[] createArray(int length) {
134 // TODO: with appropriate refactoring of OneSizeGenerator, we can perhaps
135 // tidy this up and get rid of the casts here and in
136 // MapValueCollectionGenerator.
137
138 return ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).createKeyArray(length);
139 }
140
141 @Override
142 public Iterable<K> order(List<K> insertionOrder) {
143 V v = ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).samples().e0().getValue();
144 List<Entry<K, V>> entries = new ArrayList<>();
145 for (K element : insertionOrder) {
146 entries.add(mapEntry(element, v));
147 }
148
149 List<K> keys = new ArrayList<>();
150 for (Entry<K, V> entry : mapGenerator.order(entries)) {
151 keys.add(entry.getKey());
152 }
153 return keys;
154 }
155
156 @Override
157 public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
158 return mapGenerator;
159 }
160 }
161
162 public static class MapSortedKeySetGenerator<K, V> extends MapKeySetGenerator<K, V>
163 implements TestSortedSetGenerator<K>, DerivedGenerator {
164 private final TestSortedMapGenerator<K, V> delegate;
165
166 public MapSortedKeySetGenerator(
167 OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
168 super(mapGenerator);
169 this.delegate = (TestSortedMapGenerator<K, V>) mapGenerator.getInnerGenerator();
170 }
171
172 @Override
173 public SortedSet<K> create(Object... elements) {
174 return (SortedSet<K>) super.create(elements);
175 }
176
177 @Override
178 public K belowSamplesLesser() {
179 return delegate.belowSamplesLesser().getKey();
180 }
181
182 @Override
183 public K belowSamplesGreater() {
184 return delegate.belowSamplesGreater().getKey();
185 }
186
187 @Override
188 public K aboveSamplesLesser() {
189 return delegate.aboveSamplesLesser().getKey();
190 }
191
192 @Override
193 public K aboveSamplesGreater() {
194 return delegate.aboveSamplesGreater().getKey();
195 }
196 }
197
198 public static class MapValueCollectionGenerator<K, V>
199 implements TestCollectionGenerator<V>, DerivedGenerator {
200 private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
201 private final SampleElements<V> samples;
202
203 public MapValueCollectionGenerator(
204 OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
205 this.mapGenerator = mapGenerator;
206 SampleElements<Entry<K, V>> mapSamples = this.mapGenerator.samples();
207 this.samples =
208 new SampleElements<>(
209 mapSamples.e0().getValue(),
210 mapSamples.e1().getValue(),
211 mapSamples.e2().getValue(),
212 mapSamples.e3().getValue(),
213 mapSamples.e4().getValue());
214 }
215
216 @Override
217 public SampleElements<V> samples() {
218 return samples;
219 }
220
221 @Override
222 public Collection<V> create(Object... elements) {
223 @SuppressWarnings("unchecked")
224 V[] valuesArray = (V[]) elements;
225
226 // Start with a suitably shaped collection of entries
227 Collection<Entry<K, V>> originalEntries = mapGenerator.getSampleElements(elements.length);
228
229 // Create a copy of that, with the desired value for each value
230 Collection<Entry<K, V>> entries = new ArrayList<>(elements.length);
231 int i = 0;
232 for (Entry<K, V> entry : originalEntries) {
233 entries.add(Helpers.mapEntry(entry.getKey(), valuesArray[i++]));
234 }
235
236 return mapGenerator.create(entries.toArray()).values();
237 }
238
239 @Override
240 public V[] createArray(int length) {
241 // noinspection UnnecessaryLocalVariable
242 V[] vs = ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).createValueArray(length);
243 return vs;
244 }
245
246 @Override
247 public Iterable<V> order(List<V> insertionOrder) {
248 List<Entry<K, V>> orderedEntries =
249 castOrCopyToList(mapGenerator.order(castOrCopyToList(mapGenerator.getSampleElements(5))));
250 sort(
251 insertionOrder,
252 new Comparator<V>() {
253 @Override
254 public int compare(V left, V right) {
255 // The indexes are small enough for the subtraction trick to be safe.
256 return indexOfEntryWithValue(left) - indexOfEntryWithValue(right);
257 }
258
259 int indexOfEntryWithValue(V value) {
260 for (int i = 0; i < orderedEntries.size(); i++) {
261 if (equal(orderedEntries.get(i).getValue(), value)) {
262 return i;
263 }
264 }
265 throw new IllegalArgumentException(
266 "Map.values generator can order only sample values");
267 }
268 });
269 return insertionOrder;
270 }
271
272 @Override
273 public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
274 return mapGenerator;
275 }
276 }
277
278 // TODO(cpovirk): could something like this be used elsewhere, e.g., ReserializedListGenerator?
279 static class ForwardingTestMapGenerator<K, V> implements TestMapGenerator<K, V> {
280 TestMapGenerator<K, V> delegate;
281
282 ForwardingTestMapGenerator(TestMapGenerator<K, V> delegate) {
283 this.delegate = delegate;
284 }
285
286 @Override
287 public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
288 return delegate.order(insertionOrder);
289 }
290
291 @Override
292 public K[] createKeyArray(int length) {
293 return delegate.createKeyArray(length);
294 }
295
296 @Override
297 public V[] createValueArray(int length) {
298 return delegate.createValueArray(length);
299 }
300
301 @Override
302 public SampleElements<Entry<K, V>> samples() {
303 return delegate.samples();
304 }
305
306 @Override
307 public Map<K, V> create(Object... elements) {
308 return delegate.create(elements);
309 }
310
311 @Override
312 public Entry<K, V>[] createArray(int length) {
313 return delegate.createArray(length);
314 }
315 }
316
317 /** Two bounds (from and to) define how to build a subMap. */
318 public enum Bound {
319 INCLUSIVE,
320 EXCLUSIVE,
321 NO_BOUND;
322 }
323
324 public static class SortedSetSubsetTestSetGenerator<E> implements TestSortedSetGenerator<E> {
325 final Bound to;
326 final Bound from;
327 final E firstInclusive;
328 final E lastInclusive;
329 private final Comparator<? super E> comparator;
330 private final TestSortedSetGenerator<E> delegate;
331
332 public SortedSetSubsetTestSetGenerator(
333 TestSortedSetGenerator<E> delegate, Bound to, Bound from) {
334 this.to = to;
335 this.from = from;
336 this.delegate = delegate;
337
338 SortedSet<E> emptySet = delegate.create();
339 this.comparator = emptySet.comparator();
340
341 SampleElements<E> samples = delegate.samples();
342 List<E> samplesList = new ArrayList<>(samples.asList());
343 Collections.sort(samplesList, comparator);
344 this.firstInclusive = samplesList.get(0);
345 this.lastInclusive = samplesList.get(samplesList.size() - 1);
346 }
347
348 public final TestSortedSetGenerator<E> getInnerGenerator() {
349 return delegate;
350 }
351
352 public final Bound getTo() {
353 return to;
354 }
355
356 public final Bound getFrom() {
357 return from;
358 }
359
360 @Override
361 public SampleElements<E> samples() {
362 return delegate.samples();
363 }
364
365 @Override
366 public E[] createArray(int length) {
367 return delegate.createArray(length);
368 }
369
370 @Override
371 public Iterable<E> order(List<E> insertionOrder) {
372 return delegate.order(insertionOrder);
373 }
374
375 @Override
376 public SortedSet<E> create(Object... elements) {
377 List<?> normalValues = (List<?>) Arrays.asList(elements);
378 List<E> extremeValues = new ArrayList<>();
379
380 // nulls are usually out of bounds for a subset, so ban them altogether
381 for (Object o : elements) {
382 if (o == null) {
383 throw new NullPointerException();
384 }
385 }
386
387 // prepare extreme values to be filtered out of view
388 E firstExclusive = delegate.belowSamplesGreater();
389 E lastExclusive = delegate.aboveSamplesLesser();
390 if (from != Bound.NO_BOUND) {
391 extremeValues.add(delegate.belowSamplesLesser());
392 extremeValues.add(delegate.belowSamplesGreater());
393 }
394 if (to != Bound.NO_BOUND) {
395 extremeValues.add(delegate.aboveSamplesLesser());
396 extremeValues.add(delegate.aboveSamplesGreater());
397 }
398
399 // the regular values should be visible after filtering
400 List<Object> allEntries = new ArrayList<>();
401 allEntries.addAll(extremeValues);
402 allEntries.addAll(normalValues);
403 SortedSet<E> set = delegate.create(allEntries.toArray());
404
405 return createSubSet(set, firstExclusive, lastExclusive);
406 }
407
408 /** Calls the smallest subSet overload that filters out the extreme values. */
409 SortedSet<E> createSubSet(SortedSet<E> set, E firstExclusive, E lastExclusive) {
410 if (from == Bound.NO_BOUND && to == Bound.EXCLUSIVE) {
411 return set.headSet(lastExclusive);
412 } else if (from == Bound.INCLUSIVE && to == Bound.NO_BOUND) {
413 return set.tailSet(firstInclusive);
414 } else if (from == Bound.INCLUSIVE && to == Bound.EXCLUSIVE) {
415 return set.subSet(firstInclusive, lastExclusive);
416 } else {
417 throw new IllegalArgumentException();
418 }
419 }
420
421 @Override
422 public E belowSamplesLesser() {
423 throw new UnsupportedOperationException();
424 }
425
426 @Override
427 public E belowSamplesGreater() {
428 throw new UnsupportedOperationException();
429 }
430
431 @Override
432 public E aboveSamplesLesser() {
433 throw new UnsupportedOperationException();
434 }
435
436 @Override
437 public E aboveSamplesGreater() {
438 throw new UnsupportedOperationException();
439 }
440 }
441
442 /*
443 * TODO(cpovirk): surely we can find a less ugly solution than a class that accepts 3 parameters,
444 * exposes as many getters, does work in the constructor, and has both a superclass and a subclass
445 */
446 public static class SortedMapSubmapTestMapGenerator<K, V> extends ForwardingTestMapGenerator<K, V>
447 implements TestSortedMapGenerator<K, V> {
448 final Bound to;
449 final Bound from;
450 final K firstInclusive;
451 final K lastInclusive;
452 private final Comparator<Entry<K, V>> entryComparator;
453
454 public SortedMapSubmapTestMapGenerator(
455 TestSortedMapGenerator<K, V> delegate, Bound to, Bound from) {
456 super(delegate);
457 this.to = to;
458 this.from = from;
459
460 SortedMap<K, V> emptyMap = delegate.create();
461 this.entryComparator = Helpers.entryComparator(emptyMap.comparator());
462
463 // derive values for inclusive filtering from the input samples
464 SampleElements<Entry<K, V>> samples = delegate.samples();
465 @SuppressWarnings("unchecked") // no elements are inserted into the array
466 List<Entry<K, V>> samplesList =
467 Arrays.asList(samples.e0(), samples.e1(), samples.e2(), samples.e3(), samples.e4());
468 Collections.sort(samplesList, entryComparator);
469 this.firstInclusive = samplesList.get(0).getKey();
470 this.lastInclusive = samplesList.get(samplesList.size() - 1).getKey();
471 }
472
473 @Override
474 public SortedMap<K, V> create(Object... entries) {
475 List<Entry<K, V>> extremeValues = new ArrayList<>();
476
477 // prepare extreme values to be filtered out of view
478 K firstExclusive = getInnerGenerator().belowSamplesGreater().getKey();
479 K lastExclusive = getInnerGenerator().aboveSamplesLesser().getKey();
480 if (from != Bound.NO_BOUND) {
481 extremeValues.add(getInnerGenerator().belowSamplesLesser());
482 extremeValues.add(getInnerGenerator().belowSamplesGreater());
483 }
484 if (to != Bound.NO_BOUND) {
485 extremeValues.add(getInnerGenerator().aboveSamplesLesser());
486 extremeValues.add(getInnerGenerator().aboveSamplesGreater());
487 }
488
489 // the regular values should be visible after filtering
490 List<Entry<?, ?>> allEntries = new ArrayList<>();
491 allEntries.addAll(extremeValues);
492 for (Object entry : entries) {
493 allEntries.add((Entry<?, ?>) entry);
494 }
495 SortedMap<K, V> map = (SortedMap<K, V>) delegate.create(allEntries.toArray());
496
497 return createSubMap(map, firstExclusive, lastExclusive);
498 }
499
500 /**
501 * Calls the smallest subMap overload that filters out the extreme values. This method is
502 * overridden in NavigableMapTestSuiteBuilder.
503 */
504 SortedMap<K, V> createSubMap(SortedMap<K, V> map, K firstExclusive, K lastExclusive) {
505 if (from == Bound.NO_BOUND && to == Bound.EXCLUSIVE) {
506 return map.headMap(lastExclusive);
507 } else if (from == Bound.INCLUSIVE && to == Bound.NO_BOUND) {
508 return map.tailMap(firstInclusive);
509 } else if (from == Bound.INCLUSIVE && to == Bound.EXCLUSIVE) {
510 return map.subMap(firstInclusive, lastExclusive);
511 } else {
512 throw new IllegalArgumentException();
513 }
514 }
515
516 public final Bound getTo() {
517 return to;
518 }
519
520 public final Bound getFrom() {
521 return from;
522 }
523
524 public final TestSortedMapGenerator<K, V> getInnerGenerator() {
525 return (TestSortedMapGenerator<K, V>) delegate;
526 }
527
528 @Override
529 public Entry<K, V> belowSamplesLesser() {
530 // should never reach here!
531 throw new UnsupportedOperationException();
532 }
533
534 @Override
535 public Entry<K, V> belowSamplesGreater() {
536 // should never reach here!
537 throw new UnsupportedOperationException();
538 }
539
540 @Override
541 public Entry<K, V> aboveSamplesLesser() {
542 // should never reach here!
543 throw new UnsupportedOperationException();
544 }
545
546 @Override
547 public Entry<K, V> aboveSamplesGreater() {
548 // should never reach here!
549 throw new UnsupportedOperationException();
550 }
551 }
552
553 private DerivedCollectionGenerators() {}
554 }