001/* 002 * Copyright (C) 2007 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; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021import static com.google.common.collect.CollectPreconditions.checkNonnegative; 022import static com.google.common.collect.ObjectArrays.checkElementNotNull; 023import static java.lang.Math.max; 024import static java.util.Objects.requireNonNull; 025 026import com.google.common.annotations.GwtCompatible; 027import com.google.common.annotations.J2ktIncompatible; 028import com.google.common.annotations.VisibleForTesting; 029import com.google.common.primitives.Ints; 030import com.google.errorprone.annotations.CanIgnoreReturnValue; 031import com.google.errorprone.annotations.concurrent.LazyInit; 032import com.google.j2objc.annotations.RetainedWith; 033import java.io.InvalidObjectException; 034import java.io.ObjectInputStream; 035import java.io.Serializable; 036import java.util.Arrays; 037import java.util.Collection; 038import java.util.Collections; 039import java.util.Iterator; 040import java.util.Set; 041import java.util.SortedSet; 042import java.util.stream.Collector; 043import org.jspecify.annotations.Nullable; 044 045/** 046 * A {@link Set} whose contents will never change, with many other important properties detailed at 047 * {@link ImmutableCollection}. 048 * 049 * @since 2.0 050 */ 051@GwtCompatible(serializable = true, emulated = true) 052@SuppressWarnings("serial") // we're overriding default serialization 053public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements Set<E> { 054 055 /** 056 * Returns a {@code Collector} that accumulates the input elements into a new {@code 057 * ImmutableSet}. Elements appear in the resulting set in the encounter order of the stream; if 058 * the stream contains duplicates (according to {@link Object#equals(Object)}), only the first 059 * duplicate in encounter order will appear in the result. 060 * 061 * @since 33.2.0 (available since 21.0 in guava-jre) 062 */ 063 @SuppressWarnings("Java7ApiChecker") 064 @IgnoreJRERequirement // Users will use this only if they're already using streams. 065 public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() { 066 return CollectCollectors.toImmutableSet(); 067 } 068 069 /** 070 * Returns the empty immutable set. Preferred over {@link Collections#emptySet} for code 071 * consistency, and because the return type conveys the immutability guarantee. 072 * 073 * <p><b>Performance note:</b> the instance returned is a singleton. 074 */ 075 @SuppressWarnings({"unchecked"}) // fully variant implementation (never actually produces any Es) 076 public static <E> ImmutableSet<E> of() { 077 return (ImmutableSet<E>) RegularImmutableSet.EMPTY; 078 } 079 080 /** 081 * Returns an immutable set containing the given element. Preferred over {@link 082 * Collections#singleton} for code consistency, {@code null} rejection, and because the return 083 * type conveys the immutability guarantee. 084 */ 085 public static <E> ImmutableSet<E> of(E e1) { 086 return new SingletonImmutableSet<>(e1); 087 } 088 089 /** 090 * Returns an immutable set containing the given elements, minus duplicates, in the order each was 091 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except 092 * the first are ignored. 093 */ 094 public static <E> ImmutableSet<E> of(E e1, E e2) { 095 return construct(2, e1, e2); 096 } 097 098 /** 099 * Returns an immutable set containing the given elements, minus duplicates, in the order each was 100 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except 101 * the first are ignored. 102 */ 103 public static <E> ImmutableSet<E> of(E e1, E e2, E e3) { 104 return construct(3, e1, e2, e3); 105 } 106 107 /** 108 * Returns an immutable set containing the given elements, minus duplicates, in the order each was 109 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except 110 * the first are ignored. 111 */ 112 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) { 113 return construct(4, e1, e2, e3, e4); 114 } 115 116 /** 117 * Returns an immutable set containing the given elements, minus duplicates, in the order each was 118 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except 119 * the first are ignored. 120 */ 121 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) { 122 return construct(5, e1, e2, e3, e4, e5); 123 } 124 125 /** 126 * Returns an immutable set containing the given elements, minus duplicates, in the order each was 127 * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except 128 * the first are ignored. 129 * 130 * <p>The array {@code others} must not be longer than {@code Integer.MAX_VALUE - 6}. 131 * 132 * @since 3.0 (source-compatible since 2.0) 133 */ 134 @SafeVarargs // For Eclipse. For internal javac we have disabled this pointless type of warning. 135 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) { 136 checkArgument( 137 others.length <= Integer.MAX_VALUE - 6, "the total number of elements must fit in an int"); 138 final int paramCount = 6; 139 Object[] elements = new Object[paramCount + others.length]; 140 elements[0] = e1; 141 elements[1] = e2; 142 elements[2] = e3; 143 elements[3] = e4; 144 elements[4] = e5; 145 elements[5] = e6; 146 System.arraycopy(others, 0, elements, paramCount, others.length); 147 return construct(elements.length, elements); 148 } 149 150 /** 151 * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array. If 152 * {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of {@code 153 * elements} will be in the first {@code k} positions, and {@code elements[i] == null} for {@code 154 * k <= i < n}. 155 * 156 * <p>After this method returns, {@code elements} will contain no duplicates, but {@code elements} 157 * may be the real array backing the returned set, so do not modify it further. 158 * 159 * <p>{@code elements} may contain only values of type {@code E}. 160 * 161 * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is null 162 */ 163 private static <E> ImmutableSet<E> construct(int n, @Nullable Object... elements) { 164 switch (n) { 165 case 0: 166 return of(); 167 case 1: 168 @SuppressWarnings("unchecked") // safe; elements contains only E's 169 // requireNonNull is safe because the first `n` elements are non-null. 170 E elem = (E) requireNonNull(elements[0]); 171 return of(elem); 172 default: 173 // continue below to handle the general case 174 } 175 int tableSize = chooseTableSize(n); 176 Object[] table = new Object[tableSize]; 177 int mask = tableSize - 1; 178 int hashCode = 0; 179 int uniques = 0; 180 for (int i = 0; i < n; i++) { 181 Object element = checkElementNotNull(elements[i], i); 182 int hash = element.hashCode(); 183 for (int j = Hashing.smear(hash); ; j++) { 184 int index = j & mask; 185 Object value = table[index]; 186 if (value == null) { 187 // Came to an empty slot. Put the element here. 188 elements[uniques++] = element; 189 table[index] = element; 190 hashCode += hash; 191 break; 192 } else if (value.equals(element)) { 193 break; 194 } 195 } 196 } 197 Arrays.fill(elements, uniques, n, null); 198 if (uniques == 1) { 199 // There is only one element or elements are all duplicates 200 @SuppressWarnings("unchecked") // we are careful to only pass in E 201 // requireNonNull is safe because the first `uniques` elements are non-null. 202 E element = (E) requireNonNull(elements[0]); 203 return new SingletonImmutableSet<E>(element); 204 } else if (chooseTableSize(uniques) < tableSize / 2) { 205 // Resize the table when the array includes too many duplicates. 206 return construct(uniques, elements); 207 } else { 208 @Nullable 209 Object[] uniqueElements = 210 shouldTrim(uniques, elements.length) ? Arrays.copyOf(elements, uniques) : elements; 211 return new RegularImmutableSet<E>(uniqueElements, hashCode, table, mask, uniques); 212 } 213 } 214 215 private static boolean shouldTrim(int actualUnique, int expectedUnique) { 216 return actualUnique < (expectedUnique >> 1) + (expectedUnique >> 2); 217 } 218 219 // We use power-of-2 tables, and this is the highest int that's a power of 2 220 static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO; 221 222 // Represents how tightly we can pack things, as a maximum. 223 private static final double DESIRED_LOAD_FACTOR = 0.7; 224 225 // If the set has this many elements, it will "max out" the table size 226 private static final int CUTOFF = (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR); 227 228 /** 229 * Returns an array size suitable for the backing array of a hash table that uses open addressing 230 * with linear probing in its implementation. The returned size is the smallest power of two that 231 * can hold setSize elements with the desired load factor. Always returns at least setSize + 2. 232 */ 233 @VisibleForTesting 234 static int chooseTableSize(int setSize) { 235 setSize = max(setSize, 2); 236 // Correct the size for open addressing to match desired load factor. 237 if (setSize < CUTOFF) { 238 // Round up to the next highest power of 2. 239 int tableSize = Integer.highestOneBit(setSize - 1) << 1; 240 while (tableSize * DESIRED_LOAD_FACTOR < setSize) { 241 tableSize <<= 1; 242 } 243 return tableSize; 244 } 245 246 // The table can't be completely full or we'll get infinite reprobes 247 checkArgument(setSize < MAX_TABLE_SIZE, "collection too large"); 248 return MAX_TABLE_SIZE; 249 } 250 251 /** 252 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order 253 * each appears first in the source collection. 254 * 255 * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation 256 * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} will copy the data only once. 257 * This reduces the expense of habitually making defensive copies at API boundaries. However, the 258 * precise conditions for skipping the copy operation are undefined. 259 * 260 * @throws NullPointerException if any of {@code elements} is null 261 * @since 7.0 (source-compatible since 2.0) 262 */ 263 // This the best we could do to get copyOfEnumSet to compile in the mainline. 264 // The suppression also covers the cast to E[], discussed below. 265 // In the backport, we don't have those cases and thus don't need this suppression. 266 // We keep it to minimize diffs. 267 @SuppressWarnings("unchecked") 268 public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) { 269 /* 270 * TODO(lowasser): consider checking for ImmutableAsList here 271 * TODO(lowasser): consider checking for Multiset here 272 */ 273 // Don't refer to ImmutableSortedSet by name so it won't pull in all that code 274 if (elements instanceof ImmutableSet && !(elements instanceof SortedSet)) { 275 @SuppressWarnings("unchecked") // all supported methods are covariant 276 ImmutableSet<E> set = (ImmutableSet<E>) elements; 277 if (!set.isPartialView()) { 278 return set; 279 } 280 } 281 Object[] array = elements.toArray(); 282 return construct(array.length, array); 283 } 284 285 /** 286 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order 287 * each appears first in the source iterable. This method iterates over {@code elements} only 288 * once. 289 * 290 * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation 291 * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} should copy the data only 292 * once. This reduces the expense of habitually making defensive copies at API boundaries. 293 * However, the precise conditions for skipping the copy operation are undefined. 294 * 295 * @throws NullPointerException if any of {@code elements} is null 296 */ 297 public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) { 298 return (elements instanceof Collection) 299 ? copyOf((Collection<? extends E>) elements) 300 : copyOf(elements.iterator()); 301 } 302 303 /** 304 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order 305 * each appears first in the source iterator. 306 * 307 * @throws NullPointerException if any of {@code elements} is null 308 */ 309 public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) { 310 // We special-case for 0 or 1 elements, but anything further is madness. 311 if (!elements.hasNext()) { 312 return of(); 313 } 314 E first = elements.next(); 315 if (!elements.hasNext()) { 316 return of(first); 317 } else { 318 return new ImmutableSet.Builder<E>().add(first).addAll(elements).build(); 319 } 320 } 321 322 /** 323 * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order 324 * each appears first in the source array. 325 * 326 * @throws NullPointerException if any of {@code elements} is null 327 * @since 3.0 328 */ 329 public static <E> ImmutableSet<E> copyOf(E[] elements) { 330 switch (elements.length) { 331 case 0: 332 return of(); 333 case 1: 334 return of(elements[0]); 335 default: 336 return construct(elements.length, elements.clone()); 337 } 338 } 339 340 ImmutableSet() {} 341 342 /** Returns {@code true} if the {@code hashCode()} method runs quickly. */ 343 boolean isHashCodeFast() { 344 return false; 345 } 346 347 @Override 348 public boolean equals(@Nullable Object object) { 349 if (object == this) { 350 return true; 351 } 352 if (object instanceof ImmutableSet 353 && isHashCodeFast() 354 && ((ImmutableSet<?>) object).isHashCodeFast() 355 && hashCode() != object.hashCode()) { 356 return false; 357 } 358 return Sets.equalsImpl(this, object); 359 } 360 361 @Override 362 public int hashCode() { 363 return Sets.hashCodeImpl(this); 364 } 365 366 // This declaration is needed to make Set.iterator() and 367 // ImmutableCollection.iterator() consistent. 368 @Override 369 public abstract UnmodifiableIterator<E> iterator(); 370 371 @LazyInit @RetainedWith private transient @Nullable ImmutableList<E> asList; 372 373 @Override 374 public ImmutableList<E> asList() { 375 ImmutableList<E> result = asList; 376 return (result == null) ? asList = createAsList() : result; 377 } 378 379 ImmutableList<E> createAsList() { 380 return ImmutableList.asImmutableList(toArray()); 381 } 382 383 /* 384 * This class is used to serialize all ImmutableSet instances, except for 385 * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It 386 * captures their "logical contents" and they are reconstructed using public 387 * static factories. This is necessary to ensure that the existence of a 388 * particular implementation type is an implementation detail. 389 */ 390 @J2ktIncompatible // serialization 391 private static class SerializedForm implements Serializable { 392 final Object[] elements; 393 394 SerializedForm(Object[] elements) { 395 this.elements = elements; 396 } 397 398 Object readResolve() { 399 return copyOf(elements); 400 } 401 402 private static final long serialVersionUID = 0; 403 } 404 405 @Override 406 @J2ktIncompatible // serialization 407 Object writeReplace() { 408 return new SerializedForm(toArray()); 409 } 410 411 @J2ktIncompatible // serialization 412 private void readObject(ObjectInputStream stream) throws InvalidObjectException { 413 throw new InvalidObjectException("Use SerializedForm"); 414 } 415 416 /** 417 * Returns a new builder. The generated builder is equivalent to the builder created by the {@link 418 * Builder} constructor. 419 */ 420 public static <E> Builder<E> builder() { 421 return new Builder<>(); 422 } 423 424 /** 425 * Returns a new builder, expecting the specified number of distinct elements to be added. 426 * 427 * <p>If {@code expectedSize} is exactly the number of distinct elements added to the builder 428 * before {@link Builder#build} is called, the builder is likely to perform better than an unsized 429 * {@link #builder()} would have. 430 * 431 * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to, 432 * but not exactly, the number of distinct elements added to the builder. 433 * 434 * @since 23.1 435 */ 436 public static <E> Builder<E> builderWithExpectedSize(int expectedSize) { 437 checkNonnegative(expectedSize, "expectedSize"); 438 return new Builder<>(expectedSize, true); 439 } 440 441 /** 442 * A builder for creating {@code ImmutableSet} instances. Example: 443 * 444 * <pre>{@code 445 * static final ImmutableSet<Color> GOOGLE_COLORS = 446 * ImmutableSet.<Color>builder() 447 * .addAll(WEBSAFE_COLORS) 448 * .add(new Color(0, 191, 255)) 449 * .build(); 450 * }</pre> 451 * 452 * <p>Elements appear in the resulting set in the same order they were first added to the builder. 453 * 454 * <p>Building does not change the state of the builder, so it is still possible to add more 455 * elements and to build again. 456 * 457 * @since 2.0 458 */ 459 public static class Builder<E> extends ImmutableCollection.ArrayBasedBuilder<E> { 460 @VisibleForTesting @Nullable Object @Nullable [] hashTable; 461 private int hashCode; 462 463 /** 464 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link 465 * ImmutableSet#builder}. 466 */ 467 public Builder() { 468 super(DEFAULT_INITIAL_CAPACITY); 469 } 470 471 Builder(int capacity, boolean makeHashTable) { 472 super(capacity); 473 if (makeHashTable) { 474 this.hashTable = new @Nullable Object[chooseTableSize(capacity)]; 475 } 476 } 477 478 /** 479 * Adds {@code element} to the {@code ImmutableSet}. If the {@code ImmutableSet} already 480 * contains {@code element}, then {@code add} has no effect (only the previously added element 481 * is retained). 482 * 483 * @param element the element to add 484 * @return this {@code Builder} object 485 * @throws NullPointerException if {@code element} is null 486 */ 487 @CanIgnoreReturnValue 488 @Override 489 public Builder<E> add(E element) { 490 checkNotNull(element); 491 if (hashTable != null && chooseTableSize(size) <= hashTable.length) { 492 addDeduping(element); 493 return this; 494 } else { 495 hashTable = null; 496 super.add(element); 497 return this; 498 } 499 } 500 501 /** 502 * Adds each element of {@code elements} to the {@code ImmutableSet}, ignoring duplicate 503 * elements (only the first duplicate element is added). 504 * 505 * @param elements the elements to add 506 * @return this {@code Builder} object 507 * @throws NullPointerException if {@code elements} is null or contains a null element 508 */ 509 @Override 510 @CanIgnoreReturnValue 511 public Builder<E> add(E... elements) { 512 if (hashTable != null) { 513 for (E e : elements) { 514 add(e); 515 } 516 } else { 517 super.add(elements); 518 } 519 return this; 520 } 521 522 private void addDeduping(E element) { 523 requireNonNull(hashTable); // safe because we check for null before calling this method 524 int mask = hashTable.length - 1; 525 int hash = element.hashCode(); 526 for (int i = Hashing.smear(hash); ; i++) { 527 i &= mask; 528 Object previous = hashTable[i]; 529 if (previous == null) { 530 hashTable[i] = element; 531 hashCode += hash; 532 super.add(element); 533 return; 534 } else if (previous.equals(element)) { 535 return; 536 } 537 } 538 } 539 540 /** 541 * Adds each element of {@code elements} to the {@code ImmutableSet}, ignoring duplicate 542 * elements (only the first duplicate element is added). 543 * 544 * @param elements the {@code Iterable} to add to the {@code ImmutableSet} 545 * @return this {@code Builder} object 546 * @throws NullPointerException if {@code elements} is null or contains a null element 547 */ 548 @CanIgnoreReturnValue 549 @Override 550 public Builder<E> addAll(Iterable<? extends E> elements) { 551 checkNotNull(elements); 552 if (hashTable != null) { 553 for (E e : elements) { 554 add(e); 555 } 556 } else { 557 super.addAll(elements); 558 } 559 return this; 560 } 561 562 /** 563 * Adds each element of {@code elements} to the {@code ImmutableSet}, ignoring duplicate 564 * elements (only the first duplicate element is added). 565 * 566 * @param elements the elements to add to the {@code ImmutableSet} 567 * @return this {@code Builder} object 568 * @throws NullPointerException if {@code elements} is null or contains a null element 569 */ 570 @CanIgnoreReturnValue 571 @Override 572 public Builder<E> addAll(Iterator<? extends E> elements) { 573 checkNotNull(elements); 574 while (elements.hasNext()) { 575 add(elements.next()); 576 } 577 return this; 578 } 579 580 @CanIgnoreReturnValue 581 @SuppressWarnings("unchecked") // ArrayBasedBuilder stores its elements as Object. 582 Builder<E> combine(Builder<E> other) { 583 if (hashTable != null) { 584 for (int i = 0; i < other.size; ++i) { 585 // requireNonNull is safe because the first `size` elements are non-null. 586 add((E) requireNonNull(other.contents[i])); 587 } 588 } else { 589 addAll(other.contents, other.size); 590 } 591 return this; 592 } 593 594 /** 595 * Returns a newly-created {@code ImmutableSet} based on the contents of the {@code Builder}. 596 */ 597 @SuppressWarnings("unchecked") 598 @Override 599 public ImmutableSet<E> build() { 600 switch (size) { 601 case 0: 602 return of(); 603 case 1: 604 /* 605 * requireNonNull is safe because we ensure that the first `size` elements have been 606 * populated. 607 */ 608 return (ImmutableSet<E>) of(requireNonNull(contents[0])); 609 default: 610 ImmutableSet<E> result; 611 if (hashTable != null && chooseTableSize(size) == hashTable.length) { 612 @Nullable 613 Object[] uniqueElements = 614 shouldTrim(size, contents.length) ? Arrays.copyOf(contents, size) : contents; 615 result = 616 new RegularImmutableSet<E>( 617 uniqueElements, hashCode, hashTable, hashTable.length - 1, size); 618 } else { 619 result = construct(size, contents); 620 // construct has the side effect of deduping contents, so we update size 621 // accordingly. 622 size = result.size(); 623 } 624 forceCopy = true; 625 hashTable = null; 626 return result; 627 } 628 } 629 } 630 631 private static final long serialVersionUID = 0xdecaf; 632}