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