View Javadoc
1   /*
2    * Copyright (C) 2007 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkArgument;
20  import static com.google.common.base.Preconditions.checkNotNull;
21  import static com.google.common.collect.CollectPreconditions.checkNonnegative;
22  import static com.google.common.collect.ObjectArrays.checkElementNotNull;
23  
24  import com.google.common.annotations.Beta;
25  import com.google.common.annotations.GwtCompatible;
26  import com.google.common.annotations.VisibleForTesting;
27  import com.google.common.primitives.Ints;
28  import com.google.errorprone.annotations.CanIgnoreReturnValue;
29  import com.google.errorprone.annotations.concurrent.LazyInit;
30  import com.google.j2objc.annotations.RetainedWith;
31  import java.io.Serializable;
32  import java.util.Arrays;
33  import java.util.Collection;
34  import java.util.Collections;
35  import java.util.EnumSet;
36  import java.util.Iterator;
37  import java.util.Set;
38  import java.util.SortedSet;
39  import java.util.Spliterator;
40  import java.util.function.Consumer;
41  import java.util.stream.Collector;
42  import javax.annotation.Nullable;
43  
44  /**
45   * A {@link Set} whose contents will never change, with many other important properties detailed at
46   * {@link ImmutableCollection}.
47   *
48   * @since 2.0
49   */
50  @GwtCompatible(serializable = true, emulated = true)
51  @SuppressWarnings("serial") // we're overriding default serialization
52  public abstract class ImmutableSet<E> extends ImmutableCollection<E> implements Set<E> {
53    static final int SPLITERATOR_CHARACTERISTICS =
54        ImmutableCollection.SPLITERATOR_CHARACTERISTICS | Spliterator.DISTINCT;
55  
56    /**
57     * Returns a {@code Collector} that accumulates the input elements into a new {@code
58     * ImmutableSet}. Elements appear in the resulting set in the encounter order of the stream; if
59     * the stream contains duplicates (according to {@link Object#equals(Object)}), only the first
60     * duplicate in encounter order will appear in the result.
61     *
62     * @since 21.0
63     */
64    @Beta
65    public static <E> Collector<E, ?, ImmutableSet<E>> toImmutableSet() {
66      return CollectCollectors.toImmutableSet();
67    }
68  
69    /**
70     * Returns the empty immutable set. Preferred over {@link Collections#emptySet} for code
71     * consistency, and because the return type conveys the immutability guarantee.
72     */
73    @SuppressWarnings({"unchecked"}) // fully variant implementation (never actually produces any Es)
74    public static <E> ImmutableSet<E> of() {
75      return (ImmutableSet<E>) RegularImmutableSet.EMPTY;
76    }
77  
78    /**
79     * Returns an immutable set containing {@code element}. Preferred over {@link
80     * Collections#singleton} for code consistency, {@code null} rejection, and because the return
81     * type conveys the immutability guarantee.
82     */
83    public static <E> ImmutableSet<E> of(E element) {
84      return new SingletonImmutableSet<E>(element);
85    }
86  
87    /**
88     * Returns an immutable set containing the given elements, minus duplicates, in the order each was
89     * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
90     * the first are ignored.
91     */
92    public static <E> ImmutableSet<E> of(E e1, E e2) {
93      return construct(2, e1, e2);
94    }
95  
96    /**
97     * Returns an immutable set containing the given elements, minus duplicates, in the order each was
98     * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
99     * the first are ignored.
100    */
101   public static <E> ImmutableSet<E> of(E e1, E e2, E e3) {
102     return construct(3, e1, e2, e3);
103   }
104 
105   /**
106    * Returns an immutable set containing the given elements, minus duplicates, in the order each was
107    * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
108    * the first are ignored.
109    */
110   public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) {
111     return construct(4, e1, e2, e3, e4);
112   }
113 
114   /**
115    * Returns an immutable set containing the given elements, minus duplicates, in the order each was
116    * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
117    * the first are ignored.
118    */
119   public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) {
120     return construct(5, e1, e2, e3, e4, e5);
121   }
122 
123   /**
124    * Returns an immutable set containing the given elements, minus duplicates, in the order each was
125    * first specified. That is, if multiple elements are {@linkplain Object#equals equal}, all except
126    * the first are ignored.
127    *
128    * @since 3.0 (source-compatible since 2.0)
129    */
130   @SafeVarargs // For Eclipse. For internal javac we have disabled this pointless type of warning.
131   public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, E... others) {
132     final int paramCount = 6;
133     Object[] elements = new Object[paramCount + others.length];
134     elements[0] = e1;
135     elements[1] = e2;
136     elements[2] = e3;
137     elements[3] = e4;
138     elements[4] = e5;
139     elements[5] = e6;
140     System.arraycopy(others, 0, elements, paramCount, others.length);
141     return construct(elements.length, elements);
142   }
143 
144   /**
145    * Constructs an {@code ImmutableSet} from the first {@code n} elements of the specified array.
146    * If {@code k} is the size of the returned {@code ImmutableSet}, then the unique elements of
147    * {@code elements} will be in the first {@code k} positions, and {@code elements[i] == null} for
148    * {@code k <= i < n}.
149    *
150    * <p>This may modify {@code elements}.  Additionally, if {@code n == elements.length} and
151    * {@code elements} contains no duplicates, {@code elements} may be used without copying in the
152    * returned {@code ImmutableSet}, in which case it may no longer be modified.
153    *
154    * <p>{@code elements} may contain only values of type {@code E}.
155    *
156    * @throws NullPointerException if any of the first {@code n} elements of {@code elements} is
157    *          null
158    */
159   private static <E> ImmutableSet<E> construct(int n, Object... elements) {
160     switch (n) {
161       case 0:
162         return of();
163       case 1:
164         @SuppressWarnings("unchecked") // safe; elements contains only E's
165         E elem = (E) elements[0];
166         return of(elem);
167       default:
168         // continue below to handle the general case
169     }
170     int tableSize = chooseTableSize(n);
171     Object[] table = new Object[tableSize];
172     int mask = tableSize - 1;
173     int hashCode = 0;
174     int uniques = 0;
175     for (int i = 0; i < n; i++) {
176       Object element = checkElementNotNull(elements[i], i);
177       int hash = element.hashCode();
178       for (int j = Hashing.smear(hash); ; j++) {
179         int index = j & mask;
180         Object value = table[index];
181         if (value == null) {
182           // Came to an empty slot. Put the element here.
183           elements[uniques++] = element;
184           table[index] = element;
185           hashCode += hash;
186           break;
187         } else if (value.equals(element)) {
188           break;
189         }
190       }
191     }
192     Arrays.fill(elements, uniques, n, null);
193     if (uniques == 1) {
194       // There is only one element or elements are all duplicates
195       @SuppressWarnings("unchecked") // we are careful to only pass in E
196       E element = (E) elements[0];
197       return new SingletonImmutableSet<E>(element, hashCode);
198     } else if (tableSize != chooseTableSize(uniques)) {
199       // Resize the table when the array includes too many duplicates.
200       // when this happens, we have already made a copy
201       return construct(uniques, elements);
202     } else {
203       Object[] uniqueElements =
204           (uniques < elements.length) ? Arrays.copyOf(elements, uniques) : elements;
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 = Ints.MAX_POWER_OF_TWO;
211 
212   // Represents how tightly we can pack things, as a maximum.
213   private static final double DESIRED_LOAD_FACTOR = 0.7;
214 
215   // If the set has this many elements, it will "max out" the table size
216   private static final int CUTOFF = (int) (MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR);
217 
218   /**
219    * Returns an array size suitable for the backing array of a hash table that uses open addressing
220    * with linear probing in its implementation. The returned size is the smallest power of two that
221    * can hold setSize elements with the desired load factor.  Always returns at least setSize + 2.
222    */
223   @VisibleForTesting
224   static int chooseTableSize(int setSize) {
225     setSize = Math.max(setSize, 2);
226     // Correct the size for open addressing to match desired load factor.
227     if (setSize < CUTOFF) {
228       // Round up to the next highest power of 2.
229       int tableSize = Integer.highestOneBit(setSize - 1) << 1;
230       while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
231         tableSize <<= 1;
232       }
233       return tableSize;
234     }
235 
236     // The table can't be completely full or we'll get infinite reprobes
237     checkArgument(setSize < MAX_TABLE_SIZE, "collection too large");
238     return MAX_TABLE_SIZE;
239   }
240 
241   /**
242    * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
243    * each appears first in the source collection.
244    *
245    * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation
246    * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} will copy the data only once.
247    * This reduces the expense of habitually making defensive copies at API boundaries. However, the
248    * precise conditions for skipping the copy operation are undefined.
249    *
250    * @throws NullPointerException if any of {@code elements} is null
251    * @since 7.0 (source-compatible since 2.0)
252    */
253   public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) {
254     /*
255      * TODO(lowasser): consider checking for ImmutableAsList here
256      * TODO(lowasser): consider checking for Multiset here
257      */
258     // Don't refer to ImmutableSortedSet by name so it won't pull in all that code
259     if (elements instanceof ImmutableSet && !(elements instanceof SortedSet)) {
260       @SuppressWarnings("unchecked") // all supported methods are covariant
261       ImmutableSet<E> set = (ImmutableSet<E>) elements;
262       if (!set.isPartialView()) {
263         return set;
264       }
265     } else if (elements instanceof EnumSet) {
266       return copyOfEnumSet((EnumSet) elements);
267     }
268     Object[] array = elements.toArray();
269     return construct(array.length, array);
270   }
271 
272   /**
273    * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
274    * each appears first in the source iterable. This method iterates over {@code elements} only
275    * once.
276    *
277    * <p><b>Performance note:</b> This method will sometimes recognize that the actual copy operation
278    * is unnecessary; for example, {@code copyOf(copyOf(anArrayList))} should copy the data only
279    * once. This reduces the expense of habitually making defensive copies at API boundaries.
280    * However, the precise conditions for skipping the copy operation are undefined.
281    *
282    * @throws NullPointerException if any of {@code elements} is null
283    */
284   public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) {
285     return (elements instanceof Collection)
286         ? copyOf((Collection<? extends E>) elements)
287         : copyOf(elements.iterator());
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 iterator.
293    *
294    * @throws NullPointerException if any of {@code elements} is null
295    */
296   public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) {
297     // We special-case for 0 or 1 elements, but anything further is madness.
298     if (!elements.hasNext()) {
299       return of();
300     }
301     E first = elements.next();
302     if (!elements.hasNext()) {
303       return of(first);
304     } else {
305       return new ImmutableSet.Builder<E>().add(first).addAll(elements).build();
306     }
307   }
308 
309   /**
310    * Returns an immutable set containing each of {@code elements}, minus duplicates, in the order
311    * each appears first in the source array.
312    *
313    * @throws NullPointerException if any of {@code elements} is null
314    * @since 3.0
315    */
316   public static <E> ImmutableSet<E> copyOf(E[] elements) {
317     switch (elements.length) {
318       case 0:
319         return of();
320       case 1:
321         return of(elements[0]);
322       default:
323         return construct(elements.length, elements.clone());
324     }
325   }
326 
327   @SuppressWarnings("rawtypes") // necessary to compile against Java 8
328   private static ImmutableSet copyOfEnumSet(EnumSet enumSet) {
329     return ImmutableEnumSet.asImmutable(EnumSet.copyOf(enumSet));
330   }
331 
332   ImmutableSet() {}
333 
334   /** Returns {@code true} if the {@code hashCode()} method runs quickly. */
335   boolean isHashCodeFast() {
336     return false;
337   }
338 
339   @Override
340   public boolean equals(@Nullable Object object) {
341     if (object == this) {
342       return true;
343     } else if (object instanceof ImmutableSet
344         && isHashCodeFast()
345         && ((ImmutableSet<?>) object).isHashCodeFast()
346         && hashCode() != object.hashCode()) {
347       return false;
348     }
349     return Sets.equalsImpl(this, object);
350   }
351 
352   @Override
353   public int hashCode() {
354     return Sets.hashCodeImpl(this);
355   }
356 
357   // This declaration is needed to make Set.iterator() and
358   // ImmutableCollection.iterator() consistent.
359   @Override
360   public abstract UnmodifiableIterator<E> iterator();
361 
362   @LazyInit
363   @RetainedWith
364   private transient ImmutableList<E> asList;
365 
366   @Override
367   public ImmutableList<E> asList() {
368     ImmutableList<E> result = asList;
369     return (result == null) ? asList = createAsList() : result;
370   }
371 
372   ImmutableList<E> createAsList() {
373     return new RegularImmutableAsList<E>(this, toArray());
374   }
375 
376   abstract static class Indexed<E> extends ImmutableSet<E> {
377     abstract E get(int index);
378 
379     @Override
380     public UnmodifiableIterator<E> iterator() {
381       return asList().iterator();
382     }
383 
384     @Override
385     public Spliterator<E> spliterator() {
386       return CollectSpliterators.indexed(size(), SPLITERATOR_CHARACTERISTICS, this::get);
387     }
388 
389     @Override
390     public void forEach(Consumer<? super E> consumer) {
391       checkNotNull(consumer);
392       int n = size();
393       for (int i = 0; i < n; i++) {
394         consumer.accept(get(i));
395       }
396     }
397 
398     @Override
399     ImmutableList<E> createAsList() {
400       return new ImmutableAsList<E>() {
401         @Override
402         public E get(int index) {
403           return Indexed.this.get(index);
404         }
405 
406         @Override
407         Indexed<E> delegateCollection() {
408           return Indexed.this;
409         }
410       };
411     }
412   }
413 
414   /*
415    * This class is used to serialize all ImmutableSet instances, except for
416    * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
417    * captures their "logical contents" and they are reconstructed using public
418    * static factories. This is necessary to ensure that the existence of a
419    * particular implementation type is an implementation detail.
420    */
421   private static class SerializedForm implements Serializable {
422     final Object[] elements;
423 
424     SerializedForm(Object[] elements) {
425       this.elements = elements;
426     }
427 
428     Object readResolve() {
429       return copyOf(elements);
430     }
431 
432     private static final long serialVersionUID = 0;
433   }
434 
435   @Override
436   Object writeReplace() {
437     return new SerializedForm(toArray());
438   }
439 
440   /**
441    * Returns a new builder. The generated builder is equivalent to the builder
442    * created by the {@link Builder} constructor.
443    */
444   public static <E> Builder<E> builder() {
445     return new Builder<E>();
446   }
447 
448   /**
449    * Returns a new builder, expecting the specified number of distinct elements to be added.
450    *
451    * <p>If {@code expectedSize} is exactly the number of distinct elements added to the builder
452    * before {@link Builder#build} is called, the builder is likely to perform better than an unsized
453    * {@link #builder()} would have.
454    *
455    * <p>It is not specified if any performance benefits apply if {@code expectedSize} is close to,
456    * but not exactly, the number of distinct elements added to the builder.
457    *
458    * @since 23.1
459    */
460   @Beta
461   public static <E> Builder<E> builderWithExpectedSize(int expectedSize) {
462     checkNonnegative(expectedSize, "expectedSize");
463     return new Builder<E>(expectedSize);
464   }
465 
466   /**
467    * A builder for creating {@code ImmutableSet} instances. Example: <pre>   {@code
468    *
469    *   static final ImmutableSet<Color> GOOGLE_COLORS =
470    *       ImmutableSet.<Color>builder()
471    *           .addAll(WEBSAFE_COLORS)
472    *           .add(new Color(0, 191, 255))
473    *           .build();}</pre>
474    *
475    * <p>Elements appear in the resulting set in the same order they were first added to the builder.
476    *
477    * <p>Building does not change the state of the builder, so it is still possible to add more
478    * elements and to build again.
479    *
480    * @since 2.0
481    */
482   public static class Builder<E> extends ImmutableCollection.ArrayBasedBuilder<E> {
483     @VisibleForTesting
484     Object[] hashTable;
485     private int hashCode;
486     
487     /**
488      * Creates a new builder. The returned builder is equivalent to the builder
489      * generated by {@link ImmutableSet#builder}.
490      */
491     public Builder() {
492       super(DEFAULT_INITIAL_CAPACITY);
493     }
494 
495     Builder(int capacity) {
496       super(capacity);
497       this.hashTable = new Object[chooseTableSize(capacity)];
498     }
499 
500     /**
501      * Adds {@code element} to the {@code ImmutableSet}.  If the {@code
502      * ImmutableSet} already contains {@code element}, then {@code add} has no
503      * effect (only the previously added element is retained).
504      *
505      * @param element the element to add
506      * @return this {@code Builder} object
507      * @throws NullPointerException if {@code element} is null
508      */
509     @CanIgnoreReturnValue
510     @Override
511     public Builder<E> add(E element) {
512       checkNotNull(element);
513       if (hashTable != null && chooseTableSize(size) <= hashTable.length) {
514         addDeduping(element);
515         return this;
516       } else {
517         hashTable = null;
518         super.add(element);
519         return this;
520       }
521     }
522     
523     private void addDeduping(E element) {
524       int mask = hashTable.length - 1;
525       int hash = element.hashCode();
526       for (int i = Hashing.smear(hash); ; i++) {
527         i &= mask;
528         Object previous = hashTable[i];
529         if (previous == null) {
530           hashTable[i] = element;
531           hashCode += hash;
532           super.add(element);
533           return;
534         } else if (previous.equals(element)) {
535           return;
536         }
537       }
538     }
539 
540     /**
541      * Adds each element of {@code elements} to the {@code ImmutableSet},
542      * ignoring duplicate elements (only the first duplicate element is added).
543      *
544      * @param elements the elements to add
545      * @return this {@code Builder} object
546      * @throws NullPointerException if {@code elements} is null or contains a
547      *     null element
548      */
549     @CanIgnoreReturnValue
550     @Override
551     public Builder<E> add(E... elements) {
552       if (hashTable != null) {
553         for (E e : elements) {
554           add(e);
555         }
556       } else {
557         super.add(elements);
558       }
559       return this;
560     }
561 
562     /**
563      * Adds each element of {@code elements} to the {@code ImmutableSet},
564      * ignoring duplicate elements (only the first duplicate element is added).
565      *
566      * @param elements the {@code Iterable} to add to the {@code ImmutableSet}
567      * @return this {@code Builder} object
568      * @throws NullPointerException if {@code elements} is null or contains a
569      *     null element
570      */
571     @CanIgnoreReturnValue
572     @Override
573     public Builder<E> addAll(Iterable<? extends E> elements) {
574       checkNotNull(elements);
575       if (hashTable != null) {
576         for (E e : elements) {
577           add(e);
578         }
579       } else {
580         super.addAll(elements);
581       }
582       return this;
583     }
584 
585     /**
586      * Adds each element of {@code elements} to the {@code ImmutableSet},
587      * ignoring duplicate elements (only the first duplicate element is added).
588      *
589      * @param elements the elements to add to the {@code ImmutableSet}
590      * @return this {@code Builder} object
591      * @throws NullPointerException if {@code elements} is null or contains a
592      *     null element
593      */
594     @CanIgnoreReturnValue
595     @Override
596     public Builder<E> addAll(Iterator<? extends E> elements) {
597       checkNotNull(elements);
598       while (elements.hasNext()) {
599         add(elements.next());
600       }
601       return this;
602     }
603 
604     @SuppressWarnings("unchecked")
605     @CanIgnoreReturnValue
606     @Override
607     Builder<E> combine(ArrayBasedBuilder<E> builder) {
608       if (hashTable != null
609           && builder instanceof Builder) {
610         for (int i = 0; i < builder.size; i++) {
611           addDeduping((E) builder.contents[i]);
612         }
613       } else {
614         super.combine(builder);
615       }
616       return this;
617     }
618 
619     /**
620      * Returns a newly-created {@code ImmutableSet} based on the contents of
621      * the {@code Builder}.
622      */
623     @SuppressWarnings("unchecked")
624     @Override
625     public ImmutableSet<E> build() {
626       switch (size) {
627         case 0:
628           return of();
629         case 1:
630           return (ImmutableSet<E>) of(contents[0]);
631         default:
632           ImmutableSet<E> result;
633           if (hashTable != null && size == contents.length) {
634             result =
635                 new RegularImmutableSet<E>(contents, hashCode, hashTable, hashTable.length - 1);
636           } else {
637             result = construct(size, contents);
638             // construct has the side effect of deduping contents, so we update size
639             // accordingly.
640             size = result.size();
641           }
642           forceCopy = true;
643           hashTable = null;
644           return result;
645       }
646     }
647   }
648 }