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