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.checkNotNull;
020
021 import com.google.common.annotations.GwtCompatible;
022
023 import java.io.Serializable;
024 import java.util.ArrayList;
025 import java.util.Arrays;
026 import java.util.Collection;
027 import java.util.Collections;
028 import java.util.HashSet;
029 import java.util.Iterator;
030 import java.util.List;
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 (imported from Google Collections Library)
065 */
066 // TODO: benchmark and optimize all creation paths, which are a mess right now
067 @GwtCompatible(serializable = true, emulated = true)
068 @SuppressWarnings("serial") // we're overriding default serialization
069 public abstract class ImmutableSet<E> extends ImmutableCollection<E>
070 implements Set<E> {
071 /**
072 * Returns the empty immutable set. This set behaves and performs comparably
073 * to {@link Collections#emptySet}, and is preferable mainly for consistency
074 * and maintainability of your code.
075 */
076 // Casting to any type is safe because the set will never hold any elements.
077 @SuppressWarnings({"unchecked"})
078 public static <E> ImmutableSet<E> of() {
079 return (ImmutableSet<E>) EmptyImmutableSet.INSTANCE;
080 }
081
082 /**
083 * Returns an immutable set containing a single element. This set behaves and
084 * performs comparably to {@link Collections#singleton}, but will not accept
085 * a null element. It is preferable mainly for consistency and
086 * maintainability of your code.
087 */
088 public static <E> ImmutableSet<E> of(E element) {
089 return new SingletonImmutableSet<E>(element);
090 }
091
092 /**
093 * Returns an immutable set containing the given elements, in order. Repeated
094 * occurrences of an element (according to {@link Object#equals}) after the
095 * first are ignored.
096 *
097 * @throws NullPointerException if any element is null
098 */
099 @SuppressWarnings("unchecked")
100 public static <E> ImmutableSet<E> of(E e1, E e2) {
101 return create(e1, e2);
102 }
103
104 /**
105 * Returns an immutable set containing the given elements, in order. Repeated
106 * occurrences of an element (according to {@link Object#equals}) after the
107 * first are ignored.
108 *
109 * @throws NullPointerException if any element is null
110 */
111 @SuppressWarnings("unchecked")
112 public static <E> ImmutableSet<E> of(E e1, E e2, E e3) {
113 return create(e1, e2, e3);
114 }
115
116 /**
117 * Returns an immutable set containing the given elements, in order. Repeated
118 * occurrences of an element (according to {@link Object#equals}) after the
119 * first are ignored.
120 *
121 * @throws NullPointerException if any element is null
122 */
123 @SuppressWarnings("unchecked")
124 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) {
125 return create(e1, e2, e3, e4);
126 }
127
128 /**
129 * Returns an immutable set containing the given elements, in order. Repeated
130 * occurrences of an element (according to {@link Object#equals}) after the
131 * first are ignored.
132 *
133 * @throws NullPointerException if any element is null
134 */
135 @SuppressWarnings("unchecked")
136 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) {
137 return create(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 (source-compatible since release 2)
147 */
148 @SuppressWarnings("unchecked")
149 public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6,
150 E... others) {
151 int size = others.length + 6;
152 List<E> all = new ArrayList<E>(size);
153 Collections.addAll(all, e1, e2, e3, e4, e5, e6);
154 Collections.addAll(all, others);
155 return create(all, size);
156 }
157
158 /**
159 * Returns an immutable set containing the given elements, in order. Repeated
160 * occurrences of an element (according to {@link Object#equals}) after the
161 * first are ignored.
162 *
163 * @deprecated use {@link #copyOf(Object[])}.
164 * @throws NullPointerException if any of {@code elements} is null
165 * @since 2 (changed from varargs in release 3)
166 */
167 // TODO: when this is removed, remember to remove from ISS and ISSFS too
168 @Deprecated
169 public static <E> ImmutableSet<E> of(E[] elements) {
170 return copyOf(elements);
171 }
172
173 /**
174 * Returns an immutable set containing the given elements, in order. Repeated
175 * occurrences of an element (according to {@link Object#equals}) after the
176 * first are ignored.
177 *
178 * @throws NullPointerException if any of {@code elements} is null
179 * @since 3
180 */
181 public static <E> ImmutableSet<E> copyOf(E[] elements) {
182 switch (elements.length) {
183 case 0:
184 return of();
185 case 1:
186 return of(elements[0]);
187 default:
188 return create(elements);
189 }
190 }
191
192 /**
193 * Returns an immutable set containing the given elements, in order. Repeated
194 * occurrences of an element (according to {@link Object#equals}) after the
195 * first are ignored. This method iterates over {@code elements} at most
196 * once.
197 *
198 * <p>Note that if {@code s} is a {@code Set<String>}, then {@code
199 * ImmutableSet.copyOf(s)} returns an {@code ImmutableSet<String>} containing
200 * each of the strings in {@code s}, while {@code ImmutableSet.of(s)} returns
201 * a {@code ImmutableSet<Set<String>>} containing one element (the given set
202 * itself).
203 *
204 * <p><b>Note:</b> Despite what the method name suggests, if {@code elements}
205 * is an {@code ImmutableSet} (but not an {@code ImmutableSortedSet}), no copy
206 * will actually be performed, and the given set itself will be returned.
207 *
208 * @throws NullPointerException if any of {@code elements} is null
209 */
210 public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) {
211 if (elements instanceof ImmutableSet
212 && !(elements instanceof ImmutableSortedSet)) {
213 @SuppressWarnings("unchecked") // all supported methods are covariant
214 ImmutableSet<E> set = (ImmutableSet<E>) elements;
215 return set;
216 }
217 return copyOfInternal(Collections2.toCollection(elements));
218 }
219
220 /**
221 * Returns an immutable set containing the given elements, in order. Repeated
222 * occurrences of an element (according to {@link Object#equals}) after the
223 * first are ignored.
224 *
225 * @throws NullPointerException if any of {@code elements} is null
226 */
227 public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) {
228 Collection<E> list = Lists.newArrayList(elements);
229 return copyOfInternal(list);
230 }
231
232 private static <E> ImmutableSet<E> copyOfInternal(
233 Collection<? extends E> collection) {
234 // TODO: Support concurrent collections that change while this method is
235 // running.
236 switch (collection.size()) {
237 case 0:
238 return of();
239 case 1:
240 // TODO: Remove "ImmutableSet.<E>" when eclipse bug is fixed.
241 return ImmutableSet.<E>of(collection.iterator().next());
242 default:
243 return create(collection, collection.size());
244 }
245 }
246
247 ImmutableSet() {}
248
249 /** Returns {@code true} if the {@code hashCode()} method runs quickly. */
250 boolean isHashCodeFast() {
251 return false;
252 }
253
254 @Override public boolean equals(@Nullable Object object) {
255 if (object == this) {
256 return true;
257 }
258 if (object instanceof ImmutableSet
259 && isHashCodeFast()
260 && ((ImmutableSet<?>) object).isHashCodeFast()
261 && hashCode() != object.hashCode()) {
262 return false;
263 }
264 return Collections2.setEquals(this, object);
265 }
266
267 @Override public int hashCode() {
268 int hashCode = 0;
269 for (Object o : this) {
270 hashCode += o.hashCode();
271 }
272 return hashCode;
273 }
274
275 // This declaration is needed to make Set.iterator() and
276 // ImmutableCollection.iterator() consistent.
277 @Override public abstract UnmodifiableIterator<E> iterator();
278
279 private static <E> ImmutableSet<E> create(E... elements) {
280 return create(Arrays.asList(elements), elements.length);
281 }
282
283 private static <E> ImmutableSet<E> create(
284 Iterable<? extends E> iterable, int count) {
285 // count is always the (nonzero) number of elements in the iterable
286 int tableSize = Hashing.chooseTableSize(count);
287 Object[] table = new Object[tableSize];
288 int mask = tableSize - 1;
289
290 List<E> elements = new ArrayList<E>(count);
291 int hashCode = 0;
292
293 for (E element : iterable) {
294 int hash = element.hashCode();
295 for (int i = Hashing.smear(hash); true; i++) {
296 int index = i & mask;
297 Object value = table[index];
298 if (value == null) {
299 // Came to an empty bucket. Put the element here.
300 table[index] = element;
301 elements.add(element);
302 hashCode += hash;
303 break;
304 } else if (value.equals(element)) {
305 break; // Found a duplicate. Nothing to do.
306 }
307 }
308 }
309
310 if (elements.size() == 1) {
311 // The iterable contained only duplicates of the same element.
312 return new SingletonImmutableSet<E>(elements.get(0), hashCode);
313 } else if (tableSize > Hashing.chooseTableSize(elements.size())) {
314 // Resize the table when the iterable includes too many duplicates.
315 return create(elements, elements.size());
316 } else {
317 return new RegularImmutableSet<E>(
318 elements.toArray(), hashCode, table, mask);
319 }
320 }
321
322 abstract static class ArrayImmutableSet<E> extends ImmutableSet<E> {
323 // the elements (two or more) in the desired order.
324 final transient Object[] elements;
325
326 ArrayImmutableSet(Object[] elements) {
327 this.elements = elements;
328 }
329
330 public int size() {
331 return elements.length;
332 }
333
334 @Override public boolean isEmpty() {
335 return false;
336 }
337
338 /*
339 * The cast is safe because the only way to create an instance is via the
340 * create() method above, which only permits elements of type E.
341 */
342 @SuppressWarnings("unchecked")
343 @Override public UnmodifiableIterator<E> iterator() {
344 return (UnmodifiableIterator<E>) Iterators.forArray(elements);
345 }
346
347 @Override public Object[] toArray() {
348 Object[] array = new Object[size()];
349 System.arraycopy(elements, 0, array, 0, size());
350 return array;
351 }
352
353 @Override public <T> T[] toArray(T[] array) {
354 int size = size();
355 if (array.length < size) {
356 array = ObjectArrays.newArray(array, size);
357 } else if (array.length > size) {
358 array[size] = null;
359 }
360 System.arraycopy(elements, 0, array, 0, size);
361 return array;
362 }
363
364 @Override public boolean containsAll(Collection<?> targets) {
365 if (targets == this) {
366 return true;
367 }
368 if (!(targets instanceof ArrayImmutableSet)) {
369 return super.containsAll(targets);
370 }
371 if (targets.size() > size()) {
372 return false;
373 }
374 for (Object target : ((ArrayImmutableSet<?>) targets).elements) {
375 if (!contains(target)) {
376 return false;
377 }
378 }
379 return true;
380 }
381
382 @Override ImmutableList<E> createAsList() {
383 return new ImmutableAsList<E>(elements, this);
384 }
385 }
386
387 /** such as ImmutableMap.keySet() */
388 abstract static class TransformedImmutableSet<D, E> extends ImmutableSet<E> {
389 final D[] source;
390 final int hashCode;
391
392 TransformedImmutableSet(D[] source, int hashCode) {
393 this.source = source;
394 this.hashCode = hashCode;
395 }
396
397 abstract E transform(D element);
398
399 public int size() {
400 return source.length;
401 }
402
403 @Override public boolean isEmpty() {
404 return false;
405 }
406
407 @Override public UnmodifiableIterator<E> iterator() {
408 return new AbstractIterator<E>() {
409 int index = 0;
410 @Override protected E computeNext() {
411 return index < source.length
412 ? transform(source[index++])
413 : endOfData();
414 }
415 };
416 }
417
418 @Override public Object[] toArray() {
419 return toArray(new Object[size()]);
420 }
421
422 @Override public <T> T[] toArray(T[] array) {
423 int size = size();
424 if (array.length < size) {
425 array = ObjectArrays.newArray(array, size);
426 } else if (array.length > size) {
427 array[size] = null;
428 }
429
430 // Writes will produce ArrayStoreException when the toArray() doc requires
431 Object[] objectArray = array;
432 for (int i = 0; i < source.length; i++) {
433 objectArray[i] = transform(source[i]);
434 }
435 return array;
436 }
437
438 @Override public final int hashCode() {
439 return hashCode;
440 }
441
442 @Override boolean isHashCodeFast() {
443 return true;
444 }
445 }
446
447 /*
448 * This class is used to serialize all ImmutableSet instances, except for
449 * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It
450 * captures their "logical contents" and they are reconstructed using public
451 * static factories. This is necessary to ensure that the existence of a
452 * particular implementation type is an implementation detail.
453 */
454 private static class SerializedForm implements Serializable {
455 final Object[] elements;
456 SerializedForm(Object[] elements) {
457 this.elements = elements;
458 }
459 Object readResolve() {
460 return copyOf(elements);
461 }
462 private static final long serialVersionUID = 0;
463 }
464
465 @Override Object writeReplace() {
466 return new SerializedForm(toArray());
467 }
468
469 /**
470 * Returns a new builder. The generated builder is equivalent to the builder
471 * created by the {@link Builder} constructor.
472 */
473 public static <E> Builder<E> builder() {
474 return new Builder<E>();
475 }
476
477 /**
478 * A builder for creating immutable set instances, especially
479 * {@code public static final} sets ("constant sets").
480 *
481 * <p>Example:
482 * <pre>{@code
483 * public static final ImmutableSet<Color> GOOGLE_COLORS
484 * = new ImmutableSet.Builder<Color>()
485 * .addAll(WEBSAFE_COLORS)
486 * .add(new Color(0, 191, 255))
487 * .build();}</pre>
488 *
489 * <p>Builder instances can be reused - it is safe to call {@link #build}
490 * multiple times to build multiple sets in series. Each set
491 * is a superset of the set created before it.
492 */
493 public static class Builder<E> extends ImmutableCollection.Builder<E> {
494 // accessed directly by ImmutableSortedSet
495 final ArrayList<E> contents = Lists.newArrayList();
496
497 /**
498 * Creates a new builder. The returned builder is equivalent to the builder
499 * generated by {@link ImmutableSet#builder}.
500 */
501 public Builder() {}
502
503 /**
504 * Adds {@code element} to the {@code ImmutableSet}. If the {@code
505 * ImmutableSet} already contains {@code element}, then {@code add} has no
506 * effect (only the previously added element is retained).
507 *
508 * @param element the element to add
509 * @return this {@code Builder} object
510 * @throws NullPointerException if {@code element} is null
511 */
512 @Override public Builder<E> add(E element) {
513 contents.add(checkNotNull(element));
514 return this;
515 }
516
517 /**
518 * Adds each element of {@code elements} to the {@code ImmutableSet},
519 * ignoring duplicate elements (only the first duplicate element is added).
520 *
521 * @param elements the elements to add
522 * @return this {@code Builder} object
523 * @throws NullPointerException if {@code elements} is null or contains a
524 * null element
525 */
526 @Override public Builder<E> add(E... elements) {
527 contents.ensureCapacity(contents.size() + elements.length);
528 super.add(elements);
529 return this;
530 }
531
532 /**
533 * Adds each element of {@code elements} to the {@code ImmutableSet},
534 * ignoring duplicate elements (only the first duplicate element is added).
535 *
536 * @param elements the {@code Iterable} to add to the {@code ImmutableSet}
537 * @return this {@code Builder} object
538 * @throws NullPointerException if {@code elements} is null or contains a
539 * null element
540 */
541 @Override public Builder<E> addAll(Iterable<? extends E> elements) {
542 if (elements instanceof Collection) {
543 Collection<?> collection = (Collection<?>) elements;
544 contents.ensureCapacity(contents.size() + collection.size());
545 }
546 super.addAll(elements);
547 return this;
548 }
549
550 /**
551 * Adds each element of {@code elements} to the {@code ImmutableSet},
552 * ignoring duplicate elements (only the first duplicate element is added).
553 *
554 * @param elements the elements to add to the {@code ImmutableSet}
555 * @return this {@code Builder} object
556 * @throws NullPointerException if {@code elements} is null or contains a
557 * null element
558 */
559 @Override public Builder<E> addAll(Iterator<? extends E> elements) {
560 super.addAll(elements);
561 return this;
562 }
563
564 /**
565 * Returns a newly-created {@code ImmutableSet} based on the contents of
566 * the {@code Builder}.
567 */
568 @Override public ImmutableSet<E> build() {
569 return copyOf(contents);
570 }
571 }
572 }