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}