    001    /*
    002     * Copyright (C) 2007 The Guava Authors
    003     *
    004     * Licensed under the Apache License, Version 2.0 (the "License");
    005     * you may not use this file except in compliance with the License.
    006     * You may obtain a copy of the License at
    007     *
    008     * http://www.apache.org/licenses/LICENSE-2.0
    009     *
    010     * Unless required by applicable law or agreed to in writing, software
    011     * distributed under the License is distributed on an "AS IS" BASIS,
    012     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    013     * See the License for the specific language governing permissions and
    014     * limitations under the License.
    015     */
    016
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkArgument;
    020    import static com.google.common.base.Preconditions.checkNotNull;
    021    import static com.google.common.base.Preconditions.checkState;
    022    import static com.google.common.collect.Multisets.setCountImpl;
    023    import static java.util.Collections.unmodifiableList;
    024
    025    import com.google.common.annotations.GwtCompatible;
    026    import com.google.common.annotations.GwtIncompatible;
    027    import com.google.common.base.Objects;
    028    import com.google.common.base.Preconditions;
    029
    030    import java.io.IOException;
    031    import java.io.ObjectInputStream;
    032    import java.io.ObjectOutputStream;
    033    import java.io.Serializable;
    034    import java.util.AbstractCollection;
    035    import java.util.AbstractMap;
    036    import java.util.AbstractSequentialList;
    037    import java.util.AbstractSet;
    038    import java.util.Collection;
    039    import java.util.Iterator;
    040    import java.util.List;
    041    import java.util.ListIterator;
    042    import java.util.Map;
    043    import java.util.Map.Entry;
    044    import java.util.NoSuchElementException;
    045    import java.util.Set;
    046
    047    import javax.annotation.Nullable;
    048
    049    /**
    050     * An implementation of {@code ListMultimap} that supports deterministic
    051     * iteration order for both keys and values. The iteration order is preserved
    052     * across non-distinct key values. For example, for the following multimap
    053     * definition: <pre>   {@code
    054     *
    055     *   Multimap<K, V> multimap = LinkedListMultimap.create();
    056     *   multimap.put(key1, foo);
    057     *   multimap.put(key2, bar);
    058     *   multimap.put(key1, baz);}</pre>
    059     *
    060     * ... the iteration order for {@link #keys()} is {@code [key1, key2, key1]},
    061     * and similarly for {@link #entries()}. Unlike {@link LinkedHashMultimap}, the
    062     * iteration order is kept consistent between keys, entries and values. For
    063     * example, calling: <pre>   {@code
    064     *
    065     *   map.remove(key1, foo);}</pre>
    066     *
    067     * changes the entries iteration order to {@code [key2=bar, key1=baz]} and the
    068     * key iteration order to {@code [key2, key1]}. The {@link #entries()} iterator
    069     * returns mutable map entries, and {@link #replaceValues} attempts to preserve
    070     * iteration order as much as possible.
    071     *
    072     * <p>The collections returned by {@link #keySet()} and {@link #asMap} iterate
    073     * through the keys in the order they were first added to the multimap.
    074     * Similarly, {@link #get}, {@link #removeAll}, and {@link #replaceValues}
    075     * return collections that iterate through the values in the order they were
    076     * added. The collections generated by {@link #entries()}, {@link #keys()}, and
    077     * {@link #values} iterate across the key-value mappings in the order they were
    078     * added to the multimap.
    079     *
    080     * <p>The {@link #values()} and {@link #entries()} methods both return a
    081     * {@code List}, instead of the {@code Collection} specified by the {@link
    082     * ListMultimap} interface.
    083     *
    084     * <p>The methods {@link #get}, {@link #keySet()}, {@link #keys()},
    085     * {@link #values}, {@link #entries()}, and {@link #asMap} return collections
    086     * that are views of the multimap. If the multimap is modified while an
    087     * iteration over any of those collections is in progress, except through the
    088     * iterator's methods, the results of the iteration are undefined.
    089     *
    090     * <p>Keys and values may be null. All optional multimap methods are supported,
    091     * and all returned views are modifiable.
    092     *
    093     * <p>This class is not threadsafe when any concurrent operations update the
    094     * multimap. Concurrent read operations will work correctly. To allow concurrent
    095     * update operations, wrap your multimap with a call to {@link
    096     * Multimaps#synchronizedListMultimap}.
    097     *
    098     * @author Mike Bostock
    099     * @since 2.0 (imported from Google Collections Library)
    100     */
    101    @GwtCompatible(serializable = true, emulated = true)
    102    public class LinkedListMultimap<K, V>
    103        implements ListMultimap<K, V>, Serializable {
    104      /*
    105       * Order is maintained using a linked list containing all key-value pairs. In
    106       * addition, a series of disjoint linked lists of "siblings", each containing
    107       * the values for a specific key, is used to implement {@link
    108       * ValueForKeyIterator} in constant time.
    109       */
    110
    111      private static final class Node<K, V> {
    112        final K key;
    113        V value;
    114        Node<K, V> next; // the next node (with any key)
    115        Node<K, V> previous; // the previous node (with any key)
    116        Node<K, V> nextSibling; // the next node with the same key
    117        Node<K, V> previousSibling; // the previous node with the same key
    118
    119        Node(@Nullable K key, @Nullable V value) {
    120          this.key = key;
    121          this.value = value;
    122        }
    123
    124        @Override public String toString() {
    125          return key + "=" + value;
    126        }
    127      }
    128
    129      private transient Node<K, V> head; // the head for all keys
    130      private transient Node<K, V> tail; // the tail for all keys
    131      private transient Multiset<K> keyCount; // the number of values for each key
    132      private transient Map<K, Node<K, V>> keyToKeyHead; // the head for a given key
    133      private transient Map<K, Node<K, V>> keyToKeyTail; // the tail for a given key
    134
    135      /**
    136       * Creates a new, empty {@code LinkedListMultimap} with the default initial
    137       * capacity.
    138       */
    139      public static <K, V> LinkedListMultimap<K, V> create() {
    140        return new LinkedListMultimap<K, V>();
    141      }
    142
    143      /**
    144       * Constructs an empty {@code LinkedListMultimap} with enough capacity to hold
    145       * the specified number of keys without rehashing.
    146       *
    147       * @param expectedKeys the expected number of distinct keys
    148       * @throws IllegalArgumentException if {@code expectedKeys} is negative
    149       */
    150      public static <K, V> LinkedListMultimap<K, V> create(int expectedKeys) {
    151        return new LinkedListMultimap<K, V>(expectedKeys);
    152      }
    153
    154      /**
    155       * Constructs a {@code LinkedListMultimap} with the same mappings as the
    156       * specified {@code Multimap}. The new multimap has the same
    157       * {@link Multimap#entries()} iteration order as the input multimap.
    158       *
    159       * @param multimap the multimap whose contents are copied to this multimap
    160       */
    161      public static <K, V> LinkedListMultimap<K, V> create(
    162          Multimap<? extends K, ? extends V> multimap) {
    163        return new LinkedListMultimap<K, V>(multimap);
    164      }
    165
    166      LinkedListMultimap() {
    167        keyCount = LinkedHashMultiset.create();
    168        keyToKeyHead = Maps.newHashMap();
    169        keyToKeyTail = Maps.newHashMap();
    170      }
    171
    172      private LinkedListMultimap(int expectedKeys) {
    173        keyCount = LinkedHashMultiset.create(expectedKeys);
    174        keyToKeyHead = Maps.newHashMapWithExpectedSize(expectedKeys);
    175        keyToKeyTail = Maps.newHashMapWithExpectedSize(expectedKeys);
    176      }
    177
    178      private LinkedListMultimap(Multimap<? extends K, ? extends V> multimap) {
    179        this(multimap.keySet().size());
    180        putAll(multimap);
    181      }
    182
    183      /**
    184       * Adds a new node for the specified key-value pair before the specified
    185       * {@code nextSibling} element, or at the end of the list if {@code
    186       * nextSibling} is null. Note: if {@code nextSibling} is specified, it MUST be
    187       * for an node for the same {@code key}!
    188       */
    189      private Node<K, V> addNode(
    190          @Nullable K key, @Nullable V value, @Nullable Node<K, V> nextSibling) {
    191        Node<K, V> node = new Node<K, V>(key, value);
    192        if (head == null) { // empty list
    193          head = tail = node;
    194          keyToKeyHead.put(key, node);
    195          keyToKeyTail.put(key, node);
    196        } else if (nextSibling == null) { // non-empty list, add to tail
    197          tail.next = node;
    198          node.previous = tail;
    199          Node<K, V> keyTail = keyToKeyTail.get(key);
    200          if (keyTail == null) { // first for this key
    201            keyToKeyHead.put(key, node);
    202          } else {
    203            keyTail.nextSibling = node;
    204            node.previousSibling = keyTail;
    205          }
    206          keyToKeyTail.put(key, node);
    207          tail = node;
    208        } else { // non-empty list, insert before nextSibling
    209          node.previous = nextSibling.previous;
    210          node.previousSibling = nextSibling.previousSibling;
    211          node.next = nextSibling;
    212          node.nextSibling = nextSibling;
    213          if (nextSibling.previousSibling == null) { // nextSibling was key head
    214            keyToKeyHead.put(key, node);
    215          } else {
    216            nextSibling.previousSibling.nextSibling = node;
    217          }
    218          if (nextSibling.previous == null) { // nextSibling was head
    219            head = node;
    220          } else {
    221            nextSibling.previous.next = node;
    222          }
    223          nextSibling.previous = node;
    224          nextSibling.previousSibling = node;
    225        }
    226        keyCount.add(key);
    227        return node;
    228      }
    229
    230      /**
    231       * Removes the specified node from the linked list. This method is only
    232       * intended to be used from the {@code Iterator} classes. See also {@link
    233       * LinkedListMultimap#removeAllNodes(Object)}.
    234       */
    235      private void removeNode(Node<K, V> node) {
    236        if (node.previous != null) {
    237          node.previous.next = node.next;
    238        } else { // node was head
    239          head = node.next;
    240        }
    241        if (node.next != null) {
    242          node.next.previous = node.previous;
    243        } else { // node was tail
    244          tail = node.previous;
    245        }
    246        if (node.previousSibling != null) {
    247          node.previousSibling.nextSibling = node.nextSibling;
    248        } else if (node.nextSibling != null) { // node was key head
    249          keyToKeyHead.put(node.key, node.nextSibling);
    250        } else {
    251          keyToKeyHead.remove(node.key); // don't leak a key-null entry
    252        }
    253        if (node.nextSibling != null) {
    254          node.nextSibling.previousSibling = node.previousSibling;
    255        } else if (node.previousSibling != null) { // node was key tail
    256          keyToKeyTail.put(node.key, node.previousSibling);
    257        } else {
    258          keyToKeyTail.remove(node.key); // don't leak a key-null entry
    259        }
    260        keyCount.remove(node.key);
    261      }
    262
    263      /** Removes all nodes for the specified key. */
    264      private void removeAllNodes(@Nullable Object key) {
    265        for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) {
    266          i.next();
    267          i.remove();
    268        }
    269      }
    270
    271      /** Helper method for verifying that an iterator element is present. */
    272      private static void checkElement(@Nullable Object node) {
    273        if (node == null) {
    274          throw new NoSuchElementException();
    275        }
    276      }
    277
    278      /** An {@code Iterator} over all nodes. */
    279      private class NodeIterator implements ListIterator<Node<K, V>> {
    280        int nextIndex;
    281        Node<K, V> next;
    282        Node<K, V> current;
    283        Node<K, V> previous;
    284
    285        NodeIterator() {
    286          next = head;
    287        }
    288        NodeIterator(int index) {
    289          int size = size();
    290          Preconditions.checkPositionIndex(index, size);
    291          if (index >= (size / 2)) {
    292            previous = tail;
    293            nextIndex = size;
    294            while (index++ < size) {
    295              previous();
    296            }
    297          } else {
    298            next = head;
    299            while (index-- > 0) {
    300              next();
    301            }
    302          }
    303          current = null;
    304        }
    305        @Override
    306        public boolean hasNext() {
    307          return next != null;
    308        }
    309        @Override
    310        public Node<K, V> next() {
    311          checkElement(next);
    312          previous = current = next;
    313          next = next.next;
    314          nextIndex++;
    315          return current;
    316        }
    317        @Override
    318        public void remove() {
    319          checkState(current != null);
    320          if (current != next) { // after call to next()
    321            previous = current.previous;
    322            nextIndex--;
    323          } else { // after call to previous()
    324            next = current.next;
    325          }
    326          removeNode(current);
    327          current = null;
    328        }
    329        @Override
    330        public boolean hasPrevious() {
    331          return previous != null;
    332        }
    333        @Override
    334        public Node<K, V> previous() {
    335          checkElement(previous);
    336          next = current = previous;
    337          previous = previous.previous;
    338          nextIndex--;
    339          return current;
    340        }
    341        @Override
    342        public int nextIndex() {
    343          return nextIndex;
    344        }
    345        @Override
    346        public int previousIndex() {
    347          return nextIndex - 1;
    348        }
    349        @Override
    350        public void set(Node<K, V> e) {
    351          throw new UnsupportedOperationException();
    352        }
    353        @Override
    354        public void add(Node<K, V> e) {
    355          throw new UnsupportedOperationException();
    356        }
    357        void setValue(V value) {
    358          checkState(current != null);
    359          current.value = value;
    360        }
    361      }
    362
    363      /** An {@code Iterator} over distinct keys in key head order. */
    364      private class DistinctKeyIterator implements Iterator<K> {
    365        final Set<K> seenKeys = Sets.<K>newHashSetWithExpectedSize(keySet().size());
    366        Node<K, V> next = head;
    367        Node<K, V> current;
    368
    369        @Override
    370        public boolean hasNext() {
    371          return next != null;
    372        }
    373        @Override
    374        public K next() {
    375          checkElement(next);
    376          current = next;
    377          seenKeys.add(current.key);
    378          do { // skip ahead to next unseen key
    379            next = next.next;
    380          } while ((next != null) && !seenKeys.add(next.key));
    381          return current.key;
    382        }
    383        @Override
    384        public void remove() {
    385          checkState(current != null);
    386          removeAllNodes(current.key);
    387          current = null;
    388        }
    389      }
    390
    391      /** A {@code ListIterator} over values for a specified key. */
    392      private class ValueForKeyIterator implements ListIterator<V> {
    393        final Object key;
    394        int nextIndex;
    395        Node<K, V> next;
    396        Node<K, V> current;
    397        Node<K, V> previous;
    398
    399        /** Constructs a new iterator over all values for the specified key. */
    400        ValueForKeyIterator(@Nullable Object key) {
    401          this.key = key;
    402          next = keyToKeyHead.get(key);
    403        }
    404
    405        /**
    406         * Constructs a new iterator over all values for the specified key starting
    407         * at the specified index. This constructor is optimized so that it starts
    408         * at either the head or the tail, depending on which is closer to the
    409         * specified index. This allows adds to the tail to be done in constant
    410         * time.
    411         *
    412         * @throws IndexOutOfBoundsException if index is invalid
    413         */
    414        public ValueForKeyIterator(@Nullable Object key, int index) {
    415          int size = keyCount.count(key);
    416          Preconditions.checkPositionIndex(index, size);
    417          if (index >= (size / 2)) {
    418            previous = keyToKeyTail.get(key);
    419            nextIndex = size;
    420            while (index++ < size) {
    421              previous();
    422            }
    423          } else {
    424            next = keyToKeyHead.get(key);
    425            while (index-- > 0) {
    426              next();
    427            }
    428          }
    429          this.key = key;
    430          current = null;
    431        }
    432
    433        @Override
    434        public boolean hasNext() {
    435          return next != null;
    436        }
    437
    438        @Override
    439        public V next() {
    440          checkElement(next);
    441          previous = current = next;
    442          next = next.nextSibling;
    443          nextIndex++;
    444          return current.value;
    445        }
    446
    447        @Override
    448        public boolean hasPrevious() {
    449          return previous != null;
    450        }
    451
    452        @Override
    453        public V previous() {
    454          checkElement(previous);
    455          next = current = previous;
    456          previous = previous.previousSibling;
    457          nextIndex--;
    458          return current.value;
    459        }
    460
    461        @Override
    462        public int nextIndex() {
    463          return nextIndex;
    464        }
    465
    466        @Override
    467        public int previousIndex() {
    468          return nextIndex - 1;
    469        }
    470
    471        @Override
    472        public void remove() {
    473          checkState(current != null);
    474          if (current != next) { // after call to next()
    475            previous = current.previousSibling;
    476            nextIndex--;
    477          } else { // after call to previous()
    478            next = current.nextSibling;
    479          }
    480          removeNode(current);
    481          current = null;
    482        }
    483
    484        @Override
    485        public void set(V value) {
    486          checkState(current != null);
    487          current.value = value;
    488        }
    489
    490        @Override
    491        @SuppressWarnings("unchecked")
    492        public void add(V value) {
    493          previous = addNode((K) key, value, next);
    494          nextIndex++;
    495          current = null;
    496        }
    497      }
    498
    499      // Query Operations
    500
    501      @Override
    502      public int size() {
    503        return keyCount.size();
    504      }
    505
    506      @Override
    507      public boolean isEmpty() {
    508        return head == null;
    509      }
    510
    511      @Override
    512      public boolean containsKey(@Nullable Object key) {
    513        return keyToKeyHead.containsKey(key);
    514      }
    515
    516      @Override
    517      public boolean containsValue(@Nullable Object value) {
    518        for (Iterator<Node<K, V>> i = new NodeIterator(); i.hasNext();) {
    519          if (Objects.equal(i.next().value, value)) {
    520            return true;
    521          }
    522        }
    523        return false;
    524      }
    525
    526      @Override
    527      public boolean containsEntry(@Nullable Object key, @Nullable Object value) {
    528        for (Iterator<V> i = new ValueForKeyIterator(key); i.hasNext();) {
    529          if (Objects.equal(i.next(), value)) {
    530            return true;
    531          }
    532        }
    533        return false;
    534      }
    535
    536      // Modification Operations
    537
    538      /**
    539       * Stores a key-value pair in the multimap.
    540       *
    541       * @param key key to store in the multimap
    542       * @param value value to store in the multimap
    543       * @return {@code true} always
    544       */
    545      @Override
    546      public boolean put(@Nullable K key, @Nullable V value) {
    547        addNode(key, value, null);
    548        return true;
    549      }
    550
    551      @Override
    552      public boolean remove(@Nullable Object key, @Nullable Object value) {
    553        Iterator<V> values = new ValueForKeyIterator(key);
    554        while (values.hasNext()) {
    555          if (Objects.equal(values.next(), value)) {
    556            values.remove();
    557            return true;
    558          }
    559        }
    560        return false;
    561      }
    562
    563      // Bulk Operations
    564
    565      @Override
    566      public boolean putAll(@Nullable K key, Iterable<? extends V> values) {
    567        boolean changed = false;
    568        for (V value : values) {
    569          changed |= put(key, value);
    570        }
    571        return changed;
    572      }
    573
    574      @Override
    575      public boolean putAll(Multimap<? extends K, ? extends V> multimap) {
    576        boolean changed = false;
    577        for (Entry<? extends K, ? extends V> entry : multimap.entries()) {
    578          changed |= put(entry.getKey(), entry.getValue());
    579        }
    580        return changed;
    581      }
    582
    583      /**
    584       * {@inheritDoc}
    585       *
    586       * <p>If any entries for the specified {@code key} already exist in the
    587       * multimap, their values are changed in-place without affecting the iteration
    588       * order.
    589       *
    590       * <p>The returned list is immutable and implements
    591       * {@link java.util.RandomAccess}.
    592       */
    593      @Override
    594      public List<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
    595        List<V> oldValues = getCopy(key);
    596        ListIterator<V> keyValues = new ValueForKeyIterator(key);
    597        Iterator<? extends V> newValues = values.iterator();
    598
    599        // Replace existing values, if any.
    600        while (keyValues.hasNext() && newValues.hasNext()) {
    601          keyValues.next();
    602          keyValues.set(newValues.next());
    603        }
    604
    605        // Remove remaining old values, if any.
    606        while (keyValues.hasNext()) {
    607          keyValues.next();
    608          keyValues.remove();
    609        }
    610
    611        // Add remaining new values, if any.
    612        while (newValues.hasNext()) {
    613          keyValues.add(newValues.next());
    614        }
    615
    616        return oldValues;
    617      }
    618
    619      private List<V> getCopy(@Nullable Object key) {
    620        return unmodifiableList(Lists.newArrayList(new ValueForKeyIterator(key)));
    621      }
    622
    623      /**
    624       * {@inheritDoc}
    625       *
    626       * <p>The returned list is immutable and implements
    627       * {@link java.util.RandomAccess}.
    628       */
    629      @Override
    630      public List<V> removeAll(@Nullable Object key) {
    631        List<V> oldValues = getCopy(key);
    632        removeAllNodes(key);
    633        return oldValues;
    634      }
    635
    636      @Override
    637      public void clear() {
    638        head = null;
    639        tail = null;
    640        keyCount.clear();
    641        keyToKeyHead.clear();
    642        keyToKeyTail.clear();
    643      }
    644
    645      // Views
    646
    647      /**
    648       * {@inheritDoc}
    649       *
    650       * <p>If the multimap is modified while an iteration over the list is in
    651       * progress (except through the iterator's own {@code add}, {@code set} or
    652       * {@code remove} operations) the results of the iteration are undefined.
    653       *
    654       * <p>The returned list is not serializable and does not have random access.
    655       */
    656      @Override
    657      public List<V> get(final @Nullable K key) {
    658        return new AbstractSequentialList<V>() {
    659          @Override public int size() {
    660            return keyCount.count(key);
    661          }
    662          @Override public ListIterator<V> listIterator(int index) {
    663            return new ValueForKeyIterator(key, index);
    664          }
    665          @Override public boolean removeAll(Collection<?> c) {
    666            return Iterators.removeAll(iterator(), c);
    667          }
    668          @Override public boolean retainAll(Collection<?> c) {
    669            return Iterators.retainAll(iterator(), c);
    670          }
    671        };
    672      }
    673
    674      private transient Set<K> keySet;
    675
    676      @Override
    677      public Set<K> keySet() {
    678        Set<K> result = keySet;
    679        if (result == null) {
    680          keySet = result = new AbstractSet<K>() {
    681            @Override public int size() {
    682              return keyCount.elementSet().size();
    683            }
    684            @Override public Iterator<K> iterator() {
    685              return new DistinctKeyIterator();
    686            }
    687            @Override public boolean contains(Object key) { // for performance
    688              return keyCount.contains(key);
    689            }
    690            @Override public boolean removeAll(Collection<?> c) {
    691              checkNotNull(c); // eager for GWT
    692              return super.removeAll(c);
    693            }
    694          };
    695        }
    696        return result;
    697      }
    698
    699      private transient Multiset<K> keys;
    700
    701      @Override
    702      public Multiset<K> keys() {
    703        Multiset<K> result = keys;
    704        if (result == null) {
    705          keys = result = new MultisetView();
    706        }
    707        return result;
    708      }
    709
    710      private class MultisetView extends AbstractCollection<K>
    711          implements Multiset<K> {
    712
    713        @Override public int size() {
    714          return keyCount.size();
    715        }
    716
    717        @Override public Iterator<K> iterator() {
    718          final Iterator<Node<K, V>> nodes = new NodeIterator();
    719          return new Iterator<K>() {
    720            @Override
    721            public boolean hasNext() {
    722              return nodes.hasNext();
    723            }
    724            @Override
    725            public K next() {
    726              return nodes.next().key;
    727            }
    728            @Override
    729            public void remove() {
    730              nodes.remove();
    731            }
    732          };
    733        }
    734
    735        @Override
    736        public int count(@Nullable Object key) {
    737          return keyCount.count(key);
    738        }
    739
    740        @Override
    741        public int add(@Nullable K key, int occurrences) {
    742          throw new UnsupportedOperationException();
    743        }
    744
    745        @Override
    746        public int remove(@Nullable Object key, int occurrences) {
    747          checkArgument(occurrences >= 0);
    748          int oldCount = count(key);
    749          Iterator<V> values = new ValueForKeyIterator(key);
    750          while ((occurrences-- > 0) && values.hasNext()) {
    751            values.next();
    752            values.remove();
    753          }
    754          return oldCount;
    755        }
    756
    757        @Override
    758        public int setCount(K element, int count) {
    759          return setCountImpl(this, element, count);
    760        }
    761
    762        @Override
    763        public boolean setCount(K element, int oldCount, int newCount) {
    764          return setCountImpl(this, element, oldCount, newCount);
    765        }
    766
    767        @Override public boolean removeAll(Collection<?> c) {
    768          return Iterators.removeAll(iterator(), c);
    769        }
    770
    771        @Override public boolean retainAll(Collection<?> c) {
    772          return Iterators.retainAll(iterator(), c);
    773        }
    774
    775        @Override
    776        public Set<K> elementSet() {
    777          return keySet();
    778        }
    779
    780        @Override
    781        public Set<Entry<K>> entrySet() {
    782          // TODO(jlevy): lazy init?
    783          return new AbstractSet<Entry<K>>() {
    784            @Override public int size() {
    785              return keyCount.elementSet().size();
    786            }
    787
    788            @Override public Iterator<Entry<K>> iterator() {
    789              final Iterator<K> keyIterator = new DistinctKeyIterator();
    790              return new Iterator<Entry<K>>() {
    791                @Override
    792                public boolean hasNext() {
    793                  return keyIterator.hasNext();
    794                }
    795                @Override
    796                public Entry<K> next() {
    797                  final K key = keyIterator.next();
    798                  return new Multisets.AbstractEntry<K>() {
    799                    @Override
    800                    public K getElement() {
    801                      return key;
    802                    }
    803                    @Override
    804                    public int getCount() {
    805                      return keyCount.count(key);
    806                    }
    807                  };
    808                }
    809                @Override
    810                public void remove() {
    811                  keyIterator.remove();
    812                }
    813              };
    814            }
    815          };
    816        }
    817
    818        @Override public boolean equals(@Nullable Object object) {
    819          return keyCount.equals(object);
    820        }
    821
    822        @Override public int hashCode() {
    823          return keyCount.hashCode();
    824        }
    825
    826        @Override public String toString() {
    827          return keyCount.toString(); // XXX observe order?
    828        }
    829      }
    830
    831      private transient List<V> valuesList;
    832
    833      /**
    834       * {@inheritDoc}
    835       *
    836       * <p>The iterator generated by the returned collection traverses the values
    837       * in the order they were added to the multimap. Because the values may have
    838       * duplicates and follow the insertion ordering, this method returns a {@link
    839       * List}, instead of the {@link Collection} specified in the {@link
    840       * ListMultimap} interface.
    841       */
    842      @Override
    843      public List<V> values() {
    844        List<V> result = valuesList;
    845        if (result == null) {
    846          valuesList = result = new AbstractSequentialList<V>() {
    847            @Override public int size() {
    848              return keyCount.size();
    849            }
    850            @Override
    851            public ListIterator<V> listIterator(int index) {
    852              final NodeIterator nodes = new NodeIterator(index);
    853              return new ListIterator<V>() {
    854                @Override
    855                public boolean hasNext() {
    856                  return nodes.hasNext();
    857                }
    858                @Override
    859                public V next() {
    860                  return nodes.next().value;
    861                }
    862                @Override
    863                public boolean hasPrevious() {
    864                  return nodes.hasPrevious();
    865                }
    866                @Override
    867                public V previous() {
    868                  return nodes.previous().value;
    869                }
    870                @Override
    871                public int nextIndex() {
    872                  return nodes.nextIndex();
    873                }
    874                @Override
    875                public int previousIndex() {
    876                  return nodes.previousIndex();
    877                }
    878                @Override
    879                public void remove() {
    880                  nodes.remove();
    881                }
    882                @Override
    883                public void set(V e) {
    884                  nodes.setValue(e);
    885                }
    886                @Override
    887                public void add(V e) {
    888                  throw new UnsupportedOperationException();
    889                }
    890              };
    891            }
    892          };
    893        }
    894        return result;
    895      }
    896
    897      private static <K, V> Entry<K, V> createEntry(final Node<K, V> node) {
    898        return new AbstractMapEntry<K, V>() {
    899          @Override public K getKey() {
    900            return node.key;
    901          }
    902          @Override public V getValue() {
    903            return node.value;
    904          }
    905          @Override public V setValue(V value) {
    906            V oldValue = node.value;
    907            node.value = value;
    908            return oldValue;
    909          }
    910        };
    911      }
    912
    913      private transient List<Entry<K, V>> entries;
    914
    915      /**
    916       * {@inheritDoc}
    917       *
    918       * <p>The iterator generated by the returned collection traverses the entries
    919       * in the order they were added to the multimap. Because the entries may have
    920       * duplicates and follow the insertion ordering, this method returns a {@link
    921       * List}, instead of the {@link Collection} specified in the {@link
    922       * ListMultimap} interface.
    923       *
    924       * <p>An entry's {@link Entry#getKey} method always returns the same key,
    925       * regardless of what happens subsequently. As long as the corresponding
    926       * key-value mapping is not removed from the multimap, {@link Entry#getValue}
    927       * returns the value from the multimap, which may change over time, and {@link
    928       * Entry#setValue} modifies that value. Removing the mapping from the
    929       * multimap does not alter the value returned by {@code getValue()}, though a
    930       * subsequent {@code setValue()} call won't update the multimap but will lead
    931       * to a revised value being returned by {@code getValue()}.
    932       */
    933      @Override
    934      public List<Entry<K, V>> entries() {
    935        List<Entry<K, V>> result = entries;
    936        if (result == null) {
    937          entries = result = new AbstractSequentialList<Entry<K, V>>() {
    938            @Override public int size() {
    939              return keyCount.size();
    940            }
    941
    942            @Override public ListIterator<Entry<K, V>> listIterator(int index) {
    943              final ListIterator<Node<K, V>> nodes = new NodeIterator(index);
    944              return new ListIterator<Entry<K, V>>() {
    945                @Override
    946                public boolean hasNext() {
    947                  return nodes.hasNext();
    948                }
    949
    950                @Override
    951                public Entry<K, V> next() {
    952                  return createEntry(nodes.next());
    953                }
    954
    955                @Override
    956                public void remove() {
    957                  nodes.remove();
    958                }
    959
    960                @Override
    961                public boolean hasPrevious() {
    962                  return nodes.hasPrevious();
    963                }
    964
    965                @Override
    966                public Map.Entry<K, V> previous() {
    967                  return createEntry(nodes.previous());
    968                }
    969
    970                @Override
    971                public int nextIndex() {
    972                  return nodes.nextIndex();
    973                }
    974
    975                @Override
    976                public int previousIndex() {
    977                  return nodes.previousIndex();
    978                }
    979
    980                @Override
    981                public void set(Map.Entry<K, V> e) {
    982                  throw new UnsupportedOperationException();
    983                }
    984
    985                @Override
    986                public void add(Map.Entry<K, V> e) {
    987                  throw new UnsupportedOperationException();
    988                }
    989              };
    990            }
    991          };
    992        }
    993        return result;
    994      }
    995
    996      private class AsMapEntries extends AbstractSet<Entry<K, Collection<V>>> {
    997        @Override public int size() {
    998          return keyCount.elementSet().size();
    999        }
    1000
    1001        @Override public Iterator<Entry<K, Collection<V>>> iterator() {
    1002          final Iterator<K> keyIterator = new DistinctKeyIterator();
    1003          return new Iterator<Entry<K, Collection<V>>>() {
    1004            @Override
    1005            public boolean hasNext() {
    1006              return keyIterator.hasNext();
    1007            }
    1008
    1009            @Override
    1010            public Entry<K, Collection<V>> next() {
    1011              final K key = keyIterator.next();
    1012              return new AbstractMapEntry<K, Collection<V>>() {
    1013                @Override public K getKey() {
    1014                  return key;
    1015                }
    1016
    1017                @Override public Collection<V> getValue() {
    1018                  return LinkedListMultimap.this.get(key);
    1019                }
    1020              };
    1021            }
    1022
    1023            @Override
    1024            public void remove() {
    1025              keyIterator.remove();
    1026            }
    1027          };
    1028        }
    1029
    1030        // TODO(jlevy): Override contains() and remove() for better performance.
    1031      }
    1032
    1033      private transient Map<K, Collection<V>> map;
    1034
    1035      @Override
    1036      public Map<K, Collection<V>> asMap() {
    1037        Map<K, Collection<V>> result = map;
    1038        if (result == null) {
    1039          map = result = new AbstractMap<K, Collection<V>>() {
    1040            Set<Entry<K, Collection<V>>> entrySet;
    1041
    1042            @Override public Set<Entry<K, Collection<V>>> entrySet() {
    1043              Set<Entry<K, Collection<V>>> result = entrySet;
    1044              if (result == null) {
    1045                entrySet = result = new AsMapEntries();
    1046              }
    1047              return result;
    1048            }
    1049
    1050            // The following methods are included for performance.
    1051
    1052            @Override public boolean containsKey(@Nullable Object key) {
    1053              return LinkedListMultimap.this.containsKey(key);
    1054            }
    1055
    1056            @SuppressWarnings("unchecked")
    1057            @Override public Collection<V> get(@Nullable Object key) {
    1058              Collection<V> collection = LinkedListMultimap.this.get((K) key);
    1059              return collection.isEmpty() ? null : collection;
    1060            }
    1061
    1062            @Override public Collection<V> remove(@Nullable Object key) {
    1063              Collection<V> collection = removeAll(key);
    1064              return collection.isEmpty() ? null : collection;
    1065            }
    1066          };
    1067        }
    1068
    1069        return result;
    1070      }
    1071
    1072      // Comparison and hashing
    1073
    1074      /**
    1075       * Compares the specified object to this multimap for equality.
    1076       *
    1077       * <p>Two {@code ListMultimap} instances are equal if, for each key, they
    1078       * contain the same values in the same order. If the value orderings disagree,
    1079       * the multimaps will not be considered equal.
    1080       */
    1081      @Override public boolean equals(@Nullable Object other) {
    1082        if (other == this) {
    1083          return true;
    1084        }
    1085        if (other instanceof Multimap) {
    1086          Multimap<?, ?> that = (Multimap<?, ?>) other;
    1087          return this.asMap().equals(that.asMap());
    1088        }
    1089        return false;
    1090      }
    1091
    1092      /**
    1093       * Returns the hash code for this multimap.
    1094       *
    1095       * <p>The hash code of a multimap is defined as the hash code of the map view,
    1096       * as returned by {@link Multimap#asMap}.
    1097       */
    1098      @Override public int hashCode() {
    1099        return asMap().hashCode();
    1100      }
    1101
    1102      /**
    1103       * Returns a string representation of the multimap, generated by calling
    1104       * {@code toString} on the map returned by {@link Multimap#asMap}.
    1105       *
    1106       * @return a string representation of the multimap
    1107       */
    1108      @Override public String toString() {
    1109        return asMap().toString();
    1110      }
    1111
    1112      /**
    1113       * @serialData the number of distinct keys, and then for each distinct key:
    1114       *     the first key, the number of values for that key, and the key's values,
    1115       *     followed by successive keys and values from the entries() ordering
    1116       */
    1117      @GwtIncompatible("java.io.ObjectOutputStream")
    1118      private void writeObject(ObjectOutputStream stream) throws IOException {
    1119        stream.defaultWriteObject();
    1120        stream.writeInt(size());
    1121        for (Entry<K, V> entry : entries()) {
    1122          stream.writeObject(entry.getKey());
    1123          stream.writeObject(entry.getValue());
    1124        }
    1125      }
    1126
    1127      @GwtIncompatible("java.io.ObjectInputStream")
    1128      private void readObject(ObjectInputStream stream)
    1129          throws IOException, ClassNotFoundException {
    1130        stream.defaultReadObject();
    1131        keyCount = LinkedHashMultiset.create();
    1132        keyToKeyHead = Maps.newHashMap();
    1133        keyToKeyTail = Maps.newHashMap();
    1134        int size = stream.readInt();
    1135        for (int i = 0; i < size; i++) {
    1136          @SuppressWarnings("unchecked") // reading data stored by writeObject
    1137          K key = (K) stream.readObject();
    1138          @SuppressWarnings("unchecked") // reading data stored by writeObject
    1139          V value = (V) stream.readObject();
    1140          put(key, value);
    1141        }
    1142      }
    1143
    1144      @GwtIncompatible("java serialization not supported")
    1145      private static final long serialVersionUID = 0;
    1146    }