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