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
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 @Override
401 public int size() {
402 return elements.length;
403 }
404
405 @Override public boolean isEmpty() {
406 return false;
407 }
408
409 /*
410 * The cast is safe because the only way to create an instance is via the
411 * create() method above, which only permits elements of type E.
412 */
413 @SuppressWarnings("unchecked")
414 @Override public UnmodifiableIterator<E> iterator() {
415 return (UnmodifiableIterator<E>) Iterators.forArray(elements);
416 }
417
418 @Override public Object[] toArray() {
419 Object[] array = new Object[size()];
420 System.arraycopy(elements, 0, array, 0, size());
421 return array;
422 }
423
424 @Override public <T> T[] toArray(T[] array) {
425 int size = size();
426 if (array.length < size) {
427 array = ObjectArrays.newArray(array, size);
428 } else if (array.length > size) {
429 array[size] = null;
430 }
431 System.arraycopy(elements, 0, array, 0, size);
432 return array;
433 }
434
435 @Override public boolean containsAll(Collection<?> targets) {
436 if (targets == this) {
437 return true;
438 }
439 if (!(targets instanceof ArrayImmutableSet)) {
440 return super.containsAll(targets);
441 }
442 if (targets.size() > size()) {
443 return false;
444 }
445 for (Object target : ((ArrayImmutableSet<?>) targets).elements) {
446 if (!contains(target)) {
447 return false;
448 }
449 }
450 return true;
451 }
452
453 @Override boolean isPartialView() {
454 return false;
455 }
456
457 @Override ImmutableList<E> createAsList() {
458 return new ImmutableAsList<E>(elements, this);
459 }
460 }
461
462 /** such as ImmutableMap.keySet() */
463 abstract static class TransformedImmutableSet<D, E> extends ImmutableSet<E> {
464 final D[] source;
465 final int hashCode;
466
467 TransformedImmutableSet(D[] source, int hashCode) {
468 this.source = source;
469 this.hashCode = hashCode;
470 }
471
472 abstract E transform(D element);
473
474 @Override
475 public int size() {
476 return source.length;
477 }
478
479 @Override public boolean isEmpty() {
480 return false;
481 }
482
483 @Override public UnmodifiableIterator<E> iterator() {
484 return new AbstractIndexedListIterator<E>(source.length) {
485 @Override protected E get(int index) {
486 return transform(source[index]);
487 }
488 };
489 }
490
491 @Override public Object[] toArray() {
492 return toArray(new Object[size()]);
493 }
494
495 @Override public <T> T[] toArray(T[] array) {
496 int size = size();
497 if (array.length < size) {
498 array = ObjectArrays.newArray(array, size);
499 } else if (array.length > size) {
500 array[size] = null;
501 }
502
503 // Writes will produce ArrayStoreException when the toArray() doc requires
504 Object[] objectArray = array;
505 for (int i = 0; i < source.length; i++) {
506 objectArray[i] = transform(source[i]);
507 }
508 return array;
509 }
510
511 @Override public final int hashCode() {
512 return hashCode;
513 }
514
515 @Override boolean isHashCodeFast() {
516 return true;
517 }
518 }
519
520 /*
521 * This class is used to serialize all ImmutableSet instances, except for
522 * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
523 * captures their "logical contents" and they are reconstructed using public
524 * static factories. This is necessary to ensure that the existence of a
525 * particular implementation type is an implementation detail.
526 */
527 private static class SerializedForm implements Serializable {
528 final Object[] elements;
529 SerializedForm(Object[] elements) {
530 this.elements = elements;
531 }
532 Object readResolve() {
533 return copyOf(elements);
534 }
535 private static final long serialVersionUID = 0;
536 }
537
538 @Override Object writeReplace() {
539 return new SerializedForm(toArray());
540 }
541
542 /**
543 * Returns a new builder. The generated builder is equivalent to the builder
544 * created by the {@link Builder} constructor.
545 */
546 public static <E> Builder<E> builder() {
547 return new Builder<E>();
548 }
549
550 /**
551 * A builder for creating immutable set instances, especially {@code public
552 * static final} sets ("constant sets"). Example: <pre> {@code
553 *
554 * public static final ImmutableSet<Color> GOOGLE_COLORS =
555 * new ImmutableSet.Builder<Color>()
556 * .addAll(WEBSAFE_COLORS)
557 * .add(new Color(0, 191, 255))
558 * .build();}</pre>
559 *
560 * Builder instances can be reused; it is safe to call {@link #build} multiple
561 * times to build multiple sets in series. Each set is a superset of the set
562 * created before it.
563 *
564 * @since 2 (imported from Google Collections Library)
565 */
566 public static class Builder<E> extends ImmutableCollection.Builder<E> {
567 // accessed directly by ImmutableSortedSet
568 final ArrayList<E> contents = Lists.newArrayList();
569
570 /**
571 * Creates a new builder. The returned builder is equivalent to the builder
572 * generated by {@link ImmutableSet#builder}.
573 */
574 public Builder() {}
575
576 /**
577 * Adds {@code element} to the {@code ImmutableSet}. If the {@code
578 * ImmutableSet} already contains {@code element}, then {@code add} has no
579 * effect (only the previously added element is retained).
580 *
581 * @param element the element to add
582 * @return this {@code Builder} object
583 * @throws NullPointerException if {@code element} is null
584 */
585 @Override public Builder<E> add(E element) {
586 contents.add(checkNotNull(element));
587 return this;
588 }
589
590 /**
591 * Adds each element of {@code elements} to the {@code ImmutableSet},
592 * ignoring duplicate elements (only the first duplicate element is added).
593 *
594 * @param elements the elements to add
595 * @return this {@code Builder} object
596 * @throws NullPointerException if {@code elements} is null or contains a
597 * null element
598 */
599 @Override public Builder<E> add(E... elements) {
600 contents.ensureCapacity(contents.size() + elements.length);
601 super.add(elements);
602 return this;
603 }
604
605 /**
606 * Adds each element of {@code elements} to the {@code ImmutableSet},
607 * ignoring duplicate elements (only the first duplicate element is added).
608 *
609 * @param elements the {@code Iterable} to add to the {@code ImmutableSet}
610 * @return this {@code Builder} object
611 * @throws NullPointerException if {@code elements} is null or contains a
612 * null element
613 */
614 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
615 if (elements instanceof Collection) {
616 Collection<?> collection = (Collection<?>) elements;
617 contents.ensureCapacity(contents.size() + collection.size());
618 }
619 super.addAll(elements);
620 return this;
621 }
622
623 /**
624 * Adds each element of {@code elements} to the {@code ImmutableSet},
625 * ignoring duplicate elements (only the first duplicate element is added).
626 *
627 * @param elements the elements to add to the {@code ImmutableSet}
628 * @return this {@code Builder} object
629 * @throws NullPointerException if {@code elements} is null or contains a
630 * null element
631 */
632 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
633 super.addAll(elements);
634 return this;
635 }
636
637 /**
638 * Returns a newly-created {@code ImmutableSet} based on the contents of
639 * the {@code Builder}.
640 */
641 @Override public ImmutableSet<E> build() {
642 return copyOf(contents);
643 }
644 }
645 }