guava

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
import org.checkerframework.checker.nullness.qual.Nullable;
37

38
/**
39
 * Derived suite generators, split out of the suite builders so that they are available to GWT.
40
 *
41
 * @author George van den Driessche
42
 */
43
@GwtCompatible
44
@ElementTypesAreNonnullByDefault
45
public final class DerivedCollectionGenerators {
46
  public static class MapEntrySetGenerator<K extends @Nullable Object, V extends @Nullable Object>
47
      implements TestSetGenerator<Entry<K, V>>, DerivedGenerator {
48
    private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
49

50
    public MapEntrySetGenerator(
51
        OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
52
      this.mapGenerator = mapGenerator;
53
    }
54

55
    @Override
56
    public SampleElements<Entry<K, V>> samples() {
57
      return mapGenerator.samples();
58
    }
59

60
    @Override
61
    public Set<Entry<K, V>> create(Object... elements) {
62
      return mapGenerator.create(elements).entrySet();
63
    }
64

65
    @Override
66
    public Entry<K, V>[] createArray(int length) {
67
      return mapGenerator.createArray(length);
68
    }
69

70
    @Override
71
    public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
72
      return mapGenerator.order(insertionOrder);
73
    }
74

75
    @Override
76
    public OneSizeTestContainerGenerator<Map<K, V>, 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
  static <K extends @Nullable Object, V extends @Nullable Object>
85
      TestSetGenerator<K> keySetGenerator(
86
          OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
87
    TestContainerGenerator<Map<K, V>, Entry<K, V>> generator = mapGenerator.getInnerGenerator();
88
    if (generator instanceof TestSortedMapGenerator
89
        && ((TestSortedMapGenerator<K, V>) generator).create().keySet() instanceof SortedSet) {
90
      return new MapSortedKeySetGenerator<>(mapGenerator);
91
    } else {
92
      return new MapKeySetGenerator<>(mapGenerator);
93
    }
94
  }
95

96
  public static class MapKeySetGenerator<K extends @Nullable Object, V extends @Nullable Object>
97
      implements TestSetGenerator<K>, DerivedGenerator {
98
    private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
99
    private final SampleElements<K> samples;
100

101
    public MapKeySetGenerator(OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
102
      this.mapGenerator = mapGenerator;
103
      SampleElements<Entry<K, V>> mapSamples = this.mapGenerator.samples();
104
      this.samples =
105
          new SampleElements<>(
106
              mapSamples.e0().getKey(),
107
              mapSamples.e1().getKey(),
108
              mapSamples.e2().getKey(),
109
              mapSamples.e3().getKey(),
110
              mapSamples.e4().getKey());
111
    }
112

113
    @Override
114
    public SampleElements<K> samples() {
115
      return samples;
116
    }
117

118
    @Override
119
    public Set<K> create(Object... elements) {
120
      @SuppressWarnings("unchecked")
121
      K[] keysArray = (K[]) elements;
122

123
      // Start with a suitably shaped collection of entries
124
      Collection<Entry<K, V>> originalEntries = mapGenerator.getSampleElements(elements.length);
125

126
      // Create a copy of that, with the desired value for each key
127
      Collection<Entry<K, V>> entries = new ArrayList<>(elements.length);
128
      int i = 0;
129
      for (Entry<K, V> entry : originalEntries) {
130
        entries.add(Helpers.mapEntry(keysArray[i++], entry.getValue()));
131
      }
132

133
      return mapGenerator.create(entries.toArray()).keySet();
134
    }
135

136
    @Override
137
    public K[] createArray(int length) {
138
      // TODO: with appropriate refactoring of OneSizeGenerator, we can perhaps
139
      // tidy this up and get rid of the casts here and in
140
      // MapValueCollectionGenerator.
141

142
      return ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).createKeyArray(length);
143
    }
144

145
    @Override
146
    public Iterable<K> order(List<K> insertionOrder) {
147
      V v = ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).samples().e0().getValue();
148
      List<Entry<K, V>> entries = new ArrayList<>();
149
      for (K element : insertionOrder) {
150
        entries.add(mapEntry(element, v));
151
      }
152

153
      List<K> keys = new ArrayList<>();
154
      for (Entry<K, V> entry : mapGenerator.order(entries)) {
155
        keys.add(entry.getKey());
156
      }
157
      return keys;
158
    }
159

160
    @Override
161
    public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
162
      return mapGenerator;
163
    }
164
  }
165

166
  public static class MapSortedKeySetGenerator<
167
          K extends @Nullable Object, V extends @Nullable Object>
