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