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