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