1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2007 The Guava Authors 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkArgument; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkNotNull; 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.primitives.Ints; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.Serializable; 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.ArrayList; 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collections; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.HashSet; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * A high-performance, immutable {@code Set} with reliable, user-specified 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order. Does not permit null elements. 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Unlike {@link Collections#unmodifiableSet}, which is a <i>view</i> of a 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * separate collection that can still change, an instance of this class contains 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * its own private data and will <i>never</i> change. This class is convenient 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * for {@code public static final} sets ("constant sets") and also lets you 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * easily make a "defensive copy" of a set provided to your class by a caller. 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Warning:</b> Like most sets, an {@code ImmutableSet} will not function 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * correctly if an element is modified after being placed in the set. For this 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * reason, and to avoid general confusion, it is strongly recommended to place 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * only immutable objects into this collection. 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This class has been observed to perform significantly better than {@link 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * HashSet} for objects with very fast {@link Object#hashCode} implementations 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * (as a well-behaved immutable object should). While this class's factory 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * methods create hash-based instances, the {@link ImmutableSortedSet} subclass 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * performs binary searches instead. 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Note:</b> Although this class is not final, it cannot be subclassed 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * outside its package as it has no public or protected constructors. Thus, 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * instances of this type are guaranteed to be immutable. 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @see ImmutableList 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @see ImmutableMap 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Kevin Bourrillion 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Nick Kralevich 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true, emulated = true) 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@SuppressWarnings("serial") // we're overriding default serialization 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic abstract class ImmutableSet<E> extends ImmutableCollection<E> 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements Set<E> { 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the empty immutable set. This set behaves and performs comparably 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to {@link Collections#emptySet}, and is preferable mainly for consistency 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and maintainability of your code. 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Casting to any type is safe because the set will never hold any elements. 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings({"unchecked"}) 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> ImmutableSet<E> of() { 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (ImmutableSet<E>) EmptyImmutableSet.INSTANCE; 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set containing a single element. This set behaves and 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * performs comparably to {@link Collections#singleton}, but will not accept 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a null element. It is preferable mainly for consistency and 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * maintainability of your code. 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> ImmutableSet<E> of(E element) { 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SingletonImmutableSet<E>(element); 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set containing the given elements, in order. Repeated 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * occurrences of an element (according to {@link Object#equals}) after the 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * first are ignored. 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any element is null 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> ImmutableSet<E> of(E e1, E e2) { 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return construct(e1, e2); 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set containing the given elements, in order. Repeated 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * occurrences of an element (according to {@link Object#equals}) after the 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * first are ignored. 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any element is null 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> ImmutableSet<E> of(E e1, E e2, E e3) { 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return construct(e1, e2, e3); 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set containing the given elements, in order. Repeated 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * occurrences of an element (according to {@link Object#equals}) after the 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * first are ignored. 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any element is null 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4) { 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return construct(e1, e2, e3, e4); 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set containing the given elements, in order. Repeated 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * occurrences of an element (according to {@link Object#equals}) after the 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * first are ignored. 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any element is null 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5) { 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return construct(e1, e2, e3, e4, e5); 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set containing the given elements, in order. Repeated 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * occurrences of an element (according to {@link Object#equals}) after the 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * first are ignored. 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any element is null 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 3.0 (source-compatible since 2.0) 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ImmutableSet<E> of(E e1, E e2, E e3, E e4, E e5, E e6, 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E... others) { 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final int paramCount = 6; 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object[] elements = new Object[paramCount + others.length]; 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements[0] = e1; 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements[1] = e2; 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements[2] = e3; 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements[3] = e4; 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements[4] = e5; 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements[5] = e6; 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = paramCount; i < elements.length; i++) { 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert elements[i] = others[i - paramCount]; 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return construct(elements); 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** {@code elements} has to be internally created array. */ 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static <E> ImmutableSet<E> construct(Object... elements) { 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int tableSize = chooseTableSize(elements.length); 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object[] table = new Object[tableSize]; 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int mask = tableSize - 1; 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ArrayList<Object> uniqueElementsList = null; 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int hashCode = 0; 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int i = 0; i < elements.length; i++) { 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object element = elements[i]; 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int hash = element.hashCode(); 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int j = Hashing.smear(hash); ; j++) { 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int index = j & mask; 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object value = table[index]; 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (value == null) { 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (uniqueElementsList != null) { 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert uniqueElementsList.add(element); 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Came to an empty slot. Put the element here. 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert table[index] = element; 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert hashCode += hash; 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (value.equals(element)) { 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (uniqueElementsList == null) { 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // first dup 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert uniqueElementsList = new ArrayList<Object>(elements.length); 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (int k = 0; k < i; k++) { 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object previous = elements[k]; 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert uniqueElementsList.add(previous); 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert break; 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object[] uniqueElements = uniqueElementsList == null 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ? elements 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert : uniqueElementsList.toArray(); 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (uniqueElements.length == 1) { 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // There is only one element or elements are all duplicates 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") // we are careful to only pass in E 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E element = (E) uniqueElements[0]; 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new SingletonImmutableSet<E>(element, hashCode); 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else if (tableSize > 2 * chooseTableSize(uniqueElements.length)) { 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Resize the table when the array includes too many duplicates. 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // when this happens, we have already made a copy 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return construct(uniqueElements); 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new RegularImmutableSet<E>(uniqueElements, hashCode, table, mask); 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // We use power-of-2 tables, and this is the highest int that's a power of 2 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final int MAX_TABLE_SIZE = Ints.MAX_POWER_OF_TWO; 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // If the set has this many elements, it will "max out" the table size 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static final int CUTOFF = 1 << 29; 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an array size suitable for the backing array of a hash table that 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * uses linear probing in its implementation. The returned size is the 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * smallest power of two that can hold setSize elements while being at most 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 50% full, if possible. 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static int chooseTableSize(int setSize) { 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (setSize < CUTOFF) { 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Integer.highestOneBit(setSize) << 2; 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // The table can't be completely full or we'll get infinite reprobes 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(setSize < MAX_TABLE_SIZE, "collection too large"); 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return MAX_TABLE_SIZE; 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable set containing the given elements, in order. Repeated 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * occurrences of an element (according to {@link Object#equals}) after the 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * first are ignored. 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any of {@code elements} is null 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 3.0 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ImmutableSet<E> copyOf(E[] elements) { 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(benyu): could we delegate to 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // copyFromCollection(Arrays.asList(elements))? 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson switch (elements.length) { 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson case 0: 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return of(); 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson case 1: 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return of(elements[0]); 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson default: 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return construct(elements.clone()); 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set containing the given elements, in order. Repeated 255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * occurrences of an element (according to {@link Object#equals}) after the 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * first are ignored. This method iterates over {@code elements} at most once. 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Note that if {@code s} is a {@code Set<String>}, then {@code 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSet.copyOf(s)} returns an {@code ImmutableSet<String>} containing 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * each of the strings in {@code s}, while {@code ImmutableSet.of(s)} returns 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a {@code ImmutableSet<Set<String>>} containing one element (the given set 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * itself). 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Despite the method name, this method attempts to avoid actually copying 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the data when it is safe to do so. The exact circumstances under which a 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * copy will or will not be performed are undocumented and subject to change. 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any of {@code elements} is null 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> ImmutableSet<E> copyOf(Iterable<? extends E> elements) { 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (elements instanceof Collection) 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ? copyOf(Collections2.cast(elements)) 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert : copyOf(elements.iterator()); 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set containing the given elements, in order. Repeated 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * occurrences of an element (according to {@link Object#equals}) after the 279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * first are ignored. 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if any of {@code elements} is null 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> ImmutableSet<E> copyOf(Iterator<? extends E> elements) { 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(benyu): here we could avoid toArray() for 0 or 1-element list, 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // worth it? 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyFromCollection(Lists.newArrayList(elements)); 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an immutable set containing the given elements, in order. Repeated 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * occurrences of an element (according to {@link Object#equals}) after the 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * first are ignored. This method iterates over {@code elements} at most 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * once. 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Note that if {@code s} is a {@code Set<String>}, then {@code 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ImmutableSet.copyOf(s)} returns an {@code ImmutableSet<String>} containing 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * each of the strings in {@code s}, while {@code ImmutableSet.of(s)} returns 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * a {@code ImmutableSet<Set<String>>} containing one element (the given set 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * itself). 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Note:</b> Despite what the method name suggests, {@code copyOf} will 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * return constant-space views, rather than linear-space copies, of some 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * inputs known to be immutable. For some other immutable inputs, such as key 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * sets of an {@code ImmutableMap}, it still performs a copy in order to avoid 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * holding references to the values of the map. The heuristics used in this 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * decision are undocumented and subject to change except that: 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <ul> 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <li>A full copy will be done of any {@code ImmutableSortedSet}.</li> 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <li>{@code ImmutableSet.copyOf()} is idempotent with respect to pointer 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equality.</li> 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * </ul> 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>This method is safe to use even when {@code elements} is a synchronized 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or concurrent collection that is currently being modified by another 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * thread. 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if any of {@code elements} is null 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 7.0 (source-compatible since 2.0) 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> ImmutableSet<E> copyOf(Collection<? extends E> elements) { 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (elements instanceof ImmutableSet 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert && !(elements instanceof ImmutableSortedSet)) { 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") // all supported methods are covariant 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSet<E> set = (ImmutableSet<E>) elements; 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (!set.isPartialView()) { 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return set; 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyFromCollection(elements); 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static <E> ImmutableSet<E> copyFromCollection( 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<? extends E> collection) { 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Object[] elements = collection.toArray(); 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert switch (elements.length) { 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson case 0: 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return of(); 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson case 1: 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") // collection had only Es in it 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E onlyElement = (E) elements[0]; 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return of(onlyElement); 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson default: 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // safe to use the array without copying it 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // as specified by Collection.toArray(). 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return construct(elements); 346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 348090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 349090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ImmutableSet() {} 350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 351090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Returns {@code true} if the {@code hashCode()} method runs quickly. */ 352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean isHashCodeFast() { 353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 354090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 355090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 356090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 357090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (object == this) { 358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (object instanceof ImmutableSet 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson && isHashCodeFast() 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson && ((ImmutableSet<?>) object).isHashCodeFast() 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson && hashCode() != object.hashCode()) { 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 3661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Sets.equalsImpl(this, object); 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 3701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Sets.hashCodeImpl(this); 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // This declaration is needed to make Set.iterator() and 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // ImmutableCollection.iterator() consistent. 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public abstract UnmodifiableIterator<E> iterator(); 376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson abstract static class ArrayImmutableSet<E> extends ImmutableSet<E> { 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // the elements (two or more) in the desired order. 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final transient Object[] elements; 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ArrayImmutableSet(Object[] elements) { 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.elements = elements; 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return elements.length; 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 389090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 392090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * The cast is safe because the only way to create an instance is via the 396090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * create() method above, which only permits elements of type E. 397090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 398090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 399090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public UnmodifiableIterator<E> iterator() { 400090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (UnmodifiableIterator<E>) Iterators.forArray(elements); 401090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 402090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 403090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Object[] toArray() { 404090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Object[] array = new Object[size()]; 4051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert System.arraycopy(elements, 0, array, 0, size()); 406090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return array; 407090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 408090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 409090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public <T> T[] toArray(T[] array) { 410090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int size = size(); 411090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (array.length < size) { 412090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson array = ObjectArrays.newArray(array, size); 413090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (array.length > size) { 414090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson array[size] = null; 415090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 4161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert System.arraycopy(elements, 0, array, 0, size); 417090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return array; 418090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 419090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 420090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsAll(Collection<?> targets) { 421090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (targets == this) { 422090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 423090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 424090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!(targets instanceof ArrayImmutableSet)) { 425090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return super.containsAll(targets); 426090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 427090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (targets.size() > size()) { 428090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 429090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 430090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Object target : ((ArrayImmutableSet<?>) targets).elements) { 431090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!contains(target)) { 432090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 433090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 434090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 435090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 436090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 437bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 4381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override boolean isPartialView() { 4391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 4401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 4411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 442bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override ImmutableList<E> createAsList() { 443bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return new ImmutableAsList<E>(elements, this); 444bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 445090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 446090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 447090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** such as ImmutableMap.keySet() */ 448090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson abstract static class TransformedImmutableSet<D, E> extends ImmutableSet<E> { 449090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final D[] source; 450090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final int hashCode; 451090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 452090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson TransformedImmutableSet(D[] source, int hashCode) { 453090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.source = source; 454090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.hashCode = hashCode; 455090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 456090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 457090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson abstract E transform(D element); 458090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 460090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 461090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return source.length; 462090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 463090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 464090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 465090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 466090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 467090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 468090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public UnmodifiableIterator<E> iterator() { 4691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new AbstractIndexedListIterator<E>(source.length) { 4701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override protected E get(int index) { 4711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return transform(source[index]); 472090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 473090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 474090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 475090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 476090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Object[] toArray() { 477090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return toArray(new Object[size()]); 478090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 479090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 480090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public <T> T[] toArray(T[] array) { 481090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int size = size(); 482090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (array.length < size) { 483090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson array = ObjectArrays.newArray(array, size); 484090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (array.length > size) { 485090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson array[size] = null; 486090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 487090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Writes will produce ArrayStoreException when the toArray() doc requires 489090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Object[] objectArray = array; 490090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = 0; i < source.length; i++) { 491090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson objectArray[i] = transform(source[i]); 492090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 493090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return array; 494090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 495090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 496090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public final int hashCode() { 497090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return hashCode; 498090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 499090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 500090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override boolean isHashCodeFast() { 501090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 502090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 503090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 504090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 505090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 506090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This class is used to serialize all ImmutableSet instances, except for 507090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableEnumSet/ImmutableSortedSet, regardless of implementation type. It 508090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * captures their "logical contents" and they are reconstructed using public 509090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * static factories. This is necessary to ensure that the existence of a 510090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * particular implementation type is an implementation detail. 511090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 512090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class SerializedForm implements Serializable { 513090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Object[] elements; 514090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SerializedForm(Object[] elements) { 515090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.elements = elements; 516090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 517090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Object readResolve() { 5181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return copyOf(elements); 519090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 520090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 521090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 522090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 523090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override Object writeReplace() { 524090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SerializedForm(toArray()); 525090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 526090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 527090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 528090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a new builder. The generated builder is equivalent to the builder 529090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * created by the {@link Builder} constructor. 530090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 531090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> Builder<E> builder() { 532090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Builder<E>(); 533090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 534090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 535090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 5361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * A builder for creating immutable set instances, especially {@code public 5371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * static final} sets ("constant sets"). Example: <pre> {@code 538090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 5391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * public static final ImmutableSet<Color> GOOGLE_COLORS = 5401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * new ImmutableSet.Builder<Color>() 541090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .addAll(WEBSAFE_COLORS) 542090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .add(new Color(0, 191, 255)) 543090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * .build();}</pre> 544090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 5451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Builder instances can be reused; it is safe to call {@link #build} multiple 5461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * times to build multiple sets in series. Each set is a superset of the set 5471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * created before it. 5481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 5491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 550090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 551090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static class Builder<E> extends ImmutableCollection.Builder<E> { 552090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // accessed directly by ImmutableSortedSet 553090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final ArrayList<E> contents = Lists.newArrayList(); 554090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 555090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 556090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a new builder. The returned builder is equivalent to the builder 557090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * generated by {@link ImmutableSet#builder}. 558090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 559090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Builder() {} 560090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 561090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 562090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds {@code element} to the {@code ImmutableSet}. If the {@code 563090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSet} already contains {@code element}, then {@code add} has no 564090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * effect (only the previously added element is retained). 565090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 566090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param element the element to add 567090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return this {@code Builder} object 568090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code element} is null 569090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 570090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Builder<E> add(E element) { 571090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson contents.add(checkNotNull(element)); 572090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this; 573090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 574090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 575090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 576090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds each element of {@code elements} to the {@code ImmutableSet}, 577090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ignoring duplicate elements (only the first duplicate element is added). 578090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 579090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements to add 580090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return this {@code Builder} object 581090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code elements} is null or contains a 582090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * null element 583090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 584090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Builder<E> add(E... elements) { 585090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson contents.ensureCapacity(contents.size() + elements.length); 586090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super.add(elements); 587090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this; 588090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 589090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 590090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 591090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds each element of {@code elements} to the {@code ImmutableSet}, 592090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ignoring duplicate elements (only the first duplicate element is added). 593090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 594090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the {@code Iterable} to add to the {@code ImmutableSet} 595090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return this {@code Builder} object 596090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code elements} is null or contains a 597090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * null element 598090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 599090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Builder<E> addAll(Iterable<? extends E> elements) { 600090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (elements instanceof Collection) { 601090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<?> collection = (Collection<?>) elements; 602090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson contents.ensureCapacity(contents.size() + collection.size()); 603090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 604090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super.addAll(elements); 605090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this; 606090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 607090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 608090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 609090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds each element of {@code elements} to the {@code ImmutableSet}, 610090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ignoring duplicate elements (only the first duplicate element is added). 611090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 612090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements to add to the {@code ImmutableSet} 613090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return this {@code Builder} object 614090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code elements} is null or contains a 615090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * null element 616090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 617090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Builder<E> addAll(Iterator<? extends E> elements) { 618090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super.addAll(elements); 619090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this; 620090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 621090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 622090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 623090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a newly-created {@code ImmutableSet} based on the contents of 624090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the {@code Builder}. 625090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 626090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ImmutableSet<E> build() { 627090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return copyOf(contents); 628090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 629090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 630090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 631