|
Java example source code file (LinkedListMultimap.java)
This example Java source code file (LinkedListMultimap.java) is included in the alvinalexander.com
"Java Source Code
Warehouse" project. The intent of this project is to help you "Learn
Java by Example" TM.
Learn more about this Java project at its project page.
The LinkedListMultimap.java Java example source code
/*
* 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.checkPositionIndex;
import static com.google.common.base.Preconditions.checkState;
import static com.google.common.collect.CollectPreconditions.checkRemove;
import static java.util.Collections.unmodifiableList;
import com.google.common.annotations.GwtCompatible;
import com.google.common.annotations.GwtIncompatible;
import com.google.errorprone.annotations.CanIgnoreReturnValue;
import com.google.j2objc.annotations.WeakOuter;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.util.AbstractSequentialList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
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: <pre> {@code
*
* Multimap<K, V> multimap = LinkedListMultimap.create();
* multimap.put(key1, foo);
* multimap.put(key2, bar);
* multimap.put(key1, baz);}</pre>
*
* ... 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: <pre> {@code
*
* map.remove(key1, foo);}</pre>
*
* <p>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.
*
* <p>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.
*
* <p>The {@link #values()} and {@link #entries()} methods both return a
* {@code List}, instead of the {@code Collection} specified by the {@link
* ListMultimap} interface.
*
* <p>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.
*
* <p>Keys and values may be null. All optional multimap methods are supported,
* and all returned views are modifiable.
*
* <p>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}.
*
* <p>See the Guava User Guide article on
implements ListMultimap<K, V>, 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<K, V> extends AbstractMapEntry {
final K key;
V value;
Node<K, V> next; // the next node (with any key)
Node<K, V> previous; // the previous node (with any key)
Node<K, V> nextSibling; // the next node with the same key
Node<K, V> previousSibling; // the previous node with the same key
Node(@Nullable K key, @Nullable V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return value;
}
@Override
public V setValue(@Nullable V newValue) {
V result = value;
this.value = newValue;
return result;
}
}
private static class KeyList<K, V> {
Node<K, V> head;
Node<K, V> tail;
int count;
KeyList(Node<K, V> firstNode) {
this.head = firstNode;
this.tail = firstNode;
firstNode.previousSibling = null;
firstNode.nextSibling = null;
this.count = 1;
}
}
private transient Node<K, V> head; // the head for all keys
private transient Node<K, V> tail; // the tail for all keys
private transient Map<K, KeyList keyToKeyList;
private transient int size;
/*
* Tracks modifications to keyToKeyList so that addition or removal of keys invalidates
* preexisting iterators. This does *not* track simple additions and removals of values
* that are not the first to be added or last to be removed for their key.
*/
private transient int modCount;
/**
* Creates a new, empty {@code LinkedListMultimap} with the default initial
* capacity.
*/
public static <K, V> LinkedListMultimap create() {
return new LinkedListMultimap<K, V>();
}
/**
* 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 <K, V> LinkedListMultimap create(int expectedKeys) {
return new LinkedListMultimap<K, V>(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 <K, V> LinkedListMultimap create(
Multimap<? extends K, ? extends V> multimap) {
return new LinkedListMultimap<K, V>(multimap);
}
LinkedListMultimap() {
keyToKeyList = Maps.newHashMap();
}
private LinkedListMultimap(int expectedKeys) {
keyToKeyList = new HashMap<K, KeyList(expectedKeys);
}
private LinkedListMultimap(Multimap<? extends K, ? extends V> 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}!
*/
@CanIgnoreReturnValue
private Node<K, V> addNode(@Nullable K key, @Nullable V value, @Nullable Node nextSibling) {
Node<K, V> node = new Node(key, value);
if (head == null) { // empty list
head = tail = node;
keyToKeyList.put(key, new KeyList<K, V>(node));
modCount++;
} else if (nextSibling == null) { // non-empty list, add to tail
tail.next = node;
node.previous = tail;
tail = node;
KeyList<K, V> keyList = keyToKeyList.get(key);
if (keyList == null) {
keyToKeyList.put(key, keyList = new KeyList<K, V>(node));
modCount++;
} else {
keyList.count++;
Node<K, V> keyTail = keyList.tail;
keyTail.nextSibling = node;
node.previousSibling = keyTail;
keyList.tail = node;
}
} else { // non-empty list, insert before nextSibling
KeyList<K, V> keyList = keyToKeyList.get(key);
keyList.count++;
node.previous = nextSibling.previous;
node.previousSibling = nextSibling.previousSibling;
node.next = nextSibling;
node.nextSibling = nextSibling;
if (nextSibling.previousSibling == null) { // nextSibling was key head
keyToKeyList.get(key).head = 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;
}
size++;
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<K, V> 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.nextSibling == null) {
KeyList<K, V> keyList = keyToKeyList.remove(node.key);
keyList.count = 0;
modCount++;
} else {
KeyList<K, V> keyList = keyToKeyList.get(node.key);
keyList.count--;
if (node.previousSibling == null) {
keyList.head = node.nextSibling;
} else {
node.previousSibling.nextSibling = node.nextSibling;
}
if (node.nextSibling == null) {
keyList.tail = node.previousSibling;
} else {
node.nextSibling.previousSibling = node.previousSibling;
}
}
size--;
}
/** Removes all nodes for the specified key. */
private void removeAllNodes(@Nullable Object key) {
Iterators.clear(new ValueForKeyIterator(key));
}
/** 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<Entry {
int nextIndex;
Node<K, V> next;
Node<K, V> current;
Node<K, V> previous;
int expectedModCount = modCount;
NodeIterator(int index) {
int size = size();
checkPositionIndex(index, size);
if (index >= (size / 2)) {
previous = tail;
nextIndex = size;
while (index++ < size) {
previous();
}
} else {
next = head;
while (index-- > 0) {
next();
}
}
current = null;
}
private void checkForConcurrentModification() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
@Override
public boolean hasNext() {
checkForConcurrentModification();
return next != null;
}
@CanIgnoreReturnValue
@Override
public Node<K, V> next() {
checkForConcurrentModification();
checkElement(next);
previous = current = next;
next = next.next;
nextIndex++;
return current;
}
@Override
public void remove() {
checkForConcurrentModification();
checkRemove(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;
expectedModCount = modCount;
}
@Override
public boolean hasPrevious() {
checkForConcurrentModification();
return previous != null;
}
@CanIgnoreReturnValue
@Override
public Node<K, V> previous() {
checkForConcurrentModification();
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(Entry<K, V> e) {
throw new UnsupportedOperationException();
}
@Override
public void add(Entry<K, V> 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<K> {
final Set<K> seenKeys = Sets.newHashSetWithExpectedSize(keySet().size());
Node<K, V> next = head;
Node<K, V> current;
int expectedModCount = modCount;
private void checkForConcurrentModification() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
@Override
public boolean hasNext() {
checkForConcurrentModification();
return next != null;
}
@Override
public K next() {
checkForConcurrentModification();
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() {
checkForConcurrentModification();
checkRemove(current != null);
removeAllNodes(current.key);
current = null;
expectedModCount = modCount;
}
}
/** A {@code ListIterator} over values for a specified key. */
private class ValueForKeyIterator implements ListIterator<V> {
final Object key;
int nextIndex;
Node<K, V> next;
Node<K, V> current;
Node<K, V> previous;
/** Constructs a new iterator over all values for the specified key. */
ValueForKeyIterator(@Nullable Object key) {
this.key = key;
KeyList<K, V> keyList = keyToKeyList.get(key);
next = (keyList == null) ? null : keyList.head;
}
/**
* 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) {
KeyList<K, V> keyList = keyToKeyList.get(key);
int size = (keyList == null) ? 0 : keyList.count;
checkPositionIndex(index, size);
if (index >= (size / 2)) {
previous = (keyList == null) ? null : keyList.tail;
nextIndex = size;
while (index++ < size) {
previous();
}
} else {
next = (keyList == null) ? null : keyList.head;
while (index-- > 0) {
next();
}
}
this.key = key;
current = null;
}
@Override
public boolean hasNext() {
return next != null;
}
@CanIgnoreReturnValue
@Override
public V next() {
checkElement(next);
previous = current = next;
next = next.nextSibling;
nextIndex++;
return current.value;
}
@Override
public boolean hasPrevious() {
return previous != null;
}
@CanIgnoreReturnValue
@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() {
checkRemove(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 size;
}
@Override
public boolean isEmpty() {
return head == null;
}
@Override
public boolean containsKey(@Nullable Object key) {
return keyToKeyList.containsKey(key);
}
@Override
public boolean containsValue(@Nullable Object value) {
return values().contains(value);
}
// 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
*/
@CanIgnoreReturnValue
@Override
public boolean put(@Nullable K key, @Nullable V value) {
addNode(key, value, null);
return true;
}
// Bulk Operations
/**
* {@inheritDoc}
*
* <p>If any entries for the specified {@code key} already exist in the
* multimap, their values are changed in-place without affecting the iteration
* order.
*
* <p>The returned list is immutable and implements
* {@link java.util.RandomAccess}.
*/
@CanIgnoreReturnValue
@Override
public List<V> replaceValues(@Nullable K key, Iterable values) {
List<V> oldValues = getCopy(key);
ListIterator<V> keyValues = new ValueForKeyIterator(key);
Iterator<? extends V> 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<V> getCopy(@Nullable Object key) {
return unmodifiableList(Lists.newArrayList(new ValueForKeyIterator(key)));
}
/**
* {@inheritDoc}
*
* <p>The returned list is immutable and implements
* {@link java.util.RandomAccess}.
*/
@CanIgnoreReturnValue
@Override
public List<V> removeAll(@Nullable Object key) {
List<V> oldValues = getCopy(key);
removeAllNodes(key);
return oldValues;
}
@Override
public void clear() {
head = null;
tail = null;
keyToKeyList.clear();
size = 0;
modCount++;
}
// Views
/**
* {@inheritDoc}
*
* <p>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.
*
* <p>The returned list is not serializable and does not have random access.
*/
@Override
public List<V> get(final @Nullable K key) {
return new AbstractSequentialList<V>() {
@Override
public int size() {
KeyList<K, V> keyList = keyToKeyList.get(key);
return (keyList == null) ? 0 : keyList.count;
}
@Override
public ListIterator<V> listIterator(int index) {
return new ValueForKeyIterator(key, index);
}
};
}
@Override
Set<K> createKeySet() {
@WeakOuter
class KeySetImpl extends Sets.ImprovedAbstractSet<K> {
@Override
public int size() {
return keyToKeyList.size();
}
@Override
public Iterator<K> iterator() {
return new DistinctKeyIterator();
}
@Override
public boolean contains(Object key) { // for performance
return containsKey(key);
}
@Override
public boolean remove(Object o) { // for performance
return !LinkedListMultimap.this.removeAll(o).isEmpty();
}
}
return new KeySetImpl();
}
/**
* {@inheritDoc}
*
* <p>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<V> values() {
return (List<V>) super.values();
}
@Override
List<V> createValues() {
@WeakOuter
class ValuesImpl extends AbstractSequentialList<V> {
@Override
public int size() {
return size;
}
@Override
public ListIterator<V> listIterator(int index) {
final NodeIterator nodeItr = new NodeIterator(index);
return new TransformedListIterator<Entry(nodeItr) {
@Override
V transform(Entry<K, V> entry) {
return entry.getValue();
}
@Override
public void set(V value) {
nodeItr.setValue(value);
}
};
}
}
return new ValuesImpl();
}
/**
* {@inheritDoc}
*
* <p>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.
*
* <p>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<Entry entries() {
return (List<Entry) super.entries();
}
@Override
List<Entry createEntries() {
@WeakOuter
class EntriesImpl extends AbstractSequentialList<Entry {
@Override
public int size() {
return size;
}
@Override
public ListIterator<Entry listIterator(int index) {
return new NodeIterator(index);
}
}
return new EntriesImpl();
}
@Override
Iterator<Entry entryIterator() {
throw new AssertionError("should never be called");
}
@Override
Map<K, Collection createAsMap() {
return new Multimaps.AsMap<K, V>(this);
}
/**
* @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<K, V> entry : entries()) {
stream.writeObject(entry.getKey());
stream.writeObject(entry.getValue());
}
}
@GwtIncompatible // java.io.ObjectInputStream
private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
stream.defaultReadObject();
keyToKeyList = Maps.newLinkedHashMap();
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;
}
|