Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * 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 java.util.List;
 import java.util.Map;
 import java.util.Set;
 
 import  javax.annotation.Nullable;

An implementation of 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:
   Multimap<K, V> multimap = LinkedListMultimap.create();
   multimap.put(key1, foo);
   multimap.put(key2, bar);
   multimap.put(key1, baz);
... the iteration order for keys() is [key1, key2, key1], and similarly for entries(). Unlike LinkedHashMultimap, the iteration order is kept consistent between keys, entries and values. For example, calling:
   map.remove(key1, foo);

changes the entries iteration order to [key2=bar, key1=baz] and the key iteration order to [key2, key1]. The entries() iterator returns mutable map entries, and replaceValues attempts to preserve iteration order as much as possible.

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

The values() and entries() methods both return a List, instead of the Collection specified by the ListMultimap interface.

The methods get, keySet(), keys(), values, entries(), and 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 Multimaps.synchronizedListMultimap.

See the Guava User Guide article on Multimap.

Author(s):
Mike Bostock
Since:
2.0 (imported from Google Collections Library)
@GwtCompatible(serializable = true, emulated = true)
public class LinkedListMultimap<K, V> extends AbstractMultimap<K, V>
    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<K, V> {
    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;
      this. = value;
    }
    @Override
    public K getKey() {
      return ;
    }
    @Override
    public V getValue() {
      return ;
    }
    @Override
    public V setValue(@Nullable V newValue) {
      V result = ;
      this. = 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. = firstNode;
      this. = firstNode;
      firstNode.previousSibling = null;
      firstNode.nextSibling = null;
      this. = 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<K, V>> 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 LinkedListMultimap with the default initial capacity.
  public static <K, V> LinkedListMultimap<K, V> create() {
    return new LinkedListMultimap<K, V>();
  }

  
Constructs an empty LinkedListMultimap with enough capacity to hold the specified number of keys without rehashing.

Parameters:
expectedKeys the expected number of distinct keys
Throws:
IllegalArgumentException if expectedKeys is negative
  public static <K, V> LinkedListMultimap<K, V> create(int expectedKeys) {
    return new LinkedListMultimap<K, V>(expectedKeys);
  }

  
Constructs a LinkedListMultimap with the same mappings as the specified Multimap. The new multimap has the same Multimap.entries() iteration order as the input multimap.

Parameters:
multimap the multimap whose contents are copied to this multimap
  public static <K, V> LinkedListMultimap<K, V> create(
      Multimap<? extends K, ? extends V> multimap) {
    return new LinkedListMultimap<K, V>(multimap);
  }
     = Maps.newHashMap();
  }
  private LinkedListMultimap(int expectedKeys) {
     = new HashMap<K, KeyList<K, V>>(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 nextSibling element, or at the end of the list if nextSibling is null. Note: if nextSibling is specified, it MUST be for an node for the same key!
  private Node<K, V> addNode(
      @Nullable K key, @Nullable V value, @Nullable Node<K, V> nextSibling) {
    Node<K, V> node = new Node<K, V>(keyvalue);
    if ( == null) { // empty list
       =  = node;
      .put(keynew KeyList<K, V>(node));
      ++;
    } else if (nextSibling == null) { // non-empty list, add to tail
      . = node;
      node.previous = ;
       = node;
      KeyList<K, V> keyList = .get(key);
      if (keyList == null) {
        .put(keykeyList = new KeyList<K, V>(node));
        ++;
      } 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 = .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
        .get(key). = node;
      } else {
        nextSibling.previousSibling.nextSibling = node;
      }
      if (nextSibling.previous == null) { // nextSibling was head
         = node;
      } else {
        nextSibling.previous.next = node;
      }
      nextSibling.previous = node;
      nextSibling.previousSibling = node;
    }
    ++;
    return node;
  }

  
Removes the specified node from the linked list. This method is only intended to be used from the Iterator classes. See also LinkedListMultimap.removeAllNodes(Object).
  private void removeNode(Node<K, V> node) {
    if (node.previous != null) {
      node.previous.next = node.next;
    } else { // node was head
       = node.next;
    }
    if (node.next != null) {
      node.next.previous = node.previous;
    } else { // node was tail
       = node.previous;
    }
    if (node.previousSibling == null && node.nextSibling == null) {
      KeyList<K, V> keyList = .remove(node.key);
      keyList.count = 0;
      ++;
    } else {
      KeyList<K, V> keyList = .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;
      }
    }
    --;
  }

  
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 Iterator over all nodes.
  private class NodeIterator implements ListIterator<Entry<K, V>> {
    int nextIndex;
    Node<K, V> next;
    Node<K, V> current;
    Node<K, V> previous;
    int expectedModCount = ;
    NodeIterator(int index) {
      int size = size();
      checkPositionIndex(indexsize);
      if (index >= (size / 2)) {
         = ;
         = size;
        while (index++ < size) {
          previous();
        }
      } else {
         = ;
        while (index-- > 0) {
          next();
        }
      }
       = null;
    }
    private void checkForConcurrentModification() {
      if ( != ) {
        throw new ConcurrentModificationException();
      }
    }
    @Override
    public boolean hasNext() {
      return  != null;
    }
    @Override
    public Node<K, V> next() {
      checkElement();
       =  = ;
       = .;
      ++;
      return ;
    }
    @Override
    public void remove() {
      checkRemove( != null);
      if ( != ) { // after call to next()
         = .;
        --;
      } else { // after call to previous()
         = .;
      }
      removeNode();
       = null;
       = ;
    }
    @Override
    public boolean hasPrevious() {
      return  != null;
    }
    @Override
    public Node<K, V> previous() {
       =  = ;
       = .;
      --;
      return ;
    }
    @Override
    public int nextIndex() {
      return ;
    }
    @Override
    public int previousIndex() {
      return  - 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( != null);
      . = value;
    }
  }

  