168
      extends MapKeySetGenerator<K, V> implements TestSortedSetGenerator<K>, DerivedGenerator {
169
    private final TestSortedMapGenerator<K, V> delegate;
170

171
    public MapSortedKeySetGenerator(
172
        OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
173
      super(mapGenerator);
174
      this.delegate = (TestSortedMapGenerator<K, V>) mapGenerator.getInnerGenerator();
175
    }
176

177
    @Override
178
    public SortedSet<K> create(Object... elements) {
179
      return (SortedSet<K>) super.create(elements);
180
    }
181

182
    @Override
183
    public K belowSamplesLesser() {
184
      return delegate.belowSamplesLesser().getKey();
185
    }
186

187
    @Override
188
    public K belowSamplesGreater() {
189
      return delegate.belowSamplesGreater().getKey();
190
    }
191

192
    @Override
193
    public K aboveSamplesLesser() {
194
      return delegate.aboveSamplesLesser().getKey();
195
    }
196

197
    @Override
198
    public K aboveSamplesGreater() {
199
      return delegate.aboveSamplesGreater().getKey();
200
    }
201
  }
202

203
  public static class MapValueCollectionGenerator<
204
          K extends @Nullable Object, V extends @Nullable Object>
205
      implements TestCollectionGenerator<V>, DerivedGenerator {
206
    private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
207
    private final SampleElements<V> samples;
208

209
    public MapValueCollectionGenerator(
210
        OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
211
      this.mapGenerator = mapGenerator;
212
      SampleElements<Entry<K, V>> mapSamples = this.mapGenerator.samples();
213
      this.samples =
214
          new SampleElements<>(
215
              mapSamples.e0().getValue(),
216
              mapSamples.e1().getValue(),
217
              mapSamples.e2().getValue(),
218
              mapSamples.e3().getValue(),
219
              mapSamples.e4().getValue());
220
    }
221

222
    @Override
223
    public SampleElements<V> samples() {
224
      return samples;
225
    }
226

227
    @Override
228
    public Collection<V> create(Object... elements) {
229
      @SuppressWarnings("unchecked")
230
      V[] valuesArray = (V[]) elements;
231

232
      // Start with a suitably shaped collection of entries
233
      Collection<Entry<K, V>> originalEntries = mapGenerator.getSampleElements(elements.length);
234

235
      // Create a copy of that, with the desired value for each value
236
      Collection<Entry<K, V>> entries = new ArrayList<>(elements.length);
237
      int i = 0;
238
      for (Entry<K, V> entry : originalEntries) {
239
        entries.add(Helpers.mapEntry(entry.getKey(), valuesArray[i++]));
240
      }
241

242
      return mapGenerator.create(entries.toArray()).values();
243
    }
244

245
    @Override
246
    public V[] createArray(int length) {
247
      // noinspection UnnecessaryLocalVariable
248
      V[] vs = ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).createValueArray(length);
249
      return vs;
250
    }
251

252
    @Override
253
    public Iterable<V> order(List<V> insertionOrder) {
254
      List<Entry<K, V>> orderedEntries =
255
          castOrCopyToList(mapGenerator.order(castOrCopyToList(mapGenerator.getSampleElements(5))));
256
      sort(
257
          insertionOrder,
258
          new Comparator<V>() {
259
            @Override
260
            public int compare(V left, V right) {
261
              // The indexes are small enough for the subtraction trick to be safe.
262
              return indexOfEntryWithValue(left) - indexOfEntryWithValue(right);
263
            }
264

265
            int indexOfEntryWithValue(V value) {
266
              for (int i = 0; i < orderedEntries.size(); i++) {
267
                if (equal(orderedEntries.get(i).getValue(), value)) {
268
                  return i;
269
                }
270
              }
271
              throw new IllegalArgumentException(
272
                  "Map.values generator can order only sample values");
273
            }
274
          });
275
      return insertionOrder;
276
    }
277

278
    @Override
279
    public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
280
      return mapGenerator;
281
    }
282
  }
283

284
  // TODO(cpovirk): could something like this be used elsewhere, e.g., ReserializedListGenerator?
285
  static class ForwardingTestMapGenerator<K extends @Nullable Object, V extends @Nullable Object>
286
      implements TestMapGenerator<K, V> {
287
    TestMapGenerator<K, V> delegate;
288

289
    ForwardingTestMapGenerator(TestMapGenerator<K, V> delegate) {
290
      this.delegate = delegate;
291
    }
292

293
    @Override
294
    public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
295
      return delegate.order(insertionOrder);
296
    }
297

298
    @Override
299
    public K[] createKeyArray(int length) {
300
      return delegate.createKeyArray(length);
301
    }
302

303
    @Override
304
    public V[] createValueArray(int length) {
305
      return delegate.createValueArray(length);
306
    }
307

308
    @Override
309
    public SampleElements<Entry<K, V>> samples() {
310
      return delegate.samples();
311
    }
312

