1/*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.google.common.collect;
18
19import static com.google.common.collect.CollectPreconditions.checkNonnegative;
20import static com.google.common.collect.CollectPreconditions.checkRemove;
21
22import com.google.common.annotations.GwtCompatible;
23import com.google.common.annotations.GwtIncompatible;
24import com.google.common.annotations.VisibleForTesting;
25import com.google.common.base.Objects;
26
27import java.io.IOException;
28import java.io.ObjectInputStream;
29import java.io.ObjectOutputStream;
30import java.util.Arrays;
31import java.util.Collection;
32import java.util.ConcurrentModificationException;
33import java.util.Iterator;
34import java.util.LinkedHashMap;
35import java.util.LinkedHashSet;
36import java.util.Map;
37import java.util.NoSuchElementException;
38import java.util.Set;
39
40import javax.annotation.Nullable;
41
42/**
43 * Implementation of {@code Multimap} that does not allow duplicate key-value
44 * entries and that returns collections whose iterators follow the ordering in
45 * which the data was added to the multimap.
46 *
47 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code
48 * asMap} iterate through the keys in the order they were first added to the
49 * multimap. Similarly, {@code get}, {@code removeAll}, and {@code
50 * replaceValues} return collections that iterate through the values in the
51 * order they were added. The collections generated by {@code entries} and
52 * {@code values} iterate across the key-value mappings in the order they were
53 * added to the multimap.
54 *
55 * <p>The iteration ordering of the collections generated by {@code keySet},
56 * {@code keys}, and {@code asMap} has a few subtleties. As long as the set of
57 * keys remains unchanged, adding or removing mappings does not affect the key
58 * iteration order. However, if you remove all values associated with a key and
59 * then add the key back to the multimap, that key will come last in the key
60 * iteration order.
61 *
62 * <p>The multimap does not store duplicate key-value pairs. Adding a new
63 * key-value pair equal to an existing key-value pair has no effect.
64 *
65 * <p>Keys and values may be null. All optional multimap methods are supported,
66 * and all returned views are modifiable.
67 *
68 * <p>This class is not threadsafe when any concurrent operations update the
69 * multimap. Concurrent read operations will work correctly. To allow concurrent
70 * update operations, wrap your multimap with a call to {@link
71 * Multimaps#synchronizedSetMultimap}.
72 *
73 * <p>See the Guava User Guide article on <a href=
74 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
75 * {@code Multimap}</a>.
76 *
77 * @author Jared Levy
78 * @author Louis Wasserman
79 * @since 2.0 (imported from Google Collections Library)
80 */
81@GwtCompatible(serializable = true, emulated = true)
82public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> {
83
84  /**
85   * Creates a new, empty {@code LinkedHashMultimap} with the default initial
86   * capacities.
87   */
88  public static <K, V> LinkedHashMultimap<K, V> create() {
89    return new LinkedHashMultimap<K, V>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
90  }
91
92  /**
93   * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold
94   * the specified numbers of keys and values without rehashing.
95   *
96   * @param expectedKeys the expected number of distinct keys
97   * @param expectedValuesPerKey the expected average number of values per key
98   * @throws IllegalArgumentException if {@code expectedKeys} or {@code
99   *      expectedValuesPerKey} is negative
100   */
101  public static <K, V> LinkedHashMultimap<K, V> create(
102      int expectedKeys, int expectedValuesPerKey) {
103    return new LinkedHashMultimap<K, V>(
104        Maps.capacity(expectedKeys),
105        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    ValueSetLink<K, V> getSuccessorInValueSet();
127
128    void setPredecessorInValueSet(ValueSetLink<K, V> entry);
129    void setSuccessorInValueSet(ValueSetLink<K, V> entry);
130  }
131
132  private static <K, V> void succeedsInValueSet(ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) {
133    pred.setSuccessorInValueSet(succ);
134    succ.setPredecessorInValueSet(pred);
135  }
136
137  private static <K, V> void succeedsInMultimap(
138      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>
159      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(@Nullable K key, @Nullable V value, int smearedValueHash,
171        @Nullable ValueEntry<K, V> nextInValueBucket) {
172      super(key, value);
173      this.smearedValueHash = smearedValueHash;
174      this.nextInValueBucket = nextInValueBucket;
175    }
176
177    boolean matchesValue(@Nullable Object v, int smearedVHash) {
178      return smearedValueHash == smearedVHash && Objects.equal(getValue(), v);
179    }
180
181    @Override
182    public ValueSetLink<K, V> getPredecessorInValueSet() {
183      return predecessorInValueSet;
184    }
185
186    @Override
187    public ValueSetLink<K, V> getSuccessorInValueSet() {
188      return successorInValueSet;
189    }
190
191    @Override
192    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
193      predecessorInValueSet = entry;
194    }
195
196    @Override
197    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
198      successorInValueSet = entry;
199    }
200
201    public ValueEntry<K, V> getPredecessorInMultimap() {
202      return predecessorInMultimap;
203    }
204
205    public ValueEntry<K, V> getSuccessorInMultimap() {
206      return successorInMultimap;
207    }
208
209    public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
210      this.successorInMultimap = multimapSuccessor;
211    }
212
213    public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
214      this.predecessorInMultimap = multimapPredecessor;
215    }
216  }
217
218  private static final int DEFAULT_KEY_CAPACITY = 16;
219  private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
220  @VisibleForTesting static final double VALUE_SET_LOAD_FACTOR = 1.0;
221
222  @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
223  private transient ValueEntry<K, V> multimapHeaderEntry;
224
225  private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
226    super(new LinkedHashMap<K, Collection<V>>(keyCapacity));
227    checkNonnegative(valueSetCapacity, "expectedValuesPerKey");
228
229    this.valueSetCapacity = valueSetCapacity;
230    this.multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
231    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
232  }
233
234  /**
235   * {@inheritDoc}
236   *
237   * <p>Creates an empty {@code LinkedHashSet} for a collection of values for
238   * one key.
239   *
240   * @return a new {@code LinkedHashSet} containing a collection of values for
241   *     one key
242   */
243  @Override
244  Set<V> createCollection() {
245    return new LinkedHashSet<V>(valueSetCapacity);
246  }
247
248  /**
249   * {@inheritDoc}
250   *
251   * <p>Creates a decorated insertion-ordered set that also keeps track of the
252   * order in which key-value pairs are added to the multimap.
253   *
254   * @param key key to associate with values in the collection
255   * @return a new decorated set containing a collection of values for one key
256   */
257  @Override
258  Collection<V> createCollection(K key) {
259    return new ValueSet(key, valueSetCapacity);
260  }
261
262  /**
263   * {@inheritDoc}
264   *
265   * <p>If {@code values} is not empty and the multimap already contains a
266   * mapping for {@code key}, the {@code keySet()} ordering is unchanged.
267   * However, the provided values always come last in the {@link #entries()} and
268   * {@link #values()} iteration orderings.
269   */
270  @Override
271  public Set<V> replaceValues(@Nullable K key, Iterable<? extends V> values) {
272    return super.replaceValues(key, values);
273  }
274
275  /**
276   * Returns a set of all key-value pairs. Changes to the returned set will
277   * update the underlying multimap, and vice versa. The entries set does not
278   * support the {@code add} or {@code addAll} operations.
279   *
280   * <p>The iterator generated by the returned set traverses the entries in the
281   * order they were added to the multimap.
282   *
283   * <p>Each entry is an immutable snapshot of a key-value mapping in the
284   * multimap, taken at the time the entry is returned by a method call to the
285   * collection or its iterator.
286   */
287  @Override public Set<Map.Entry<K, V>> entries() {
288    return super.entries();
289  }
290
291  /**
292   * Returns a collection of all values in the multimap. Changes to the returned
293   * collection will update the underlying multimap, and vice versa.
294   *
295   * <p>The iterator generated by the returned collection traverses the values
296   * in the order they were added to the multimap.
297   */
298  @Override public Collection<V> values() {
299    return super.values();
300  }
301
302  @VisibleForTesting
303  final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
304    /*
305     * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
306     * consumption.
307     */
308
309    private final K key;
310    @VisibleForTesting ValueEntry<K, V>[] hashTable;
311    private int size = 0;
312    private int modCount = 0;
313
314    // We use the set object itself as the end of the linked list, avoiding an unnecessary
315    // entry object per key.
316    private ValueSetLink<K, V> firstEntry;
317    private ValueSetLink<K, V> lastEntry;
318
319    ValueSet(K key, int expectedValues) {
320      this.key = key;
321      this.firstEntry = this;
322      this.lastEntry = this;
323      // Round expected values up to a power of 2 to get the table size.
324      int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR);
325
326      @SuppressWarnings("unchecked")
327      ValueEntry<K, V>[] hashTable = new ValueEntry[tableSize];
328      this.hashTable = hashTable;
329    }
330
331    private int mask() {
332      return hashTable.length - 1;
333    }
334
335    @Override
336    public ValueSetLink<K, V> getPredecessorInValueSet() {
337      return lastEntry;
338    }
339
340    @Override
341    public ValueSetLink<K, V> getSuccessorInValueSet() {
342      return firstEntry;
343    }
344
345    @Override
346    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
347      lastEntry = entry;
348    }
349
350    @Override
351    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
352      firstEntry = entry;
353    }
354
355    @Override
356    public Iterator<V> iterator() {
357      return new Iterator<V>() {
358        ValueSetLink<K, V> nextEntry = firstEntry;
359        ValueEntry<K, V> toRemove;
360        int expectedModCount = modCount;
361
362        private void checkForComodification() {
363          if (modCount != expectedModCount) {
364            throw new ConcurrentModificationException();
365          }
366        }
367
368        @Override
369        public boolean hasNext() {
370          checkForComodification();
371          return nextEntry != ValueSet.this;
372        }
373
374        @Override
375        public V next() {
376          if (!hasNext()) {
377            throw new NoSuchElementException();
378          }
379          ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
380          V result = entry.getValue();
381          toRemove = entry;
382          nextEntry = entry.getSuccessorInValueSet();
383          return result;
384        }
385
386        @Override
387        public void remove() {
388          checkForComodification();
389          checkRemove(toRemove != null);
390          ValueSet.this.remove(toRemove.getValue());
391          expectedModCount = modCount;
392          toRemove = null;
393        }
394      };
395    }
396
397    @Override
398    public int size() {
399      return size;
400    }
401
402    @Override
403    public boolean contains(@Nullable Object o) {
404      int smearedHash = Hashing.smearedHash(o);
405      for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()]; entry != null;
406          entry = entry.nextInValueBucket) {
407        if (entry.matchesValue(o, smearedHash)) {
408          return true;
409        }
410      }
411      return false;
412    }
413
414    @Override
415    public boolean add(@Nullable V value) {
416      int smearedHash = Hashing.smearedHash(value);
417      int bucket = smearedHash & mask();
418      ValueEntry<K, V> rowHead = hashTable[bucket];
419      for (ValueEntry<K, V> entry = rowHead; entry != null;
420          entry = entry.nextInValueBucket) {
421        if (entry.matchesValue(value, smearedHash)) {
422          return false;
423        }
424      }
425
426      ValueEntry<K, V> newEntry = new ValueEntry<K, V>(key, value, smearedHash, rowHead);
427      succeedsInValueSet(lastEntry, newEntry);
428      succeedsInValueSet(newEntry, this);
429      succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
430      succeedsInMultimap(newEntry, multimapHeaderEntry);
431      hashTable[bucket] = newEntry;
432      size++;
433      modCount++;
434      rehashIfNecessary();
435      return true;
436    }
437
438    private void rehashIfNecessary() {
439      if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR)) {
440        @SuppressWarnings("unchecked")
441        ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2];
442        this.hashTable = hashTable;
443        int mask = hashTable.length - 1;
444        for (ValueSetLink<K, V> entry = firstEntry;
445            entry != this; entry = entry.getSuccessorInValueSet()) {
446          ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
447          int bucket = valueEntry.smearedValueHash & mask;
448          valueEntry.nextInValueBucket = hashTable[bucket];
449          hashTable[bucket] = valueEntry;
450        }
451      }
452    }
453
454    @Override
455    public boolean remove(@Nullable Object o) {
456      int smearedHash = Hashing.smearedHash(o);
457      int bucket = smearedHash & mask();
458      ValueEntry<K, V> prev = null;
459      for (ValueEntry<K, V> entry = hashTable[bucket]; entry != null;
460           prev = entry, entry = entry.nextInValueBucket) {
461        if (entry.matchesValue(o, smearedHash)) {
462          if (prev == null) {
463            // first entry in the bucket
464            hashTable[bucket] = entry.nextInValueBucket;
465          } else {
466            prev.nextInValueBucket = entry.nextInValueBucket;
467          }
468          deleteFromValueSet(entry);
469          deleteFromMultimap(entry);
470          size--;
471          modCount++;
472          return true;
473        }
474      }
475      return false;
476    }
477
478    @Override
479    public void clear() {
480      Arrays.fill(hashTable, null);
481      size = 0;
482      for (ValueSetLink<K, V> entry = firstEntry;
483           entry != this; entry = entry.getSuccessorInValueSet()) {
484        ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
485        deleteFromMultimap(valueEntry);
486      }
487      succeedsInValueSet(this, this);
488      modCount++;
489    }
490  }
491
492  @Override
493  Iterator<Map.Entry<K, V>> entryIterator() {
494    return new Iterator<Map.Entry<K, V>>() {
495      ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap;
496      ValueEntry<K, V> toRemove;
497
498      @Override
499      public boolean hasNext() {
500        return nextEntry != multimapHeaderEntry;
501      }
502
503      @Override
504      public Map.Entry<K, V> next() {
505        if (!hasNext()) {
506          throw new NoSuchElementException();
507        }
508        ValueEntry<K, V> result = nextEntry;
509        toRemove = result;
510        nextEntry = nextEntry.successorInMultimap;
511        return result;
512      }
513
514      @Override
515      public void remove() {
516        checkRemove(toRemove != null);
517        LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
518        toRemove = null;
519      }
520    };
521  }
522
523  @Override
524  Iterator<V> valueIterator() {
525    return Maps.valueIterator(entryIterator());
526  }
527
528  @Override
529  public void clear() {
530    super.clear();
531    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
532  }
533
534  /**
535   * @serialData the expected values per key, the number of distinct keys,
536   * the number of entries, and the entries in order
537   */
538  @GwtIncompatible("java.io.ObjectOutputStream")
539  private void writeObject(ObjectOutputStream stream) throws IOException {
540    stream.defaultWriteObject();
541    stream.writeInt(valueSetCapacity);
542    stream.writeInt(keySet().size());
543    for (K key : keySet()) {
544      stream.writeObject(key);
545    }
546    stream.writeInt(size());
547    for (Map.Entry<K, V> entry : entries()) {
548      stream.writeObject(entry.getKey());
549      stream.writeObject(entry.getValue());
550    }
551  }
552
553  @GwtIncompatible("java.io.ObjectInputStream")
554  private void readObject(ObjectInputStream stream)
555      throws IOException, ClassNotFoundException {
556    stream.defaultReadObject();
557    multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
558    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
559    valueSetCapacity = stream.readInt();
560    int distinctKeys = stream.readInt();
561    Map<K, Collection<V>> map =
562        new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys));
563    for (int i = 0; i < distinctKeys; i++) {
564      @SuppressWarnings("unchecked")
565      K key = (K) stream.readObject();
566      map.put(key, createCollection(key));
567    }
568    int entries = stream.readInt();
569    for (int i = 0; i < entries; i++) {
570      @SuppressWarnings("unchecked")
571      K key = (K) stream.readObject();
572      @SuppressWarnings("unchecked")
573      V value = (V) stream.readObject();
574      map.get(key).add(value);
575    }
576    setMap(map);
577  }
578
579  @GwtIncompatible("java serialization not supported")
580  private static final long serialVersionUID = 1;
581}
582