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 }