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
017package com.google.common.collect;
018
019import com.google.common.annotations.GwtCompatible;
020import com.google.common.annotations.GwtIncompatible;
021import com.google.common.annotations.VisibleForTesting;
022import com.google.common.base.Preconditions;
023
024import java.io.IOException;
025import java.io.ObjectInputStream;
026import java.io.ObjectOutputStream;
027import java.util.Collection;
028import java.util.Iterator;
029import java.util.LinkedHashMap;
030import java.util.LinkedHashSet;
031import java.util.Map;
032import java.util.Set;
033
034import 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)
071public 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        (int) Math.min(1 << 30, ((long) 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      for (V value : delegate) {
213        linkedEntries.remove(createEntry(value));
214      }
215      delegate.clear();
216    }
217
218    @Override public Iterator<V> iterator() {
219      final Iterator<V> delegateIterator = delegate.iterator();
220      return new Iterator<V>() {
221        V value;
222
223        @Override
224        public boolean hasNext() {
225          return delegateIterator.hasNext();
226        }
227        @Override
228        public V next() {
229          value = delegateIterator.next();
230          return value;
231        }
232        @Override
233        public void remove() {
234          delegateIterator.remove();
235          linkedEntries.remove(createEntry(value));
236        }
237      };
238    }
239
240    @Override public boolean remove(@Nullable Object value) {
241      boolean changed = delegate.remove(value);
242      if (changed) {
243        /*
244         * linkedEntries.remove() will return false when this method is called
245         * by entries().iterator().remove()
246         */
247        linkedEntries.remove(createEntry(value));
248      }
249      return changed;
250    }
251
252    @Override public boolean removeAll(Collection<?> values) {
253      boolean changed = delegate.removeAll(values);
254      if (changed) {
255        linkedEntries.removeAll(createEntries(values));
256      }
257      return changed;
258    }
259
260    @Override public boolean retainAll(Collection<?> values) {
261      /*
262       * Calling linkedEntries.retainAll() would incorrectly remove values
263       * with other keys.
264       */
265      boolean changed = false;
266      Iterator<V> iterator = delegate.iterator();
267      while (iterator.hasNext()) {
268        V value = iterator.next();
269        if (!values.contains(value)) {
270          iterator.remove();
271          linkedEntries.remove(Maps.immutableEntry(key, value));
272          changed = true;
273        }
274      }
275      return changed;
276    }
277  }
278
279  /**
280   * {@inheritDoc}
281   *
282   * <p>Generates an iterator across map entries that follows the ordering in
283   * which the key-value pairs were added to the multimap.
284   *
285   * @return a key-value iterator with the correct ordering
286   */
287  @Override Iterator<Map.Entry<K, V>> createEntryIterator() {
288    final Iterator<Map.Entry<K, V>> delegateIterator = linkedEntries.iterator();
289
290    return new Iterator<Map.Entry<K, V>>() {
291      Map.Entry<K, V> entry;
292
293      @Override
294      public boolean hasNext() {
295        return delegateIterator.hasNext();
296      }
297
298      @Override
299      public Map.Entry<K, V> next() {
300        entry = delegateIterator.next();
301        return entry;
302      }
303
304      @Override
305      public void remove() {
306        // Remove from iterator first to keep iterator valid.
307        delegateIterator.remove();
308        LinkedHashMultimap.this.remove(entry.getKey(), entry.getValue());
309      }
310    };
311  }
312
313  /**
314   * {@inheritDoc}
315   *
316   * <p>If {@code values} is not empty and the multimap already contains a
317   * mapping for {@code key}, the {@code keySet()} ordering is unchanged.
318   * However, the provided values always come last in the {@link #entries()} and
319   * {@link #values()} iteration orderings.
320   */
321  @Override public Set<V> replaceValues(
322      @Nullable K key, Iterable<? extends V> values) {
323    return super.replaceValues(key, values);
324  }
325
326  /**
327   * Returns a set of all key-value pairs. Changes to the returned set will
328   * update the underlying multimap, and vice versa. The entries set does not
329   * support the {@code add} or {@code addAll} operations.
330   *
331   * <p>The iterator generated by the returned set traverses the entries in the
332   * order they were added to the multimap.
333   *
334   * <p>Each entry is an immutable snapshot of a key-value mapping in the
335   * multimap, taken at the time the entry is returned by a method call to the
336   * collection or its iterator.
337   */
338  @Override public Set<Map.Entry<K, V>> entries() {
339    return super.entries();
340  }
341
342  /**
343   * Returns a collection of all values in the multimap. Changes to the returned
344   * collection will update the underlying multimap, and vice versa.
345   *
346   * <p>The iterator generated by the returned collection traverses the values
347   * in the order they were added to the multimap.
348   */
349  @Override public Collection<V> values() {
350    return super.values();
351  }
352
353  // Unfortunately, the entries() ordering does not determine the key ordering;
354  // see the example in the LinkedListMultimap class Javadoc.
355
356  /**
357   * @serialData the number of distinct keys, and then for each distinct key:
358   *     the first key, the number of values for that key, and the key's values,
359   *     followed by successive keys and values from the entries() ordering
360   */
361  @GwtIncompatible("java.io.ObjectOutputStream")
362  private void writeObject(ObjectOutputStream stream) throws IOException {
363    stream.defaultWriteObject();
364    stream.writeInt(expectedValuesPerKey);
365    Serialization.writeMultimap(this, stream);
366    for (Map.Entry<K, V> entry : linkedEntries) {
367      stream.writeObject(entry.getKey());
368      stream.writeObject(entry.getValue());
369    }
370  }
371
372  @GwtIncompatible("java.io.ObjectInputStream")
373  private void readObject(ObjectInputStream stream)
374      throws IOException, ClassNotFoundException {
375    stream.defaultReadObject();
376    expectedValuesPerKey = stream.readInt();
377    int distinctKeys = Serialization.readCount(stream);
378    setMap(new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys)));
379    linkedEntries = new LinkedHashSet<Map.Entry<K, V>>(
380        distinctKeys * expectedValuesPerKey);
381    Serialization.populateMultimap(this, stream, distinctKeys);
382    linkedEntries.clear(); // will clear and repopulate entries
383    for (int i = 0; i < size(); i++) {
384      @SuppressWarnings("unchecked") // reading data stored by writeObject
385      K key = (K) stream.readObject();
386      @SuppressWarnings("unchecked") // reading data stored by writeObject
387      V value = (V) stream.readObject();
388      linkedEntries.add(Maps.immutableEntry(key, value));
389    }
390  }
391
392  @GwtIncompatible("java serialization not supported")
393  private static final long serialVersionUID = 0;
394}