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