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.J2ktIncompatible;
026import com.google.common.annotations.VisibleForTesting;
027import com.google.common.base.Objects;
028import com.google.errorprone.annotations.CanIgnoreReturnValue;
029import com.google.j2objc.annotations.WeakOuter;
030import java.io.IOException;
031import java.io.ObjectInputStream;
032import java.io.ObjectOutputStream;
033import java.util.Arrays;
034import java.util.Collection;
035import java.util.ConcurrentModificationException;
036import java.util.Iterator;
037import java.util.Map;
038import java.util.Map.Entry;
039import java.util.NoSuchElementException;
040import java.util.Set;
041import org.jspecify.annotations.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)
082public final class LinkedHashMultimap<K extends @Nullable Object, V extends @Nullable Object>
083    extends LinkedHashMultimapGwtSerializationDependencies<K, V> {
084
085  /** Creates a new, empty {@code LinkedHashMultimap} with the default initial capacities. */
086  public static <K extends @Nullable Object, V extends @Nullable Object>
087      LinkedHashMultimap<K, V> create() {
088    return new LinkedHashMultimap<>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
089  }
090
091  /**
092   * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold the specified
093   * numbers of keys and values without rehashing.
094   *
095   * @param expectedKeys the expected number of distinct keys
096   * @param expectedValuesPerKey the expected average number of values per key
097   * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is
098   *     negative
099   */
100  public static <K extends @Nullable Object, V extends @Nullable Object>
101      LinkedHashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) {
102    return new LinkedHashMultimap<>(
103        Maps.capacity(expectedKeys), Maps.capacity(expectedValuesPerKey));
104  }
105
106  /**
107   * Constructs a {@code LinkedHashMultimap} with the same mappings as the specified multimap. If a
108   * key-value mapping appears multiple times in the input multimap, it only appears once in the
109   * constructed multimap. The new multimap has the same {@link Multimap#entries()} iteration order
110   * as the input multimap, except for excluding duplicate mappings.
111   *
112   * @param multimap the multimap whose contents are copied to this multimap
113   */
114  public static <K extends @Nullable Object, V extends @Nullable Object>
115      LinkedHashMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
116    LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY);
117    result.putAll(multimap);
118    return result;
119  }
120
121  private interface ValueSetLink<K extends @Nullable Object, V extends @Nullable Object> {
122    ValueSetLink<K, V> getPredecessorInValueSet();
123
124    ValueSetLink<K, V> getSuccessorInValueSet();
125
126    void setPredecessorInValueSet(ValueSetLink<K, V> entry);
127
128    void setSuccessorInValueSet(ValueSetLink<K, V> entry);
129  }
130
131  private static <K extends @Nullable Object, V extends @Nullable Object> void succeedsInValueSet(
132      ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) {
133    pred.setSuccessorInValueSet(succ);
134    succ.setPredecessorInValueSet(pred);
135  }
136
137  private static <K extends @Nullable Object, V extends @Nullable Object> 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 extends @Nullable Object, V extends @Nullable Object> void deleteFromValueSet(
144      ValueSetLink<K, V> entry) {
145    succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet());
146  }
147
148  private static <K extends @Nullable Object, V extends @Nullable Object> void deleteFromMultimap(
149      ValueEntry<K, V> entry) {
150    succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap());
151  }
152
153  /**
154   * LinkedHashMultimap entries are in no less than three coexisting linked lists: a bucket in the
155   * hash table for a {@code Set<V>} associated with a key, the linked list of insertion-ordered
156   * entries in that {@code Set<V>}, and the linked list of entries in the LinkedHashMultimap as a
157   * whole.
158   */
159  @VisibleForTesting
160  static final class ValueEntry<K extends @Nullable Object, V extends @Nullable Object>
161      extends ImmutableEntry<K, V> implements ValueSetLink<K, V> {
162    final int smearedValueHash;
163
164    @Nullable ValueEntry<K, V> nextInValueBucket;
165    /*
166     * The *InValueSet and *InMultimap fields below are null after construction, but we almost
167     * always call succeedsIn*() to initialize them immediately thereafter.
168     *
169     * The exception is the *InValueSet fields of multimapHeaderEntry, which are never set. (That
170     * works out fine as long as we continue to be careful not to try to delete them or iterate
171     * past them.)
172     *
173     * We could consider "lying" and omitting @CheckNotNull from all these fields. Normally, I'm not
174     * a fan of that: What if we someday implement (presumably to be enabled during tests only)
175     * bytecode rewriting that checks for any null value that passes through an API with a
176     * known-non-null type? But that particular problem might not arise here, since we're not
177     * actually reading from the fields in any case in which they might be null (as proven by the
178     * requireNonNull checks below). Plus, we're *already* lying here, since newHeader passes a null
179     * key and value, which we pass to the superconstructor, even though the key and value type for
180     * a given entry might not include null. The right fix for the header problems is probably to
181     * define a separate MultimapLink interface with a separate "header" implementation, which
182     * hopefully could avoid implementing Entry or ValueSetLink at all. (But note that that approach
183     * requires us to define extra classes -- unfortunate under Android.) *Then* we could consider
184     * lying about the fields below on the grounds that we always initialize them just after the
185     * constructor -- an example of the kind of lying that our hypothetical bytecode rewriter would
186     * already have to deal with, thanks to DI frameworks that perform field and method injection,
187     * frameworks like Android that define post-construct hooks like Activity.onCreate, etc.
188     */
189
190    private @Nullable ValueSetLink<K, V> predecessorInValueSet;
191    private @Nullable ValueSetLink<K, V> successorInValueSet;
192
193    private @Nullable ValueEntry<K, V> predecessorInMultimap;
194    private @Nullable ValueEntry<K, V> successorInMultimap;
195
196    ValueEntry(
197        @ParametricNullness K key,
198        @ParametricNullness V value,
199        int smearedValueHash,
200        @Nullable ValueEntry<K, V> nextInValueBucket) {
201      super(key, value);
202      this.smearedValueHash = smearedValueHash;
203      this.nextInValueBucket = nextInValueBucket;
204    }
205
206    @SuppressWarnings("nullness") // see the comment on the class fields, especially about newHeader
207    static <K extends @Nullable Object, V extends @Nullable Object> ValueEntry<K, V> newHeader() {
208      return new ValueEntry<>(null, null, 0, null);
209    }
210
211    boolean matchesValue(@Nullable Object v, int smearedVHash) {
212      return smearedValueHash == smearedVHash && Objects.equal(getValue(), v);
213    }
214
215    @Override
216    public ValueSetLink<K, V> getPredecessorInValueSet() {
217      return requireNonNull(predecessorInValueSet); // see the comment on the class fields
218    }
219
220    @Override
221    public ValueSetLink<K, V> getSuccessorInValueSet() {
222      return requireNonNull(successorInValueSet); // see the comment on the class fields
223    }
224
225    @Override
226    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
227      predecessorInValueSet = entry;
228    }
229
230    @Override
231    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
232      successorInValueSet = entry;
233    }
234
235    public ValueEntry<K, V> getPredecessorInMultimap() {
236      return requireNonNull(predecessorInMultimap); // see the comment on the class fields
237    }
238
239    public ValueEntry<K, V> getSuccessorInMultimap() {
240      return requireNonNull(successorInMultimap); // see the comment on the class fields
241    }
242
243    public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
244      this.successorInMultimap = multimapSuccessor;
245    }
246
247    public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
248      this.predecessorInMultimap = multimapPredecessor;
249    }
250  }
251
252  private static final int DEFAULT_KEY_CAPACITY = 16;
253  private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
254  @VisibleForTesting static final double VALUE_SET_LOAD_FACTOR = 1.0;
255
256  @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
257  private transient ValueEntry<K, V> multimapHeaderEntry;
258
259  private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
260    super(Platform.<K, Collection<V>>newLinkedHashMapWithExpectedSize(keyCapacity));
261    checkNonnegative(valueSetCapacity, "expectedValuesPerKey");
262
263    this.valueSetCapacity = valueSetCapacity;
264    this.multimapHeaderEntry = ValueEntry.newHeader();
265    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
266  }
267
268  /**
269   * {@inheritDoc}
270   *
271   * <p>Creates an empty {@code LinkedHashSet} for a collection of values for one key.
272   *
273   * @return a new {@code LinkedHashSet} containing a collection of values for one key
274   */
275  @Override
276  Set<V> createCollection() {
277    return Platform.newLinkedHashSetWithExpectedSize(valueSetCapacity);
278  }
279
280  /**
281   * {@inheritDoc}
282   *
283   * <p>Creates a decorated insertion-ordered set that also keeps track of the order in which
284   * key-value pairs are added to the multimap.
285   *
286   * @param key key to associate with values in the collection
287   * @return a new decorated set containing a collection of values for one key
288   */
289  @Override
290  Collection<V> createCollection(@ParametricNullness K key) {
291    return new ValueSet(key, valueSetCapacity);
292  }
293
294  /**
295   * {@inheritDoc}
296   *
297   * <p>If {@code values} is not empty and the multimap already contains a mapping for {@code key},
298   * the {@code keySet()} ordering is unchanged. However, the provided values always come last in
299   * the {@link #entries()} and {@link #values()} iteration orderings.
300   */
301  @CanIgnoreReturnValue
302  @Override
303  public Set<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) {
304    return super.replaceValues(key, values);
305  }
306
307  /**
308   * Returns a set of all key-value pairs. Changes to the returned set will update the underlying
309   * multimap, and vice versa. The entries set does not support the {@code add} or {@code addAll}
310   * operations.
311   *
312   * <p>The iterator generated by the returned set traverses the entries in the order they were
313   * added to the multimap.
314   *
315   * <p>Each entry is an immutable snapshot of a key-value mapping in the multimap, taken at the
316   * time the entry is returned by a method call to the collection or its iterator.
317   */
318  @Override
319  public Set<Entry<K, V>> entries() {
320    return super.entries();
321  }
322
323  /**
324   * Returns a view collection of all <i>distinct</i> keys contained in this multimap. Note that the
325   * key set contains a key if and only if this multimap maps that key to at least one value.
326   *
327   * <p>The iterator generated by the returned set traverses the keys in the order they were first
328   * added to the multimap.
329   *
330   * <p>Changes to the returned set will update the underlying multimap, and vice versa. However,
331   * <i>adding</i> to the returned set is not possible.
332   */
333  @Override
334  public Set<K> keySet() {
335    return super.keySet();
336  }
337
338  /**
339   * Returns a collection of all values in the multimap. Changes to the returned collection will
340   * update the underlying multimap, and vice versa.
341   *
342   * <p>The iterator generated by the returned collection traverses the values in the order they
343   * were added to the multimap.
344   */
345  @Override
346  public Collection<V> values() {
347    return super.values();
348  }
349
350  @VisibleForTesting
351  @WeakOuter
352  final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
353    /*
354     * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
355     * consumption.
356     */
357
358    @ParametricNullness private final K key;
359    @VisibleForTesting @Nullable ValueEntry<K, V>[] hashTable;
360    private int size = 0;
361    private int modCount = 0;
362
363    // We use the set object itself as the end of the linked list, avoiding an unnecessary
364    // entry object per key.
365    private ValueSetLink<K, V> firstEntry;
366    private ValueSetLink<K, V> lastEntry;
367
368    ValueSet(@ParametricNullness K key, int expectedValues) {
369      this.key = key;
370      this.firstEntry = this;
371      this.lastEntry = this;
372      // Round expected values up to a power of 2 to get the table size.
373      int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR);
374
375      @SuppressWarnings({"rawtypes", "unchecked"})
376      @Nullable
377      ValueEntry<K, V>[] hashTable = new @Nullable ValueEntry[tableSize];
378      this.hashTable = hashTable;
379    }
380
381    private int mask() {
382      return hashTable.length - 1;
383    }
384
385    @Override
386    public ValueSetLink<K, V> getPredecessorInValueSet() {
387      return lastEntry;
388    }
389
390    @Override
391    public ValueSetLink<K, V> getSuccessorInValueSet() {
392      return firstEntry;
393    }
394
395    @Override
396    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
397      lastEntry = entry;
398    }
399
400    @Override
401    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
402      firstEntry = entry;
403    }
404
405    @Override
406    public Iterator<V> iterator() {
407      return new Iterator<V>() {
408        ValueSetLink<K, V> nextEntry = firstEntry;
409        @Nullable ValueEntry<K, V> toRemove;
410        int expectedModCount = modCount;
411
412        private void checkForComodification() {
413          if (modCount != expectedModCount) {
414            throw new ConcurrentModificationException();
415          }
416        }
417
418        @Override
419        public boolean hasNext() {
420          checkForComodification();
421          return nextEntry != ValueSet.this;
422        }
423
424        @Override
425        @ParametricNullness
426        public V next() {
427          if (!hasNext()) {
428            throw new NoSuchElementException();
429          }
430          ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
431          V result = entry.getValue();
432          toRemove = entry;
433          nextEntry = entry.getSuccessorInValueSet();
434          return result;
435        }
436
437        @Override
438        public void remove() {
439          checkForComodification();
440          checkState(toRemove != null, "no calls to next() since the last call to remove()");
441          ValueSet.this.remove(toRemove.getValue());
442          expectedModCount = modCount;
443          toRemove = null;
444        }
445      };
446    }
447
448    @Override
449    public int size() {
450      return size;
451    }
452
453    @Override
454    public boolean contains(@Nullable Object o) {
455      int smearedHash = Hashing.smearedHash(o);
456      for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()];
457          entry != null;
458          entry = entry.nextInValueBucket) {
459        if (entry.matchesValue(o, smearedHash)) {
460          return true;
461        }
462      }
463      return false;
464    }
465
466    @Override
467    public boolean add(@ParametricNullness V value) {
468      int smearedHash = Hashing.smearedHash(value);
469      int bucket = smearedHash & mask();
470      ValueEntry<K, V> rowHead = hashTable[bucket];
471      for (ValueEntry<K, V> entry = rowHead; entry != null; entry = entry.nextInValueBucket) {
472        if (entry.matchesValue(value, smearedHash)) {
473          return false;
474        }
475      }
476
477      ValueEntry<K, V> newEntry = new ValueEntry<>(key, value, smearedHash, rowHead);
478      succeedsInValueSet(lastEntry, newEntry);
479      succeedsInValueSet(newEntry, this);
480      succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
481      succeedsInMultimap(newEntry, multimapHeaderEntry);
482      hashTable[bucket] = newEntry;
483      size++;
484      modCount++;
485      rehashIfNecessary();
486      return true;
487    }
488
489    private void rehashIfNecessary() {
490      if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR)) {
491        @SuppressWarnings("unchecked")
492        ValueEntry<K, V>[] hashTable =
493            (ValueEntry<K, V>[]) 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(@Nullable 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      @Nullable 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  @J2ktIncompatible
596  private void writeObject(ObjectOutputStream stream) throws IOException {
597    stream.defaultWriteObject();
598    stream.writeInt(keySet().size());
599    for (K key : keySet()) {
600      stream.writeObject(key);
601    }
602    stream.writeInt(size());
603    for (Entry<K, V> entry : entries()) {
604      stream.writeObject(entry.getKey());
605      stream.writeObject(entry.getValue());
606    }
607  }
608
609  @GwtIncompatible // java.io.ObjectInputStream
610  @J2ktIncompatible
611  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
612    stream.defaultReadObject();
613    multimapHeaderEntry = ValueEntry.newHeader();
614    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
615    valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
616    int distinctKeys = stream.readInt();
617    Map<K, Collection<V>> map = Platform.newLinkedHashMapWithExpectedSize(12);
618    for (int i = 0; i < distinctKeys; i++) {
619      @SuppressWarnings("unchecked")
620      K key = (K) stream.readObject();
621      map.put(key, createCollection(key));
622    }
623    int entries = stream.readInt();
624    for (int i = 0; i < entries; i++) {
625      @SuppressWarnings("unchecked")
626      K key = (K) stream.readObject();
627      @SuppressWarnings("unchecked")
628      V value = (V) stream.readObject();
629      /*
630       * requireNonNull is safe for a properly serialized multimap: We've already inserted a
631       * collection for each key that we expect.
632       */
633      requireNonNull(map.get(key)).add(value);
634    }
635    setMap(map);
636  }
637
638  @GwtIncompatible // java serialization not supported
639  @J2ktIncompatible
640  private static final long serialVersionUID = 1;
641}