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}