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