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