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 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkArgument; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkNotNull; 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkState; 22090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.Serializable; 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractCollection; 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractMap; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collections; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Comparator; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.ConcurrentModificationException; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.List; 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.ListIterator; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map.Entry; 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.RandomAccess; 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.SortedMap; 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.SortedSet; 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Basic implementation of the {@link Multimap} interface. This class represents 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * a multimap as a map that associates each key with a collection of values. All 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * methods of {@link Multimap} are supported, including those specified as 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * optional in the interface. 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>To implement a multimap, a subclass must define the method {@link 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * #createCollection()}, which creates an empty collection of values for a key. 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The multimap constructor takes a map that has a single entry for each 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distinct key. When you insert a key-value pair with a key that isn't already 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * in the multimap, {@code AbstractMultimap} calls {@link #createCollection()} 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to create the collection of values for that key. The subclass should not call 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #createCollection()} directly, and a new instance should be created 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * every time the method is called. 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>For example, the subclass could pass a {@link java.util.TreeMap} during 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * construction, and {@link #createCollection()} could return a {@link 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * java.util.TreeSet}, in which case the multimap's iterators would propagate 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * through the keys and values in sorted order. 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Keys and values may be null, as long as the underlying collection classes 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * support null elements. 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The collections created by {@link #createCollection()} may or may not 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * allow duplicates. If the collection, such as a {@link Set}, does not support 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * duplicates, an added key-value pair will replace an existing pair with the 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * same key and value, if such a pair is present. With collections like {@link 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * List} that allow duplicates, the collection will keep the existing key-value 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * pairs while adding a new pair. 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This class is not threadsafe when any concurrent operations update the 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap, even if the underlying map and {@link #createCollection()} method 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * return threadsafe classes. Concurrent read operations will work correctly. To 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * allow concurrent update operations, wrap your multimap with a call to {@link 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multimaps#synchronizedMultimap}. 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>For serialization to work, the subclass must specify explicit 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code readObject} and {@code writeObject} methods. 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Jared Levy 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@GwtCompatible 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonabstract class AbstractMultimap<K, V> implements Multimap<K, V>, Serializable { 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Here's an outline of the overall design. 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * The map variable contains the collection of values associated with each 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key. When a key-value pair is added to a multimap that didn't previously 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * contain any values for that key, a new collection generated by 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * createCollection is added to the map. That same collection instance 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * remains in the map as long as the multimap has any values for the key. If 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * all values for the key are removed, the key and collection are removed 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * from the map. 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * The get method returns a WrappedCollection, which decorates the collection 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * in the map (if the key is present) or an empty collection (if the key is 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * not present). When the collection delegate in the WrappedCollection is 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * empty, the multimap may contain subsequently added values for that key. To 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * handle that situation, the WrappedCollection checks whether map contains 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * an entry for the provided key, and if so replaces the delegate. 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Map<K, Collection<V>> map; 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient int totalSize; 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a new multimap that uses the provided map. 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param map place to store the mapping from each key to its corresponding 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * values 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code map} is not empty 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson protected AbstractMultimap(Map<K, Collection<V>> map) { 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(map.isEmpty()); 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.map = map; 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Used during deserialization only. */ 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final void setMap(Map<K, Collection<V>> map) { 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.map = map; 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize = 0; 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Collection<V> values : map.values()) { 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(!values.isEmpty()); 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize += values.size(); 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates the collection of values for a single key. 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Collections with weak, soft, or phantom references are not supported. 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Each call to {@code createCollection} should create a new instance. 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned collection class determines whether duplicate key-value 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * pairs are allowed. 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return an empty collection of values 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson abstract Collection<V> createCollection(); 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates the collection of values for an explicitly provided key. By 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * default, it simply calls {@link #createCollection()}, which is the correct 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * behavior for most implementations. The {@link LinkedHashMultimap} class 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * overrides it. 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param key key to associate with values in the collection 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return an empty collection of values 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> createCollection(@Nullable K key) { 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return createCollection(); 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map<K, Collection<V>> backingMap() { 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map; 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Query Operations 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return totalSize; 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean isEmpty() { 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return totalSize == 0; 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsKey(@Nullable Object key) { 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map.containsKey(key); 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsValue(@Nullable Object value) { 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Collection<V> collection : map.values()) { 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection.contains(value)) { 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsEntry(@Nullable Object key, @Nullable Object value) { 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = map.get(key); 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return collection != null && collection.contains(value); 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Modification Operations 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean put(@Nullable K key, @Nullable V value) { 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = getOrCreateCollection(key); 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection.add(value)) { 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize++; 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 210090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 211090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Collection<V> getOrCreateCollection(@Nullable K key) { 212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = map.get(key); 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection == null) { 214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection = createCollection(key); 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson map.put(key, collection); 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return collection; 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean remove(@Nullable Object key, @Nullable Object value) { 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = map.get(key); 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection == null) { 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = collection.remove(value); 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize--; 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection.isEmpty()) { 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson map.remove(key); 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Bulk Operations 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean putAll(@Nullable K key, Iterable<? extends V> values) { 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!values.iterator().hasNext()) { 242090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = getOrCreateCollection(key); 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldSize = collection.size(); 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = false; 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (values instanceof Collection) { 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collection<? extends V> c = Collections2.cast(values); 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson changed = collection.addAll(c); 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (V value : values) { 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson changed |= collection.add(value); 254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize += (collection.size() - oldSize); 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = false; 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Map.Entry<? extends K, ? extends V> entry : multimap.entries()) { 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson changed |= put(entry.getKey(), entry.getValue()); 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned collection is immutable. 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Collection<V> replaceValues( 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Nullable K key, Iterable<? extends V> values) { 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<? extends V> iterator = values.iterator(); 279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!iterator.hasNext()) { 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return removeAll(key); 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = getOrCreateCollection(key); 284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> oldValues = createCollection(); 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson oldValues.addAll(collection); 286090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 287090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize -= collection.size(); 288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection.clear(); 289090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (iterator.hasNext()) { 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection.add(iterator.next())) { 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize++; 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return unmodifiableCollectionSubclass(oldValues); 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned collection is immutable. 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Collection<V> removeAll(@Nullable Object key) { 306090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = map.remove(key); 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> output = createCollection(); 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection != null) { 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson output.addAll(collection); 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize -= collection.size(); 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection.clear(); 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return unmodifiableCollectionSubclass(output); 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Collection<V> unmodifiableCollectionSubclass( 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection) { 320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection instanceof SortedSet) { 321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Collections.unmodifiableSortedSet((SortedSet<V>) collection); 322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (collection instanceof Set) { 323090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Collections.unmodifiableSet((Set<V>) collection); 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (collection instanceof List) { 325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Collections.unmodifiableList((List<V>) collection); 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Collections.unmodifiableCollection(collection); 328090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void clear() { 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Clear each collection, to make previously returned collections empty. 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Collection<V> collection : map.values()) { 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection.clear(); 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson map.clear(); 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize = 0; 339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 341090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Views 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 343090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned collection is not serializable. 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 349090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Collection<V> get(@Nullable K key) { 350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = map.get(key); 351090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection == null) { 352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection = createCollection(key); 353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 354090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return wrapCollection(key, collection); 355090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 356090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 357090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Generates a decorated collection that remains consistent with the values in 359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the multimap for the provided key. Changes to the multimap may alter the 360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returned collection, and vice versa. 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Collection<V> wrapCollection( 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Nullable K key, Collection<V> collection) { 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection instanceof SortedSet) { 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new WrappedSortedSet(key, (SortedSet<V>) collection, null); 366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (collection instanceof Set) { 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new WrappedSet(key, (Set<V>) collection); 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (collection instanceof List) { 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return wrapList(key, (List<V>) collection, null); 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new WrappedCollection(key, collection, null); 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private List<V> wrapList( 3761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable K key, List<V> list, @Nullable WrappedCollection ancestor) { 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (list instanceof RandomAccess) 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ? new RandomAccessWrappedList(key, list, ancestor) 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson : new WrappedList(key, list, ancestor); 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Collection decorator that stays in sync with the multimap values for a key. 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * There are two kinds of wrapped collections: full and subcollections. Both 385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * have a delegate pointing to the underlying collection class. 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Full collections, identified by a null ancestor field, contain all 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap values for a given key. Its delegate is a value in {@link 389090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * AbstractMultimap#map} whenever the delegate is non-empty. The {@code 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * refreshIfEmpty}, {@code removeIfEmpty}, and {@code addToMap} methods ensure 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * that the {@code WrappedCollection} and map remain consistent. 392090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>A subcollection, such as a sublist, contains some of the values for a 394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * given key. Its ancestor field points to the full wrapped collection with 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * all values for the key. The subcollection {@code refreshIfEmpty}, {@code 396090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * removeIfEmpty}, and {@code addToMap} methods call the corresponding methods 397090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * of the full wrapped collection. 398090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 399090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class WrappedCollection extends AbstractCollection<V> { 400090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final K key; 401090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> delegate; 402090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final WrappedCollection ancestor; 403090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Collection<V> ancestorDelegate; 404090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 405090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson WrappedCollection(@Nullable K key, Collection<V> delegate, 406090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Nullable WrappedCollection ancestor) { 407090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.key = key; 408090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.delegate = delegate; 409090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.ancestor = ancestor; 410090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.ancestorDelegate 411090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = (ancestor == null) ? null : ancestor.getDelegate(); 412090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 413090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 414090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 415090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * If the delegate collection is empty, but the multimap has values for the 416090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key, replace the delegate with the new collection for the key. 417090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 418090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>For a subcollection, refresh its ancestor and validate that the 419090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ancestor delegate hasn't changed. 420090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 421090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson void refreshIfEmpty() { 422090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (ancestor != null) { 423090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ancestor.refreshIfEmpty(); 424090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (ancestor.getDelegate() != ancestorDelegate) { 425090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new ConcurrentModificationException(); 426090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 427090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (delegate.isEmpty()) { 428090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> newDelegate = map.get(key); 429090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (newDelegate != null) { 430090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegate = newDelegate; 431090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 432090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 433090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 434090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 435090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 4361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * If collection is empty, remove it from {@code AbstractMultimap.this.map}. 4371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * For subcollections, check whether the ancestor collection is empty. 438090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 439090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson void removeIfEmpty() { 440090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (ancestor != null) { 441090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ancestor.removeIfEmpty(); 442090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (delegate.isEmpty()) { 443090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson map.remove(key); 444090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 445090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 446090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 447090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson K getKey() { 448090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return key; 449090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 450090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 451090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 452090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Add the delegate to the map. Other {@code WrappedCollection} methods 453090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * should call this method after adding elements to a previously empty 454090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collection. 455090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 456090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Subcollection add the ancestor's delegate instead. 457090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 458090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson void addToMap() { 459090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (ancestor != null) { 460090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ancestor.addToMap(); 461090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 462090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson map.put(key, delegate); 463090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 464090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 465090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 466090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 467090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 468090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate.size(); 469090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 470090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 471090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 472090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (object == this) { 473090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 474090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 475090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 476090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate.equals(object); 477090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 478090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 479090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 480090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 481090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate.hashCode(); 482090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 483090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 484090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 485090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 486090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate.toString(); 487090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 488090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 489090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> getDelegate() { 490090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate; 491090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 492090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 493090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<V> iterator() { 494090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 495090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new WrappedIterator(); 496090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 497090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 498090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Collection iterator for {@code WrappedCollection}. */ 499090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson class WrappedIterator implements Iterator<V> { 500090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<V> delegateIterator; 501090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Collection<V> originalDelegate = delegate; 502090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 503090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson WrappedIterator() { 504090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegateIterator = iteratorOrListIterator(delegate); 505090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 506090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 507090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson WrappedIterator(Iterator<V> delegateIterator) { 508090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.delegateIterator = delegateIterator; 509090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 510090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 511090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 512090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * If the delegate changed since the iterator was created, the iterator is 513090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * no longer valid. 514090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 515090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson void validateIterator() { 516090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 517090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (delegate != originalDelegate) { 518090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new ConcurrentModificationException(); 519090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 520090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 521090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 523090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 524090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson validateIterator(); 525090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegateIterator.hasNext(); 526090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 527090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 529090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V next() { 530090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson validateIterator(); 531090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegateIterator.next(); 532090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 533090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 535090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 536090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegateIterator.remove(); 537090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize--; 538090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeIfEmpty(); 539090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 540090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 541090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<V> getDelegateIterator() { 542090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson validateIterator(); 543090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegateIterator; 544090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 545090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 546090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 547090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean add(V value) { 548090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 549090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean wasEmpty = delegate.isEmpty(); 550090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.add(value); 551090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 552090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize++; 553090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (wasEmpty) { 554090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson addToMap(); 555090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 556090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 557090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 558090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 559090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 560090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson WrappedCollection getAncestor() { 561090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return ancestor; 562090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 563090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 564090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // The following methods are provided for better performance. 565090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 566090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean addAll(Collection<? extends V> collection) { 567090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection.isEmpty()) { 568090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 569090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 570090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldSize = size(); // calls refreshIfEmpty 571090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.addAll(collection); 572090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 573090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int newSize = delegate.size(); 574090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize += (newSize - oldSize); 575090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (oldSize == 0) { 576090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson addToMap(); 577090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 578090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 579090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 580090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 581090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 582090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object o) { 583090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 584090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate.contains(o); 585090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 586090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 587090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsAll(Collection<?> c) { 588090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 589090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegate.containsAll(c); 590090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 591090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 592090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public void clear() { 593090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldSize = size(); // calls refreshIfEmpty 594090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (oldSize == 0) { 595090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return; 596090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 597090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegate.clear(); 598090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize -= oldSize; 599090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeIfEmpty(); // maybe shouldn't be removed if this is a sublist 600090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 601090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 602090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean remove(Object o) { 603090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 604090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.remove(o); 605090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 606090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize--; 607090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeIfEmpty(); 608090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 609090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 610090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 611090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 612090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> c) { 613090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (c.isEmpty()) { 614090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 615090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 616090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldSize = size(); // calls refreshIfEmpty 617090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.removeAll(c); 618090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 619090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int newSize = delegate.size(); 620090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize += (newSize - oldSize); 621090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeIfEmpty(); 622090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 623090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 624090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 625090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 626090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> c) { 627090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkNotNull(c); 628090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldSize = size(); // calls refreshIfEmpty 629090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = delegate.retainAll(c); 630090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 631090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int newSize = delegate.size(); 632090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize += (newSize - oldSize); 633090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeIfEmpty(); 634090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 635090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 636090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 637090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 638090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 639090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Iterator<V> iteratorOrListIterator(Collection<V> collection) { 640090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (collection instanceof List) 641090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ? ((List<V>) collection).listIterator() 642090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson : collection.iterator(); 643090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 644090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 645090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Set decorator that stays in sync with the multimap values for a key. */ 646090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class WrappedSet extends WrappedCollection implements Set<V> { 6471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert WrappedSet(@Nullable K key, Set<V> delegate) { 648090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(key, delegate, null); 649090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 650090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 651090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 652090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 653090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * SortedSet decorator that stays in sync with the multimap values for a key. 654090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 655090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class WrappedSortedSet extends WrappedCollection 656090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements SortedSet<V> { 657090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson WrappedSortedSet(@Nullable K key, SortedSet<V> delegate, 658090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Nullable WrappedCollection ancestor) { 659090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(key, delegate, ancestor); 660090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 661090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 662090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SortedSet<V> getSortedSetDelegate() { 663090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (SortedSet<V>) getDelegate(); 664090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 665090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 667090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Comparator<? super V> comparator() { 668090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getSortedSetDelegate().comparator(); 669090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 670090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 672090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V first() { 673090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 674090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getSortedSetDelegate().first(); 675090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 676090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 678090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V last() { 679090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 680090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getSortedSetDelegate().last(); 681090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 682090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 684090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public SortedSet<V> headSet(V toElement) { 685090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 686090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new WrappedSortedSet( 687090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson getKey(), getSortedSetDelegate().headSet(toElement), 688090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson (getAncestor() == null) ? this : getAncestor()); 689090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 690090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 692090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public SortedSet<V> subSet(V fromElement, V toElement) { 693090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 694090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new WrappedSortedSet( 695090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson getKey(), getSortedSetDelegate().subSet(fromElement, toElement), 696090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson (getAncestor() == null) ? this : getAncestor()); 697090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 698090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 700090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public SortedSet<V> tailSet(V fromElement) { 701090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 702090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new WrappedSortedSet( 703090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson getKey(), getSortedSetDelegate().tailSet(fromElement), 704090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson (getAncestor() == null) ? this : getAncestor()); 705090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 706090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 707090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 708090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** List decorator that stays in sync with the multimap values for a key. */ 709090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class WrappedList extends WrappedCollection implements List<V> { 7101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert WrappedList(@Nullable K key, List<V> delegate, 7111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable WrappedCollection ancestor) { 712090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(key, delegate, ancestor); 713090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 714090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 715090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson List<V> getListDelegate() { 716090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (List<V>) getDelegate(); 717090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 718090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 720090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean addAll(int index, Collection<? extends V> c) { 721090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (c.isEmpty()) { 722090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 723090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 724090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldSize = size(); // calls refreshIfEmpty 725090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = getListDelegate().addAll(index, c); 726090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (changed) { 727090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int newSize = getDelegate().size(); 728090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize += (newSize - oldSize); 729090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (oldSize == 0) { 730090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson addToMap(); 731090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 732090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 733090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 734090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 735090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 737090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V get(int index) { 738090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 739090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getListDelegate().get(index); 740090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 741090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 743090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V set(int index, V element) { 744090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 745090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getListDelegate().set(index, element); 746090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 747090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 749090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void add(int index, V element) { 750090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 751090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean wasEmpty = getDelegate().isEmpty(); 752090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson getListDelegate().add(index, element); 753090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize++; 754090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (wasEmpty) { 755090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson addToMap(); 756090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 757090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 758090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 760090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V remove(int index) { 761090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 762090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V value = getListDelegate().remove(index); 763090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize--; 764090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeIfEmpty(); 765090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return value; 766090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 767090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 769090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int indexOf(Object o) { 770090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 771090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getListDelegate().indexOf(o); 772090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 773090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 775090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int lastIndexOf(Object o) { 776090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 777090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getListDelegate().lastIndexOf(o); 778090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 779090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 781090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ListIterator<V> listIterator() { 782090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 783090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new WrappedListIterator(); 784090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 785090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 787090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ListIterator<V> listIterator(int index) { 788090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 789090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new WrappedListIterator(index); 790090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 791090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 793090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public List<V> subList(int fromIndex, int toIndex) { 794090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson refreshIfEmpty(); 795090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return wrapList(getKey(), 7961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert getListDelegate().subList(fromIndex, toIndex), 797090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson (getAncestor() == null) ? this : getAncestor()); 798090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 799090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 800090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** ListIterator decorator. */ 801090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class WrappedListIterator extends WrappedIterator 802090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements ListIterator<V> { 803090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson WrappedListIterator() {} 804090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 805090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public WrappedListIterator(int index) { 806090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(getListDelegate().listIterator(index)); 807090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 808090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 809090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private ListIterator<V> getDelegateListIterator() { 810090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (ListIterator<V>) getDelegateIterator(); 811090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 812090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 814090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasPrevious() { 815090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getDelegateListIterator().hasPrevious(); 816090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 817090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 819090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V previous() { 820090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getDelegateListIterator().previous(); 821090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 822090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 824090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int nextIndex() { 825090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getDelegateListIterator().nextIndex(); 826090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 827090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 829090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int previousIndex() { 830090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return getDelegateListIterator().previousIndex(); 831090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 832090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 834090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void set(V value) { 835090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson getDelegateListIterator().set(value); 836090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 837090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 839090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void add(V value) { 840090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean wasEmpty = isEmpty(); 841090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson getDelegateListIterator().add(value); 842090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize++; 843090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (wasEmpty) { 844090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson addToMap(); 845090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 846090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 847090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 848090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 849090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 850090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 851090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * List decorator that stays in sync with the multimap values for a key and 852090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * supports rapid random access. 853090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 854090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class RandomAccessWrappedList extends WrappedList 855090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements RandomAccess { 8561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert RandomAccessWrappedList(@Nullable K key, List<V> delegate, 857090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Nullable WrappedCollection ancestor) { 858090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(key, delegate, ancestor); 859090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 860090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 861090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 862090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Set<K> keySet; 863090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 865090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Set<K> keySet() { 866090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<K> result = keySet; 867090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (result == null) ? keySet = createKeySet() : result; 868090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 869090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 870090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Set<K> createKeySet() { 871090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (map instanceof SortedMap) 872090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ? new SortedKeySet((SortedMap<K, Collection<V>>) map) : new KeySet(map); 873090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 874090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private class KeySet extends Maps.KeySet<K, Collection<V>> { 876090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 877090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 878090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * This is usually the same as map, except when someone requests a 879090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * subcollection of a {@link SortedKeySet}. 880090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 881090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Map<K, Collection<V>> subMap; 882090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 883090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson KeySet(final Map<K, Collection<V>> subMap) { 884090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.subMap = subMap; 885090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 886090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map<K, Collection<V>> map() { 8891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return subMap; 890090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 891090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 892090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<K> iterator() { 893090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<K>() { 894090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<Map.Entry<K, Collection<V>>> entryIterator 895090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = subMap.entrySet().iterator(); 896090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map.Entry<K, Collection<V>> entry; 897090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 899090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 900090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return entryIterator.hasNext(); 901090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 9021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 903090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K next() { 904090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entry = entryIterator.next(); 905090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return entry.getKey(); 906090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 9071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 908090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 909090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(entry != null); 910090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = entry.getValue(); 911090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entryIterator.remove(); 912090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize -= collection.size(); 913090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection.clear(); 914090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 915090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 916090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 917090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 918090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // The following methods are included for better performance. 919090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 920090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean remove(Object key) { 921090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int count = 0; 922090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = subMap.remove(key); 923090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection != null) { 924090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson count = collection.size(); 925090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection.clear(); 926090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize -= count; 927090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 928090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return count > 0; 929090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 930090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 9321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void clear() { 9331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterators.clear(iterator()); 9341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 936090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsAll(Collection<?> c) { 937090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return subMap.keySet().containsAll(c); 938090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 939090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 940090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 941090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this == object || this.subMap.keySet().equals(object); 942090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 943090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 944090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 945090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return subMap.keySet().hashCode(); 946090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 947090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 948090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 949090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class SortedKeySet extends KeySet implements SortedSet<K> { 950090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 951090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SortedKeySet(SortedMap<K, Collection<V>> subMap) { 952090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(subMap); 953090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 954090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 955090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SortedMap<K, Collection<V>> sortedMap() { 956090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (SortedMap<K, Collection<V>>) subMap; 957090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 958090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 960090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Comparator<? super K> comparator() { 961090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return sortedMap().comparator(); 962090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 963090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 965090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K first() { 966090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return sortedMap().firstKey(); 967090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 968090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 970090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public SortedSet<K> headSet(K toElement) { 971090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SortedKeySet(sortedMap().headMap(toElement)); 972090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 973090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 975090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K last() { 976090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return sortedMap().lastKey(); 977090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 978090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 980090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public SortedSet<K> subSet(K fromElement, K toElement) { 981090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SortedKeySet(sortedMap().subMap(fromElement, toElement)); 982090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 983090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 985090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public SortedSet<K> tailSet(K fromElement) { 986090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SortedKeySet(sortedMap().tailMap(fromElement)); 987090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 988090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 989090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 990090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Multiset<K> multiset; 991090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 993090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Multiset<K> keys() { 994090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multiset<K> result = multiset; 9951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (result == null) { 9961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return multiset = new Multimaps.Keys<K, V>() { 9971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override Multimap<K, V> multimap() { 9981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return AbstractMultimap.this; 999090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 10001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1001090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 10021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 1003090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1004090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1005090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1006090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Removes all values for the provided key. Unlike {@link #removeAll}, it 1007090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returns the number of removed mappings. 1008090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1009090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private int removeValuesForKey(Object key) { 1010090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection; 1011090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson try { 1012090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection = map.remove(key); 1013090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } catch (NullPointerException e) { 1014090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return 0; 1015090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } catch (ClassCastException e) { 1016090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return 0; 1017090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1018090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1019090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int count = 0; 1020090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection != null) { 1021090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson count = collection.size(); 1022090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection.clear(); 1023090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize -= count; 1024090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1025090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return count; 1026090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1027090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1028090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Collection<V> valuesCollection; 1029090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1030090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1031090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 1032090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1033090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iterator generated by the returned collection traverses the values 1034090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * for one key, followed by the values of a second key, and so on. 1035090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 10361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Collection<V> values() { 1037090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> result = valuesCollection; 10381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (result == null) { 10391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return valuesCollection = new Multimaps.Values<K, V>() { 10401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override Multimap<K, V> multimap() { 10411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return AbstractMultimap.this; 10421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1044090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 10451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return result; 1046090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1047090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1048090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Collection<Map.Entry<K, V>> entries; 1049090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 10501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /* 10511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * TODO(kevinb): should we copy this javadoc to each concrete class, so that 10521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * classes like LinkedHashMultimap that need to say something different are 10531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * still able to {@inheritDoc} all the way from Multimap? 10541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1055090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1056090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1057090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 1058090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1059090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iterator generated by the returned collection traverses the values 1060090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * for one key, followed by the values of a second key, and so on. 1061090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1062090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Each entry is an immutable snapshot of a key-value mapping in the 1063090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap, taken at the time the entry is returned by a method call to the 1064090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collection or its iterator. 1065090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 10661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1067090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Collection<Map.Entry<K, V>> entries() { 1068090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<Map.Entry<K, V>> result = entries; 10691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (result == null) ? entries = createEntries() : result; 1070090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1071090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 10721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Collection<Map.Entry<K, V>> createEntries() { 10731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (this instanceof SetMultimap) { 10741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Multimaps.EntrySet<K, V>() { 10751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override Multimap<K, V> multimap() { 10761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return AbstractMultimap.this; 10771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1078090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 10791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Iterator<Entry<K, V>> iterator() { 10801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return createEntryIterator(); 10811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 10821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1083090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 10841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new Multimaps.Entries<K, V>() { 10851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override Multimap<K, V> multimap() { 10861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return AbstractMultimap.this; 1087090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1088090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 10891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Iterator<Entry<K, V>> iterator() { 10901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return createEntryIterator(); 1091090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 10921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 1093090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1094090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1095090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1096090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns an iterator across all key-value map entries, used by {@code 1097090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * entries().iterator()} and {@code values().iterator()}. The default 1098090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * behavior, which traverses the values for one key, the values for a second 1099090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key, and so on, suffices for most {@code AbstractMultimap} implementations. 1100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return an iterator across map entries 1102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<Map.Entry<K, V>> createEntryIterator() { 1104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new EntryIterator(); 1105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Iterator across all key-value pairs. */ 1108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class EntryIterator implements Iterator<Map.Entry<K, V>> { 1109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<Map.Entry<K, Collection<V>>> keyIterator; 1110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson K key; 1111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection; 1112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<V> valueIterator; 1113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson EntryIterator() { 1115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyIterator = map.entrySet().iterator(); 1116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (keyIterator.hasNext()) { 1117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson findValueIteratorAndKey(); 1118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 1119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson valueIterator = Iterators.emptyModifiableIterator(); 1120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson void findValueIteratorAndKey() { 1124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map.Entry<K, Collection<V>> entry = keyIterator.next(); 1125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson key = entry.getKey(); 1126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection = entry.getValue(); 1127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson valueIterator = collection.iterator(); 1128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 11301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 1132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyIterator.hasNext() || valueIterator.hasNext(); 1133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 11351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Map.Entry<K, V> next() { 1137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!valueIterator.hasNext()) { 1138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson findValueIteratorAndKey(); 1139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Maps.immutableEntry(key, valueIterator.next()); 1141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 11431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 1145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson valueIterator.remove(); 1146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection.isEmpty()) { 1147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyIterator.remove(); 1148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize--; 1150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Map<K, Collection<V>> asMap; 1154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 11551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Map<K, Collection<V>> asMap() { 1157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map<K, Collection<V>> result = asMap; 1158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (result == null) ? asMap = createAsMap() : result; 1159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Map<K, Collection<V>> createAsMap() { 1162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (map instanceof SortedMap) 1163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ? new SortedAsMap((SortedMap<K, Collection<V>>) map) : new AsMap(map); 1164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class AsMap extends AbstractMap<K, Collection<V>> { 1167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Usually the same as map, but smaller for the headMap(), tailMap(), or 1169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * subMap() of a SortedAsMap. 1170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final transient Map<K, Collection<V>> submap; 1172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson AsMap(Map<K, Collection<V>> submap) { 1174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.submap = submap; 1175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson transient Set<Map.Entry<K, Collection<V>>> entrySet; 1178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Set<Map.Entry<K, Collection<V>>> entrySet() { 1180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<Map.Entry<K, Collection<V>>> result = entrySet; 11811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (result == null) ? entrySet = new AsMapEntries() : result; 1182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // The following methods are included for performance. 1185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsKey(Object key) { 1187bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return Maps.safeContainsKey(submap, key); 1188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Collection<V> get(Object key) { 1191bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor Collection<V> collection = Maps.safeGet(submap, key); 1192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection == null) { 1193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return null; 1194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 1196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson K k = (K) key; 1197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return wrapCollection(k, collection); 1198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Set<K> keySet() { 1201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return AbstractMultimap.this.keySet(); 1202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 12041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 12051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int size() { 12061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return submap.size(); 12071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Collection<V> remove(Object key) { 1210090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = submap.remove(key); 1211090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (collection == null) { 1212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return null; 1213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> output = createCollection(); 1216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson output.addAll(collection); 1217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize -= collection.size(); 1218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection.clear(); 1219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return output; 1220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 1223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this == object || submap.equals(object); 1224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 1227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return submap.hashCode(); 1228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 1231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return submap.toString(); 1232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 12341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 12351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void clear() { 12361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (submap == map) { 12371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert AbstractMultimap.this.clear(); 12381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 12391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Iterators.clear(new AsMapIterator()); 12411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 12431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 12441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert class AsMapEntries extends Maps.EntrySet<K, Collection<V>> { 12451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 12461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Map<K, Collection<V>> map() { 12471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return AsMap.this; 1248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 12501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Iterator<Map.Entry<K, Collection<V>>> iterator() { 12511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new AsMapIterator(); 1252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // The following methods are included for performance. 1255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object o) { 1257bfe2dd089341dcb4c1fb65a5b6b077ad0ebbf6dcDan Egnor return Collections2.safeContains(submap.entrySet(), o); 1258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean remove(Object o) { 1261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (!contains(o)) { 1262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 1263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map.Entry<?, ?> entry = (Map.Entry<?, ?>) o; 1265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeValuesForKey(entry.getKey()); 1266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 1267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Iterator across all keys and value collections. */ 1271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson class AsMapIterator implements Iterator<Map.Entry<K, Collection<V>>> { 1272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<Map.Entry<K, Collection<V>>> delegateIterator 1273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson = submap.entrySet().iterator(); 1274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection; 1275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 12761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 1278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return delegateIterator.hasNext(); 1279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 12811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Map.Entry<K, Collection<V>> next() { 1283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map.Entry<K, Collection<V>> entry = delegateIterator.next(); 1284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson K key = entry.getKey(); 1285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection = entry.getValue(); 1286090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Maps.immutableEntry(key, wrapCollection(key, collection)); 1287090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 12891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 1291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson delegateIterator.remove(); 1292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson totalSize -= collection.size(); 1293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson collection.clear(); 1294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class SortedAsMap extends AsMap 1299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements SortedMap<K, Collection<V>> { 1300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SortedAsMap(SortedMap<K, Collection<V>> submap) { 1301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson super(submap); 1302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SortedMap<K, Collection<V>> sortedMap() { 1305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (SortedMap<K, Collection<V>>) submap; 1306090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 13081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Comparator<? super K> comparator() { 1310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return sortedMap().comparator(); 1311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 13131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K firstKey() { 1315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return sortedMap().firstKey(); 1316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 13181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K lastKey() { 1320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return sortedMap().lastKey(); 1321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 13231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public SortedMap<K, Collection<V>> headMap(K toKey) { 1325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SortedAsMap(sortedMap().headMap(toKey)); 1326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 13281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public SortedMap<K, Collection<V>> subMap(K fromKey, K toKey) { 1330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SortedAsMap(sortedMap().subMap(fromKey, toKey)); 1331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 13331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public SortedMap<K, Collection<V>> tailMap(K fromKey) { 1335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new SortedAsMap(sortedMap().tailMap(fromKey)); 1336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SortedSet<K> sortedKeySet; 1339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // returns a SortedSet, even though returning a Set would be sufficient to 1341090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // satisfy the SortedMap.keySet() interface 1342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public SortedSet<K> keySet() { 1343090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson SortedSet<K> result = sortedKeySet; 1344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return (result == null) 1345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ? sortedKeySet = new SortedKeySet(sortedMap()) : result; 1346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1348090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1349090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Comparison and hashing 1350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1351090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 1352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (object == this) { 1353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 1354090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1355090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (object instanceof Multimap) { 1356090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multimap<?, ?> that = (Multimap<?, ?>) object; 1357090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this.map.equals(that.asMap()); 1358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 1360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the hash code for this multimap. 1364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The hash code of a multimap is defined as the hash code of the map view, 1366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * as returned by {@link Multimap#asMap}. 1367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @see Map#hashCode 1369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 1371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map.hashCode(); 1372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a string representation of the multimap, generated by calling 1376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code toString} on the map returned by {@link Multimap#asMap}. 1377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a string representation of the multimap 1379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 13801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 13811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public String toString() { 1382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return map.toString(); 1383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 2447537837011683357L; 1386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 13871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1388