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