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