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