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