313
    @Override
314
    public Map<K, V> create(Object... elements) {
315
      return delegate.create(elements);
316
    }
317

318
    @Override
319
    public Entry<K, V>[] createArray(int length) {
320
      return delegate.createArray(length);
321
    }
322
  }
323

324
  /** Two bounds (from and to) define how to build a subMap. */
325
  public enum Bound {
326
    INCLUSIVE,
327
    EXCLUSIVE,
328
    NO_BOUND;
329
  }
330

331
  public static class SortedSetSubsetTestSetGenerator<E extends @Nullable Object>
332
      implements TestSortedSetGenerator<E> {
333
    final Bound to;
334
    final Bound from;
335
    final E firstInclusive;
336
    final E lastInclusive;
337
    private final Comparator<? super E> comparator;
338
    private final TestSortedSetGenerator<E> delegate;
339

340
    public SortedSetSubsetTestSetGenerator(
341
        TestSortedSetGenerator<E> delegate, Bound to, Bound from) {
342
      this.to = to;
343
      this.from = from;
344
      this.delegate = delegate;
345

346
      SortedSet<E> emptySet = delegate.create();
347
      this.comparator = emptySet.comparator();
348

349
      SampleElements<E> samples = delegate.samples();
350
      List<E> samplesList = new ArrayList<>(samples.asList());
351
      Collections.sort(samplesList, comparator);
352
      this.firstInclusive = samplesList.get(0);
353
      this.lastInclusive = samplesList.get(samplesList.size() - 1);
354
    }
355

356
    public final TestSortedSetGenerator<E> getInnerGenerator() {
357
      return delegate;
358
    }
359

360
    public final Bound getTo() {
361
      return to;
362
    }
363

364
    public final Bound getFrom() {
365
      return from;
366
    }
367

368
    @Override
369
    public SampleElements<E> samples() {
370
      return delegate.samples();
371
    }
372

373
    @Override
374
    public E[] createArray(int length) {
375
      return delegate.createArray(length);
376
    }
377

378
    @Override
379
    public Iterable<E> order(List<E> insertionOrder) {
380
      return delegate.order(insertionOrder);
381
    }
382

383
    @Override
384
    public SortedSet<E> create(Object... elements) {
385
      List<?> normalValues = (List<?>) Arrays.asList(elements);
386
      List<E> extremeValues = new ArrayList<>();
387

388
      // nulls are usually out of bounds for a subset, so ban them altogether
389
      for (Object o : elements) {
390
        if (o == null) {
391
          throw new NullPointerException();
392
        }
393
      }
394

395
      // prepare extreme values to be filtered out of view
396
      E firstExclusive = delegate.belowSamplesGreater();
397
      E lastExclusive = delegate.aboveSamplesLesser();
398
      if (from != Bound.NO_BOUND) {
399
        extremeValues.add(delegate.belowSamplesLesser());
400
        extremeValues.add(delegate.belowSamplesGreater());
401
      }
402
      if (to != Bound.NO_BOUND) {
403
        extremeValues.add(delegate.aboveSamplesLesser());
404
        extremeValues.add(delegate.aboveSamplesGreater());
405
      }
406

407
      // the regular values should be visible after filtering
408
      List<@Nullable Object> allEntries = new ArrayList<>();
409
      allEntries.addAll(extremeValues);
410
      allEntries.addAll(normalValues);
411
      SortedSet<E> set = delegate.create(allEntries.toArray());
412

413
      return createSubSet(set, firstExclusive, lastExclusive);
414
    }
415

416
    /** Calls the smallest subSet overload that filters out the extreme values. */
417
    SortedSet<E> createSubSet(SortedSet<E> set, E firstExclusive, E lastExclusive) {
418
      if (from == Bound.NO_BOUND && to == Bound.EXCLUSIVE) {
419
        return set.headSet(lastExclusive);
420
      } else if (from == Bound.INCLUSIVE && to == Bound.NO_BOUND) {
421
        return set.tailSet(firstInclusive);
422
      } else if (from == Bound.INCLUSIVE && to == Bound.EXCLUSIVE) {
423
        return set.subSet(firstInclusive, lastExclusive);
424
      } else {
425
        throw new IllegalArgumentException();
426
      }
427
    }
428

429
    @Override
430
    public E belowSamplesLesser() {
431
      throw new UnsupportedOperationException();
432
    }
433

434
    @Override
435
    public E belowSamplesGreater() {
436
      throw new UnsupportedOperationException();
437
    }
438

439
    @Override
440
    public E aboveSamplesLesser() {
441
      throw new UnsupportedOperationException();
442
    }
443

444
    @Override
445
    public E aboveSamplesGreater() {
446
      throw new UnsupportedOperationException();
447
    }
448
  }
449

