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