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    }