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; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 21090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.base.Preconditions.checkState; 22090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport static com.google.common.collect.Multisets.setCountImpl; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static java.util.Collections.unmodifiableList; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Objects; 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Preconditions; 29090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 30090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.IOException; 31090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectInputStream; 32090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.ObjectOutputStream; 33090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.io.Serializable; 34090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractCollection; 35090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractMap; 36090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractSequentialList; 37090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.AbstractSet; 38090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Collection; 39090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Iterator; 40090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.List; 41090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.ListIterator; 42090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map; 43090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Map.Entry; 44090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.NoSuchElementException; 45090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport java.util.Set; 46090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 47090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilsonimport javax.annotation.Nullable; 48090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 49090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson/** 50090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * An implementation of {@code ListMultimap} that supports deterministic 51090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order for both keys and values. The iteration order is preserved 52090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * across non-distinct key values. For example, for the following multimap 53090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * definition: <pre> {@code 54090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 55090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multimap<K, V> multimap = LinkedListMultimap.create(); 56090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap.put(key1, foo); 57090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap.put(key2, bar); 58090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap.put(key1, baz);}</pre> 59090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 60090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ... the iteration order for {@link #keys()} is {@code [key1, key2, key1]}, 61090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and similarly for {@link #entries()}. Unlike {@link LinkedHashMultimap}, the 62090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order is kept consistent between keys, entries and values. For 63090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * example, calling: <pre> {@code 64090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 65090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * map.remove(key1, foo);}</pre> 66090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 67090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * changes the entries iteration order to {@code [key2=bar, key1=baz]} and the 68090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key iteration order to {@code [key2, key1]}. The {@link #entries()} iterator 69090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returns mutable map entries, and {@link #replaceValues} attempts to preserve 70090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * iteration order as much as possible. 71090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The collections returned by {@link #keySet()} and {@link #asMap} iterate 73090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * through the keys in the order they were first added to the multimap. 74090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Similarly, {@link #get}, {@link #removeAll}, and {@link #replaceValues} 75090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * return collections that iterate through the values in the order they were 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * added. The collections generated by {@link #entries()}, {@link #keys()}, and 77090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link #values} iterate across the key-value mappings in the order they were 78090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * added to the multimap. 79090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The {@link #values()} and {@link #entries()} methods both return a 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code List}, instead of the {@code Collection} specified by the {@link 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ListMultimap} interface. 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The methods {@link #get}, {@link #keySet()}, {@link #keys()}, 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@link #values}, {@link #entries()}, and {@link #asMap} return collections 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * that are views of the multimap. If the multimap is modified while an 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * iteration over any of those collections is in progress, except through the 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * iterator's methods, the results of the iteration are undefined. 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 90090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Keys and values may be null. All optional multimap methods are supported, 91090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * and all returned views are modifiable. 92090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 93090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>This class is not threadsafe when any concurrent operations update the 94090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap. Concurrent read operations will work correctly. To allow concurrent 95090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * update operations, wrap your multimap with a call to {@link 96090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Multimaps#synchronizedListMultimap}. 97090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 98090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @author Mike Bostock 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 2.0 (imported from Google Collections Library) 100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible(serializable = true, emulated = true) 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic class LinkedListMultimap<K, V> 103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements ListMultimap<K, V>, Serializable { 104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /* 105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Order is maintained using a linked list containing all key-value pairs. In 106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * addition, a series of disjoint linked lists of "siblings", each containing 107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the values for a specific key, is used to implement {@link 108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * ValueForKeyIterator} in constant time. 109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final class Node<K, V> { 112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final K key; 113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V value; 114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> next; // the next node (with any key) 115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> previous; // the previous node (with any key) 116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> nextSibling; // the next node with the same key 117090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> previousSibling; // the previous node with the same key 118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node(@Nullable K key, @Nullable V value) { 120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.key = key; 121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.value = value; 122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return key + "=" + value; 126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 127090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Node<K, V> head; // the head for all keys 130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Node<K, V> tail; // the tail for all keys 131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Multiset<K> keyCount; // the number of values for each key 132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Map<K, Node<K, V>> keyToKeyHead; // the head for a given key 133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Map<K, Node<K, V>> keyToKeyTail; // the tail for a given key 134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Creates a new, empty {@code LinkedListMultimap} with the default initial 137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * capacity. 138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedListMultimap<K, V> create() { 140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedListMultimap<K, V>(); 141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 144090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs an empty {@code LinkedListMultimap} with enough capacity to hold 145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the specified number of keys without rehashing. 146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 147090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param expectedKeys the expected number of distinct keys 148090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IllegalArgumentException if {@code expectedKeys} is negative 149090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 150090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedListMultimap<K, V> create(int expectedKeys) { 151090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedListMultimap<K, V>(expectedKeys); 152090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 153090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 154090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 155090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs a {@code LinkedListMultimap} with the same mappings as the 156090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * specified {@code Multimap}. The new multimap has the same 157090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link Multimap#entries()} iteration order as the input multimap. 158090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 159090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param multimap the multimap whose contents are copied to this multimap 160090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 161090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public static <K, V> LinkedListMultimap<K, V> create( 162090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multimap<? extends K, ? extends V> multimap) { 163090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new LinkedListMultimap<K, V>(multimap); 164090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 165090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert LinkedListMultimap() { 167090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount = LinkedHashMultiset.create(); 168090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead = Maps.newHashMap(); 169090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail = Maps.newHashMap(); 170090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 171090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 172090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedListMultimap(int expectedKeys) { 173090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount = LinkedHashMultiset.create(expectedKeys); 174090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead = Maps.newHashMapWithExpectedSize(expectedKeys); 175090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail = Maps.newHashMapWithExpectedSize(expectedKeys); 176090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 177090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 178090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private LinkedListMultimap(Multimap<? extends K, ? extends V> multimap) { 179090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this(multimap.keySet().size()); 180090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson putAll(multimap); 181090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 182090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 183090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 184090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Adds a new node for the specified key-value pair before the specified 185090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code nextSibling} element, or at the end of the list if {@code 186090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * nextSibling} is null. Note: if {@code nextSibling} is specified, it MUST be 187090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * for an node for the same {@code key}! 188090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 189090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private Node<K, V> addNode( 190090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Nullable K key, @Nullable V value, @Nullable Node<K, V> nextSibling) { 191090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> node = new Node<K, V>(key, value); 192090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (head == null) { // empty list 193090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson head = tail = node; 194090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.put(key, node); 195090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail.put(key, node); 196090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (nextSibling == null) { // non-empty list, add to tail 197090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson tail.next = node; 198090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previous = tail; 199090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> keyTail = keyToKeyTail.get(key); 200090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (keyTail == null) { // first for this key 201090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.put(key, node); 202090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 203090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyTail.nextSibling = node; 204090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previousSibling = keyTail; 205090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 206090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail.put(key, node); 207090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson tail = node; 208090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { // non-empty list, insert before nextSibling 209090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previous = nextSibling.previous; 210090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previousSibling = nextSibling.previousSibling; 211090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.next = nextSibling; 212090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.nextSibling = nextSibling; 213090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (nextSibling.previousSibling == null) { // nextSibling was key head 214090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.put(key, node); 215090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 216090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextSibling.previousSibling.nextSibling = node; 217090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 218090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (nextSibling.previous == null) { // nextSibling was head 219090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson head = node; 220090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 221090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextSibling.previous.next = node; 222090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 223090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextSibling.previous = node; 224090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextSibling.previousSibling = node; 225090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 226090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount.add(key); 227090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return node; 228090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 229090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 230090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 231090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Removes the specified node from the linked list. This method is only 232090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * intended to be used from the {@code Iterator} classes. See also {@link 233090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * LinkedListMultimap#removeAllNodes(Object)}. 234090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 235090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void removeNode(Node<K, V> node) { 236090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (node.previous != null) { 237090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previous.next = node.next; 238090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { // node was head 239090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson head = node.next; 240090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 241090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (node.next != null) { 242090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.next.previous = node.previous; 243090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { // node was tail 244090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson tail = node.previous; 245090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 246090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (node.previousSibling != null) { 247090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.previousSibling.nextSibling = node.nextSibling; 248090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (node.nextSibling != null) { // node was key head 249090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.put(node.key, node.nextSibling); 250090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 251090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.remove(node.key); // don't leak a key-null entry 252090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 253090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (node.nextSibling != null) { 254090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson node.nextSibling.previousSibling = node.previousSibling; 255090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else if (node.previousSibling != null) { // node was key tail 256090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail.put(node.key, node.previousSibling); 257090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 258090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail.remove(node.key); // don't leak a key-null entry 259090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 260090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount.remove(node.key); 261090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 262090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 263090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Removes all nodes for the specified key. */ 264090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void removeAllNodes(@Nullable Object key) { 265090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) { 266090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson i.next(); 267090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson i.remove(); 268090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 269090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 270090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 271090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Helper method for verifying that an iterator element is present. */ 272090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static void checkElement(@Nullable Object node) { 273090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (node == null) { 274090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new NoSuchElementException(); 275090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 276090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 277090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 278090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** An {@code Iterator} over all nodes. */ 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private class NodeIterator implements ListIterator<Node<K, V>> { 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int nextIndex; 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Node<K, V> next; 282090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> current; 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Node<K, V> previous; 284090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert NodeIterator() { 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert next = head; 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert NodeIterator(int index) { 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert int size = size(); 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Preconditions.checkPositionIndex(index, size); 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (index >= (size / 2)) { 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert previous = tail; 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert nextIndex = size; 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (index++ < size) { 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert previous(); 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert next = head; 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (index-- > 0) { 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert next(); 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert current = null; 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 306090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 307090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return next != null; 308090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 310090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Node<K, V> next() { 311090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkElement(next); 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert previous = current = next; 313090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = next.next; 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert nextIndex++; 315090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return current; 316090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 318090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 319090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(current != null); 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (current != next) { // after call to next() 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert previous = current.previous; 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert nextIndex--; 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { // after call to previous() 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert next = current.next; 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 326090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeNode(current); 327090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = null; 328090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean hasPrevious() { 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return previous != null; 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Node<K, V> previous() { 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkElement(previous); 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert next = current = previous; 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert previous = previous.previous; 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert nextIndex--; 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return current; 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int nextIndex() { 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nextIndex; 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int previousIndex() { 3471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nextIndex - 1; 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void set(Node<K, V> e) { 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void add(Node<K, V> e) { 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert void setValue(V value) { 3581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkState(current != null); 3591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert current.value = value; 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 361090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 362090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 363090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** An {@code Iterator} over distinct keys in key head order. */ 364090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class DistinctKeyIterator implements Iterator<K> { 3651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final Set<K> seenKeys = Sets.<K>newHashSetWithExpectedSize(keySet().size()); 366090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> next = head; 367090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> current; 368090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 3691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 370090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 371090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return next != null; 372090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 374090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K next() { 375090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkElement(next); 376090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = next; 377090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson seenKeys.add(current.key); 378090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson do { // skip ahead to next unseen key 379090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = next.next; 380090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } while ((next != null) && !seenKeys.add(next.key)); 381090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return current.key; 382090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 3831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 384090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 385090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(current != null); 386090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeAllNodes(current.key); 387090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = null; 388090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 389090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 390090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 391090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** A {@code ListIterator} over values for a specified key. */ 392090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class ValueForKeyIterator implements ListIterator<V> { 393090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Object key; 394090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int nextIndex; 395090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> next; 396090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> current; 397090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Node<K, V> previous; 398090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 399090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** Constructs a new iterator over all values for the specified key. */ 400090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ValueForKeyIterator(@Nullable Object key) { 401090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.key = key; 402090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = keyToKeyHead.get(key); 403090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 404090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 405090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 406090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Constructs a new iterator over all values for the specified key starting 407090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * at the specified index. This constructor is optimized so that it starts 408090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * at either the head or the tail, depending on which is closer to the 409090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * specified index. This allows adds to the tail to be done in constant 410090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * time. 411090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 412090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @throws IndexOutOfBoundsException if index is invalid 413090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 414090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public ValueForKeyIterator(@Nullable Object key, int index) { 415090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int size = keyCount.count(key); 416090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Preconditions.checkPositionIndex(index, size); 417090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (index >= (size / 2)) { 418090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous = keyToKeyTail.get(key); 419090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextIndex = size; 420090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (index++ < size) { 421090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous(); 422090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 423090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } else { 424090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = keyToKeyHead.get(key); 425090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (index-- > 0) { 426090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next(); 427090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 428090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 429090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson this.key = key; 430090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = null; 431090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 432090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 434090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 435090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return next != null; 436090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 437090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 439090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V next() { 440090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkElement(next); 441090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous = current = next; 442090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = next.nextSibling; 443090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextIndex++; 444090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return current.value; 445090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 446090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 448090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasPrevious() { 449090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return previous != null; 450090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 451090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 453090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V previous() { 454090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkElement(previous); 455090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = current = previous; 456090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous = previous.previousSibling; 457090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextIndex--; 458090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return current.value; 459090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 460090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 462090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int nextIndex() { 463090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nextIndex; 464090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 465090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 467090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int previousIndex() { 468090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nextIndex - 1; 469090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 470090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 472090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 473090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(current != null); 4741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (current != next) { // after call to next() 475090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous = current.previousSibling; 476090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextIndex--; 4771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } else { // after call to previous() 478090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson next = current.nextSibling; 479090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 480090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeNode(current); 481090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = null; 482090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 483090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 485090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void set(V value) { 486090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkState(current != null); 487090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current.value = value; 488090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 489090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 4901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 491090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 492090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void add(V value) { 493090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson previous = addNode((K) key, value, next); 494090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nextIndex++; 495090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson current = null; 496090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 497090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 498090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 499090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Query Operations 500090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 502090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int size() { 503090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.size(); 504090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 505090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 507090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean isEmpty() { 508090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return head == null; 509090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 510090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 512090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsKey(@Nullable Object key) { 513090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyToKeyHead.containsKey(key); 514090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 515090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 517090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsValue(@Nullable Object value) { 518090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Iterator<Node<K, V>> i = new NodeIterator(); i.hasNext();) { 519090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (Objects.equal(i.next().value, value)) { 520090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 521090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 522090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 523090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 524090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 525090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 527090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean containsEntry(@Nullable Object key, @Nullable Object value) { 528090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) { 529090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (Objects.equal(i.next(), value)) { 530090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 531090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 532090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 533090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 534090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 535090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 536090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Modification Operations 537090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 538090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 539090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Stores a key-value pair in the multimap. 540090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 541090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param key key to store in the multimap 542090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @param value value to store in the multimap 543090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return {@code true} always 544090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 5451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 546090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean put(@Nullable K key, @Nullable V value) { 547090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson addNode(key, value, null); 548090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 549090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 550090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 552090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean remove(@Nullable Object key, @Nullable Object value) { 553090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<V> values = new ValueForKeyIterator(key); 554090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (values.hasNext()) { 555090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (Objects.equal(values.next(), value)) { 556090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson values.remove(); 557090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 558090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 559090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 560090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 561090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 562090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 563090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Bulk Operations 564090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 566090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean putAll(@Nullable K key, Iterable<? extends V> values) { 567090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = false; 568090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (V value : values) { 569090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson changed |= put(key, value); 570090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 571090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 572090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 573090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 5741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 575090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean putAll(Multimap<? extends K, ? extends V> multimap) { 576090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson boolean changed = false; 577090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Entry<? extends K, ? extends V> entry : multimap.entries()) { 578090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson changed |= put(entry.getKey(), entry.getValue()); 579090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 580090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return changed; 581090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 582090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 583090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 584090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 585090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 586090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>If any entries for the specified {@code key} already exist in the 587090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap, their values are changed in-place without affecting the iteration 588090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * order. 589090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 590090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned list is immutable and implements 591090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link java.util.RandomAccess}. 592090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 5931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 594090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public List<V> replaceValues(@Nullable K key, Iterable<? extends V> values) { 595090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson List<V> oldValues = getCopy(key); 596090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson ListIterator<V> keyValues = new ValueForKeyIterator(key); 597090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<? extends V> newValues = values.iterator(); 598090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 599090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Replace existing values, if any. 600090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (keyValues.hasNext() && newValues.hasNext()) { 601090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyValues.next(); 602090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyValues.set(newValues.next()); 603090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 604090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 605090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Remove remaining old values, if any. 606090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (keyValues.hasNext()) { 607090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyValues.next(); 608090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyValues.remove(); 609090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 610090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 611090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Add remaining new values, if any. 612090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while (newValues.hasNext()) { 613090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyValues.add(newValues.next()); 614090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 615090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 616090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldValues; 617090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 618090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 619090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private List<V> getCopy(@Nullable Object key) { 620090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return unmodifiableList(Lists.newArrayList(new ValueForKeyIterator(key))); 621090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 622090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 623090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 624090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 625090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 626090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned list is immutable and implements 627090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@link java.util.RandomAccess}. 628090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 630090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public List<V> removeAll(@Nullable Object key) { 631090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson List<V> oldValues = getCopy(key); 632090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson removeAllNodes(key); 633090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldValues; 634090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 635090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 637090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void clear() { 638090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson head = null; 639090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson tail = null; 640090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount.clear(); 641090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead.clear(); 642090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail.clear(); 643090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 644090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 645090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Views 646090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 647090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 648090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 649090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 650090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>If the multimap is modified while an iteration over the list is in 651090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * progress (except through the iterator's own {@code add}, {@code set} or 652090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code remove} operations) the results of the iteration are undefined. 653090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 654090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The returned list is not serializable and does not have random access. 655090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 6561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 657090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public List<V> get(final @Nullable K key) { 658090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new AbstractSequentialList<V>() { 659090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 660090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.count(key); 661090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 662090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public ListIterator<V> listIterator(int index) { 663090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new ValueForKeyIterator(key, index); 664090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 665090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> c) { 666090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.removeAll(iterator(), c); 667090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 668090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> c) { 669090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.retainAll(iterator(), c); 670090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 671090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 672090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 673090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 674090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Set<K> keySet; 675090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 6761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 677090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Set<K> keySet() { 678090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<K> result = keySet; 679090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 680090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keySet = result = new AbstractSet<K>() { 681090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 682090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.elementSet().size(); 683090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 684090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<K> iterator() { 685090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new DistinctKeyIterator(); 686090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 687090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean contains(Object key) { // for performance 688090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.contains(key); 689090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 6901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public boolean removeAll(Collection<?> c) { 6911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(c); // eager for GWT 6921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return super.removeAll(c); 6931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 694090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 695090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 696090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 697090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 698090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 699090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Multiset<K> keys; 700090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 702090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Multiset<K> keys() { 703090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multiset<K> result = keys; 704090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 705090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keys = result = new MultisetView(); 706090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 707090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 708090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 709090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 710090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class MultisetView extends AbstractCollection<K> 711090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson implements Multiset<K> { 712090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 713090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 714090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.size(); 715090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 716090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 717090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<K> iterator() { 718090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<Node<K, V>> nodes = new NodeIterator(); 719090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<K>() { 7201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 721090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 722090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nodes.hasNext(); 723090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 7241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 725090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K next() { 726090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nodes.next().key; 727090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 7281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 729090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 730090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nodes.remove(); 731090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 732090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 733090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 734090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 736090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int count(@Nullable Object key) { 737090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.count(key); 738090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 739090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 741090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int add(@Nullable K key, int occurrences) { 742090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throw new UnsupportedOperationException(); 743090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 744090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 746090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int remove(@Nullable Object key, int occurrences) { 747090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson checkArgument(occurrences >= 0); 748090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int oldCount = count(key); 749090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Iterator<V> values = new ValueForKeyIterator(key); 750090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson while ((occurrences-- > 0) && values.hasNext()) { 751090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson values.next(); 752090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson values.remove(); 753090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 754090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return oldCount; 755090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 756090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 758090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int setCount(K element, int count) { 759090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return setCountImpl(this, element, count); 760090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 761090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 763090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean setCount(K element, int oldCount, int newCount) { 764090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return setCountImpl(this, element, oldCount, newCount); 765090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 766090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 767090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean removeAll(Collection<?> c) { 768090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.removeAll(iterator(), c); 769090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 770090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 771090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean retainAll(Collection<?> c) { 772090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return Iterators.retainAll(iterator(), c); 773090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 774090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 776090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Set<K> elementSet() { 777090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keySet(); 778090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 779090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 7801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 781090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Set<Entry<K>> entrySet() { 7821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(jlevy): lazy init? 783090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new AbstractSet<Entry<K>>() { 784090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 785090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.elementSet().size(); 786090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 787090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 788090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<Entry<K>> iterator() { 789090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<K> keyIterator = new DistinctKeyIterator(); 790090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<Entry<K>>() { 7911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 792090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 793090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyIterator.hasNext(); 794090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 7951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 796090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Entry<K> next() { 797090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final K key = keyIterator.next(); 798090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Multisets.AbstractEntry<K>() { 7991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 800090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public K getElement() { 801090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return key; 802090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 8031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 804090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public int getCount() { 805090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.count(key); 806090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 807090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 808090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 8091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 810090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 811090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyIterator.remove(); 812090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 813090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 814090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 815090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 816090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 817090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 818090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object object) { 819090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.equals(object); 820090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 821090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 822090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 823090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.hashCode(); 824090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 825090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 826090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 827090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.toString(); // XXX observe order? 828090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 829090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 830090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private transient List<V> valuesList; 832090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 833090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 834090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 835090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 836090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iterator generated by the returned collection traverses the values 8371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in the order they were added to the multimap. Because the values may have 8381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * duplicates and follow the insertion ordering, this method returns a {@link 8391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * List}, instead of the {@link Collection} specified in the {@link 8401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ListMultimap} interface. 841090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 8421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public List<V> values() { 8441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<V> result = valuesList; 845090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 8461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert valuesList = result = new AbstractSequentialList<V>() { 847090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 848090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.size(); 849090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 8501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public ListIterator<V> listIterator(int index) { 8521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final NodeIterator nodes = new NodeIterator(index); 8531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ListIterator<V>() { 8541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 855090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 856090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nodes.hasNext(); 857090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 8581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 859090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public V next() { 860090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nodes.next().value; 861090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 8621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean hasPrevious() { 8641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nodes.hasPrevious(); 8651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public V previous() { 8681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nodes.previous().value; 8691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int nextIndex() { 8721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nodes.nextIndex(); 8731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int previousIndex() { 8761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nodes.previousIndex(); 8771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 879090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 880090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nodes.remove(); 881090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 8821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void set(V e) { 8841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert nodes.setValue(e); 8851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 8861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 8871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void add(V e) { 8881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 8891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 890090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 891090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 892090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 893090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 894090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 895090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 896090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 8971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static <K, V> Entry<K, V> createEntry(final Node<K, V> node) { 8981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new AbstractMapEntry<K, V>() { 8991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public K getKey() { 9001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return node.key; 9011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public V getValue() { 9031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return node.value; 9041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public V setValue(V value) { 9061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert V oldValue = node.value; 9071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert node.value = value; 9081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return oldValue; 9091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 9111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private transient List<Entry<K, V>> entries; 914090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 915090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 916090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@inheritDoc} 917090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 918090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The iterator generated by the returned collection traverses the entries 9191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * in the order they were added to the multimap. Because the entries may have 9201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * duplicates and follow the insertion ordering, this method returns a {@link 9211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * List}, instead of the {@link Collection} specified in the {@link 9221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ListMultimap} interface. 923090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 924090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>An entry's {@link Entry#getKey} method always returns the same key, 925090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * regardless of what happens subsequently. As long as the corresponding 926090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * key-value mapping is not removed from the multimap, {@link Entry#getValue} 927090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * returns the value from the multimap, which may change over time, and {@link 928090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Entry#setValue} modifies that value. Removing the mapping from the 929090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * multimap does not alter the value returned by {@code getValue()}, though a 930090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * subsequent {@code setValue()} call won't update the multimap but will lead 931090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * to a revised value being returned by {@code getValue()}. 932090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 9331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 9341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public List<Entry<K, V>> entries() { 9351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert List<Entry<K, V>> result = entries; 936090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 9371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert entries = result = new AbstractSequentialList<Entry<K, V>>() { 938090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 939090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.size(); 940090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 941090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public ListIterator<Entry<K, V>> listIterator(int index) { 9431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final ListIterator<Node<K, V>> nodes = new NodeIterator(index); 9441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new ListIterator<Entry<K, V>>() { 9451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 946090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 947090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return nodes.hasNext(); 948090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 949090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 951090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Entry<K, V> next() { 9521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return createEntry(nodes.next()); 953090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 954090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 9551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 956090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 957090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson nodes.remove(); 958090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 9591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 9611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean hasPrevious() { 9621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nodes.hasPrevious(); 9631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 9661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public Map.Entry<K, V> previous() { 9671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return createEntry(nodes.previous()); 9681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 9711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int nextIndex() { 9721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nodes.nextIndex(); 9731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 9761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public int previousIndex() { 9771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return nodes.previousIndex(); 9781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 9811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void set(Map.Entry<K, V> e) { 9821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 9831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 9841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 9851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 9861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public void add(Map.Entry<K, V> e) { 9871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert throw new UnsupportedOperationException(); 9881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 989090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 990090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 991090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 992090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 993090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 994090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 995090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 996090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> { 997090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int size() { 998090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyCount.elementSet().size(); 999090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1000090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1001090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Iterator<Entry<K, Collection<V>>> iterator() { 1002090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final Iterator<K> keyIterator = new DistinctKeyIterator(); 1003090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new Iterator<Entry<K, Collection<V>>>() { 10041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1005090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public boolean hasNext() { 1006090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return keyIterator.hasNext(); 1007090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1008090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 10091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1010090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Entry<K, Collection<V>> next() { 1011090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson final K key = keyIterator.next(); 1012090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return new AbstractMapEntry<K, Collection<V>>() { 1013090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public K getKey() { 1014090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return key; 1015090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1016090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1017090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Collection<V> getValue() { 1018090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return LinkedListMultimap.this.get(key); 1019090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1020090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 1021090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1022090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 10231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1024090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public void remove() { 1025090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyIterator.remove(); 1026090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1027090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 1028090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 10291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 10301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO(jlevy): Override contains() and remove() for better performance. 1031090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1032090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1033090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private transient Map<K, Collection<V>> map; 1034090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 10351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 1036090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson public Map<K, Collection<V>> asMap() { 1037090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Map<K, Collection<V>> result = map; 1038090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 1039090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson map = result = new AbstractMap<K, Collection<V>>() { 1040090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<Entry<K, Collection<V>>> entrySet; 1041090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1042090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Set<Entry<K, Collection<V>>> entrySet() { 1043090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Set<Entry<K, Collection<V>>> result = entrySet; 1044090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (result == null) { 1045090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson entrySet = result = new AsMapEntries(); 1046090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1047090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 1048090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1049090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1050090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // The following methods are included for performance. 1051090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1052090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean containsKey(@Nullable Object key) { 1053090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return LinkedListMultimap.this.containsKey(key); 1054090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1055090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1056090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") 1057090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Collection<V> get(@Nullable Object key) { 1058090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = LinkedListMultimap.this.get((K) key); 1059090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return collection.isEmpty() ? null : collection; 1060090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1061090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1062090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public Collection<V> remove(@Nullable Object key) { 1063090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Collection<V> collection = removeAll(key); 1064090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return collection.isEmpty() ? null : collection; 1065090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1066090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson }; 1067090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1068090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1069090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return result; 1070090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1071090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1072090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson // Comparison and hashing 1073090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1074090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1075090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Compares the specified object to this multimap for equality. 1076090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1077090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>Two {@code ListMultimap} instances are equal if, for each key, they 1078090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * contain the same values in the same order. If the value orderings disagree, 1079090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the multimaps will not be considered equal. 1080090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1081090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public boolean equals(@Nullable Object other) { 1082090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (other == this) { 1083090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return true; 1084090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1085090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson if (other instanceof Multimap) { 1086090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson Multimap<?, ?> that = (Multimap<?, ?>) other; 1087090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return this.asMap().equals(that.asMap()); 1088090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1089090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return false; 1090090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1091090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1092090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1093090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns the hash code for this multimap. 1094090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1095090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * <p>The hash code of a multimap is defined as the hash code of the map view, 1096090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * as returned by {@link Multimap#asMap}. 1097090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1098090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public int hashCode() { 1099090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return asMap().hashCode(); 1100090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1101090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1102090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1103090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * Returns a string representation of the multimap, generated by calling 1104090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * {@code toString} on the map returned by {@link Multimap#asMap}. 1105090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * 1106090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @return a string representation of the multimap 1107090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 1108090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @Override public String toString() { 1109090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson return asMap().toString(); 1110090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1111090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 1112090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson /** 1113090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * @serialData the number of distinct keys, and then for each distinct key: 1114090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * the first key, the number of values for that key, and the key's values, 1115090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson * followed by successive keys and values from the entries() ordering 1116090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson */ 11171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectOutputStream") 1118090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void writeObject(ObjectOutputStream stream) throws IOException { 1119090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultWriteObject(); 1120090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeInt(size()); 1121090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (Entry<K, V> entry : entries()) { 1122090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeObject(entry.getKey()); 1123090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.writeObject(entry.getValue()); 1124090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1125090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1126090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 11271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java.io.ObjectInputStream") 1128090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private void readObject(ObjectInputStream stream) 1129090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson throws IOException, ClassNotFoundException { 1130090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson stream.defaultReadObject(); 1131090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyCount = LinkedHashMultiset.create(); 1132090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyHead = Maps.newHashMap(); 1133090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson keyToKeyTail = Maps.newHashMap(); 1134090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson int size = stream.readInt(); 1135090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson for (int i = 0; i < size; i++) { 1136090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") // reading data stored by writeObject 1137090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson K key = (K) stream.readObject(); 1138090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson @SuppressWarnings("unchecked") // reading data stored by writeObject 1139090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson V value = (V) stream.readObject(); 1140090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson put(key, value); 1141090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1142090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson } 1143090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson 11441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("java serialization not supported") 1145090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson private static final long serialVersionUID = 0; 1146090f9b4c879985bc747c214f82c62471e60c7742Jesse Wilson} 1147