Source code

001/*
002 * Copyright (C) 2008 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of 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,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect.testing;
018
019import static com.google.common.collect.testing.Helpers.castOrCopyToList;
020import static com.google.common.collect.testing.Helpers.entryComparator;
021import static com.google.common.collect.testing.Helpers.mapEntry;
022import static java.util.Arrays.asList;
023import static java.util.Collections.sort;
024import static java.util.Objects.requireNonNull;
025
026import com.google.common.annotations.GwtCompatible;
027import java.util.ArrayList;
028import java.util.Collection;
029import java.util.Comparator;
030import java.util.List;
031import java.util.Map;
032import java.util.Map.Entry;
033import java.util.Objects;
034import java.util.Set;
035import java.util.SortedMap;
036import java.util.SortedSet;
037import org.jspecify.annotations.NullMarked;
038import org.jspecify.annotations.Nullable;
039
040/**
041 * Derived suite generators, split out of the suite builders so that they are available to GWT.
042 *
043 * @author George van den Driessche
044 */
045@GwtCompatible
046@NullMarked
047public final class DerivedCollectionGenerators {
048  public static class MapEntrySetGenerator<K extends @Nullable Object, V extends @Nullable Object>
049      implements TestSetGenerator<Entry<K, V>>, DerivedGenerator {
050    private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
051
052    public MapEntrySetGenerator(
053        OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
054      this.mapGenerator = mapGenerator;
055    }
056
057    @Override
058    public SampleElements<Entry<K, V>> samples() {
059      return mapGenerator.samples();
060    }
061
062    @Override
063    public Set<Entry<K, V>> create(Object... elements) {
064      return mapGenerator.create(elements).entrySet();
065    }
066
067    @Override
068    public Entry<K, V>[] createArray(int length) {
069      return mapGenerator.createArray(length);
070    }
071
072    @Override
073    public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
074      return mapGenerator.order(insertionOrder);
075    }
076
077    @Override
078    public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
079      return mapGenerator;
080    }
081  }
082
083  // TODO: investigate some API changes to SampleElements that would tidy up
084  // parts of the following classes.
085
086  static <K extends @Nullable Object, V extends @Nullable Object>
087      TestSetGenerator<K> keySetGenerator(
088          OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
089    TestContainerGenerator<Map<K, V>, Entry<K, V>> generator = mapGenerator.getInnerGenerator();
090    if (generator instanceof TestSortedMapGenerator
091        && ((TestSortedMapGenerator<K, V>) generator).create().keySet() instanceof SortedSet) {
092      return new MapSortedKeySetGenerator<>(mapGenerator);
093    } else {
094      return new MapKeySetGenerator<>(mapGenerator);
095    }
096  }
097
098  public static class MapKeySetGenerator<K extends @Nullable Object, V extends @Nullable Object>
099      implements TestSetGenerator<K>, DerivedGenerator {
100    private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
101    private final SampleElements<K> samples;
102
103    public MapKeySetGenerator(OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
104      this.mapGenerator = mapGenerator;
105      SampleElements<Entry<K, V>> mapSamples = this.mapGenerator.samples();
106      this.samples =
107          new SampleElements<>(
108              mapSamples.e0().getKey(),
109              mapSamples.e1().getKey(),
110              mapSamples.e2().getKey(),
111              mapSamples.e3().getKey(),
112              mapSamples.e4().getKey());
113    }
114
115    @Override
116    public SampleElements<K> samples() {
117      return samples;
118    }
119
120    @Override
121    public Set<K> create(Object... elements) {
122      @SuppressWarnings("unchecked")
123      K[] keysArray = (K[]) elements;
124
125      // Start with a suitably shaped collection of entries
126      Collection<Entry<K, V>> originalEntries = mapGenerator.getSampleElements(elements.length);
127
128      // Create a copy of that, with the desired value for each key
129      Collection<Entry<K, V>> entries = new ArrayList<>(elements.length);
130      int i = 0;
131      for (Entry<K, V> entry : originalEntries) {
132        entries.add(mapEntry(keysArray[i++], entry.getValue()));
133      }
134
135      return mapGenerator.create(entries.toArray()).keySet();
136    }
137
138    @Override
139    public K[] createArray(int length) {
140      // TODO: with appropriate refactoring of OneSizeGenerator, we can perhaps
141      // tidy this up and get rid of the casts here and in
142      // MapValueCollectionGenerator.
143
144      return ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).createKeyArray(length);
145    }
146
147    @Override
148    public Iterable<K> order(List<K> insertionOrder) {
149      V v = mapGenerator.getInnerGenerator().samples().e0().getValue();
150      List<Entry<K, V>> entries = new ArrayList<>();
151      for (K element : insertionOrder) {
152        entries.add(mapEntry(element, v));
153      }
154
155      List<K> keys = new ArrayList<>();
156      for (Entry<K, V> entry : mapGenerator.order(entries)) {
157        keys.add(entry.getKey());
158      }
159      return keys;
160    }
161
162    @Override
163    public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
164      return mapGenerator;
165    }
166  }
167
168  public static class MapSortedKeySetGenerator<
169          K extends @Nullable Object, V extends @Nullable Object>
170      extends MapKeySetGenerator<K, V> implements TestSortedSetGenerator<K> {
171    private final TestSortedMapGenerator<K, V> delegate;
172
173    public MapSortedKeySetGenerator(
174        OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
175      super(mapGenerator);
176      this.delegate = (TestSortedMapGenerator<K, V>) mapGenerator.getInnerGenerator();
177    }
178
179    @Override
180    public SortedSet<K> create(Object... elements) {
181      return (SortedSet<K>) super.create(elements);
182    }
183
184    @Override
185    public K belowSamplesLesser() {
186      return delegate.belowSamplesLesser().getKey();
187    }
188
189    @Override
190    public K belowSamplesGreater() {
191      return delegate.belowSamplesGreater().getKey();
192    }
193
194    @Override
195    public K aboveSamplesLesser() {
196      return delegate.aboveSamplesLesser().getKey();
197    }
198
199    @Override
200    public K aboveSamplesGreater() {
201      return delegate.aboveSamplesGreater().getKey();
202    }
203  }
204
205  public static class MapValueCollectionGenerator<
206          K extends @Nullable Object, V extends @Nullable Object>
207      implements TestCollectionGenerator<V>, DerivedGenerator {
208    private final OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator;
209    private final SampleElements<V> samples;
210
211    public MapValueCollectionGenerator(
212        OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> mapGenerator) {
213      this.mapGenerator = mapGenerator;
214      SampleElements<Entry<K, V>> mapSamples = this.mapGenerator.samples();
215      this.samples =
216          new SampleElements<>(
217              mapSamples.e0().getValue(),
218              mapSamples.e1().getValue(),
219              mapSamples.e2().getValue(),
220              mapSamples.e3().getValue(),
221              mapSamples.e4().getValue());
222    }
223
224    @Override
225    public SampleElements<V> samples() {
226      return samples;
227    }
228
229    @Override
230    public Collection<V> create(Object... elements) {
231      @SuppressWarnings("unchecked")
232      V[] valuesArray = (V[]) elements;
233
234      // Start with a suitably shaped collection of entries
235      Collection<Entry<K, V>> originalEntries = mapGenerator.getSampleElements(elements.length);
236
237      // Create a copy of that, with the desired value for each value
238      Collection<Entry<K, V>> entries = new ArrayList<>(elements.length);
239      int i = 0;
240      for (Entry<K, V> entry : originalEntries) {
241        entries.add(mapEntry(entry.getKey(), valuesArray[i++]));
242      }
243
244      return mapGenerator.create(entries.toArray()).values();
245    }
246
247    @Override
248    public V[] createArray(int length) {
249      // noinspection UnnecessaryLocalVariable
250      V[] vs = ((TestMapGenerator<K, V>) mapGenerator.getInnerGenerator()).createValueArray(length);
251      return vs;
252    }
253
254    @Override
255    public Iterable<V> order(List<V> insertionOrder) {
256      List<Entry<K, V>> orderedEntries =
257          castOrCopyToList(mapGenerator.order(castOrCopyToList(mapGenerator.getSampleElements(5))));
258      sort(
259          insertionOrder,
260          new Comparator<V>() {
261            @Override
262            public int compare(V left, V right) {
263              // The indexes are small enough for the subtraction trick to be safe.
264              return indexOfEntryWithValue(left) - indexOfEntryWithValue(right);
265            }
266
267            int indexOfEntryWithValue(V value) {
268              for (int i = 0; i < orderedEntries.size(); i++) {
269                if (Objects.equals(orderedEntries.get(i).getValue(), value)) {
270                  return i;
271                }
272              }
273              throw new IllegalArgumentException(
274                  "Map.values generator can order only sample values");
275            }
276          });
277      return insertionOrder;
278    }
279
280    @Override
281    public OneSizeTestContainerGenerator<Map<K, V>, Entry<K, V>> getInnerGenerator() {
282      return mapGenerator;
283    }
284  }
285
286  // TODO(cpovirk): could something like this be used elsewhere, e.g., ReserializedListGenerator?
287  static class ForwardingTestMapGenerator<K extends @Nullable Object, V extends @Nullable Object>
288      implements TestMapGenerator<K, V> {
289    TestMapGenerator<K, V> delegate;
290
291    ForwardingTestMapGenerator(TestMapGenerator<K, V> delegate) {
292      this.delegate = delegate;
293    }
294
295    @Override
296    public Iterable<Entry<K, V>> order(List<Entry<K, V>> insertionOrder) {
297      return delegate.order(insertionOrder);
298    }
299
300    @Override
301    public K[] createKeyArray(int length) {
302      return delegate.createKeyArray(length);
303    }
304
305    @Override
306    public V[] createValueArray(int length) {
307      return delegate.createValueArray(length);
308    }
309
310    @Override
311    public SampleElements<Entry<K, V>> samples() {
312      return delegate.samples();
313    }
314
315    @Override
316    public Map<K, V> create(Object... elements) {
317      return delegate.create(elements);
318    }
319
320    @Override
321    public Entry<K, V>[] createArray(int length) {
322      return delegate.createArray(length);
323    }
324  }
325
326  /** Two bounds (from and to) define how to build a subMap. */
327  public enum Bound {
328    INCLUSIVE,
329    EXCLUSIVE,
330    NO_BOUND;
331  }
332
333  public static class SortedSetSubsetTestSetGenerator<E extends @Nullable Object>
334      implements TestSortedSetGenerator<E> {
335    final Bound to;
336    final Bound from;
337    final E firstInclusive;
338    final E lastInclusive;
339    private final @Nullable Comparator<? super E> comparator;
340    private final TestSortedSetGenerator<E> delegate;
341
342    public SortedSetSubsetTestSetGenerator(
343        TestSortedSetGenerator<E> delegate, Bound to, Bound from) {
344      this.to = to;
345      this.from = from;
346      this.delegate = delegate;
347
348      SortedSet<E> emptySet = delegate.create();
349      this.comparator = emptySet.comparator();
350
351      SampleElements<E> samples = delegate.samples();
352      List<E> samplesList = new ArrayList<>(samples.asList());
353      sort(samplesList, comparator);
354      this.firstInclusive = samplesList.get(0);
355      this.lastInclusive = samplesList.get(samplesList.size() - 1);
356    }
357
358    public final TestSortedSetGenerator<E> getInnerGenerator() {
359      return delegate;
360    }
361
362    public final Bound getTo() {
363      return to;
364    }
365
366    public final Bound getFrom() {
367      return from;
368    }
369
370    @Override
371    public SampleElements<E> samples() {
372      return delegate.samples();
373    }
374
375    @Override
376    public E[] createArray(int length) {
377      return delegate.createArray(length);
378    }
379
380    @Override
381    public Iterable<E> order(List<E> insertionOrder) {
382      return delegate.order(insertionOrder);
383    }
384
385    @Override
386    public SortedSet<E> create(Object... elements) {
387      List<?> normalValues = asList(elements);
388      List<E> extremeValues = new ArrayList<>();
389
390      // nulls are usually out of bounds for a subset, so ban them altogether
391      for (Object o : elements) {
392        requireNonNull(o);
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 @Nullable 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 = 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          asList(samples.e0(), samples.e1(), samples.e2(), samples.e3(), samples.e4());
476      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}