/*
    * 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 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 <a href=
   * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
   * {@code Multimap}</a>.
   *
   * @author 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 = 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<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 {@code LinkedListMultimap} with the default initial
    * capacity.
    */
   public static <K, V> LinkedListMultimap<K, V> 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<K, V> 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<K, V> 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<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
    * {@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<K, V> addNode(
       @Nullable K key, @Nullable V value, @Nullable Node<K, V> nextSibling) {
     Node<K, V> node = new Node<K, V>(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<K, V>> {
     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;
     }
     @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;
     }
     @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.<K>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;
     }
 
     @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() {
       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
    */
   @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}.
    */
   @Override
   public List<V> replaceValues(@Nullable K key, Iterable<? 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)));
   }
 
   /**
    * {@inheritDoc}
    *
    * <p>The returned list is immutable and implements
    * {@link java.util.RandomAccess}.
    */
   @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() {
     return new 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();
       }
     };
   }
 
   /**
    * {@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() {
     return new 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<K, V>, V>(nodeItr) {
           @Override
           V transform(Entry<K, V> entry) {
             return entry.getValue();
           }
 
           @Override
           public void set(V value) {
             nodeItr.setValue(value);
           }
         };
       }
     };
   }
 
   /**
    * {@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<K, V>> entries() {
     return (List<Entry<K, V>>) super.entries();
   }
 
   @Override
   List<Entry<K, V>> createEntries() {
     return new AbstractSequentialList<Entry<K, V>>() {
       @Override public int size() {
         return size;
       }
 
       @Override public ListIterator<Entry<K, V>> listIterator(int index) {
         return new NodeIterator(index);
       }
     };
   }
 
   @Override
   Iterator<Entry<K, V>> entryIterator() {
     throw new AssertionError("should never be called");
   }
 
   @Override
   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 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;
 }