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