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