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