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