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