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