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