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.checkArgument;
020
021import com.google.common.annotations.GwtCompatible;
022import com.google.common.annotations.GwtIncompatible;
023import com.google.common.annotations.VisibleForTesting;
024import com.google.common.base.Objects;
025import com.google.common.primitives.Ints;
026
027import java.io.IOException;
028import java.io.ObjectInputStream;
029import java.io.ObjectOutputStream;
030import java.util.Arrays;
031import java.util.Collection;
032import java.util.ConcurrentModificationException;
033import java.util.Iterator;
034import java.util.LinkedHashMap;
035import java.util.LinkedHashSet;
036import java.util.Map;
037import java.util.NoSuchElementException;
038import java.util.Set;
039
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 * "http://code.google.com/p/guava-libraries/wiki/NewCollectionTypesExplained#Multimap">
075 * {@code Multimap}</a>.
076 *
077 * @author Jared Levy
078 * @author Louis Wasserman
079 * @since 2.0 (imported from Google Collections Library)
080 */
081@GwtCompatible(serializable = true, emulated = true)
082public final class LinkedHashMultimap<K, V> extends AbstractSetMultimap<K, V> {
083
084  /**
085   * Creates a new, empty {@code LinkedHashMultimap} with the default initial
086   * capacities.
087   */
088  public static <K, V> LinkedHashMultimap<K, V> create() {
089    return new LinkedHashMultimap<K, V>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
090  }
091
092  /**
093   * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold
094   * the specified numbers of keys and values without rehashing.
095   *
096   * @param expectedKeys the expected number of distinct keys
097   * @param expectedValuesPerKey the expected average number of values per key
098   * @throws IllegalArgumentException if {@code expectedKeys} or {@code
099   *      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 row 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  private static final class ValueEntry<K, V> extends AbstractMapEntry<K, V>
158      implements ValueSetLink<K, V> {
159    final K key;
160    final V value;
161    final int valueHash;
162
163    @Nullable ValueEntry<K, V> nextInValueSetHashRow;
164
165    ValueSetLink<K, V> predecessorInValueSet;
166    ValueSetLink<K, V> successorInValueSet;
167
168    ValueEntry<K, V> predecessorInMultimap;
169    ValueEntry<K, V> successorInMultimap;
170
171    ValueEntry(@Nullable K key, @Nullable V value, int valueHash,
172        @Nullable ValueEntry<K, V> nextInValueSetHashRow) {
173      this.key = key;
174      this.value = value;
175      this.valueHash = valueHash;
176      this.nextInValueSetHashRow = nextInValueSetHashRow;
177    }
178
179    @Override
180    public K getKey() {
181      return key;
182    }
183
184    @Override
185    public V getValue() {
186      return value;
187    }
188
189    @Override
190    public ValueSetLink<K, V> getPredecessorInValueSet() {
191      return predecessorInValueSet;
192    }
193
194    @Override
195    public ValueSetLink<K, V> getSuccessorInValueSet() {
196      return successorInValueSet;
197    }
198
199    @Override
200    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
201      predecessorInValueSet = entry;
202    }
203
204    @Override
205    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
206      successorInValueSet = entry;
207    }
208
209    public ValueEntry<K, V> getPredecessorInMultimap() {
210      return predecessorInMultimap;
211    }
212
213    public ValueEntry<K, V> getSuccessorInMultimap() {
214      return successorInMultimap;
215    }
216
217    public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
218      this.successorInMultimap = multimapSuccessor;
219    }
220
221    public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
222      this.predecessorInMultimap = multimapPredecessor;
223    }
224  }
225
226  private static final int DEFAULT_KEY_CAPACITY = 16;
227  private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
228
229  private static final int MAX_VALUE_SET_TABLE_SIZE = Ints.MAX_POWER_OF_TWO;
230
231  @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
232  private transient ValueEntry<K, V> multimapHeaderEntry;
233
234  private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
235    super(new LinkedHashMap<K, Collection<V>>(keyCapacity));
236
237    checkArgument(valueSetCapacity >= 0,
238        "expectedValuesPerKey must be >= 0 but was %s", valueSetCapacity);
239
240    this.valueSetCapacity = valueSetCapacity;
241    this.multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
242    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
243  }
244
245  /**
246   * {@inheritDoc}
247   *
248   * <p>Creates an empty {@code LinkedHashSet} for a collection of values for
249   * one key.
250   *
251   * @return a new {@code LinkedHashSet} containing a collection of values for
252   *     one key
253   */
254  @Override
255  Set<V> createCollection() {
256    return new LinkedHashSet<V>(valueSetCapacity);
257  }
258
259  /**
260   * {@inheritDoc}
261   *
262   * <p>Creates a decorated insertion-ordered set that also keeps track of the
263   * order in which key-value pairs are added to the multimap.
264   *
265   * @param key key to associate with values in the collection
266   * @return a new decorated set containing a collection of values for one key
267   */
268  @Override
269  Collection<V> createCollection(K key) {
270    return new ValueSet(key, valueSetCapacity);
271  }
272
273  /**
274   * {@inheritDoc}
275   *
276   * <p>If {@code values} is not empty and the multimap already contains a
277   * mapping for {@code key}, the {@code keySet()} ordering is unchanged.
278   * However, the provided values always come last in the {@link #entries()} and
279   * {@link #values()} iteration orderings.
280   */
281  @Override
282  public Set<V> replaceValues(K key, Iterable<? extends V> values) {
283    return super.replaceValues(key, values);
284  }
285
286  /**
287   * Returns a set of all key-value pairs. Changes to the returned set will
288   * update the underlying multimap, and vice versa. The entries set does not
289   * support the {@code add} or {@code addAll} operations.
290   *
291   * <p>The iterator generated by the returned set traverses the entries in the
292   * order they were added to the multimap.
293   *
294   * <p>Each entry is an immutable snapshot of a key-value mapping in the
295   * multimap, taken at the time the entry is returned by a method call to the
296   * collection or its iterator.
297   */
298  @Override public Set<Map.Entry<K, V>> entries() {
299    return super.entries();
300  }
301
302  /**
303   * Returns a collection of all values in the multimap. Changes to the returned
304   * collection will update the underlying multimap, and vice versa.
305   *
306   * <p>The iterator generated by the returned collection traverses the values
307   * in the order they were added to the multimap.
308   */
309  @Override public Collection<V> values() {
310    return super.values();
311  }
312
313  @VisibleForTesting
314  final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
315    /*
316     * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
317     * consumption.
318     */
319
320    private final K key;
321    private ValueEntry<K, V>[] hashTable;
322    private int size = 0;
323    private int modCount = 0;
324
325    // We use the set object itself as the end of the linked list, avoiding an unnecessary
326    // entry object per key.
327    private ValueSetLink<K, V> firstEntry;
328    private ValueSetLink<K, V> lastEntry;
329
330    ValueSet(K key, int expectedValues) {
331      this.key = key;
332      this.firstEntry = this;
333      this.lastEntry = this;
334      // Round expected values up to a power of 2 to get the table size.
335      int tableSize = Integer.highestOneBit(Math.max(expectedValues, 2) - 1) << 1;
336      if (tableSize < 0) {
337        tableSize = MAX_VALUE_SET_TABLE_SIZE;
338      }
339
340      @SuppressWarnings("unchecked")
341      ValueEntry<K, V>[] hashTable = new ValueEntry[tableSize];
342      this.hashTable = hashTable;
343    }
344
345    @Override
346    public ValueSetLink<K, V> getPredecessorInValueSet() {
347      return lastEntry;
348    }
349
350    @Override
351    public ValueSetLink<K, V> getSuccessorInValueSet() {
352      return firstEntry;
353    }
354
355    @Override
356    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
357      lastEntry = entry;
358    }
359
360    @Override
361    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
362      firstEntry = entry;
363    }
364
365    @Override
366    public Iterator<V> iterator() {
367      return new Iterator<V>() {
368        ValueSetLink<K, V> nextEntry = firstEntry;
369        ValueEntry<K, V> toRemove;
370        int expectedModCount = modCount;
371
372        private void checkForComodification() {
373          if (modCount != expectedModCount) {
374            throw new ConcurrentModificationException();
375          }
376        }
377
378        @Override
379        public boolean hasNext() {
380          checkForComodification();
381          return nextEntry != ValueSet.this;
382        }
383
384        @Override
385        public V next() {
386          if (!hasNext()) {
387            throw new NoSuchElementException();
388          }
389          ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
390          V result = entry.getValue();
391          toRemove = entry;
392          nextEntry = entry.getSuccessorInValueSet();
393          return result;
394        }
395
396        @Override
397        public void remove() {
398          checkForComodification();
399          Iterators.checkRemove(toRemove != null);
400          Object o = toRemove.getValue();
401          int hash = (o == null) ? 0 : o.hashCode();
402          int row = Hashing.smear(hash) & (hashTable.length - 1);
403          ValueEntry<K, V> prev = null;
404          for (ValueEntry<K, V> entry = hashTable[row]; entry != null;
405               prev = entry, entry = entry.nextInValueSetHashRow) {
406            if (entry == toRemove) {
407              if (prev == null) {
408                // first entry in row
409                hashTable[row] = entry.nextInValueSetHashRow;
410              } else {
411                prev.nextInValueSetHashRow = entry.nextInValueSetHashRow;
412              }
413              deleteFromValueSet(toRemove);
414              deleteFromMultimap(toRemove);
415              size--;
416              expectedModCount = ++modCount;
417              break;
418            }
419          }
420          toRemove = null;
421        }
422      };
423    }
424
425    @Override
426    public int size() {
427      return size;
428    }
429
430    @Override
431    public boolean contains(@Nullable Object o) {
432      int hash = (o == null) ? 0 : o.hashCode();
433      int row = Hashing.smear(hash) & (hashTable.length - 1);
434
435      for (ValueEntry<K, V> entry = hashTable[row]; entry != null;
436          entry = entry.nextInValueSetHashRow) {
437        if (hash == entry.valueHash && Objects.equal(o, entry.getValue())) {
438          return true;
439        }
440      }
441      return false;
442    }
443
444    /**
445     * The threshold above which the hash table should be rebuilt.
446     */
447    @VisibleForTesting int threshold() {
448      return hashTable.length; // load factor of 1.0
449    }
450
451    @Override
452    public boolean add(@Nullable V value) {
453      int hash = (value == null) ? 0 : value.hashCode();
454      int row = Hashing.smear(hash) & (hashTable.length - 1);
455
456      ValueEntry<K, V> rowHead = hashTable[row];
457      for (ValueEntry<K, V> entry = rowHead; entry != null;
458          entry = entry.nextInValueSetHashRow) {
459        if (hash == entry.valueHash && Objects.equal(value, entry.getValue())) {
460          return false;
461        }
462      }
463
464      ValueEntry<K, V> newEntry = new ValueEntry<K, V>(key, value, hash, rowHead);
465      succeedsInValueSet(lastEntry, newEntry);
466      succeedsInValueSet(newEntry, this);
467      succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
468      succeedsInMultimap(newEntry, multimapHeaderEntry);
469      hashTable[row] = newEntry;
470      size++;
471      modCount++;
472      rehashIfNecessary();
473      return true;
474    }
475
476    private void rehashIfNecessary() {
477      if (size > threshold() && hashTable.length < MAX_VALUE_SET_TABLE_SIZE) {
478        @SuppressWarnings("unchecked")
479        ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2];
480        this.hashTable = hashTable;
481        int mask = hashTable.length - 1;
482        for (ValueSetLink<K, V> entry = firstEntry;
483              entry != this; entry = entry.getSuccessorInValueSet()) {
484          ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
485          int row = Hashing.smear(valueEntry.valueHash) & mask;
486          valueEntry.nextInValueSetHashRow = hashTable[row];
487          hashTable[row] = valueEntry;
488        }
489      }
490    }
491
492    @Override
493    public boolean remove(@Nullable Object o) {
494      int hash = (o == null) ? 0 : o.hashCode();
495      int row = Hashing.smear(hash) & (hashTable.length - 1);
496
497      ValueEntry<K, V> prev = null;
498      for (ValueEntry<K, V> entry = hashTable[row]; entry != null;
499           prev = entry, entry = entry.nextInValueSetHashRow) {
500        if (hash == entry.valueHash && Objects.equal(o, entry.getValue())) {
501          if (prev == null) {
502            // first entry in the row
503            hashTable[row] = entry.nextInValueSetHashRow;
504          } else {
505            prev.nextInValueSetHashRow = entry.nextInValueSetHashRow;
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; entry = entry.getSuccessorInValueSet()) {
523        ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
524        deleteFromMultimap(valueEntry);
525      }
526      succeedsInValueSet(this, this);
527      modCount++;
528    }
529  }
530
531  @Override
532  Iterator<Map.Entry<K, V>> createEntryIterator() {
533    return new Iterator<Map.Entry<K, V>>() {
534      ValueEntry<K, V> nextEntry = multimapHeaderEntry.successorInMultimap;
535      ValueEntry<K, V> toRemove;
536
537      @Override
538      public boolean hasNext() {
539        return nextEntry != multimapHeaderEntry;
540      }
541
542      @Override
543      public Map.Entry<K, V> next() {
544        if (!hasNext()) {
545          throw new NoSuchElementException();
546        }
547        ValueEntry<K, V> result = nextEntry;
548        toRemove = result;
549        nextEntry = nextEntry.successorInMultimap;
550        return result;
551      }
552
553      @Override
554      public void remove() {
555        Iterators.checkRemove(toRemove != null);
556        LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
557        toRemove = null;
558      }
559    };
560  }
561
562  @Override
563  public void clear() {
564    super.clear();
565    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
566  }
567
568  /**
569   * @serialData the expected values per key, the number of distinct keys,
570   * the number of entries, and the entries in order
571   */
572  @GwtIncompatible("java.io.ObjectOutputStream")
573  private void writeObject(ObjectOutputStream stream) throws IOException {
574    stream.defaultWriteObject();
575    stream.writeInt(valueSetCapacity);
576    stream.writeInt(keySet().size());
577    for (K key : keySet()) {
578      stream.writeObject(key);
579    }
580    stream.writeInt(size());
581    for (Map.Entry<K, V> entry : entries()) {
582      stream.writeObject(entry.getKey());
583      stream.writeObject(entry.getValue());
584    }
585  }
586
587  @GwtIncompatible("java.io.ObjectInputStream")
588  private void readObject(ObjectInputStream stream)
589      throws IOException, ClassNotFoundException {
590    stream.defaultReadObject();
591    multimapHeaderEntry = new ValueEntry<K, V>(null, null, 0, null);
592    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
593    valueSetCapacity = stream.readInt();
594    int distinctKeys = stream.readInt();
595    Map<K, Collection<V>> map =
596        new LinkedHashMap<K, Collection<V>>(Maps.capacity(distinctKeys));
597    for (int i = 0; i < distinctKeys; i++) {
598      @SuppressWarnings("unchecked")
599      K key = (K) stream.readObject();
600      map.put(key, createCollection(key));
601    }
602    int entries = stream.readInt();
603    for (int i = 0; i < entries; i++) {
604      @SuppressWarnings("unchecked")
605      K key = (K) stream.readObject();
606      @SuppressWarnings("unchecked")
607      V value = (V) stream.readObject();
608      map.get(key).add(value);
609    }
610    setMap(map);
611  }
612
613  @GwtIncompatible("java serialization not supported")
614  private static final long serialVersionUID = 1;
615}