Sets.java revision bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dc
1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 2090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Copyright (C) 2007 Google Inc. 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 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Predicate; 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Predicates; 22090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.collect.Collections2.FilteredCollection; 23bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport com.google.common.primitives.Ints; 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.IOException; 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectInputStream; 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.Serializable; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractSet; 29bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport java.util.Arrays; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collections; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Comparator; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.EnumSet; 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.HashMap; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.HashSet; 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.IdentityHashMap; 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.LinkedHashSet; 39bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport java.util.List; 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 41bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport java.util.NoSuchElementException; 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.SortedSet; 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.TreeMap; 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.TreeSet; 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 49bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport static com.google.common.base.Preconditions.checkArgument; 50bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnorimport static com.google.common.base.Preconditions.checkNotNull; 51bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Static utility methods pertaining to {@link Set} instances. Also see this 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * class's counterparts {@link Lists} and {@link Maps}. 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Kevin Bourrillion 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Jared Levy 58bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @since 2010.01.04 <b>stable</b> (imported from Google Collections Library) 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@GwtCompatible 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic final class Sets { 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Sets() {} 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set instance containing the given enum elements. 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Internally, the returned set will be backed by an {@link EnumSet}. 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iteration order of the returned set follows the enum's iteration 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order, not the order in which the elements are provided to the method. 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param anElement one of the elements the set should contain 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param otherElements the rest of the elements the set should contain 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return an immutable set containing those elements, minus duplicates 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet( 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E anElement, E... otherElements) { 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ImmutableEnumSet<E>(EnumSet.of(anElement, otherElements)); 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable set instance containing the given enum elements. 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Internally, the returned set will be backed by an {@link EnumSet}. 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iteration order of the returned set follows the enum's iteration 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order, not the order in which the elements appear in the given collection. 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements, all of the same {@code enum} type, that the 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * set should contain 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return an immutable set containing those elements, minus duplicates 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // http://code.google.com/p/google-web-toolkit/issues/detail?id=3028 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @GwtCompatible(serializable = true) 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Enum<E>> ImmutableSet<E> immutableEnumSet( 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterable<E> elements) { 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<E> iterator = elements.iterator(); 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!iterator.hasNext()) { 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return ImmutableSet.of(); 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (elements instanceof EnumSet) { 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EnumSet<E> enumSetClone = EnumSet.copyOf((EnumSet<E>) elements); 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ImmutableEnumSet<E>(enumSetClone); 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson E first = iterator.next(); 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EnumSet<E> set = EnumSet.of(first); 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (iterator.hasNext()) { 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.add(iterator.next()); 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ImmutableEnumSet<E>(set); 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a new {@code EnumSet} instance containing the given elements. 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unlike {@link EnumSet#copyOf(Collection)}, this method does not produce an 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * exception on an empty collection, and it may be called on any iterable, not 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * just a {@code Collection}. 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Enum<E>> EnumSet<E> newEnumSet(Iterable<E> iterable, 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Class<E> elementType) { 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * TODO: noneOf() and addAll() will both throw NullPointerExceptions when 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * appropriate. However, NullPointerTester will fail on this method because 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * it passes in Class.class instead of an enum type. This means that, when 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iterable is null but elementType is not, noneOf() will throw a 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ClassCastException before addAll() has a chance to throw a 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * NullPointerException. NullPointerTester considers this a failure. 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Ideally the test would be fixed, but it would require a special case for 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Class<E> where E extends Enum. Until that happens (if ever), leave 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * checkNotNull() here. For now, contemplate the irony that checking 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elementType, the problem argument, is harmful, while checking iterable, 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the innocent bystander, is effective. 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(iterable); 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EnumSet<E> set = EnumSet.noneOf(elementType); 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterables.addAll(set, iterable); 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // HashSet 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i>, empty {@code HashSet} instance. 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required, use {@link 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSet#of()} instead. 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * EnumSet#noneOf} instead. 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, empty {@code HashSet} 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> HashSet<E> newHashSet() { 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new HashSet<E>(); 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i> {@code HashSet} instance containing the given 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements in unspecified order. 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required and the elements are 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * non-null, use {@link ImmutableSet#of(Object[])} instead. 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use {@link 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * EnumSet#of(Enum, Enum[])} instead. 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements that the set should contain 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code HashSet} containing those elements (minus duplicates) 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> HashSet<E> newHashSet(E... elements) { 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int capacity = Maps.capacity(elements.length); 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson HashSet<E> set = new HashSet<E>(capacity); 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collections.addAll(set, elements); 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates an empty {@code HashSet} instance with enough capacity to hold the 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * specified number of elements without rehashing. 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param expectedSize the expected size 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, empty {@code HashSet} with enough capacity to hold {@code 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * expectedSize} elements without rehashing 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code expectedSize} is negative 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> HashSet<E> newHashSetWithExpectedSize(int expectedSize) { 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new HashSet<E>(Maps.capacity(expectedSize)); 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i> {@code HashSet} instance containing the given 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements in unspecified order. 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required and the elements are 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead. 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if {@code E} is an {@link Enum} type, use 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #newEnumSet(Iterable, Class)} instead. 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements that the set should contain 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code HashSet} containing those elements (minus duplicates) 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> HashSet<E> newHashSet(Iterable<? extends E> elements) { 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (elements instanceof Collection) { 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<? extends E> collection = (Collection<? extends E>) elements; 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new HashSet<E>(collection); 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return newHashSet(elements.iterator()); 210090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 211090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i> {@code HashSet} instance containing the given 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements in unspecified order. 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required and the elements are 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead. 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if {@code E} is an {@link Enum} type, you should create an 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link EnumSet} instead. 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements that the set should contain 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code HashSet} containing those elements (minus duplicates) 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> HashSet<E> newHashSet(Iterator<? extends E> elements) { 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson HashSet<E> set = newHashSet(); 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (elements.hasNext()) { 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.add(elements.next()); 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // LinkedHashSet 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i>, empty {@code LinkedHashSet} instance. 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required, use {@link 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSet#of()} instead. 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 242090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, empty {@code LinkedHashSet} 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> LinkedHashSet<E> newLinkedHashSet() { 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashSet<E>(); 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i> {@code LinkedHashSet} instance containing the 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * given elements in order. 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required and the elements are 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * non-null, use {@link ImmutableSet#copyOf(Iterable)} instead. 254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements that the set should contain, in order 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code LinkedHashSet} containing those elements (minus 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * duplicates) 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> LinkedHashSet<E> newLinkedHashSet( 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterable<? extends E> elements) { 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (elements instanceof Collection) { 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<? extends E> collection = (Collection<? extends E>) elements; 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedHashSet<E>(collection); 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson LinkedHashSet<E> set = newLinkedHashSet(); 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (E element : elements) { 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.add(element); 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // TreeSet 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i>, empty {@code TreeSet} instance sorted by the 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * natural sort ordering of its elements. 279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required, use {@link 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSortedSet#of()} instead. 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, empty {@code TreeSet} 284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") // allow ungenerified Comparable types 286090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Comparable> TreeSet<E> newTreeSet() { 287090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new TreeSet<E>(); 288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 289090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i> {@code TreeSet} instance containing the given 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * elements sorted by their natural ordering. 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required, use {@link 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSortedSet#copyOf(Iterable)} instead. 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> If {@code elements} is a {@code SortedSet} with an explicit 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparator, this method has different behavior than 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link TreeSet#TreeSet(SortedSet)}, which returns a {@code TreeSet} with 300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that comparator. 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param elements the elements that the set should contain 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new {@code TreeSet} containing those elements (minus duplicates) 304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") // allow ungenerified Comparable types 306090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Comparable> TreeSet<E> newTreeSet( 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterable<? extends E> elements) { 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson TreeSet<E> set = newTreeSet(); 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (E element : elements) { 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.add(element); 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a <i>mutable</i>, empty {@code TreeSet} instance with the given 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * comparator. 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> if mutability is not required, use {@code 320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ImmutableSortedSet.orderedBy(comparator).build()} instead. 321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param comparator the comparator to use to sort the set 323090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, empty {@code TreeSet} 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws NullPointerException if {@code comparator} is null 325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> TreeSet<E> newTreeSet(Comparator<? super E> comparator) { 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new TreeSet<E>(checkNotNull(comparator)); 328090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates an {@code EnumSet} consisting of all enum values that are not in 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the specified collection. If the collection is an {@link EnumSet}, this 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * method has the same behavior as {@link EnumSet#complementOf}. Otherwise, 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the specified collection must contain at least one element, in order to 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * determine the element type. If the collection could be empty, use 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #complementOf(Collection, Class)} instead of this method. 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param collection the collection whose complement should be stored in the 339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * enum set 340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, modifiable {@code EnumSet} containing all values of the enum 341090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that aren't present in the given collection 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code collection} is not an 343090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code EnumSet} instance and contains no elements 344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Enum<E>> EnumSet<E> complementOf( 346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<E> collection) { 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection instanceof EnumSet) { 348090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return EnumSet.complementOf((EnumSet<E>) collection); 349090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(!collection.isEmpty(), 351090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson "collection is empty; use the other version of this method"); 352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Class<E> type = collection.iterator().next().getDeclaringClass(); 353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return makeComplementByHand(collection, type); 354090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 355090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 356090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 357090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates an {@code EnumSet} consisting of all enum values that are not in 358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the specified collection. This is equivalent to 359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link EnumSet#complementOf}, but can act on any input collection, as long 360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * as the elements are of enum type. 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param collection the collection whose complement should be stored in the 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code EnumSet} 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param type the type of the elements in the set 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a new, modifiable {@code EnumSet} initially containing all the 366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * values of the enum not present in the given collection 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E extends Enum<E>> EnumSet<E> complementOf( 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<E> collection, Class<E> type) { 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(collection); 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (collection instanceof EnumSet) 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ? EnumSet.complementOf((EnumSet<E>) collection) 373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson : makeComplementByHand(collection, type); 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static <E extends Enum<E>> EnumSet<E> makeComplementByHand( 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<E> collection, Class<E> type) { 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EnumSet<E> result = EnumSet.allOf(type); 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson result.removeAll(collection); 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Regarding newSetForMap() and SetFromMap: 385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Written by Doug Lea with assistance from members of JCP JSR-166 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Expert Group and released to the public domain, as explained at 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://creativecommons.org/licenses/publicdomain 389090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 392090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a set backed by the specified map. The resulting set displays 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the same ordering, concurrency, and performance characteristics as the 394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * backing map. In essence, this factory method provides a {@link Set} 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * implementation corresponding to any {@link Map} implementation. There is no 396090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * need to use this method on a {@link Map} implementation that already has a 397090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * corresponding {@link Set} implementation (such as {@link HashMap} or 398090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link TreeMap}). 399090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 400090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Each method invocation on the set returned by this method results in 401090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * exactly one method invocation on the backing map or its <tt>keySet</tt> 402090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * view, with one exception. The <tt>addAll</tt> method is implemented as a 403090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * sequence of <tt>put</tt> invocations on the backing map. 404090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 405090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The specified map must be empty at the time this method is invoked, 406090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and should not be accessed directly after this method returns. These 407090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * conditions are ensured if the map is created empty, passed directly 408090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to this method, and no reference to the map is retained, as illustrated 409090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * in the following code fragment: <pre> {@code 410090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 411090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Set<Object> identityHashSet = Sets.newSetFromMap( 412090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * new IdentityHashMap<Object, Boolean>());}</pre> 413090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 414090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This method has the same behavior as the JDK 6 method 415090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code Collections.newSetFromMap()}. The returned set is serializable if 416090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the backing map is. 417090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 418090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param map the backing map 419090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return the set backed by the map 420090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if <tt>map</tt> is not empty 421090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 422090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> Set<E> newSetFromMap(Map<E, Boolean> map) { 423090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SetFromMap<E>(map); 424090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 425090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 426090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class SetFromMap<E> extends AbstractSet<E> 427090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements Set<E>, Serializable { 428090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private final Map<E, Boolean> m; // The backing map 429090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Set<E> s; // Its keySet 430090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 431090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SetFromMap(Map<E, Boolean> map) { 432090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(map.isEmpty(), "Map is non-empty"); 433090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson m = map; 434090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson s = map.keySet(); 435090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 436090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 437090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public void clear() { 438090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson m.clear(); 439090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 440090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 441090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return m.size(); 442090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 443090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 444090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return m.isEmpty(); 445090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 446090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object o) { 447090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return m.containsKey(o); 448090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 449090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean remove(Object o) { 450090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return m.remove(o) != null; 451090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 452090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean add(E e) { 453090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return m.put(e, Boolean.TRUE) == null; 454090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 455090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 456090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.iterator(); 457090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 458090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Object[] toArray() { 459090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.toArray(); 460090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 461090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public <T> T[] toArray(T[] a) { 462090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.toArray(a); 463090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 464090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 465090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.toString(); 466090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 467090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 468090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.hashCode(); 469090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 470090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 471090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this == object || this.s.equals(object); 472090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 473090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsAll(Collection<?> c) { 474090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.containsAll(c); 475090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 476090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> c) { 477090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.removeAll(c); 478090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 479090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> c) { 480090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return s.retainAll(c); 481090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 482090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 483090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // addAll is the only inherited implementation 484090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 485bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor private static final long serialVersionUID = 0; 486090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 487090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void readObject(ObjectInputStream stream) 488090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throws IOException, ClassNotFoundException { 489090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultReadObject(); 490090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson s = m.keySet(); 491090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 492090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 493090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 494090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 495090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * An unmodifiable view of a set which may be backed by other sets; this view 496090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * will change as the backing sets do. Contains methods to copy the data into 497090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a new set which will then remain stable. There is usually no reason to 498090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * retain a reference of type {@code SetView}; typically, you either use it 499090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * as a plain {@link Set}, or immediately invoke {@link #immutableCopy} or 500090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #copyInto} and forget the {@code SetView} itself. 501090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 502090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public abstract static class SetView<E> extends AbstractSet<E> { 503090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private SetView() {} // no subclasses but our own 504090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 505090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 506090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an immutable copy of the current contents of this set view. 507090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Does not support null elements. 508090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 509090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Warning:</b> this may have unexpected results if a backing set of 510090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * this view uses a nonstandard notion of equivalence, for example if it is 511090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a {@link TreeSet} using a comparator that is inconsistent with {@link 512090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Object#equals(Object)}. 513090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 514090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ImmutableSet<E> immutableCopy() { 515090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return ImmutableSet.copyOf(this); 516090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 517090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 518090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 519090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Copies the current contents of this set view into an existing set. This 520090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * method has equivalent behavior to {@code set.addAll(this)}, assuming that 521090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * all the sets involved are based on the same notion of equivalence. 522bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 523bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @return a reference to {@code set}, for convenience 524090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 525090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Note: S should logically extend Set<? super E> but can't due to either 526090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // some javac bug or some weirdness in the spec, not sure which. 527090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public <S extends Set<E>> S copyInto(S set) { 528090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.addAll(this); 529090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 530090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 531090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 532090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 533090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 534090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an unmodifiable <b>view</b> of the union of two sets. The returned 535090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * set contains all elements that are contained in either backing set. 536090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Iterating over the returned set iterates first over all the elements of 537090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code set1}, then over each element of {@code set2}, in order, that is not 538090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * contained in {@code set1}. 539090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 540090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Results are undefined if {@code set1} and {@code set2} are sets based on 541090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * different equivalence relations (as {@link HashSet}, {@link TreeSet}, and 542090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the {@link Map#keySet} of an {@link IdentityHashMap} all are). 543090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 544090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> The returned view performs better when {@code set1} is the 545090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * smaller of the two sets. If you have reason to believe one of your sets 546090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * will generally be smaller than the other, pass it first. 547090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 548090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> SetView<E> union( 549090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<? extends E> set1, final Set<? extends E> set2) { 550090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set1, "set1"); 551090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set2, "set2"); 552090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 553090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // TODO: once we have OrderedIterators, check if these are compatible 554090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // sorted sets and use that instead if so 555090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 556090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<? extends E> set2minus1 = difference(set2, set1); 557090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 558090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SetView<E>() { 559090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 560090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.size() + set2minus1.size(); 561090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 562090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 563090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.isEmpty() && set2.isEmpty(); 564090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 565090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 566090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.unmodifiableIterator( 567090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterators.concat(set1.iterator(), set2minus1.iterator())); 568090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 569090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object object) { 570090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.contains(object) || set2.contains(object); 571090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 572090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public <S extends Set<E>> S copyInto(S set) { 573090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.addAll(set1); 574090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson set.addAll(set2); 575090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set; 576090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 577090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ImmutableSet<E> immutableCopy() { 578090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ImmutableSet.Builder<E>() 579090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson .addAll(set1).addAll(set2).build(); 580090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 581090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 582090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 583090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 584090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 585090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an unmodifiable <b>view</b> of the intersection of two sets. The 586090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returned set contains all elements that are contained by both backing sets. 587090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * The iteration order of the returned set matches that of {@code set1}. 588090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 589090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Results are undefined if {@code set1} and {@code set2} are sets based 590090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * on different equivalence relations (as {@code HashSet}, {@code TreeSet}, 591090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and the keySet of an {@code IdentityHashMap} all are). 592090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 593090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p><b>Note:</b> The returned view performs slightly better when {@code 594090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * set1} is the smaller of the two sets. If you have reason to believe one of 595090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * your sets will generally be smaller than the other, pass it first. 596090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unfortunately, since this method sets the generic type of the returned set 597090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * based on the type of the first set passed, this could in rare cases force 598090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you to make a cast, for example: <pre> {@code 599090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 600090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Set<Object> aFewBadObjects = ... 601090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Set<String> manyBadStrings = ... 602090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 603090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * // impossible for a non-String to be in the intersection 604090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * SuppressWarnings("unchecked") 605090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Set<String> badStrings = (Set) Sets.intersection( 606090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * aFewBadObjects, manyBadStrings);}</pre> 607090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 608090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This is unfortunate, but should come up only very rarely. 609090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 610090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> SetView<E> intersection( 611090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<E> set1, final Set<?> set2) { 612090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set1, "set1"); 613090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set2, "set2"); 614090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 615090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // TODO: once we have OrderedIterators, check if these are compatible 616090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // sorted sets and use that instead if so 617090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 618090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Predicate<Object> inSet2 = Predicates.in(set2); 619090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SetView<E>() { 620090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 621090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.filter(set1.iterator(), inSet2); 622090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 623090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 624090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.size(iterator()); 625090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 626090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 627090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return !iterator().hasNext(); 628090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 629090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object object) { 630090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.contains(object) && set2.contains(object); 631090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 632090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsAll(Collection<?> collection) { 633090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.containsAll(collection) 634090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson && set2.containsAll(collection); 635090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 636090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 637090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 638090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 639090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 640090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an unmodifiable <b>view</b> of the difference of two sets. The 641090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returned set contains all elements that are contained by {@code set1} and 642090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * not contained by {@code set2}. {@code set2} may also contain elements not 643090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * present in {@code set1}; these are simply ignored. The iteration order of 644090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the returned set matches that of {@code set1}. 645090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 646090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Results are undefined if {@code set1} and {@code set2} are sets based 647090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * on different equivalence relations (as {@code HashSet}, {@code TreeSet}, 648090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and the keySet of an {@code IdentityHashMap} all are). 649090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 650090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> SetView<E> difference( 651090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<E> set1, final Set<?> set2) { 652090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set1, "set1"); 653090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(set2, "set2"); 654090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 655090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // TODO: once we have OrderedIterators, check if these are compatible 656090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // sorted sets and use that instead if so 657090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 658090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Predicate<Object> notInSet2 = Predicates.not(Predicates.in(set2)); 659090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SetView<E>() { 660090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<E> iterator() { 661090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.filter(set1.iterator(), notInSet2); 662090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 663090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 664090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.size(iterator()); 665090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 666090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean isEmpty() { 667090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set2.containsAll(set1); 668090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 669090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object element) { 670090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return set1.contains(element) && !set2.contains(element); 671090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 672090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 673090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 674090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 675090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 676090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the elements of {@code unfiltered} that satisfy a predicate. The 677090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returned set is a live view of {@code unfiltered}; changes to one affect 678090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the other. 679090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 680090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The resulting set's iterator does not support {@code remove()}, but all 681090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * other set methods are supported. The set's {@code add()} and 682090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code addAll()} methods throw an {@link IllegalArgumentException} if an 683090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * element that doesn't satisfy the predicate is provided. When methods such 684090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * as {@code removeAll()} and {@code clear()} are called on the filtered set, 685090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * only elements that satisfy the filter will be removed from the underlying 686090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collection. 687090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 688090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned set isn't threadsafe or serializable, even if 689090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code unfiltered} is. 690090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 691090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Many of the filtered set's methods, such as {@code size()}, iterate 692090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * across every element in the underlying set and determine which elements 693090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * satisfy the filter. When a live view is <i>not</i> needed, it may be faster 694090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to copy {@code Iterables.filter(unfiltered, predicate)} and use the copy. 695090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 696090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <E> Set<E> filter( 697090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<E> unfiltered, Predicate<? super E> predicate) { 698090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (unfiltered instanceof FilteredSet) { 699090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Support clear(), removeAll(), and retainAll() when filtering a filtered 700090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // collection. 701090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson FilteredSet<E> filtered = (FilteredSet<E>) unfiltered; 702090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Predicate<E> combinedPredicate 703090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = Predicates.<E>and(filtered.predicate, predicate); 704090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new FilteredSet<E>( 705090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson (Set<E>) filtered.unfiltered, combinedPredicate); 706090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 707090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 708090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new FilteredSet<E>( 709090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(unfiltered), checkNotNull(predicate)); 710090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 711090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 712090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static class FilteredSet<E> extends FilteredCollection<E> 713090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements Set<E> { 714090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson FilteredSet(Set<E> unfiltered, Predicate<? super E> predicate) { 715090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(unfiltered, predicate); 716090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 717090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 718090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 719090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Collections2.setEquals(this, object); 720090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 721090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 722090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 723090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return hashCodeImpl(this); 724090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 725090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 726090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 727090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 728bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Returns every possible list that can be formed by choosing one element 729bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * from each of the given sets in order; the "n-ary 730bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian 731bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * product</a>" of the sets. For example: <pre class="code"> {@code 732bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 733bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * cartesianProduct(ImmutableList.of( 734bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * ImmutableSet.of(1, 2), 735bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * ImmutableSet.of("A", "B", "C")))}</pre> 736bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 737bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * returns a set containing six lists: 738bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 739bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <ul> 740bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "A")} 741bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "B")} 742bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "C")} 743bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "A")} 744bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "B")} 745bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "C")} 746bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * </ul> 747bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 748bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * The order in which these lists are returned is not guaranteed, however the 749bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * position of an element inside a tuple always corresponds to the position of 750bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * the set from which it came in the input list. Note that if any input set is 751bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * empty, the Cartesian product will also be empty. If no sets at all are 752bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * provided (an empty list), the resulting Cartesian product has one element, 753bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * an empty list (counter-intuitive, but mathematically consistent). 754bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 755bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @param sets the sets to choose elements from, in the order that 756bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * the elements chosen from those sets should appear in the resulting 757bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * lists 758bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @param <B> any common base class shared by all axes (often just {@link 759bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Object}) 760bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @return the Cartesian product, as an immutable set containing immutable 761bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * lists 762bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @throws NullPointerException if {@code sets}, any one of the {@code sets}, 763bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * or any element of a provided set is null 764bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @since 2010.01.04 <b>tentative</b> 765bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor */ 766bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public static <B> Set<List<B>> cartesianProduct( 767bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor List<? extends Set<? extends B>> sets) { 768bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor CartesianSet<B> cartesianSet = new CartesianSet<B>(sets); 769bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return cartesianSet.isEmpty() ? ImmutableSet.<List<B>>of() : cartesianSet; 770bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 771bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 772bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor /** 773bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Returns every possible list that can be formed by choosing one element 774bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * from each of the given sets in order; the "n-ary 775bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <a href="http://en.wikipedia.org/wiki/Cartesian_product">Cartesian 776bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * product</a>" of the sets. For example: <pre class="code"> {@code 777bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 778bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * cartesianProduct( 779bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * ImmutableSet.of(1, 2), 780bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * ImmutableSet.of("A", "B", "C"))}</pre> 781bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 782bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * returns a set containing six lists: 783bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor w 784bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <ul> 785bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "A")} 786bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "B")} 787bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(1, "C")} 788bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "A")} 789bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "B")} 790bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * <li>{@code ImmutableList.of(2, "C")} 791bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * </ul> 792bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 793bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * The order in which these lists are returned is not guaranteed, however the 794bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * position of an element inside a tuple always corresponds to the position of 795bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * the set from which it came in the input list. Note that if any input set is 796bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * empty, the Cartesian product will also be empty. If no sets at all are 797bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * provided, the resulting Cartesian product has one element, an empty list 798bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * (counter-intuitive, but mathematically consistent). 799bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * 800bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @param sets the sets to choose elements from, in the order that 801bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * the elements chosen from those sets should appear in the resulting 802bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * lists 803bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @param <B> any common base class shared by all axes (often just {@link 804bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * Object}) 805bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @return the Cartesian product, as an immutable set containing immutable 806bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * lists 807bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @throws NullPointerException if {@code sets}, any one of the {@code sets}, 808bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * or any element of a provided set is null 809bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor * @since 2010.01.04 <b>tentative</b> 810bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor */ 811bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public static <B> Set<List<B>> cartesianProduct( 812bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Set<? extends B>... sets) { 813bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return cartesianProduct(Arrays.asList(sets)); 814bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 815bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 816bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor private static class CartesianSet<B> extends AbstractSet<List<B>> { 817bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor final ImmutableList<Axis> axes; 818bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor final int size; 819bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 820bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor CartesianSet(List<? extends Set<? extends B>> sets) { 821bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor long dividend = 1; 822bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor ImmutableList.Builder<Axis> builder = ImmutableList.builder(); 823bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor for (Set<? extends B> set : sets) { 824bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Axis axis = new Axis(set, (int) dividend); // check overflow at end 825bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor builder.add(axis); 826bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor dividend *= axis.size(); 827bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 828bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor this.axes = builder.build(); 829bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor size = Ints.checkedCast(dividend); 830bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 831bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 832bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public int size() { 833bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return size; 834bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 835bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 836bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public UnmodifiableIterator<List<B>> iterator() { 837bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return new UnmodifiableIterator<List<B>>() { 838bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int index; 839bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 840bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public boolean hasNext() { 841bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return index < size; 842bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 843bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 844bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor public List<B> next() { 845bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (!hasNext()) { 846bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor throw new NoSuchElementException(); 847bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 848bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 849bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Object[] tuple = new Object[axes.size()]; 850bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor for (int i = 0 ; i < tuple.length; i++) { 851bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor tuple[i] = axes.get(i).getForIndex(index); 852bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 853bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor index++; 854bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 855bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @SuppressWarnings("unchecked") // only B's are put in here 856bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor List<B> result = (ImmutableList<B>) ImmutableList.of(tuple); 857bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return result; 858bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 859bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor }; 860bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 861bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 862bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public boolean contains(Object element) { 863bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (!(element instanceof List<?>)) { 864bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return false; 865bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 866bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor List<?> tuple = (List<?>) element; 867bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int dimensions = axes.size(); 868bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (tuple.size() != dimensions) { 869bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return false; 870bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 871bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor for (int i = 0; i < dimensions; i++) { 872bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (!axes.get(i).contains(tuple.get(i))) { 873bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return false; 874bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 875bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 876bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return true; 877bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 878bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 879bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public boolean equals(@Nullable Object object) { 880bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // Warning: this is broken if size() == 0, so it is critical that we 881bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // substitute an empty ImmutableSet to the user in place of this 882bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (object instanceof CartesianSet<?>) { 883bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor CartesianSet<?> that = (CartesianSet) object; 884bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return this.axes.equals(that.axes); 885bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 886bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return super.equals(object); 887bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 888bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 889bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public int hashCode() { 890bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // Warning: this is broken if size() == 0, so it is critical that we 891bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // substitute an empty ImmutableSet to the user in place of this 892bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 893bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // It's a weird formula, but tests prove it works. 894bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int adjust = size - 1; 895bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor for (int i = 0; i < axes.size(); i++) { 896bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor adjust *= 31; 897bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 898bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return axes.hashCode() + adjust; 899bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 900bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 901bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor private class Axis { 902bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor final ImmutableSet<? extends B> choices; 903bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor final int dividend; 904bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 905bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Axis(Set<? extends B> set, int dividend) { 906bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor choices = ImmutableSet.copyOf(set); 907bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor this.dividend = dividend; 908bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 909bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 910bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor int size() { 911bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return choices.size(); 912bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 913bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 914bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor B getForIndex(int index) { 915bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return choices.asList().get(index / dividend % size()); 916bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 917bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 918bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor boolean contains(Object target) { 919bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return choices.contains(target); 920bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 921bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 922bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public boolean equals(Object obj) { 923bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor if (obj instanceof CartesianSet.Axis) { 924bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor CartesianSet.Axis that = (CartesianSet.Axis) obj; 925bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return this.choices.equals(that.choices); 926bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // dividends must be equal or we wouldn't have gotten this far 927bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 928bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return false; 929bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 930bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 931bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor @Override public int hashCode() { 932bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // an opportunistic formula chosen because it happens to make 933bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor // CartesianSet.hashCode() work! 934bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return size / choices.size() * choices.hashCode(); 935bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 936bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 937bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor } 938bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor 939bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor /** 940090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Calculates and returns the hash code of {@code s}. 941090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 942090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson static int hashCodeImpl(Set<?> s) { 943090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int hashCode = 0; 944090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Object o : s) { 945090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson hashCode += o != null ? o.hashCode() : 0; 946090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 947090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return hashCode; 948090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 949090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 950