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; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.Beta; 23090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Function; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Objects; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Preconditions; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Predicate; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Predicates; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.collect.Collections2.FilteredCollection; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.math.IntMath; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.IOException; 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectInputStream; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.Serializable; 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractSet; 37bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport java.util.Arrays; 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collections; 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Comparator; 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.EnumSet; 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.HashSet; 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.LinkedHashSet; 45bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport java.util.List; 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 47bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport java.util.NoSuchElementException; 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.SortedSet; 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.TreeSet; 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Static utility methods pertaining to {@link Set} instances. Also see this 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * class's counterparts {@link Lists} and {@link Maps}. 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Kevin Bourrillion 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Jared Levy 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Chris Povirk 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(emulated = true) 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic final class Sets { 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Sets() {} 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set instance containing the given enum elements. 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Internally, the returned set will be backed by an {@link EnumSet}. 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iteration order of the returned set follows the enum's iteration 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order, not the order in which the elements are provided to the method. 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param anElement one of the elements the set should contain 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param otherElements the rest of the elements the set should contain 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return an immutable set containing those elements, minus duplicates 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet( 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E anElement, E... otherElements) { 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ImmutableEnumSet<E>(EnumSet.of(anElement, otherElements)); 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set instance containing the given enum elements. 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Internally, the returned set will be backed by an {@link EnumSet}. 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iteration order of the returned set follows the enum's iteration 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order, not the order in which the elements appear in the given collection. 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements, all of the same {@code enum} type, that the 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * set should contain 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return an immutable set containing those elements, minus duplicates 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet( 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterable<E> elements) { 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<E> iterator = elements.iterator(); 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!iterator.hasNext()) { 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return ImmutableSet.of(); 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (elements instanceof EnumSet) { 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EnumSet<E> enumSetClone = EnumSet.copyOf((EnumSet<E>) elements); 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ImmutableEnumSet<E>(enumSetClone); 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E first = iterator.next(); 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EnumSet<E> set = EnumSet.of(first); 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (iterator.hasNext()) { 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.add(iterator.next()); 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ImmutableEnumSet<E>(set); 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a new {@code EnumSet} instance containing the given elements. 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unlike {@link EnumSet#copyOf(Collection)}, this method does not produce an 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * exception on an empty collection, and it may be called on any iterable, not 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * just a {@code Collection}. 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Enum<E>> EnumSet<E> newEnumSet(Iterable<E> iterable, 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Class<E> elementType) { 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * TODO(cpovirk): noneOf() and addAll() will both throw 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * NullPointerExceptions when appropriate. However, NullPointerTester will 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * fail on this method because it passes in Class.class instead of an enum 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * type. This means that, when iterable is null but elementType is not, 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * noneOf() will throw a ClassCastException before addAll() has a chance to 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * throw a NullPointerException. NullPointerTester considers this a failure. 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Ideally the test would be fixed, but it would require a special case for 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Class<E> where E extends Enum. Until that happens (if ever), leave 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * checkNotNull() here. For now, contemplate the irony that checking 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elementType, the problem argument, is harmful, while checking iterable, 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the innocent bystander, is effective. 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(iterable); 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EnumSet<E> set = EnumSet.noneOf(elementType); 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterables.addAll(set, iterable); 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // HashSet 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i>, empty {@code HashSet} instance. 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required, use {@link 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSet#of()} instead. 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * EnumSet#noneOf} instead. 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, empty {@code HashSet} 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> HashSet<E> newHashSet() { 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new HashSet<E>(); 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i> {@code HashSet} instance containing the given 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements in unspecified order. 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required and the elements are 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * non-null, use an overload of {@link ImmutableSet#of()} (for varargs) or 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link ImmutableSet#copyOf(Object[])} (for an array) instead. 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * EnumSet#of(Enum, Enum[])} instead. 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements that the set should contain 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code HashSet} containing those elements (minus duplicates) 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> HashSet<E> newHashSet(E... elements) { 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert HashSet<E> set = newHashSetWithExpectedSize(elements.length); 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collections.addAll(set, elements); 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates a {@code HashSet} instance, with a high enough "initial capacity" 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * that it <i>should</i> hold {@code expectedSize} elements without growth. 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * This behavior cannot be broadly guaranteed, but it is observed to be true 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * for OpenJDK 1.6. It also can't be guaranteed that the method isn't 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * inadvertently <i>oversizing</i> the returned set. 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param expectedSize the number of elements you expect to add to the 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returned set 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, empty {@code HashSet} with enough capacity to hold {@code 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * expectedSize} elements without resizing 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code expectedSize} is negative 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> HashSet<E> newHashSetWithExpectedSize(int expectedSize) { 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new HashSet<E>(Maps.capacity(expectedSize)); 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i> {@code HashSet} instance containing the given 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements in unspecified order. 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required and the elements are 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead. 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #newEnumSet(Iterable, Class)} instead. 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements that the set should contain 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code HashSet} containing those elements (minus duplicates) 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 210090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> HashSet<E> newHashSet(Iterable<? extends E> elements) { 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (elements instanceof Collection) 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ? new HashSet<E>(Collections2.cast(elements)) 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert : newHashSet(elements.iterator()); 214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i> {@code HashSet} instance containing the given 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements in unspecified order. 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required and the elements are 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead. 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if {@code E} is an {@link Enum} type, you should create an 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link EnumSet} instead. 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements that the set should contain 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code HashSet} containing those elements (minus duplicates) 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> HashSet<E> newHashSet(Iterator<? extends E> elements) { 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson HashSet<E> set = newHashSet(); 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (elements.hasNext()) { 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.add(elements.next()); 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // LinkedHashSet 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i>, empty {@code LinkedHashSet} instance. 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 242090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required, use {@link 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSet#of()} instead. 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, empty {@code LinkedHashSet} 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> LinkedHashSet<E> newLinkedHashSet() { 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashSet<E>(); 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates a {@code LinkedHashSet} instance, with a high enough "initial 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * capacity" that it <i>should</i> hold {@code expectedSize} elements without 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * growth. This behavior cannot be broadly guaranteed, but it is observed to 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * be true for OpenJDK 1.6. It also can't be guaranteed that the method isn't 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * inadvertently <i>oversizing</i> the returned set. 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param expectedSize the number of elements you expect to add to the 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returned set 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return a new, empty {@code LinkedHashSet} with enough capacity to hold 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code expectedSize} elements without resizing 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code expectedSize} is negative 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> LinkedHashSet<E> newLinkedHashSetWithExpectedSize( 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int expectedSize) { 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new LinkedHashSet<E>(Maps.capacity(expectedSize)); 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i> {@code LinkedHashSet} instance containing the 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * given elements in order. 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required and the elements are 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead. 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements that the set should contain, in order 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code LinkedHashSet} containing those elements (minus 279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * duplicates) 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> LinkedHashSet<E> newLinkedHashSet( 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterable<? extends E> elements) { 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (elements instanceof Collection) { 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new LinkedHashSet<E>(Collections2.cast(elements)); 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert LinkedHashSet<E> set = newLinkedHashSet(); 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (E element : elements) { 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert set.add(element); 289090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return set; 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // TreeSet 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i>, empty {@code TreeSet} instance sorted by the 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * natural sort ordering of its elements. 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required, use {@link 300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSortedSet#of()} instead. 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, empty {@code TreeSet} 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Comparable> TreeSet<E> newTreeSet() { 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new TreeSet<E>(); 306090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i> {@code TreeSet} instance containing the given 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements sorted by their natural ordering. 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required, use {@link 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSortedSet#copyOf(Iterable)} instead. 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparator, this method has different behavior than 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code TreeSet} with 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that comparator. 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements that the set should contain 321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code TreeSet} containing those elements (minus duplicates) 322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 323090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Comparable> TreeSet<E> newTreeSet( 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterable<? extends E> elements) { 325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson TreeSet<E> set = newTreeSet(); 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (E element : elements) { 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.add(element); 328090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparator. 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required, use {@code 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSortedSet.orderedBy(comparator).build()} instead. 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param comparator the comparator to use to sort the set 340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, empty {@code TreeSet} 341090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code comparator} is null 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 343090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> TreeSet<E> newTreeSet(Comparator<? super E> comparator) { 344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new TreeSet<E>(checkNotNull(comparator)); 345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates an empty {@code Set} that uses identity to determine equality. It 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * compares object references, instead of calling {@code equals}, to 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * determine whether a provided object matches an element in the set. For 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * example, {@code contains} returns {@code false} when passed an object that 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equals a set member, but isn't the same instance. This behavior is similar 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * to the way {@code IdentityHashMap} handles key lookups. 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 8.0 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> Set<E> newIdentityHashSet() { 3581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Sets.newSetFromMap(Maps.<E, Boolean>newIdentityHashMap()); 3591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates an {@code EnumSet} consisting of all enum values that are not in 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the specified collection. If the collection is an {@link EnumSet}, this 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * method has the same behavior as {@link EnumSet#complementOf}. Otherwise, 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the specified collection must contain at least one element, in order to 366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * determine the element type. If the collection could be empty, use 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #complementOf(Collection, Class)} instead of this method. 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param collection the collection whose complement should be stored in the 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * enum set 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, modifiable {@code EnumSet} containing all values of the enum 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that aren't present in the given collection 373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code collection} is not an 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code EnumSet} instance and contains no elements 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Enum<E>> EnumSet<E> complementOf( 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<E> collection) { 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection instanceof EnumSet) { 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return EnumSet.complementOf((EnumSet<E>) collection); 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(!collection.isEmpty(), 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson "collection is empty; use the other version of this method"); 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Class<E> type = collection.iterator().next().getDeclaringClass(); 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return makeComplementByHand(collection, type); 385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates an {@code EnumSet} consisting of all enum values that are not in 389090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the specified collection. This is equivalent to 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link EnumSet#complementOf}, but can act on any input collection, as long 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * as the elements are of enum type. 392090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param collection the collection whose complement should be stored in the 394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code EnumSet} 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param type the type of the elements in the set 396090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, modifiable {@code EnumSet} initially containing all the 397090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * values of the enum not present in the given collection 398090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 399090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Enum<E>> EnumSet<E> complementOf( 400090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<E> collection, Class<E> type) { 401090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(collection); 402090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (collection instanceof EnumSet) 403090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ? EnumSet.complementOf((EnumSet<E>) collection) 404090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson : makeComplementByHand(collection, type); 405090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 406090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 407090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static <E extends Enum<E>> EnumSet<E> makeComplementByHand( 408090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<E> collection, Class<E> type) { 409090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EnumSet<E> result = EnumSet.allOf(type); 410090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson result.removeAll(collection); 411090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 412090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 413090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 414090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 415090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Regarding newSetForMap() and SetFromMap: 416090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 417090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Written by Doug Lea with assistance from members of JCP JSR-166 418090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Expert Group and released to the public domain, as explained at 419090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://creativecommons.org/licenses/publicdomain 420090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 421090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 422090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 423090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a set backed by the specified map. The resulting set displays 424090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the same ordering, concurrency, and performance characteristics as the 425090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * backing map. In essence, this factory method provides a {@link Set} 426090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation corresponding to any {@link Map} implementation. There is no 427090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * need to use this method on a {@link Map} implementation that already has a 4281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * corresponding {@link Set} implementation (such as {@link java.util.HashMap} 4291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or {@link java.util.TreeMap}). 430090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 431090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Each method invocation on the set returned by this method results in 4321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * exactly one method invocation on the backing map or its {@code keySet} 4331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * view, with one exception. The {@code addAll} method is implemented as a 4341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * sequence of {@code put} invocations on the backing map. 435090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 436090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The specified map must be empty at the time this method is invoked, 437090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and should not be accessed directly after this method returns. These 438090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * conditions are ensured if the map is created empty, passed directly 439090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to this method, and no reference to the map is retained, as illustrated 440090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * in the following code fragment: <pre> {@code 441090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Set<Object> identityHashSet = Sets.newSetFromMap( 4431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * new IdentityHashMap<Object, Boolean>());}</pre> 444090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 445090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This method has the same behavior as the JDK 6 method 446090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code Collections.newSetFromMap()}. The returned set is serializable if 447090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the backing map is. 448090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 449090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param map the backing map 450090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the set backed by the map 4511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code map} is not empty 452090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 453090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) { 454090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SetFromMap<E>(map); 455090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 456090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 457090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class SetFromMap<E> extends AbstractSet<E> 458090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements Set<E>, Serializable { 459090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final Map<E, Boolean> m; // The backing map 460090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Set<E> s; // Its keySet 461090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 462090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SetFromMap(Map<E, Boolean> map) { 463090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(map.isEmpty(), "Map is non-empty"); 464090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson m = map; 465090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson s = map.keySet(); 466090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 467090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 468090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public void clear() { 469090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson m.clear(); 470090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 471090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 472090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return m.size(); 473090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 474090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 475090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return m.isEmpty(); 476090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 477090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object o) { 478090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return m.containsKey(o); 479090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 480090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean remove(Object o) { 481090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return m.remove(o) != null; 482090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 483090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean add(E e) { 484090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return m.put(e, Boolean.TRUE) == null; 485090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 486090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 487090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.iterator(); 488090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 489090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Object[] toArray() { 490090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.toArray(); 491090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 492090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public <T> T[] toArray(T[] a) { 493090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.toArray(a); 494090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 495090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 496090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.toString(); 497090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 498090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 499090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.hashCode(); 500090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 501090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 502090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this == object || this.s.equals(object); 503090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 504090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsAll(Collection<?> c) { 505090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.containsAll(c); 506090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 507090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> c) { 508090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.removeAll(c); 509090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 510090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> c) { 511090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.retainAll(c); 512090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 513090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 514090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // addAll is the only inherited implementation 5151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("not needed in emulated source") 516bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor private static final long serialVersionUID = 0; 517090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectInputStream") 519090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void readObject(ObjectInputStream stream) 520090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throws IOException, ClassNotFoundException { 521090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultReadObject(); 522090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson s = m.keySet(); 523090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 524090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 525090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 526090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 527090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * An unmodifiable view of a set which may be backed by other sets; this view 528090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * will change as the backing sets do. Contains methods to copy the data into 529090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a new set which will then remain stable. There is usually no reason to 530090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * retain a reference of type {@code SetView}; typically, you either use it 531090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or 532090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #copyInto} and forget the {@code SetView} itself. 5331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 5341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 535090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 536090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public abstract static class SetView<E> extends AbstractSet<E> { 537090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private SetView() {} // no subclasses but our own 538090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 539090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 540090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable copy of the current contents of this set view. 541090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Does not support null elements. 542090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 543090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Warning:</b> this may have unexpected results if a backing set of 544090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * this view uses a nonstandard notion of equivalence, for example if it is 545090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a {@link TreeSet} using a comparator that is inconsistent with {@link 546090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Object#equals(Object)}. 547090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 548090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ImmutableSet<E> immutableCopy() { 549090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return ImmutableSet.copyOf(this); 550090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 551090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 552090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 553090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Copies the current contents of this set view into an existing set. This 554090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * method has equivalent behavior to {@code set.addAll(this)}, assuming that 555090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * all the sets involved are based on the same notion of equivalence. 556bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 557bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @return a reference to {@code set}, for convenience 558090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 559090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Note: S should logically extend Set<? super E> but can't due to either 560090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // some javac bug or some weirdness in the spec, not sure which. 561090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public <S extends Set<E>> S copyInto(S set) { 562090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.addAll(this); 563090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 564090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 565090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 566090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 567090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 568090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an unmodifiable <b>view</b> of the union of two sets. The returned 569090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * set contains all elements that are contained in either backing set. 570090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Iterating over the returned set iterates first over all the elements of 571090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code set1}, then over each element of {@code set2}, in order, that is not 572090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * contained in {@code set1}. 573090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 574090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Results are undefined if {@code set1} and {@code set2} are sets based on 575090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * different equivalence relations (as {@link HashSet}, {@link TreeSet}, and 5761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the {@link Map#keySet} of an {@code IdentityHashMap} all are). 577090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 578090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> The returned view performs better when {@code set1} is the 579090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * smaller of the two sets. If you have reason to believe one of your sets 580090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * will generally be smaller than the other, pass it first. 581090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 582090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> SetView<E> union( 583090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<? extends E> set1, final Set<? extends E> set2) { 584090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set1, "set1"); 585090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set2, "set2"); 586090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 587090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<? extends E> set2minus1 = difference(set2, set1); 588090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 589090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SetView<E>() { 590090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 591090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.size() + set2minus1.size(); 592090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 593090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 594090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.isEmpty() && set2.isEmpty(); 595090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 596090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 597090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.unmodifiableIterator( 598090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterators.concat(set1.iterator(), set2minus1.iterator())); 599090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 600090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object object) { 601090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.contains(object) || set2.contains(object); 602090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 603090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public <S extends Set<E>> S copyInto(S set) { 604090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.addAll(set1); 605090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.addAll(set2); 606090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 607090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 608090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ImmutableSet<E> immutableCopy() { 609090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ImmutableSet.Builder<E>() 610090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson .addAll(set1).addAll(set2).build(); 611090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 612090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 613090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 614090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 615090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 616090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an unmodifiable <b>view</b> of the intersection of two sets. The 617090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returned set contains all elements that are contained by both backing sets. 618090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * The iteration order of the returned set matches that of {@code set1}. 619090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 620090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Results are undefined if {@code set1} and {@code set2} are sets based 621090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * on different equivalence relations (as {@code HashSet}, {@code TreeSet}, 622090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and the keySet of an {@code IdentityHashMap} all are). 623090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 624090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> The returned view performs slightly better when {@code 625090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * set1} is the smaller of the two sets. If you have reason to believe one of 626090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * your sets will generally be smaller than the other, pass it first. 627090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unfortunately, since this method sets the generic type of the returned set 628090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * based on the type of the first set passed, this could in rare cases force 6291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you to make a cast, for example: <pre> {@code 630090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 6311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Set<Object> aFewBadObjects = ... 6321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Set<String> manyBadStrings = ... 633090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 6341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * // impossible for a non-String to be in the intersection 6351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * SuppressWarnings("unchecked") 6361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Set<String> badStrings = (Set) Sets.intersection( 6371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * aFewBadObjects, manyBadStrings);}</pre> 638090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 639090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This is unfortunate, but should come up only very rarely. 640090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 641090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> SetView<E> intersection( 642090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<E> set1, final Set<?> set2) { 643090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set1, "set1"); 644090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set2, "set2"); 645090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 646090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Predicate<Object> inSet2 = Predicates.in(set2); 647090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SetView<E>() { 648090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 649090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.filter(set1.iterator(), inSet2); 650090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 651090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 652090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.size(iterator()); 653090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 654090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 655090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return !iterator().hasNext(); 656090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 657090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object object) { 658090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.contains(object) && set2.contains(object); 659090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 660090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsAll(Collection<?> collection) { 661090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.containsAll(collection) 662090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson && set2.containsAll(collection); 663090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 664090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 665090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 666090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 667090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 668090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an unmodifiable <b>view</b> of the difference of two sets. The 669090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returned set contains all elements that are contained by {@code set1} and 670090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * not contained by {@code set2}. {@code set2} may also contain elements not 671090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * present in {@code set1}; these are simply ignored. The iteration order of 672090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the returned set matches that of {@code set1}. 673090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 674090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Results are undefined if {@code set1} and {@code set2} are sets based 675090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * on different equivalence relations (as {@code HashSet}, {@code TreeSet}, 676090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and the keySet of an {@code IdentityHashMap} all are). 677090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 678090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> SetView<E> difference( 679090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<E> set1, final Set<?> set2) { 680090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set1, "set1"); 681090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set2, "set2"); 682090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 683090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Predicate<Object> notInSet2 = Predicates.not(Predicates.in(set2)); 684090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SetView<E>() { 685090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 686090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.filter(set1.iterator(), notInSet2); 687090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 688090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 689090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.size(iterator()); 690090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 691090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 692090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set2.containsAll(set1); 693090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 694090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object element) { 695090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.contains(element) && !set2.contains(element); 696090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 697090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 698090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 699090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 700090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 7011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns an unmodifiable <b>view</b> of the symmetric difference of two 7021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * sets. The returned set contains all elements that are contained in either 7031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code set1} or {@code set2} but not in both. The iteration order of the 7041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returned set is undefined. 7051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 7061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Results are undefined if {@code set1} and {@code set2} are sets based 7071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * on different equivalence relations (as {@code HashSet}, {@code TreeSet}, 7081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * and the keySet of an {@code IdentityHashMap} all are). 7091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 7101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 3.0 7111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 7121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> SetView<E> symmetricDifference( 7131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<? extends E> set1, Set<? extends E> set2) { 7141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(set1, "set1"); 7151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(set2, "set2"); 7161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): Replace this with a more efficient implementation 7181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return difference(union(set1, set2), intersection(set1, set2)); 7191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 722090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the elements of {@code unfiltered} that satisfy a predicate. The 723090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returned set is a live view of {@code unfiltered}; changes to one affect 724090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the other. 725090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 726090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The resulting set's iterator does not support {@code remove()}, but all 7271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * other set methods are supported. When given an element that doesn't satisfy 7281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the predicate, the set's {@code add()} and {@code addAll()} methods throw 7291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * an {@link IllegalArgumentException}. When methods such as {@code 7301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * removeAll()} and {@code clear()} are called on the filtered set, only 7311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements that satisfy the filter will be removed from the underlying set. 732090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 733090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned set isn't threadsafe or serializable, even if 734090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code unfiltered} is. 735090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 736090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Many of the filtered set's methods, such as {@code size()}, iterate 737090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * across every element in the underlying set and determine which elements 738090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * satisfy the filter. When a live view is <i>not</i> needed, it may be faster 739090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to copy {@code Iterables.filter(unfiltered, predicate)} and use the copy. 7401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 7411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, 7421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * as documented at {@link Predicate#apply}. Do not provide a predicate such 7431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * as {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent 7441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * with equals. (See {@link Iterables#filter(Iterable, Class)} for related 7451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * functionality.) 746090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 7471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(kevinb): how to omit that last sentence when building GWT javadoc? 748090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> Set<E> filter( 749090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<E> unfiltered, Predicate<? super E> predicate) { 7501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (unfiltered instanceof SortedSet) { 7511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return filter((SortedSet<E>) unfiltered, predicate); 7521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 753090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (unfiltered instanceof FilteredSet) { 754090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Support clear(), removeAll(), and retainAll() when filtering a filtered 755090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // collection. 756090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson FilteredSet<E> filtered = (FilteredSet<E>) unfiltered; 757090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Predicate<E> combinedPredicate 758090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = Predicates.<E>and(filtered.predicate, predicate); 759090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new FilteredSet<E>( 760090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson (Set<E>) filtered.unfiltered, combinedPredicate); 761090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 762090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 763090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new FilteredSet<E>( 764090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(unfiltered), checkNotNull(predicate)); 765090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 766090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 767090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class FilteredSet<E> extends FilteredCollection<E> 768090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements Set<E> { 769090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson FilteredSet(Set<E> unfiltered, Predicate<? super E> predicate) { 770090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(unfiltered, predicate); 771090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 772090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 773090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 7741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return equalsImpl(this, object); 7751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int hashCode() { 7781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return hashCodeImpl(this); 7791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 7811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 7821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 7831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the elements of a {@code SortedSet}, {@code unfiltered}, that 7841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * satisfy a predicate. The returned set is a live view of {@code unfiltered}; 7851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * changes to one affect the other. 7861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 7871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The resulting set's iterator does not support {@code remove()}, but all 7881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * other set methods are supported. When given an element that doesn't satisfy 7891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the predicate, the set's {@code add()} and {@code addAll()} methods throw 7901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * an {@link IllegalArgumentException}. When methods such as 7911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code removeAll()} and {@code clear()} are called on the filtered set, 7921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * only elements that satisfy the filter will be removed from the underlying 7931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * set. 7941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 7951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned set isn't threadsafe or serializable, even if 7961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code unfiltered} is. 7971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 7981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Many of the filtered set's methods, such as {@code size()}, iterate across 7991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * every element in the underlying set and determine which elements satisfy 8001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the filter. When a live view is <i>not</i> needed, it may be faster to copy 8011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code Iterables.filter(unfiltered, predicate)} and use the copy. 8021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 8031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Warning:</b> {@code predicate} must be <i>consistent with equals</i>, 8041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * as documented at {@link Predicate#apply}. Do not provide a predicate such as 8051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code Predicates.instanceOf(ArrayList.class)}, which is inconsistent with 8061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equals. (See {@link Iterables#filter(Iterable, Class)} for related 8071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * functionality.) 8081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 8091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 11.0 8101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 8111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Beta 8121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 8131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> SortedSet<E> filter( 8141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedSet<E> unfiltered, Predicate<? super E> predicate) { 8151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (unfiltered instanceof FilteredSet) { 8161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Support clear(), removeAll(), and retainAll() when filtering a filtered 8171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // collection. 8181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert FilteredSet<E> filtered = (FilteredSet<E>) unfiltered; 8191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Predicate<E> combinedPredicate 8201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert = Predicates.<E>and(filtered.predicate, predicate); 8211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new FilteredSortedSet<E>( 8221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert (SortedSet<E>) filtered.unfiltered, combinedPredicate); 8231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new FilteredSortedSet<E>( 8261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(unfiltered), checkNotNull(predicate)); 8271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static class FilteredSortedSet<E> extends FilteredCollection<E> 8301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert implements SortedSet<E> { 8311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert FilteredSortedSet(SortedSet<E> unfiltered, Predicate<? super E> predicate) { 8331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(unfiltered, predicate); 8341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean equals(@Nullable Object object) { 8371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return equalsImpl(this, object); 838090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 839090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 840090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 841090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return hashCodeImpl(this); 842090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 8431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Comparator<? super E> comparator() { 8461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ((SortedSet<E>) unfiltered).comparator(); 8471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedSet<E> subSet(E fromElement, E toElement) { 8511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).subSet(fromElement, toElement), 8521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert predicate); 8531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedSet<E> headSet(E toElement) { 8571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).headSet(toElement), predicate); 8581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public SortedSet<E> tailSet(E fromElement) { 8621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new FilteredSortedSet<E>(((SortedSet<E>) unfiltered).tailSet(fromElement), predicate); 8631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public E first() { 8671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return iterator().next(); 8681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 8701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public E last() { 8721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedSet<E> sortedUnfiltered = (SortedSet<E>) unfiltered; 8731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 8741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert E element = sortedUnfiltered.last(); 8751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (predicate.apply(element)) { 8761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return element; 8771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortedUnfiltered = sortedUnfiltered.headSet(element); 8791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 881090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 882090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 883090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 884bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Returns every possible list that can be formed by choosing one element 885bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * from each of the given sets in order; the "n-ary 886bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian 8871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * product</a>" of the sets. For example: <pre> {@code 888bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 8891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Sets.cartesianProduct(ImmutableList.of( 890bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * ImmutableSet.of(1, 2), 891bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * ImmutableSet.of("A", "B", "C")))}</pre> 892bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 893bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * returns a set containing six lists: 894bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 895bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <ul> 896bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "A")} 897bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "B")} 898bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "C")} 899bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "A")} 900bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "B")} 901bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "C")} 902bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * </ul> 903bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 904bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * The order in which these lists are returned is not guaranteed, however the 905bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * position of an element inside a tuple always corresponds to the position of 906bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * the set from which it came in the input list. Note that if any input set is 907bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * empty, the Cartesian product will also be empty. If no sets at all are 908bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * provided (an empty list), the resulting Cartesian product has one element, 909bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * an empty list (counter-intuitive, but mathematically consistent). 910bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 9111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><i>Performance notes:</i> while the cartesian product of sets of size 9121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory 9131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * consumption is much smaller. When the cartesian set is constructed, the 9141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * input sets are merely copied. Only as the resulting set is iterated are the 9151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * individual lists created, and these are not retained after iteration. 9161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 917bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @param sets the sets to choose elements from, in the order that 918bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * the elements chosen from those sets should appear in the resulting 919bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * lists 920bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @param <B> any common base class shared by all axes (often just {@link 921bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Object}) 922bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @return the Cartesian product, as an immutable set containing immutable 923bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * lists 924bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @throws NullPointerException if {@code sets}, any one of the {@code sets}, 925bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * or any element of a provided set is null 9261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 927bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor */ 928bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public static <B> Set<List<B>> cartesianProduct( 929bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor List<? extends Set<? extends B>> sets) { 9301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Set<? extends B> set : sets) { 9311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (set.isEmpty()) { 9321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return ImmutableSet.of(); 9331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 935bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor CartesianSet<B> cartesianSet = new CartesianSet<B>(sets); 9361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return cartesianSet; 937bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 938bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 939bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor /** 940bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Returns every possible list that can be formed by choosing one element 941bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * from each of the given sets in order; the "n-ary 942bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian 9431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * product</a>" of the sets. For example: <pre> {@code 944bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 9451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Sets.cartesianProduct( 946bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * ImmutableSet.of(1, 2), 947bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * ImmutableSet.of("A", "B", "C"))}</pre> 948bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 949bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * returns a set containing six lists: 9501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 951bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <ul> 952bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "A")} 953bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "B")} 954bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "C")} 955bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "A")} 956bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "B")} 957bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "C")} 958bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * </ul> 959bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 960bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * The order in which these lists are returned is not guaranteed, however the 961bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * position of an element inside a tuple always corresponds to the position of 962bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * the set from which it came in the input list. Note that if any input set is 963bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * empty, the Cartesian product will also be empty. If no sets at all are 964bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * provided, the resulting Cartesian product has one element, an empty list 965bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * (counter-intuitive, but mathematically consistent). 966bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 9671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><i>Performance notes:</i> while the cartesian product of sets of size 9681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code m, n, p} is a set of size {@code m x n x p}, its actual memory 9691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * consumption is much smaller. When the cartesian set is constructed, the 9701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * input sets are merely copied. Only as the resulting set is iterated are the 9711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * individual lists created, and these are not retained after iteration. 9721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 973bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @param sets the sets to choose elements from, in the order that 974bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * the elements chosen from those sets should appear in the resulting 975bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * lists 976bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @param <B> any common base class shared by all axes (often just {@link 977bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Object}) 978bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @return the Cartesian product, as an immutable set containing immutable 979bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * lists 980bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @throws NullPointerException if {@code sets}, any one of the {@code sets}, 981bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * or any element of a provided set is null 9821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 983bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor */ 984bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public static <B> Set<List<B>> cartesianProduct( 985bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Set<? extends B>... sets) { 986bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return cartesianProduct(Arrays.asList(sets)); 987bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 988bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 989bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor private static class CartesianSet<B> extends AbstractSet<List<B>> { 990bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor final ImmutableList<Axis> axes; 991bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor final int size; 992bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 993bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor CartesianSet(List<? extends Set<? extends B>> sets) { 9941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int dividend = 1; 995bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor ImmutableList.Builder<Axis> builder = ImmutableList.builder(); 9961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 9971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Set<? extends B> set : sets) { 9981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Axis axis = new Axis(set, dividend); 9991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert builder.add(axis); 10001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert dividend = IntMath.checkedMultiply(dividend, axis.size()); 10011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ArithmeticException overflow) { 10031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new IllegalArgumentException("cartesian product too big"); 1004bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1005bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor this.axes = builder.build(); 10061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert size = dividend; 1007bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1008bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1009bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public int size() { 1010bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return size; 1011bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1012bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1013bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public UnmodifiableIterator<List<B>> iterator() { 1014bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return new UnmodifiableIterator<List<B>>() { 1015bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int index; 1016bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 10171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1018bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public boolean hasNext() { 1019bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return index < size; 1020bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1021bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 10221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1023bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public List<B> next() { 1024bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (!hasNext()) { 1025bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor throw new NoSuchElementException(); 1026bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1027bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1028bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Object[] tuple = new Object[axes.size()]; 1029bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor for (int i = 0 ; i < tuple.length; i++) { 1030bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor tuple[i] = axes.get(i).getForIndex(index); 1031bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1032bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor index++; 1033bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1034bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @SuppressWarnings("unchecked") // only B's are put in here 10351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<B> result = (ImmutableList<B>) ImmutableList.copyOf(tuple); 1036bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return result; 1037bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1038bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor }; 1039bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1040bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1041bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public boolean contains(Object element) { 1042bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (!(element instanceof List<?>)) { 1043bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return false; 1044bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1045bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor List<?> tuple = (List<?>) element; 1046bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int dimensions = axes.size(); 1047bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (tuple.size() != dimensions) { 1048bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return false; 1049bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1050bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor for (int i = 0; i < dimensions; i++) { 1051bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (!axes.get(i).contains(tuple.get(i))) { 1052bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return false; 1053bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1054bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1055bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return true; 1056bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1057bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1058bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public boolean equals(@Nullable Object object) { 1059bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // Warning: this is broken if size() == 0, so it is critical that we 1060bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // substitute an empty ImmutableSet to the user in place of this 10611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (object instanceof CartesianSet) { 10621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert CartesianSet<?> that = (CartesianSet<?>) object; 1063bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return this.axes.equals(that.axes); 1064bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1065bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return super.equals(object); 1066bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1067bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1068bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public int hashCode() { 1069bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // Warning: this is broken if size() == 0, so it is critical that we 1070bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // substitute an empty ImmutableSet to the user in place of this 1071bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1072bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // It's a weird formula, but tests prove it works. 1073bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int adjust = size - 1; 1074bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor for (int i = 0; i < axes.size(); i++) { 1075bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor adjust *= 31; 1076bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1077bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return axes.hashCode() + adjust; 1078bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1079bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1080bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor private class Axis { 1081bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor final ImmutableSet<? extends B> choices; 10821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final ImmutableList<? extends B> choicesList; 1083bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor final int dividend; 1084bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1085bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Axis(Set<? extends B> set, int dividend) { 1086bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor choices = ImmutableSet.copyOf(set); 10871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert choicesList = choices.asList(); 1088bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor this.dividend = dividend; 1089bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1090bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1091bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int size() { 1092bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return choices.size(); 1093bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1094bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1095bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor B getForIndex(int index) { 10961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return choicesList.get(index / dividend % size()); 1097bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1098bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1099bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor boolean contains(Object target) { 1100bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return choices.contains(target); 1101bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1102bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1103bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public boolean equals(Object obj) { 1104bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (obj instanceof CartesianSet.Axis) { 1105bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor CartesianSet.Axis that = (CartesianSet.Axis) obj; 1106bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return this.choices.equals(that.choices); 1107bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // dividends must be equal or we wouldn't have gotten this far 1108bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1109bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return false; 1110bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1111bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1112bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public int hashCode() { 11131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Because Axis instances are not exposed, we can 11141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // opportunistically choose whatever bizarre formula happens 11151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // to make CartesianSet.hashCode() as simple as possible. 1116bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return size / choices.size() * choices.hashCode(); 1117bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1118bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1119bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 1120bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 1121bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor /** 11221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the set of all possible subsets of {@code set}. For example, 11231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code powerSet(ImmutableSet.of(1, 2))} returns the set {@code {{}, 11241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {1}, {2}, {1, 2}}}. 11251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 11261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Elements appear in these subsets in the same iteration order as they 11271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * appeared in the input set. The order in which these subsets appear in the 11281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * outer set is undefined. Note that the power set of the empty set is not the 11291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * empty set, but a one-element set containing the empty set. 11301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 11311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned set and its constituent sets use {@code equals} to decide 11321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * whether two elements are identical, even if the input set uses a different 11331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * concept of equivalence. 11341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 11351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><i>Performance notes:</i> while the power set of a set with size {@code 11361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * n} is of size {@code 2^n}, its memory usage is only {@code O(n)}. When the 11371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * power set is constructed, the input set is merely copied. Only as the 11381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * power set is iterated are the individual subsets created, and these subsets 11391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * themselves occupy only a few bytes of memory regardless of their size. 11401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 11411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param set the set of elements to construct a power set from 11421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the power set, as an immutable set of immutable sets 11431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws IllegalArgumentException if {@code set} has more than 30 unique 11441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * elements (causing the power set size to exceed the {@code int} range) 11451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @throws NullPointerException if {@code set} is or contains {@code null} 11461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @see <a href="http://en.wikipedia.org/wiki/Power_set">Power set article at 11471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Wikipedia</a> 11481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 4.0 11491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 11501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtCompatible(serializable = false) 11511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <E> Set<Set<E>> powerSet(Set<E> set) { 11521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ImmutableSet<E> input = ImmutableSet.copyOf(set); 11531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkArgument(input.size() <= 30, 11541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert "Too many elements to create power set: %s > 30", input.size()); 11551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new PowerSet<E>(input); 11561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 11571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 11581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final class PowerSet<E> extends AbstractSet<Set<E>> { 11591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final ImmutableSet<E> inputSet; 11601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final ImmutableList<E> inputList; 11611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final int powerSetSize; 11621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 11631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert PowerSet(ImmutableSet<E> input) { 11641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.inputSet = input; 11651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.inputList = input.asList(); 11661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.powerSetSize = 1 << input.size(); 11671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 11681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 11691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int size() { 11701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return powerSetSize; 11711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 11721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 11731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean isEmpty() { 11741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 11751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 11761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 11771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Iterator<Set<E>> iterator() { 11781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new AbstractIndexedListIterator<Set<E>>(powerSetSize) { 11791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override protected Set<E> get(final int setBits) { 11801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new AbstractSet<E>() { 11811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int size() { 11821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Integer.bitCount(setBits); 11831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 11841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Iterator<E> iterator() { 11851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new BitFilteredSetIterator<E>(inputList, setBits); 11861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 11871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 11881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 11891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 11901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 11911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 11921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static final class BitFilteredSetIterator<E> 11931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert extends UnmodifiableIterator<E> { 11941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final ImmutableList<E> input; 11951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int remainingSetBits; 11961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 11971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert BitFilteredSetIterator(ImmutableList<E> input, int allSetBits) { 11981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.input = input; 11991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.remainingSetBits = allSetBits; 12001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean hasNext() { 12031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return remainingSetBits != 0; 12041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public E next() { 12071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int index = Integer.numberOfTrailingZeros(remainingSetBits); 12081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (index == 32) { 12091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new NoSuchElementException(); 12101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int currentElementMask = 1 << index; 12131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert remainingSetBits &= ~currentElementMask; 12141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return input.get(index); 12151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean contains(@Nullable Object obj) { 12191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (obj instanceof Set) { 12201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<?> set = (Set<?>) obj; 12211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return inputSet.containsAll(set); 12221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 12241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean equals(@Nullable Object obj) { 12271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (obj instanceof PowerSet) { 12281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert PowerSet<?> that = (PowerSet<?>) obj; 12291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return inputSet.equals(that.inputSet); 12301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.equals(obj); 12321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int hashCode() { 12351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 12361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * The sum of the sums of the hash codes in each subset is just the sum of 12371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * each input element's hash code times the number of sets that element 12381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * appears in. Each element appears in exactly half of the 2^n sets, so: 12391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 12401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return inputSet.hashCode() << (inputSet.size() - 1); 12411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public String toString() { 12441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return "powerSet(" + inputSet + ")"; 12451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 12491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation for {@link Set#hashCode()}. 1250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson static int hashCodeImpl(Set<?> s) { 1252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int hashCode = 0; 1253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Object o : s) { 1254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson hashCode += o != null ? o.hashCode() : 0; 1255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return hashCode; 1257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 12581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 12601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * An implementation for {@link Set#equals(Object)}. 12611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 12621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static boolean equalsImpl(Set<?> s, @Nullable Object object){ 12631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (s == object) { 12641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return true; 12651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (object instanceof Set) { 12671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<?> o = (Set<?>) object; 12681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert try { 12701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return s.size() == o.size() && s.containsAll(o); 12711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (NullPointerException ignored) { 12721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 12731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } catch (ClassCastException ignored) { 12741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 12751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return false; 12781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 12811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Creates a view of Set<B> for a Set<A>, given a bijection between A and B. 12821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * (Modelled for now as InvertibleFunction<A, B>, can't be Converter<A, B> 12831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * because that's not in Guava, though both designs are less than optimal). 12841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Note that the bijection is treated as undefined for values not in the 12851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * given Set<A> - it doesn't have to define a true bijection for those. 12861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 12871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Note that the returned Set's contains method is unsafe - 12881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you *must* pass an instance of B to it, since the bijection 12891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * can only invert B's (not any Object) back to A, so we can 12901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * then delegate the call to the original Set<A>. 12911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 12921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <A, B> Set<B> transform( 12931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Set<A> set, InvertibleFunction<A, B> bijection) { 12941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new TransformedSet<A, B>( 12951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Preconditions.checkNotNull(set, "set"), 12961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Preconditions.checkNotNull(bijection, "bijection") 12971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ); 12981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 13011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Stop-gap measure since there is no bijection related type in Guava. 13021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 13031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract static class InvertibleFunction<A, B> implements Function<A, B> { 13041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert abstract A invert(B b); 13051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public InvertibleFunction<B, A> inverse() { 13071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new InvertibleFunction<B, A>() { 13081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public A apply(B b) { 13091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return InvertibleFunction.this.invert(b); 13101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override B invert(A a) { 13131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return InvertibleFunction.this.apply(a); 13141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // Not required per se, but just for good karma. 13171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public InvertibleFunction<A, B> inverse() { 13181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return InvertibleFunction.this; 13191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 13211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static class TransformedSet<A, B> extends AbstractSet<B> { 13251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Set<A> delegate; 13261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final InvertibleFunction<A, B> bijection; 13271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert TransformedSet(Set<A> delegate, InvertibleFunction<A, B> bijection) { 13291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.delegate = delegate; 13301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert this.bijection = bijection; 13311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Iterator<B> iterator() { 13341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Iterators.transform(delegate.iterator(), bijection); 13351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public int size() { 13381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return delegate.size(); 13391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") // unsafe, passed object *must* be B 13421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean contains(Object o) { 13431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert B b = (B) o; 13441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert A a = bijection.invert(b); 13451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 13461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Mathematically, Converter<A, B> defines a bijection between ALL A's 13471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * on ALL B's. Here we concern ourselves with a subset 13481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of this relation: we only want the part that is defined by a *subset* 13491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of all A's (defined by that Set<A> delegate), and the image 13501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of *that* on B (which is this set). We don't care whether 13511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the converter is *not* a bijection for A's that are not in Set<A> 13521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or B's not in this Set<B>. 13531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 13541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * We only want to return true if and only f the user passes a B instance 13551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * that is contained in precisely in the image of Set<A>. 13561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 13571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * The first test is whether the inverse image of this B is indeed 13581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in Set<A>. But we don't know whether that B belongs in this Set<B> 13591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * or not; if not, the converter is free to return 13601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * anything it wants, even an element of Set<A> (and this relationship 13611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * is not part of the Set<A> <--> Set<B> bijection), and we must not 13621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * be confused by that. So we have to do a final check to see if the 13631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * image of that A is really equivalent to the passed B, which proves 13641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * that the given B belongs indeed in the image of Set<A>. 13651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 13661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return delegate.contains(a) && Objects.equal(bijection.apply(a), o); 13671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean add(B b) { 13701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return delegate.add(bijection.invert(b)); 13711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") // unsafe, passed object *must* be B 13741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean remove(Object o) { 13751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return contains(o) && delegate.remove(bijection.invert((B) o)); 13761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public void clear() { 13791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert delegate.clear(); 13801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 13831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 13841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Remove each element in an iterable from a set. 13851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 13861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static boolean removeAllImpl(Set<?> set, Iterable<?> iterable) { 13871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(jlevy): Have ForwardingSet.standardRemoveAll() call this method. 13881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert boolean changed = false; 13891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert for (Object o : iterable) { 13901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert changed |= set.remove(o); 13911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 13921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return changed; 13931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 1395