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.google;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.collect.Lists.newArrayList;
021import static com.google.common.collect.Sets.newHashSet;
022import static com.google.common.collect.Sets.newTreeSet;
023import static com.google.common.collect.testing.SampleElements.Strings.AFTER_LAST;
024import static com.google.common.collect.testing.SampleElements.Strings.AFTER_LAST_2;
025import static com.google.common.collect.testing.SampleElements.Strings.BEFORE_FIRST;
026import static com.google.common.collect.testing.SampleElements.Strings.BEFORE_FIRST_2;
027import static java.lang.Math.max;
028import static java.util.Arrays.asList;
029import static java.util.Collections.sort;
030import static junit.framework.Assert.assertEquals;
031
032import com.google.common.annotations.GwtCompatible;
033import com.google.common.annotations.GwtIncompatible;
034import com.google.common.collect.ContiguousSet;
035import com.google.common.collect.DiscreteDomain;
036import com.google.common.collect.ImmutableSet;
037import com.google.common.collect.ImmutableSortedSet;
038import com.google.common.collect.Lists;
039import com.google.common.collect.Ordering;
040import com.google.common.collect.Range;
041import com.google.common.collect.Sets;
042import com.google.common.collect.testing.TestCollidingSetGenerator;
043import com.google.common.collect.testing.TestIntegerSortedSetGenerator;
044import com.google.common.collect.testing.TestSetGenerator;
045import com.google.common.collect.testing.TestStringListGenerator;
046import com.google.common.collect.testing.TestStringSetGenerator;
047import com.google.common.collect.testing.TestStringSortedSetGenerator;
048import com.google.common.collect.testing.TestUnhashableCollectionGenerator;
049import com.google.common.collect.testing.UnhashableObject;
050import java.util.Collections;
051import java.util.Comparator;
052import java.util.List;
053import java.util.Set;
054import java.util.SortedSet;
055import org.jspecify.annotations.NullMarked;
056
057/**
058 * Generators of different types of sets and derived collections from sets.
059 *
060 * @author Kevin Bourrillion
061 * @author Jared Levy
062 * @author Hayward Chan
063 */
064@GwtCompatible(emulated = true)
065@NullMarked
066public class SetGenerators {
067
068  public static class ImmutableSetCopyOfGenerator extends TestStringSetGenerator {
069    @Override
070    protected Set<String> create(String[] elements) {
071      return ImmutableSet.copyOf(elements);
072    }
073  }
074
075  public static class ImmutableSetUnsizedBuilderGenerator extends TestStringSetGenerator {
076    @Override
077    protected Set<String> create(String[] elements) {
078      ImmutableSet.Builder<String> builder = ImmutableSet.builder();
079      for (String e : elements) {
080        builder.add(e);
081      }
082      return builder.build();
083    }
084  }
085
086  public static class ImmutableSetSizedBuilderGenerator extends TestStringSetGenerator {
087    @Override
088    protected Set<String> create(String[] elements) {
089      ImmutableSet.Builder<String> builder =
090          ImmutableSet.builderWithExpectedSize(newHashSet(elements).size());
091      for (String e : elements) {
092        builder.add(e);
093      }
094      return builder.build();
095    }
096  }
097
098  public static class ImmutableSetTooBigBuilderGenerator extends TestStringSetGenerator {
099    @Override
100    protected Set<String> create(String[] elements) {
101      ImmutableSet.Builder<String> builder =
102          ImmutableSet.builderWithExpectedSize(newHashSet(elements).size() + 1);
103      for (String e : elements) {
104        builder.add(e);
105      }
106      return builder.build();
107    }
108  }
109
110  public static class ImmutableSetTooSmallBuilderGenerator extends TestStringSetGenerator {
111    @Override
112    protected Set<String> create(String[] elements) {
113      ImmutableSet.Builder<String> builder =
114          ImmutableSet.builderWithExpectedSize(max(0, newHashSet(elements).size() - 1));
115      for (String e : elements) {
116        builder.add(e);
117      }
118      return builder.build();
119    }
120  }
121
122  public static class ImmutableSetWithBadHashesGenerator extends TestCollidingSetGenerator {
123    @Override
124    public Set<Object> create(Object... elements) {
125      return ImmutableSet.copyOf(elements);
126    }
127  }
128
129  public static class DegeneratedImmutableSetGenerator extends TestStringSetGenerator {
130    @SuppressWarnings("DistinctVarargsChecker") // deliberately testing deduplication
131    @Override
132    protected Set<String> create(String[] elements) {
133      return ImmutableSet.of(elements[0], elements[0]);
134    }
135  }
136
137  public static class ImmutableSortedSetCopyOfGenerator extends TestStringSortedSetGenerator {
138    @Override
139    protected SortedSet<String> create(String[] elements) {
140      return ImmutableSortedSet.copyOf(elements);
141    }
142  }
143
144  public static class ImmutableSortedSetHeadsetGenerator extends TestStringSortedSetGenerator {
145    @Override
146    protected SortedSet<String> create(String[] elements) {
147      List<String> list = Lists.newArrayList(elements);
148      list.add("zzz");
149      return ImmutableSortedSet.copyOf(list).headSet("zzy");
150    }
151  }
152
153  public static class ImmutableSortedSetTailsetGenerator extends TestStringSortedSetGenerator {
154    @Override
155    protected SortedSet<String> create(String[] elements) {
156      List<String> list = Lists.newArrayList(elements);
157      list.add("\0");
158      return ImmutableSortedSet.copyOf(list).tailSet("\0\0");
159    }
160  }
161
162  public static class ImmutableSortedSetSubsetGenerator extends TestStringSortedSetGenerator {
163    @Override
164    protected SortedSet<String> create(String[] elements) {
165      List<String> list = Lists.newArrayList(elements);
166      list.add("\0");
167      list.add("zzz");
168      return ImmutableSortedSet.copyOf(list).subSet("\0\0", "zzy");
169    }
170  }
171
172  @GwtIncompatible // NavigableSet
173  public static class ImmutableSortedSetDescendingGenerator extends TestStringSortedSetGenerator {
174    @Override
175    protected SortedSet<String> create(String[] elements) {
176      return ImmutableSortedSet.<String>reverseOrder().add(elements).build().descendingSet();
177    }
178  }
179
180  public static class ImmutableSortedSetExplicitComparator extends TestStringSetGenerator {
181
182    private static final Comparator<String> STRING_REVERSED = Collections.reverseOrder();
183
184    @Override
185    protected SortedSet<String> create(String[] elements) {
186      return ImmutableSortedSet.orderedBy(STRING_REVERSED).add(elements).build();
187    }
188
189    /*
190     * While the current implementation returns `this`, that's not something we mean to guarantee.
191     * Callers of TestContainerGenerator.order need to be prepared for implementations to return a new
192     * collection.
193     */
194    @SuppressWarnings("CanIgnoreReturnValueSuggester")
195    @Override
196    public List<String> order(List<String> insertionOrder) {
197      sort(insertionOrder, Collections.reverseOrder());
198      return insertionOrder;
199    }
200  }
201
202  public static class ImmutableSortedSetExplicitSuperclassComparatorGenerator
203      extends TestStringSetGenerator {
204
205    private static final Comparator<Comparable<?>> COMPARABLE_REVERSED = Collections.reverseOrder();
206
207    @Override
208    protected SortedSet<String> create(String[] elements) {
209      return new ImmutableSortedSet.Builder<String>(COMPARABLE_REVERSED).add(elements).build();
210    }
211
212    @SuppressWarnings("CanIgnoreReturnValueSuggester") // see ImmutableSortedSetExplicitComparator
213    @Override
214    public List<String> order(List<String> insertionOrder) {
215      sort(insertionOrder, Collections.reverseOrder());
216      return insertionOrder;
217    }
218  }
219
220  public static class ImmutableSortedSetReversedOrderGenerator extends TestStringSetGenerator {
221
222    @Override
223    protected SortedSet<String> create(String[] elements) {
224      return ImmutableSortedSet.<String>reverseOrder().addAll(asList(elements).iterator()).build();
225    }
226
227    @SuppressWarnings("CanIgnoreReturnValueSuggester") // see ImmutableSortedSetExplicitComparator
228    @Override
229    public List<String> order(List<String> insertionOrder) {
230      sort(insertionOrder, Collections.reverseOrder());
231      return insertionOrder;
232    }
233  }
234
235  public static class ImmutableSortedSetUnhashableGenerator extends TestUnhashableSetGenerator {
236    @Override
237    public Set<UnhashableObject> create(UnhashableObject[] elements) {
238      return ImmutableSortedSet.copyOf(elements);
239    }
240  }
241
242  public static class ImmutableSetAsListGenerator extends TestStringListGenerator {
243    @Override
244    protected List<String> create(String[] elements) {
245      return ImmutableSet.copyOf(elements).asList();
246    }
247  }
248
249  public static class ImmutableSortedSetAsListGenerator extends TestStringListGenerator {
250    @Override
251    protected List<String> create(String[] elements) {
252      Comparator<String> comparator = createExplicitComparator(elements);
253      ImmutableSet<String> set = ImmutableSortedSet.copyOf(comparator, asList(elements));
254      return set.asList();
255    }
256  }
257
258  public static class ImmutableSortedSetSubsetAsListGenerator extends TestStringListGenerator {
259    @Override
260    protected List<String> create(String[] elements) {
261      Comparator<String> comparator = createExplicitComparator(elements);
262      ImmutableSortedSet.Builder<String> builder = ImmutableSortedSet.orderedBy(comparator);
263      builder.add(BEFORE_FIRST);
264      builder.add(elements);
265      builder.add(AFTER_LAST);
266      return builder.build().subSet(BEFORE_FIRST_2, AFTER_LAST).asList();
267    }
268  }
269
270  @GwtIncompatible // NavigableSet
271  public static class ImmutableSortedSetDescendingAsListGenerator extends TestStringListGenerator {
272    @Override
273    protected List<String> create(String[] elements) {
274      Comparator<String> comparator = createExplicitComparator(elements).reverse();
275      return ImmutableSortedSet.orderedBy(comparator)
276          .add(elements)
277          .build()
278          .descendingSet()
279          .asList();
280    }
281  }
282
283  public static class ImmutableSortedSetAsListSubListGenerator extends TestStringListGenerator {
284    @Override
285    protected List<String> create(String[] elements) {
286      Comparator<String> comparator = createExplicitComparator(elements);
287      ImmutableSortedSet.Builder<String> builder = ImmutableSortedSet.orderedBy(comparator);
288      builder.add(BEFORE_FIRST);
289      builder.add(elements);
290      builder.add(AFTER_LAST);
291      return builder.build().asList().subList(1, elements.length + 1);
292    }
293  }
294
295  public static class ImmutableSortedSetSubsetAsListSubListGenerator
296      extends TestStringListGenerator {
297    @Override
298    protected List<String> create(String[] elements) {
299      Comparator<String> comparator = createExplicitComparator(elements);
300      ImmutableSortedSet.Builder<String> builder = ImmutableSortedSet.orderedBy(comparator);
301      builder.add(BEFORE_FIRST);
302      builder.add(BEFORE_FIRST_2);
303      builder.add(elements);
304      builder.add(AFTER_LAST);
305      builder.add(AFTER_LAST_2);
306      return builder
307          .build()
308          .subSet(BEFORE_FIRST_2, AFTER_LAST_2)
309          .asList()
310          .subList(1, elements.length + 1);
311    }
312  }
313
314  public abstract static class TestUnhashableSetGenerator
315      extends TestUnhashableCollectionGenerator<Set<UnhashableObject>>
316      implements TestSetGenerator<UnhashableObject> {}
317
318  private static Ordering<String> createExplicitComparator(String[] elements) {
319    // Collapse equal elements, which Ordering.explicit() doesn't support, while
320    // maintaining the ordering by first occurrence.
321    Set<String> elementsPlus = Sets.newLinkedHashSet();
322    elementsPlus.add(BEFORE_FIRST);
323    elementsPlus.add(BEFORE_FIRST_2);
324    elementsPlus.addAll(asList(elements));
325    elementsPlus.add(AFTER_LAST);
326    elementsPlus.add(AFTER_LAST_2);
327    return Ordering.explicit(Lists.newArrayList(elementsPlus));
328  }
329
330  /*
331   * All the ContiguousSet generators below manually reject nulls here. In principle, we'd like to
332   * defer that to Range, since it's ContiguousSet.create() that's used to create the sets. However,
333   * that gets messy here, and we already have null tests for Range.
334   */
335
336  /*
337   * These generators also rely on consecutive integer inputs (not necessarily in order, but no
338   * holes).
339   */
340
341  // SetCreationTester has some tests that pass in duplicates. Dedup them.
342  private static <E extends Comparable<? super E>> SortedSet<E> nullCheckedTreeSet(E[] elements) {
343    SortedSet<E> set = newTreeSet();
344    for (E element : elements) {
345      // Explicit null check because TreeSet wrongly accepts add(null) when empty.
346      set.add(checkNotNull(element));
347    }
348    return set;
349  }
350
351  public static class ContiguousSetGenerator extends AbstractContiguousSetGenerator {
352    @Override
353    protected SortedSet<Integer> create(Integer[] elements) {
354      return checkedCreate(nullCheckedTreeSet(elements));
355    }
356  }
357
358  public static class ContiguousSetHeadsetGenerator extends AbstractContiguousSetGenerator {
359    @Override
360    protected SortedSet<Integer> create(Integer[] elements) {
361      SortedSet<Integer> set = nullCheckedTreeSet(elements);
362      int tooHigh = set.isEmpty() ? 0 : set.last() + 1;
363      set.add(tooHigh);
364      return checkedCreate(set).headSet(tooHigh);
365    }
366  }
367
368  public static class ContiguousSetTailsetGenerator extends AbstractContiguousSetGenerator {
369    @Override
370    protected SortedSet<Integer> create(Integer[] elements) {
371      SortedSet<Integer> set = nullCheckedTreeSet(elements);
372      int tooLow = set.isEmpty() ? 0 : set.first() - 1;
373      set.add(tooLow);
374      return checkedCreate(set).tailSet(tooLow + 1);
375    }
376  }
377
378  public static class ContiguousSetSubsetGenerator extends AbstractContiguousSetGenerator {
379    @Override
380    protected SortedSet<Integer> create(Integer[] elements) {
381      SortedSet<Integer> set = nullCheckedTreeSet(elements);
382      if (set.isEmpty()) {
383        /*
384         * The (tooLow + 1, tooHigh) arguments below would be invalid because tooLow would be
385         * greater than tooHigh.
386         */
387        return ContiguousSet.create(Range.openClosed(0, 1), DiscreteDomain.integers()).subSet(0, 1);
388      }
389      int tooHigh = set.last() + 1;
390      int tooLow = set.first() - 1;
391      set.add(tooHigh);
392      set.add(tooLow);
393      return checkedCreate(set).subSet(tooLow + 1, tooHigh);
394    }
395  }
396
397  @GwtIncompatible // NavigableSet
398  public static class ContiguousSetDescendingGenerator extends AbstractContiguousSetGenerator {
399    @Override
400    protected SortedSet<Integer> create(Integer[] elements) {
401      return checkedCreate(nullCheckedTreeSet(elements)).descendingSet();
402    }
403
404    /** Sorts the elements in reverse natural order. */
405    @SuppressWarnings("CanIgnoreReturnValueSuggester") // see ImmutableSortedSetExplicitComparator
406    @Override
407    public List<Integer> order(List<Integer> insertionOrder) {
408      sort(insertionOrder, Ordering.<Integer>natural().reverse());
409      return insertionOrder;
410    }
411  }
412
413  private abstract static class AbstractContiguousSetGenerator
414      extends TestIntegerSortedSetGenerator {
415    protected final ContiguousSet<Integer> checkedCreate(SortedSet<Integer> elementsSet) {
416      List<Integer> elements = newArrayList(elementsSet);
417      /*
418       * A ContiguousSet can't have holes. If a test demands a hole, it should be changed so that it
419       * doesn't need one, or it should be suppressed for ContiguousSet.
420       */
421      for (int i = 0; i < elements.size() - 1; i++) {
422        assertEquals(elements.get(i) + 1, (int) elements.get(i + 1));
423      }
424      Range<Integer> range =
425          elements.isEmpty() ? Range.closedOpen(0, 0) : Range.encloseAll(elements);
426      return ContiguousSet.create(range, DiscreteDomain.integers());
427    }
428  }
429}