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