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;
023
024import java.io.Serializable;
025import java.util.ArrayList;
026import java.util.Collection;
027import java.util.Collections;
028import java.util.HashSet;
029import java.util.Iterator;
030import java.util.Set;
031
032import javax.annotation.Nullable;
033
034/**
035 * A high-performance, immutable {@code Set} with reliable, user-specified
036 * iteration order. Does not permit null elements.
037 *
038 * <p>Unlike {@link Collections#unmodifiableSet}, which is a <i>view</i> of a
039 * separate collection that can still change, an instance of this class contains
040 * its own private data and will <i>never</i> change. This class is convenient
041 * for {@code public static final} sets ("constant sets") and also lets you
042 * easily make a "defensive copy" of a set provided to your class by a caller.
043 *
044 * <p><b>Warning:</b> Like most sets, an {@code ImmutableSet} will not function
045 * correctly if an element is modified after being placed in the set. For this
046 * reason, and to avoid general confusion, it is strongly recommended to place
047 * only immutable objects into this collection.
048 *
049 * <p>This class has been observed to perform significantly better than {@link
050 * HashSet} for objects with very fast {@link Object#hashCode} implementations
051 * (as a well-behaved immutable object should). While this class's factory
052 * methods create hash-based instances, the {@link ImmutableSortedSet} subclass
053 * performs binary searches instead.
054 *
055 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed
056 * outside its package as it has no public or protected constructors. Thus,
057 * instances of this type are guaranteed to be immutable.
058 *
059 * @see ImmutableList
060 * @see ImmutableMap
061 * @author Kevin Bourrillion
062 * @author Nick Kralevich
063 * @since 2 (imported from Google Collections Library)
064 */
065@GwtCompatible(serializable = true, emulated = true)
066@SuppressWarnings("serial") // we're overriding default serialization
067public abstract class ImmutableSet<E> extends ImmutableCollection<E>
068    implements Set<E> {
069  /**
070   * Returns the empty immutable set. This set behaves and performs comparably
071   * to {@link Collections#emptySet}, and is preferable mainly for consistency
072   * and maintainability of your code.
073   */
074  // Casting to any type is safe because the set will never hold any elements.
075  @SuppressWarnings({"unchecked"})
076  public static <E> ImmutableSet<E> of() {
077    return (ImmutableSet<E>) EmptyImmutableSet.INSTANCE;
078  }
079
080  /**
081   * Returns an immutable set containing a single element. This set behaves and
082   * performs comparably to {@link Collections#singleton}, but will not accept
083   * a null element. It is preferable mainly for consistency and
084   * maintainability of your code.
085   */
086  public static <E> ImmutableSet<E> of(E element) {
087    return new SingletonImmutableSet<E>(element);
088  }
089
090  /**
091   * Returns an immutable set containing the given elements, in order. Repeated
092   * occurrences of an element (according to {@link Object#equals}) after the
093   * first are ignored.
094   *
095   * @throws NullPointerException if any element is null
096   */
097  public static <E> ImmutableSet<E> of(E e1, E e2) {
098    return construct(e1, e2);
099  }
100
101  /**
102   * Returns an immutable set containing the given elements, in order. Repeated
103   * occurrences of an element (according to {@link Object#equals}) after the
104   * first are ignored.
105   *
106   * @throws NullPointerException if any element is null
107   */
108  public static <E> ImmutableSet<E> of(E e1, E e2, E e3) {
109    return construct(e1, e2, e3);
110  }
111
112  /**
113   * Returns an immutable set containing the given elements, in order. Repeated
114   * occurrences of an element (according to {@link Object#equals}) after the
115   * first are ignored.
116   *
117   * @throws NullPointerException if any element is null
118   */
119  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) {
120    return construct(e1, e2, e3, e4);
121  }
122
123  /**
124   * Returns an immutable set containing the given elements, in order. Repeated
125   * occurrences of an element (according to {@link Object#equals}) after the
126   * first are ignored.
127   *
128   * @throws NullPointerException if any element is null
129   */
130  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) {
131    return construct(e1, e2, e3, e4, e5);
132  }
133
134  /**
135   * Returns an immutable set containing the given elements, in order. Repeated
136   * occurrences of an element (according to {@link Object#equals}) after the
137   * first are ignored.
138   *
139   * @throws NullPointerException if any element is null
140   * @since 3 (source-compatible since release 2)
141   */
142  public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6,
143      E... others) {
144    final int paramCount = 6;
145    Object[] elements = new Object[paramCount + others.length];
146    elements[0] = e1;
147    elements[1] = e2;
148    elements[2] = e3;
149    elements[3] = e4;
150    elements[4] = e5;
151    elements[5] = e6;
152    for (int i = paramCount; i < elements.length; i++) {
153      elements[i] = others[i - paramCount];
154    }
155    return construct(elements);
156  }
157
158  /** {@code elements} has to be internally created array. */
159  private static <E> ImmutableSet<E> construct(Object... elements) {
160    int tableSize = chooseTableSize(elements.length);
161    Object[] table = new Object[tableSize];
162    int mask = tableSize - 1;
163    ArrayList<Object> uniqueElementsList = null;
164    int hashCode = 0;
165    for (int i = 0; i < elements.length; i++) {
166      Object element = elements[i];
167      int hash = element.hashCode();
168      for (int j = Hashing.smear(hash); ; j++) {
169        int index = j & mask;
170        Object value = table[index];
171        if (value == null) {
172          if (uniqueElementsList != null) {
173            uniqueElementsList.add(element);
174          }
175          // Came to an empty slot. Put the element here.
176          table[index] = element;
177          hashCode += hash;
178          break;
179        } else if (value.equals(element)) {
180          if (uniqueElementsList == null) {
181            // first dup
182            uniqueElementsList = new ArrayList<Object>(elements.length);
183            for (int k = 0; k < i; k++) {
184              Object previous = elements[k];
185              uniqueElementsList.add(previous);
186            }
187          }
188          break;
189        }
190      }
191    }
192    Object[] uniqueElements = uniqueElementsList == null
193        ? elements
194        : uniqueElementsList.toArray();
195    if (uniqueElements.length == 1) {
196      // There is only one element or elements are all duplicates
197      @SuppressWarnings("unchecked") // we are careful to only pass in E
198      E element = (E) uniqueElements[0];
199      return new SingletonImmutableSet<E>(element, hashCode);
200    } else if (tableSize > 2 * chooseTableSize(uniqueElements.length)) {
201      // Resize the table when the array includes too many duplicates.
202      // when this happens, we have already made a copy
203      return construct(uniqueElements);
204    } else {
205      return new RegularImmutableSet<E>(uniqueElements, hashCode, table, mask);
206    }
207  }
208
209  // We use power-of-2 tables, and this is the highest int that's a power of 2
210  static final int MAX_TABLE_SIZE = 1 << 30;
211
212  // If the set has this many elements, it will "max out" the table size
213  static final int CUTOFF = 1 << 29;
214
215  /**
216   * Returns an array size suitable for the backing array of a hash table that
217   * uses linear probing in its implementation.  The returned size is the
218   * smallest power of two that can hold setSize elements while being at most
219   * 50% full, if possible.
220   */
221  static int chooseTableSize(int setSize) {
222    if (setSize < CUTOFF) {
223      return Integer.highestOneBit(setSize) << 2;
224    }
225
226    // The table can't be completely full or we'll get infinite reprobes
227    checkArgument(setSize < MAX_TABLE_SIZE, "collection too large");
228    return MAX_TABLE_SIZE;
229  }
230
231  /**
232   * Returns an immutable set containing the given elements, in order. Repeated
233   * occurrences of an element (according to {@link Object#equals}) after the
234   * first are ignored.
235   *
236   * @deprecated use {@link #copyOf(Object[])}. <b>This method is scheduled for
237   *     deletion in October 2011.</b>
238   * @throws NullPointerException if any of {@code elements} is null
239   * @since 2 (changed from varargs in release 3)
240   */
241  // TODO(kevinb): when this is removed, remember to remove from ISS and ISSFS
242  @Deprecated
243  public static <E> ImmutableSet<E> of(E[] elements) {
244    return copyOf(elements);
245  }
246
247 /**
248  * Returns an immutable set containing the given elements, in order. Repeated
249  * occurrences of an element (according to {@link Object#equals}) after the
250  * first are ignored.
251  *
252  * @throws NullPointerException if any of {@code elements} is null
253  * @since 3
254  */
255  public static <E> ImmutableSet<E> copyOf(E[] elements) {
256    // TODO(benyu): could we delegate to
257    // copyFromCollection(Arrays.asList(elements))?
258    switch (elements.length) {
259      case 0:
260        return of();
261      case 1:
262        return of(elements[0]);
263      default:
264        return construct(elements.clone());
265    }
266  }
267
268  /**
269   * Returns an immutable set containing the given elements, in order. Repeated
270   * occurrences of an element (according to {@link Object#equals}) after the
271   * first are ignored. This method iterates over {@code elements} at most once.
272   *
273   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
274   * ImmutableSet.copyOf(s)} returns an {@code ImmutableSet<String>} containing
275   * each of the strings in {@code s}, while {@code ImmutableSet.of(s)} returns
276   * a {@code ImmutableSet<Set<String>>} containing one element (the given set
277   * itself).
278   *
279   * <p>Despite the method name, this method attempts to avoid actually copying
280   * the data when it is safe to do so. The exact circumstances under which a
281   * copy will or will not be performed are undocumented and subject to change.
282   *
283   * @throws NullPointerException if any of {@code elements} is null
284   */
285  public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) {
286    return (elements instanceof Collection)
287        ? copyOf(Collections2.cast(elements))
288        : copyOf(elements.iterator());
289  }
290
291  /**
292   * Returns an immutable set containing the given elements, in order. Repeated
293   * occurrences of an element (according to {@link Object#equals}) after the
294   * first are ignored.
295   *
296   * @throws NullPointerException if any of {@code elements} is null
297   */
298  public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) {
299    // TODO(benyu): here we could avoid toArray() for 0 or 1-element list,
300    // worth it?
301    return copyFromCollection(Lists.newArrayList(elements));
302  }
303
304  /**
305   * Returns an immutable set containing the given elements, in order. Repeated
306   * occurrences of an element (according to {@link Object#equals}) after the
307   * first are ignored. This method iterates over {@code elements} at most
308   * once.
309   *
310   * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
311   * ImmutableSet.copyOf(s)} returns an {@code ImmutableSet<String>} containing
312   * each of the strings in {@code s}, while {@code ImmutableSet.of(s)} returns
313   * a {@code ImmutableSet<Set<String>>} containing one element (the given set
314   * itself).
315   *
316   * <p><b>Note:</b> Despite what the method name suggests, {@code copyOf} will
317   * return constant-space views, rather than linear-space copies, of some
318   * inputs known to be immutable. For some other immutable inputs, such as key
319   * sets of an {@code ImmutableMap}, it still performs a copy in order to avoid
320   * holding references to the values of the map. The heuristics used in this
321   * decision are undocumented and subject to change except that:
322   * <ul>
323   * <li>A full copy will be done of any {@code ImmutableSortedSet}.</li>
324   * <li>{@code ImmutableSet.copyOf()} is idempotent with respect to pointer
325   * equality.</li>
326   * </ul>
327   *
328   * <p>This method is safe to use even when {@code elements} is a synchronized
329   * or concurrent collection that is currently being modified by another
330   * thread.
331   *
332   * @throws NullPointerException if any of {@code elements} is null
333   * @since 7 (source-compatible since release 2)
334   */
335  public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) {
336    if (elements instanceof ImmutableSet
337        && !(elements instanceof ImmutableSortedSet)) {
338      @SuppressWarnings("unchecked") // all supported methods are covariant
339      ImmutableSet<E> set = (ImmutableSet<E>) elements;
340      if (!set.isPartialView()) {
341        return set;
342      }
343    }
344    return copyFromCollection(elements);
345  }
346
347  private static <E> ImmutableSet<E> copyFromCollection(
348      Collection<? extends E> collection) {
349    Object[] elements = collection.toArray();
350    switch (elements.length) {
351      case 0:
352        return of();
353      case 1:
354        @SuppressWarnings("unchecked") // collection had only Es in it
355        E onlyElement = (E) elements[0];
356        return of(onlyElement);
357      default:
358        // safe to use the array without copying it
359        // as specified by Collection.toArray().
360        return construct(elements);
361    }
362  }
363
364  ImmutableSet() {}
365
366  /** Returns {@code true} if the {@code hashCode()} method runs quickly. */
367  boolean isHashCodeFast() {
368    return false;
369  }
370
371  @Override public boolean equals(@Nullable Object object) {
372    if (object == this) {
373      return true;
374    }
375    if (object instanceof ImmutableSet
376        && isHashCodeFast()
377        && ((ImmutableSet<?>) object).isHashCodeFast()
378        && hashCode() != object.hashCode()) {
379      return false;
380    }
381    return Sets.equalsImpl(this, object);
382  }
383
384  @Override public int hashCode() {
385    return Sets.hashCodeImpl(this);
386  }
387
388  // This declaration is needed to make Set.iterator() and
389  // ImmutableCollection.iterator() consistent.
390  @Override public abstract UnmodifiableIterator<E> iterator();
391
392  abstract static class ArrayImmutableSet<E> extends ImmutableSet<E> {
393    // the elements (two or more) in the desired order.
394    final transient Object[] elements;
395
396    ArrayImmutableSet(Object[] elements) {
397      this.elements = elements;
398    }
399
400    @Override
401    public int size() {
402      return elements.length;
403    }
404
405    @Override public boolean isEmpty() {
406      return false;
407    }
408
409    /*
410     * The cast is safe because the only way to create an instance is via the
411     * create() method above, which only permits elements of type E.
412     */
413    @SuppressWarnings("unchecked")
414    @Override public UnmodifiableIterator<E> iterator() {
415      return (UnmodifiableIterator<E>) Iterators.forArray(elements);
416    }
417
418    @Override public Object[] toArray() {
419      Object[] array = new Object[size()];
420      System.arraycopy(elements, 0, array, 0, size());
421      return array;
422    }
423
424    @Override public <T> T[] toArray(T[] array) {
425      int size = size();
426      if (array.length < size) {
427        array = ObjectArrays.newArray(array, size);
428      } else if (array.length > size) {
429        array[size] = null;
430      }
431      System.arraycopy(elements, 0, array, 0, size);
432      return array;
433    }
434
435    @Override public boolean containsAll(Collection<?> targets) {
436      if (targets == this) {
437        return true;
438      }
439      if (!(targets instanceof ArrayImmutableSet)) {
440        return super.containsAll(targets);
441      }
442      if (targets.size() > size()) {
443        return false;
444      }
445      for (Object target : ((ArrayImmutableSet<?>) targets).elements) {
446        if (!contains(target)) {
447          return false;
448        }
449      }
450      return true;
451    }
452
453    @Override boolean isPartialView() {
454      return false;
455    }
456
457    @Override ImmutableList<E> createAsList() {
458      return new ImmutableAsList<E>(elements, this);
459    }
460  }
461
462  /** such as ImmutableMap.keySet() */
463  abstract static class TransformedImmutableSet<D, E> extends ImmutableSet<E> {
464    final D[] source;
465    final int hashCode;
466
467    TransformedImmutableSet(D[] source, int hashCode) {
468      this.source = source;
469      this.hashCode = hashCode;
470    }
471
472    abstract E transform(D element);
473
474    @Override
475    public int size() {
476      return source.length;
477    }
478
479    @Override public boolean isEmpty() {
480      return false;
481    }
482
483    @Override public UnmodifiableIterator<E> iterator() {
484      return new AbstractIndexedListIterator<E>(source.length) {
485        @Override protected E get(int index) {
486          return transform(source[index]);
487        }
488      };
489    }
490
491    @Override public Object[] toArray() {
492      return toArray(new Object[size()]);
493    }
494
495    @Override public <T> T[] toArray(T[] array) {
496      int size = size();
497      if (array.length < size) {
498        array = ObjectArrays.newArray(array, size);
499      } else if (array.length > size) {
500        array[size] = null;
501      }
502
503      // Writes will produce ArrayStoreException when the toArray() doc requires
504      Object[] objectArray = array;
505      for (int i = 0; i < source.length; i++) {
506        objectArray[i] = transform(source[i]);
507      }
508      return array;
509    }
510
511    @Override public final int hashCode() {
512      return hashCode;
513    }
514
515    @Override boolean isHashCodeFast() {
516      return true;
517    }
518  }
519
520  /*
521   * This class is used to serialize all ImmutableSet instances, except for
522   * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
523   * captures their "logical contents" and they are reconstructed using public
524   * static factories. This is necessary to ensure that the existence of a
525   * particular implementation type is an implementation detail.
526   */
527  private static class SerializedForm implements Serializable {
528    final Object[] elements;
529    SerializedForm(Object[] elements) {
530      this.elements = elements;
531    }
532    Object readResolve() {
533      return copyOf(elements);
534    }
535    private static final long serialVersionUID = 0;
536  }
537
538  @Override Object writeReplace() {
539    return new SerializedForm(toArray());
540  }
541
542  /**
543   * Returns a new builder. The generated builder is equivalent to the builder
544   * created by the {@link Builder} constructor.
545   */
546  public static <E> Builder<E> builder() {
547    return new Builder<E>();
548  }
549
550  /**
551   * A builder for creating immutable set instances, especially {@code public
552   * static final} sets ("constant sets"). Example: <pre>   {@code
553   *
554   *   public static final ImmutableSet<Color> GOOGLE_COLORS =
555   *       new ImmutableSet.Builder<Color>()
556   *           .addAll(WEBSAFE_COLORS)
557   *           .add(new Color(0, 191, 255))
558   *           .build();}</pre>
559   *
560   * Builder instances can be reused; it is safe to call {@link #build} multiple
561   * times to build multiple sets in series. Each set is a superset of the set
562   * created before it.
563   *
564   * @since 2 (imported from Google Collections Library)
565   */
566  public static class Builder<E> extends ImmutableCollection.Builder<E> {
567    // accessed directly by ImmutableSortedSet
568    final ArrayList<E> contents = Lists.newArrayList();
569
570    /**
571     * Creates a new builder. The returned builder is equivalent to the builder
572     * generated by {@link ImmutableSet#builder}.
573     */
574    public Builder() {}
575
576    /**
577     * Adds {@code element} to the {@code ImmutableSet}.  If the {@code
578     * ImmutableSet} already contains {@code element}, then {@code add} has no
579     * effect (only the previously added element is retained).
580     *
581     * @param element the element to add
582     * @return this {@code Builder} object
583     * @throws NullPointerException if {@code element} is null
584     */
585    @Override public Builder<E> add(E element) {
586      contents.add(checkNotNull(element));
587      return this;
588    }
589
590    /**
591     * Adds each element of {@code elements} to the {@code ImmutableSet},
592     * ignoring duplicate elements (only the first duplicate element is added).
593     *
594     * @param elements the elements to add
595     * @return this {@code Builder} object
596     * @throws NullPointerException if {@code elements} is null or contains a
597     *     null element
598     */
599    @Override public Builder<E> add(E... elements) {
600      contents.ensureCapacity(contents.size() + elements.length);
601      super.add(elements);
602      return this;
603    }
604
605    /**
606     * Adds each element of {@code elements} to the {@code ImmutableSet},
607     * ignoring duplicate elements (only the first duplicate element is added).
608     *
609     * @param elements the {@code Iterable} to add to the {@code ImmutableSet}
610     * @return this {@code Builder} object
611     * @throws NullPointerException if {@code elements} is null or contains a
612     *     null element
613     */
614    @Override public Builder<E> addAll(Iterable<? extends E> elements) {
615      if (elements instanceof Collection) {
616        Collection<?> collection = (Collection<?>) elements;
617        contents.ensureCapacity(contents.size() + collection.size());
618      }
619      super.addAll(elements);
620      return this;
621    }
622
623    /**
624     * Adds each element of {@code elements} to the {@code ImmutableSet},
625     * ignoring duplicate elements (only the first duplicate element is added).
626     *
627     * @param elements the elements to add to the {@code ImmutableSet}
628     * @return this {@code Builder} object
629     * @throws NullPointerException if {@code elements} is null or contains a
630     *     null element
631     */
632    @Override public Builder<E> addAll(Iterator<? extends E> elements) {
633      super.addAll(elements);
634      return this;
635    }
636
637    /**
638     * Returns a newly-created {@code ImmutableSet} based on the contents of
639     * the {@code Builder}.
640     */
641    @Override public ImmutableSet<E> build() {
642      return copyOf(contents);
643    }
644  }
645}