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