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.checkArgument;
 import static com.google.common.base.Preconditions.checkState;
 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>
    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> {
    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 String toString() {
      return  + "=" + ;
    }
  }
  private transient Node<K, V> head// the head for all keys
  private transient Node<K, V> tail// the tail for all keys
  private transient Multiset<K> keyCount// the number of values for each key
  private transient Map<K, Node<K, V>> keyToKeyHead// the head for a given key
  private transient Map<K, Node<K, V>> keyToKeyTail// the tail for a given key

  
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);
  }
     = LinkedHashMultiset.create();
     = Maps.newHashMap();
     = Maps.newHashMap();
  }
  private LinkedListMultimap(int expectedKeys) {
     = LinkedHashMultiset.create(expectedKeys);
     = Maps.newHashMapWithExpectedSize(expectedKeys);
     = Maps.newHashMapWithExpectedSize(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(keynode);
      .put(keynode);
    } else if (nextSibling == null) { // non-empty list, add to tail
      . = node;
      node.previous = ;
      Node<K, V> keyTail = .get(key);
      if (keyTail == null) { // first for this key
        .put(keynode);
      } else {
        keyTail.nextSibling = node;
        node.previousSibling = keyTail;
      }
      .put(keynode);
       = 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
        .put(keynode);
      } else {
        nextSibling.previousSibling.nextSibling = node;
      }
      if (nextSibling.previous == null) { // nextSibling was head
         = node;
      } else {
        nextSibling.previous.next = node;
      }
      nextSibling.previous = node;
      nextSibling.previousSibling = node;
    }
    .add(key);
    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.previousSibling.nextSibling = node.nextSibling;
    } else if (node.nextSibling != null) { // node was key head
      .put(node.keynode.nextSibling);
    } else {
      .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
      .put(node.keynode.previousSibling);
    } else {
      .remove(node.key); // don't leak a key-null entry
    }
    .remove(node.key);
  }

  
