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 java.util.Objects.requireNonNull;
023
024import com.google.common.annotations.Beta;
025import com.google.common.annotations.GwtCompatible;
026import com.google.common.annotations.VisibleForTesting;
027import com.google.common.math.IntMath;
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.math.RoundingMode;
036import java.util.Arrays;
037import java.util.Collection;
038import java.util.Collections;
039import java.util.EnumSet;
040import java.util.Iterator;
041import java.util.Set;
042import java.util.SortedSet;
043import java.util.Spliterator;
044import java.util.function.Consumer;
045import java.util.stream.Collector;
046import javax.annotation.CheckForNull;
047import org.checkerframework.checker.nullness.qual.Nullable;
048
049/**
050 * A {@link Set} whose contents will never change, with many other important properties detailed at
051 * {@link ImmutableCollection}.
052 *
053 * @since 2.0
054 */
055@GwtCompatible(serializable = true, emulated = true)
056@SuppressWarnings("serial") // we're overriding default serialization
057@ElementTypesAreNonnullByDefault
058public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements Set<E> {
059  static final int SPLITERATOR_CHARACTERISTICS =
060      ImmutableCollection.SPLITERATOR_CHARACTERISTICS | Spliterator.DISTINCT;
061
062  /**
063   * Returns a {@code Collector} that accumulates the input elements into a new {@code
064   * ImmutableSet}. Elements appear in the resulting set in the encounter order of the stream; if
065   * the stream contains duplicates (according to {@link Object#equals(Object)}), only the first
066   * duplicate in encounter order will appear in the result.
067   *
068   * @since 21.0
069   */
070  public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() {
071    return CollectCollectors.toImmutableSet();
072  }
073
074  /**
075   * Returns the empty immutable set. Preferred over {@link Collections#emptySet} for code
076   * consistency, and because the return type conveys the immutability guarantee.
077   *
078   * <p><b>Performance note:</b> the instance returned is a singleton.
079   */
080  @SuppressWarnings({"unchecked"}) // fully variant implementation (never actually produces any Es)
081  public static <E> ImmutableSet<E> of() {
082    return (ImmutableSet<E>) RegularImmutableSet.EMPTY;
083  }
084
085  /**
086   * Returns an immutable set containing {@code element}. Preferred over {@link
087   * Collections#singleton} for code consistency, {@code null} rejection, and because the return
088   * type conveys the immutability guarantee.
089   */
090  public static <E> ImmutableSet<E> of(E element) {
091    return new SingletonImmutableSet<E>(element);
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) {
100    return construct(2, 2, e1, e2);
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  public static <E> ImmutableSet<E> of(E e1, E e2, E e3) {
109    return construct(3, 3, e1, e2, e3);
110  }
111
112  /**
113   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
114   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
115   * the first are ignored.
116   */
117  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) {
118    return construct(4, 4, e1, e2, e3, e4);
119  }
120
121  /**
122   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
123   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
124   * the first are ignored.
125   */
126  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) {
127    return construct(5, 5, e1, e2, e3, e4, e5);
128  }
129
130  /**
131   * Returns an immutable set containing the given elements, minus duplicates, in the order each was
132   * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
133   * the first are ignored.
134   *
135   * <p>The array {@code others} must not be longer than {@code Integer.MAX_VALUE - 6}.
136   *
137   * @since 3.0 (source-compatible since 2.0)
138   */
139  @SafeVarargs // For Eclipse. For internal javac we have disabled this pointless type of warning.
140  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
141    checkArgument(
142        others.length <= Integer.MAX_VALUE - 6, "the total number of elements must fit in an int");
143    final int paramCount = 6;
144    Object[] elements = new Object[paramCount + others.length];
145    elements[0] = e1;
146    elements[1] = e2;
147    elements[2] = e3;
148    elements[3] = e4;
149    elements[4] = e5;
150    elements[5] = e6;
151    System.arraycopy(others, 0, elements, paramCount, others.length);
152    return construct(elements.length, elements.length, elements);
153  }
154
155  /**
156   * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array,
157   * which we have no particular reason to believe does or does not contain duplicates. If {@code k}
158   * is the size of the returned {@code ImmutableSet}, then the unique elements of {@code elements}
159   * will be in the first {@code k} positions, and {@code elements[i] == null} for {@code k <= i <
160   * n}.
161   *
162   * <p>This may modify {@code elements}. Additionally, if {@code n == elements.length} and {@code
163   * elements} contains no duplicates, {@code elements} may be used without copying in the returned
164   * {@code ImmutableSet}, in which case the caller must not modify it.
165   *
166   * <p>{@code elements} may contain only values of type {@code E}.
167   *
168   * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is null
169   */
170  private static <E> ImmutableSet<E> constructUnknownDuplication(int n, Object... elements) {
171    // Guess the size is "halfway between" all duplicates and no duplicates, on a log scale.
172    return construct(
173        n,
174        Math.max(
175            ImmutableCollection.Builder.DEFAULT_INITIAL_CAPACITY,
176            IntMath.sqrt(n, RoundingMode.CEILING)),
177        elements);
178  }
179
180  /**
181   * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array. If
182   * {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of {@code
183   * elements} will be in the first {@code k} positions, and {@code elements[i] == null} for {@code
184   * k <= i < n}.
185   *
186   * <p>This may modify {@code elements}. Additionally, if {@code n == elements.length} and {@code
187   * elements} contains no duplicates, {@code elements} may be used without copying in the returned
188   * {@code ImmutableSet}, in which case it may no longer be modified.
189   *
190   * <p>{@code elements} may contain only values of type {@code E}.
191   *
192   * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is null
193   */
194  private static <E> ImmutableSet<E> construct(int n, int expectedSize, Object... elements) {
195    switch (n) {
196      case 0:
197        return of();
198      case 1:
199        @SuppressWarnings("unchecked") // safe; elements contains only E's
200        E elem = (E) elements[0];
201        return of(elem);
202      default:
203        SetBuilderImpl<E> builder = new RegularSetBuilderImpl<E>(expectedSize);
204        for (int i = 0; i < n; i++) {
205          @SuppressWarnings("unchecked")
206          E e = (E) checkNotNull(elements[i]);
207          builder = builder.add(e);
208        }
209        return builder.review().build();
210    }
211  }
212
213  /**
214   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
215   * each appears first in the source collection.
216   *
217   * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation
218   * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} will copy the data only once.
219   * This reduces the expense of habitually making defensive copies at API boundaries. However, the
220   * precise conditions for skipping the copy operation are undefined.
221   *
222   * @throws NullPointerException if any of {@code elements} is null
223   * @since 7.0 (source-compatible since 2.0)
224   */
225  public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) {
226    /*
227     * TODO(lowasser): consider checking for ImmutableAsList here
228     * TODO(lowasser): consider checking for Multiset here
229     */
230    // Don't refer to ImmutableSortedSet by name so it won't pull in all that code
231    if (elements instanceof ImmutableSet && !(elements instanceof SortedSet)) {
232      @SuppressWarnings("unchecked") // all supported methods are covariant
233      ImmutableSet<E> set = (ImmutableSet<E>) elements;
234      if (!set.isPartialView()) {
235        return set;
236      }
237    } else if (elements instanceof EnumSet) {
238      return copyOfEnumSet((EnumSet) elements);
239    }
240    Object[] array = elements.toArray();
241    if (elements instanceof Set) {
242      // assume probably no duplicates (though it might be using different equality semantics)
243      return construct(array.length, array.length, array);
244    } else {
245      return constructUnknownDuplication(array.length, array);
246    }
247  }
248
249  /**
250   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
251   * each appears first in the source iterable. This method iterates over {@code elements} only
252   * once.
253   *
254   * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation
255   * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} should copy the data only
256   * once. This reduces the expense of habitually making defensive copies at API boundaries.
257   * However, the precise conditions for skipping the copy operation are undefined.
258   *
259   * @throws NullPointerException if any of {@code elements} is null
260   */
261  public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) {
262    return (elements instanceof Collection)
263        ? copyOf((Collection<? extends E>) elements)
264        : copyOf(elements.iterator());
265  }
266
267  /**
268   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
269   * each appears first in the source iterator.
270   *
271   * @throws NullPointerException if any of {@code elements} is null
272   */
273  public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) {
274    // We special-case for 0 or 1 elements, but anything further is madness.
275    if (!elements.hasNext()) {
276      return of();
277    }
278    E first = elements.next();
279    if (!elements.hasNext()) {
280      return of(first);
281    } else {
282      return new ImmutableSet.Builder<E>().add(first).addAll(elements).build();
283    }
284  }
285
286  /**
287   * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
288   * each appears first in the source array.
289   *
290   * @throws NullPointerException if any of {@code elements} is null
291   * @since 3.0
292   */
293  public static <E> ImmutableSet<E> copyOf(E[] elements) {
294    switch (elements.length) {
295      case 0:
296        return of();
297      case 1:
298        return of(elements[0]);
299      default:
300        return constructUnknownDuplication(elements.length, elements.clone());
301    }
302  }
303
304  @SuppressWarnings("rawtypes") // necessary to compile against Java 8
305  private static ImmutableSet copyOfEnumSet(EnumSet enumSet) {
306    return ImmutableEnumSet.asImmutable(EnumSet.copyOf(enumSet));
307  }
308
309  ImmutableSet() {}
310
311  /** Returns {@code true} if the {@code hashCode()} method runs quickly. */
312  boolean isHashCodeFast() {
313    return false;
314  }
315
316  @Override
317  public boolean equals(@CheckForNull Object object) {
318    if (object == this) {
319      return true;
320    }
321    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  @GwtCompatible
341  abstract static class CachingAsList<E> extends ImmutableSet<E> {
342    @LazyInit @RetainedWith @CheckForNull private transient ImmutableList<E> asList;
343
344    @Override
345    public ImmutableList<E> asList() {
346      ImmutableList<E> result = asList;
347      if (result == null) {
348        return asList = createAsList();
349      } else {
350        return result;
351      }
352    }
353
354    ImmutableList<E> createAsList() {
355      return new RegularImmutableAsList<E>(this, toArray());
356    }
357  }
358
359  abstract static class Indexed<E> extends CachingAsList<E> {
360    abstract E get(int index);
361
362    @Override
363    public UnmodifiableIterator<E> iterator() {
364      return asList().iterator();
365    }
366
367    @Override
368    public Spliterator<E> spliterator() {
369      return CollectSpliterators.indexed(size(), SPLITERATOR_CHARACTERISTICS, this::get);
370    }
371
372    @Override
373    public void forEach(Consumer<? super E> consumer) {
374      checkNotNull(consumer);
375      int n = size();
376      for (int i = 0; i < n; i++) {
377        consumer.accept(get(i));
378      }
379    }
380
381    @Override
382    int copyIntoArray(@Nullable Object[] dst, int offset) {
383      return asList().copyIntoArray(dst, offset);
384    }
385
386    @Override
387    ImmutableList<E> createAsList() {
388      return new ImmutableAsList<E>() {
389        @Override
390        public E get(int index) {
391          return Indexed.this.get(index);
392        }
393
394        @Override
395        Indexed<E> delegateCollection() {
396          return Indexed.this;
397        }
398      };
399    }
400  }
401
402  /*
403   * This class is used to serialize all ImmutableSet instances, except for
404   * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
405   * captures their "logical contents" and they are reconstructed using public
406   * static factories. This is necessary to ensure that the existence of a
407   * particular implementation type is an implementation detail.
408   */
409  private static class SerializedForm implements Serializable {
410    final Object[] elements;
411
412    SerializedForm(Object[] elements) {
413      this.elements = elements;
414    }
415
416    Object readResolve() {
417      return copyOf(elements);
418    }
419
420    private static final long serialVersionUID = 0;
421  }
422
423  @Override
424  Object writeReplace() {
425    return new SerializedForm(toArray());
426  }
427
428  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
429    throw new InvalidObjectException("Use SerializedForm");
430  }
431
432  /**
433   * Returns a new builder. The generated builder is equivalent to the builder created by the {@link
434   * Builder} constructor.
435   */
436  public static <E> Builder<E> builder() {
437    return new Builder<E>();
438  }
439
440  /**
441   * Returns a new builder, expecting the specified number of distinct elements to be added.
442   *
443   * <p>If {@code expectedSize} is exactly the number of distinct elements added to the builder
444   * before {@link Builder#build} is called, the builder is likely to perform better than an unsized
445   * {@link #builder()} would have.
446   *
447   * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
448   * but not exactly, the number of distinct elements added to the builder.
449   *
450   * @since 23.1
451   */
452  @Beta
453  public static <E> Builder<E> builderWithExpectedSize(int expectedSize) {
454    checkNonnegative(expectedSize, "expectedSize");
455    return new Builder<E>(expectedSize);
456  }
457
458  /**
459   * A builder for creating {@code ImmutableSet} instances. Example:
460   *
461   * <pre>{@code
462   * static final ImmutableSet<Color> GOOGLE_COLORS =
463   *     ImmutableSet.<Color>builder()
464   *         .addAll(WEBSAFE_COLORS)
465   *         .add(new Color(0, 191, 255))
466   *         .build();
467   * }</pre>
468   *
469   * <p>Elements appear in the resulting set in the same order they were first added to the builder.
470   *
471   * <p>Building does not change the state of the builder, so it is still possible to add more
472   * elements and to build again.
473   *
474   * @since 2.0
475   */
476  public static class Builder<E> extends ImmutableCollection.Builder<E> {
477    /*
478     * `impl` is null only for instances of the subclass, ImmutableSortedSet.Builder. That subclass
479     * overrides all the methods that access it here. Thus, all the methods here can safely assume
480     * that this field is non-null.
481     */
482    @CheckForNull private SetBuilderImpl<E> impl;
483    boolean forceCopy;
484
485    public Builder() {
486      this(0);
487    }
488
489    Builder(int capacity) {
490      if (capacity > 0) {
491        impl = new RegularSetBuilderImpl<E>(capacity);
492      } else {
493        impl = EmptySetBuilderImpl.instance();
494      }
495    }
496
497    Builder(@SuppressWarnings("unused") boolean subclass) {
498      this.impl = null; // unused
499    }
500
501    @VisibleForTesting
502    void forceJdk() {
503      requireNonNull(impl); // see the comment on the field
504      this.impl = new JdkBackedSetBuilderImpl<E>(impl);
505    }
506
507    final void copyIfNecessary() {
508      if (forceCopy) {
509        copy();
510        forceCopy = false;
511      }
512    }
513
514    void copy() {
515      requireNonNull(impl); // see the comment on the field
516      impl = impl.copy();
517    }
518
519    @Override
520    @CanIgnoreReturnValue
521    public Builder<E> add(E element) {
522      requireNonNull(impl); // see the comment on the field
523      checkNotNull(element);
524      copyIfNecessary();
525      impl = impl.add(element);
526      return this;
527    }
528
529    @Override
530    @CanIgnoreReturnValue
531    public Builder<E> add(E... elements) {
532      super.add(elements);
533      return this;
534    }
535
536    /**
537     * Adds each element of {@code elements} to the {@code ImmutableSet}, ignoring duplicate
538     * elements (only the first duplicate element is added).
539     *
540     * @param elements the elements to add
541     * @return this {@code Builder} object
542     * @throws NullPointerException if {@code elements} is null or contains a null element
543     */
544    @Override
545    @CanIgnoreReturnValue
546    public Builder<E> addAll(Iterable<? extends E> elements) {
547      super.addAll(elements);
548      return this;
549    }
550
551    @Override
552    @CanIgnoreReturnValue
553    public Builder<E> addAll(Iterator<? extends E> elements) {
554      super.addAll(elements);
555      return this;
556    }
557
558    Builder<E> combine(Builder<E> other) {
559      requireNonNull(impl);
560      requireNonNull(other.impl);
561      /*
562       * For discussion of requireNonNull, see the comment on the field.
563       *
564       * (And I don't believe there's any situation in which we call x.combine(y) when x is a plain
565       * ImmutableSet.Builder but y is an ImmutableSortedSet.Builder (or vice versa). Certainly
566       * ImmutableSortedSet.Builder.combine() is written as if its argument will never be a plain
567       * ImmutableSet.Builder: It casts immediately to ImmutableSortedSet.Builder.)
568       */
569      copyIfNecessary();
570      this.impl = this.impl.combine(other.impl);
571      return this;
572    }
573
574    @Override
575    public ImmutableSet<E> build() {
576      requireNonNull(impl); // see the comment on the field
577      forceCopy = true;
578      impl = impl.review();
579      return impl.build();
580    }
581  }
582
583  /** Swappable internal implementation of an ImmutableSet.Builder. */
584  private abstract static class SetBuilderImpl<E> {
585    // The first `distinct` elements are non-null.
586    // Since we can never access null elements, we don't mark this nullable.
587    E[] dedupedElements;
588    int distinct;
589
590    @SuppressWarnings("unchecked")
591    SetBuilderImpl(int expectedCapacity) {
592      this.dedupedElements = (E[]) new Object[expectedCapacity];
593      this.distinct = 0;
594    }
595
596    /** Initializes this SetBuilderImpl with a copy of the deduped elements array from toCopy. */
597    SetBuilderImpl(SetBuilderImpl<E> toCopy) {
598      this.dedupedElements = Arrays.copyOf(toCopy.dedupedElements, toCopy.dedupedElements.length);
599      this.distinct = toCopy.distinct;
600    }
601
602    /**
603     * Resizes internal data structures if necessary to store the specified number of distinct
604     * elements.
605     */
606    private void ensureCapacity(int minCapacity) {
607      if (minCapacity > dedupedElements.length) {
608        int newCapacity =
609            ImmutableCollection.Builder.expandedCapacity(dedupedElements.length, minCapacity);
610        dedupedElements = Arrays.copyOf(dedupedElements, newCapacity);
611      }
612    }
613
614    /** Adds e to the insertion-order array of deduplicated elements. Calls ensureCapacity. */
615    final void addDedupedElement(E e) {
616      ensureCapacity(distinct + 1);
617      dedupedElements[distinct++] = e;
618    }
619
620    /**
621     * Adds e to this SetBuilderImpl, returning the updated result. Only use the returned
622     * SetBuilderImpl, since we may switch implementations if e.g. hash flooding is detected.
623     */
624    abstract SetBuilderImpl<E> add(E e);
625
626    /** Adds all the elements from the specified SetBuilderImpl to this SetBuilderImpl. */
627    final SetBuilderImpl<E> combine(SetBuilderImpl<E> other) {
628      SetBuilderImpl<E> result = this;
629      for (int i = 0; i < other.distinct; i++) {
630        /*
631         * requireNonNull is safe because we ensure that the first `distinct` elements have been
632         * populated.
633         */
634        result = result.add(requireNonNull(other.dedupedElements[i]));
635      }
636      return result;
637    }
638
639    /**
640     * Creates a new copy of this SetBuilderImpl. Modifications to that SetBuilderImpl will not
641     * affect this SetBuilderImpl or sets constructed from this SetBuilderImpl via build().
642     */
643    abstract SetBuilderImpl<E> copy();
644
645    /**
646     * Call this before build(). Does a final check on the internal data structures, e.g. shrinking
647     * unnecessarily large structures or detecting previously unnoticed hash flooding.
648     */
649    SetBuilderImpl<E> review() {
650      return this;
651    }
652
653    abstract ImmutableSet<E> build();
654  }
655
656  private static final class EmptySetBuilderImpl<E> extends SetBuilderImpl<E> {
657    private static final EmptySetBuilderImpl<Object> INSTANCE = new EmptySetBuilderImpl<>();
658
659    @SuppressWarnings("unchecked")
660    static <E> SetBuilderImpl<E> instance() {
661      return (SetBuilderImpl<E>) INSTANCE;
662    }
663
664    private EmptySetBuilderImpl() {
665      super(0);
666    }
667
668    @Override
669    SetBuilderImpl<E> add(E e) {
670      return new RegularSetBuilderImpl<E>(Builder.DEFAULT_INITIAL_CAPACITY).add(e);
671    }
672
673    @Override
674    SetBuilderImpl<E> copy() {
675      return this;
676    }
677
678    @Override
679    ImmutableSet<E> build() {
680      return ImmutableSet.of();
681    }
682  }
683
684  // We use power-of-2 tables, and this is the highest int that's a power of 2
685  static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO;
686
687  // Represents how tightly we can pack things, as a maximum.
688  private static final double DESIRED_LOAD_FACTOR = 0.7;
689
690  // If the set has this many elements, it will "max out" the table size
691  private static final int CUTOFF = (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR);
692
693  /**
694   * Returns an array size suitable for the backing array of a hash table that uses open addressing
695   * with linear probing in its implementation. The returned size is the smallest power of two that
696   * can hold setSize elements with the desired load factor. Always returns at least setSize + 2.
697   */
698  // TODO(cpovirk): Move to Hashing or something, since it's used elsewhere in the Android version.
699  static int chooseTableSize(int setSize) {
700    setSize = Math.max(setSize, 2);
701    // Correct the size for open addressing to match desired load factor.
702    if (setSize < CUTOFF) {
703      // Round up to the next highest power of 2.
704      int tableSize = Integer.highestOneBit(setSize - 1) << 1;
705      while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
706        tableSize <<= 1;
707      }
708      return tableSize;
709    }
710
711    // The table can't be completely full or we'll get infinite reprobes
712    checkArgument(setSize < MAX_TABLE_SIZE, "collection too large");
713    return MAX_TABLE_SIZE;
714  }
715
716  /**
717   * Default implementation of the guts of ImmutableSet.Builder, creating an open-addressed hash
718   * table and deduplicating elements as they come, so it only allocates O(max(distinct,
719   * expectedCapacity)) rather than O(calls to add).
720   *
721   * <p>This implementation attempts to detect hash flooding, and if it's identified, falls back to
722   * JdkBackedSetBuilderImpl.
723   */
724  private static final class RegularSetBuilderImpl<E> extends SetBuilderImpl<E> {
725    // null until at least two elements are present
726    private @Nullable Object @Nullable [] hashTable;
727    private int maxRunBeforeFallback;
728    private int expandTableThreshold;
729    private int hashCode;
730
731    RegularSetBuilderImpl(int expectedCapacity) {
732      super(expectedCapacity);
733      this.hashTable = null;
734      this.maxRunBeforeFallback = 0;
735      this.expandTableThreshold = 0;
736    }
737
738    RegularSetBuilderImpl(RegularSetBuilderImpl<E> toCopy) {
739      super(toCopy);
740      this.hashTable = (toCopy.hashTable == null) ? null : toCopy.hashTable.clone();
741      this.maxRunBeforeFallback = toCopy.maxRunBeforeFallback;
742      this.expandTableThreshold = toCopy.expandTableThreshold;
743      this.hashCode = toCopy.hashCode;
744    }
745
746    @Override
747    SetBuilderImpl<E> add(E e) {
748      checkNotNull(e);
749      if (hashTable == null) {
750        if (distinct == 0) {
751          addDedupedElement(e);
752          return this;
753        } else {
754          ensureTableCapacity(dedupedElements.length);
755          E elem = dedupedElements[0];
756          distinct--;
757          return insertInHashTable(elem).add(e);
758        }
759      }
760      return insertInHashTable(e);
761    }
762
763    private SetBuilderImpl<E> insertInHashTable(E e) {
764      requireNonNull(hashTable);
765      int eHash = e.hashCode();
766      int i0 = Hashing.smear(eHash);
767      int mask = hashTable.length - 1;
768      for (int i = i0; i - i0 < maxRunBeforeFallback; i++) {
769        int index = i & mask;
770        Object tableEntry = hashTable[index];
771        if (tableEntry == null) {
772          addDedupedElement(e);
773          hashTable[index] = e;
774          hashCode += eHash;
775          ensureTableCapacity(distinct); // rebuilds table if necessary
776          return this;
777        } else if (tableEntry.equals(e)) { // not a new element, ignore
778          return this;
779        }
780      }
781      // we fell out of the loop due to a long run; fall back to JDK impl
782      return new JdkBackedSetBuilderImpl<E>(this).add(e);
783    }
784
785    @Override
786    SetBuilderImpl<E> copy() {
787      return new RegularSetBuilderImpl<E>(this);
788    }
789
790    @Override
791    SetBuilderImpl<E> review() {
792      if (hashTable == null) {
793        return this;
794      }
795      int targetTableSize = chooseTableSize(distinct);
796      if (targetTableSize * 2 < hashTable.length) {
797        hashTable = rebuildHashTable(targetTableSize, dedupedElements, distinct);
798        maxRunBeforeFallback = maxRunBeforeFallback(targetTableSize);
799        expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * targetTableSize);
800      }
801      return hashFloodingDetected(hashTable) ? new JdkBackedSetBuilderImpl<E>(this) : this;
802    }
803
804    @Override
805    ImmutableSet<E> build() {
806      switch (distinct) {
807        case 0:
808          return of();
809        case 1:
810          /*
811           * requireNonNull is safe because we ensure that the first `distinct` elements have been
812           * populated.
813           */
814          return of(requireNonNull(dedupedElements[0]));
815        default:
816          /*
817           * The suppression is safe because we ensure that the first `distinct` elements have been
818           * populated.
819           */
820          @SuppressWarnings("nullness")
821          Object[] elements =
822              (distinct == dedupedElements.length)
823                  ? dedupedElements
824                  : Arrays.copyOf(dedupedElements, distinct);
825          return new RegularImmutableSet<E>(
826              elements, hashCode, requireNonNull(hashTable), hashTable.length - 1);
827      }
828    }
829
830    /** Builds a new open-addressed hash table from the first n objects in elements. */
831    static @Nullable Object[] rebuildHashTable(int newTableSize, Object[] elements, int n) {
832      @Nullable Object[] hashTable = new @Nullable Object[newTableSize];
833      int mask = hashTable.length - 1;
834      for (int i = 0; i < n; i++) {
835        // requireNonNull is safe because we ensure that the first n elements have been populated.
836        Object e = requireNonNull(elements[i]);
837        int j0 = Hashing.smear(e.hashCode());
838        for (int j = j0; ; j++) {
839          int index = j & mask;
840          if (hashTable[index] == null) {
841            hashTable[index] = e;
842            break;
843          }
844        }
845      }
846      return hashTable;
847    }
848
849    void ensureTableCapacity(int minCapacity) {
850      int newTableSize;
851      if (hashTable == null) {
852        newTableSize = chooseTableSize(minCapacity);
853        hashTable = new Object[newTableSize];
854      } else if (minCapacity > expandTableThreshold && hashTable.length < MAX_TABLE_SIZE) {
855        newTableSize = hashTable.length * 2;
856        hashTable = rebuildHashTable(newTableSize, dedupedElements, distinct);
857      } else {
858        return;
859      }
860      maxRunBeforeFallback = maxRunBeforeFallback(newTableSize);
861      expandTableThreshold = (int) (DESIRED_LOAD_FACTOR * newTableSize);
862    }
863
864    /**
865     * We attempt to detect deliberate hash flooding attempts. If one is detected, we fall back to a
866     * wrapper around j.u.HashSet, which has built in flooding protection. MAX_RUN_MULTIPLIER was
867     * determined experimentally to match our desired probability of false positives.
868     */
869    // NB: yes, this is surprisingly high, but that's what the experiments said was necessary
870    // Raising this number slows the worst-case contains behavior, speeds up hashFloodingDetected,
871    // and reduces the false-positive probability.
872    static final int MAX_RUN_MULTIPLIER = 13;
873
874    /**
875     * Checks the whole hash table for poor hash distribution. Takes O(n) in the worst case, O(n /
876     * log n) on average.
877     *
878     * <p>The online hash flooding detecting in RegularSetBuilderImpl.add can detect e.g. many
879     * exactly matching hash codes, which would cause construction to take O(n^2), but can't detect
880     * e.g. hash codes adversarially designed to go into ascending table locations, which keeps
881     * construction O(n) (as desired) but then can have O(n) queries later.
882     *
883     * <p>If this returns false, then no query can take more than O(log n).
884     *
885     * <p>Note that for a RegularImmutableSet with elements with truly random hash codes, contains
886     * operations take expected O(1) time but with high probability take O(log n) for at least some
887     * element. (https://en.wikipedia.org/wiki/Linear_probing#Analysis)
888     *
889     * <p>This method may return {@code true} even on truly random input, but {@code
890     * ImmutableSetTest} tests that the probability of that is low.
891     */
892    static boolean hashFloodingDetected(@Nullable Object[] hashTable) {
893      int maxRunBeforeFallback = maxRunBeforeFallback(hashTable.length);
894      int mask = hashTable.length - 1;
895
896      // Invariant: all elements at indices in [knownRunStart, knownRunEnd) are nonnull.
897      // If knownRunStart == knownRunEnd, this is vacuously true.
898      // When knownRunEnd exceeds hashTable.length, it "wraps", detecting runs around the end
899      // of the table.
900      int knownRunStart = 0;
901      int knownRunEnd = 0;
902
903      outerLoop:
904      while (knownRunStart < hashTable.length) {
905        if (knownRunStart == knownRunEnd && hashTable[knownRunStart] == null) {
906          if (hashTable[(knownRunStart + maxRunBeforeFallback - 1) & mask] == null) {
907            // There are only maxRunBeforeFallback - 1 elements between here and there,
908            // so even if they were all nonnull, we wouldn't detect a hash flood.  Therefore,
909            // we can skip them all.
910            knownRunStart += maxRunBeforeFallback;
911          } else {
912            knownRunStart++; // the only case in which maxRunEnd doesn't increase by mRBF
913            // happens about f * (1-f) for f = DESIRED_LOAD_FACTOR, so around 21% of the time
914          }
915          knownRunEnd = knownRunStart;
916        } else {
917          for (int j = knownRunStart + maxRunBeforeFallback - 1; j >= knownRunEnd; j--) {
918            if (hashTable[j & mask] == null) {
919              knownRunEnd = knownRunStart + maxRunBeforeFallback;
920              knownRunStart = j + 1;
921              continue outerLoop;
922            }
923          }
924          return true;
925        }
926      }
927      return false;
928    }
929
930    /**
931     * If more than this many consecutive positions are filled in a table of the specified size,
932     * report probable hash flooding. ({@link #hashFloodingDetected} may also report hash flooding
933     * if fewer consecutive positions are filled; see that method for details.)
934     */
935    static int maxRunBeforeFallback(int tableSize) {
936      return MAX_RUN_MULTIPLIER * IntMath.log2(tableSize, RoundingMode.UNNECESSARY);
937    }
938  }
939
940  /**
941   * SetBuilderImpl version that uses a JDK HashSet, which has built in hash flooding protection.
942   */
943  private static final class JdkBackedSetBuilderImpl<E> extends SetBuilderImpl<E> {
944    private final Set<Object> delegate;
945
946    JdkBackedSetBuilderImpl(SetBuilderImpl<E> toCopy) {
947      super(toCopy); // initializes dedupedElements and distinct
948      delegate = Sets.newHashSetWithExpectedSize(distinct);
949      for (int i = 0; i < distinct; i++) {
950        /*
951         * requireNonNull is safe because we ensure that the first `distinct` elements have been
952         * populated.
953         */
954        delegate.add(requireNonNull(dedupedElements[i]));
955      }
956    }
957
958    @Override
959    SetBuilderImpl<E> add(E e) {
960      checkNotNull(e);
961      if (delegate.add(e)) {
962        addDedupedElement(e);
963      }
964      return this;
965    }
966
967    @Override
968    SetBuilderImpl<E> copy() {
969      return new JdkBackedSetBuilderImpl<>(this);
970    }
971
972    @Override
973    ImmutableSet<E> build() {
974      switch (distinct) {
975        case 0:
976          return of();
977        case 1:
978          /*
979           * requireNonNull is safe because we ensure that the first `distinct` elements have been
980           * populated.
981           */
982          return of(requireNonNull(dedupedElements[0]));
983        default:
984          return new JdkBackedImmutableSet<E>(
985              delegate, ImmutableList.asImmutableList(dedupedElements, distinct));
986      }
987    }
988  }
989}