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