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