LinkedListMultimap.java revision 090f9b4c879985bc747c214f82c62471e60c7742
1090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/* 2090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Copyright (C) 2007 Google Inc. 3090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 4090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Licensed under the Apache License, Version 2.0 (the "License"); 5090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * you may not use this file except in compliance with the License. 6090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * You may obtain a copy of the License at 7090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 8090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * http://www.apache.org/licenses/LICENSE-2.0 9090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 10090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Unless required by applicable law or agreed to in writing, software 11090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * distributed under the License is distributed on an "AS IS" BASIS, 12090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * See the License for the specific language governing permissions and 14090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * limitations under the License. 15090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 16090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 17090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpackage com.google.common.collect; 18090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 19090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.annotations.GwtCompatible; 20090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Objects; 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport com.google.common.base.Preconditions; 22090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkArgument; 23090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkState; 24090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.collect.Multisets.setCountImpl; 25090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 26090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.IOException; 27090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectInputStream; 28090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectOutputStream; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.Serializable; 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractCollection; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractMap; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractSequentialList; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractSet; 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static java.util.Collections.unmodifiableList; 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.HashSet; 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.List; 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.ListIterator; 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map.Entry; 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.NoSuchElementException; 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * An implementation of {@code ListMultimap} that supports deterministic 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order for both keys and values. The iteration order is preserved 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * across non-distinct key values. For example, for the following multimap 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * definition: <pre> {@code 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multimap<K, V> multimap = LinkedListMultimap.create(); 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap.put(key1, foo); 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap.put(key2, bar); 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap.put(key1, baz);}</pre> 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ... the iteration order for {@link #keys()} is {@code [key1, key2, key1]}, 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and similarly for {@link #entries()}. Unlike {@link LinkedHashMultimap}, the 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order is kept consistent between keys, entries and values. For 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * example, calling: <pre> {@code 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * map.remove(key1, foo);}</pre> 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * changes the entries iteration order to {@code [key2=bar, key1=baz]} and the 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key iteration order to {@code [key2, key1]}. The {@link #entries()} iterator 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returns mutable map entries, and {@link #replaceValues} attempts to preserve 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order as much as possible. 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The collections returned by {@link #keySet} and {@link #asMap} iterate 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * through the keys in the order they were first added to the multimap. 72090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Similarly, {@link #get}, {@link #removeAll}, and {@link #replaceValues} 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * return collections that iterate through the values in the order they were 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * added. The collections generated by {@link #entries}, {@link #keys}, and 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #values} iterate across the key-value mappings in the order they were 76090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * added to the multimap. 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Keys and values may be null. All optional multimap methods are supported, 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and all returned views are modifiable. 80090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 81090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The methods {@link #get}, {@link #keySet}, {@link #keys}, {@link #values}, 82090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #entries}, and {@link #asMap} return collections that are views of the 83090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap. If the multimap is modified while an iteration over any of those 84090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * collections is in progress, except through the iterator's own {@code remove} 85090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * operation, the results of the iteration are undefined. 86090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 87090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This class is not threadsafe when any concurrent operations update the 88090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap. Concurrent read operations will work correctly. To allow concurrent 89090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * update operations, wrap your multimap with a call to {@link 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multimaps#synchronizedListMultimap}. 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Mike Bostock 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson@GwtCompatible(serializable = true) 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonpublic final class LinkedListMultimap<K, V> 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements ListMultimap<K, V>, Serializable { 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Order is maintained using a linked list containing all key-value pairs. In 99090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * addition, a series of disjoint linked lists of "siblings", each containing 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the values for a specific key, is used to implement {@link 101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ValueForKeyIterator} in constant time. 102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final class Node<K, V> { 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final K key; 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V value; 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> next; // the next node (with any key) 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> previous; // the previous node (with any key) 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> nextSibling; // the next node with the same key 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> previousSibling; // the previous node with the same key 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node(@Nullable K key, @Nullable V value) { 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.key = key; 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.value = value; 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return key + "=" + value; 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Node<K, V> head; // the head for all keys 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Node<K, V> tail; // the tail for all keys 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Multiset<K> keyCount; // the number of values for each key 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Map<K, Node<K, V>> keyToKeyHead; // the head for a given key 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Map<K, Node<K, V>> keyToKeyTail; // the tail for a given key 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a new, empty {@code LinkedListMultimap} with the default initial 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * capacity. 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedListMultimap<K, V> create() { 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedListMultimap<K, V>(); 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs an empty {@code LinkedListMultimap} with enough capacity to hold 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the specified number of keys without rehashing. 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param expectedKeys the expected number of distinct keys 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code expectedKeys} is negative 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedListMultimap<K, V> create(int expectedKeys) { 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedListMultimap<K, V>(expectedKeys); 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs a {@code LinkedListMultimap} with the same mappings as the 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * specified {@code Multimap}. The new multimap has the same 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Multimap#entries()} iteration order as the input multimap. 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param multimap the multimap whose contents are copied to this multimap 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedListMultimap<K, V> create( 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multimap<? extends K, ? extends V> multimap) { 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedListMultimap<K, V>(multimap); 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedListMultimap() { 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount = LinkedHashMultiset.create(); 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead = Maps.newHashMap(); 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail = Maps.newHashMap(); 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedListMultimap(int expectedKeys) { 166090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount = LinkedHashMultiset.create(expectedKeys); 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead = Maps.newHashMapWithExpectedSize(expectedKeys); 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail = Maps.newHashMapWithExpectedSize(expectedKeys); 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedListMultimap(Multimap<? extends K, ? extends V> multimap) { 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this(multimap.keySet().size()); 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson putAll(multimap); 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds a new node for the specified key-value pair before the specified 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code nextSibling} element, or at the end of the list if {@code 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * nextSibling} is null. Note: if {@code nextSibling} is specified, it MUST be 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * for an node for the same {@code key}! 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Node<K, V> addNode( 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Nullable K key, @Nullable V value, @Nullable Node<K, V> nextSibling) { 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> node = new Node<K, V>(key, value); 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (head == null) { // empty list 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson head = tail = node; 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.put(key, node); 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail.put(key, node); 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (nextSibling == null) { // non-empty list, add to tail 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson tail.next = node; 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previous = tail; 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> keyTail = keyToKeyTail.get(key); 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (keyTail == null) { // first for this key 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.put(key, node); 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyTail.nextSibling = node; 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previousSibling = keyTail; 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail.put(key, node); 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson tail = node; 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { // non-empty list, insert before nextSibling 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previous = nextSibling.previous; 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previousSibling = nextSibling.previousSibling; 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.next = nextSibling; 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.nextSibling = nextSibling; 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (nextSibling.previousSibling == null) { // nextSibling was key head 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.put(key, node); 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextSibling.previousSibling.nextSibling = node; 210090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 211090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (nextSibling.previous == null) { // nextSibling was head 212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson head = node; 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextSibling.previous.next = node; 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextSibling.previous = node; 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextSibling.previousSibling = node; 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount.add(key); 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return node; 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Removes the specified node from the linked list. This method is only 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * intended to be used from the {@code Iterator} classes. See also {@link 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * LinkedListMultimap#removeAllNodes(Object)}. 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void removeNode(Node<K, V> node) { 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (node.previous != null) { 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previous.next = node.next; 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { // node was head 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson head = node.next; 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (node.next != null) { 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.next.previous = node.previous; 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { // node was tail 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson tail = node.previous; 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (node.previousSibling != null) { 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previousSibling.nextSibling = node.nextSibling; 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (node.nextSibling != null) { // node was key head 242090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.put(node.key, node.nextSibling); 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.remove(node.key); // don't leak a key-null entry 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (node.nextSibling != null) { 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.nextSibling.previousSibling = node.previousSibling; 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (node.previousSibling != null) { // node was key tail 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail.put(node.key, node.previousSibling); 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail.remove(node.key); // don't leak a key-null entry 252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount.remove(node.key); 254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Removes all nodes for the specified key. */ 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void removeAllNodes(@Nullable Object key) { 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) { 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson i.next(); 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson i.remove(); 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Helper method for verifying that an iterator element is present. */ 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static void checkElement(@Nullable Object node) { 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (node == null) { 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new NoSuchElementException(); 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** An {@code Iterator} over all nodes. */ 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class NodeIterator implements Iterator<Node<K, V>> { 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> next = head; 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> current; 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return next != null; 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 279090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Node<K, V> next() { 280090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkElement(next); 281090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = next; 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = next.next; 283090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return current; 284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 285090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 286090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(current != null); 287090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeNode(current); 288090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = null; 289090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 290090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 291090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 292090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** An {@code Iterator} over distinct keys in key head order. */ 293090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class DistinctKeyIterator implements Iterator<K> { 294090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Set<K> seenKeys = new HashSet<K>(Maps.capacity(keySet().size())); 295090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> next = head; 296090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> current; 297090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 298090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 299090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return next != null; 300090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 301090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K next() { 302090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkElement(next); 303090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = next; 304090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson seenKeys.add(current.key); 305090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson do { // skip ahead to next unseen key 306090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = next.next; 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } while ((next != null) && !seenKeys.add(next.key)); 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return current.key; 309090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(current != null); 312090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeAllNodes(current.key); 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = null; 314090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 317090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** A {@code ListIterator} over values for a specified key. */ 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class ValueForKeyIterator implements ListIterator<V> { 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Object key; 320090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int nextIndex; 321090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> next; 322090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> current; 323090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> previous; 324090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 325090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Constructs a new iterator over all values for the specified key. */ 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ValueForKeyIterator(@Nullable Object key) { 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.key = key; 328090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = keyToKeyHead.get(key); 329090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 330090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 331090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 332090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs a new iterator over all values for the specified key starting 333090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * at the specified index. This constructor is optimized so that it starts 334090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * at either the head or the tail, depending on which is closer to the 335090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * specified index. This allows adds to the tail to be done in constant 336090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * time. 337090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 338090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IndexOutOfBoundsException if index is invalid 339090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 340090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ValueForKeyIterator(@Nullable Object key, int index) { 341090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int size = keyCount.count(key); 342090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Preconditions.checkPositionIndex(index, size); 343090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (index >= (size / 2)) { 344090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous = keyToKeyTail.get(key); 345090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextIndex = size; 346090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (index++ < size) { 347090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous(); 348090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 349090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 350090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = keyToKeyHead.get(key); 351090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (index-- > 0) { 352090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next(); 353090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 354090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 355090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.key = key; 356090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = null; 357090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 358090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 359090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 360090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return next != null; 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V next() { 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkElement(next); 365090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous = current = next; 366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = next.nextSibling; 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextIndex++; 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return current.value; 369090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasPrevious() { 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return previous != null; 373090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V previous() { 376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkElement(previous); 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = current = previous; 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous = previous.previousSibling; 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextIndex--; 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return current.value; 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 383090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int nextIndex() { 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nextIndex; 385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int previousIndex() { 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nextIndex - 1; 389090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 392090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(current != null); 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (current != next) { // removing next element 394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous = current.previousSibling; 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextIndex--; 396090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 397090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = current.nextSibling; 398090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 399090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeNode(current); 400090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = null; 401090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 402090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 403090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void set(V value) { 404090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(current != null); 405090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current.value = value; 406090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 407090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 408090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 409090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void add(V value) { 410090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous = addNode((K) key, value, next); 411090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextIndex++; 412090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = null; 413090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 414090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 415090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 416090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Query Operations 417090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 418090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 419090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.size(); 420090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 421090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 422090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean isEmpty() { 423090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return head == null; 424090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 425090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 426090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsKey(@Nullable Object key) { 427090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyToKeyHead.containsKey(key); 428090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 429090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 430090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsValue(@Nullable Object value) { 431090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Iterator<Node<K, V>> i = new NodeIterator(); i.hasNext();) { 432090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (Objects.equal(i.next().value, value)) { 433090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 434090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 435090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 436090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 437090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 438090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 439090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsEntry(@Nullable Object key, @Nullable Object value) { 440090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) { 441090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (Objects.equal(i.next(), value)) { 442090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 443090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 444090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 445090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 446090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 447090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 448090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Modification Operations 449090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 450090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 451090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Stores a key-value pair in the multimap. 452090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 453090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param key key to store in the multimap 454090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param value value to store in the multimap 455090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return {@code true} always 456090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 457090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean put(@Nullable K key, @Nullable V value) { 458090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson addNode(key, value, null); 459090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 460090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 461090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 462090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean remove(@Nullable Object key, @Nullable Object value) { 463090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<V> values = new ValueForKeyIterator(key); 464090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (values.hasNext()) { 465090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (Objects.equal(values.next(), value)) { 466090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson values.remove(); 467090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 468090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 469090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 470090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 471090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 472090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 473090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Bulk Operations 474090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 475090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean putAll(@Nullable K key, Iterable<? extends V> values) { 476090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = false; 477090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (V value : values) { 478090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson changed |= put(key, value); 479090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 480090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 481090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 482090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 483090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 484090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = false; 485090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Entry<? extends K, ? extends V> entry : multimap.entries()) { 486090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson changed |= put(entry.getKey(), entry.getValue()); 487090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 488090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 489090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 490090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 491090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 492090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 493090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 494090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>If any entries for the specified {@code key} already exist in the 495090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap, their values are changed in-place without affecting the iteration 496090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order. 497090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 498090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned list is immutable and implements 499090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link java.util.RandomAccess}. 500090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 501090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public List<V> replaceValues(@Nullable K key, Iterable<? extends V> values) { 502090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson List<V> oldValues = getCopy(key); 503090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ListIterator<V> keyValues = new ValueForKeyIterator(key); 504090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<? extends V> newValues = values.iterator(); 505090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 506090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Replace existing values, if any. 507090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (keyValues.hasNext() && newValues.hasNext()) { 508090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyValues.next(); 509090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyValues.set(newValues.next()); 510090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 511090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 512090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Remove remaining old values, if any. 513090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (keyValues.hasNext()) { 514090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyValues.next(); 515090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyValues.remove(); 516090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 517090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 518090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Add remaining new values, if any. 519090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (newValues.hasNext()) { 520090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyValues.add(newValues.next()); 521090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 522090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 523090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldValues; 524090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 525090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 526090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private List<V> getCopy(@Nullable Object key) { 527090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return unmodifiableList(Lists.newArrayList(new ValueForKeyIterator(key))); 528090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 529090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 530090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 531090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 532090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 533090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned list is immutable and implements 534090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link java.util.RandomAccess}. 535090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 536090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public List<V> removeAll(@Nullable Object key) { 537090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson List<V> oldValues = getCopy(key); 538090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeAllNodes(key); 539090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldValues; 540090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 541090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 542090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void clear() { 543090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson head = null; 544090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson tail = null; 545090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount.clear(); 546090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.clear(); 547090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail.clear(); 548090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 549090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 550090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Views 551090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 552090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 553090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 554090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 555090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>If the multimap is modified while an iteration over the list is in 556090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * progress (except through the iterator's own {@code add}, {@code set} or 557090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code remove} operations) the results of the iteration are undefined. 558090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 559090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned list is not serializable and does not have random access. 560090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 561090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public List<V> get(final @Nullable K key) { 562090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new AbstractSequentialList<V>() { 563090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 564090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.count(key); 565090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 566090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ListIterator<V> listIterator(int index) { 567090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ValueForKeyIterator(key, index); 568090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 569090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> c) { 570090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.removeAll(iterator(), c); 571090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 572090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> c) { 573090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.retainAll(iterator(), c); 574090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 575090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 576090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 577090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 578090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Set<K> keySet; 579090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 580090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Set<K> keySet() { 581090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<K> result = keySet; 582090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 583090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keySet = result = new AbstractSet<K>() { 584090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 585090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.elementSet().size(); 586090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 587090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<K> iterator() { 588090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new DistinctKeyIterator(); 589090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 590090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object key) { // for performance 591090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.contains(key); 592090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 593090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 594090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 595090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 596090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 597090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 598090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Multiset<K> keys; 599090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 600090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Multiset<K> keys() { 601090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multiset<K> result = keys; 602090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 603090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keys = result = new MultisetView(); 604090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 605090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 606090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 607090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 608090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class MultisetView extends AbstractCollection<K> 609090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements Multiset<K> { 610090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 611090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 612090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.size(); 613090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 614090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 615090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<K> iterator() { 616090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<Node<K, V>> nodes = new NodeIterator(); 617090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<K>() { 618090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 619090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nodes.hasNext(); 620090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 621090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K next() { 622090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nodes.next().key; 623090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 624090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 625090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nodes.remove(); 626090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 627090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 628090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 629090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 630090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int count(@Nullable Object key) { 631090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.count(key); 632090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 633090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 634090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int add(@Nullable K key, int occurrences) { 635090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new UnsupportedOperationException(); 636090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 637090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 638090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int remove(@Nullable Object key, int occurrences) { 639090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(occurrences >= 0); 640090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldCount = count(key); 641090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<V> values = new ValueForKeyIterator(key); 642090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while ((occurrences-- > 0) && values.hasNext()) { 643090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson values.next(); 644090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson values.remove(); 645090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 646090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldCount; 647090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 648090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 649090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int setCount(K element, int count) { 650090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return setCountImpl(this, element, count); 651090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 652090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 653090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean setCount(K element, int oldCount, int newCount) { 654090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return setCountImpl(this, element, oldCount, newCount); 655090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 656090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 657090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> c) { 658090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.removeAll(iterator(), c); 659090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 660090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 661090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> c) { 662090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.retainAll(iterator(), c); 663090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 664090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 665090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Set<K> elementSet() { 666090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keySet(); 667090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 668090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 669090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Set<Entry<K>> entrySet() { 670090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // TODO: lazy init? 671090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new AbstractSet<Entry<K>>() { 672090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 673090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.elementSet().size(); 674090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 675090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 676090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<Entry<K>> iterator() { 677090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<K> keyIterator = new DistinctKeyIterator(); 678090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<Entry<K>>() { 679090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 680090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyIterator.hasNext(); 681090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 682090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Entry<K> next() { 683090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final K key = keyIterator.next(); 684090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Multisets.AbstractEntry<K>() { 685090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K getElement() { 686090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return key; 687090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 688090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int getCount() { 689090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.count(key); 690090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 691090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 692090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 693090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 694090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyIterator.remove(); 695090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 696090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 697090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 698090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 699090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 700090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 701090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 702090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.equals(object); 703090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 704090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 705090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 706090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.hashCode(); 707090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 708090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 709090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 710090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.toString(); // XXX observe order? 711090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 712090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 713090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 714090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Collection<V> valuesCollection; 715090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 716090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 717090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 718090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 719090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iterator generated by the returned collection traverses the values 720090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * in the order they were added to the multimap. 721090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 722090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Collection<V> values() { 723090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> result = valuesCollection; 724090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 725090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson valuesCollection = result = new AbstractCollection<V>() { 726090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 727090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.size(); 728090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 729090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<V> iterator() { 730090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<Node<K, V>> nodes = new NodeIterator(); 731090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<V>() { 732090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 733090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nodes.hasNext(); 734090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 735090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V next() { 736090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nodes.next().value; 737090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 738090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 739090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nodes.remove(); 740090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 741090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 742090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 743090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 744090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 745090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 746090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 747090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 748090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Collection<Entry<K, V>> entries; 749090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 750090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 751090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 752090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 753090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iterator generated by the returned collection traverses the entries 754090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * in the order they were added to the multimap. 755090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 756090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>An entry's {@link Entry#getKey} method always returns the same key, 757090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * regardless of what happens subsequently. As long as the corresponding 758090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key-value mapping is not removed from the multimap, {@link Entry#getValue} 759090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returns the value from the multimap, which may change over time, and {@link 760090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Entry#setValue} modifies that value. Removing the mapping from the 761090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap does not alter the value returned by {@code getValue()}, though a 762090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * subsequent {@code setValue()} call won't update the multimap but will lead 763090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to a revised value being returned by {@code getValue()}. 764090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 765090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Collection<Entry<K, V>> entries() { 766090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<Entry<K, V>> result = entries; 767090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 768090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entries = result = new AbstractCollection<Entry<K, V>>() { 769090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 770090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.size(); 771090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 772090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 773090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<Entry<K, V>> iterator() { 774090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<Node<K, V>> nodes = new NodeIterator(); 775090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<Entry<K, V>>() { 776090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 777090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nodes.hasNext(); 778090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 779090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 780090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Entry<K, V> next() { 781090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Node<K, V> node = nodes.next(); 782090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new AbstractMapEntry<K, V>() { 783090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public K getKey() { 784090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return node.key; 785090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 786090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public V getValue() { 787090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return node.value; 788090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 789090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public V setValue(V value) { 790090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V oldValue = node.value; 791090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.value = value; 792090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldValue; 793090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 794090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 795090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 796090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 797090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 798090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nodes.remove(); 799090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 800090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 801090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 802090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 803090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 804090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 805090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 806090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 807090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> { 808090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 809090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // TODO: Override contains() and remove() for better performance. 810090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 811090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 812090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.elementSet().size(); 813090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 814090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 815090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<Entry<K, Collection<V>>> iterator() { 816090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<K> keyIterator = new DistinctKeyIterator(); 817090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<Entry<K, Collection<V>>>() { 818090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 819090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyIterator.hasNext(); 820090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 821090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 822090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Entry<K, Collection<V>> next() { 823090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final K key = keyIterator.next(); 824090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new AbstractMapEntry<K, Collection<V>>() { 825090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public K getKey() { 826090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return key; 827090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 828090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 829090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Collection<V> getValue() { 830090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return LinkedListMultimap.this.get(key); 831090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 832090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 833090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 834090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 835090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 836090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyIterator.remove(); 837090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 838090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 839090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 840090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 841090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 842090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Map<K, Collection<V>> map; 843090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 844090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Map<K, Collection<V>> asMap() { 845090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map<K, Collection<V>> result = map; 846090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 847090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson map = result = new AbstractMap<K, Collection<V>>() { 848090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<Entry<K, Collection<V>>> entrySet; 849090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 850090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Set<Entry<K, Collection<V>>> entrySet() { 851090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<Entry<K, Collection<V>>> result = entrySet; 852090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 853090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entrySet = result = new AsMapEntries(); 854090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 855090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 856090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 857090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 858090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // The following methods are included for performance. 859090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 860090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsKey(@Nullable Object key) { 861090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return LinkedListMultimap.this.containsKey(key); 862090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 863090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 864090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 865090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Collection<V> get(@Nullable Object key) { 866090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = LinkedListMultimap.this.get((K) key); 867090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return collection.isEmpty() ? null : collection; 868090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 869090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 870090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Collection<V> remove(@Nullable Object key) { 871090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = removeAll(key); 872090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return collection.isEmpty() ? null : collection; 873090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 874090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 875090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 876090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 877090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 878090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 879090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 880090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Comparison and hashing 881090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 882090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 883090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Compares the specified object to this multimap for equality. 884090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 885090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Two {@code ListMultimap} instances are equal if, for each key, they 886090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * contain the same values in the same order. If the value orderings disagree, 887090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the multimaps will not be considered equal. 888090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 889090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object other) { 890090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (other == this) { 891090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 892090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 893090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (other instanceof Multimap) { 894090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multimap<?, ?> that = (Multimap<?, ?>) other; 895090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this.asMap().equals(that.asMap()); 896090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 897090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 898090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 899090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 900090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 901090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the hash code for this multimap. 902090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 903090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The hash code of a multimap is defined as the hash code of the map view, 904090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * as returned by {@link Multimap#asMap}. 905090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 906090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 907090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return asMap().hashCode(); 908090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 909090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 910090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 911090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a string representation of the multimap, generated by calling 912090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code toString} on the map returned by {@link Multimap#asMap}. 913090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 914090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a string representation of the multimap 915090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 916090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 917090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return asMap().toString(); 918090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 919090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 920090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 921090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @serialData the number of distinct keys, and then for each distinct key: 922090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the first key, the number of values for that key, and the key's values, 923090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * followed by successive keys and values from the entries() ordering 924090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 925090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void writeObject(ObjectOutputStream stream) throws IOException { 926090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultWriteObject(); 927090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeInt(size()); 928090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Entry<K, V> entry : entries()) { 929090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeObject(entry.getKey()); 930090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeObject(entry.getValue()); 931090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 932090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 933090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 934090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void readObject(ObjectInputStream stream) 935090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throws IOException, ClassNotFoundException { 936090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultReadObject(); 937090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount = LinkedHashMultiset.create(); 938090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead = Maps.newHashMap(); 939090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail = Maps.newHashMap(); 940090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int size = stream.readInt(); 941090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = 0; i < size; i++) { 942090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") // reading data stored by writeObject 943090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson K key = (K) stream.readObject(); 944090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") // reading data stored by writeObject 945090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V value = (V) stream.readObject(); 946090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson put(key, value); 947090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 948090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 949090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 950090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 951090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 952