An Iterator over distinct keys in key head order.
  private class DistinctKeyIterator implements Iterator<K> {
    final Set<K> seenKeys = Sets.<K>newHashSetWithExpectedSize(keySet().size());
    Node<K, V> next = ;
    Node<K, V> current;
    int expectedModCount = ;
    
    private void checkForConcurrentModification() {
      if ( != ) {
        throw new ConcurrentModificationException();
      }
    }
    @Override
    public boolean hasNext() {
      return  != null;
    }
    @Override
    public K next() {
      checkElement();
       = ;
      .add(.);
      do { // skip ahead to next unseen key
         = .;
      } while (( != null) && !.add(.));
      return .;
    }
    @Override
    public void remove() {
      checkRemove( != null);
       = null;
       = ;
    }
  }

  
A 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;
      KeyList<K, V> keyList = .get(key);
       = (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 keyint index) {
      KeyList<K, V> keyList = .get(key);
      int size = (keyList == null) ? 0 : keyList.count;
      checkPositionIndex(indexsize);
      if (index >= (size / 2)) {
         = (keyList == null) ? null : keyList.tail;
         = size;
        while (index++ < size) {
          previous();
        }
      } else {
         = (keyList == null) ? null : keyList.head;
        while (index-- > 0) {
          next();
        }
      }
      this. = key;
       = null;
    }
    @Override
    public boolean hasNext() {
      return  != null;
    }
    @Override
    public V next() {
      checkElement();
       =  = ;
       = .;
      ++;
      return .;
    }
    @Override
    public boolean hasPrevious() {
      return  != null;
    }
    @Override
    public V previous() {
       =  = ;
      --;
      return .;
    }
    @Override
    public int nextIndex() {
      return ;
    }
    @Override
    public int previousIndex() {
      return  - 1;
    }
    @Override
    public void remove() {
      checkRemove( != null);
      if ( != ) { // after call to next()
         = .;
        --;
      } else { // after call to previous()
         = .;
      }
      removeNode();
       = null;
    }
    @Override
    public void set(V value) {
      checkState( != null);
      . = value;
    }
    @Override
    @SuppressWarnings("unchecked")
    public void add(V value) {
       = addNode((K) value);
      ++;
       = null;
    }
  }
  // Query Operations
  public int size() {
    return ;
  }
  public boolean isEmpty() {
    return  == null;
  }
  public boolean containsKey(@Nullable Object key) {
    return .containsKey(key);
  }
  public boolean containsValue(@Nullable Object value) {
    return values().contains(value);
  }
  // Modification Operations

  
