/* * Copyright (C) 2007 The Guava Authors * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ package com.google.common.collect; import static com.google.common.base.Preconditions.checkArgument; import static com.google.common.base.Preconditions.checkNotNull; import static com.google.common.base.Preconditions.checkState; import static com.google.common.collect.Multisets.setCountImpl; import static java.util.Collections.unmodifiableList; import com.google.common.annotations.GwtCompatible; import com.google.common.annotations.GwtIncompatible; import com.google.common.base.Objects; import com.google.common.base.Preconditions; import java.io.IOException; import java.io.ObjectInputStream; import java.io.ObjectOutputStream; import java.io.Serializable; import java.util.AbstractCollection; import java.util.AbstractMap; import java.util.AbstractSequentialList; import java.util.AbstractSet; import java.util.Collection; import java.util.Iterator; import java.util.List; import java.util.ListIterator; import java.util.Map; import java.util.Map.Entry; import java.util.NoSuchElementException; import java.util.Set; import javax.annotation.Nullable; /** * An implementation of {@code ListMultimap} that supports deterministic * iteration order for both keys and values. The iteration order is preserved * across non-distinct key values. For example, for the following multimap * definition:
   {@code
 *
 *   Multimap multimap = LinkedListMultimap.create();
 *   multimap.put(key1, foo);
 *   multimap.put(key2, bar);
 *   multimap.put(key1, baz);}
* * ... the iteration order for {@link #keys()} is {@code [key1, key2, key1]}, * and similarly for {@link #entries()}. Unlike {@link LinkedHashMultimap}, the * iteration order is kept consistent between keys, entries and values. For * example, calling:
   {@code
 *
 *   map.remove(key1, foo);}
* * changes the entries iteration order to {@code [key2=bar, key1=baz]} and the * key iteration order to {@code [key2, key1]}. The {@link #entries()} iterator * returns mutable map entries, and {@link #replaceValues} attempts to preserve * iteration order as much as possible. * *

The collections returned by {@link #keySet()} and {@link #asMap} iterate * through the keys in the order they were first added to the multimap. * Similarly, {@link #get}, {@link #removeAll}, and {@link #replaceValues} * return collections that iterate through the values in the order they were * added. The collections generated by {@link #entries()}, {@link #keys()}, and * {@link #values} iterate across the key-value mappings in the order they were * added to the multimap. * *

The {@link #values()} and {@link #entries()} methods both return a * {@code List}, instead of the {@code Collection} specified by the {@link * ListMultimap} interface. * *

The methods {@link #get}, {@link #keySet()}, {@link #keys()}, * {@link #values}, {@link #entries()}, and {@link #asMap} return collections * that are views of the multimap. If the multimap is modified while an * iteration over any of those collections is in progress, except through the * iterator's methods, the results of the iteration are undefined. * *

Keys and values may be null. All optional multimap methods are supported, * and all returned views are modifiable. * *

This class is not threadsafe when any concurrent operations update the * multimap. Concurrent read operations will work correctly. To allow concurrent * update operations, wrap your multimap with a call to {@link * Multimaps#synchronizedListMultimap}. * * @author Mike Bostock * @since 2.0 (imported from Google Collections Library) */ @GwtCompatible(serializable = true, emulated = true) public class LinkedListMultimap implements ListMultimap, Serializable { /* * Order is maintained using a linked list containing all key-value pairs. In * addition, a series of disjoint linked lists of "siblings", each containing * the values for a specific key, is used to implement {@link * ValueForKeyIterator} in constant time. */ private static final class Node { final K key; V value; Node next; // the next node (with any key) Node previous; // the previous node (with any key) Node nextSibling; // the next node with the same key Node previousSibling; // the previous node with the same key Node(@Nullable K key, @Nullable V value) { this.key = key; this.value = value; } @Override public String toString() { return key + "=" + value; } } private transient Node head; // the head for all keys private transient Node tail; // the tail for all keys private transient Multiset keyCount; // the number of values for each key private transient Map> keyToKeyHead; // the head for a given key private transient Map> keyToKeyTail; // the tail for a given key /** * Creates a new, empty {@code LinkedListMultimap} with the default initial * capacity. */ public static LinkedListMultimap create() { return new LinkedListMultimap(); } /** * Constructs an empty {@code LinkedListMultimap} with enough capacity to hold * the specified number of keys without rehashing. * * @param expectedKeys the expected number of distinct keys * @throws IllegalArgumentException if {@code expectedKeys} is negative */ public static LinkedListMultimap create(int expectedKeys) { return new LinkedListMultimap(expectedKeys); } /** * Constructs a {@code LinkedListMultimap} with the same mappings as the * specified {@code Multimap}. The new multimap has the same * {@link Multimap#entries()} iteration order as the input multimap. * * @param multimap the multimap whose contents are copied to this multimap */ public static LinkedListMultimap create( Multimap multimap) { return new LinkedListMultimap(multimap); } LinkedListMultimap() { keyCount = LinkedHashMultiset.create(); keyToKeyHead = Maps.newHashMap(); keyToKeyTail = Maps.newHashMap(); } private LinkedListMultimap(int expectedKeys) { keyCount = LinkedHashMultiset.create(expectedKeys); keyToKeyHead = Maps.newHashMapWithExpectedSize(expectedKeys); keyToKeyTail = Maps.newHashMapWithExpectedSize(expectedKeys); } private LinkedListMultimap(Multimap multimap) { this(multimap.keySet().size()); putAll(multimap); } /** * Adds a new node for the specified key-value pair before the specified * {@code nextSibling} element, or at the end of the list if {@code * nextSibling} is null. Note: if {@code nextSibling} is specified, it MUST be * for an node for the same {@code key}! */ private Node addNode( @Nullable K key, @Nullable V value, @Nullable Node nextSibling) { Node node = new Node(key, value); if (head == null) { // empty list head = tail = node; keyToKeyHead.put(key, node); keyToKeyTail.put(key, node); } else if (nextSibling == null) { // non-empty list, add to tail tail.next = node; node.previous = tail; Node keyTail = keyToKeyTail.get(key); if (keyTail == null) { // first for this key keyToKeyHead.put(key, node); } else { keyTail.nextSibling = node; node.previousSibling = keyTail; } keyToKeyTail.put(key, node); tail = node; } else { // non-empty list, insert before nextSibling node.previous = nextSibling.previous; node.previousSibling = nextSibling.previousSibling; node.next = nextSibling; node.nextSibling = nextSibling; if (nextSibling.previousSibling == null) { // nextSibling was key head keyToKeyHead.put(key, node); } else { nextSibling.previousSibling.nextSibling = node; } if (nextSibling.previous == null) { // nextSibling was head head = node; } else { nextSibling.previous.next = node; } nextSibling.previous = node; nextSibling.previousSibling = node; } keyCount.add(key); return node; } /** * Removes the specified node from the linked list. This method is only * intended to be used from the {@code Iterator} classes. See also {@link * LinkedListMultimap#removeAllNodes(Object)}. */ private void removeNode(Node node) { if (node.previous != null) { node.previous.next = node.next; } else { // node was head head = node.next; } if (node.next != null) { node.next.previous = node.previous; } else { // node was tail tail = node.previous; } if (node.previousSibling != null) { node.previousSibling.nextSibling = node.nextSibling; } else if (node.nextSibling != null) { // node was key head keyToKeyHead.put(node.key, node.nextSibling); } else { keyToKeyHead.remove(node.key); // don't leak a key-null entry } if (node.nextSibling != null) { node.nextSibling.previousSibling = node.previousSibling; } else if (node.previousSibling != null) { // node was key tail keyToKeyTail.put(node.key, node.previousSibling); } else { keyToKeyTail.remove(node.key); // don't leak a key-null entry } keyCount.remove(node.key); } /** Removes all nodes for the specified key. */ private void removeAllNodes(@Nullable Object key) { for (Iterator i = new ValueForKeyIterator(key); i.hasNext();) { i.next(); i.remove(); } } /** Helper method for verifying that an iterator element is present. */ private static void checkElement(@Nullable Object node) { if (node == null) { throw new NoSuchElementException(); } } /** An {@code Iterator} over all nodes. */ private class NodeIterator implements ListIterator> { int nextIndex; Node next; Node current; Node previous; NodeIterator() { next = head; } NodeIterator(int index) { int size = size(); Preconditions.checkPositionIndex(index, size); if (index >= (size / 2)) { previous = tail; nextIndex = size; while (index++ < size) { previous(); } } else { next = head; while (index-- > 0) { next(); } } current = null; } @Override public boolean hasNext() { return next != null; } @Override public Node next() { checkElement(next); previous = current = next; next = next.next; nextIndex++; return current; } @Override public void remove() { checkState(current != null); if (current != next) { // after call to next() previous = current.previous; nextIndex--; } else { // after call to previous() next = current.next; } removeNode(current); current = null; } @Override public boolean hasPrevious() { return previous != null; } @Override public Node previous() { checkElement(previous); next = current = previous; previous = previous.previous; nextIndex--; return current; } @Override public int nextIndex() { return nextIndex; } @Override public int previousIndex() { return nextIndex - 1; } @Override public void set(Node e) { throw new UnsupportedOperationException(); } @Override public void add(Node e) { throw new UnsupportedOperationException(); } void setValue(V value) { checkState(current != null); current.value = value; } } /** An {@code Iterator} over distinct keys in key head order. */ private class DistinctKeyIterator implements Iterator { final Set seenKeys = Sets.newHashSetWithExpectedSize(keySet().size()); Node next = head; Node current; @Override public boolean hasNext() { return next != null; } @Override public K next() { checkElement(next); current = next; seenKeys.add(current.key); do { // skip ahead to next unseen key next = next.next; } while ((next != null) && !seenKeys.add(next.key)); return current.key; } @Override public void remove() { checkState(current != null); removeAllNodes(current.key); current = null; } } /** A {@code ListIterator} over values for a specified key. */ private class ValueForKeyIterator implements ListIterator { final Object key; int nextIndex; Node next; Node current; Node previous; /** Constructs a new iterator over all values for the specified key. */ ValueForKeyIterator(@Nullable Object key) { this.key = key; next = keyToKeyHead.get(key); } /** * Constructs a new iterator over all values for the specified key starting * at the specified index. This constructor is optimized so that it starts * at either the head or the tail, depending on which is closer to the * specified index. This allows adds to the tail to be done in constant * time. * * @throws IndexOutOfBoundsException if index is invalid */ public ValueForKeyIterator(@Nullable Object key, int index) { int size = keyCount.count(key); Preconditions.checkPositionIndex(index, size); if (index >= (size / 2)) { previous = keyToKeyTail.get(key); nextIndex = size; while (index++ < size) { previous(); } } else { next = keyToKeyHead.get(key); while (index-- > 0) { next(); } } this.key = key; current = null; } @Override public boolean hasNext() { return next != null; } @Override public V next() { checkElement(next); previous = current = next; next = next.nextSibling; nextIndex++; return current.value; } @Override public boolean hasPrevious() { return previous != null; } @Override public V previous() { checkElement(previous); next = current = previous; previous = previous.previousSibling; nextIndex--; return current.value; } @Override public int nextIndex() { return nextIndex; } @Override public int previousIndex() { return nextIndex - 1; } @Override public void remove() { checkState(current != null); if (current != next) { // after call to next() previous = current.previousSibling; nextIndex--; } else { // after call to previous() next = current.nextSibling; } removeNode(current); current = null; } @Override public void set(V value) { checkState(current != null); current.value = value; } @Override @SuppressWarnings("unchecked") public void add(V value) { previous = addNode((K) key, value, next); nextIndex++; current = null; } } // Query Operations @Override public int size() { return keyCount.size(); } @Override public boolean isEmpty() { return head == null; } @Override public boolean containsKey(@Nullable Object key) { return keyToKeyHead.containsKey(key); } @Override public boolean containsValue(@Nullable Object value) { for (Iterator> i = new NodeIterator(); i.hasNext();) { if (Objects.equal(i.next().value, value)) { return true; } } return false; } @Override public boolean containsEntry(@Nullable Object key, @Nullable Object value) { for (Iterator i = new ValueForKeyIterator(key); i.hasNext();) { if (Objects.equal(i.next(), value)) { return true; } } return false; } // Modification Operations /** * Stores a key-value pair in the multimap. * * @param key key to store in the multimap * @param value value to store in the multimap * @return {@code true} always */ @Override public boolean put(@Nullable K key, @Nullable V value) { addNode(key, value, null); return true; } @Override public boolean remove(@Nullable Object key, @Nullable Object value) { Iterator values = new ValueForKeyIterator(key); while (values.hasNext()) { if (Objects.equal(values.next(), value)) { values.remove(); return true; } } return false; } // Bulk Operations @Override public boolean putAll(@Nullable K key, Iterable values) { boolean changed = false; for (V value : values) { changed |= put(key, value); } return changed; } @Override public boolean putAll(Multimap multimap) { boolean changed = false; for (Entry entry : multimap.entries()) { changed |= put(entry.getKey(), entry.getValue()); } return changed; } /** * {@inheritDoc} * *

If any entries for the specified {@code key} already exist in the * multimap, their values are changed in-place without affecting the iteration * order. * *

The returned list is immutable and implements * {@link java.util.RandomAccess}. */ @Override public List replaceValues(@Nullable K key, Iterable values) { List oldValues = getCopy(key); ListIterator keyValues = new ValueForKeyIterator(key); Iterator newValues = values.iterator(); // Replace existing values, if any. while (keyValues.hasNext() && newValues.hasNext()) { keyValues.next(); keyValues.set(newValues.next()); } // Remove remaining old values, if any. while (keyValues.hasNext()) { keyValues.next(); keyValues.remove(); } // Add remaining new values, if any. while (newValues.hasNext()) { keyValues.add(newValues.next()); } return oldValues; } private List getCopy(@Nullable Object key) { return unmodifiableList(Lists.newArrayList(new ValueForKeyIterator(key))); } /** * {@inheritDoc} * *

The returned list is immutable and implements * {@link java.util.RandomAccess}. */ @Override public List removeAll(@Nullable Object key) { List oldValues = getCopy(key); removeAllNodes(key); return oldValues; } @Override public void clear() { head = null; tail = null; keyCount.clear(); keyToKeyHead.clear(); keyToKeyTail.clear(); } // Views /** * {@inheritDoc} * *

If the multimap is modified while an iteration over the list is in * progress (except through the iterator's own {@code add}, {@code set} or * {@code remove} operations) the results of the iteration are undefined. * *

The returned list is not serializable and does not have random access. */ @Override public List get(final @Nullable K key) { return new AbstractSequentialList() { @Override public int size() { return keyCount.count(key); } @Override public ListIterator listIterator(int index) { return new ValueForKeyIterator(key, index); } @Override public boolean removeAll(Collection c) { return Iterators.removeAll(iterator(), c); } @Override public boolean retainAll(Collection c) { return Iterators.retainAll(iterator(), c); } }; } private transient Set keySet; @Override public Set keySet() { Set result = keySet; if (result == null) { keySet = result = new AbstractSet() { @Override public int size() { return keyCount.elementSet().size(); } @Override public Iterator iterator() { return new DistinctKeyIterator(); } @Override public boolean contains(Object key) { // for performance return keyCount.contains(key); } @Override public boolean removeAll(Collection c) { checkNotNull(c); // eager for GWT return super.removeAll(c); } }; } return result; } private transient Multiset keys; @Override public Multiset keys() { Multiset result = keys; if (result == null) { keys = result = new MultisetView(); } return result; } private class MultisetView extends AbstractCollection implements Multiset { @Override public int size() { return keyCount.size(); } @Override public Iterator iterator() { final Iterator> nodes = new NodeIterator(); return new Iterator() { @Override public boolean hasNext() { return nodes.hasNext(); } @Override public K next() { return nodes.next().key; } @Override public void remove() { nodes.remove(); } }; } @Override public int count(@Nullable Object key) { return keyCount.count(key); } @Override public int add(@Nullable K key, int occurrences) { throw new UnsupportedOperationException(); } @Override public int remove(@Nullable Object key, int occurrences) { checkArgument(occurrences >= 0); int oldCount = count(key); Iterator values = new ValueForKeyIterator(key); while ((occurrences-- > 0) && values.hasNext()) { values.next(); values.remove(); } return oldCount; } @Override public int setCount(K element, int count) { return setCountImpl(this, element, count); } @Override public boolean setCount(K element, int oldCount, int newCount) { return setCountImpl(this, element, oldCount, newCount); } @Override public boolean removeAll(Collection c) { return Iterators.removeAll(iterator(), c); } @Override public boolean retainAll(Collection c) { return Iterators.retainAll(iterator(), c); } @Override public Set elementSet() { return keySet(); } @Override public Set> entrySet() { // TODO(jlevy): lazy init? return new AbstractSet>() { @Override public int size() { return keyCount.elementSet().size(); } @Override public Iterator> iterator() { final Iterator keyIterator = new DistinctKeyIterator(); return new Iterator>() { @Override public boolean hasNext() { return keyIterator.hasNext(); } @Override public Entry next() { final K key = keyIterator.next(); return new Multisets.AbstractEntry() { @Override public K getElement() { return key; } @Override public int getCount() { return keyCount.count(key); } }; } @Override public void remove() { keyIterator.remove(); } }; } }; } @Override public boolean equals(@Nullable Object object) { return keyCount.equals(object); } @Override public int hashCode() { return keyCount.hashCode(); } @Override public String toString() { return keyCount.toString(); // XXX observe order? } } private transient List valuesList; /** * {@inheritDoc} * *

The iterator generated by the returned collection traverses the values * in the order they were added to the multimap. Because the values may have * duplicates and follow the insertion ordering, this method returns a {@link * List}, instead of the {@link Collection} specified in the {@link * ListMultimap} interface. */ @Override public List values() { List result = valuesList; if (result == null) { valuesList = result = new AbstractSequentialList() { @Override public int size() { return keyCount.size(); } @Override public ListIterator listIterator(int index) { final NodeIterator nodes = new NodeIterator(index); return new ListIterator() { @Override public boolean hasNext() { return nodes.hasNext(); } @Override public V next() { return nodes.next().value; } @Override public boolean hasPrevious() { return nodes.hasPrevious(); } @Override public V previous() { return nodes.previous().value; } @Override public int nextIndex() { return nodes.nextIndex(); } @Override public int previousIndex() { return nodes.previousIndex(); } @Override public void remove() { nodes.remove(); } @Override public void set(V e) { nodes.setValue(e); } @Override public void add(V e) { throw new UnsupportedOperationException(); } }; } }; } return result; } private static Entry createEntry(final Node node) { return new AbstractMapEntry() { @Override public K getKey() { return node.key; } @Override public V getValue() { return node.value; } @Override public V setValue(V value) { V oldValue = node.value; node.value = value; return oldValue; } }; } private transient List> entries; /** * {@inheritDoc} * *

The iterator generated by the returned collection traverses the entries * in the order they were added to the multimap. Because the entries may have * duplicates and follow the insertion ordering, this method returns a {@link * List}, instead of the {@link Collection} specified in the {@link * ListMultimap} interface. * *

An entry's {@link Entry#getKey} method always returns the same key, * regardless of what happens subsequently. As long as the corresponding * key-value mapping is not removed from the multimap, {@link Entry#getValue} * returns the value from the multimap, which may change over time, and {@link * Entry#setValue} modifies that value. Removing the mapping from the * multimap does not alter the value returned by {@code getValue()}, though a * subsequent {@code setValue()} call won't update the multimap but will lead * to a revised value being returned by {@code getValue()}. */ @Override public List> entries() { List> result = entries; if (result == null) { entries = result = new AbstractSequentialList>() { @Override public int size() { return keyCount.size(); } @Override public ListIterator> listIterator(int index) { final ListIterator> nodes = new NodeIterator(index); return new ListIterator>() { @Override public boolean hasNext() { return nodes.hasNext(); } @Override public Entry next() { return createEntry(nodes.next()); } @Override public void remove() { nodes.remove(); } @Override public boolean hasPrevious() { return nodes.hasPrevious(); } @Override public Map.Entry previous() { return createEntry(nodes.previous()); } @Override public int nextIndex() { return nodes.nextIndex(); } @Override public int previousIndex() { return nodes.previousIndex(); } @Override public void set(Map.Entry e) { throw new UnsupportedOperationException(); } @Override public void add(Map.Entry e) { throw new UnsupportedOperationException(); } }; } }; } return result; } private class AsMapEntries extends AbstractSet>> { @Override public int size() { return keyCount.elementSet().size(); } @Override public Iterator>> iterator() { final Iterator keyIterator = new DistinctKeyIterator(); return new Iterator>>() { @Override public boolean hasNext() { return keyIterator.hasNext(); } @Override public Entry> next() { final K key = keyIterator.next(); return new AbstractMapEntry>() { @Override public K getKey() { return key; } @Override public Collection getValue() { return LinkedListMultimap.this.get(key); } }; } @Override public void remove() { keyIterator.remove(); } }; } // TODO(jlevy): Override contains() and remove() for better performance. } private transient Map> map; @Override public Map> asMap() { Map> result = map; if (result == null) { map = result = new AbstractMap>() { Set>> entrySet; @Override public Set>> entrySet() { Set>> result = entrySet; if (result == null) { entrySet = result = new AsMapEntries(); } return result; } // The following methods are included for performance. @Override public boolean containsKey(@Nullable Object key) { return LinkedListMultimap.this.containsKey(key); } @SuppressWarnings("unchecked") @Override public Collection get(@Nullable Object key) { Collection collection = LinkedListMultimap.this.get((K) key); return collection.isEmpty() ? null : collection; } @Override public Collection remove(@Nullable Object key) { Collection collection = removeAll(key); return collection.isEmpty() ? null : collection; } }; } return result; } // Comparison and hashing /** * Compares the specified object to this multimap for equality. * *

Two {@code ListMultimap} instances are equal if, for each key, they * contain the same values in the same order. If the value orderings disagree, * the multimaps will not be considered equal. */ @Override public boolean equals(@Nullable Object other) { if (other == this) { return true; } if (other instanceof Multimap) { Multimap that = (Multimap) other; return this.asMap().equals(that.asMap()); } return false; } /** * Returns the hash code for this multimap. * *

The hash code of a multimap is defined as the hash code of the map view, * as returned by {@link Multimap#asMap}. */ @Override public int hashCode() { return asMap().hashCode(); } /** * Returns a string representation of the multimap, generated by calling * {@code toString} on the map returned by {@link Multimap#asMap}. * * @return a string representation of the multimap */ @Override public String toString() { return asMap().toString(); } /** * @serialData the number of distinct keys, and then for each distinct key: * the first key, the number of values for that key, and the key's values, * followed by successive keys and values from the entries() ordering */ @GwtIncompatible("java.io.ObjectOutputStream") private void writeObject(ObjectOutputStream stream) throws IOException { stream.defaultWriteObject(); stream.writeInt(size()); for (Entry entry : entries()) { stream.writeObject(entry.getKey()); stream.writeObject(entry.getValue()); } } @GwtIncompatible("java.io.ObjectInputStream") private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { stream.defaultReadObject(); keyCount = LinkedHashMultiset.create(); keyToKeyHead = Maps.newHashMap(); keyToKeyTail = Maps.newHashMap(); int size = stream.readInt(); for (int i = 0; i < size; i++) { @SuppressWarnings("unchecked") // reading data stored by writeObject K key = (K) stream.readObject(); @SuppressWarnings("unchecked") // reading data stored by writeObject V value = (V) stream.readObject(); put(key, value); } } @GwtIncompatible("java serialization not supported") private static final long serialVersionUID = 0; }