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