450
  /*
451
   * TODO(cpovirk): surely we can find a less ugly solution than a class that accepts 3 parameters,
452
   * exposes as many getters, does work in the constructor, and has both a superclass and a subclass
453
   */
454
  public static class SortedMapSubmapTestMapGenerator<
455
          K extends @Nullable Object, V extends @Nullable Object>
456
      extends ForwardingTestMapGenerator<K, V> implements TestSortedMapGenerator<K, V> {
457
    final Bound to;
458
    final Bound from;
459
    final K firstInclusive;
460
    final K lastInclusive;
461
    private final Comparator<Entry<K, V>> entryComparator;
462

463
    public SortedMapSubmapTestMapGenerator(
464
        TestSortedMapGenerator<K, V> delegate, Bound to, Bound from) {
465
      super(delegate);
466
      this.to = to;
467
      this.from = from;
468

469
      SortedMap<K, V> emptyMap = delegate.create();
470
      this.entryComparator = Helpers.entryComparator(emptyMap.comparator());
471

472
      // derive values for inclusive filtering from the input samples
473
      SampleElements<Entry<K, V>> samples = delegate.samples();
474
      List<Entry<K, V>> samplesList =
475
          Arrays.asList(samples.e0(), samples.e1(), samples.e2(), samples.e3(), samples.e4());
476
      Collections.sort(samplesList, entryComparator);
477
      this.firstInclusive = samplesList.get(0).getKey();
478
      this.lastInclusive = samplesList.get(samplesList.size() - 1).getKey();
479
    }
480

481
    @Override
482
    public SortedMap<K, V> create(Object... entries) {
483
      List<Entry<K, V>> extremeValues = new ArrayList<>();
484

485
      // prepare extreme values to be filtered out of view
486
      K firstExclusive = getInnerGenerator().belowSamplesGreater().getKey();
487
      K lastExclusive = getInnerGenerator().aboveSamplesLesser().getKey();
488
      if (from != Bound.NO_BOUND) {
489
        extremeValues.add(getInnerGenerator().belowSamplesLesser());
490
        extremeValues.add(getInnerGenerator().belowSamplesGreater());
491
      }
492
      if (to != Bound.NO_BOUND) {
493
        extremeValues.add(getInnerGenerator().aboveSamplesLesser());
494
        extremeValues.add(getInnerGenerator().aboveSamplesGreater());
495
      }
496

497
      // the regular values should be visible after filtering
498
      List<Entry<?, ?>> allEntries = new ArrayList<>();
499
      allEntries.addAll(extremeValues);
500
      for (Object entry : entries) {
501
        allEntries.add((Entry<?, ?>) entry);
502
      }
503
      SortedMap<K, V> map = (SortedMap<K, V>) delegate.create(allEntries.toArray());
504

505
      return createSubMap(map, firstExclusive, lastExclusive);
506
    }
507

508
    /**
509
     * Calls the smallest subMap overload that filters out the extreme values. This method is
510
     * overridden in NavigableMapTestSuiteBuilder.
511
     */
512
    SortedMap<K, V> createSubMap(SortedMap<K, V> map, K firstExclusive, K lastExclusive) {
513
      if (from == Bound.NO_BOUND && to == Bound.EXCLUSIVE) {
514
        return map.headMap(lastExclusive);
515
      } else if (from == Bound.INCLUSIVE && to == Bound.NO_BOUND) {
516
        return map.tailMap(firstInclusive);
517
      } else if (from == Bound.INCLUSIVE && to == Bound.EXCLUSIVE) {
518
        return map.subMap(firstInclusive, lastExclusive);
519
      } else {
520
        throw new IllegalArgumentException();
521
      }
522
    }
523

524
    public final Bound getTo() {
525
      return to;
526
    }
527

528
    public final Bound getFrom() {
529
      return from;
530
    }
531

532
    public final TestSortedMapGenerator<K, V> getInnerGenerator() {
533
      return (TestSortedMapGenerator<K, V>) delegate;
534
    }
535

536
    @Override
537
    public Entry<K, V> belowSamplesLesser() {
538
      // should never reach here!
539
      throw new UnsupportedOperationException();
540
    }
541

542
    @Override
543
    public Entry<K, V> belowSamplesGreater() {
544
      // should never reach here!
545
      throw new UnsupportedOperationException();
546
    }
547

548
    @Override
549
    public Entry<K, V> aboveSamplesLesser() {
550
      // should never reach here!
551
      throw new UnsupportedOperationException();
552
    }
553

554
    @Override
555
    public Entry<K, V> aboveSamplesGreater() {
556
      // should never reach here!
557
      throw new UnsupportedOperationException();
558
    }
559
  }
560

561
  private DerivedCollectionGenerators() {}
562
}
563