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