Removes all nodes for the specified key.
  private void removeAllNodes(@Nullable Object key) {
    for (Iterator<V> 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 Iterator over all nodes.
  private class NodeIterator implements ListIterator<Node<K, V>> {
    int nextIndex;
    Node<K, V> next;
    Node<K, V> current;
    Node<K, V> previous;
    NodeIterator() {
       = ;
    }
    NodeIterator(int index) {
      int size = size();
      Preconditions.checkPositionIndex(indexsize);
      if (index >= (size / 2)) {
         = ;
         = size;
        while (index++ < size) {
          previous();
        }
      } else {
         = ;
        while (index-- > 0) {
          next();
        }
      }
       = null;
    }
    @Override
    public boolean hasNext() {
      return  != null;
    }
    @Override
    public Node<K, V> next() {
      checkElement();
       =  = ;
       = .;
      ++;
      return ;
    }
    @Override
    public void remove() {
      checkState( != 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(Node<K, V> e) {
      throw new UnsupportedOperationException();
    }
    @Override
    public void add(Node<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;
    @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() {
      checkState( != 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;
       = .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 keyint index) {
      int size = .count(key);
      Preconditions.checkPositionIndex(indexsize);
      if (index >= (size / 2)) {
         = .get(key);
         = size;
        while (index++ < size) {
          previous();
        }
      } else {
         = .get(key);
        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() {
      checkState( != 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 .size();
  }
  public boolean isEmpty() {
    return  == null;
  }
  public boolean containsKey(@Nullable Object key) {
    return .containsKey(key);
  }
  public boolean containsValue(@Nullable Object value) {
    for (Iterator<Node<K, V>> i = new NodeIterator(); i.hasNext();) {
      if (Objects.equal(i.next().value)) {
        return true;
      }
    }
    return false;
  }
  public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
    for (Iterator<V> 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.

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;
  }
  public boolean remove(@Nullable Object key, @Nullable Object value) {
    Iterator<V> values = new ValueForKeyIterator(key);
    while (values.hasNext()) {
      if (Objects.equal(values.next(), value)) {
        values.remove();
        return true;
      }
    }
    return false;
  }
  // Bulk Operations
  public boolean putAll(@Nullable K keyIterable<? extends V> values) {
    boolean changed = false;
    for (V value : values) {
      changed |= put(keyvalue);
    }
    return changed;
  }
  public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
    boolean changed = false;
    for (Entry<? extends K, ? extends V> entry : multimap.entries()) {
      changed |= put(entry.getKey(), entry.getValue());
    }
    return changed;
  }

  

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;
    .clear();
  }
  // 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() {
        return .count(key);
      }
      @Override public ListIterator<V> listIterator(int index) {
        return new ValueForKeyIterator(keyindex);
      }
      @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<K> keySet;
  public Set<K> keySet() {
    Set<K> result = ;
    if (result == null) {
       = result = new Sets.ImprovedAbstractSet<K>() {
        @Override public int size() {
          return .elementSet().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 result;
  }
  private transient Multiset<K> keys;
  public Multiset<K> keys() {
    Multiset<K> result = ;
    if (result == null) {
       = result = new MultisetView();
    }
    return result;
  }
  private class MultisetView extends AbstractMultiset<K> {
    @Override
    public int size() {
      return .size();
    }
    @Override
    public int count(Object element) {
      return .count(element);
    }
    @Override
    Iterator<Entry<K>> entryIterator() {
      return new TransformedIterator<K, Entry<K>>(new DistinctKeyIterator()) {
        @Override
        Entry<K> transform(final K key) {
          return new Multisets.AbstractEntry<K>() {
            @Override
            public K getElement() {
              return key;
            }
            @Override
            public int getCount() {
              return .count(key);
            }
          };
        }
      };
    }
    @Override
    int distinctElements() {
      return elementSet().size();
    }
    @Override public Iterator<K> iterator() {
      return new TransformedIterator<Node<K, V>, K>(new NodeIterator()) {
        @Override
        K transform(Node<K, V> node) {
          return node.key;
        }
      };
    }
    @Override
    public int remove(@Nullable Object keyint occurrences) {
      checkArgument(occurrences >= 0);
      int oldCount = count(key);
      Iterator<V> values = new ValueForKeyIterator(key);
      while ((occurrences-- > 0) && values.hasNext()) {
        values.next();
        values.remove();
      }
      return oldCount;
    }
    @Override
    public Set<K> elementSet() {
      return keySet();
    }
    @Override public boolean equals(@Nullable Object object) {
      return .equals(object);
    }
    @Override public int hashCode() {
      return .hashCode();
    }
    @Override public String toString() {
      return .toString(); // XXX observe order?
    }
  }
  private transient List<V> valuesList;

  

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() {
    List<V> result = ;
    if (result == null) {
       = result = new AbstractSequentialList<V>() {
        @Override public int size() {
          return .size();
        }
        @Override
        public ListIterator<V> listIterator(int index) {
          final NodeIterator nodes = new NodeIterator(index);
          return new TransformedListIterator<Node<K, V>, V>(nodes) {
            @Override
            V transform(Node<K, V> node) {
              return node.value;
            }
            @Override
            public void set(V value) {
              nodes.setValue(value);
            }
          };
        }
      };
    }
    return result;
  }
  private static <K, V> Entry<K, V> createEntry(final Node<K, V> node) {
    return new AbstractMapEntry<K, V>() {
      @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<Entry<K, V>> entries;

  

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() {
    List<Entry<K, V>> result = ;
    if (result == null) {
       = result = new AbstractSequentialList<Entry<K, V>>() {
        @Override public int size() {
          return .size();
        }
        @Override public ListIterator<Entry<K, V>> listIterator(int index) {
          return new TransformedListIterator<Node<K, V>, Entry<K, V>>(new NodeIterator(index)) {
            @Override
            Entry<K, V> transform(Node<K, V> node) {
              return createEntry(node);
            }
          };
        }
      };
    }
    return result;
  }
  private transient Map<K, Collection<V>> map;
  public Map<K, Collection<V>> asMap() {
    Map<K, Collection<V>> result = ;
    if (result == null) {
       = result = new Multimaps.AsMap<K, V>() {
        @Override
        public int size() {
          return .elementSet().size();
        }
        @Override
        Multimap<K, V> multimap() {
          return LinkedListMultimap.this;
        }
        @Override
        Iterator<Entry<K, Collection<V>>> entryIterator() {
          return new TransformedIterator<K, Entry<K, Collection<V>>>(new DistinctKeyIterator()) {
            @Override
            Entry<K, Collection<V>> transform(final K key) {
              return new AbstractMapEntry<K, Collection<V>>() {
                @Override public K getKey() {
                  return key;
                }
                @Override public Collection<V> getValue() {
                  return LinkedListMultimap.this.get(key);
                }
              };
            }
          };
        }
      };
    }
    return result;
  }
  // Comparison and hashing

  
Compares the specified object to this multimap for equality.

Two 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 Multimap.asMap.

  @Override public int hashCode() {
    return asMap().hashCode();
  }

  
Returns a string representation of the multimap, generated by calling toString on the map returned by Multimap.asMap.

Returns:
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 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();
     = LinkedHashMultiset.create();
     = Maps.newHashMap();
     = Maps.newHashMap();
    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