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;
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.HashSet;
031import java.util.Iterator;
032import java.util.Set;
033
034import javax.annotation.Nullable;
035
036/**
037 * A high-performance, immutable {@code Set} with reliable, user-specified
038 * iteration order. Does not permit null elements.
039 *
040 * <p>Unlike {@link Collections#unmodifiableSet}, which is a <i>view</i> of a
041 * separate collection that can still change, an instance of this class contains
042 * its own private data and will <i>never</i> change. This class is convenient
043 * for {@code public static final} sets ("constant sets") and also lets you
044 * easily make a "defensive copy" of a set provided to your class by a caller.
045 *
046 * <p><b>Warning:</b> Like most sets, an {@code ImmutableSet} will not function
047 * correctly if an element is modified after being placed in the set. For this
048 * reason, and to avoid general confusion, it is strongly recommended to place
049 * only immutable objects into this collection.
050 *
051 * <p>This class has been observed to perform significantly better than {@link
052 * HashSet} for objects with very fast {@link Object#hashCode} implementations
053 * (as a well-behaved immutable object should). While this class's factory
054 * methods create hash-based instances, the {@link ImmutableSortedSet} subclass
055 * performs binary searches instead.
056 *
057 * <p><b>Note:</b> Although this class is not final, it cannot be subclassed
058 * outside its package as it has no public or protected constructors. Thus,
059 * instances of this type are guaranteed to be immutable.
060 *
061 * <p>See the Guava User Guide article on <a href=
062 * "http://code.google.com/p/guava-libraries/wiki/ImmutableCollectionsExplained">
063 * immutable collections</a>.
064 *
065 * @see ImmutableList
066 * @see ImmutableMap
067 * @author Kevin Bourrillion
068 * @author Nick Kralevich
069 * @since 2.0 (imported from Google Collections Library)
070 */
071@GwtCompatible(serializable = true, emulated = true)
072@SuppressWarnings("serial") // we're overriding default serialization
073public abstract class ImmutableSet<E> extends ImmutableCollection<E>
074    implements Set<E> {
075  /**
076   * Returns the empty immutable set. This set behaves and performs comparably
077   * to {@link Collections#emptySet}, and is preferable mainly for consistency
078   * and maintainability of your code.
079   */
080  // Casting to any type is safe because the set will never hold any elements.
081  @SuppressWarnings({"unchecked"})
082  public static <E> ImmutableSet<E> of() {
083    return (ImmutableSet<E>) EmptyImmutableSet.INSTANCE;
084  }
085
086  /**
087   * Returns an immutable set containing a single element. This set behaves and
088   * performs comparably to {@link Collections#singleton}, but will not accept
089   * a null element. It is preferable mainly for consistency and
090   * maintainability of your code.
091   */
092  public static <E> ImmutableSet<E> of(E element) {
093    return new SingletonImmutableSet<E>(element);
094  }
095
096  /**
097   * Returns an immutable set containing the given elements, in order. Repeated
098   * occurrences of an element (according to {@link Object#equals}) after the
099   * first are ignored.
100   *
101   * @throws NullPointerException if any element is null
102   */
103  public static <E> ImmutableSet<E> of(E e1, E e2) {
104    return construct(2, e1, e2);
105  }
106
107  /**
108   * Returns an immutable set containing the given elements, in order. Repeated
109   * occurrences of an element (according to {@link Object#equals}) after the
110   * first are ignored.
111   *
112   * @throws NullPointerException if any element is null
113   */
114  public static <E> ImmutableSet<E> of(E e1, E e2, E e3) {
115    return construct(3, e1, e2, e3);
116  }
117
118  /**
119   * Returns an immutable set containing the given elements, in order. Repeated
120   * occurrences of an element (according to {@link Object#equals}) after the
121   * first are ignored.
122   *
123   * @throws NullPointerException if any element is null
124   */
125  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) {
126    return construct(4, e1, e2, e3, e4);
127  }
128
129  /**
130   * Returns an immutable set containing the given elements, in order. Repeated
131   * occurrences of an element (according to {@link Object#equals}) after the
132   * first are ignored.
133   *
134   * @throws NullPointerException if any element is null
135   */
136  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) {
137    return construct(5, e1, e2, e3, e4, e5);
138  }
139
140  /**
141   * Returns an immutable set containing the given elements, in order. Repeated
142   * occurrences of an element (according to {@link Object#equals}) after the
143   * first are ignored.
144   *
145   * @throws NullPointerException if any element is null
146   * @since 3.0 (source-compatible since 2.0)
147   */
148  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6,
149      E... others) {
150    final int paramCount = 6;
151    Object[] elements = new Object[paramCount + others.length];
152    elements[0] = e1;
153    elements[1] = e2;
154    elements[2] = e3;
155    elements[3] = e4;
156    elements[4] = e5;
157    elements[5] = e6;
158    System.arraycopy(others, 0, elements, paramCount, others.length);
159    return construct(elements.length, elements);
160  }
161
162  /**
163   * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array.
164   * If {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of
165   * {@code elements} will be in the first {@code k} positions, and {@code elements[i] == null} for
166   * {@code k <= i < n}.
167   *
168   * <p>This may modify {@code elements}.  Additionally, if {@code n == elements.length} and
169   * {@code elements} contains no duplicates, {@code elements} may be used without copying in the
170   * returned {@code ImmutableSet}, in which case it may no longer be modified.
171   *
172   * <p>{@code elements} may contain only values of type {@code E}.
173   *
174   * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is
175   *          null
176   */
177  private static <E> ImmutableSet<E> construct(int n, Object... elements) {
178    switch (n) {
179      case 0:
180        return of();
181      case 1: {
182        @SuppressWarnings("unchecked") // safe; elements contains only E's
183        E elem = (E) elements[0];
184        return of(elem);
185      }
186    }
187    int tableSize = chooseTableSize(n);
188    Object[] table = new Object[tableSize];
189    int mask = tableSize - 1;
190    int hashCode = 0;
191    int uniques = 0;
192    for (int i = 0; i < n; i++) {
193      Object element = ObjectArrays.checkElementNotNull(elements[i], i);
194      int hash = element.hashCode();
195      for (int j = Hashing.smear(hash); ; j++) {
196        int index = j & mask;
197        Object value = table[index];
198        if (value == null) {
199          // Came to an empty slot. Put the element here.
200          elements[uniques++] = element;
201          table[index] = element;
202          hashCode += hash;
203          break;
204        } else if (value.equals(element)) {
205          break;
206        }
207      }
208    }
209    Arrays.fill(elements, uniques, n, null);
210    if (uniques == 1) {
211      // There is only one element or elements are all duplicates
212      @SuppressWarnings("unchecked") // we are careful to only pass in E
213      E element = (E) elements[0];
214      return new SingletonImmutableSet<E>(element, hashCode);
215    } else if (tableSize != chooseTableSize(uniques)) {
216      // Resize the table when the array includes too many duplicates.
217      // when this happens, we have already made a copy
218      return construct(uniques, elements);
219    } else {
220      Object[] uniqueElements = (uniques < elements.length)
221          ? ObjectArrays.arraysCopyOf(elements, uniques)
222          : elements;
223      return new RegularImmutableSet<E>(uniqueElements, hashCode, table, mask);
224    }
225  }
226
227  // We use power-of-2 tables, and this is the highest int that's a power of 2
228  static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO;
229
230  // Represents how tightly we can pack things, as a maximum.
231  private static final double DESIRED_LOAD_FACTOR = 0.7;
232
233  // If the set has this many elements, it will "max out" the table size
234  private static final int CUTOFF =
235      (int) Math.floor(MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR);
236
237  /**
238   * Returns an array size suitable for the backing array of a hash table that
239   * uses open addressing with linear probing in its implementation.  The
240   * returned size is the smallest power of two that can hold setSize elements
241   * with the desired load factor.
242   *
243   * <p>Do not call this method with setSize < 2.
244   */
245  @VisibleForTesting static int chooseTableSize(int setSize) {
246    // Correct the size for open addressing to match desired load factor.
247    if (setSize < CUTOFF) {
248      // Round up to the next highest power of 2.
249      int tableSize = Integer.highestOneBit(setSize - 1) << 1;
250      while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
251        tableSize <<= 1;
252      }
253      return tableSize;
254    }
255
256    // The table can't be completely full or we'll get infinite reprobes
257    checkArgument(setSize < MAX_TABLE_SIZE, "collection too large");
258    return MAX_TABLE_SIZE;
259  }
260
261  /**
262   * Returns an immutable set containing the given elements, in order. Repeated
263   * occurrences of an element (according to {@link Object#equals}) after the
264   * first are ignored.
265   *
266   * @throws NullPointerException if any of {@code elements} is null
267   * @since 3.0
268   */
269  public static <E> ImmutableSet<E> copyOf(E[] elements) {
270    // TODO(benyu): could we delegate to
271    // copyFromCollection(Arrays.asList(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    if (elements instanceof ImmutableSet
361        && !(elements instanceof ImmutableSortedSet)) {
362      @SuppressWarnings("unchecked") // all supported methods are covariant
363      ImmutableSet<E> set = (ImmutableSet<E>) elements;
364      if (!set.isPartialView()) {
365        return set;
366      }
367    }
368    return copyFromCollection(elements);
369  }
370
371  private static <E> ImmutableSet<E> copyFromCollection(
372      Collection<? extends E> collection) {
373    Object[] elements = collection.toArray();
374    switch (elements.length) {
375      case 0:
376        return of();
377      case 1:
378        @SuppressWarnings("unchecked") // collection had only Es in it
379        E onlyElement = (E) elements[0];
380        return of(onlyElement);
381      default:
382        // safe to use the array without copying it
383        // as specified by Collection.toArray().
384        return construct(elements.length, elements);
385    }
386  }
387
388  ImmutableSet() {}
389
390  /** Returns {@code true} if the {@code hashCode()} method runs quickly. */
391  boolean isHashCodeFast() {
392    return false;
393  }
394
395  @Override public boolean equals(@Nullable Object object) {
396    if (object == this) {
397      return true;
398    }
399    if (object instanceof ImmutableSet
400        && isHashCodeFast()
401        && ((ImmutableSet<?>) object).isHashCodeFast()
402        && hashCode() != object.hashCode()) {
403      return false;
404    }
405    return Sets.equalsImpl(this, object);
406  }
407
408  @Override public int hashCode() {
409    return Sets.hashCodeImpl(this);
410  }
411
412  // This declaration is needed to make Set.iterator() and
413  // ImmutableCollection.iterator() consistent.
414  @Override public abstract UnmodifiableIterator<E> iterator();
415
416  abstract static class ArrayImmutableSet<E> extends ImmutableSet<E> {
417    // the elements (two or more) in the desired order.
418    final transient Object[] elements;
419
420    ArrayImmutableSet(Object[] elements) {
421      this.elements = elements;
422    }
423
424    @Override
425    public int size() {
426      return elements.length;
427    }
428
429    @Override public boolean isEmpty() {
430      return false;
431    }
432
433    @Override public UnmodifiableIterator<E> iterator() {
434      return asList().iterator();
435    }
436
437    @Override public Object[] toArray() {
438      return asList().toArray();
439    }
440
441    @Override public <T> T[] toArray(T[] array) {
442      return asList().toArray(array);
443    }
444
445    @Override public boolean containsAll(Collection<?> targets) {
446      if (targets == this) {
447        return true;
448      }
449      if (!(targets instanceof ArrayImmutableSet)) {
450        return super.containsAll(targets);
451      }
452      if (targets.size() > size()) {
453        return false;
454      }
455      for (Object target : ((ArrayImmutableSet<?>) targets).elements) {
456        if (!contains(target)) {
457          return false;
458        }
459      }
460      return true;
461    }
462
463    @Override boolean isPartialView() {
464      return false;
465    }
466
467    @Override ImmutableList<E> createAsList() {
468      return new RegularImmutableAsList<E>(this, elements);
469    }
470  }
471
472  /*
473   * This class is used to serialize all ImmutableSet instances, except for
474   * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
475   * captures their "logical contents" and they are reconstructed using public
476   * static factories. This is necessary to ensure that the existence of a
477   * particular implementation type is an implementation detail.
478   */
479  private static class SerializedForm implements Serializable {
480    final Object[] elements;
481    SerializedForm(Object[] elements) {
482      this.elements = elements;
483    }
484    Object readResolve() {
485      return copyOf(elements);
486    }
487    private static final long serialVersionUID = 0;
488  }
489
490  @Override Object writeReplace() {
491    return new SerializedForm(toArray());
492  }
493
494  /**
495   * Returns a new builder. The generated builder is equivalent to the builder
496   * created by the {@link Builder} constructor.
497   */
498  public static <E> Builder<E> builder() {
499    return new Builder<E>();
500  }
501
502  /**
503   * A builder for creating immutable set instances, especially {@code public
504   * static final} sets ("constant sets"). Example: <pre>   {@code
505   *
506   *   public static final ImmutableSet<Color> GOOGLE_COLORS =
507   *       new ImmutableSet.Builder<Color>()
508   *           .addAll(WEBSAFE_COLORS)
509   *           .add(new Color(0, 191, 255))
510   *           .build();}</pre>
511   *
512   * Builder instances can be reused; it is safe to call {@link #build} multiple
513   * times to build multiple sets in series. Each set is a superset of the set
514   * created before it.
515   *
516   * @since 2.0 (imported from Google Collections Library)
517   */
518  public static class Builder<E> extends ImmutableCollection.Builder<E> {
519    Object[] contents;
520    int size;
521
522    /**
523     * Creates a new builder. The returned builder is equivalent to the builder
524     * generated by {@link ImmutableSet#builder}.
525     */
526    public Builder() {
527      this(DEFAULT_INITIAL_CAPACITY);
528    }
529
530    Builder(int capacity) {
531      checkArgument(capacity >= 0, "capacity must be >= 0 but was %s", capacity);
532      this.contents = new Object[capacity];
533      this.size = 0;
534    }
535
536    /**
537     * Expand capacity to allow the specified number of elements to be added.
538     */
539    Builder<E> expandFor(int count) {
540      int minCapacity = size + count;
541      if (contents.length < minCapacity) {
542        contents = ObjectArrays.arraysCopyOf(
543            contents, expandedCapacity(contents.length, minCapacity));
544      }
545      return this;
546    }
547
548    /**
549     * Adds {@code element} to the {@code ImmutableSet}.  If the {@code
550     * ImmutableSet} already contains {@code element}, then {@code add} has no
551     * effect (only the previously added element is retained).
552     *
553     * @param element the element to add
554     * @return this {@code Builder} object
555     * @throws NullPointerException if {@code element} is null
556     */
557    @Override public Builder<E> add(E element) {
558      expandFor(1);
559      contents[size++] = checkNotNull(element);
560      return this;
561    }
562
563    /**
564     * Adds each element of {@code elements} to the {@code ImmutableSet},
565     * ignoring duplicate elements (only the first duplicate element is added).
566     *
567     * @param elements the elements to add
568     * @return this {@code Builder} object
569     * @throws NullPointerException if {@code elements} is null or contains a
570     *     null element
571     */
572    @Override public Builder<E> add(E... elements) {
573      for (int i = 0; i < elements.length; i++) {
574        ObjectArrays.checkElementNotNull(elements[i], i);
575      }
576      expandFor(elements.length);
577      System.arraycopy(elements, 0, contents, size, elements.length);
578      size += elements.length;
579      return this;
580    }
581
582    /**
583     * Adds each element of {@code elements} to the {@code ImmutableSet},
584     * ignoring duplicate elements (only the first duplicate element is added).
585     *
586     * @param elements the {@code Iterable} to add to the {@code ImmutableSet}
587     * @return this {@code Builder} object
588     * @throws NullPointerException if {@code elements} is null or contains a
589     *     null element
590     */
591    @Override public Builder<E> addAll(Iterable<? extends E> elements) {
592      if (elements instanceof Collection) {
593        Collection<?> collection = (Collection<?>) elements;
594        expandFor(collection.size());
595      }
596      super.addAll(elements);
597      return this;
598    }
599
600    /**
601     * Adds each element of {@code elements} to the {@code ImmutableSet},
602     * ignoring duplicate elements (only the first duplicate element is added).
603     *
604     * @param elements the elements to add to the {@code ImmutableSet}
605     * @return this {@code Builder} object
606     * @throws NullPointerException if {@code elements} is null or contains a
607     *     null element
608     */
609    @Override public Builder<E> addAll(Iterator<? extends E> elements) {
610      super.addAll(elements);
611      return this;
612    }
613
614    /**
615     * Returns a newly-created {@code ImmutableSet} based on the contents of
616     * the {@code Builder}.
617     */
618    @Override public ImmutableSet<E> build() {
619      ImmutableSet<E> result = construct(size, contents);
620      // construct has the side effect of deduping contents, so we update size
621      // accordingly.
622      size = result.size();
623      return result;
624    }
625  }
626}