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;
025
026import java.io.Serializable;
027import java.util.Arrays;
028import java.util.Collection;
029import java.util.Collections;
030import java.util.EnumSet;
031import java.util.HashSet;
032import java.util.Iterator;
033import java.util.Set;
034
035import javax.annotation.Nullable;
036
037/**
038 * A high-performance, immutable {@code Set} with reliable, user-specified
039 * iteration order. Does not permit null elements.
040 *
041 * <p>Unlike {@link Collections#unmodifiableSet}, which is a <i>view</i> of a
042 * separate collection that can still change, an instance of this class contains
043 * its own private data and will <i>never</i> change. This class is convenient
044 * for {@code public static final} sets ("constant sets") and also lets you
045 * easily make a "defensive copy" of a set provided to your class by a caller.
046 *
047 * <p><b>Warning:</b> Like most sets, an {@code ImmutableSet} will not function
048 * correctly if an element is modified after being placed in the set. For this
049 * reason, and to avoid general confusion, it is strongly recommended to place
050 * only immutable objects into this collection.
051 *
052 * <p>This class has been observed to perform significantly better than {@link
053 * HashSet} for objects with very fast {@link Object#hashCode} implementations
054 * (as a well-behaved immutable object should). While this class's factory
055 * methods create hash-based instances, the {@link ImmutableSortedSet} subclass
056 * performs binary searches instead.
057 *
058 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed
059 * outside its package as it has no public or protected constructors. Thus,
060 * instances of this type are guaranteed to be immutable.
061 *
062 * <p>See the Guava User Guide article on <a href=
063 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
064 * immutable collections</a>.
065 *
066 * @see ImmutableList
067 * @see ImmutableMap
068 * @author Kevin Bourrillion
069 * @author Nick Kralevich
070 * @since 2.0 (imported from Google Collections Library)
071 */
072@GwtCompatible(serializable = true, emulated = true)
073@SuppressWarnings("serial") // we're overriding default serialization
074public abstract class ImmutableSet<E> extends ImmutableCollection<E>
075    implements Set<E> {
076  /**
077   * Returns the empty immutable set. This set behaves and performs comparably
078   * to {@link Collections#emptySet}, and is preferable mainly for consistency
079   * and maintainability of your code.
080   */
081  // Casting to any type is safe because the set will never hold any elements.
082  @SuppressWarnings({"unchecked"})
083  public static <E> ImmutableSet<E> of() {
084    return (ImmutableSet<E>) EmptyImmutableSet.INSTANCE;
085  }
086
087  /**
088   * Returns an immutable set containing a single element. This set behaves and
089   * performs comparably to {@link Collections#singleton}, but will not accept
090   * a null element. It is preferable mainly for consistency and
091   * maintainability of your code.
092   */
093  public static <E> ImmutableSet<E> of(E element) {
094    return new SingletonImmutableSet<E>(element);
095  }
096
097  /**
098   * Returns an immutable set containing the given elements, in order. Repeated
099   * occurrences of an element (according to {@link Object#equals}) after the
100   * first are ignored.
101   *
102   * @throws NullPointerException if any element is null
103   */
104  public static <E> ImmutableSet<E> of(E e1, E e2) {
105    return construct(2, e1, e2);
106  }
107
108  /**
109   * Returns an immutable set containing the given elements, in order. Repeated
110   * occurrences of an element (according to {@link Object#equals}) after the
111   * first are ignored.
112   *
113   * @throws NullPointerException if any element is null
114   */
115  public static <E> ImmutableSet<E> of(E e1, E e2, E e3) {
116    return construct(3, e1, e2, e3);
117  }
118
119  /**
120   * Returns an immutable set containing the given elements, in order. Repeated
121   * occurrences of an element (according to {@link Object#equals}) after the
122   * first are ignored.
123   *
124   * @throws NullPointerException if any element is null
125   */
126  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) {
127    return construct(4, e1, e2, e3, e4);
128  }
129
130  /**
131   * Returns an immutable set containing the given elements, in order. Repeated
132   * occurrences of an element (according to {@link Object#equals}) after the
133   * first are ignored.
134   *
135   * @throws NullPointerException if any element is null
136   */
137  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) {
138    return construct(5, e1, e2, e3, e4, e5);
139  }
140
141  /**
142   * Returns an immutable set containing the given elements, in order. Repeated
143   * occurrences of an element (according to {@link Object#equals}) after the
144   * first are ignored.
145   *
146   * @throws NullPointerException if any element is null
147   * @since 3.0 (source-compatible since 2.0)
148   */
149  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6,
150      E... others) {
151    final int paramCount = 6;
152    Object[] elements = new Object[paramCount + others.length];
153    elements[0] = e1;
154    elements[1] = e2;
155    elements[2] = e3;
156    elements[3] = e4;
157    elements[4] = e5;
158    elements[5] = e6;
159    System.arraycopy(others, 0, elements, paramCount, others.length);
160    return construct(elements.length, elements);
161  }
162
163  /**
164   * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array.
165   * If {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of
166   * {@code elements} will be in the first {@code k} positions, and {@code elements[i] == null} for
167   * {@code k <= i < n}.
168   *
169   * <p>This may modify {@code elements}.  Additionally, if {@code n == elements.length} and
170   * {@code elements} contains no duplicates, {@code elements} may be used without copying in the
171   * returned {@code ImmutableSet}, in which case it may no longer be modified.
172   *
173   * <p>{@code elements} may contain only values of type {@code E}.
174   *
175   * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is
176   *          null
177   */
178  private static <E> ImmutableSet<E> construct(int n, Object... elements) {
179    switch (n) {
180      case 0:
181        return of();
182      case 1:
183        @SuppressWarnings("unchecked") // safe; elements contains only E's
184        E elem = (E) elements[0];
185        return of(elem);
186      default:
187        // continue below to handle the general case
188    }
189    int tableSize = chooseTableSize(n);
190    Object[] table = new Object[tableSize];
191    int mask = tableSize - 1;
192    int hashCode = 0;
193    int uniques = 0;
194    for (int i = 0; i < n; i++) {
195      Object element = checkElementNotNull(elements[i], i);
196      int hash = element.hashCode();
197      for (int j = Hashing.smear(hash); ; j++) {
198        int index = j & mask;
199        Object value = table[index];
200        if (value == null) {
201          // Came to an empty slot. Put the element here.
202          elements[uniques++] = element;
203          table[index] = element;
204          hashCode += hash;
205          break;
206        } else if (value.equals(element)) {
207          break;
208        }
209      }
210    }
211    Arrays.fill(elements, uniques, n, null);
212    if (uniques == 1) {
213      // There is only one element or elements are all duplicates
214      @SuppressWarnings("unchecked") // we are careful to only pass in E
215      E element = (E) elements[0];
216      return new SingletonImmutableSet<E>(element, hashCode);
217    } else if (tableSize != chooseTableSize(uniques)) {
218      // Resize the table when the array includes too many duplicates.
219      // when this happens, we have already made a copy
220      return construct(uniques, elements);
221    } else {
222      Object[] uniqueElements = (uniques < elements.length)
223          ? ObjectArrays.arraysCopyOf(elements, uniques)
224          : elements;
225      return new RegularImmutableSet<E>(uniqueElements, hashCode, table, mask);
226    }
227  }
228
229  // We use power-of-2 tables, and this is the highest int that's a power of 2
230  static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO;
231
232  // Represents how tightly we can pack things, as a maximum.
233  private static final double DESIRED_LOAD_FACTOR = 0.7;
234
235  // If the set has this many elements, it will "max out" the table size
236  private static final int CUTOFF =
237      (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR);
238
239  /**
240   * Returns an array size suitable for the backing array of a hash table that
241   * uses open addressing with linear probing in its implementation.  The
242   * returned size is the smallest power of two that can hold setSize elements
243   * with the desired load factor.
244   *
245   * <p>Do not call this method with setSize < 2.
246   */
247  @VisibleForTesting static int chooseTableSize(int setSize) {
248    // Correct the size for open addressing to match desired load factor.
249    if (setSize < CUTOFF) {
250      // Round up to the next highest power of 2.
251      int tableSize = Integer.highestOneBit(setSize - 1) << 1;
252      while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
253        tableSize <<= 1;
254      }
255      return tableSize;
256    }
257
258    // The table can't be completely full or we'll get infinite reprobes
259    checkArgument(setSize < MAX_TABLE_SIZE, "collection too large");
260    return MAX_TABLE_SIZE;
261  }
262
263  /**
264   * Returns an immutable set containing the given elements, in order. Repeated
265   * occurrences of an element (according to {@link Object#equals}) after the
266   * first are ignored.
267   *
268   * @throws NullPointerException if any of {@code elements} is null
269   * @since 3.0
270   */
271  public static <E> ImmutableSet<E> copyOf(E[] elements) {
272    switch (elements.length) {
273      case 0:
274        return of();
275      case 1:
276        return of(elements[0]);
277      default:
278        return construct(elements.length, elements.clone());
279    }
280  }
281
282  /**
283   * Returns an immutable set containing the given elements, in order. Repeated
284   * occurrences of an element (according to {@link Object#equals}) after the
285   * first are ignored. This method iterates over {@code elements} at most once.
286   *
287   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
288   * ImmutableSet.copyOf(s)} returns an {@code ImmutableSet<String>} containing
289   * each of the strings in {@code s}, while {@code ImmutableSet.of(s)} returns
290   * a {@code ImmutableSet<Set<String>>} containing one element (the given set
291   * itself).
292   *
293   * <p>Despite the method name, this method attempts to avoid actually copying
294   * the data when it is safe to do so. The exact circumstances under which a
295   * copy will or will not be performed are undocumented and subject to change.
296   *
297   * @throws NullPointerException if any of {@code elements} is null
298   */
299  public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) {
300    return (elements instanceof Collection)
301        ? copyOf(Collections2.cast(elements))
302        : copyOf(elements.iterator());
303  }
304
305  /**
306   * Returns an immutable set containing the given elements, in order. Repeated
307   * occurrences of an element (according to {@link Object#equals}) after the
308   * first are ignored.
309   *
310   * @throws NullPointerException if any of {@code elements} is null
311   */
312  public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) {
313    // We special-case for 0 or 1 elements, but anything further is madness.
314    if (!elements.hasNext()) {
315      return of();
316    }
317    E first = elements.next();
318    if (!elements.hasNext()) {
319      return of(first);
320    } else {
321      return new ImmutableSet.Builder<E>()
322          .add(first)
323          .addAll(elements)
324          .build();
325    }
326  }
327
328  /**
329   * Returns an immutable set containing the given elements, in order. Repeated
330   * occurrences of an element (according to {@link Object#equals}) after the
331   * first are ignored. This method iterates over {@code elements} at most
332   * once.
333   *
334   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
335   * ImmutableSet.copyOf(s)} returns an {@code ImmutableSet<String>} containing
336   * each of the strings in {@code s}, while {@code ImmutableSet.of(s)} returns
337   * a {@code ImmutableSet<Set<String>>} containing one element (the given set
338   * itself).
339   *
340   * <p><b>Note:</b> Despite what the method name suggests, {@code copyOf} will
341   * return constant-space views, rather than linear-space copies, of some
342   * inputs known to be immutable. For some other immutable inputs, such as key
343   * sets of an {@code ImmutableMap}, it still performs a copy in order to avoid
344   * holding references to the values of the map. The heuristics used in this
345   * decision are undocumented and subject to change except that:
346   * <ul>
347   * <li>A full copy will be done of any {@code ImmutableSortedSet}.</li>
348   * <li>{@code ImmutableSet.copyOf()} is idempotent with respect to pointer
349   * equality.</li>
350   * </ul>
351   *
352   * <p>This method is safe to use even when {@code elements} is a synchronized
353   * or concurrent collection that is currently being modified by another
354   * thread.
355   *
356   * @throws NullPointerException if any of {@code elements} is null
357   * @since 7.0 (source-compatible since 2.0)
358   */
359  public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) {
360    /*
361     * TODO(user): consider checking for ImmutableAsList here
362     * TODO(user): consider checking for Multiset here
363     */
364    if (elements instanceof ImmutableSet
365        && !(elements instanceof ImmutableSortedSet)) {
366      @SuppressWarnings("unchecked") // all supported methods are covariant
367      ImmutableSet<E> set = (ImmutableSet<E>) elements;
368      if (!set.isPartialView()) {
369        return set;
370      }
371    } else if (elements instanceof EnumSet) {
372      return copyOfEnumSet((EnumSet) elements);
373    }
374    Object[] array = elements.toArray();
375    return construct(array.length, array);
376  }
377
378  private static <E extends Enum<E>> ImmutableSet<E> copyOfEnumSet(
379      EnumSet<E> enumSet) {
380    return ImmutableEnumSet.asImmutable(EnumSet.copyOf(enumSet));
381  }
382
383  ImmutableSet() {}
384
385  /** Returns {@code true} if the {@code hashCode()} method runs quickly. */
386  boolean isHashCodeFast() {
387    return false;
388  }
389
390  @Override public boolean equals(@Nullable Object object) {
391    if (object == this) {
392      return true;
393    } else if (object instanceof ImmutableSet
394        && isHashCodeFast()
395        && ((ImmutableSet<?>) object).isHashCodeFast()
396        && hashCode() != object.hashCode()) {
397      return false;
398    }
399    return Sets.equalsImpl(this, object);
400  }
401
402  @Override public int hashCode() {
403    return Sets.hashCodeImpl(this);
404  }
405
406  // This declaration is needed to make Set.iterator() and
407  // ImmutableCollection.iterator() consistent.
408  @Override public abstract UnmodifiableIterator<E> iterator();
409
410  /*
411   * This class is used to serialize all ImmutableSet instances, except for
412   * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
413   * captures their "logical contents" and they are reconstructed using public
414   * static factories. This is necessary to ensure that the existence of a
415   * particular implementation type is an implementation detail.
416   */
417  private static class SerializedForm implements Serializable {
418    final Object[] elements;
419    SerializedForm(Object[] elements) {
420      this.elements = elements;
421    }
422    Object readResolve() {
423      return copyOf(elements);
424    }
425    private static final long serialVersionUID = 0;
426  }
427
428  @Override Object writeReplace() {
429    return new SerializedForm(toArray());
430  }
431
432  /**
433   * Returns a new builder. The generated builder is equivalent to the builder
434   * created by the {@link Builder} constructor.
435   */
436  public static <E> Builder<E> builder() {
437    return new Builder<E>();
438  }
439
440  /**
441   * A builder for creating immutable set instances, especially {@code public
442   * static final} sets ("constant sets"). Example: <pre>   {@code
443   *
444   *   public static final ImmutableSet<Color> GOOGLE_COLORS =
445   *       new ImmutableSet.Builder<Color>()
446   *           .addAll(WEBSAFE_COLORS)
447   *           .add(new Color(0, 191, 255))
448   *           .build();}</pre>
449   *
450   * <p>Builder instances can be reused; it is safe to call {@link #build} multiple
451   * times to build multiple sets in series. Each set is a superset of the set
452   * created before it.
453   *
454   * @since 2.0 (imported from Google Collections Library)
455   */
456  public static class Builder<E> extends ImmutableCollection.ArrayBasedBuilder<E> {
457
458    /**
459     * Creates a new builder. The returned builder is equivalent to the builder
460     * generated by {@link ImmutableSet#builder}.
461     */
462    public Builder() {
463      this(DEFAULT_INITIAL_CAPACITY);
464    }
465
466    Builder(int capacity) {
467      super(capacity);
468    }
469
470    /**
471     * Adds {@code element} to the {@code ImmutableSet}.  If the {@code
472     * ImmutableSet} already contains {@code element}, then {@code add} has no
473     * effect (only the previously added element is retained).
474     *
475     * @param element the element to add
476     * @return this {@code Builder} object
477     * @throws NullPointerException if {@code element} is null
478     */
479    @Override public Builder<E> add(E element) {
480      super.add(element);
481      return this;
482    }
483
484    /**
485     * Adds each element of {@code elements} to the {@code ImmutableSet},
486     * ignoring duplicate elements (only the first duplicate element is added).
487     *
488     * @param elements the elements to add
489     * @return this {@code Builder} object
490     * @throws NullPointerException if {@code elements} is null or contains a
491     *     null element
492     */
493    @Override public Builder<E> add(E... elements) {
494      super.add(elements);
495      return this;
496    }
497
498    /**
499     * Adds each element of {@code elements} to the {@code ImmutableSet},
500     * ignoring duplicate elements (only the first duplicate element is added).
501     *
502     * @param elements the {@code Iterable} to add to the {@code ImmutableSet}
503     * @return this {@code Builder} object
504     * @throws NullPointerException if {@code elements} is null or contains a
505     *     null element
506     */
507    @Override public Builder<E> addAll(Iterable<? extends E> elements) {
508      super.addAll(elements);
509      return this;
510    }
511
512    /**
513     * Adds each element of {@code elements} to the {@code ImmutableSet},
514     * ignoring duplicate elements (only the first duplicate element is added).
515     *
516     * @param elements the elements to add to the {@code ImmutableSet}
517     * @return this {@code Builder} object
518     * @throws NullPointerException if {@code elements} is null or contains a
519     *     null element
520     */
521    @Override public Builder<E> addAll(Iterator<? extends E> elements) {
522      super.addAll(elements);
523      return this;
524    }
525
526    /**
527     * Returns a newly-created {@code ImmutableSet} based on the contents of
528     * the {@code Builder}.
529     */
530    @Override public ImmutableSet<E> build() {
531      ImmutableSet<E> result = construct(size, contents);
532      // construct has the side effect of deduping contents, so we update size
533      // accordingly.
534      size = result.size();
535      return result;
536    }
537  }
538}