Stores a key-value pair in the multimap.

Parameters:
key key to store in the multimap
value value to store in the multimap
Returns:
true always
  public boolean put(@Nullable K key, @Nullable V value) {
    addNode(keyvaluenull);
    return true;
  }
  // Bulk Operations

  

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

The returned list is immutable and implements java.util.RandomAccess.

  public List<V> replaceValues(@Nullable K keyIterable<? extends V> 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)));
  }

  

The returned list is immutable and implements java.util.RandomAccess.

  public List<V> removeAll(@Nullable Object key) {
    List<V> oldValues = getCopy(key);
    removeAllNodes(key);
    return oldValues;
  }
  public void clear() {
     = null;
     = null;
     = 0;
    ++;
  }
  // Views

  

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

The returned list is not serializable and does not have random access.

  public List<V> get(final @Nullable K key) {
    return new AbstractSequentialList<V>() {
      @Override public int size() {
        KeyList<K, V> keyList = .get(key);
        return (keyList == null) ? 0 : keyList.count;
      }
      @Override public ListIterator<V> listIterator(int index) {
        return new ValueForKeyIterator(keyindex);
      }
    };
  }
  Set<K> createKeySet() {
    return new Sets.ImprovedAbstractSet<K>() {
      @Override public int size() {
        return .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();
      }
    };
  }

  

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 List, instead of the Collection specified in the ListMultimap interface.

  public List<V> values() {
    return (List<V>) super.values();
  }
  List<V> createValues() {
    return new AbstractSequentialList<V>() {
      @Override public int size() {
        return ;
      }
      @Override public ListIterator<V> listIterator(int index) {
        final NodeIterator nodeItr = new NodeIterator(index);
        return new TransformedListIterator<Entry<K, V>, V>(nodeItr) {
          @Override
          V transform(Entry<K, V> entry) {
            return entry.getValue();
          }
          @Override
          public void set(V value) {
            nodeItr.setValue(value);
          }
        };
      }
    };
  }

  

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 List, instead of the Collection specified in the ListMultimap interface.

An entry's 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, Entry.getValue returns the value from the multimap, which may change over time, and Entry.setValue modifies that value. Removing the mapping from the multimap does not alter the value returned by getValue(), though a subsequent setValue() call won't update the multimap but will lead to a revised value being returned by getValue().

  public List<Entry<K, V>> entries() {
    return (List<Entry<K, V>>) super.entries();
  }
  List<Entry<K, V>> createEntries() {
    return new AbstractSequentialList<Entry<K, V>>() {
      @Override public int size() {
        return ;
      }
      @Override public ListIterator<Entry<K, V>> listIterator(int index) {
        return new NodeIterator(index);
      }
    };
  }
  Iterator<Entry<K, V>> entryIterator() {
    throw new AssertionError("should never be called");
  }
  Map<K, Collection<V>> 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 streamthrows 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 IOExceptionClassNotFoundException {
    stream.defaultReadObject();
     = Maps.newLinkedHashMap();
    int size = stream.readInt();
    for (int i = 0; i < sizei++) {
      @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(keyvalue);
    }
  }
  @GwtIncompatible("java serialization not supported")
  private static final long serialVersionUID = 0;
New to GrepCode? Check out our FAQ X