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 static com.google.common.collect.CollectPreconditions.checkNonnegative;
020import static com.google.common.collect.CollectPreconditions.checkRemove;
021
022import com.google.common.annotations.GwtCompatible;
023import com.google.common.annotations.GwtIncompatible;
024import com.google.common.annotations.VisibleForTesting;
025import com.google.common.base.Objects;
026import com.google.errorprone.annotations.CanIgnoreReturnValue;
027import com.google.j2objc.annotations.WeakOuter;
028import java.io.IOException;
029import java.io.ObjectInputStream;
030import java.io.ObjectOutputStream;
031import java.util.Arrays;
032import java.util.Collection;
033import java.util.ConcurrentModificationException;
034import java.util.Iterator;
035import java.util.LinkedHashMap;
036import java.util.LinkedHashSet;
037import java.util.Map;
038import java.util.NoSuchElementException;
039import java.util.Set;
040import javax.annotation.Nullable;
041
042/**
043 * Implementation of {@code Multimap} that does not allow duplicate key-value
044 * entries and that returns collections whose iterators follow the ordering in
045 * which the data was added to the multimap.
046 *
047 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code
048 * asMap} iterate through the keys in the order they were first added to the
049 * multimap. Similarly, {@code get}, {@code removeAll}, and {@code
050 * replaceValues} return collections that iterate through the values in the
051 * order they were added. The collections generated by {@code entries} and
052 * {@code values} iterate across the key-value mappings in the order they were
053 * added to the multimap.
054 *
055 * <p>The iteration ordering of the collections generated by {@code keySet},
056 * {@code keys}, and {@code asMap} has a few subtleties. As long as the set of
057 * keys remains unchanged, adding or removing mappings does not affect the key
058 * iteration order. However, if you remove all values associated with a key and
059 * then add the key back to the multimap, that key will come last in the key
060 * iteration order.
061 *
062 * <p>The multimap does not store duplicate key-value pairs. Adding a new
063 * key-value pair equal to an existing key-value pair has no effect.
064 *
065 * <p>Keys and values may be null. All optional multimap methods are supported,
066 * and all returned views are modifiable.
067 *
068 * <p>This class is not threadsafe when any concurrent operations update the
069 * multimap. Concurrent read operations will work correctly. To allow concurrent
070 * update operations, wrap your multimap with a call to {@link
071 * Multimaps#synchronizedSetMultimap}.
072 *
073 * <p>See the Guava User Guide article on <a href=
074 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">
075 * {@code Multimap}</a>.
076 *
077 * @author Jared Levy
078 * @author Louis Wasserman
079 * @since 2.0
080 */
081@GwtCompatible(serializable = true, emulated = true)
082public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> {
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>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
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(int expectedKeys, int expectedValuesPerKey) {
102    return new LinkedHashMultimap<K, V>(
103        Maps.capacity(expectedKeys), Maps.capacity(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    LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY);
118    result.putAll(multimap);
119    return result;
120  }
121
122  private interface ValueSetLink<K, V> {
123    ValueSetLink<K, V> getPredecessorInValueSet();
124
125    ValueSetLink<K, V> getSuccessorInValueSet();
126
127    void setPredecessorInValueSet(ValueSetLink<K, V> entry);
128
129    void setSuccessorInValueSet(ValueSetLink<K, V> entry);
130  }
131
132  private static <K, V> void succeedsInValueSet(ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) {
133    pred.setSuccessorInValueSet(succ);
134    succ.setPredecessorInValueSet(pred);
135  }
136
137  private static <K, V> void succeedsInMultimap(ValueEntry<K, V> pred, ValueEntry<K, V> succ) {
138    pred.setSuccessorInMultimap(succ);
139    succ.setPredecessorInMultimap(pred);
140  }
141
142  private static <K, V> void deleteFromValueSet(ValueSetLink<K, V> entry) {
143    succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet());
144  }
145
146  private static <K, V> void deleteFromMultimap(ValueEntry<K, V> entry) {
147    succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap());
148  }
149
150  /**
151   * LinkedHashMultimap entries are in no less than three coexisting linked lists:
152   * a bucket in the hash table for a Set<V> associated with a key, the linked list
153   * of insertion-ordered entries in that Set<V>, and the linked list of entries
154   * in the LinkedHashMultimap as a whole.
155   */
156  @VisibleForTesting
157  static final class ValueEntry<K, V> extends ImmutableEntry<K, V> implements ValueSetLink<K, V> {
158    final int smearedValueHash;
159
160    @Nullable ValueEntry<K, V> nextInValueBucket;
161
162    ValueSetLink<K, V> predecessorInValueSet;
163    ValueSetLink<K, V> successorInValueSet;
164
165    ValueEntry<K, V> predecessorInMultimap;
166    ValueEntry<K, V> successorInMultimap;
167
168    ValueEntry(
169        @Nullable K key,
170        @Nullable V value,
171        int smearedValueHash,
172        @Nullable ValueEntry<K, V> nextInValueBucket) {
173      super(key, value);
174      this.smearedValueHash = smearedValueHash;
175      this.nextInValueBucket = nextInValueBucket;
176    }
177
178    boolean matchesValue(@Nullable Object v, int smearedVHash) {
179      return smearedValueHash == smearedVHash && Objects.equal(getValue(), v);
180    }
181
182    @Override
183    public ValueSetLink<K, V> getPredecessorInValueSet() {
184      return predecessorInValueSet;
185    }
186
187    @Override
188    public ValueSetLink<K, V> getSuccessorInValueSet() {
189      return successorInValueSet;
190    }
191
192    @Override
193    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
194      predecessorInValueSet = entry;
195    }
196
197    @Override
198    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
199      successorInValueSet = entry;
200    }
201
202    public ValueEntry<K, V> getPredecessorInMultimap() {
203      return predecessorInMultimap;
204    }
205
206    public ValueEntry<K, V> getSuccessorInMultimap() {
207      return successorInMultimap;
208    }
209
210    public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
211      this.successorInMultimap = multimapSuccessor;
212    }
213
214    public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
215      this.predecessorInMultimap = multimapPredecessor;
216    }
217  }
218
219  private static final int DEFAULT_KEY_CAPACITY = 16;
220  private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
221  @VisibleForTesting static final double VALUE_SET_LOAD_FACTOR = 1.0;
222
223  @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
224  private transient ValueEntry<K, V> multimapHeaderEntry;
225
226  private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
227    super(new LinkedHashMap<K, Collection<V>>(keyCapacity));
228    checkNonnegative(valueSetCapacity, "expectedValuesPerKey");
229
230    this.valueSetCapacity = valueSetCapacity;
231    this.multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
232    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
233  }
234
235  /**
236   * {@inheritDoc}
237   *
238   * <p>Creates an empty {@code LinkedHashSet} for a collection of values for
239   * one key.
240   *
241   * @return a new {@code LinkedHashSet} containing a collection of values for
242   *     one key
243   */
244  @Override
245  Set<V> createCollection() {
246    return new LinkedHashSet<V>(valueSetCapacity);
247  }
248
249  /**
250   * {@inheritDoc}
251   *
252   * <p>Creates a decorated insertion-ordered set that also keeps track of the
253   * order in which key-value pairs are added to the multimap.
254   *
255   * @param key key to associate with values in the collection
256   * @return a new decorated set containing a collection of values for one key
257   */
258  @Override
259  Collection<V> createCollection(K key) {
260    return new ValueSet(key, valueSetCapacity);
261  }
262
263  /**
264   * {@inheritDoc}
265   *
266   * <p>If {@code values} is not empty and the multimap already contains a
267   * mapping for {@code key}, the {@code keySet()} ordering is unchanged.
268   * However, the provided values always come last in the {@link #entries()} and
269   * {@link #values()} iteration orderings.
270   */
271  @CanIgnoreReturnValue
272  @Override
273  public Set<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
274    return super.replaceValues(key, values);
275  }
276
277  /**
278   * Returns a set of all key-value pairs. Changes to the returned set will
279   * update the underlying multimap, and vice versa. The entries set does not
280   * support the {@code add} or {@code addAll} operations.
281   *
282   * <p>The iterator generated by the returned set traverses the entries in the
283   * order they were added to the multimap.
284   *
285   * <p>Each entry is an immutable snapshot of a key-value mapping in the
286   * multimap, taken at the time the entry is returned by a method call to the
287   * collection or its iterator.
288   */
289  @Override
290  public Set<Map.Entry<K, V>> entries() {
291    return super.entries();
292  }
293
294  /**
295   * Returns a view collection of all <i>distinct</i> keys contained in this
296   * multimap. Note that the key set contains a key if and only if this multimap
297   * maps that key to at least one value.
298   * 
299   * <p>The iterator generated by the returned set traverses the keys in the
300   * order they were first added to the multimap.
301   *
302   * <p>Changes to the returned set will update the underlying multimap, and
303   * vice versa. However, <i>adding</i> to the returned set is not possible.
304   */
305  @Override
306  public Set<K> keySet() {
307    return super.keySet();
308  }
309
310  /**
311   * Returns a collection of all values in the multimap. Changes to the returned
312   * collection will update the underlying multimap, and vice versa.
313   *
314   * <p>The iterator generated by the returned collection traverses the values
315   * in the order they were added to the multimap.
316   */
317  @Override
318  public Collection<V> values() {
319    return super.values();
320  }
321
322  @VisibleForTesting
323  @WeakOuter
324  final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
325    /*
326     * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
327     * consumption.
328     */
329
330    private final K key;
331    @VisibleForTesting ValueEntry<K, V>[] hashTable;
332    private int size = 0;
333    private int modCount = 0;
334
335    // We use the set object itself as the end of the linked list, avoiding an unnecessary
336    // entry object per key.
337    private ValueSetLink<K, V> firstEntry;
338    private ValueSetLink<K, V> lastEntry;
339
340    ValueSet(K key, int expectedValues) {
341      this.key = key;
342      this.firstEntry = this;
343      this.lastEntry = this;
344      // Round expected values up to a power of 2 to get the table size.
345      int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR);
346
347      @SuppressWarnings("unchecked")
348      ValueEntry<K, V>[] hashTable = new ValueEntry[tableSize];
349      this.hashTable = hashTable;
350    }
351
352    private int mask() {
353      return hashTable.length - 1;
354    }
355
356    @Override
357    public ValueSetLink<K, V> getPredecessorInValueSet() {
358      return lastEntry;
359    }
360
361    @Override
362    public ValueSetLink<K, V> getSuccessorInValueSet() {
363      return firstEntry;
364    }
365
366    @Override
367    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
368      lastEntry = entry;
369    }
370
371    @Override
372    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
373      firstEntry = entry;
374    }
375
376    @Override
377    public Iterator<V> iterator() {
378      return new Iterator<V>() {
379        ValueSetLink<K, V> nextEntry = firstEntry;
380        ValueEntry<K, V> toRemove;
381        int expectedModCount = modCount;
382
383        private void checkForComodification() {
384          if (modCount != expectedModCount) {
385            throw new ConcurrentModificationException();
386          }
387        }
388
389        @Override
390        public boolean hasNext() {
391          checkForComodification();
392          return nextEntry != ValueSet.this;
393        }
394
395        @Override
396        public V next() {
397          if (!hasNext()) {
398            throw new NoSuchElementException();
399          }
400          ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
401          V result = entry.getValue();
402          toRemove = entry;
403          nextEntry = entry.getSuccessorInValueSet();
404          return result;
405        }
406
407        @Override
408        public void remove() {
409          checkForComodification();
410          checkRemove(toRemove != null);
411          ValueSet.this.remove(toRemove.getValue());
412          expectedModCount = modCount;
413          toRemove = null;
414        }
415      };
416    }
417
418    @Override
419    public int size() {
420      return size;
421    }
422
423    @Override
424    public boolean contains(@Nullable Object o) {
425      int smearedHash = Hashing.smearedHash(o);
426      for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()];
427          entry != null;
428          entry = entry.nextInValueBucket) {
429        if (entry.matchesValue(o, smearedHash)) {
430          return true;
431        }
432      }
433      return false;
434    }
435
436    @Override
437    public boolean add(@Nullable V value) {
438      int smearedHash = Hashing.smearedHash(value);
439      int bucket = smearedHash & mask();
440      ValueEntry<K, V> rowHead = hashTable[bucket];
441      for (ValueEntry<K, V> entry = rowHead; entry != null; entry = entry.nextInValueBucket) {
442        if (entry.matchesValue(value, smearedHash)) {
443          return false;
444        }
445      }
446
447      ValueEntry<K, V> newEntry = new ValueEntry<K, V>(key, value, smearedHash, rowHead);
448      succeedsInValueSet(lastEntry, newEntry);
449      succeedsInValueSet(newEntry, this);
450      succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
451      succeedsInMultimap(newEntry, multimapHeaderEntry);
452      hashTable[bucket] = newEntry;
453      size++;
454      modCount++;
455      rehashIfNecessary();
456      return true;
457    }
458
459    private void rehashIfNecessary() {
460      if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR)) {
461        @SuppressWarnings("unchecked")
462        ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2];
463        this.hashTable = hashTable;
464        int mask = hashTable.length - 1;
465        for (ValueSetLink<K, V> entry = firstEntry;
466            entry != this;
467            entry = entry.getSuccessorInValueSet()) {
468          ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
469          int bucket = valueEntry.smearedValueHash & mask;
470          valueEntry.nextInValueBucket = hashTable[bucket];
471          hashTable[bucket] = valueEntry;
472        }
473      }
474    }
475
476    @CanIgnoreReturnValue
477    @Override
478    public boolean remove(@Nullable Object o) {
479      int smearedHash = Hashing.smearedHash(o);
480      int bucket = smearedHash & mask();
481      ValueEntry<K, V> prev = null;
482      for (ValueEntry<K, V> entry = hashTable[bucket];
483          entry != null;
484          prev = entry, entry = entry.nextInValueBucket) {
485        if (entry.matchesValue(o, smearedHash)) {
486          if (prev == null) {
487            // first entry in the bucket
488            hashTable[bucket] = entry.nextInValueBucket;
489          } else {
490            prev.nextInValueBucket = entry.nextInValueBucket;
491          }
492          deleteFromValueSet(entry);
493          deleteFromMultimap(entry);
494          size--;
495          modCount++;
496          return true;
497        }
498      }
499      return false;
500    }
501
502    @Override
503    public void clear() {
504      Arrays.fill(hashTable, null);
505      size = 0;
506      for (ValueSetLink<K, V> entry = firstEntry;
507          entry != this;
508          entry = entry.getSuccessorInValueSet()) {
509        ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
510        deleteFromMultimap(valueEntry);
511      }
512      succeedsInValueSet(this, this);
513      modCount++;
514    }
515  }
516
517  @Override
518  Iterator<Map.Entry<K, V>> entryIterator() {
519    return new Iterator<Map.Entry<K, V>>() {
520      ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap;
521      ValueEntry<K, V> toRemove;
522
523      @Override
524      public boolean hasNext() {
525        return nextEntry != multimapHeaderEntry;
526      }
527
528      @Override
529      public Map.Entry<K, V> next() {
530        if (!hasNext()) {
531          throw new NoSuchElementException();
532        }
533        ValueEntry<K, V> result = nextEntry;
534        toRemove = result;
535        nextEntry = nextEntry.successorInMultimap;
536        return result;
537      }
538
539      @Override
540      public void remove() {
541        checkRemove(toRemove != null);
542        LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
543        toRemove = null;
544      }
545    };
546  }
547
548  @Override
549  Iterator<V> valueIterator() {
550    return Maps.valueIterator(entryIterator());
551  }
552
553  @Override
554  public void clear() {
555    super.clear();
556    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
557  }
558
559  /**
560   * @serialData the expected values per key, the number of distinct keys,
561   * the number of entries, and the entries in order
562   */
563  @GwtIncompatible // java.io.ObjectOutputStream
564  private void writeObject(ObjectOutputStream stream) throws IOException {
565    stream.defaultWriteObject();
566    stream.writeInt(keySet().size());
567    for (K key : keySet()) {
568      stream.writeObject(key);
569    }
570    stream.writeInt(size());
571    for (Map.Entry<K, V> entry : entries()) {
572      stream.writeObject(entry.getKey());
573      stream.writeObject(entry.getValue());
574    }
575  }
576
577  @GwtIncompatible // java.io.ObjectInputStream
578  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
579    stream.defaultReadObject();
580    multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
581    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
582    valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
583    int distinctKeys = stream.readInt();
584    Map<K, Collection<V>> map = new LinkedHashMap<K, Collection<V>>();
585    for (int i = 0; i < distinctKeys; i++) {
586      @SuppressWarnings("unchecked")
587      K key = (K) stream.readObject();
588      map.put(key, createCollection(key));
589    }
590    int entries = stream.readInt();
591    for (int i = 0; i < entries; i++) {
592      @SuppressWarnings("unchecked")
593      K key = (K) stream.readObject();
594      @SuppressWarnings("unchecked")
595      V value = (V) stream.readObject();
596      map.get(key).add(value);
597    }
598    setMap(map);
599  }
600
601  @GwtIncompatible // java serialization not supported
602  private static final long serialVersionUID = 1;
603}