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