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.base.Preconditions.checkNotNull;
021import static com.google.common.base.Predicates.compose;
022import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
023import static com.google.common.collect.CollectPreconditions.checkNonnegative;
024import static com.google.common.collect.NullnessCasts.uncheckedCastNullableTToT;
025import static java.util.Collections.singletonMap;
026import static java.util.Objects.requireNonNull;
027
028import com.google.common.annotations.GwtCompatible;
029import com.google.common.annotations.GwtIncompatible;
030import com.google.common.annotations.J2ktIncompatible;
031import com.google.common.base.Converter;
032import com.google.common.base.Equivalence;
033import com.google.common.base.Function;
034import com.google.common.base.Objects;
035import com.google.common.base.Preconditions;
036import com.google.common.base.Predicate;
037import com.google.common.base.Predicates;
038import com.google.common.collect.MapDifference.ValueDifference;
039import com.google.common.primitives.Ints;
040import com.google.errorprone.annotations.CanIgnoreReturnValue;
041import com.google.j2objc.annotations.RetainedWith;
042import com.google.j2objc.annotations.Weak;
043import com.google.j2objc.annotations.WeakOuter;
044import java.io.Serializable;
045import java.util.AbstractCollection;
046import java.util.AbstractMap;
047import java.util.Collection;
048import java.util.Collections;
049import java.util.Comparator;
050import java.util.EnumMap;
051import java.util.Enumeration;
052import java.util.HashMap;
053import java.util.IdentityHashMap;
054import java.util.Iterator;
055import java.util.LinkedHashMap;
056import java.util.Map;
057import java.util.Map.Entry;
058import java.util.NavigableMap;
059import java.util.NavigableSet;
060import java.util.Properties;
061import java.util.Set;
062import java.util.SortedMap;
063import java.util.SortedSet;
064import java.util.TreeMap;
065import java.util.concurrent.ConcurrentHashMap;
066import java.util.concurrent.ConcurrentMap;
067import javax.annotation.CheckForNull;
068import org.checkerframework.checker.nullness.qual.NonNull;
069import org.checkerframework.checker.nullness.qual.Nullable;
070
071/**
072 * Static utility methods pertaining to {@link Map} instances (including instances of {@link
073 * SortedMap}, {@link BiMap}, etc.). Also see this class's counterparts {@link Lists}, {@link Sets}
074 * and {@link Queues}.
075 *
076 * <p>See the Guava User Guide article on <a href=
077 * "https://github.com/google/guava/wiki/CollectionUtilitiesExplained#maps">{@code Maps}</a>.
078 *
079 * @author Kevin Bourrillion
080 * @author Mike Bostock
081 * @author Isaac Shum
082 * @author Louis Wasserman
083 * @since 2.0
084 */
085@GwtCompatible(emulated = true)
086@ElementTypesAreNonnullByDefault
087public final class Maps {
088  private Maps() {}
089
090  private enum EntryFunction implements Function<Entry<?, ?>, @Nullable Object> {
091    KEY {
092      @Override
093      @CheckForNull
094      public Object apply(Entry<?, ?> entry) {
095        return entry.getKey();
096      }
097    },
098    VALUE {
099      @Override
100      @CheckForNull
101      public Object apply(Entry<?, ?> entry) {
102        return entry.getValue();
103      }
104    };
105  }
106
107  @SuppressWarnings("unchecked")
108  static <K extends @Nullable Object> Function<Entry<K, ?>, K> keyFunction() {
109    return (Function) EntryFunction.KEY;
110  }
111
112  @SuppressWarnings("unchecked")
113  static <V extends @Nullable Object> Function<Entry<?, V>, V> valueFunction() {
114    return (Function) EntryFunction.VALUE;
115  }
116
117  static <K extends @Nullable Object, V extends @Nullable Object> Iterator<K> keyIterator(
118      Iterator<Entry<K, V>> entryIterator) {
119    return new TransformedIterator<Entry<K, V>, K>(entryIterator) {
120      @Override
121      @ParametricNullness
122      K transform(Entry<K, V> entry) {
123        return entry.getKey();
124      }
125    };
126  }
127
128  static <K extends @Nullable Object, V extends @Nullable Object> Iterator<V> valueIterator(
129      Iterator<Entry<K, V>> entryIterator) {
130    return new TransformedIterator<Entry<K, V>, V>(entryIterator) {
131      @Override
132      @ParametricNullness
133      V transform(Entry<K, V> entry) {
134        return entry.getValue();
135      }
136    };
137  }
138
139  /**
140   * Returns an immutable map instance containing the given entries. Internally, the returned map
141   * will be backed by an {@link EnumMap}.
142   *
143   * <p>The iteration order of the returned map follows the enum's iteration order, not the order in
144   * which the elements appear in the given map.
145   *
146   * @param map the map to make an immutable copy of
147   * @return an immutable map containing those entries
148   * @since 14.0
149   */
150  @GwtCompatible(serializable = true)
151  @J2ktIncompatible
152  public static <K extends Enum<K>, V> ImmutableMap<K, V> immutableEnumMap(
153      Map<K, ? extends V> map) {
154    if (map instanceof ImmutableEnumMap) {
155      @SuppressWarnings("unchecked") // safe covariant cast
156      ImmutableEnumMap<K, V> result = (ImmutableEnumMap<K, V>) map;
157      return result;
158    }
159    Iterator<? extends Entry<K, ? extends V>> entryItr = map.entrySet().iterator();
160    if (!entryItr.hasNext()) {
161      return ImmutableMap.of();
162    }
163    Entry<K, ? extends V> entry1 = entryItr.next();
164    K key1 = entry1.getKey();
165    V value1 = entry1.getValue();
166    checkEntryNotNull(key1, value1);
167    // Do something that works for j2cl, where we can't call getDeclaredClass():
168    EnumMap<K, V> enumMap = new EnumMap<>(singletonMap(key1, value1));
169    while (entryItr.hasNext()) {
170      Entry<K, ? extends V> entry = entryItr.next();
171      K key = entry.getKey();
172      V value = entry.getValue();
173      checkEntryNotNull(key, value);
174      enumMap.put(key, value);
175    }
176    return ImmutableEnumMap.asImmutable(enumMap);
177  }
178
179  /**
180   * Creates a <i>mutable</i>, empty {@code HashMap} instance.
181   *
182   * <p><b>Note:</b> if mutability is not required, use {@link ImmutableMap#of()} instead.
183   *
184   * <p><b>Note:</b> if {@code K} is an {@code enum} type, use {@link #newEnumMap} instead.
185   *
186   * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
187   * use the {@code HashMap} constructor directly, taking advantage of <a
188   * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
189   *
190   * @return a new, empty {@code HashMap}
191   */
192  public static <K extends @Nullable Object, V extends @Nullable Object>
193      HashMap<K, V> newHashMap() {
194    return new HashMap<>();
195  }
196
197  /**
198   * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as the specified map.
199   *
200   * <p><b>Note:</b> if mutability is not required, use {@link ImmutableMap#copyOf(Map)} instead.
201   *
202   * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link #newEnumMap} instead.
203   *
204   * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
205   * use the {@code HashMap} constructor directly, taking advantage of <a
206   * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
207   *
208   * @param map the mappings to be placed in the new map
209   * @return a new {@code HashMap} initialized with the mappings from {@code map}
210   */
211  public static <K extends @Nullable Object, V extends @Nullable Object> HashMap<K, V> newHashMap(
212      Map<? extends K, ? extends V> map) {
213    return new HashMap<>(map);
214  }
215
216  /**
217   * Creates a {@code HashMap} instance, with a high enough "initial capacity" that it <i>should</i>
218   * hold {@code expectedSize} elements without growth. This behavior cannot be broadly guaranteed,
219   * but it is observed to be true for OpenJDK 1.7. It also can't be guaranteed that the method
220   * isn't inadvertently <i>oversizing</i> the returned map.
221   *
222   * @param expectedSize the number of entries you expect to add to the returned map
223   * @return a new, empty {@code HashMap} with enough capacity to hold {@code expectedSize} entries
224   *     without resizing
225   * @throws IllegalArgumentException if {@code expectedSize} is negative
226   */
227  public static <K extends @Nullable Object, V extends @Nullable Object>
228      HashMap<K, V> newHashMapWithExpectedSize(int expectedSize) {
229    return new HashMap<>(capacity(expectedSize));
230  }
231
232  /**
233   * Returns a capacity that is sufficient to keep the map from being resized as long as it grows no
234   * larger than expectedSize and the load factor is ≥ its default (0.75).
235   */
236  static int capacity(int expectedSize) {
237    if (expectedSize < 3) {
238      checkNonnegative(expectedSize, "expectedSize");
239      return expectedSize + 1;
240    }
241    if (expectedSize < Ints.MAX_POWER_OF_TWO) {
242      // This seems to be consistent across JDKs. The capacity argument to HashMap and LinkedHashMap
243      // ends up being used to compute a "threshold" size, beyond which the internal table
244      // will be resized. That threshold is ceilingPowerOfTwo(capacity*loadFactor), where
245      // loadFactor is 0.75 by default. So with the calculation here we ensure that the
246      // threshold is equal to ceilingPowerOfTwo(expectedSize). There is a separate code
247      // path when the first operation on the new map is putAll(otherMap). There, prior to
248      // https://github.com/openjdk/jdk/commit/3e393047e12147a81e2899784b943923fc34da8e, a bug
249      // meant that sometimes a too-large threshold is calculated. However, this new threshold is
250      // independent of the initial capacity, except that it won't be lower than the threshold
251      // computed from that capacity. Because the internal table is only allocated on the first
252      // write, we won't see copying because of the new threshold. So it is always OK to use the
253      // calculation here.
254      return (int) Math.ceil(expectedSize / 0.75);
255    }
256    return Integer.MAX_VALUE; // any large value
257  }
258
259  /**
260   * Creates a <i>mutable</i>, empty, insertion-ordered {@code LinkedHashMap} instance.
261   *
262   * <p><b>Note:</b> if mutability is not required, use {@link ImmutableMap#of()} instead.
263   *
264   * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
265   * use the {@code LinkedHashMap} constructor directly, taking advantage of <a
266   * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
267   *
268   * @return a new, empty {@code LinkedHashMap}
269   */
270  public static <K extends @Nullable Object, V extends @Nullable Object>
271      LinkedHashMap<K, V> newLinkedHashMap() {
272    return new LinkedHashMap<>();
273  }
274
275  /**
276   * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance with the same
277   * mappings as the specified map.
278   *
279   * <p><b>Note:</b> if mutability is not required, use {@link ImmutableMap#copyOf(Map)} instead.
280   *
281   * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
282   * use the {@code LinkedHashMap} constructor directly, taking advantage of <a
283   * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
284   *
285   * @param map the mappings to be placed in the new map
286   * @return a new, {@code LinkedHashMap} initialized with the mappings from {@code map}
287   */
288  public static <K extends @Nullable Object, V extends @Nullable Object>
289      LinkedHashMap<K, V> newLinkedHashMap(Map<? extends K, ? extends V> map) {
290    return new LinkedHashMap<>(map);
291  }
292
293  /**
294   * Creates a {@code LinkedHashMap} instance, with a high enough "initial capacity" that it
295   * <i>should</i> hold {@code expectedSize} elements without growth. This behavior cannot be
296   * broadly guaranteed, but it is observed to be true for OpenJDK 1.7. It also can't be guaranteed
297   * that the method isn't inadvertently <i>oversizing</i> the returned map.
298   *
299   * @param expectedSize the number of entries you expect to add to the returned map
300   * @return a new, empty {@code LinkedHashMap} with enough capacity to hold {@code expectedSize}
301   *     entries without resizing
302   * @throws IllegalArgumentException if {@code expectedSize} is negative
303   * @since 19.0
304   */
305  public static <K extends @Nullable Object, V extends @Nullable Object>
306      LinkedHashMap<K, V> newLinkedHashMapWithExpectedSize(int expectedSize) {
307    return new LinkedHashMap<>(capacity(expectedSize));
308  }
309
310  /**
311   * Creates a new empty {@link ConcurrentHashMap} instance.
312   *
313   * @since 3.0
314   */
315  public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
316    return new ConcurrentHashMap<>();
317  }
318
319  /**
320   * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural ordering of its
321   * elements.
322   *
323   * <p><b>Note:</b> if mutability is not required, use {@link ImmutableSortedMap#of()} instead.
324   *
325   * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
326   * use the {@code TreeMap} constructor directly, taking advantage of <a
327   * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
328   *
329   * @return a new, empty {@code TreeMap}
330   */
331  public static <K extends Comparable, V extends @Nullable Object> TreeMap<K, V> newTreeMap() {
332    return new TreeMap<>();
333  }
334
335  /**
336   * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as the specified map
337   * and using the same ordering as the specified map.
338   *
339   * <p><b>Note:</b> if mutability is not required, use {@link
340   * ImmutableSortedMap#copyOfSorted(SortedMap)} instead.
341   *
342   * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
343   * use the {@code TreeMap} constructor directly, taking advantage of <a
344   * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
345   *
346   * @param map the sorted map whose mappings are to be placed in the new map and whose comparator
347   *     is to be used to sort the new map
348   * @return a new {@code TreeMap} initialized with the mappings from {@code map} and using the
349   *     comparator of {@code map}
350   */
351  public static <K extends @Nullable Object, V extends @Nullable Object> TreeMap<K, V> newTreeMap(
352      SortedMap<K, ? extends V> map) {
353    return new TreeMap<>(map);
354  }
355
356  /**
357   * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given comparator.
358   *
359   * <p><b>Note:</b> if mutability is not required, use {@code
360   * ImmutableSortedMap.orderedBy(comparator).build()} instead.
361   *
362   * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
363   * use the {@code TreeMap} constructor directly, taking advantage of <a
364   * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
365   *
366   * @param comparator the comparator to sort the keys with
367   * @return a new, empty {@code TreeMap}
368   */
369  public static <C extends @Nullable Object, K extends C, V extends @Nullable Object>
370      TreeMap<K, V> newTreeMap(@CheckForNull Comparator<C> comparator) {
371    // Ideally, the extra type parameter "C" shouldn't be necessary. It is a
372    // work-around of a compiler type inference quirk that prevents the
373    // following code from being compiled:
374    // Comparator<Class<?>> comparator = null;
375    // Map<Class<? extends Throwable>, String> map = newTreeMap(comparator);
376    return new TreeMap<>(comparator);
377  }
378
379  /**
380   * Creates an {@code EnumMap} instance.
381   *
382   * @param type the key type for this map
383   * @return a new, empty {@code EnumMap}
384   */
385  public static <K extends Enum<K>, V extends @Nullable Object> EnumMap<K, V> newEnumMap(
386      Class<K> type) {
387    return new EnumMap<>(checkNotNull(type));
388  }
389
390  /**
391   * Creates an {@code EnumMap} with the same mappings as the specified map.
392   *
393   * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
394   * use the {@code EnumMap} constructor directly, taking advantage of <a
395   * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
396   *
397   * @param map the map from which to initialize this {@code EnumMap}
398   * @return a new {@code EnumMap} initialized with the mappings from {@code map}
399   * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap} instance and contains
400   *     no mappings
401   */
402  public static <K extends Enum<K>, V extends @Nullable Object> EnumMap<K, V> newEnumMap(
403      Map<K, ? extends V> map) {
404    return new EnumMap<>(map);
405  }
406
407  /**
408   * Creates an {@code IdentityHashMap} instance.
409   *
410   * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated. Instead,
411   * use the {@code IdentityHashMap} constructor directly, taking advantage of <a
412   * href="http://goo.gl/iz2Wi">"diamond" syntax</a>.
413   *
414   * @return a new, empty {@code IdentityHashMap}
415   */
416  public static <K extends @Nullable Object, V extends @Nullable Object>
417      IdentityHashMap<K, V> newIdentityHashMap() {
418    return new IdentityHashMap<>();
419  }
420
421  /**
422   * Computes the difference between two maps. This difference is an immutable snapshot of the state
423   * of the maps at the time this method is called. It will never change, even if the maps change at
424   * a later time.
425   *
426   * <p>Since this method uses {@code HashMap} instances internally, the keys of the supplied maps
427   * must be well-behaved with respect to {@link Object#equals} and {@link Object#hashCode}.
428   *
429   * <p><b>Note:</b>If you only need to know whether two maps have the same mappings, call {@code
430   * left.equals(right)} instead of this method.
431   *
432   * @param left the map to treat as the "left" map for purposes of comparison
433   * @param right the map to treat as the "right" map for purposes of comparison
434   * @return the difference between the two maps
435   */
436  public static <K extends @Nullable Object, V extends @Nullable Object>
437      MapDifference<K, V> difference(
438          Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
439    if (left instanceof SortedMap) {
440      @SuppressWarnings("unchecked")
441      SortedMap<K, ? extends V> sortedLeft = (SortedMap<K, ? extends V>) left;
442      return difference(sortedLeft, right);
443    }
444    return difference(left, right, Equivalence.equals());
445  }
446
447  /**
448   * Computes the difference between two maps. This difference is an immutable snapshot of the state
449   * of the maps at the time this method is called. It will never change, even if the maps change at
450   * a later time.
451   *
452   * <p>Since this method uses {@code HashMap} instances internally, the keys of the supplied maps
453   * must be well-behaved with respect to {@link Object#equals} and {@link Object#hashCode}.
454   *
455   * @param left the map to treat as the "left" map for purposes of comparison
456   * @param right the map to treat as the "right" map for purposes of comparison
457   * @param valueEquivalence the equivalence relationship to use to compare values
458   * @return the difference between the two maps
459   * @since 10.0
460   */
461  public static <K extends @Nullable Object, V extends @Nullable Object>
462      MapDifference<K, V> difference(
463          Map<? extends K, ? extends V> left,
464          Map<? extends K, ? extends V> right,
465          Equivalence<? super @NonNull V> valueEquivalence) {
466    Preconditions.checkNotNull(valueEquivalence);
467
468    Map<K, V> onlyOnLeft = newLinkedHashMap();
469    Map<K, V> onlyOnRight = new LinkedHashMap<>(right); // will whittle it down
470    Map<K, V> onBoth = newLinkedHashMap();
471    Map<K, MapDifference.ValueDifference<V>> differences = newLinkedHashMap();
472    doDifference(left, right, valueEquivalence, onlyOnLeft, onlyOnRight, onBoth, differences);
473    return new MapDifferenceImpl<>(onlyOnLeft, onlyOnRight, onBoth, differences);
474  }
475
476  /**
477   * Computes the difference between two sorted maps, using the comparator of the left map, or
478   * {@code Ordering.natural()} if the left map uses the natural ordering of its elements. This
479   * difference is an immutable snapshot of the state of the maps at the time this method is called.
480   * It will never change, even if the maps change at a later time.
481   *
482   * <p>Since this method uses {@code TreeMap} instances internally, the keys of the right map must
483   * all compare as distinct according to the comparator of the left map.
484   *
485   * <p><b>Note:</b>If you only need to know whether two sorted maps have the same mappings, call
486   * {@code left.equals(right)} instead of this method.
487   *
488   * @param left the map to treat as the "left" map for purposes of comparison
489   * @param right the map to treat as the "right" map for purposes of comparison
490   * @return the difference between the two maps
491   * @since 11.0
492   */
493  public static <K extends @Nullable Object, V extends @Nullable Object>
494      SortedMapDifference<K, V> difference(
495          SortedMap<K, ? extends V> left, Map<? extends K, ? extends V> right) {
496    checkNotNull(left);
497    checkNotNull(right);
498    Comparator<? super K> comparator = orNaturalOrder(left.comparator());
499    SortedMap<K, V> onlyOnLeft = Maps.newTreeMap(comparator);
500    SortedMap<K, V> onlyOnRight = Maps.newTreeMap(comparator);
501    onlyOnRight.putAll(right); // will whittle it down
502    SortedMap<K, V> onBoth = Maps.newTreeMap(comparator);
503    SortedMap<K, MapDifference.ValueDifference<V>> differences = Maps.newTreeMap(comparator);
504
505    doDifference(left, right, Equivalence.equals(), onlyOnLeft, onlyOnRight, onBoth, differences);
506    return new SortedMapDifferenceImpl<>(onlyOnLeft, onlyOnRight, onBoth, differences);
507  }
508
509  private static <K extends @Nullable Object, V extends @Nullable Object> void doDifference(
510      Map<? extends K, ? extends V> left,
511      Map<? extends K, ? extends V> right,
512      Equivalence<? super @NonNull V> valueEquivalence,
513      Map<K, V> onlyOnLeft,
514      Map<K, V> onlyOnRight,
515      Map<K, V> onBoth,
516      Map<K, MapDifference.ValueDifference<V>> differences) {
517    for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
518      K leftKey = entry.getKey();
519      V leftValue = entry.getValue();
520      if (right.containsKey(leftKey)) {
521        /*
522         * The cast is safe because onlyOnRight contains all the keys of right.
523         *
524         * TODO(cpovirk): Consider checking onlyOnRight.containsKey instead of right.containsKey.
525         * That could change behavior if the input maps use different equivalence relations (and so
526         * a key that appears once in `right` might appear multiple times in `left`). We don't
527         * guarantee behavior in that case, anyway, and the current behavior is likely undesirable.
528         * So that's either a reason to feel free to change it or a reason to not bother thinking
529         * further about this.
530         */
531        V rightValue = uncheckedCastNullableTToT(onlyOnRight.remove(leftKey));
532        if (valueEquivalence.equivalent(leftValue, rightValue)) {
533          onBoth.put(leftKey, leftValue);
534        } else {
535          differences.put(leftKey, ValueDifferenceImpl.create(leftValue, rightValue));
536        }
537      } else {
538        onlyOnLeft.put(leftKey, leftValue);
539      }
540    }
541  }
542
543  private static <K extends @Nullable Object, V extends @Nullable Object> Map<K, V> unmodifiableMap(
544      Map<K, ? extends V> map) {
545    if (map instanceof SortedMap) {
546      return Collections.unmodifiableSortedMap((SortedMap<K, ? extends V>) map);
547    } else {
548      return Collections.unmodifiableMap(map);
549    }
550  }
551
552  static class MapDifferenceImpl<K extends @Nullable Object, V extends @Nullable Object>
553      implements MapDifference<K, V> {
554    final Map<K, V> onlyOnLeft;
555    final Map<K, V> onlyOnRight;
556    final Map<K, V> onBoth;
557    final Map<K, ValueDifference<V>> differences;
558
559    MapDifferenceImpl(
560        Map<K, V> onlyOnLeft,
561        Map<K, V> onlyOnRight,
562        Map<K, V> onBoth,
563        Map<K, ValueDifference<V>> differences) {
564      this.onlyOnLeft = unmodifiableMap(onlyOnLeft);
565      this.onlyOnRight = unmodifiableMap(onlyOnRight);
566      this.onBoth = unmodifiableMap(onBoth);
567      this.differences = unmodifiableMap(differences);
568    }
569
570    @Override
571    public boolean areEqual() {
572      return onlyOnLeft.isEmpty() && onlyOnRight.isEmpty() && differences.isEmpty();
573    }
574
575    @Override
576    public Map<K, V> entriesOnlyOnLeft() {
577      return onlyOnLeft;
578    }
579
580    @Override
581    public Map<K, V> entriesOnlyOnRight() {
582      return onlyOnRight;
583    }
584
585    @Override
586    public Map<K, V> entriesInCommon() {
587      return onBoth;
588    }
589
590    @Override
591    public Map<K, ValueDifference<V>> entriesDiffering() {
592      return differences;
593    }
594
595    @Override
596    public boolean equals(@CheckForNull Object object) {
597      if (object == this) {
598        return true;
599      }
600      if (object instanceof MapDifference) {
601        MapDifference<?, ?> other = (MapDifference<?, ?>) object;
602        return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
603            && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
604            && entriesInCommon().equals(other.entriesInCommon())
605            && entriesDiffering().equals(other.entriesDiffering());
606      }
607      return false;
608    }
609
610    @Override
611    public int hashCode() {
612      return Objects.hashCode(
613          entriesOnlyOnLeft(), entriesOnlyOnRight(), entriesInCommon(), entriesDiffering());
614    }
615
616    @Override
617    public String toString() {
618      if (areEqual()) {
619        return "equal";
620      }
621
622      StringBuilder result = new StringBuilder("not equal");
623      if (!onlyOnLeft.isEmpty()) {
624        result.append(": only on left=").append(onlyOnLeft);
625      }
626      if (!onlyOnRight.isEmpty()) {
627        result.append(": only on right=").append(onlyOnRight);
628      }
629      if (!differences.isEmpty()) {
630        result.append(": value differences=").append(differences);
631      }
632      return result.toString();
633    }
634  }
635
636  static class ValueDifferenceImpl<V extends @Nullable Object>
637      implements MapDifference.ValueDifference<V> {
638    @ParametricNullness private final V left;
639    @ParametricNullness private final V right;
640
641    static <V extends @Nullable Object> ValueDifference<V> create(
642        @ParametricNullness V left, @ParametricNullness V right) {
643      return new ValueDifferenceImpl<V>(left, right);
644    }
645
646    private ValueDifferenceImpl(@ParametricNullness V left, @ParametricNullness V right) {
647      this.left = left;
648      this.right = right;
649    }
650
651    @Override
652    @ParametricNullness
653    public V leftValue() {
654      return left;
655    }
656
657    @Override
658    @ParametricNullness
659    public V rightValue() {
660      return right;
661    }
662
663    @Override
664    public boolean equals(@CheckForNull Object object) {
665      if (object instanceof MapDifference.ValueDifference) {
666        MapDifference.ValueDifference<?> that = (MapDifference.ValueDifference<?>) object;
667        return Objects.equal(this.left, that.leftValue())
668            && Objects.equal(this.right, that.rightValue());
669      }
670      return false;
671    }
672
673    @Override
674    public int hashCode() {
675      return Objects.hashCode(left, right);
676    }
677
678    @Override
679    public String toString() {
680      return "(" + left + ", " + right + ")";
681    }
682  }
683
684  static class SortedMapDifferenceImpl<K extends @Nullable Object, V extends @Nullable Object>
685      extends MapDifferenceImpl<K, V> implements SortedMapDifference<K, V> {
686    SortedMapDifferenceImpl(
687        SortedMap<K, V> onlyOnLeft,
688        SortedMap<K, V> onlyOnRight,
689        SortedMap<K, V> onBoth,
690        SortedMap<K, ValueDifference<V>> differences) {
691      super(onlyOnLeft, onlyOnRight, onBoth, differences);
692    }
693
694    @Override
695    public SortedMap<K, ValueDifference<V>> entriesDiffering() {
696      return (SortedMap<K, ValueDifference<V>>) super.entriesDiffering();
697    }
698
699    @Override
700    public SortedMap<K, V> entriesInCommon() {
701      return (SortedMap<K, V>) super.entriesInCommon();
702    }
703
704    @Override
705    public SortedMap<K, V> entriesOnlyOnLeft() {
706      return (SortedMap<K, V>) super.entriesOnlyOnLeft();
707    }
708
709    @Override
710    public SortedMap<K, V> entriesOnlyOnRight() {
711      return (SortedMap<K, V>) super.entriesOnlyOnRight();
712    }
713  }
714
715  /**
716   * Returns the specified comparator if not null; otherwise returns {@code Ordering.natural()}.
717   * This method is an abomination of generics; the only purpose of this method is to contain the
718   * ugly type-casting in one place.
719   */
720  @SuppressWarnings("unchecked")
721  static <E extends @Nullable Object> Comparator<? super E> orNaturalOrder(
722      @CheckForNull Comparator<? super E> comparator) {
723    if (comparator != null) { // can't use ? : because of javac bug 5080917
724      return comparator;
725    }
726    return (Comparator<E>) Ordering.natural();
727  }
728
729  /**
730   * Returns a live {@link Map} view whose keys are the contents of {@code set} and whose values are
731   * computed on demand using {@code function}. To get an immutable <i>copy</i> instead, use {@link
732   * #toMap(Iterable, Function)}.
733   *
734   * <p>Specifically, for each {@code k} in the backing set, the returned map has an entry mapping
735   * {@code k} to {@code function.apply(k)}. The {@code keySet}, {@code values}, and {@code
736   * entrySet} views of the returned map iterate in the same order as the backing set.
737   *
738   * <p>Modifications to the backing set are read through to the returned map. The returned map
739   * supports removal operations if the backing set does. Removal operations write through to the
740   * backing set. The returned map does not support put operations.
741   *
742   * <p><b>Warning:</b> If the function rejects {@code null}, caution is required to make sure the
743   * set does not contain {@code null}, because the view cannot stop {@code null} from being added
744   * to the set.
745   *
746   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of key type {@code K},
747   * {@code k.equals(k2)} implies that {@code k2} is also of type {@code K}. Using a key type for
748   * which this may not hold, such as {@code ArrayList}, may risk a {@code ClassCastException} when
749   * calling methods on the resulting map view.
750   *
751   * @since 14.0
752   */
753  public static <K extends @Nullable Object, V extends @Nullable Object> Map<K, V> asMap(
754      Set<K> set, Function<? super K, V> function) {
755    return new AsMapView<>(set, function);
756  }
757
758  /**
759   * Returns a view of the sorted set as a map, mapping keys from the set according to the specified
760   * function.
761   *
762   * <p>Specifically, for each {@code k} in the backing set, the returned map has an entry mapping
763   * {@code k} to {@code function.apply(k)}. The {@code keySet}, {@code values}, and {@code
764   * entrySet} views of the returned map iterate in the same order as the backing set.
765   *
766   * <p>Modifications to the backing set are read through to the returned map. The returned map
767   * supports removal operations if the backing set does. Removal operations write through to the
768   * backing set. The returned map does not support put operations.
769   *
770   * <p><b>Warning:</b> If the function rejects {@code null}, caution is required to make sure the
771   * set does not contain {@code null}, because the view cannot stop {@code null} from being added
772   * to the set.
773   *
774   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of key type {@code K},
775   * {@code k.equals(k2)} implies that {@code k2} is also of type {@code K}. Using a key type for
776   * which this may not hold, such as {@code ArrayList}, may risk a {@code ClassCastException} when
777   * calling methods on the resulting map view.
778   *
779   * @since 14.0
780   */
781  public static <K extends @Nullable Object, V extends @Nullable Object> SortedMap<K, V> asMap(
782      SortedSet<K> set, Function<? super K, V> function) {
783    return new SortedAsMapView<>(set, function);
784  }
785
786  /**
787   * Returns a view of the navigable set as a map, mapping keys from the set according to the
788   * specified function.
789   *
790   * <p>Specifically, for each {@code k} in the backing set, the returned map has an entry mapping
791   * {@code k} to {@code function.apply(k)}. The {@code keySet}, {@code values}, and {@code
792   * entrySet} views of the returned map iterate in the same order as the backing set.
793   *
794   * <p>Modifications to the backing set are read through to the returned map. The returned map
795   * supports removal operations if the backing set does. Removal operations write through to the
796   * backing set. The returned map does not support put operations.
797   *
798   * <p><b>Warning:</b> If the function rejects {@code null}, caution is required to make sure the
799   * set does not contain {@code null}, because the view cannot stop {@code null} from being added
800   * to the set.
801   *
802   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of key type {@code K},
803   * {@code k.equals(k2)} implies that {@code k2} is also of type {@code K}. Using a key type for
804   * which this may not hold, such as {@code ArrayList}, may risk a {@code ClassCastException} when
805   * calling methods on the resulting map view.
806   *
807   * @since 14.0
808   */
809  @GwtIncompatible // NavigableMap
810  public static <K extends @Nullable Object, V extends @Nullable Object> NavigableMap<K, V> asMap(
811      NavigableSet<K> set, Function<? super K, V> function) {
812    return new NavigableAsMapView<>(set, function);
813  }
814
815  private static class AsMapView<K extends @Nullable Object, V extends @Nullable Object>
816      extends ViewCachingAbstractMap<K, V> {
817
818    private final Set<K> set;
819    final Function<? super K, V> function;
820
821    Set<K> backingSet() {
822      return set;
823    }
824
825    AsMapView(Set<K> set, Function<? super K, V> function) {
826      this.set = checkNotNull(set);
827      this.function = checkNotNull(function);
828    }
829
830    @Override
831    public Set<K> createKeySet() {
832      return removeOnlySet(backingSet());
833    }
834
835    @Override
836    Collection<V> createValues() {
837      return Collections2.transform(set, function);
838    }
839
840    @Override
841    public int size() {
842      return backingSet().size();
843    }
844
845    @Override
846    public boolean containsKey(@CheckForNull Object key) {
847      return backingSet().contains(key);
848    }
849
850    @Override
851    @CheckForNull
852    public V get(@CheckForNull Object key) {
853      if (Collections2.safeContains(backingSet(), key)) {
854        @SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it
855        K k = (K) key;
856        return function.apply(k);
857      } else {
858        return null;
859      }
860    }
861
862    @Override
863    @CheckForNull
864    public V remove(@CheckForNull Object key) {
865      if (backingSet().remove(key)) {
866        @SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it
867        K k = (K) key;
868        return function.apply(k);
869      } else {
870        return null;
871      }
872    }
873
874    @Override
875    public void clear() {
876      backingSet().clear();
877    }
878
879    @Override
880    protected Set<Entry<K, V>> createEntrySet() {
881      @WeakOuter
882      class EntrySetImpl extends EntrySet<K, V> {
883        @Override
884        Map<K, V> map() {
885          return AsMapView.this;
886        }
887
888        @Override
889        public Iterator<Entry<K, V>> iterator() {
890          return asMapEntryIterator(backingSet(), function);
891        }
892      }
893      return new EntrySetImpl();
894    }
895  }
896
897  static <K extends @Nullable Object, V extends @Nullable Object>
898      Iterator<Entry<K, V>> asMapEntryIterator(Set<K> set, final Function<? super K, V> function) {
899    return new TransformedIterator<K, Entry<K, V>>(set.iterator()) {
900      @Override
901      Entry<K, V> transform(@ParametricNullness final K key) {
902        return immutableEntry(key, function.apply(key));
903      }
904    };
905  }
906
907  private static class SortedAsMapView<K extends @Nullable Object, V extends @Nullable Object>
908      extends AsMapView<K, V> implements SortedMap<K, V> {
909
910    SortedAsMapView(SortedSet<K> set, Function<? super K, V> function) {
911      super(set, function);
912    }
913
914    @Override
915    SortedSet<K> backingSet() {
916      return (SortedSet<K>) super.backingSet();
917    }
918
919    @Override
920    @CheckForNull
921    public Comparator<? super K> comparator() {
922      return backingSet().comparator();
923    }
924
925    @Override
926    public Set<K> keySet() {
927      return removeOnlySortedSet(backingSet());
928    }
929
930    @Override
931    public SortedMap<K, V> subMap(@ParametricNullness K fromKey, @ParametricNullness K toKey) {
932      return asMap(backingSet().subSet(fromKey, toKey), function);
933    }
934
935    @Override
936    public SortedMap<K, V> headMap(@ParametricNullness K toKey) {
937      return asMap(backingSet().headSet(toKey), function);
938    }
939
940    @Override
941    public SortedMap<K, V> tailMap(@ParametricNullness K fromKey) {
942      return asMap(backingSet().tailSet(fromKey), function);
943    }
944
945    @Override
946    @ParametricNullness
947    public K firstKey() {
948      return backingSet().first();
949    }
950
951    @Override
952    @ParametricNullness
953    public K lastKey() {
954      return backingSet().last();
955    }
956  }
957
958  @GwtIncompatible // NavigableMap
959  private static final class NavigableAsMapView<
960          K extends @Nullable Object, V extends @Nullable Object>
961      extends AbstractNavigableMap<K, V> {
962    /*
963     * Using AbstractNavigableMap is simpler than extending SortedAsMapView and rewriting all the
964     * NavigableMap methods.
965     */
966
967    private final NavigableSet<K> set;
968    private final Function<? super K, V> function;
969
970    NavigableAsMapView(NavigableSet<K> ks, Function<? super K, V> vFunction) {
971      this.set = checkNotNull(ks);
972      this.function = checkNotNull(vFunction);
973    }
974
975    @Override
976    public NavigableMap<K, V> subMap(
977        @ParametricNullness K fromKey,
978        boolean fromInclusive,
979        @ParametricNullness K toKey,
980        boolean toInclusive) {
981      return asMap(set.subSet(fromKey, fromInclusive, toKey, toInclusive), function);
982    }
983
984    @Override
985    public NavigableMap<K, V> headMap(@ParametricNullness K toKey, boolean inclusive) {
986      return asMap(set.headSet(toKey, inclusive), function);
987    }
988
989    @Override
990    public NavigableMap<K, V> tailMap(@ParametricNullness K fromKey, boolean inclusive) {
991      return asMap(set.tailSet(fromKey, inclusive), function);
992    }
993
994    @Override
995    @CheckForNull
996    public Comparator<? super K> comparator() {
997      return set.comparator();
998    }
999
1000    @Override
1001    @CheckForNull
1002    public V get(@CheckForNull Object key) {
1003      if (Collections2.safeContains(set, key)) {
1004        @SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it
1005        K k = (K) key;
1006        return function.apply(k);
1007      } else {
1008        return null;
1009      }
1010    }
1011
1012    @Override
1013    public void clear() {
1014      set.clear();
1015    }
1016
1017    @Override
1018    Iterator<Entry<K, V>> entryIterator() {
1019      return asMapEntryIterator(set, function);
1020    }
1021
1022    @Override
1023    Iterator<Entry<K, V>> descendingEntryIterator() {
1024      return descendingMap().entrySet().iterator();
1025    }
1026
1027    @Override
1028    public NavigableSet<K> navigableKeySet() {
1029      return removeOnlyNavigableSet(set);
1030    }
1031
1032    @Override
1033    public int size() {
1034      return set.size();
1035    }
1036
1037    @Override
1038    public NavigableMap<K, V> descendingMap() {
1039      return asMap(set.descendingSet(), function);
1040    }
1041  }
1042
1043  private static <E extends @Nullable Object> Set<E> removeOnlySet(final Set<E> set) {
1044    return new ForwardingSet<E>() {
1045      @Override
1046      protected Set<E> delegate() {
1047        return set;
1048      }
1049
1050      @Override
1051      public boolean add(@ParametricNullness E element) {
1052        throw new UnsupportedOperationException();
1053      }
1054
1055      @Override
1056      public boolean addAll(Collection<? extends E> es) {
1057        throw new UnsupportedOperationException();
1058      }
1059    };
1060  }
1061
1062  private static <E extends @Nullable Object> SortedSet<E> removeOnlySortedSet(
1063      final SortedSet<E> set) {
1064    return new ForwardingSortedSet<E>() {
1065      @Override
1066      protected SortedSet<E> delegate() {
1067        return set;
1068      }
1069
1070      @Override
1071      public boolean add(@ParametricNullness E element) {
1072        throw new UnsupportedOperationException();
1073      }
1074
1075      @Override
1076      public boolean addAll(Collection<? extends E> es) {
1077        throw new UnsupportedOperationException();
1078      }
1079
1080      @Override
1081      public SortedSet<E> headSet(@ParametricNullness E toElement) {
1082        return removeOnlySortedSet(super.headSet(toElement));
1083      }
1084
1085      @Override
1086      public SortedSet<E> subSet(
1087          @ParametricNullness E fromElement, @ParametricNullness E toElement) {
1088        return removeOnlySortedSet(super.subSet(fromElement, toElement));
1089      }
1090
1091      @Override
1092      public SortedSet<E> tailSet(@ParametricNullness E fromElement) {
1093        return removeOnlySortedSet(super.tailSet(fromElement));
1094      }
1095    };
1096  }
1097
1098  @GwtIncompatible // NavigableSet
1099  private static <E extends @Nullable Object> NavigableSet<E> removeOnlyNavigableSet(
1100      final NavigableSet<E> set) {
1101    return new ForwardingNavigableSet<E>() {
1102      @Override
1103      protected NavigableSet<E> delegate() {
1104        return set;
1105      }
1106
1107      @Override
1108      public boolean add(@ParametricNullness E element) {
1109        throw new UnsupportedOperationException();
1110      }
1111
1112      @Override
1113      public boolean addAll(Collection<? extends E> es) {
1114        throw new UnsupportedOperationException();
1115      }
1116
1117      @Override
1118      public SortedSet<E> headSet(@ParametricNullness E toElement) {
1119        return removeOnlySortedSet(super.headSet(toElement));
1120      }
1121
1122      @Override
1123      public NavigableSet<E> headSet(@ParametricNullness E toElement, boolean inclusive) {
1124        return removeOnlyNavigableSet(super.headSet(toElement, inclusive));
1125      }
1126
1127      @Override
1128      public SortedSet<E> subSet(
1129          @ParametricNullness E fromElement, @ParametricNullness E toElement) {
1130        return removeOnlySortedSet(super.subSet(fromElement, toElement));
1131      }
1132
1133      @Override
1134      public NavigableSet<E> subSet(
1135          @ParametricNullness E fromElement,
1136          boolean fromInclusive,
1137          @ParametricNullness E toElement,
1138          boolean toInclusive) {
1139        return removeOnlyNavigableSet(
1140            super.subSet(fromElement, fromInclusive, toElement, toInclusive));
1141      }
1142
1143      @Override
1144      public SortedSet<E> tailSet(@ParametricNullness E fromElement) {
1145        return removeOnlySortedSet(super.tailSet(fromElement));
1146      }
1147
1148      @Override
1149      public NavigableSet<E> tailSet(@ParametricNullness E fromElement, boolean inclusive) {
1150        return removeOnlyNavigableSet(super.tailSet(fromElement, inclusive));
1151      }
1152
1153      @Override
1154      public NavigableSet<E> descendingSet() {
1155        return removeOnlyNavigableSet(super.descendingSet());
1156      }
1157    };
1158  }
1159
1160  /**
1161   * Returns an immutable map whose keys are the distinct elements of {@code keys} and whose value
1162   * for each key was computed by {@code valueFunction}. The map's iteration order is the order of
1163   * the first appearance of each key in {@code keys}.
1164   *
1165   * <p>When there are multiple instances of a key in {@code keys}, it is unspecified whether {@code
1166   * valueFunction} will be applied to more than one instance of that key and, if it is, which
1167   * result will be mapped to that key in the returned map.
1168   *
1169   * <p>If {@code keys} is a {@link Set}, a live view can be obtained instead of a copy using {@link
1170   * Maps#asMap(Set, Function)}.
1171   *
1172   * @throws NullPointerException if any element of {@code keys} is {@code null}, or if {@code
1173   *     valueFunction} produces {@code null} for any key
1174   * @since 14.0
1175   */
1176  public static <K, V> ImmutableMap<K, V> toMap(
1177      Iterable<K> keys, Function<? super K, V> valueFunction) {
1178    return toMap(keys.iterator(), valueFunction);
1179  }
1180
1181  /**
1182   * Returns an immutable map whose keys are the distinct elements of {@code keys} and whose value
1183   * for each key was computed by {@code valueFunction}. The map's iteration order is the order of
1184   * the first appearance of each key in {@code keys}.
1185   *
1186   * <p>When there are multiple instances of a key in {@code keys}, it is unspecified whether {@code
1187   * valueFunction} will be applied to more than one instance of that key and, if it is, which
1188   * result will be mapped to that key in the returned map.
1189   *
1190   * @throws NullPointerException if any element of {@code keys} is {@code null}, or if {@code
1191   *     valueFunction} produces {@code null} for any key
1192   * @since 14.0
1193   */
1194  public static <K, V> ImmutableMap<K, V> toMap(
1195      Iterator<K> keys, Function<? super K, V> valueFunction) {
1196    checkNotNull(valueFunction);
1197    ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
1198    while (keys.hasNext()) {
1199      K key = keys.next();
1200      builder.put(key, valueFunction.apply(key));
1201    }
1202    // Using buildKeepingLast() so as not to fail on duplicate keys
1203    return builder.buildKeepingLast();
1204  }
1205
1206  /**
1207   * Returns a map with the given {@code values}, indexed by keys derived from those values. In
1208   * other words, each input value produces an entry in the map whose key is the result of applying
1209   * {@code keyFunction} to that value. These entries appear in the same order as the input values.
1210   * Example usage:
1211   *
1212   * <pre>{@code
1213   * Color red = new Color("red", 255, 0, 0);
1214   * ...
1215   * ImmutableSet<Color> allColors = ImmutableSet.of(red, green, blue);
1216   *
1217   * ImmutableMap<String, Color> colorForName =
1218   *     uniqueIndex(allColors, c -> c.toString());
1219   * assertThat(colorForName).containsEntry("red", red);
1220   * }</pre>
1221   *
1222   * <p>If your index may associate multiple values with each key, use {@link
1223   * Multimaps#index(Iterable, Function) Multimaps.index}.
1224   *
1225   * <p><b>Note:</b> on Java 8 and later, it is usually better to use streams. For example:
1226   *
1227   * <pre>{@code
1228   * import static com.google.common.collect.ImmutableMap.toImmutableMap;
1229   * ...
1230   * ImmutableMap<String, Color> colorForName =
1231   *     allColors.stream().collect(toImmutableMap(c -> c.toString(), c -> c));
1232   * }</pre>
1233   *
1234   * <p>Streams provide a more standard and flexible API and the lambdas make it clear what the keys
1235   * and values in the map are.
1236   *
1237   * @param values the values to use when constructing the {@code Map}
1238   * @param keyFunction the function used to produce the key for each value
1239   * @return a map mapping the result of evaluating the function {@code keyFunction} on each value
1240   *     in the input collection to that value
1241   * @throws IllegalArgumentException if {@code keyFunction} produces the same key for more than one
1242   *     value in the input collection
1243   * @throws NullPointerException if any element of {@code values} is {@code null}, or if {@code
1244   *     keyFunction} produces {@code null} for any value
1245   */
1246  @CanIgnoreReturnValue
1247  public static <K, V> ImmutableMap<K, V> uniqueIndex(
1248      Iterable<V> values, Function<? super V, K> keyFunction) {
1249    if (values instanceof Collection) {
1250      return uniqueIndex(
1251          values.iterator(),
1252          keyFunction,
1253          ImmutableMap.builderWithExpectedSize(((Collection<?>) values).size()));
1254    }
1255    return uniqueIndex(values.iterator(), keyFunction);
1256  }
1257
1258  /**
1259   * Returns a map with the given {@code values}, indexed by keys derived from those values. In
1260   * other words, each input value produces an entry in the map whose key is the result of applying
1261   * {@code keyFunction} to that value. These entries appear in the same order as the input values.
1262   * Example usage:
1263   *
1264   * <pre>{@code
1265   * Color red = new Color("red", 255, 0, 0);
1266   * ...
1267   * Iterator<Color> allColors = ImmutableSet.of(red, green, blue).iterator();
1268   *
1269   * Map<String, Color> colorForName =
1270   *     uniqueIndex(allColors, toStringFunction());
1271   * assertThat(colorForName).containsEntry("red", red);
1272   * }</pre>
1273   *
1274   * <p>If your index may associate multiple values with each key, use {@link
1275   * Multimaps#index(Iterator, Function) Multimaps.index}.
1276   *
1277   * @param values the values to use when constructing the {@code Map}
1278   * @param keyFunction the function used to produce the key for each value
1279   * @return a map mapping the result of evaluating the function {@code keyFunction} on each value
1280   *     in the input collection to that value
1281   * @throws IllegalArgumentException if {@code keyFunction} produces the same key for more than one
1282   *     value in the input collection
1283   * @throws NullPointerException if any element of {@code values} is {@code null}, or if {@code
1284   *     keyFunction} produces {@code null} for any value
1285   * @since 10.0
1286   */
1287  @CanIgnoreReturnValue
1288  public static <K, V> ImmutableMap<K, V> uniqueIndex(
1289      Iterator<V> values, Function<? super V, K> keyFunction) {
1290    return uniqueIndex(values, keyFunction, ImmutableMap.builder());
1291  }
1292
1293  private static <K, V> ImmutableMap<K, V> uniqueIndex(
1294      Iterator<V> values, Function<? super V, K> keyFunction, ImmutableMap.Builder<K, V> builder) {
1295    checkNotNull(keyFunction);
1296    while (values.hasNext()) {
1297      V value = values.next();
1298      builder.put(keyFunction.apply(value), value);
1299    }
1300    try {
1301      return builder.buildOrThrow();
1302    } catch (IllegalArgumentException duplicateKeys) {
1303      throw new IllegalArgumentException(
1304          duplicateKeys.getMessage()
1305              + ". To index multiple values under a key, use Multimaps.index.");
1306    }
1307  }
1308
1309  /**
1310   * Creates an {@code ImmutableMap<String, String>} from a {@code Properties} instance. Properties
1311   * normally derive from {@code Map<Object, Object>}, but they typically contain strings, which is
1312   * awkward. This method lets you get a plain-old-{@code Map} out of a {@code Properties}.
1313   *
1314   * @param properties a {@code Properties} object to be converted
1315   * @return an immutable map containing all the entries in {@code properties}
1316   * @throws ClassCastException if any key in {@code properties} is not a {@code String}
1317   * @throws NullPointerException if any key or value in {@code properties} is null
1318   */
1319  @J2ktIncompatible
1320  @GwtIncompatible // java.util.Properties
1321  public static ImmutableMap<String, String> fromProperties(Properties properties) {
1322    ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
1323
1324    for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements(); ) {
1325      /*
1326       * requireNonNull is safe because propertyNames contains only non-null elements.
1327       *
1328       * Accordingly, we have it annotated as returning `Enumeration<? extends Object>` in our
1329       * prototype checker's JDK. However, the checker still sees the return type as plain
1330       * `Enumeration<?>`, probably because of one of the following two bugs (and maybe those two
1331       * bugs are themselves just symptoms of the same underlying problem):
1332       *
1333       * https://github.com/typetools/checker-framework/issues/3030
1334       *
1335       * https://github.com/typetools/checker-framework/issues/3236
1336       */
1337      String key = (String) requireNonNull(e.nextElement());
1338      /*
1339       * requireNonNull is safe because the key came from propertyNames...
1340       *
1341       * ...except that it's possible for users to insert a string key with a non-string value, and
1342       * in that case, getProperty *will* return null.
1343       *
1344       * TODO(b/192002623): Handle that case: Either:
1345       *
1346       * - Skip non-string keys and values entirely, as proposed in the linked bug.
1347       *
1348       * - Throw ClassCastException instead of NullPointerException, as documented in the current
1349       *   Javadoc. (Note that we can't necessarily "just" change our call to `getProperty` to `get`
1350       *   because `get` does not consult the default properties.)
1351       */
1352      builder.put(key, requireNonNull(properties.getProperty(key)));
1353    }
1354
1355    return builder.buildOrThrow();
1356  }
1357
1358  /**
1359   * Returns an immutable map entry with the specified key and value. The {@link Entry#setValue}
1360   * operation throws an {@link UnsupportedOperationException}.
1361   *
1362   * <p>The returned entry is serializable.
1363   *
1364   * <p><b>Java 9 users:</b> consider using {@code java.util.Map.entry(key, value)} if the key and
1365   * value are non-null and the entry does not need to be serializable.
1366   *
1367   * @param key the key to be associated with the returned entry
1368   * @param value the value to be associated with the returned entry
1369   */
1370  @GwtCompatible(serializable = true)
1371  public static <K extends @Nullable Object, V extends @Nullable Object> Entry<K, V> immutableEntry(
1372      @ParametricNullness K key, @ParametricNullness V value) {
1373    return new ImmutableEntry<>(key, value);
1374  }
1375
1376  /**
1377   * Returns an unmodifiable view of the specified set of entries. The {@link Entry#setValue}
1378   * operation throws an {@link UnsupportedOperationException}, as do any operations that would
1379   * modify the returned set.
1380   *
1381   * @param entrySet the entries for which to return an unmodifiable view
1382   * @return an unmodifiable view of the entries
1383   */
1384  static <K extends @Nullable Object, V extends @Nullable Object>
1385      Set<Entry<K, V>> unmodifiableEntrySet(Set<Entry<K, V>> entrySet) {
1386    return new UnmodifiableEntrySet<>(Collections.unmodifiableSet(entrySet));
1387  }
1388
1389  /**
1390   * Returns an unmodifiable view of the specified map entry. The {@link Entry#setValue} operation
1391   * throws an {@link UnsupportedOperationException}. This also has the side effect of redefining
1392   * {@code equals} to comply with the Entry contract, to avoid a possible nefarious implementation
1393   * of equals.
1394   *
1395   * @param entry the entry for which to return an unmodifiable view
1396   * @return an unmodifiable view of the entry
1397   */
1398  static <K extends @Nullable Object, V extends @Nullable Object> Entry<K, V> unmodifiableEntry(
1399      final Entry<? extends K, ? extends V> entry) {
1400    checkNotNull(entry);
1401    return new AbstractMapEntry<K, V>() {
1402      @Override
1403      @ParametricNullness
1404      public K getKey() {
1405        return entry.getKey();
1406      }
1407
1408      @Override
1409      @ParametricNullness
1410      public V getValue() {
1411        return entry.getValue();
1412      }
1413    };
1414  }
1415
1416  static <K extends @Nullable Object, V extends @Nullable Object>
1417      UnmodifiableIterator<Entry<K, V>> unmodifiableEntryIterator(
1418          final Iterator<Entry<K, V>> entryIterator) {
1419    return new UnmodifiableIterator<Entry<K, V>>() {
1420      @Override
1421      public boolean hasNext() {
1422        return entryIterator.hasNext();
1423      }
1424
1425      @Override
1426      public Entry<K, V> next() {
1427        return unmodifiableEntry(entryIterator.next());
1428      }
1429    };
1430  }
1431
1432  /** The implementation of {@link Multimaps#unmodifiableEntries}. */
1433  static class UnmodifiableEntries<K extends @Nullable Object, V extends @Nullable Object>
1434      extends ForwardingCollection<Entry<K, V>> {
1435    private final Collection<Entry<K, V>> entries;
1436
1437    UnmodifiableEntries(Collection<Entry<K, V>> entries) {
1438      this.entries = entries;
1439    }
1440
1441    @Override
1442    protected Collection<Entry<K, V>> delegate() {
1443      return entries;
1444    }
1445
1446    @Override
1447    public Iterator<Entry<K, V>> iterator() {
1448      return unmodifiableEntryIterator(entries.iterator());
1449    }
1450
1451    // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
1452
1453    @Override
1454    public @Nullable Object[] toArray() {
1455      /*
1456       * standardToArray returns `@Nullable Object[]` rather than `Object[]` but because it can
1457       * be used with collections that may contain null. This collection never contains nulls, so we
1458       * could return `Object[]`. But this class is private and J2KT cannot change return types in
1459       * overrides, so we declare `@Nullable Object[]` as the return type.
1460       */
1461      return standardToArray();
1462    }
1463
1464    @Override
1465    @SuppressWarnings("nullness") // b/192354773 in our checker affects toArray declarations
1466    public <T extends @Nullable Object> T[] toArray(T[] array) {
1467      return standardToArray(array);
1468    }
1469  }
1470
1471  /** The implementation of {@link Maps#unmodifiableEntrySet(Set)}. */
1472  static class UnmodifiableEntrySet<K extends @Nullable Object, V extends @Nullable Object>
1473      extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> {
1474    UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
1475      super(entries);
1476    }
1477
1478    // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
1479
1480    @Override
1481    public boolean equals(@CheckForNull Object object) {
1482      return Sets.equalsImpl(this, object);
1483    }
1484
1485    @Override
1486    public int hashCode() {
1487      return Sets.hashCodeImpl(this);
1488    }
1489  }
1490
1491  /**
1492   * Returns a {@link Converter} that converts values using {@link BiMap#get bimap.get()}, and whose
1493   * inverse view converts values using {@link BiMap#inverse bimap.inverse()}{@code .get()}.
1494   *
1495   * <p>To use a plain {@link Map} as a {@link Function}, see {@link
1496   * com.google.common.base.Functions#forMap(Map)} or {@link
1497   * com.google.common.base.Functions#forMap(Map, Object)}.
1498   *
1499   * @since 16.0
1500   */
1501  public static <A, B> Converter<A, B> asConverter(final BiMap<A, B> bimap) {
1502    return new BiMapConverter<>(bimap);
1503  }
1504
1505  private static final class BiMapConverter<A, B> extends Converter<A, B> implements Serializable {
1506    private final BiMap<A, B> bimap;
1507
1508    BiMapConverter(BiMap<A, B> bimap) {
1509      this.bimap = checkNotNull(bimap);
1510    }
1511
1512    @Override
1513    protected B doForward(A a) {
1514      return convert(bimap, a);
1515    }
1516
1517    @Override
1518    protected A doBackward(B b) {
1519      return convert(bimap.inverse(), b);
1520    }
1521
1522    private static <X, Y> Y convert(BiMap<X, Y> bimap, X input) {
1523      Y output = bimap.get(input);
1524      checkArgument(output != null, "No non-null mapping present for input: %s", input);
1525      return output;
1526    }
1527
1528    @Override
1529    public boolean equals(@CheckForNull Object object) {
1530      if (object instanceof BiMapConverter) {
1531        BiMapConverter<?, ?> that = (BiMapConverter<?, ?>) object;
1532        return this.bimap.equals(that.bimap);
1533      }
1534      return false;
1535    }
1536
1537    @Override
1538    public int hashCode() {
1539      return bimap.hashCode();
1540    }
1541
1542    // There's really no good way to implement toString() without printing the entire BiMap, right?
1543    @Override
1544    public String toString() {
1545      return "Maps.asConverter(" + bimap + ")";
1546    }
1547
1548    private static final long serialVersionUID = 0L;
1549  }
1550
1551  /**
1552   * Returns a synchronized (thread-safe) bimap backed by the specified bimap. In order to guarantee
1553   * serial access, it is critical that <b>all</b> access to the backing bimap is accomplished
1554   * through the returned bimap.
1555   *
1556   * <p>It is imperative that the user manually synchronize on the returned map when accessing any
1557   * of its collection views:
1558   *
1559   * <pre>{@code
1560   * BiMap<Long, String> map = Maps.synchronizedBiMap(
1561   *     HashBiMap.<Long, String>create());
1562   * ...
1563   * Set<Long> set = map.keySet();  // Needn't be in synchronized block
1564   * ...
1565   * synchronized (map) {  // Synchronizing on map, not set!
1566   *   Iterator<Long> it = set.iterator(); // Must be in synchronized block
1567   *   while (it.hasNext()) {
1568   *     foo(it.next());
1569   *   }
1570   * }
1571   * }</pre>
1572   *
1573   * <p>Failure to follow this advice may result in non-deterministic behavior.
1574   *
1575   * <p>The returned bimap will be serializable if the specified bimap is serializable.
1576   *
1577   * @param bimap the bimap to be wrapped in a synchronized view
1578   * @return a synchronized view of the specified bimap
1579   */
1580  public static <K extends @Nullable Object, V extends @Nullable Object>
1581      BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) {
1582    return Synchronized.biMap(bimap, null);
1583  }
1584
1585  /**
1586   * Returns an unmodifiable view of the specified bimap. This method allows modules to provide
1587   * users with "read-only" access to internal bimaps. Query operations on the returned bimap "read
1588   * through" to the specified bimap, and attempts to modify the returned map, whether direct or via
1589   * its collection views, result in an {@code UnsupportedOperationException}.
1590   *
1591   * <p>The returned bimap will be serializable if the specified bimap is serializable.
1592   *
1593   * @param bimap the bimap for which an unmodifiable view is to be returned
1594   * @return an unmodifiable view of the specified bimap
1595   */
1596  public static <K extends @Nullable Object, V extends @Nullable Object>
1597      BiMap<K, V> unmodifiableBiMap(BiMap<? extends K, ? extends V> bimap) {
1598    return new UnmodifiableBiMap<>(bimap, null);
1599  }
1600
1601  /**
1602   * @see Maps#unmodifiableBiMap(BiMap)
1603   */
1604  private static class UnmodifiableBiMap<K extends @Nullable Object, V extends @Nullable Object>
1605      extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable {
1606    final Map<K, V> unmodifiableMap;
1607    final BiMap<? extends K, ? extends V> delegate;
1608    @RetainedWith @CheckForNull BiMap<V, K> inverse;
1609    @CheckForNull transient Set<V> values;
1610
1611    UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate, @CheckForNull BiMap<V, K> inverse) {
1612      unmodifiableMap = Collections.unmodifiableMap(delegate);
1613      this.delegate = delegate;
1614      this.inverse = inverse;
1615    }
1616
1617    @Override
1618    protected Map<K, V> delegate() {
1619      return unmodifiableMap;
1620    }
1621
1622    @Override
1623    @CheckForNull
1624    public V forcePut(@ParametricNullness K key, @ParametricNullness V value) {
1625      throw new UnsupportedOperationException();
1626    }
1627
1628    @Override
1629    public BiMap<V, K> inverse() {
1630      BiMap<V, K> result = inverse;
1631      return (result == null)
1632          ? inverse = new UnmodifiableBiMap<>(delegate.inverse(), this)
1633          : result;
1634    }
1635
1636    @Override
1637    public Set<V> values() {
1638      Set<V> result = values;
1639      return (result == null) ? values = Collections.unmodifiableSet(delegate.values()) : result;
1640    }
1641
1642    private static final long serialVersionUID = 0;
1643  }
1644
1645  /**
1646   * Returns a view of a map where each value is transformed by a function. All other properties of
1647   * the map, such as iteration order, are left intact. For example, the code:
1648   *
1649   * <pre>{@code
1650   * Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
1651   * Function<Integer, Double> sqrt =
1652   *     new Function<Integer, Double>() {
1653   *       public Double apply(Integer in) {
1654   *         return Math.sqrt((int) in);
1655   *       }
1656   *     };
1657   * Map<String, Double> transformed = Maps.transformValues(map, sqrt);
1658   * System.out.println(transformed);
1659   * }</pre>
1660   *
1661   * ... prints {@code {a=2.0, b=3.0}}.
1662   *
1663   * <p>Changes in the underlying map are reflected in this view. Conversely, this view supports
1664   * removal operations, and these are reflected in the underlying map.
1665   *
1666   * <p>It's acceptable for the underlying map to contain null keys, and even null values provided
1667   * that the function is capable of accepting null input. The transformed map might contain null
1668   * values, if the function sometimes gives a null result.
1669   *
1670   * <p>The returned map is not thread-safe or serializable, even if the underlying map is.
1671   *
1672   * <p>The function is applied lazily, invoked when needed. This is necessary for the returned map
1673   * to be a view, but it means that the function will be applied many times for bulk operations
1674   * like {@link Map#containsValue} and {@code Map.toString()}. For this to perform well, {@code
1675   * function} should be fast. To avoid lazy evaluation when the returned map doesn't need to be a
1676   * view, copy the returned map into a new map of your choosing.
1677   */
1678  public static <
1679          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1680      Map<K, V2> transformValues(Map<K, V1> fromMap, Function<? super V1, V2> function) {
1681    return transformEntries(fromMap, asEntryTransformer(function));
1682  }
1683
1684  /**
1685   * Returns a view of a sorted map where each value is transformed by a function. All other
1686   * properties of the map, such as iteration order, are left intact. For example, the code:
1687   *
1688   * <pre>{@code
1689   * SortedMap<String, Integer> map = ImmutableSortedMap.of("a", 4, "b", 9);
1690   * Function<Integer, Double> sqrt =
1691   *     new Function<Integer, Double>() {
1692   *       public Double apply(Integer in) {
1693   *         return Math.sqrt((int) in);
1694   *       }
1695   *     };
1696   * SortedMap<String, Double> transformed =
1697   *      Maps.transformValues(map, sqrt);
1698   * System.out.println(transformed);
1699   * }</pre>
1700   *
1701   * ... prints {@code {a=2.0, b=3.0}}.
1702   *
1703   * <p>Changes in the underlying map are reflected in this view. Conversely, this view supports
1704   * removal operations, and these are reflected in the underlying map.
1705   *
1706   * <p>It's acceptable for the underlying map to contain null keys, and even null values provided
1707   * that the function is capable of accepting null input. The transformed map might contain null
1708   * values, if the function sometimes gives a null result.
1709   *
1710   * <p>The returned map is not thread-safe or serializable, even if the underlying map is.
1711   *
1712   * <p>The function is applied lazily, invoked when needed. This is necessary for the returned map
1713   * to be a view, but it means that the function will be applied many times for bulk operations
1714   * like {@link Map#containsValue} and {@code Map.toString()}. For this to perform well, {@code
1715   * function} should be fast. To avoid lazy evaluation when the returned map doesn't need to be a
1716   * view, copy the returned map into a new map of your choosing.
1717   *
1718   * @since 11.0
1719   */
1720  public static <
1721          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1722      SortedMap<K, V2> transformValues(
1723          SortedMap<K, V1> fromMap, Function<? super V1, V2> function) {
1724    return transformEntries(fromMap, asEntryTransformer(function));
1725  }
1726
1727  /**
1728   * Returns a view of a navigable map where each value is transformed by a function. All other
1729   * properties of the map, such as iteration order, are left intact. For example, the code:
1730   *
1731   * <pre>{@code
1732   * NavigableMap<String, Integer> map = Maps.newTreeMap();
1733   * map.put("a", 4);
1734   * map.put("b", 9);
1735   * Function<Integer, Double> sqrt =
1736   *     new Function<Integer, Double>() {
1737   *       public Double apply(Integer in) {
1738   *         return Math.sqrt((int) in);
1739   *       }
1740   *     };
1741   * NavigableMap<String, Double> transformed =
1742   *      Maps.transformNavigableValues(map, sqrt);
1743   * System.out.println(transformed);
1744   * }</pre>
1745   *
1746   * ... prints {@code {a=2.0, b=3.0}}.
1747   *
1748   * <p>Changes in the underlying map are reflected in this view. Conversely, this view supports
1749   * removal operations, and these are reflected in the underlying map.
1750   *
1751   * <p>It's acceptable for the underlying map to contain null keys, and even null values provided
1752   * that the function is capable of accepting null input. The transformed map might contain null
1753   * values, if the function sometimes gives a null result.
1754   *
1755   * <p>The returned map is not thread-safe or serializable, even if the underlying map is.
1756   *
1757   * <p>The function is applied lazily, invoked when needed. This is necessary for the returned map
1758   * to be a view, but it means that the function will be applied many times for bulk operations
1759   * like {@link Map#containsValue} and {@code Map.toString()}. For this to perform well, {@code
1760   * function} should be fast. To avoid lazy evaluation when the returned map doesn't need to be a
1761   * view, copy the returned map into a new map of your choosing.
1762   *
1763   * @since 13.0
1764   */
1765  @GwtIncompatible // NavigableMap
1766  public static <
1767          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1768      NavigableMap<K, V2> transformValues(
1769          NavigableMap<K, V1> fromMap, Function<? super V1, V2> function) {
1770    return transformEntries(fromMap, asEntryTransformer(function));
1771  }
1772
1773  /**
1774   * Returns a view of a map whose values are derived from the original map's entries. In contrast
1775   * to {@link #transformValues}, this method's entry-transformation logic may depend on the key as
1776   * well as the value.
1777   *
1778   * <p>All other properties of the transformed map, such as iteration order, are left intact. For
1779   * example, the code:
1780   *
1781   * <pre>{@code
1782   * Map<String, Boolean> options =
1783   *     ImmutableMap.of("verbose", true, "sort", false);
1784   * EntryTransformer<String, Boolean, String> flagPrefixer =
1785   *     new EntryTransformer<String, Boolean, String>() {
1786   *       public String transformEntry(String key, Boolean value) {
1787   *         return value ? key : "no" + key;
1788   *       }
1789   *     };
1790   * Map<String, String> transformed =
1791   *     Maps.transformEntries(options, flagPrefixer);
1792   * System.out.println(transformed);
1793   * }</pre>
1794   *
1795   * ... prints {@code {verbose=verbose, sort=nosort}}.
1796   *
1797   * <p>Changes in the underlying map are reflected in this view. Conversely, this view supports
1798   * removal operations, and these are reflected in the underlying map.
1799   *
1800   * <p>It's acceptable for the underlying map to contain null keys and null values provided that
1801   * the transformer is capable of accepting null inputs. The transformed map might contain null
1802   * values if the transformer sometimes gives a null result.
1803   *
1804   * <p>The returned map is not thread-safe or serializable, even if the underlying map is.
1805   *
1806   * <p>The transformer is applied lazily, invoked when needed. This is necessary for the returned
1807   * map to be a view, but it means that the transformer will be applied many times for bulk
1808   * operations like {@link Map#containsValue} and {@link Object#toString}. For this to perform
1809   * well, {@code transformer} should be fast. To avoid lazy evaluation when the returned map
1810   * doesn't need to be a view, copy the returned map into a new map of your choosing.
1811   *
1812   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of {@code
1813   * EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of
1814   * type {@code K}. Using an {@code EntryTransformer} key type for which this may not hold, such as
1815   * {@code ArrayList}, may risk a {@code ClassCastException} when calling methods on the
1816   * transformed map.
1817   *
1818   * @since 7.0
1819   */
1820  public static <
1821          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1822      Map<K, V2> transformEntries(
1823          Map<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1824    return new TransformedEntriesMap<>(fromMap, transformer);
1825  }
1826
1827  /**
1828   * Returns a view of a sorted map whose values are derived from the original sorted map's entries.
1829   * In contrast to {@link #transformValues}, this method's entry-transformation logic may depend on
1830   * the key as well as the value.
1831   *
1832   * <p>All other properties of the transformed map, such as iteration order, are left intact. For
1833   * example, the code:
1834   *
1835   * <pre>{@code
1836   * Map<String, Boolean> options =
1837   *     ImmutableSortedMap.of("verbose", true, "sort", false);
1838   * EntryTransformer<String, Boolean, String> flagPrefixer =
1839   *     new EntryTransformer<String, Boolean, String>() {
1840   *       public String transformEntry(String key, Boolean value) {
1841   *         return value ? key : "yes" + key;
1842   *       }
1843   *     };
1844   * SortedMap<String, String> transformed =
1845   *     Maps.transformEntries(options, flagPrefixer);
1846   * System.out.println(transformed);
1847   * }</pre>
1848   *
1849   * ... prints {@code {sort=yessort, verbose=verbose}}.
1850   *
1851   * <p>Changes in the underlying map are reflected in this view. Conversely, this view supports
1852   * removal operations, and these are reflected in the underlying map.
1853   *
1854   * <p>It's acceptable for the underlying map to contain null keys and null values provided that
1855   * the transformer is capable of accepting null inputs. The transformed map might contain null
1856   * values if the transformer sometimes gives a null result.
1857   *
1858   * <p>The returned map is not thread-safe or serializable, even if the underlying map is.
1859   *
1860   * <p>The transformer is applied lazily, invoked when needed. This is necessary for the returned
1861   * map to be a view, but it means that the transformer will be applied many times for bulk
1862   * operations like {@link Map#containsValue} and {@link Object#toString}. For this to perform
1863   * well, {@code transformer} should be fast. To avoid lazy evaluation when the returned map
1864   * doesn't need to be a view, copy the returned map into a new map of your choosing.
1865   *
1866   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of {@code
1867   * EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of
1868   * type {@code K}. Using an {@code EntryTransformer} key type for which this may not hold, such as
1869   * {@code ArrayList}, may risk a {@code ClassCastException} when calling methods on the
1870   * transformed map.
1871   *
1872   * @since 11.0
1873   */
1874  public static <
1875          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1876      SortedMap<K, V2> transformEntries(
1877          SortedMap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1878    return new TransformedEntriesSortedMap<>(fromMap, transformer);
1879  }
1880
1881  /**
1882   * Returns a view of a navigable map whose values are derived from the original navigable map's
1883   * entries. In contrast to {@link #transformValues}, this method's entry-transformation logic may
1884   * depend on the key as well as the value.
1885   *
1886   * <p>All other properties of the transformed map, such as iteration order, are left intact. For
1887   * example, the code:
1888   *
1889   * <pre>{@code
1890   * NavigableMap<String, Boolean> options = Maps.newTreeMap();
1891   * options.put("verbose", false);
1892   * options.put("sort", true);
1893   * EntryTransformer<String, Boolean, String> flagPrefixer =
1894   *     new EntryTransformer<String, Boolean, String>() {
1895   *       public String transformEntry(String key, Boolean value) {
1896   *         return value ? key : ("yes" + key);
1897   *       }
1898   *     };
1899   * NavigableMap<String, String> transformed =
1900   *     LabsMaps.transformNavigableEntries(options, flagPrefixer);
1901   * System.out.println(transformed);
1902   * }</pre>
1903   *
1904   * ... prints {@code {sort=yessort, verbose=verbose}}.
1905   *
1906   * <p>Changes in the underlying map are reflected in this view. Conversely, this view supports
1907   * removal operations, and these are reflected in the underlying map.
1908   *
1909   * <p>It's acceptable for the underlying map to contain null keys and null values provided that
1910   * the transformer is capable of accepting null inputs. The transformed map might contain null
1911   * values if the transformer sometimes gives a null result.
1912   *
1913   * <p>The returned map is not thread-safe or serializable, even if the underlying map is.
1914   *
1915   * <p>The transformer is applied lazily, invoked when needed. This is necessary for the returned
1916   * map to be a view, but it means that the transformer will be applied many times for bulk
1917   * operations like {@link Map#containsValue} and {@link Object#toString}. For this to perform
1918   * well, {@code transformer} should be fast. To avoid lazy evaluation when the returned map
1919   * doesn't need to be a view, copy the returned map into a new map of your choosing.
1920   *
1921   * <p><b>Warning:</b> This method assumes that for any instance {@code k} of {@code
1922   * EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of
1923   * type {@code K}. Using an {@code EntryTransformer} key type for which this may not hold, such as
1924   * {@code ArrayList}, may risk a {@code ClassCastException} when calling methods on the
1925   * transformed map.
1926   *
1927   * @since 13.0
1928   */
1929  @GwtIncompatible // NavigableMap
1930  public static <
1931          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1932      NavigableMap<K, V2> transformEntries(
1933          NavigableMap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
1934    return new TransformedEntriesNavigableMap<>(fromMap, transformer);
1935  }
1936
1937  /**
1938   * A transformation of the value of a key-value pair, using both key and value as inputs. To apply
1939   * the transformation to a map, use {@link Maps#transformEntries(Map, EntryTransformer)}.
1940   *
1941   * @param <K> the key type of the input and output entries
1942   * @param <V1> the value type of the input entry
1943   * @param <V2> the value type of the output entry
1944   * @since 7.0
1945   */
1946  public interface EntryTransformer<
1947      K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object> {
1948    /**
1949     * Determines an output value based on a key-value pair. This method is <i>generally
1950     * expected</i>, but not absolutely required, to have the following properties:
1951     *
1952     * <ul>
1953     *   <li>Its execution does not cause any observable side effects.
1954     *   <li>The computation is <i>consistent with equals</i>; that is, {@link Objects#equal
1955     *       Objects.equal}{@code (k1, k2) &&} {@link Objects#equal}{@code (v1, v2)} implies that
1956     *       {@code Objects.equal(transformer.transform(k1, v1), transformer.transform(k2, v2))}.
1957     * </ul>
1958     *
1959     * @throws NullPointerException if the key or value is null and this transformer does not accept
1960     *     null arguments
1961     */
1962    @ParametricNullness
1963    V2 transformEntry(@ParametricNullness K key, @ParametricNullness V1 value);
1964  }
1965
1966  /** Views a function as an entry transformer that ignores the entry key. */
1967  static <K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1968      EntryTransformer<K, V1, V2> asEntryTransformer(final Function<? super V1, V2> function) {
1969    checkNotNull(function);
1970    return new EntryTransformer<K, V1, V2>() {
1971      @Override
1972      @ParametricNullness
1973      public V2 transformEntry(@ParametricNullness K key, @ParametricNullness V1 value) {
1974        return function.apply(value);
1975      }
1976    };
1977  }
1978
1979  static <K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1980      Function<V1, V2> asValueToValueFunction(
1981          final EntryTransformer<? super K, V1, V2> transformer, @ParametricNullness final K key) {
1982    checkNotNull(transformer);
1983    return new Function<V1, V2>() {
1984      @Override
1985      @ParametricNullness
1986      public V2 apply(@ParametricNullness V1 v1) {
1987        return transformer.transformEntry(key, v1);
1988      }
1989    };
1990  }
1991
1992  /** Views an entry transformer as a function from {@code Entry} to values. */
1993  static <K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
1994      Function<Entry<K, V1>, V2> asEntryToValueFunction(
1995          final EntryTransformer<? super K, ? super V1, V2> transformer) {
1996    checkNotNull(transformer);
1997    return new Function<Entry<K, V1>, V2>() {
1998      @Override
1999      @ParametricNullness
2000      public V2 apply(Entry<K, V1> entry) {
2001        return transformer.transformEntry(entry.getKey(), entry.getValue());
2002      }
2003    };
2004  }
2005
2006  /** Returns a view of an entry transformed by the specified transformer. */
2007  static <V2 extends @Nullable Object, K extends @Nullable Object, V1 extends @Nullable Object>
2008      Entry<K, V2> transformEntry(
2009          final EntryTransformer<? super K, ? super V1, V2> transformer, final Entry<K, V1> entry) {
2010    checkNotNull(transformer);
2011    checkNotNull(entry);
2012    return new AbstractMapEntry<K, V2>() {
2013      @Override
2014      @ParametricNullness
2015      public K getKey() {
2016        return entry.getKey();
2017      }
2018
2019      @Override
2020      @ParametricNullness
2021      public V2 getValue() {
2022        return transformer.transformEntry(entry.getKey(), entry.getValue());
2023      }
2024    };
2025  }
2026
2027  /** Views an entry transformer as a function from entries to entries. */
2028  static <K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
2029      Function<Entry<K, V1>, Entry<K, V2>> asEntryToEntryFunction(
2030          final EntryTransformer<? super K, ? super V1, V2> transformer) {
2031    checkNotNull(transformer);
2032    return new Function<Entry<K, V1>, Entry<K, V2>>() {
2033      @Override
2034      public Entry<K, V2> apply(final Entry<K, V1> entry) {
2035        return transformEntry(transformer, entry);
2036      }
2037    };
2038  }
2039
2040  static class TransformedEntriesMap<
2041          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
2042      extends IteratorBasedAbstractMap<K, V2> {
2043    final Map<K, V1> fromMap;
2044    final EntryTransformer<? super K, ? super V1, V2> transformer;
2045
2046    TransformedEntriesMap(
2047        Map<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
2048      this.fromMap = checkNotNull(fromMap);
2049      this.transformer = checkNotNull(transformer);
2050    }
2051
2052    @Override
2053    public int size() {
2054      return fromMap.size();
2055    }
2056
2057    @Override
2058    public boolean containsKey(@CheckForNull Object key) {
2059      return fromMap.containsKey(key);
2060    }
2061
2062    // safe as long as the user followed the <b>Warning</b> in the javadoc
2063    @SuppressWarnings("unchecked")
2064    @Override
2065    @CheckForNull
2066    public V2 get(@CheckForNull Object key) {
2067      V1 value = fromMap.get(key);
2068      if (value != null || fromMap.containsKey(key)) {
2069        // The cast is safe because of the containsKey check.
2070        return transformer.transformEntry((K) key, uncheckedCastNullableTToT(value));
2071      }
2072      return null;
2073    }
2074
2075    // safe as long as the user followed the <b>Warning</b> in the javadoc
2076    @SuppressWarnings("unchecked")
2077    @Override
2078    @CheckForNull
2079    public V2 remove(@CheckForNull Object key) {
2080      return fromMap.containsKey(key)
2081          // The cast is safe because of the containsKey check.
2082          ? transformer.transformEntry((K) key, uncheckedCastNullableTToT(fromMap.remove(key)))
2083          : null;
2084    }
2085
2086    @Override
2087    public void clear() {
2088      fromMap.clear();
2089    }
2090
2091    @Override
2092    public Set<K> keySet() {
2093      return fromMap.keySet();
2094    }
2095
2096    @Override
2097    Iterator<Entry<K, V2>> entryIterator() {
2098      return Iterators.transform(
2099          fromMap.entrySet().iterator(), Maps.<K, V1, V2>asEntryToEntryFunction(transformer));
2100    }
2101
2102    @Override
2103    public Collection<V2> values() {
2104      return new Values<>(this);
2105    }
2106  }
2107
2108  static class TransformedEntriesSortedMap<
2109          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
2110      extends TransformedEntriesMap<K, V1, V2> implements SortedMap<K, V2> {
2111
2112    protected SortedMap<K, V1> fromMap() {
2113      return (SortedMap<K, V1>) fromMap;
2114    }
2115
2116    TransformedEntriesSortedMap(
2117        SortedMap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
2118      super(fromMap, transformer);
2119    }
2120
2121    @Override
2122    @CheckForNull
2123    public Comparator<? super K> comparator() {
2124      return fromMap().comparator();
2125    }
2126
2127    @Override
2128    @ParametricNullness
2129    public K firstKey() {
2130      return fromMap().firstKey();
2131    }
2132
2133    @Override
2134    public SortedMap<K, V2> headMap(@ParametricNullness K toKey) {
2135      return transformEntries(fromMap().headMap(toKey), transformer);
2136    }
2137
2138    @Override
2139    @ParametricNullness
2140    public K lastKey() {
2141      return fromMap().lastKey();
2142    }
2143
2144    @Override
2145    public SortedMap<K, V2> subMap(@ParametricNullness K fromKey, @ParametricNullness K toKey) {
2146      return transformEntries(fromMap().subMap(fromKey, toKey), transformer);
2147    }
2148
2149    @Override
2150    public SortedMap<K, V2> tailMap(@ParametricNullness K fromKey) {
2151      return transformEntries(fromMap().tailMap(fromKey), transformer);
2152    }
2153  }
2154
2155  @GwtIncompatible // NavigableMap
2156  private static class TransformedEntriesNavigableMap<
2157          K extends @Nullable Object, V1 extends @Nullable Object, V2 extends @Nullable Object>
2158      extends TransformedEntriesSortedMap<K, V1, V2> implements NavigableMap<K, V2> {
2159
2160    TransformedEntriesNavigableMap(
2161        NavigableMap<K, V1> fromMap, EntryTransformer<? super K, ? super V1, V2> transformer) {
2162      super(fromMap, transformer);
2163    }
2164
2165    @Override
2166    @CheckForNull
2167    public Entry<K, V2> ceilingEntry(@ParametricNullness K key) {
2168      return transformEntry(fromMap().ceilingEntry(key));
2169    }
2170
2171    @Override
2172    @CheckForNull
2173    public K ceilingKey(@ParametricNullness K key) {
2174      return fromMap().ceilingKey(key);
2175    }
2176
2177    @Override
2178    public NavigableSet<K> descendingKeySet() {
2179      return fromMap().descendingKeySet();
2180    }
2181
2182    @Override
2183    public NavigableMap<K, V2> descendingMap() {
2184      return transformEntries(fromMap().descendingMap(), transformer);
2185    }
2186
2187    @Override
2188    @CheckForNull
2189    public Entry<K, V2> firstEntry() {
2190      return transformEntry(fromMap().firstEntry());
2191    }
2192
2193    @Override
2194    @CheckForNull
2195    public Entry<K, V2> floorEntry(@ParametricNullness K key) {
2196      return transformEntry(fromMap().floorEntry(key));
2197    }
2198
2199    @Override
2200    @CheckForNull
2201    public K floorKey(@ParametricNullness K key) {
2202      return fromMap().floorKey(key);
2203    }
2204
2205    @Override
2206    public NavigableMap<K, V2> headMap(@ParametricNullness K toKey) {
2207      return headMap(toKey, false);
2208    }
2209
2210    @Override
2211    public NavigableMap<K, V2> headMap(@ParametricNullness K toKey, boolean inclusive) {
2212      return transformEntries(fromMap().headMap(toKey, inclusive), transformer);
2213    }
2214
2215    @Override
2216    @CheckForNull
2217    public Entry<K, V2> higherEntry(@ParametricNullness K key) {
2218      return transformEntry(fromMap().higherEntry(key));
2219    }
2220
2221    @Override
2222    @CheckForNull
2223    public K higherKey(@ParametricNullness K key) {
2224      return fromMap().higherKey(key);
2225    }
2226
2227    @Override
2228    @CheckForNull
2229    public Entry<K, V2> lastEntry() {
2230      return transformEntry(fromMap().lastEntry());
2231    }
2232
2233    @Override
2234    @CheckForNull
2235    public Entry<K, V2> lowerEntry(@ParametricNullness K key) {
2236      return transformEntry(fromMap().lowerEntry(key));
2237    }
2238
2239    @Override
2240    @CheckForNull
2241    public K lowerKey(@ParametricNullness K key) {
2242      return fromMap().lowerKey(key);
2243    }
2244
2245    @Override
2246    public NavigableSet<K> navigableKeySet() {
2247      return fromMap().navigableKeySet();
2248    }
2249
2250    @Override
2251    @CheckForNull
2252    public Entry<K, V2> pollFirstEntry() {
2253      return transformEntry(fromMap().pollFirstEntry());
2254    }
2255
2256    @Override
2257    @CheckForNull
2258    public Entry<K, V2> pollLastEntry() {
2259      return transformEntry(fromMap().pollLastEntry());
2260    }
2261
2262    @Override
2263    public NavigableMap<K, V2> subMap(
2264        @ParametricNullness K fromKey,
2265        boolean fromInclusive,
2266        @ParametricNullness K toKey,
2267        boolean toInclusive) {
2268      return transformEntries(
2269          fromMap().subMap(fromKey, fromInclusive, toKey, toInclusive), transformer);
2270    }
2271
2272    @Override
2273    public NavigableMap<K, V2> subMap(@ParametricNullness K fromKey, @ParametricNullness K toKey) {
2274      return subMap(fromKey, true, toKey, false);
2275    }
2276
2277    @Override
2278    public NavigableMap<K, V2> tailMap(@ParametricNullness K fromKey) {
2279      return tailMap(fromKey, true);
2280    }
2281
2282    @Override
2283    public NavigableMap<K, V2> tailMap(@ParametricNullness K fromKey, boolean inclusive) {
2284      return transformEntries(fromMap().tailMap(fromKey, inclusive), transformer);
2285    }
2286
2287    @CheckForNull
2288    private Entry<K, V2> transformEntry(@CheckForNull Entry<K, V1> entry) {
2289      return (entry == null) ? null : Maps.transformEntry(transformer, entry);
2290    }
2291
2292    @Override
2293    protected NavigableMap<K, V1> fromMap() {
2294      return (NavigableMap<K, V1>) super.fromMap();
2295    }
2296  }
2297
2298  static <K extends @Nullable Object> Predicate<Entry<K, ?>> keyPredicateOnEntries(
2299      Predicate<? super K> keyPredicate) {
2300    return compose(keyPredicate, Maps.<K>keyFunction());
2301  }
2302
2303  static <V extends @Nullable Object> Predicate<Entry<?, V>> valuePredicateOnEntries(
2304      Predicate<? super V> valuePredicate) {
2305    return compose(valuePredicate, Maps.<V>valueFunction());
2306  }
2307
2308  /**
2309   * Returns a map containing the mappings in {@code unfiltered} whose keys satisfy a predicate. The
2310   * returned map is a live view of {@code unfiltered}; changes to one affect the other.
2311   *
2312   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2313   * iterators that don't support {@code remove()}, but all other methods are supported by the map
2314   * and its views. When given a key that doesn't satisfy the predicate, the map's {@code put()} and
2315   * {@code putAll()} methods throw an {@link IllegalArgumentException}.
2316   *
2317   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered map
2318   * or its views, only mappings whose keys satisfy the filter will be removed from the underlying
2319   * map.
2320   *
2321   * <p>The returned map isn't threadsafe or serializable, even if {@code unfiltered} is.
2322   *
2323   * <p>Many of the filtered map's methods, such as {@code size()}, iterate across every key/value
2324   * mapping in the underlying map and determine which satisfy the filter. When a live view is
2325   * <i>not</i> needed, it may be faster to copy the filtered map and use the copy.
2326   *
2327   * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at
2328   * {@link Predicate#apply}. Do not provide a predicate such as {@code
2329   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2330   */
2331  public static <K extends @Nullable Object, V extends @Nullable Object> Map<K, V> filterKeys(
2332      Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2333    checkNotNull(keyPredicate);
2334    Predicate<Entry<K, ?>> entryPredicate = keyPredicateOnEntries(keyPredicate);
2335    return (unfiltered instanceof AbstractFilteredMap)
2336        ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
2337        : new FilteredKeyMap<K, V>(checkNotNull(unfiltered), keyPredicate, entryPredicate);
2338  }
2339
2340  /**
2341   * Returns a sorted map containing the mappings in {@code unfiltered} whose keys satisfy a
2342   * predicate. The returned map is a live view of {@code unfiltered}; changes to one affect the
2343   * other.
2344   *
2345   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2346   * iterators that don't support {@code remove()}, but all other methods are supported by the map
2347   * and its views. When given a key that doesn't satisfy the predicate, the map's {@code put()} and
2348   * {@code putAll()} methods throw an {@link IllegalArgumentException}.
2349   *
2350   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered map
2351   * or its views, only mappings whose keys satisfy the filter will be removed from the underlying
2352   * map.
2353   *
2354   * <p>The returned map isn't threadsafe or serializable, even if {@code unfiltered} is.
2355   *
2356   * <p>Many of the filtered map's methods, such as {@code size()}, iterate across every key/value
2357   * mapping in the underlying map and determine which satisfy the filter. When a live view is
2358   * <i>not</i> needed, it may be faster to copy the filtered map and use the copy.
2359   *
2360   * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at
2361   * {@link Predicate#apply}. Do not provide a predicate such as {@code
2362   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2363   *
2364   * @since 11.0
2365   */
2366  public static <K extends @Nullable Object, V extends @Nullable Object> SortedMap<K, V> filterKeys(
2367      SortedMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2368    // TODO(lowasser): Return a subclass of Maps.FilteredKeyMap for slightly better
2369    // performance.
2370    return filterEntries(unfiltered, Maps.<K>keyPredicateOnEntries(keyPredicate));
2371  }
2372
2373  /**
2374   * Returns a navigable map containing the mappings in {@code unfiltered} whose keys satisfy a
2375   * predicate. The returned map is a live view of {@code unfiltered}; changes to one affect the
2376   * other.
2377   *
2378   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2379   * iterators that don't support {@code remove()}, but all other methods are supported by the map
2380   * and its views. When given a key that doesn't satisfy the predicate, the map's {@code put()} and
2381   * {@code putAll()} methods throw an {@link IllegalArgumentException}.
2382   *
2383   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered map
2384   * or its views, only mappings whose keys satisfy the filter will be removed from the underlying
2385   * map.
2386   *
2387   * <p>The returned map isn't threadsafe or serializable, even if {@code unfiltered} is.
2388   *
2389   * <p>Many of the filtered map's methods, such as {@code size()}, iterate across every key/value
2390   * mapping in the underlying map and determine which satisfy the filter. When a live view is
2391   * <i>not</i> needed, it may be faster to copy the filtered map and use the copy.
2392   *
2393   * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with equals</i>, as documented at
2394   * {@link Predicate#apply}. Do not provide a predicate such as {@code
2395   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2396   *
2397   * @since 14.0
2398   */
2399  @GwtIncompatible // NavigableMap
2400  public static <K extends @Nullable Object, V extends @Nullable Object>
2401      NavigableMap<K, V> filterKeys(
2402          NavigableMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2403    // TODO(lowasser): Return a subclass of Maps.FilteredKeyMap for slightly better
2404    // performance.
2405    return filterEntries(unfiltered, Maps.<K>keyPredicateOnEntries(keyPredicate));
2406  }
2407
2408  /**
2409   * Returns a bimap containing the mappings in {@code unfiltered} whose keys satisfy a predicate.
2410   * The returned bimap is a live view of {@code unfiltered}; changes to one affect the other.
2411   *
2412   * <p>The resulting bimap's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2413   * iterators that don't support {@code remove()}, but all other methods are supported by the bimap
2414   * and its views. When given a key that doesn't satisfy the predicate, the bimap's {@code put()},
2415   * {@code forcePut()} and {@code putAll()} methods throw an {@link IllegalArgumentException}.
2416   *
2417   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2418   * bimap or its views, only mappings that satisfy the filter will be removed from the underlying
2419   * bimap.
2420   *
2421   * <p>The returned bimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2422   *
2423   * <p>Many of the filtered bimap's methods, such as {@code size()}, iterate across every key in
2424   * the underlying bimap and determine which satisfy the filter. When a live view is <i>not</i>
2425   * needed, it may be faster to copy the filtered bimap and use the copy.
2426   *
2427   * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals </i>, as documented
2428   * at {@link Predicate#apply}.
2429   *
2430   * @since 14.0
2431   */
2432  public static <K extends @Nullable Object, V extends @Nullable Object> BiMap<K, V> filterKeys(
2433      BiMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
2434    checkNotNull(keyPredicate);
2435    return filterEntries(unfiltered, Maps.<K>keyPredicateOnEntries(keyPredicate));
2436  }
2437
2438  /**
2439   * Returns a map containing the mappings in {@code unfiltered} whose values satisfy a predicate.
2440   * The returned map is a live view of {@code unfiltered}; changes to one affect the other.
2441   *
2442   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2443   * iterators that don't support {@code remove()}, but all other methods are supported by the map
2444   * and its views. When given a value that doesn't satisfy the predicate, the map's {@code put()},
2445   * {@code putAll()}, and {@link Entry#setValue} methods throw an {@link IllegalArgumentException}.
2446   *
2447   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered map
2448   * or its views, only mappings whose values satisfy the filter will be removed from the underlying
2449   * map.
2450   *
2451   * <p>The returned map isn't threadsafe or serializable, even if {@code unfiltered} is.
2452   *
2453   * <p>Many of the filtered map's methods, such as {@code size()}, iterate across every key/value
2454   * mapping in the underlying map and determine which satisfy the filter. When a live view is
2455   * <i>not</i> needed, it may be faster to copy the filtered map and use the copy.
2456   *
2457   * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with equals</i>, as documented
2458   * at {@link Predicate#apply}. Do not provide a predicate such as {@code
2459   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2460   */
2461  public static <K extends @Nullable Object, V extends @Nullable Object> Map<K, V> filterValues(
2462      Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2463    return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2464  }
2465
2466  /**
2467   * Returns a sorted map containing the mappings in {@code unfiltered} whose values satisfy a
2468   * predicate. The returned map is a live view of {@code unfiltered}; changes to one affect the
2469   * other.
2470   *
2471   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2472   * iterators that don't support {@code remove()}, but all other methods are supported by the map
2473   * and its views. When given a value that doesn't satisfy the predicate, the map's {@code put()},
2474   * {@code putAll()}, and {@link Entry#setValue} methods throw an {@link IllegalArgumentException}.
2475   *
2476   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered map
2477   * or its views, only mappings whose values satisfy the filter will be removed from the underlying
2478   * map.
2479   *
2480   * <p>The returned map isn't threadsafe or serializable, even if {@code unfiltered} is.
2481   *
2482   * <p>Many of the filtered map's methods, such as {@code size()}, iterate across every key/value
2483   * mapping in the underlying map and determine which satisfy the filter. When a live view is
2484   * <i>not</i> needed, it may be faster to copy the filtered map and use the copy.
2485   *
2486   * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with equals</i>, as documented
2487   * at {@link Predicate#apply}. Do not provide a predicate such as {@code
2488   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2489   *
2490   * @since 11.0
2491   */
2492  public static <K extends @Nullable Object, V extends @Nullable Object>
2493      SortedMap<K, V> filterValues(
2494          SortedMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2495    return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2496  }
2497
2498  /**
2499   * Returns a navigable map containing the mappings in {@code unfiltered} whose values satisfy a
2500   * predicate. The returned map is a live view of {@code unfiltered}; changes to one affect the
2501   * other.
2502   *
2503   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2504   * iterators that don't support {@code remove()}, but all other methods are supported by the map
2505   * and its views. When given a value that doesn't satisfy the predicate, the map's {@code put()},
2506   * {@code putAll()}, and {@link Entry#setValue} methods throw an {@link IllegalArgumentException}.
2507   *
2508   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered map
2509   * or its views, only mappings whose values satisfy the filter will be removed from the underlying
2510   * map.
2511   *
2512   * <p>The returned map isn't threadsafe or serializable, even if {@code unfiltered} is.
2513   *
2514   * <p>Many of the filtered map's methods, such as {@code size()}, iterate across every key/value
2515   * mapping in the underlying map and determine which satisfy the filter. When a live view is
2516   * <i>not</i> needed, it may be faster to copy the filtered map and use the copy.
2517   *
2518   * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with equals</i>, as documented
2519   * at {@link Predicate#apply}. Do not provide a predicate such as {@code
2520   * Predicates.instanceOf(ArrayList.class)}, which is inconsistent with equals.
2521   *
2522   * @since 14.0
2523   */
2524  @GwtIncompatible // NavigableMap
2525  public static <K extends @Nullable Object, V extends @Nullable Object>
2526      NavigableMap<K, V> filterValues(
2527          NavigableMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2528    return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2529  }
2530
2531  /**
2532   * Returns a bimap containing the mappings in {@code unfiltered} whose values satisfy a predicate.
2533   * The returned bimap is a live view of {@code unfiltered}; changes to one affect the other.
2534   *
2535   * <p>The resulting bimap's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2536   * iterators that don't support {@code remove()}, but all other methods are supported by the bimap
2537   * and its views. When given a value that doesn't satisfy the predicate, the bimap's {@code
2538   * put()}, {@code forcePut()} and {@code putAll()} methods throw an {@link
2539   * IllegalArgumentException}. Similarly, the map's entries have a {@link Entry#setValue} method
2540   * that throws an {@link IllegalArgumentException} when the provided value doesn't satisfy the
2541   * predicate.
2542   *
2543   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2544   * bimap or its views, only mappings that satisfy the filter will be removed from the underlying
2545   * bimap.
2546   *
2547   * <p>The returned bimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2548   *
2549   * <p>Many of the filtered bimap's methods, such as {@code size()}, iterate across every value in
2550   * the underlying bimap and determine which satisfy the filter. When a live view is <i>not</i>
2551   * needed, it may be faster to copy the filtered bimap and use the copy.
2552   *
2553   * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals </i>, as documented
2554   * at {@link Predicate#apply}.
2555   *
2556   * @since 14.0
2557   */
2558  public static <K extends @Nullable Object, V extends @Nullable Object> BiMap<K, V> filterValues(
2559      BiMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
2560    return filterEntries(unfiltered, Maps.<V>valuePredicateOnEntries(valuePredicate));
2561  }
2562
2563  /**
2564   * Returns a map containing the mappings in {@code unfiltered} that satisfy a predicate. The
2565   * returned map is a live view of {@code unfiltered}; changes to one affect the other.
2566   *
2567   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2568   * iterators that don't support {@code remove()}, but all other methods are supported by the map
2569   * and its views. When given a key/value pair that doesn't satisfy the predicate, the map's {@code
2570   * put()} and {@code putAll()} methods throw an {@link IllegalArgumentException}. Similarly, the
2571   * map's entries have a {@link Entry#setValue} method that throws an {@link
2572   * IllegalArgumentException} when the existing key and the provided value don't satisfy the
2573   * predicate.
2574   *
2575   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered map
2576   * or its views, only mappings that satisfy the filter will be removed from the underlying map.
2577   *
2578   * <p>The returned map isn't threadsafe or serializable, even if {@code unfiltered} is.
2579   *
2580   * <p>Many of the filtered map's methods, such as {@code size()}, iterate across every key/value
2581   * mapping in the underlying map and determine which satisfy the filter. When a live view is
2582   * <i>not</i> needed, it may be faster to copy the filtered map and use the copy.
2583   *
2584   * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals</i>, as documented
2585   * at {@link Predicate#apply}.
2586   */
2587  public static <K extends @Nullable Object, V extends @Nullable Object> Map<K, V> filterEntries(
2588      Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2589    checkNotNull(entryPredicate);
2590    return (unfiltered instanceof AbstractFilteredMap)
2591        ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
2592        : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
2593  }
2594
2595  /**
2596   * Returns a sorted map containing the mappings in {@code unfiltered} that satisfy a predicate.
2597   * The returned map is a live view of {@code unfiltered}; changes to one affect the other.
2598   *
2599   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2600   * iterators that don't support {@code remove()}, but all other methods are supported by the map
2601   * and its views. When given a key/value pair that doesn't satisfy the predicate, the map's {@code
2602   * put()} and {@code putAll()} methods throw an {@link IllegalArgumentException}. Similarly, the
2603   * map's entries have a {@link Entry#setValue} method that throws an {@link
2604   * IllegalArgumentException} when the existing key and the provided value don't satisfy the
2605   * predicate.
2606   *
2607   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered map
2608   * or its views, only mappings that satisfy the filter will be removed from the underlying map.
2609   *
2610   * <p>The returned map isn't threadsafe or serializable, even if {@code unfiltered} is.
2611   *
2612   * <p>Many of the filtered map's methods, such as {@code size()}, iterate across every key/value
2613   * mapping in the underlying map and determine which satisfy the filter. When a live view is
2614   * <i>not</i> needed, it may be faster to copy the filtered map and use the copy.
2615   *
2616   * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals</i>, as documented
2617   * at {@link Predicate#apply}.
2618   *
2619   * @since 11.0
2620   */
2621  public static <K extends @Nullable Object, V extends @Nullable Object>
2622      SortedMap<K, V> filterEntries(
2623          SortedMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2624    checkNotNull(entryPredicate);
2625    return (unfiltered instanceof FilteredEntrySortedMap)
2626        ? filterFiltered((FilteredEntrySortedMap<K, V>) unfiltered, entryPredicate)
2627        : new FilteredEntrySortedMap<K, V>(checkNotNull(unfiltered), entryPredicate);
2628  }
2629
2630  /**
2631   * Returns a sorted map containing the mappings in {@code unfiltered} that satisfy a predicate.
2632   * The returned map is a live view of {@code unfiltered}; changes to one affect the other.
2633   *
2634   * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2635   * iterators that don't support {@code remove()}, but all other methods are supported by the map
2636   * and its views. When given a key/value pair that doesn't satisfy the predicate, the map's {@code
2637   * put()} and {@code putAll()} methods throw an {@link IllegalArgumentException}. Similarly, the
2638   * map's entries have a {@link Entry#setValue} method that throws an {@link
2639   * IllegalArgumentException} when the existing key and the provided value don't satisfy the
2640   * predicate.
2641   *
2642   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered map
2643   * or its views, only mappings that satisfy the filter will be removed from the underlying map.
2644   *
2645   * <p>The returned map isn't threadsafe or serializable, even if {@code unfiltered} is.
2646   *
2647   * <p>Many of the filtered map's methods, such as {@code size()}, iterate across every key/value
2648   * mapping in the underlying map and determine which satisfy the filter. When a live view is
2649   * <i>not</i> needed, it may be faster to copy the filtered map and use the copy.
2650   *
2651   * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals</i>, as documented
2652   * at {@link Predicate#apply}.
2653   *
2654   * @since 14.0
2655   */
2656  @GwtIncompatible // NavigableMap
2657  public static <K extends @Nullable Object, V extends @Nullable Object>
2658      NavigableMap<K, V> filterEntries(
2659          NavigableMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2660    checkNotNull(entryPredicate);
2661    return (unfiltered instanceof FilteredEntryNavigableMap)
2662        ? filterFiltered((FilteredEntryNavigableMap<K, V>) unfiltered, entryPredicate)
2663        : new FilteredEntryNavigableMap<K, V>(checkNotNull(unfiltered), entryPredicate);
2664  }
2665
2666  /**
2667   * Returns a bimap containing the mappings in {@code unfiltered} that satisfy a predicate. The
2668   * returned bimap is a live view of {@code unfiltered}; changes to one affect the other.
2669   *
2670   * <p>The resulting bimap's {@code keySet()}, {@code entrySet()}, and {@code values()} views have
2671   * iterators that don't support {@code remove()}, but all other methods are supported by the bimap
2672   * and its views. When given a key/value pair that doesn't satisfy the predicate, the bimap's
2673   * {@code put()}, {@code forcePut()} and {@code putAll()} methods throw an {@link
2674   * IllegalArgumentException}. Similarly, the map's entries have an {@link Entry#setValue} method
2675   * that throws an {@link IllegalArgumentException} when the existing key and the provided value
2676   * don't satisfy the predicate.
2677   *
2678   * <p>When methods such as {@code removeAll()} and {@code clear()} are called on the filtered
2679   * bimap or its views, only mappings that satisfy the filter will be removed from the underlying
2680   * bimap.
2681   *
2682   * <p>The returned bimap isn't threadsafe or serializable, even if {@code unfiltered} is.
2683   *
2684   * <p>Many of the filtered bimap's methods, such as {@code size()}, iterate across every key/value
2685   * mapping in the underlying bimap and determine which satisfy the filter. When a live view is
2686   * <i>not</i> needed, it may be faster to copy the filtered bimap and use the copy.
2687   *
2688   * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with equals </i>, as documented
2689   * at {@link Predicate#apply}.
2690   *
2691   * @since 14.0
2692   */
2693  public static <K extends @Nullable Object, V extends @Nullable Object> BiMap<K, V> filterEntries(
2694      BiMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2695    checkNotNull(unfiltered);
2696    checkNotNull(entryPredicate);
2697    return (unfiltered instanceof FilteredEntryBiMap)
2698        ? filterFiltered((FilteredEntryBiMap<K, V>) unfiltered, entryPredicate)
2699        : new FilteredEntryBiMap<K, V>(unfiltered, entryPredicate);
2700  }
2701
2702  /**
2703   * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when filtering a filtered
2704   * map.
2705   */
2706  private static <K extends @Nullable Object, V extends @Nullable Object> Map<K, V> filterFiltered(
2707      AbstractFilteredMap<K, V> map, Predicate<? super Entry<K, V>> entryPredicate) {
2708    return new FilteredEntryMap<>(
2709        map.unfiltered, Predicates.<Entry<K, V>>and(map.predicate, entryPredicate));
2710  }
2711
2712  /**
2713   * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when filtering a filtered
2714   * sorted map.
2715   */
2716  private static <K extends @Nullable Object, V extends @Nullable Object>
2717      SortedMap<K, V> filterFiltered(
2718          FilteredEntrySortedMap<K, V> map, Predicate<? super Entry<K, V>> entryPredicate) {
2719    Predicate<Entry<K, V>> predicate = Predicates.<Entry<K, V>>and(map.predicate, entryPredicate);
2720    return new FilteredEntrySortedMap<>(map.sortedMap(), predicate);
2721  }
2722
2723  /**
2724   * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when filtering a filtered
2725   * navigable map.
2726   */
2727  @GwtIncompatible // NavigableMap
2728  private static <K extends @Nullable Object, V extends @Nullable Object>
2729      NavigableMap<K, V> filterFiltered(
2730          FilteredEntryNavigableMap<K, V> map, Predicate<? super Entry<K, V>> entryPredicate) {
2731    Predicate<Entry<K, V>> predicate =
2732        Predicates.<Entry<K, V>>and(map.entryPredicate, entryPredicate);
2733    return new FilteredEntryNavigableMap<>(map.unfiltered, predicate);
2734  }
2735
2736  /**
2737   * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when filtering a filtered
2738   * map.
2739   */
2740  private static <K extends @Nullable Object, V extends @Nullable Object>
2741      BiMap<K, V> filterFiltered(
2742          FilteredEntryBiMap<K, V> map, Predicate<? super Entry<K, V>> entryPredicate) {
2743    Predicate<Entry<K, V>> predicate = Predicates.<Entry<K, V>>and(map.predicate, entryPredicate);
2744    return new FilteredEntryBiMap<>(map.unfiltered(), predicate);
2745  }
2746
2747  private abstract static class AbstractFilteredMap<
2748          K extends @Nullable Object, V extends @Nullable Object>
2749      extends ViewCachingAbstractMap<K, V> {
2750    final Map<K, V> unfiltered;
2751    final Predicate<? super Entry<K, V>> predicate;
2752
2753    AbstractFilteredMap(Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
2754      this.unfiltered = unfiltered;
2755      this.predicate = predicate;
2756    }
2757
2758    boolean apply(@CheckForNull Object key, @ParametricNullness V value) {
2759      // This method is called only when the key is in the map (or about to be added to the map),
2760      // implying that key is a K.
2761      @SuppressWarnings({"unchecked", "nullness"})
2762      K k = (K) key;
2763      return predicate.apply(Maps.immutableEntry(k, value));
2764    }
2765
2766    @Override
2767    @CheckForNull
2768    public V put(@ParametricNullness K key, @ParametricNullness V value) {
2769      checkArgument(apply(key, value));
2770      return unfiltered.put(key, value);
2771    }
2772
2773    @Override
2774    public void putAll(Map<? extends K, ? extends V> map) {
2775      for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
2776        checkArgument(apply(entry.getKey(), entry.getValue()));
2777      }
2778      unfiltered.putAll(map);
2779    }
2780
2781    @Override
2782    public boolean containsKey(@CheckForNull Object key) {
2783      return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
2784    }
2785
2786    @Override
2787    @CheckForNull
2788    public V get(@CheckForNull Object key) {
2789      V value = unfiltered.get(key);
2790      return ((value != null) && apply(key, value)) ? value : null;
2791    }
2792
2793    @Override
2794    public boolean isEmpty() {
2795      return entrySet().isEmpty();
2796    }
2797
2798    @Override
2799    @CheckForNull
2800    public V remove(@CheckForNull Object key) {
2801      return containsKey(key) ? unfiltered.remove(key) : null;
2802    }
2803
2804    @Override
2805    Collection<V> createValues() {
2806      return new FilteredMapValues<>(this, unfiltered, predicate);
2807    }
2808  }
2809
2810  private static final class FilteredMapValues<
2811          K extends @Nullable Object, V extends @Nullable Object>
2812      extends Maps.Values<K, V> {
2813    final Map<K, V> unfiltered;
2814    final Predicate<? super Entry<K, V>> predicate;
2815
2816    FilteredMapValues(
2817        Map<K, V> filteredMap, Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
2818      super(filteredMap);
2819      this.unfiltered = unfiltered;
2820      this.predicate = predicate;
2821    }
2822
2823    @Override
2824    public boolean remove(@CheckForNull Object o) {
2825      Iterator<Entry<K, V>> entryItr = unfiltered.entrySet().iterator();
2826      while (entryItr.hasNext()) {
2827        Entry<K, V> entry = entryItr.next();
2828        if (predicate.apply(entry) && Objects.equal(entry.getValue(), o)) {
2829          entryItr.remove();
2830          return true;
2831        }
2832      }
2833      return false;
2834    }
2835
2836    @Override
2837    public boolean removeAll(Collection<?> collection) {
2838      Iterator<Entry<K, V>> entryItr = unfiltered.entrySet().iterator();
2839      boolean result = false;
2840      while (entryItr.hasNext()) {
2841        Entry<K, V> entry = entryItr.next();
2842        if (predicate.apply(entry) && collection.contains(entry.getValue())) {
2843          entryItr.remove();
2844          result = true;
2845        }
2846      }
2847      return result;
2848    }
2849
2850    @Override
2851    public boolean retainAll(Collection<?> collection) {
2852      Iterator<Entry<K, V>> entryItr = unfiltered.entrySet().iterator();
2853      boolean result = false;
2854      while (entryItr.hasNext()) {
2855        Entry<K, V> entry = entryItr.next();
2856        if (predicate.apply(entry) && !collection.contains(entry.getValue())) {
2857          entryItr.remove();
2858          result = true;
2859        }
2860      }
2861      return result;
2862    }
2863
2864    @Override
2865    public @Nullable Object[] toArray() {
2866      // creating an ArrayList so filtering happens once
2867      return Lists.newArrayList(iterator()).toArray();
2868    }
2869
2870    @Override
2871    @SuppressWarnings("nullness") // b/192354773 in our checker affects toArray declarations
2872    public <T extends @Nullable Object> T[] toArray(T[] array) {
2873      return Lists.newArrayList(iterator()).toArray(array);
2874    }
2875  }
2876
2877  private static class FilteredKeyMap<K extends @Nullable Object, V extends @Nullable Object>
2878      extends AbstractFilteredMap<K, V> {
2879    final Predicate<? super K> keyPredicate;
2880
2881    FilteredKeyMap(
2882        Map<K, V> unfiltered,
2883        Predicate<? super K> keyPredicate,
2884        Predicate<? super Entry<K, V>> entryPredicate) {
2885      super(unfiltered, entryPredicate);
2886      this.keyPredicate = keyPredicate;
2887    }
2888
2889    @Override
2890    protected Set<Entry<K, V>> createEntrySet() {
2891      return Sets.filter(unfiltered.entrySet(), predicate);
2892    }
2893
2894    @Override
2895    Set<K> createKeySet() {
2896      return Sets.filter(unfiltered.keySet(), keyPredicate);
2897    }
2898
2899    // The cast is called only when the key is in the unfiltered map, implying
2900    // that key is a K.
2901    @Override
2902    @SuppressWarnings("unchecked")
2903    public boolean containsKey(@CheckForNull Object key) {
2904      return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
2905    }
2906  }
2907
2908  static class FilteredEntryMap<K extends @Nullable Object, V extends @Nullable Object>
2909      extends AbstractFilteredMap<K, V> {
2910    /**
2911     * Entries in this set satisfy the predicate, but they don't validate the input to {@code
2912     * Entry.setValue()}.
2913     */
2914    final Set<Entry<K, V>> filteredEntrySet;
2915
2916    FilteredEntryMap(Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
2917      super(unfiltered, entryPredicate);
2918      filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
2919    }
2920
2921    @Override
2922    protected Set<Entry<K, V>> createEntrySet() {
2923      return new EntrySet();
2924    }
2925
2926    @WeakOuter
2927    private class EntrySet extends ForwardingSet<Entry<K, V>> {
2928      @Override
2929      protected Set<Entry<K, V>> delegate() {
2930        return filteredEntrySet;
2931      }
2932
2933      @Override
2934      public Iterator<Entry<K, V>> iterator() {
2935        return new TransformedIterator<Entry<K, V>, Entry<K, V>>(filteredEntrySet.iterator()) {
2936          @Override
2937          Entry<K, V> transform(final Entry<K, V> entry) {
2938            return new ForwardingMapEntry<K, V>() {
2939              @Override
2940              protected Entry<K, V> delegate() {
2941                return entry;
2942              }
2943
2944              @Override
2945              @ParametricNullness
2946              public V setValue(@ParametricNullness V newValue) {
2947                checkArgument(apply(getKey(), newValue));
2948                return super.setValue(newValue);
2949              }
2950            };
2951          }
2952        };
2953      }
2954    }
2955
2956    @Override
2957    Set<K> createKeySet() {
2958      return new KeySet();
2959    }
2960
2961    static <K extends @Nullable Object, V extends @Nullable Object> boolean removeAllKeys(
2962        Map<K, V> map, Predicate<? super Entry<K, V>> entryPredicate, Collection<?> keyCollection) {
2963      Iterator<Entry<K, V>> entryItr = map.entrySet().iterator();
2964      boolean result = false;
2965      while (entryItr.hasNext()) {
2966        Entry<K, V> entry = entryItr.next();
2967        if (entryPredicate.apply(entry) && keyCollection.contains(entry.getKey())) {
2968          entryItr.remove();
2969          result = true;
2970        }
2971      }
2972      return result;
2973    }
2974
2975    static <K extends @Nullable Object, V extends @Nullable Object> boolean retainAllKeys(
2976        Map<K, V> map, Predicate<? super Entry<K, V>> entryPredicate, Collection<?> keyCollection) {
2977      Iterator<Entry<K, V>> entryItr = map.entrySet().iterator();
2978      boolean result = false;
2979      while (entryItr.hasNext()) {
2980        Entry<K, V> entry = entryItr.next();
2981        if (entryPredicate.apply(entry) && !keyCollection.contains(entry.getKey())) {
2982          entryItr.remove();
2983          result = true;
2984        }
2985      }
2986      return result;
2987    }
2988
2989    @WeakOuter
2990    class KeySet extends Maps.KeySet<K, V> {
2991      KeySet() {
2992        super(FilteredEntryMap.this);
2993      }
2994
2995      @Override
2996      public boolean remove(@CheckForNull Object o) {
2997        if (containsKey(o)) {
2998          unfiltered.remove(o);
2999          return true;
3000        }
3001        return false;
3002      }
3003
3004      @Override
3005      public boolean removeAll(Collection<?> collection) {
3006        return removeAllKeys(unfiltered, predicate, collection);
3007      }
3008
3009      @Override
3010      public boolean retainAll(Collection<?> collection) {
3011        return retainAllKeys(unfiltered, predicate, collection);
3012      }
3013
3014      @Override
3015      public @Nullable Object[] toArray() {
3016        // creating an ArrayList so filtering happens once
3017        return Lists.newArrayList(iterator()).toArray();
3018      }
3019
3020      @Override
3021      @SuppressWarnings("nullness") // b/192354773 in our checker affects toArray declarations
3022      public <T extends @Nullable Object> T[] toArray(T[] array) {
3023        return Lists.newArrayList(iterator()).toArray(array);
3024      }
3025    }
3026  }
3027
3028  private static class FilteredEntrySortedMap<
3029          K extends @Nullable Object, V extends @Nullable Object>
3030      extends FilteredEntryMap<K, V> implements SortedMap<K, V> {
3031
3032    FilteredEntrySortedMap(
3033        SortedMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
3034      super(unfiltered, entryPredicate);
3035    }
3036
3037    SortedMap<K, V> sortedMap() {
3038      return (SortedMap<K, V>) unfiltered;
3039    }
3040
3041    @Override
3042    public SortedSet<K> keySet() {
3043      return (SortedSet<K>) super.keySet();
3044    }
3045
3046    @Override
3047    SortedSet<K> createKeySet() {
3048      return new SortedKeySet();
3049    }
3050
3051    @WeakOuter
3052    class SortedKeySet extends KeySet implements SortedSet<K> {
3053      @Override
3054      @CheckForNull
3055      public Comparator<? super K> comparator() {
3056        return sortedMap().comparator();
3057      }
3058
3059      @Override
3060      public SortedSet<K> subSet(
3061          @ParametricNullness K fromElement, @ParametricNullness K toElement) {
3062        return (SortedSet<K>) subMap(fromElement, toElement).keySet();
3063      }
3064
3065      @Override
3066      public SortedSet<K> headSet(@ParametricNullness K toElement) {
3067        return (SortedSet<K>) headMap(toElement).keySet();
3068      }
3069
3070      @Override
3071      public SortedSet<K> tailSet(@ParametricNullness K fromElement) {
3072        return (SortedSet<K>) tailMap(fromElement).keySet();
3073      }
3074
3075      @Override
3076      @ParametricNullness
3077      public K first() {
3078        return firstKey();
3079      }
3080
3081      @Override
3082      @ParametricNullness
3083      public K last() {
3084        return lastKey();
3085      }
3086    }
3087
3088    @Override
3089    @CheckForNull
3090    public Comparator<? super K> comparator() {
3091      return sortedMap().comparator();
3092    }
3093
3094    @Override
3095    @ParametricNullness
3096    public K firstKey() {
3097      // correctly throws NoSuchElementException when filtered map is empty.
3098      return keySet().iterator().next();
3099    }
3100
3101    @Override
3102    @ParametricNullness
3103    public K lastKey() {
3104      SortedMap<K, V> headMap = sortedMap();
3105      while (true) {
3106        // correctly throws NoSuchElementException when filtered map is empty.
3107        K key = headMap.lastKey();
3108        // The cast is safe because the key is taken from the map.
3109        if (apply(key, uncheckedCastNullableTToT(unfiltered.get(key)))) {
3110          return key;
3111        }
3112        headMap = sortedMap().headMap(key);
3113      }
3114    }
3115
3116    @Override
3117    public SortedMap<K, V> headMap(@ParametricNullness K toKey) {
3118      return new FilteredEntrySortedMap<>(sortedMap().headMap(toKey), predicate);
3119    }
3120
3121    @Override
3122    public SortedMap<K, V> subMap(@ParametricNullness K fromKey, @ParametricNullness K toKey) {
3123      return new FilteredEntrySortedMap<>(sortedMap().subMap(fromKey, toKey), predicate);
3124    }
3125
3126    @Override
3127    public SortedMap<K, V> tailMap(@ParametricNullness K fromKey) {
3128      return new FilteredEntrySortedMap<>(sortedMap().tailMap(fromKey), predicate);
3129    }
3130  }
3131
3132  @GwtIncompatible // NavigableMap
3133  private static class FilteredEntryNavigableMap<
3134          K extends @Nullable Object, V extends @Nullable Object>
3135      extends AbstractNavigableMap<K, V> {
3136    /*
3137     * It's less code to extend AbstractNavigableMap and forward the filtering logic to
3138     * FilteredEntryMap than to extend FilteredEntrySortedMap and reimplement all the NavigableMap
3139     * methods.
3140     */
3141
3142    private final NavigableMap<K, V> unfiltered;
3143    private final Predicate<? super Entry<K, V>> entryPredicate;
3144    private final Map<K, V> filteredDelegate;
3145
3146    FilteredEntryNavigableMap(
3147        NavigableMap<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
3148      this.unfiltered = checkNotNull(unfiltered);
3149      this.entryPredicate = entryPredicate;
3150      this.filteredDelegate = new FilteredEntryMap<>(unfiltered, entryPredicate);
3151    }
3152
3153    @Override
3154    @CheckForNull
3155    public Comparator<? super K> comparator() {
3156      return unfiltered.comparator();
3157    }
3158
3159    @Override
3160    public NavigableSet<K> navigableKeySet() {
3161      return new Maps.NavigableKeySet<K, V>(this) {
3162        @Override
3163        public boolean removeAll(Collection<?> collection) {
3164          return FilteredEntryMap.removeAllKeys(unfiltered, entryPredicate, collection);
3165        }
3166
3167        @Override
3168        public boolean retainAll(Collection<?> collection) {
3169          return FilteredEntryMap.retainAllKeys(unfiltered, entryPredicate, collection);
3170        }
3171      };
3172    }
3173
3174    @Override
3175    public Collection<V> values() {
3176      return new FilteredMapValues<>(this, unfiltered, entryPredicate);
3177    }
3178
3179    @Override
3180    Iterator<Entry<K, V>> entryIterator() {
3181      return Iterators.filter(unfiltered.entrySet().iterator(), entryPredicate);
3182    }
3183
3184    @Override
3185    Iterator<Entry<K, V>> descendingEntryIterator() {
3186      return Iterators.filter(unfiltered.descendingMap().entrySet().iterator(), entryPredicate);
3187    }
3188
3189    @Override
3190    public int size() {
3191      return filteredDelegate.size();
3192    }
3193
3194    @Override
3195    public boolean isEmpty() {
3196      return !Iterables.any(unfiltered.entrySet(), entryPredicate);
3197    }
3198
3199    @Override
3200    @CheckForNull
3201    public V get(@CheckForNull Object key) {
3202      return filteredDelegate.get(key);
3203    }
3204
3205    @Override
3206    public boolean containsKey(@CheckForNull Object key) {
3207      return filteredDelegate.containsKey(key);
3208    }
3209
3210    @Override
3211    @CheckForNull
3212    public V put(@ParametricNullness K key, @ParametricNullness V value) {
3213      return filteredDelegate.put(key, value);
3214    }
3215
3216    @Override
3217    @CheckForNull
3218    public V remove(@CheckForNull Object key) {
3219      return filteredDelegate.remove(key);
3220    }
3221
3222    @Override
3223    public void putAll(Map<? extends K, ? extends V> m) {
3224      filteredDelegate.putAll(m);
3225    }
3226
3227    @Override
3228    public void clear() {
3229      filteredDelegate.clear();
3230    }
3231
3232    @Override
3233    public Set<Entry<K, V>> entrySet() {
3234      return filteredDelegate.entrySet();
3235    }
3236
3237    @Override
3238    @CheckForNull
3239    public Entry<K, V> pollFirstEntry() {
3240      return Iterables.removeFirstMatching(unfiltered.entrySet(), entryPredicate);
3241    }
3242
3243    @Override
3244    @CheckForNull
3245    public Entry<K, V> pollLastEntry() {
3246      return Iterables.removeFirstMatching(unfiltered.descendingMap().entrySet(), entryPredicate);
3247    }
3248
3249    @Override
3250    public NavigableMap<K, V> descendingMap() {
3251      return filterEntries(unfiltered.descendingMap(), entryPredicate);
3252    }
3253
3254    @Override
3255    public NavigableMap<K, V> subMap(
3256        @ParametricNullness K fromKey,
3257        boolean fromInclusive,
3258        @ParametricNullness K toKey,
3259        boolean toInclusive) {
3260      return filterEntries(
3261          unfiltered.subMap(fromKey, fromInclusive, toKey, toInclusive), entryPredicate);
3262    }
3263
3264    @Override
3265    public NavigableMap<K, V> headMap(@ParametricNullness K toKey, boolean inclusive) {
3266      return filterEntries(unfiltered.headMap(toKey, inclusive), entryPredicate);
3267    }
3268
3269    @Override
3270    public NavigableMap<K, V> tailMap(@ParametricNullness K fromKey, boolean inclusive) {
3271      return filterEntries(unfiltered.tailMap(fromKey, inclusive), entryPredicate);
3272    }
3273  }
3274
3275  static final class FilteredEntryBiMap<K extends @Nullable Object, V extends @Nullable Object>
3276      extends FilteredEntryMap<K, V> implements BiMap<K, V> {
3277    @RetainedWith private final BiMap<V, K> inverse;
3278
3279    private static <K extends @Nullable Object, V extends @Nullable Object>
3280        Predicate<Entry<V, K>> inversePredicate(
3281            final Predicate<? super Entry<K, V>> forwardPredicate) {
3282      return new Predicate<Entry<V, K>>() {
3283        @Override
3284        public boolean apply(Entry<V, K> input) {
3285          return forwardPredicate.apply(Maps.immutableEntry(input.getValue(), input.getKey()));
3286        }
3287      };
3288    }
3289
3290    FilteredEntryBiMap(BiMap<K, V> delegate, Predicate<? super Entry<K, V>> predicate) {
3291      super(delegate, predicate);
3292      this.inverse =
3293          new FilteredEntryBiMap<>(delegate.inverse(), inversePredicate(predicate), this);
3294    }
3295
3296    private FilteredEntryBiMap(
3297        BiMap<K, V> delegate, Predicate<? super Entry<K, V>> predicate, BiMap<V, K> inverse) {
3298      super(delegate, predicate);
3299      this.inverse = inverse;
3300    }
3301
3302    BiMap<K, V> unfiltered() {
3303      return (BiMap<K, V>) unfiltered;
3304    }
3305
3306    @Override
3307    @CheckForNull
3308    public V forcePut(@ParametricNullness K key, @ParametricNullness V value) {
3309      checkArgument(apply(key, value));
3310      return unfiltered().forcePut(key, value);
3311    }
3312
3313    @Override
3314    public BiMap<V, K> inverse() {
3315      return inverse;
3316    }
3317
3318    @Override
3319    public Set<V> values() {
3320      return inverse.keySet();
3321    }
3322  }
3323
3324  /**
3325   * Returns an unmodifiable view of the specified navigable map. Query operations on the returned
3326   * map read through to the specified map, and attempts to modify the returned map, whether direct
3327   * or via its views, result in an {@code UnsupportedOperationException}.
3328   *
3329   * <p>The returned navigable map will be serializable if the specified navigable map is
3330   * serializable.
3331   *
3332   * <p>This method's signature will not permit you to convert a {@code NavigableMap<? extends K,
3333   * V>} to a {@code NavigableMap<K, V>}. If it permitted this, the returned map's {@code
3334   * comparator()} method might return a {@code Comparator<? extends K>}, which works only on a
3335   * particular subtype of {@code K}, but promise that it's a {@code Comparator<? super K>}, which
3336   * must work on any type of {@code K}.
3337   *
3338   * @param map the navigable map for which an unmodifiable view is to be returned
3339   * @return an unmodifiable view of the specified navigable map
3340   * @since 12.0
3341   */
3342  @GwtIncompatible // NavigableMap
3343  public static <K extends @Nullable Object, V extends @Nullable Object>
3344      NavigableMap<K, V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> map) {
3345    checkNotNull(map);
3346    if (map instanceof UnmodifiableNavigableMap) {
3347      @SuppressWarnings("unchecked") // covariant
3348      NavigableMap<K, V> result = (NavigableMap<K, V>) map;
3349      return result;
3350    } else {
3351      return new UnmodifiableNavigableMap<>(map);
3352    }
3353  }
3354
3355  @CheckForNull
3356  private static <K extends @Nullable Object, V extends @Nullable Object>
3357      Entry<K, V> unmodifiableOrNull(@CheckForNull Entry<K, ? extends V> entry) {
3358    return (entry == null) ? null : Maps.unmodifiableEntry(entry);
3359  }
3360
3361  @GwtIncompatible // NavigableMap
3362  static class UnmodifiableNavigableMap<K extends @Nullable Object, V extends @Nullable Object>
3363      extends ForwardingSortedMap<K, V> implements NavigableMap<K, V>, Serializable {
3364    private final NavigableMap<K, ? extends V> delegate;
3365
3366    UnmodifiableNavigableMap(NavigableMap<K, ? extends V> delegate) {
3367      this.delegate = delegate;
3368    }
3369
3370    UnmodifiableNavigableMap(
3371        NavigableMap<K, ? extends V> delegate, UnmodifiableNavigableMap<K, V> descendingMap) {
3372      this.delegate = delegate;
3373      this.descendingMap = descendingMap;
3374    }
3375
3376    @Override
3377    protected SortedMap<K, V> delegate() {
3378      return Collections.unmodifiableSortedMap(delegate);
3379    }
3380
3381    @Override
3382    @CheckForNull
3383    public Entry<K, V> lowerEntry(@ParametricNullness K key) {
3384      return unmodifiableOrNull(delegate.lowerEntry(key));
3385    }
3386
3387    @Override
3388    @CheckForNull
3389    public K lowerKey(@ParametricNullness K key) {
3390      return delegate.lowerKey(key);
3391    }
3392
3393    @Override
3394    @CheckForNull
3395    public Entry<K, V> floorEntry(@ParametricNullness K key) {
3396      return unmodifiableOrNull(delegate.floorEntry(key));
3397    }
3398
3399    @Override
3400    @CheckForNull
3401    public K floorKey(@ParametricNullness K key) {
3402      return delegate.floorKey(key);
3403    }
3404
3405    @Override
3406    @CheckForNull
3407    public Entry<K, V> ceilingEntry(@ParametricNullness K key) {
3408      return unmodifiableOrNull(delegate.ceilingEntry(key));
3409    }
3410
3411    @Override
3412    @CheckForNull
3413    public K ceilingKey(@ParametricNullness K key) {
3414      return delegate.ceilingKey(key);
3415    }
3416
3417    @Override
3418    @CheckForNull
3419    public Entry<K, V> higherEntry(@ParametricNullness K key) {
3420      return unmodifiableOrNull(delegate.higherEntry(key));
3421    }
3422
3423    @Override
3424    @CheckForNull
3425    public K higherKey(@ParametricNullness K key) {
3426      return delegate.higherKey(key);
3427    }
3428
3429    @Override
3430    @CheckForNull
3431    public Entry<K, V> firstEntry() {
3432      return unmodifiableOrNull(delegate.firstEntry());
3433    }
3434
3435    @Override
3436    @CheckForNull
3437    public Entry<K, V> lastEntry() {
3438      return unmodifiableOrNull(delegate.lastEntry());
3439    }
3440
3441    @Override
3442    @CheckForNull
3443    public final Entry<K, V> pollFirstEntry() {
3444      throw new UnsupportedOperationException();
3445    }
3446
3447    @Override
3448    @CheckForNull
3449    public final Entry<K, V> pollLastEntry() {
3450      throw new UnsupportedOperationException();
3451    }
3452
3453    @CheckForNull private transient UnmodifiableNavigableMap<K, V> descendingMap;
3454
3455    @Override
3456    public NavigableMap<K, V> descendingMap() {
3457      UnmodifiableNavigableMap<K, V> result = descendingMap;
3458      return (result == null)
3459          ? descendingMap = new UnmodifiableNavigableMap<>(delegate.descendingMap(), this)
3460          : result;
3461    }
3462
3463    @Override
3464    public Set<K> keySet() {
3465      return navigableKeySet();
3466    }
3467
3468    @Override
3469    public NavigableSet<K> navigableKeySet() {
3470      return Sets.unmodifiableNavigableSet(delegate.navigableKeySet());
3471    }
3472
3473    @Override
3474    public NavigableSet<K> descendingKeySet() {
3475      return Sets.unmodifiableNavigableSet(delegate.descendingKeySet());
3476    }
3477
3478    @Override
3479    public SortedMap<K, V> subMap(@ParametricNullness K fromKey, @ParametricNullness K toKey) {
3480      return subMap(fromKey, true, toKey, false);
3481    }
3482
3483    @Override
3484    public NavigableMap<K, V> subMap(
3485        @ParametricNullness K fromKey,
3486        boolean fromInclusive,
3487        @ParametricNullness K toKey,
3488        boolean toInclusive) {
3489      return Maps.unmodifiableNavigableMap(
3490          delegate.subMap(fromKey, fromInclusive, toKey, toInclusive));
3491    }
3492
3493    @Override
3494    public SortedMap<K, V> headMap(@ParametricNullness K toKey) {
3495      return headMap(toKey, false);
3496    }
3497
3498    @Override
3499    public NavigableMap<K, V> headMap(@ParametricNullness K toKey, boolean inclusive) {
3500      return Maps.unmodifiableNavigableMap(delegate.headMap(toKey, inclusive));
3501    }
3502
3503    @Override
3504    public SortedMap<K, V> tailMap(@ParametricNullness K fromKey) {
3505      return tailMap(fromKey, true);
3506    }
3507
3508    @Override
3509    public NavigableMap<K, V> tailMap(@ParametricNullness K fromKey, boolean inclusive) {
3510      return Maps.unmodifiableNavigableMap(delegate.tailMap(fromKey, inclusive));
3511    }
3512  }
3513
3514  /**
3515   * Returns a synchronized (thread-safe) navigable map backed by the specified navigable map. In
3516   * order to guarantee serial access, it is critical that <b>all</b> access to the backing
3517   * navigable map is accomplished through the returned navigable map (or its views).
3518   *
3519   * <p>It is imperative that the user manually synchronize on the returned navigable map when
3520   * iterating over any of its collection views, or the collections views of any of its {@code
3521   * descendingMap}, {@code subMap}, {@code headMap} or {@code tailMap} views.
3522   *
3523   * <pre>{@code
3524   * NavigableMap<K, V> map = synchronizedNavigableMap(new TreeMap<K, V>());
3525   *
3526   * // Needn't be in synchronized block
3527   * NavigableSet<K> set = map.navigableKeySet();
3528   *
3529   * synchronized (map) { // Synchronizing on map, not set!
3530   *   Iterator<K> it = set.iterator(); // Must be in synchronized block
3531   *   while (it.hasNext()) {
3532   *     foo(it.next());
3533   *   }
3534   * }
3535   * }</pre>
3536   *
3537   * <p>or:
3538   *
3539   * <pre>{@code
3540   * NavigableMap<K, V> map = synchronizedNavigableMap(new TreeMap<K, V>());
3541   * NavigableMap<K, V> map2 = map.subMap(foo, false, bar, true);
3542   *
3543   * // Needn't be in synchronized block
3544   * NavigableSet<K> set2 = map2.descendingKeySet();
3545   *
3546   * synchronized (map) { // Synchronizing on map, not map2 or set2!
3547   *   Iterator<K> it = set2.iterator(); // Must be in synchronized block
3548   *   while (it.hasNext()) {
3549   *     foo(it.next());
3550   *   }
3551   * }
3552   * }</pre>
3553   *
3554   * <p>Failure to follow this advice may result in non-deterministic behavior.
3555   *
3556   * <p>The returned navigable map will be serializable if the specified navigable map is
3557   * serializable.
3558   *
3559   * @param navigableMap the navigable map to be "wrapped" in a synchronized navigable map.
3560   * @return a synchronized view of the specified navigable map.
3561   * @since 13.0
3562   */
3563  @GwtIncompatible // NavigableMap
3564  public static <K extends @Nullable Object, V extends @Nullable Object>
3565      NavigableMap<K, V> synchronizedNavigableMap(NavigableMap<K, V> navigableMap) {
3566    return Synchronized.navigableMap(navigableMap);
3567  }
3568
3569  /**
3570   * {@code AbstractMap} extension that makes it easy to cache customized keySet, values, and
3571   * entrySet views.
3572   */
3573  @GwtCompatible
3574  abstract static class ViewCachingAbstractMap<
3575          K extends @Nullable Object, V extends @Nullable Object>
3576      extends AbstractMap<K, V> {
3577    /**
3578     * Creates the entry set to be returned by {@link #entrySet()}. This method is invoked at most
3579     * once on a given map, at the time when {@code entrySet} is first called.
3580     */
3581    abstract Set<Entry<K, V>> createEntrySet();
3582
3583    @CheckForNull private transient Set<Entry<K, V>> entrySet;
3584
3585    @Override
3586    public Set<Entry<K, V>> entrySet() {
3587      Set<Entry<K, V>> result = entrySet;
3588      return (result == null) ? entrySet = createEntrySet() : result;
3589    }
3590
3591    @CheckForNull private transient Set<K> keySet;
3592
3593    @Override
3594    public Set<K> keySet() {
3595      Set<K> result = keySet;
3596      return (result == null) ? keySet = createKeySet() : result;
3597    }
3598
3599    Set<K> createKeySet() {
3600      return new KeySet<>(this);
3601    }
3602
3603    @CheckForNull private transient Collection<V> values;
3604
3605    @Override
3606    public Collection<V> values() {
3607      Collection<V> result = values;
3608      return (result == null) ? values = createValues() : result;
3609    }
3610
3611    Collection<V> createValues() {
3612      return new Values<>(this);
3613    }
3614  }
3615
3616  abstract static class IteratorBasedAbstractMap<
3617          K extends @Nullable Object, V extends @Nullable Object>
3618      extends AbstractMap<K, V> {
3619    @Override
3620    public abstract int size();
3621
3622    abstract Iterator<Entry<K, V>> entryIterator();
3623
3624    @Override
3625    public Set<Entry<K, V>> entrySet() {
3626      return new EntrySet<K, V>() {
3627        @Override
3628        Map<K, V> map() {
3629          return IteratorBasedAbstractMap.this;
3630        }
3631
3632        @Override
3633        public Iterator<Entry<K, V>> iterator() {
3634          return entryIterator();
3635        }
3636      };
3637    }
3638
3639    @Override
3640    public void clear() {
3641      Iterators.clear(entryIterator());
3642    }
3643  }
3644
3645  /**
3646   * Delegates to {@link Map#get}. Returns {@code null} on {@code ClassCastException} and {@code
3647   * NullPointerException}.
3648   */
3649  @CheckForNull
3650  static <V extends @Nullable Object> V safeGet(Map<?, V> map, @CheckForNull Object key) {
3651    checkNotNull(map);
3652    try {
3653      return map.get(key);
3654    } catch (ClassCastException | NullPointerException e) {
3655      return null;
3656    }
3657  }
3658
3659  /**
3660   * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code ClassCastException} and
3661   * {@code NullPointerException}.
3662   */
3663  static boolean safeContainsKey(Map<?, ?> map, @CheckForNull Object key) {
3664    checkNotNull(map);
3665    try {
3666      return map.containsKey(key);
3667    } catch (ClassCastException | NullPointerException e) {
3668      return false;
3669    }
3670  }
3671
3672  /**
3673   * Delegates to {@link Map#remove}. Returns {@code null} on {@code ClassCastException} and {@code
3674   * NullPointerException}.
3675   */
3676  @CheckForNull
3677  static <V extends @Nullable Object> V safeRemove(Map<?, V> map, @CheckForNull Object key) {
3678    checkNotNull(map);
3679    try {
3680      return map.remove(key);
3681    } catch (ClassCastException | NullPointerException e) {
3682      return null;
3683    }
3684  }
3685
3686  /** An admittedly inefficient implementation of {@link Map#containsKey}. */
3687  static boolean containsKeyImpl(Map<?, ?> map, @CheckForNull Object key) {
3688    return Iterators.contains(keyIterator(map.entrySet().iterator()), key);
3689  }
3690
3691  /** An implementation of {@link Map#containsValue}. */
3692  static boolean containsValueImpl(Map<?, ?> map, @CheckForNull Object value) {
3693    return Iterators.contains(valueIterator(map.entrySet().iterator()), value);
3694  }
3695
3696  /**
3697   * Implements {@code Collection.contains} safely for forwarding collections of map entries. If
3698   * {@code o} is an instance of {@code Entry}, it is wrapped using {@link #unmodifiableEntry} to
3699   * protect against a possible nefarious equals method.
3700   *
3701   * <p>Note that {@code c} is the backing (delegate) collection, rather than the forwarding
3702   * collection.
3703   *
3704   * @param c the delegate (unwrapped) collection of map entries
3705   * @param o the object that might be contained in {@code c}
3706   * @return {@code true} if {@code c} contains {@code o}
3707   */
3708  static <K extends @Nullable Object, V extends @Nullable Object> boolean containsEntryImpl(
3709      Collection<Entry<K, V>> c, @CheckForNull Object o) {
3710    if (!(o instanceof Entry)) {
3711      return false;
3712    }
3713    return c.contains(unmodifiableEntry((Entry<?, ?>) o));
3714  }
3715
3716  /**
3717   * Implements {@code Collection.remove} safely for forwarding collections of map entries. If
3718   * {@code o} is an instance of {@code Entry}, it is wrapped using {@link #unmodifiableEntry} to
3719   * protect against a possible nefarious equals method.
3720   *
3721   * <p>Note that {@code c} is backing (delegate) collection, rather than the forwarding collection.
3722   *
3723   * @param c the delegate (unwrapped) collection of map entries
3724   * @param o the object to remove from {@code c}
3725   * @return {@code true} if {@code c} was changed
3726   */
3727  static <K extends @Nullable Object, V extends @Nullable Object> boolean removeEntryImpl(
3728      Collection<Entry<K, V>> c, @CheckForNull Object o) {
3729    if (!(o instanceof Entry)) {
3730      return false;
3731    }
3732    return c.remove(unmodifiableEntry((Entry<?, ?>) o));
3733  }
3734
3735  /** An implementation of {@link Map#equals}. */
3736  static boolean equalsImpl(Map<?, ?> map, @CheckForNull Object object) {
3737    if (map == object) {
3738      return true;
3739    } else if (object instanceof Map) {
3740      Map<?, ?> o = (Map<?, ?>) object;
3741      return map.entrySet().equals(o.entrySet());
3742    }
3743    return false;
3744  }
3745
3746  /** An implementation of {@link Map#toString}. */
3747  static String toStringImpl(Map<?, ?> map) {
3748    StringBuilder sb = Collections2.newStringBuilderForCollection(map.size()).append('{');
3749    boolean first = true;
3750    for (Entry<?, ?> entry : map.entrySet()) {
3751      if (!first) {
3752        sb.append(", ");
3753      }
3754      first = false;
3755      sb.append(entry.getKey()).append('=').append(entry.getValue());
3756    }
3757    return sb.append('}').toString();
3758  }
3759
3760  /** An implementation of {@link Map#putAll}. */
3761  static <K extends @Nullable Object, V extends @Nullable Object> void putAllImpl(
3762      Map<K, V> self, Map<? extends K, ? extends V> map) {
3763    for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
3764      self.put(entry.getKey(), entry.getValue());
3765    }
3766  }
3767
3768  static class KeySet<K extends @Nullable Object, V extends @Nullable Object>
3769      extends Sets.ImprovedAbstractSet<K> {
3770    @Weak final Map<K, V> map;
3771
3772    KeySet(Map<K, V> map) {
3773      this.map = checkNotNull(map);
3774    }
3775
3776    Map<K, V> map() {
3777      return map;
3778    }
3779
3780    @Override
3781    public Iterator<K> iterator() {
3782      return keyIterator(map().entrySet().iterator());
3783    }
3784
3785    @Override
3786    public int size() {
3787      return map().size();
3788    }
3789
3790    @Override
3791    public boolean isEmpty() {
3792      return map().isEmpty();
3793    }
3794
3795    @Override
3796    public boolean contains(@CheckForNull Object o) {
3797      return map().containsKey(o);
3798    }
3799
3800    @Override
3801    public boolean remove(@CheckForNull Object o) {
3802      if (contains(o)) {
3803        map().remove(o);
3804        return true;
3805      }
3806      return false;
3807    }
3808
3809    @Override
3810    public void clear() {
3811      map().clear();
3812    }
3813  }
3814
3815  @CheckForNull
3816  static <K extends @Nullable Object> K keyOrNull(@CheckForNull Entry<K, ?> entry) {
3817    return (entry == null) ? null : entry.getKey();
3818  }
3819
3820  @CheckForNull
3821  static <V extends @Nullable Object> V valueOrNull(@CheckForNull Entry<?, V> entry) {
3822    return (entry == null) ? null : entry.getValue();
3823  }
3824
3825  static class SortedKeySet<K extends @Nullable Object, V extends @Nullable Object>
3826      extends KeySet<K, V> implements SortedSet<K> {
3827    SortedKeySet(SortedMap<K, V> map) {
3828      super(map);
3829    }
3830
3831    @Override
3832    SortedMap<K, V> map() {
3833      return (SortedMap<K, V>) super.map();
3834    }
3835
3836    @Override
3837    @CheckForNull
3838    public Comparator<? super K> comparator() {
3839      return map().comparator();
3840    }
3841
3842    @Override
3843    public SortedSet<K> subSet(@ParametricNullness K fromElement, @ParametricNullness K toElement) {
3844      return new SortedKeySet<>(map().subMap(fromElement, toElement));
3845    }
3846
3847    @Override
3848    public SortedSet<K> headSet(@ParametricNullness K toElement) {
3849      return new SortedKeySet<>(map().headMap(toElement));
3850    }
3851
3852    @Override
3853    public SortedSet<K> tailSet(@ParametricNullness K fromElement) {
3854      return new SortedKeySet<>(map().tailMap(fromElement));
3855    }
3856
3857    @Override
3858    @ParametricNullness
3859    public K first() {
3860      return map().firstKey();
3861    }
3862
3863    @Override
3864    @ParametricNullness
3865    public K last() {
3866      return map().lastKey();
3867    }
3868  }
3869
3870  @GwtIncompatible // NavigableMap
3871  static class NavigableKeySet<K extends @Nullable Object, V extends @Nullable Object>
3872      extends SortedKeySet<K, V> implements NavigableSet<K> {
3873    NavigableKeySet(NavigableMap<K, V> map) {
3874      super(map);
3875    }
3876
3877    @Override
3878    NavigableMap<K, V> map() {
3879      return (NavigableMap<K, V>) map;
3880    }
3881
3882    @Override
3883    @CheckForNull
3884    public K lower(@ParametricNullness K e) {
3885      return map().lowerKey(e);
3886    }
3887
3888    @Override
3889    @CheckForNull
3890    public K floor(@ParametricNullness K e) {
3891      return map().floorKey(e);
3892    }
3893
3894    @Override
3895    @CheckForNull
3896    public K ceiling(@ParametricNullness K e) {
3897      return map().ceilingKey(e);
3898    }
3899
3900    @Override
3901    @CheckForNull
3902    public K higher(@ParametricNullness K e) {
3903      return map().higherKey(e);
3904    }
3905
3906    @Override
3907    @CheckForNull
3908    public K pollFirst() {
3909      return keyOrNull(map().pollFirstEntry());
3910    }
3911
3912    @Override
3913    @CheckForNull
3914    public K pollLast() {
3915      return keyOrNull(map().pollLastEntry());
3916    }
3917
3918    @Override
3919    public NavigableSet<K> descendingSet() {
3920      return map().descendingKeySet();
3921    }
3922
3923    @Override
3924    public Iterator<K> descendingIterator() {
3925      return descendingSet().iterator();
3926    }
3927
3928    @Override
3929    public NavigableSet<K> subSet(
3930        @ParametricNullness K fromElement,
3931        boolean fromInclusive,
3932        @ParametricNullness K toElement,
3933        boolean toInclusive) {
3934      return map().subMap(fromElement, fromInclusive, toElement, toInclusive).navigableKeySet();
3935    }
3936
3937    @Override
3938    public SortedSet<K> subSet(@ParametricNullness K fromElement, @ParametricNullness K toElement) {
3939      return subSet(fromElement, true, toElement, false);
3940    }
3941
3942    @Override
3943    public NavigableSet<K> headSet(@ParametricNullness K toElement, boolean inclusive) {
3944      return map().headMap(toElement, inclusive).navigableKeySet();
3945    }
3946
3947    @Override
3948    public SortedSet<K> headSet(@ParametricNullness K toElement) {
3949      return headSet(toElement, false);
3950    }
3951
3952    @Override
3953    public NavigableSet<K> tailSet(@ParametricNullness K fromElement, boolean inclusive) {
3954      return map().tailMap(fromElement, inclusive).navigableKeySet();
3955    }
3956
3957    @Override
3958    public SortedSet<K> tailSet(@ParametricNullness K fromElement) {
3959      return tailSet(fromElement, true);
3960    }
3961  }
3962
3963  static class Values<K extends @Nullable Object, V extends @Nullable Object>
3964      extends AbstractCollection<V> {
3965    @Weak final Map<K, V> map;
3966
3967    Values(Map<K, V> map) {
3968      this.map = checkNotNull(map);
3969    }
3970
3971    final Map<K, V> map() {
3972      return map;
3973    }
3974
3975    @Override
3976    public Iterator<V> iterator() {
3977      return valueIterator(map().entrySet().iterator());
3978    }
3979
3980    @Override
3981    public boolean remove(@CheckForNull Object o) {
3982      try {
3983        return super.remove(o);
3984      } catch (UnsupportedOperationException e) {
3985        for (Entry<K, V> entry : map().entrySet()) {
3986          if (Objects.equal(o, entry.getValue())) {
3987            map().remove(entry.getKey());
3988            return true;
3989          }
3990        }
3991        return false;
3992      }
3993    }
3994
3995    @Override
3996    public boolean removeAll(Collection<?> c) {
3997      try {
3998        return super.removeAll(checkNotNull(c));
3999      } catch (UnsupportedOperationException e) {
4000        Set<K> toRemove = Sets.newHashSet();
4001        for (Entry<K, V> entry : map().entrySet()) {
4002          if (c.contains(entry.getValue())) {
4003            toRemove.add(entry.getKey());
4004          }
4005        }
4006        return map().keySet().removeAll(toRemove);
4007      }
4008    }
4009
4010    @Override
4011    public boolean retainAll(Collection<?> c) {
4012      try {
4013        return super.retainAll(checkNotNull(c));
4014      } catch (UnsupportedOperationException e) {
4015        Set<K> toRetain = Sets.newHashSet();
4016        for (Entry<K, V> entry : map().entrySet()) {
4017          if (c.contains(entry.getValue())) {
4018            toRetain.add(entry.getKey());
4019          }
4020        }
4021        return map().keySet().retainAll(toRetain);
4022      }
4023    }
4024
4025    @Override
4026    public int size() {
4027      return map().size();
4028    }
4029
4030    @Override
4031    public boolean isEmpty() {
4032      return map().isEmpty();
4033    }
4034
4035    @Override
4036    public boolean contains(@CheckForNull Object o) {
4037      return map().containsValue(o);
4038    }
4039
4040    @Override
4041    public void clear() {
4042      map().clear();
4043    }
4044  }
4045
4046  abstract static class EntrySet<K extends @Nullable Object, V extends @Nullable Object>
4047      extends Sets.ImprovedAbstractSet<Entry<K, V>> {
4048    abstract Map<K, V> map();
4049
4050    @Override
4051    public int size() {
4052      return map().size();
4053    }
4054
4055    @Override
4056    public void clear() {
4057      map().clear();
4058    }
4059
4060    @Override
4061    public boolean contains(@CheckForNull Object o) {
4062      if (o instanceof Entry) {
4063        Entry<?, ?> entry = (Entry<?, ?>) o;
4064        Object key = entry.getKey();
4065        V value = Maps.safeGet(map(), key);
4066        return Objects.equal(value, entry.getValue()) && (value != null || map().containsKey(key));
4067      }
4068      return false;
4069    }
4070
4071    @Override
4072    public boolean isEmpty() {
4073      return map().isEmpty();
4074    }
4075
4076    @Override
4077    public boolean remove(@CheckForNull Object o) {
4078      /*
4079       * `o instanceof Entry` is guaranteed by `contains`, but we check it here to satisfy our
4080       * nullness checker.
4081       */
4082      if (contains(o) && o instanceof Entry) {
4083        Entry<?, ?> entry = (Entry<?, ?>) o;
4084        return map().keySet().remove(entry.getKey());
4085      }
4086      return false;
4087    }
4088
4089    @Override
4090    public boolean removeAll(Collection<?> c) {
4091      try {
4092        return super.removeAll(checkNotNull(c));
4093      } catch (UnsupportedOperationException e) {
4094        // if the iterators don't support remove
4095        return Sets.removeAllImpl(this, c.iterator());
4096      }
4097    }
4098
4099    @Override
4100    public boolean retainAll(Collection<?> c) {
4101      try {
4102        return super.retainAll(checkNotNull(c));
4103      } catch (UnsupportedOperationException e) {
4104        // if the iterators don't support remove
4105        Set<@Nullable Object> keys = Sets.newHashSetWithExpectedSize(c.size());
4106        for (Object o : c) {
4107          /*
4108           * `o instanceof Entry` is guaranteed by `contains`, but we check it here to satisfy our
4109           * nullness checker.
4110           */
4111          if (contains(o) && o instanceof Entry) {
4112            Entry<?, ?> entry = (Entry<?, ?>) o;
4113            keys.add(entry.getKey());
4114          }
4115        }
4116        return map().keySet().retainAll(keys);
4117      }
4118    }
4119  }
4120
4121  @GwtIncompatible // NavigableMap
4122  abstract static class DescendingMap<K extends @Nullable Object, V extends @Nullable Object>
4123      extends ForwardingMap<K, V> implements NavigableMap<K, V> {
4124
4125    abstract NavigableMap<K, V> forward();
4126
4127    @Override
4128    protected final Map<K, V> delegate() {
4129      return forward();
4130    }
4131
4132    @CheckForNull private transient Comparator<? super K> comparator;
4133
4134    @SuppressWarnings("unchecked")
4135    @Override
4136    public Comparator<? super K> comparator() {
4137      Comparator<? super K> result = comparator;
4138      if (result == null) {
4139        Comparator<? super K> forwardCmp = forward().comparator();
4140        if (forwardCmp == null) {
4141          forwardCmp = (Comparator) Ordering.natural();
4142        }
4143        result = comparator = reverse(forwardCmp);
4144      }
4145      return result;
4146    }
4147
4148    // If we inline this, we get a javac error.
4149    private static <T extends @Nullable Object> Ordering<T> reverse(Comparator<T> forward) {
4150      return Ordering.from(forward).reverse();
4151    }
4152
4153    @Override
4154    @ParametricNullness
4155    public K firstKey() {
4156      return forward().lastKey();
4157    }
4158
4159    @Override
4160    @ParametricNullness
4161    public K lastKey() {
4162      return forward().firstKey();
4163    }
4164
4165    @Override
4166    @CheckForNull
4167    public Entry<K, V> lowerEntry(@ParametricNullness K key) {
4168      return forward().higherEntry(key);
4169    }
4170
4171    @Override
4172    @CheckForNull
4173    public K lowerKey(@ParametricNullness K key) {
4174      return forward().higherKey(key);
4175    }
4176
4177    @Override
4178    @CheckForNull
4179    public Entry<K, V> floorEntry(@ParametricNullness K key) {
4180      return forward().ceilingEntry(key);
4181    }
4182
4183    @Override
4184    @CheckForNull
4185    public K floorKey(@ParametricNullness K key) {
4186      return forward().ceilingKey(key);
4187    }
4188
4189    @Override
4190    @CheckForNull
4191    public Entry<K, V> ceilingEntry(@ParametricNullness K key) {
4192      return forward().floorEntry(key);
4193    }
4194
4195    @Override
4196    @CheckForNull
4197    public K ceilingKey(@ParametricNullness K key) {
4198      return forward().floorKey(key);
4199    }
4200
4201    @Override
4202    @CheckForNull
4203    public Entry<K, V> higherEntry(@ParametricNullness K key) {
4204      return forward().lowerEntry(key);
4205    }
4206
4207    @Override
4208    @CheckForNull
4209    public K higherKey(@ParametricNullness K key) {
4210      return forward().lowerKey(key);
4211    }
4212
4213    @Override
4214    @CheckForNull
4215    public Entry<K, V> firstEntry() {
4216      return forward().lastEntry();
4217    }
4218
4219    @Override
4220    @CheckForNull
4221    public Entry<K, V> lastEntry() {
4222      return forward().firstEntry();
4223    }
4224
4225    @Override
4226    @CheckForNull
4227    public Entry<K, V> pollFirstEntry() {
4228      return forward().pollLastEntry();
4229    }
4230
4231    @Override
4232    @CheckForNull
4233    public Entry<K, V> pollLastEntry() {
4234      return forward().pollFirstEntry();
4235    }
4236
4237    @Override
4238    public NavigableMap<K, V> descendingMap() {
4239      return forward();
4240    }
4241
4242    @CheckForNull private transient Set<Entry<K, V>> entrySet;
4243
4244    @Override
4245    public Set<Entry<K, V>> entrySet() {
4246      Set<Entry<K, V>> result = entrySet;
4247      return (result == null) ? entrySet = createEntrySet() : result;
4248    }
4249
4250    abstract Iterator<Entry<K, V>> entryIterator();
4251
4252    Set<Entry<K, V>> createEntrySet() {
4253      @WeakOuter
4254      class EntrySetImpl extends EntrySet<K, V> {
4255        @Override
4256        Map<K, V> map() {
4257          return DescendingMap.this;
4258        }
4259
4260        @Override
4261        public Iterator<Entry<K, V>> iterator() {
4262          return entryIterator();
4263        }
4264      }
4265      return new EntrySetImpl();
4266    }
4267
4268    @Override
4269    public Set<K> keySet() {
4270      return navigableKeySet();
4271    }
4272
4273    @CheckForNull private transient NavigableSet<K> navigableKeySet;
4274
4275    @Override
4276    public NavigableSet<K> navigableKeySet() {
4277      NavigableSet<K> result = navigableKeySet;
4278      return (result == null) ? navigableKeySet = new NavigableKeySet<>(this) : result;
4279    }
4280
4281    @Override
4282    public NavigableSet<K> descendingKeySet() {
4283      return forward().navigableKeySet();
4284    }
4285
4286    @Override
4287    public NavigableMap<K, V> subMap(
4288        @ParametricNullness K fromKey,
4289        boolean fromInclusive,
4290        @ParametricNullness K toKey,
4291        boolean toInclusive) {
4292      return forward().subMap(toKey, toInclusive, fromKey, fromInclusive).descendingMap();
4293    }
4294
4295    @Override
4296    public SortedMap<K, V> subMap(@ParametricNullness K fromKey, @ParametricNullness K toKey) {
4297      return subMap(fromKey, true, toKey, false);
4298    }
4299
4300    @Override
4301    public NavigableMap<K, V> headMap(@ParametricNullness K toKey, boolean inclusive) {
4302      return forward().tailMap(toKey, inclusive).descendingMap();
4303    }
4304
4305    @Override
4306    public SortedMap<K, V> headMap(@ParametricNullness K toKey) {
4307      return headMap(toKey, false);
4308    }
4309
4310    @Override
4311    public NavigableMap<K, V> tailMap(@ParametricNullness K fromKey, boolean inclusive) {
4312      return forward().headMap(fromKey, inclusive).descendingMap();
4313    }
4314
4315    @Override
4316    public SortedMap<K, V> tailMap(@ParametricNullness K fromKey) {
4317      return tailMap(fromKey, true);
4318    }
4319
4320    @Override
4321    public Collection<V> values() {
4322      return new Values<>(this);
4323    }
4324
4325    @Override
4326    public String toString() {
4327      return standardToString();
4328    }
4329  }
4330
4331  /** Returns a map from the ith element of list to i. */
4332  static <E> ImmutableMap<E, Integer> indexMap(Collection<E> list) {
4333    ImmutableMap.Builder<E, Integer> builder = new ImmutableMap.Builder<>(list.size());
4334    int i = 0;
4335    for (E e : list) {
4336      builder.put(e, i++);
4337    }
4338    return builder.buildOrThrow();
4339  }
4340
4341  /**
4342   * Returns a view of the portion of {@code map} whose keys are contained by {@code range}.
4343   *
4344   * <p>This method delegates to the appropriate methods of {@link NavigableMap} (namely {@link
4345   * NavigableMap#subMap(Object, boolean, Object, boolean) subMap()}, {@link
4346   * NavigableMap#tailMap(Object, boolean) tailMap()}, and {@link NavigableMap#headMap(Object,
4347   * boolean) headMap()}) to actually construct the view. Consult these methods for a full
4348   * description of the returned view's behavior.
4349   *
4350   * <p><b>Warning:</b> {@code Range}s always represent a range of values using the values' natural
4351   * ordering. {@code NavigableMap} on the other hand can specify a custom ordering via a {@link
4352   * Comparator}, which can violate the natural ordering. Using this method (or in general using
4353   * {@code Range}) with unnaturally-ordered maps can lead to unexpected and undefined behavior.
4354   *
4355   * @since 20.0
4356   */
4357  @GwtIncompatible // NavigableMap
4358  public static <K extends Comparable<? super K>, V extends @Nullable Object>
4359      NavigableMap<K, V> subMap(NavigableMap<K, V> map, Range<K> range) {
4360    if (map.comparator() != null
4361        && map.comparator() != Ordering.natural()
4362        && range.hasLowerBound()
4363        && range.hasUpperBound()) {
4364      checkArgument(
4365          map.comparator().compare(range.lowerEndpoint(), range.upperEndpoint()) <= 0,
4366          "map is using a custom comparator which is inconsistent with the natural ordering.");
4367    }
4368    if (range.hasLowerBound() && range.hasUpperBound()) {
4369      return map.subMap(
4370          range.lowerEndpoint(),
4371          range.lowerBoundType() == BoundType.CLOSED,
4372          range.upperEndpoint(),
4373          range.upperBoundType() == BoundType.CLOSED);
4374    } else if (range.hasLowerBound()) {
4375      return map.tailMap(range.lowerEndpoint(), range.lowerBoundType() == BoundType.CLOSED);
4376    } else if (range.hasUpperBound()) {
4377      return map.headMap(range.upperEndpoint(), range.upperBoundType() == BoundType.CLOSED);
4378    }
4379    return checkNotNull(map);
4380  }
4381}