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.j2objc.annotations.WeakOuter;
027
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;
040
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> extends AbstractSetMultimap<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<K, V>(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<K, V>(
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:
153   * a bucket in the hash table for a Set<V> associated with a key, the linked list
154   * of insertion-ordered entries in that Set<V>, and the linked list of entries
155   * in the LinkedHashMultimap as a 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<K, V>(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  @Override
273  public Set<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
274    return super.replaceValues(key, values);
275  }
276
277  /**
278   * Returns a set of all key-value pairs. Changes to the returned set will
279   * update the underlying multimap, and vice versa. The entries set does not
280   * support the {@code add} or {@code addAll} operations.
281   *
282   * <p>The iterator generated by the returned set traverses the entries in the
283   * order they were added to the multimap.
284   *
285   * <p>Each entry is an immutable snapshot of a key-value mapping in the
286   * multimap, taken at the time the entry is returned by a method call to the
287   * collection or its iterator.
288   */
289  @Override
290  public Set<Map.Entry<K, V>> entries() {
291    return super.entries();
292  }
293
294  /**
295   * Returns a collection of all values in the multimap. Changes to the returned
296   * collection will update the underlying multimap, and vice versa.
297   *
298   * <p>The iterator generated by the returned collection traverses the values
299   * in the order they were added to the multimap.
300   */
301  @Override
302  public Collection<V> values() {
303    return super.values();
304  }
305
306  @VisibleForTesting
307  @WeakOuter
308  final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
309    /*
310     * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
311     * consumption.
312     */
313
314    private final K key;
315    @VisibleForTesting ValueEntry<K, V>[] hashTable;
316    private int size = 0;
317    private int modCount = 0;
318
319    // We use the set object itself as the end of the linked list, avoiding an unnecessary
320    // entry object per key.
321    private ValueSetLink<K, V> firstEntry;
322    private ValueSetLink<K, V> lastEntry;
323
324    ValueSet(K key, int expectedValues) {
325      this.key = key;
326      this.firstEntry = this;
327      this.lastEntry = this;
328      // Round expected values up to a power of 2 to get the table size.
329      int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR);
330
331      @SuppressWarnings("unchecked")
332      ValueEntry<K, V>[] hashTable = new ValueEntry[tableSize];
333      this.hashTable = hashTable;
334    }
335
336    private int mask() {
337      return hashTable.length - 1;
338    }
339
340    @Override
341    public ValueSetLink<K, V> getPredecessorInValueSet() {
342      return lastEntry;
343    }
344
345    @Override
346    public ValueSetLink<K, V> getSuccessorInValueSet() {
347      return firstEntry;
348    }
349
350    @Override
351    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
352      lastEntry = entry;
353    }
354
355    @Override
356    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
357      firstEntry = entry;
358    }
359
360    @Override
361    public Iterator<V> iterator() {
362      return new Iterator<V>() {
363        ValueSetLink<K, V> nextEntry = firstEntry;
364        ValueEntry<K, V> toRemove;
365        int expectedModCount = modCount;
366
367        private void checkForComodification() {
368          if (modCount != expectedModCount) {
369            throw new ConcurrentModificationException();
370          }
371        }
372
373        @Override
374        public boolean hasNext() {
375          checkForComodification();
376          return nextEntry != ValueSet.this;
377        }
378
379        @Override
380        public V next() {
381          if (!hasNext()) {
382            throw new NoSuchElementException();
383          }
384          ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
385          V result = entry.getValue();
386          toRemove = entry;
387          nextEntry = entry.getSuccessorInValueSet();
388          return result;
389        }
390
391        @Override
392        public void remove() {
393          checkForComodification();
394          checkRemove(toRemove != null);
395          ValueSet.this.remove(toRemove.getValue());
396          expectedModCount = modCount;
397          toRemove = null;
398        }
399      };
400    }
401
402    @Override
403    public int size() {
404      return size;
405    }
406
407    @Override
408    public boolean contains(@Nullable Object o) {
409      int smearedHash = Hashing.smearedHash(o);
410      for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()];
411          entry != null;
412          entry = entry.nextInValueBucket) {
413        if (entry.matchesValue(o, smearedHash)) {
414          return true;
415        }
416      }
417      return false;
418    }
419
420    @Override
421    public boolean add(@Nullable V value) {
422      int smearedHash = Hashing.smearedHash(value);
423      int bucket = smearedHash & mask();
424      ValueEntry<K, V> rowHead = hashTable[bucket];
425      for (ValueEntry<K, V> entry = rowHead; entry != null; entry = entry.nextInValueBucket) {
426        if (entry.matchesValue(value, smearedHash)) {
427          return false;
428        }
429      }
430
431      ValueEntry<K, V> newEntry = new ValueEntry<K, V>(key, value, smearedHash, rowHead);
432      succeedsInValueSet(lastEntry, newEntry);
433      succeedsInValueSet(newEntry, this);
434      succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
435      succeedsInMultimap(newEntry, multimapHeaderEntry);
436      hashTable[bucket] = newEntry;
437      size++;
438      modCount++;
439      rehashIfNecessary();
440      return true;
441    }
442
443    private void rehashIfNecessary() {
444      if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR)) {
445        @SuppressWarnings("unchecked")
446        ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2];
447        this.hashTable = hashTable;
448        int mask = hashTable.length - 1;
449        for (ValueSetLink<K, V> entry = firstEntry;
450            entry != this;
451            entry = entry.getSuccessorInValueSet()) {
452          ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
453          int bucket = valueEntry.smearedValueHash & mask;
454          valueEntry.nextInValueBucket = hashTable[bucket];
455          hashTable[bucket] = valueEntry;
456        }
457      }
458    }
459
460    @Override
461    public boolean remove(@Nullable Object o) {
462      int smearedHash = Hashing.smearedHash(o);
463      int bucket = smearedHash & mask();
464      ValueEntry<K, V> prev = null;
465      for (ValueEntry<K, V> entry = hashTable[bucket];
466          entry != null;
467          prev = entry, entry = entry.nextInValueBucket) {
468        if (entry.matchesValue(o, smearedHash)) {
469          if (prev == null) {
470            // first entry in the bucket
471            hashTable[bucket] = entry.nextInValueBucket;
472          } else {
473            prev.nextInValueBucket = entry.nextInValueBucket;
474          }
475          deleteFromValueSet(entry);
476          deleteFromMultimap(entry);
477          size--;
478          modCount++;
479          return true;
480        }
481      }
482      return false;
483    }
484
485    @Override
486    public void clear() {
487      Arrays.fill(hashTable, null);
488      size = 0;
489      for (ValueSetLink<K, V> entry = firstEntry;
490          entry != this;
491          entry = entry.getSuccessorInValueSet()) {
492        ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
493        deleteFromMultimap(valueEntry);
494      }
495      succeedsInValueSet(this, this);
496      modCount++;
497    }
498  }
499
500  @Override
501  Iterator<Map.Entry<K, V>> entryIterator() {
502    return new Iterator<Map.Entry<K, V>>() {
503      ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap;
504      ValueEntry<K, V> toRemove;
505
506      @Override
507      public boolean hasNext() {
508        return nextEntry != multimapHeaderEntry;
509      }
510
511      @Override
512      public Map.Entry<K, V> next() {
513        if (!hasNext()) {
514          throw new NoSuchElementException();
515        }
516        ValueEntry<K, V> result = nextEntry;
517        toRemove = result;
518        nextEntry = nextEntry.successorInMultimap;
519        return result;
520      }
521
522      @Override
523      public void remove() {
524        checkRemove(toRemove != null);
525        LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
526        toRemove = null;
527      }
528    };
529  }
530
531  @Override
532  Iterator<V> valueIterator() {
533    return Maps.valueIterator(entryIterator());
534  }
535
536  @Override
537  public void clear() {
538    super.clear();
539    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
540  }
541
542  /**
543   * @serialData the expected values per key, the number of distinct keys,
544   * the number of entries, and the entries in order
545   */
546  @GwtIncompatible("java.io.ObjectOutputStream")
547  private void writeObject(ObjectOutputStream stream) throws IOException {
548    stream.defaultWriteObject();
549    stream.writeInt(keySet().size());
550    for (K key : keySet()) {
551      stream.writeObject(key);
552    }
553    stream.writeInt(size());
554    for (Map.Entry<K, V> entry : entries()) {
555      stream.writeObject(entry.getKey());
556      stream.writeObject(entry.getValue());
557    }
558  }
559
560  @GwtIncompatible("java.io.ObjectInputStream")
561  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
562    stream.defaultReadObject();
563    multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
564    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
565    valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
566    int distinctKeys = stream.readInt();
567    Map<K, Collection<V>> map = new LinkedHashMap<K, Collection<V>>();
568    for (int i = 0; i < distinctKeys; i++) {
569      @SuppressWarnings("unchecked")
570      K key = (K) stream.readObject();
571      map.put(key, createCollection(key));
572    }
573    int entries = stream.readInt();
574    for (int i = 0; i < entries; i++) {
575      @SuppressWarnings("unchecked")
576      K key = (K) stream.readObject();
577      @SuppressWarnings("unchecked")
578      V value = (V) stream.readObject();
579      map.get(key).add(value);
580    }
581    setMap(map);
582  }
583
584  @GwtIncompatible("java serialization not supported")
585  private static final long serialVersionUID = 1;
586}