    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 com.google.common.annotations.GwtCompatible;
    020    import com.google.common.annotations.GwtIncompatible;
    021    import com.google.common.annotations.VisibleForTesting;
    022    import com.google.common.base.Preconditions;
    023    import com.google.common.primitives.Ints;
    024
    025    import java.io.IOException;
    026    import java.io.ObjectInputStream;
    027    import java.io.ObjectOutputStream;
    028    import java.util.Collection;
    029    import java.util.Iterator;
    030    import java.util.LinkedHashMap;
    031    import java.util.LinkedHashSet;
    032    import java.util.Map;
    033    import java.util.Set;
    034
    035    import javax.annotation.Nullable;
    036
    037    /**
    038     * Implementation of {@code Multimap} that does not allow duplicate key-value
    039     * entries and that returns collections whose iterators follow the ordering in
    040     * which the data was added to the multimap.
    041     *
    042     * <p>The collections returned by {@code keySet}, {@code keys}, and {@code
    043     * asMap} iterate through the keys in the order they were first added to the
    044     * multimap. Similarly, {@code get}, {@code removeAll}, and {@code
    045     * replaceValues} return collections that iterate through the values in the
    046     * order they were added. The collections generated by {@code entries} and
    047     * {@code values} iterate across the key-value mappings in the order they were
    048     * added to the multimap.
    049     *
    050     * <p>The iteration ordering of the collections generated by {@code keySet},
    051     * {@code keys}, and {@code asMap} has a few subtleties. As long as the set of
    052     * keys remains unchanged, adding or removing mappings does not affect the key
    053     * iteration order. However, if you remove all values associated with a key and
    054     * then add the key back to the multimap, that key will come last in the key
    055     * iteration order.
    056     *
    057     * <p>The multimap does not store duplicate key-value pairs. Adding a new
    058     * key-value pair equal to an existing key-value pair has no effect.
    059     *
    060     * <p>Keys and values may be null. All optional multimap methods are supported,
    061     * and all returned views are modifiable.
    062     *
    063     * <p>This class is not threadsafe when any concurrent operations update the
    064     * multimap. Concurrent read operations will work correctly. To allow concurrent
    065     * update operations, wrap your multimap with a call to {@link
    066     * Multimaps#synchronizedSetMultimap}.
    067     *
    068     * @author Jared Levy
    069     * @since 2.0 (imported from Google Collections Library)
    070     */
    071    @GwtCompatible(serializable = true, emulated = true)
    072    public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> {
    073      private static final int DEFAULT_VALUES_PER_KEY = 8;
    074
    075      @VisibleForTesting
    076      transient int expectedValuesPerKey = DEFAULT_VALUES_PER_KEY;
    077
    078      /**
    079       * Map entries with an iteration order corresponding to the order in which the
    080       * key-value pairs were added to the multimap.
    081       */
    082      // package-private for GWT deserialization
    083      transient Collection<Map.Entry<K, V>> linkedEntries;
    084
    085      /**
    086       * Creates a new, empty {@code LinkedHashMultimap} with the default initial
    087       * capacities.
    088       */
    089      public static <K, V> LinkedHashMultimap<K, V> create() {
    090        return new LinkedHashMultimap<K, V>();
    091      }
    092
    093      /**
    094       * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold
    095       * the specified numbers of keys and values without rehashing.
    096       *
    097       * @param expectedKeys the expected number of distinct keys
    098       * @param expectedValuesPerKey the expected average number of values per key
    099       * @throws IllegalArgumentException if {@code expectedKeys} or {@code
    100       *      expectedValuesPerKey} is negative
    101       */
    102      public static <K, V> LinkedHashMultimap<K, V> create(
    103          int expectedKeys, int expectedValuesPerKey) {
    104        return new LinkedHashMultimap<K, V>(expectedKeys, expectedValuesPerKey);
    105      }
    106
    107      /**
    108       * Constructs a {@code LinkedHashMultimap} with the same mappings as the
    109       * specified multimap. If a key-value mapping appears multiple times in the
    110       * input multimap, it only appears once in the constructed multimap. The new
    111       * multimap has the same {@link Multimap#entries()} iteration order as the
    112       * input multimap, except for excluding duplicate mappings.
    113       *
    114       * @param multimap the multimap whose contents are copied to this multimap
    115       */
    116      public static <K, V> LinkedHashMultimap<K, V> create(
    117          Multimap<? extends K, ? extends V> multimap) {
    118        return new LinkedHashMultimap<K, V>(multimap);
    119      }
    120
    121      private LinkedHashMultimap() {
    122        super(new LinkedHashMap<K, Collection<V>>());
    123        linkedEntries = Sets.newLinkedHashSet();
    124      }
    125
    126      private LinkedHashMultimap(int expectedKeys, int expectedValuesPerKey) {
    127        super(new LinkedHashMap<K, Collection<V>>(expectedKeys));
    128        Preconditions.checkArgument(expectedValuesPerKey >= 0);
    129        this.expectedValuesPerKey = expectedValuesPerKey;
    130        linkedEntries = new LinkedHashSet<Map.Entry<K, V>>(
    131            (int) Math.min(Ints.MAX_POWER_OF_TWO,
    132                ((long) expectedKeys) * expectedValuesPerKey));
    133      }
    134
    135      private LinkedHashMultimap(Multimap<? extends K, ? extends V> multimap) {
    136        super(new LinkedHashMap<K, Collection<V>>(
    137            Maps.capacity(multimap.keySet().size())));
    138        linkedEntries
    139            = new LinkedHashSet<Map.Entry<K, V>>(Maps.capacity(multimap.size()));
    140        putAll(multimap);
    141      }
    142
    143      /**
    144       * {@inheritDoc}
    145       *
    146       * <p>Creates an empty {@code LinkedHashSet} for a collection of values for
    147       * one key.
    148       *
    149       * @return a new {@code LinkedHashSet} containing a collection of values for
    150       *     one key
    151       */
    152      @Override Set<V> createCollection() {
    153        return new LinkedHashSet<V>(Maps.capacity(expectedValuesPerKey));
    154      }
    155
    156      /**
    157       * {@inheritDoc}
    158       *
    159       * <p>Creates a decorated {@code LinkedHashSet} that also keeps track of the
    160       * order in which key-value pairs are added to the multimap.
    161       *
    162       * @param key key to associate with values in the collection
    163       * @return a new decorated {@code LinkedHashSet} containing a collection of
    164       *     values for one key
    165       */
    166      @Override Collection<V> createCollection(@Nullable K key) {
    167        return new SetDecorator(key, createCollection());
    168      }
    169
    170      private class SetDecorator extends ForwardingSet<V> {
    171        final Set<V> delegate;
    172        final K key;
    173
    174        SetDecorator(@Nullable K key, Set<V> delegate) {
    175          this.delegate = delegate;
    176          this.key = key;
    177        }
    178
    179        @Override protected Set<V> delegate() {
    180          return delegate;
    181        }
    182
    183        <E> Map.Entry<K, E> createEntry(@Nullable E value) {
    184          return Maps.immutableEntry(key, value);
    185        }
    186
    187        <E> Collection<Map.Entry<K, E>> createEntries(Collection<E> values) {
    188          // converts a collection of values into a list of key/value map entries
    189          Collection<Map.Entry<K, E>> entries
    190              = Lists.newArrayListWithExpectedSize(values.size());
    191          for (E value : values) {
    192            entries.add(createEntry(value));
    193          }
    194          return entries;
    195        }
    196
    197        @Override public boolean add(@Nullable V value) {
    198          boolean changed = delegate.add(value);
    199          if (changed) {
    200            linkedEntries.add(createEntry(value));
    201          }
    202          return changed;
    203        }
    204
    205        @Override public boolean addAll(Collection<? extends V> values) {
    206          boolean changed = delegate.addAll(values);
    207          if (changed) {
    208            linkedEntries.addAll(createEntries(delegate()));
    209          }
    210          return changed;
    211        }
    212
    213        @Override public void clear() {
    214          for (V value : delegate) {
    215            linkedEntries.remove(createEntry(value));
    216          }
    217          delegate.clear();
    218        }
    219
    220        @Override public Iterator<V> iterator() {
    221          final Iterator<V> delegateIterator = delegate.iterator();
    222          return new Iterator<V>() {
    223            V value;
    224
    225            @Override
    226            public boolean hasNext() {
    227              return delegateIterator.hasNext();
    228            }
    229            @Override
    230            public V next() {
    231              value = delegateIterator.next();
    232              return value;
    233            }
    234            @Override
    235            public void remove() {
    236              delegateIterator.remove();
    237              linkedEntries.remove(createEntry(value));
    238            }
    239          };
    240        }
    241
    242        @Override public boolean remove(@Nullable Object value) {
    243          boolean changed = delegate.remove(value);
    244          if (changed) {
    245            /*
    246             * linkedEntries.remove() will return false when this method is called
    247             * by entries().iterator().remove()
    248             */
    249            linkedEntries.remove(createEntry(value));
    250          }
    251          return changed;
    252        }
    253
    254        @Override public boolean removeAll(Collection<?> values) {
    255          boolean changed = delegate.removeAll(values);
    256          if (changed) {
    257            linkedEntries.removeAll(createEntries(values));
    258          }
    259          return changed;
    260        }
    261
    262        @Override public boolean retainAll(Collection<?> values) {
    263          /*
    264           * Calling linkedEntries.retainAll() would incorrectly remove values
    265           * with other keys.
    266           */
    267          boolean changed = false;
    268          Iterator<V> iterator = delegate.iterator();
    269          while (iterator.hasNext()) {
    270            V value = iterator.next();
    271            if (!values.contains(value)) {
    272              iterator.remove();
    273              linkedEntries.remove(Maps.immutableEntry(key, value));
    274              changed = true;
    275            }
    276          }
    277          return changed;
    278        }
    279      }
    280
    281      /**
    282       * {@inheritDoc}
    283       *
    284       * <p>Generates an iterator across map entries that follows the ordering in
    285       * which the key-value pairs were added to the multimap.
    286       *
    287       * @return a key-value iterator with the correct ordering
    288       */
    289      @Override Iterator<Map.Entry<K, V>> createEntryIterator() {
    290        final Iterator<Map.Entry<K, V>> delegateIterator = linkedEntries.iterator();
    291
    292        return new Iterator<Map.Entry<K, V>>() {
    293          Map.Entry<K, V> entry;
    294
    295          @Override
    296          public boolean hasNext() {
    297            return delegateIterator.hasNext();
    298          }
    299
    300          @Override
    301          public Map.Entry<K, V> next() {
    302            entry = delegateIterator.next();
    303            return entry;
    304          }
    305
    306          @Override
    307          public void remove() {
    308            // Remove from iterator first to keep iterator valid.
    309            delegateIterator.remove();
    310            LinkedHashMultimap.this.remove(entry.getKey(), entry.getValue());
    311          }
    312        };
    313      }
    314
    315      /**
    316       * {@inheritDoc}
    317       *
    318       * <p>If {@code values} is not empty and the multimap already contains a
    319       * mapping for {@code key}, the {@code keySet()} ordering is unchanged.
    320       * However, the provided values always come last in the {@link #entries()} and
    321       * {@link #values()} iteration orderings.
    322       */
    323      @Override public Set<V> replaceValues(
    324          @Nullable K key, Iterable<? extends V> values) {
    325        return super.replaceValues(key, values);
    326      }
    327
    328      /**
    329       * Returns a set of all key-value pairs. Changes to the returned set will
    330       * update the underlying multimap, and vice versa. The entries set does not
    331       * support the {@code add} or {@code addAll} operations.
    332       *
    333       * <p>The iterator generated by the returned set traverses the entries in the
    334       * order they were added to the multimap.
    335       *
    336       * <p>Each entry is an immutable snapshot of a key-value mapping in the
    337       * multimap, taken at the time the entry is returned by a method call to the
    338       * collection or its iterator.
    339       */
    340      @Override public Set<Map.Entry<K, V>> entries() {
    341        return super.entries();
    342      }
    343
    344      /**
    345       * Returns a collection of all values in the multimap. Changes to the returned
    346       * collection will update the underlying multimap, and vice versa.
    347       *
    348       * <p>The iterator generated by the returned collection traverses the values
    349       * in the order they were added to the multimap.
    350       */
    351      @Override public Collection<V> values() {
    352        return super.values();
    353      }
    354
    355      // Unfortunately, the entries() ordering does not determine the key ordering;
    356      // see the example in the LinkedListMultimap class Javadoc.
    357
    358      /**
    359       * @serialData the number of distinct keys, and then for each distinct key:
    360       *     the first key, the number of values for that key, and the key's values,
    361       *     followed by successive keys and values from the entries() ordering
    362       */
    363      @GwtIncompatible("java.io.ObjectOutputStream")
    364      private void writeObject(ObjectOutputStream stream) throws IOException {
    365        stream.defaultWriteObject();
    366        stream.writeInt(expectedValuesPerKey);
    367        Serialization.writeMultimap(this, stream);
    368        for (Map.Entry<K, V> entry : linkedEntries) {
    369          stream.writeObject(entry.getKey());
    370          stream.writeObject(entry.getValue());
    371        }
    372      }
    373
    374      @GwtIncompatible("java.io.ObjectInputStream")
    375      private void readObject(ObjectInputStream stream)
    376          throws IOException, ClassNotFoundException {
    377        stream.defaultReadObject();
    378        expectedValuesPerKey = stream.readInt();
    379        int distinctKeys = Serialization.readCount(stream);
    380        setMap(new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys)));
    381        linkedEntries = new LinkedHashSet<Map.Entry<K, V>>(
    382            distinctKeys * expectedValuesPerKey);
    383        Serialization.populateMultimap(this, stream, distinctKeys);
    384        linkedEntries.clear(); // will clear and repopulate entries
    385        for (int i = 0; i < size(); i++) {
    386          @SuppressWarnings("unchecked") // reading data stored by writeObject
    387          K key = (K) stream.readObject();
    388          @SuppressWarnings("unchecked") // reading data stored by writeObject
    389          V value = (V) stream.readObject();
    390          linkedEntries.add(Maps.immutableEntry(key, value));
    391        }
    392      }
    393
    394      @GwtIncompatible("java serialization not supported")
    395      private static final long serialVersionUID = 0;
    396    }