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.ArrayList;
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(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(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(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(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 for (int i = paramCount; i < elements.length; i++) {
159 elements[i] = others[i - paramCount];
160 }
161 return construct(elements);
162 }
163
164 /** {@code elements} has to be internally created array. */
165 private static <E> ImmutableSet<E> construct(Object... elements) {
166 int tableSize = chooseTableSize(elements.length);
167 Object[] table = new Object[tableSize];
168 int mask = tableSize - 1;
169 ArrayList<Object> uniqueElementsList = null;
170 int hashCode = 0;
171 for (int i = 0; i < elements.length; i++) {
172 Object element = elements[i];
173 int hash = element.hashCode();
174 for (int j = Hashing.smear(hash); ; j++) {
175 int index = j & mask;
176 Object value = table[index];
177 if (value == null) {
178 if (uniqueElementsList != null) {
179 uniqueElementsList.add(element);
180 }
181 // Came to an empty slot. Put the element here.
182 table[index] = element;
183 hashCode += hash;
184 break;
185 } else if (value.equals(element)) {
186 if (uniqueElementsList == null) {
187 // first dup
188 uniqueElementsList = new ArrayList<Object>(elements.length);
189 for (int k = 0; k < i; k++) {
190 Object previous = elements[k];
191 uniqueElementsList.add(previous);
192 }
193 }
194 break;
195 }
196 }
197 }
198 Object[] uniqueElements = uniqueElementsList == null
199 ? elements
200 : uniqueElementsList.toArray();
201 if (uniqueElements.length == 1) {
202 // There is only one element or elements are all duplicates
203 @SuppressWarnings("unchecked") // we are careful to only pass in E
204 E element = (E) uniqueElements[0];
205 return new SingletonImmutableSet<E>(element, hashCode);
206 } else if (tableSize != chooseTableSize(uniqueElements.length)) {
207 // Resize the table when the array includes too many duplicates.
208 // when this happens, we have already made a copy
209 return construct(uniqueElements);
210 } else {
211 return new RegularImmutableSet<E>(uniqueElements, hashCode, table, mask);
212 }
213 }
214
215 // We use power-of-2 tables, and this is the highest int that's a power of 2
216 static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO;
217
218 // Represents how tightly we can pack things, as a maximum.
219 private static final double DESIRED_LOAD_FACTOR = 0.7;
220
221 // If the set has this many elements, it will "max out" the table size
222 private static final int CUTOFF = (int) Math.floor(MAX_TABLE_SIZE * DESIRED_LOAD_FACTOR);
223
224 /**
225 * Returns an array size suitable for the backing array of a hash table that
226 * uses open addressing with linear probing in its implementation. The
227 * returned size is the smallest power of two that can hold setSize elements
228 * with the desired load factor.
229 *
230 * <p>Do not call this method with setSize < 2.
231 */
232 @VisibleForTesting static int chooseTableSize(int setSize) {
233 // Correct the size for open addressing to match desired load factor.
234 if (setSize < CUTOFF) {
235 // Round up to the next highest power of 2.
236 int tableSize = Integer.highestOneBit(setSize - 1) << 1;
237 while (tableSize * DESIRED_LOAD_FACTOR < setSize) {
238 tableSize <<= 1;
239 }
240 return tableSize;
241 }
242
243 // The table can't be completely full or we'll get infinite reprobes
244 checkArgument(setSize < MAX_TABLE_SIZE, "collection too large");
245 return MAX_TABLE_SIZE;
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 ImmutableCollection<D> source;
466 final int hashCode;
467
468 TransformedImmutableSet(ImmutableCollection<D> source) {
469 this.source = source;
470 this.hashCode = Sets.hashCodeImpl(this);
471 }
472
473 TransformedImmutableSet(ImmutableCollection<D> source, int hashCode) {
474 this.source = source;
475 this.hashCode = hashCode;
476 }
477
478 abstract E transform(D element);
479
480 @Override
481 public int size() {
482 return source.size();
483 }
484
485 @Override public boolean isEmpty() {
486 return false;
487 }
488
489 @Override public UnmodifiableIterator<E> iterator() {
490 final Iterator<D> backingIterator = source.iterator();
491 return new UnmodifiableIterator<E>() {
492 @Override
493 public boolean hasNext() {
494 return backingIterator.hasNext();
495 }
496
497 @Override
498 public E next() {
499 return transform(backingIterator.next());
500 }
501 };
502 }
503
504 @Override public Object[] toArray() {
505 return toArray(new Object[size()]);
506 }
507
508 @Override public <T> T[] toArray(T[] array) {
509 int size = size();
510 if (array.length < size) {
511 array = ObjectArrays.newArray(array, size);
512 } else if (array.length > size) {
513 array[size] = null;
514 }
515
516 // Writes will produce ArrayStoreException when the toArray() doc requires
517 Object[] objectArray = array;
518 int i = 0;
519 for (D d : source) {
520 objectArray[i++] = transform(d);
521 }
522 return array;
523 }
524
525 @Override public final int hashCode() {
526 return hashCode;
527 }
528
529 @Override boolean isHashCodeFast() {
530 return true;
531 }
532 }
533
534 /*
535 * This class is used to serialize all ImmutableSet instances, except for
536 * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
537 * captures their "logical contents" and they are reconstructed using public
538 * static factories. This is necessary to ensure that the existence of a
539 * particular implementation type is an implementation detail.
540 */
541 private static class SerializedForm implements Serializable {
542 final Object[] elements;
543 SerializedForm(Object[] elements) {
544 this.elements = elements;
545 }
546 Object readResolve() {
547 return copyOf(elements);
548 }
549 private static final long serialVersionUID = 0;
550 }
551
552 @Override Object writeReplace() {
553 return new SerializedForm(toArray());
554 }
555
556 /**
557 * Returns a new builder. The generated builder is equivalent to the builder
558 * created by the {@link Builder} constructor.
559 */
560 public static <E> Builder<E> builder() {
561 return new Builder<E>();
562 }
563
564 /**
565 * A builder for creating immutable set instances, especially {@code public
566 * static final} sets ("constant sets"). Example: <pre> {@code
567 *
568 * public static final ImmutableSet<Color> GOOGLE_COLORS =
569 * new ImmutableSet.Builder<Color>()
570 * .addAll(WEBSAFE_COLORS)
571 * .add(new Color(0, 191, 255))
572 * .build();}</pre>
573 *
574 * Builder instances can be reused; it is safe to call {@link #build} multiple
575 * times to build multiple sets in series. Each set is a superset of the set
576 * created before it.
577 *
578 * @since 2.0 (imported from Google Collections Library)
579 */
580 public static class Builder<E> extends ImmutableCollection.Builder<E> {
581 // accessed directly by ImmutableSortedSet
582 final ArrayList<E> contents = Lists.newArrayList();
583
584 /**
585 * Creates a new builder. The returned builder is equivalent to the builder
586 * generated by {@link ImmutableSet#builder}.
587 */
588 public Builder() {}
589
590 /**
591 * Adds {@code element} to the {@code ImmutableSet}. If the {@code
592 * ImmutableSet} already contains {@code element}, then {@code add} has no
593 * effect (only the previously added element is retained).
594 *
595 * @param element the element to add
596 * @return this {@code Builder} object
597 * @throws NullPointerException if {@code element} is null
598 */
599 @Override public Builder<E> add(E element) {
600 contents.add(checkNotNull(element));
601 return this;
602 }
603
604 /**
605 * Adds each element of {@code elements} to the {@code ImmutableSet},
606 * ignoring duplicate elements (only the first duplicate element is added).
607 *
608 * @param elements the elements to add
609 * @return this {@code Builder} object
610 * @throws NullPointerException if {@code elements} is null or contains a
611 * null element
612 */
613 @Override public Builder<E> add(E... elements) {
614 contents.ensureCapacity(contents.size() + elements.length);
615 super.add(elements);
616 return this;
617 }
618
619 /**
620 * Adds each element of {@code elements} to the {@code ImmutableSet},
621 * ignoring duplicate elements (only the first duplicate element is added).
622 *
623 * @param elements the {@code Iterable} to add to the {@code ImmutableSet}
624 * @return this {@code Builder} object
625 * @throws NullPointerException if {@code elements} is null or contains a
626 * null element
627 */
628 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
629 if (elements instanceof Collection) {
630 Collection<?> collection = (Collection<?>) elements;
631 contents.ensureCapacity(contents.size() + collection.size());
632 }
633 super.addAll(elements);
634 return this;
635 }
636
637 /**
638 * Adds each element of {@code elements} to the {@code ImmutableSet},
639 * ignoring duplicate elements (only the first duplicate element is added).
640 *
641 * @param elements the elements to add to the {@code ImmutableSet}
642 * @return this {@code Builder} object
643 * @throws NullPointerException if {@code elements} is null or contains a
644 * null element
645 */
646 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
647 super.addAll(elements);
648 return this;
649 }
650
651 /**
652 * Returns a newly-created {@code ImmutableSet} based on the contents of
653 * the {@code Builder}.
654 */
655 @Override public ImmutableSet<E> build() {
656 return copyOf(contents);
657 }
658 }
659 }