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