    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
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkArgument;
    020    import static com.google.common.base.Preconditions.checkNotNull;
    021
    022    import com.google.common.annotations.Beta;
    023    import com.google.common.annotations.GwtCompatible;
    024    import com.google.common.annotations.GwtIncompatible;
    025    import com.google.common.base.Equivalence;
    026    import com.google.common.base.Equivalences;
    027    import com.google.common.base.Function;
    028    import com.google.common.base.Joiner.MapJoiner;
    029    import com.google.common.base.Objects;
    030    import com.google.common.base.Preconditions;
    031    import com.google.common.base.Predicate;
    032    import com.google.common.base.Predicates;
    033    import com.google.common.collect.MapDifference.ValueDifference;
    034    import com.google.common.primitives.Ints;
    035
    036    import java.io.Serializable;
    037    import java.util.AbstractCollection;
    038    import java.util.AbstractMap;
    039    import java.util.AbstractSet;
    040    import java.util.Collection;
    041    import java.util.Collections;
    042    import java.util.Comparator;
    043    import java.util.EnumMap;
    044    import java.util.Enumeration;
    045    import java.util.HashMap;
    046    import java.util.IdentityHashMap;
    047    import java.util.Iterator;
    048    import java.util.LinkedHashMap;
    049    import java.util.Map;
    050    import java.util.Map.Entry;
    051    import java.util.Properties;
    052    import java.util.Set;
    053    import java.util.SortedMap;
    054    import java.util.TreeMap;
    055    import java.util.concurrent.ConcurrentMap;
    056
    057    import javax.annotation.Nullable;
    058
    059    /**
    060     * Static utility methods pertaining to {@link Map} instances. Also see this
    061     * class's counterparts {@link Lists} and {@link Sets}.
    062     *
    063     * @author Kevin Bourrillion
    064     * @author Mike Bostock
    065     * @author Isaac Shum
    066     * @author Louis Wasserman
    067     * @since 2.0 (imported from Google Collections Library)
    068     */
    069    @GwtCompatible(emulated = true)
    070    public final class Maps {
    071      private Maps() {}
    072
    073      /**
    074       * Creates a <i>mutable</i>, empty {@code HashMap} instance.
    075       *
    076       * <p><b>Note:</b> if mutability is not required, use {@link
    077       * ImmutableMap#of()} instead.
    078       *
    079       * <p><b>Note:</b> if {@code K} is an {@code enum} type, use {@link
    080       * #newEnumMap} instead.
    081       *
    082       * @return a new, empty {@code HashMap}
    083       */
    084      public static <K, V> HashMap<K, V> newHashMap() {
    085        return new HashMap<K, V>();
    086      }
    087
    088      /**
    089       * Creates a {@code HashMap} instance, with a high enough "initial capacity"
    090       * that it <i>should</i> hold {@code expectedSize} elements without growth.
    091       * This behavior cannot be broadly guaranteed, but it is observed to be true
    092       * for OpenJDK 1.6. It also can't be guaranteed that the method isn't
    093       * inadvertently <i>oversizing</i> the returned map.
    094       *
    095       * @param expectedSize the number of elements you expect to add to the
    096       *        returned map
    097       * @return a new, empty {@code HashMap} with enough capacity to hold {@code
    098       *         expectedSize} elements without resizing
    099       * @throws IllegalArgumentException if {@code expectedSize} is negative
    100       */
    101      public static <K, V> HashMap<K, V> newHashMapWithExpectedSize(
    102          int expectedSize) {
    103        return new HashMap<K, V>(capacity(expectedSize));
    104      }
    105
    106      /**
    107       * Returns a capacity that is sufficient to keep the map from being resized as
    108       * long as it grows no larger than expectedSize and the load factor is >= its
    109       * default (0.75).
    110       */
    111      static int capacity(int expectedSize) {
    112        if (expectedSize < 3) {
    113          checkArgument(expectedSize >= 0);
    114          return expectedSize + 1;
    115        }
    116        if (expectedSize < Ints.MAX_POWER_OF_TWO) {
    117          return expectedSize + expectedSize / 3;
    118        }
    119        return Integer.MAX_VALUE; // any large value
    120      }
    121
    122      /**
    123       * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as
    124       * the specified map.
    125       *
    126       * <p><b>Note:</b> if mutability is not required, use {@link
    127       * ImmutableMap#copyOf(Map)} instead.
    128       *
    129       * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link
    130       * #newEnumMap} instead.
    131       *
    132       * @param map the mappings to be placed in the new map
    133       * @return a new {@code HashMap} initialized with the mappings from {@code
    134       *         map}
    135       */
    136      public static <K, V> HashMap<K, V> newHashMap(
    137          Map<? extends K, ? extends V> map) {
    138        return new HashMap<K, V>(map);
    139      }
    140
    141      /**
    142       * Creates a <i>mutable</i>, empty, insertion-ordered {@code LinkedHashMap}
    143       * instance.
    144       *
    145       * <p><b>Note:</b> if mutability is not required, use {@link
    146       * ImmutableMap#of()} instead.
    147       *
    148       * @return a new, empty {@code LinkedHashMap}
    149       */
    150      public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() {
    151        return new LinkedHashMap<K, V>();
    152      }
    153
    154      /**
    155       * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance
    156       * with the same mappings as the specified map.
    157       *
    158       * <p><b>Note:</b> if mutability is not required, use {@link
    159       * ImmutableMap#copyOf(Map)} instead.
    160       *
    161       * @param map the mappings to be placed in the new map
    162       * @return a new, {@code LinkedHashMap} initialized with the mappings from
    163       *         {@code map}
    164       */
    165      public static <K, V> LinkedHashMap<K, V> newLinkedHashMap(
    166          Map<? extends K, ? extends V> map) {
    167        return new LinkedHashMap<K, V>(map);
    168      }
    169
    170      /**
    171       * Returns a general-purpose instance of {@code ConcurrentMap}, which supports
    172       * all optional operations of the ConcurrentMap interface. It does not permit
    173       * null keys or values. It is serializable.
    174       *
    175       * <p>This is currently accomplished by calling {@link MapMaker#makeMap()}.
    176       *
    177       * <p>It is preferable to use {@code MapMaker} directly (rather than through
    178       * this method), as it presents numerous useful configuration options,
    179       * such as the concurrency level, load factor, key/value reference types,
    180       * and value computation.
    181       *
    182       * @return a new, empty {@code ConcurrentMap}
    183       * @since 3.0
    184       */
    185      public static <K, V> ConcurrentMap<K, V> newConcurrentMap() {
    186        return new MapMaker().<K, V>makeMap();
    187      }
    188
    189      /**
    190       * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural
    191       * ordering of its elements.
    192       *
    193       * <p><b>Note:</b> if mutability is not required, use {@link
    194       * ImmutableSortedMap#of()} instead.
    195       *
    196       * @return a new, empty {@code TreeMap}
    197       */
    198      public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() {
    199        return new TreeMap<K, V>();
    200      }
    201
    202      /**
    203       * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as
    204       * the specified map and using the same ordering as the specified map.
    205       *
    206       * <p><b>Note:</b> if mutability is not required, use {@link
    207       * ImmutableSortedMap#copyOfSorted(SortedMap)} instead.
    208       *
    209       * @param map the sorted map whose mappings are to be placed in the new map
    210       *        and whose comparator is to be used to sort the new map
    211       * @return a new {@code TreeMap} initialized with the mappings from {@code
    212       *         map} and using the comparator of {@code map}
    213       */
    214      public static <K, V> TreeMap<K, V> newTreeMap(SortedMap<K, ? extends V> map) {
    215        return new TreeMap<K, V>(map);
    216      }
    217
    218      /**
    219       * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given
    220       * comparator.
    221       *
    222       * <p><b>Note:</b> if mutability is not required, use {@code
    223       * ImmutableSortedMap.orderedBy(comparator).build()} instead.
    224       *
    225       * @param comparator the comparator to sort the keys with
    226       * @return a new, empty {@code TreeMap}
    227       */
    228      public static <C, K extends C, V> TreeMap<K, V> newTreeMap(
    229          @Nullable Comparator<C> comparator) {
    230        // Ideally, the extra type parameter "C" shouldn't be necessary. It is a
    231        // work-around of a compiler type inference quirk that prevents the
    232        // following code from being compiled:
    233        // Comparator<Class<?>> comparator = null;
    234        // Map<Class<? extends Throwable>, String> map = newTreeMap(comparator);
    235        return new TreeMap<K, V>(comparator);
    236      }
    237
    238      /**
    239       * Creates an {@code EnumMap} instance.
    240       *
    241       * @param type the key type for this map
    242       * @return a new, empty {@code EnumMap}
    243       */
    244      public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Class<K> type) {
    245        return new EnumMap<K, V>(checkNotNull(type));
    246      }
    247
    248      /**
    249       * Creates an {@code EnumMap} with the same mappings as the specified map.
    250       *
    251       * @param map the map from which to initialize this {@code EnumMap}
    252       * @return a new {@code EnumMap} initialized with the mappings from {@code
    253       *         map}
    254       * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap}
    255       *         instance and contains no mappings
    256       */
    257      public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(
    258          Map<K, ? extends V> map) {
    259        return new EnumMap<K, V>(map);
    260      }
    261
    262      /**
    263       * Creates an {@code IdentityHashMap} instance.
    264       *
    265       * @return a new, empty {@code IdentityHashMap}
    266       */
    267      public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() {
    268        return new IdentityHashMap<K, V>();
    269      }
    270
    271      /**
    272       * Returns a synchronized (thread-safe) bimap backed by the specified bimap.
    273       * In order to guarantee serial access, it is critical that <b>all</b> access
    274       * to the backing bimap is accomplished through the returned bimap.
    275       *
    276       * <p>It is imperative that the user manually synchronize on the returned map
    277       * when accessing any of its collection views: <pre>   {@code
    278       *
    279       *   BiMap<Long, String> map = Maps.synchronizedBiMap(
    280       *       HashBiMap.<Long, String>create());
    281       *   ...
    282       *   Set<Long> set = map.keySet();  // Needn't be in synchronized block
    283       *   ...
    284       *   synchronized (map) {  // Synchronizing on map, not set!
    285       *     Iterator<Long> it = set.iterator(); // Must be in synchronized block
    286       *     while (it.hasNext()) {
    287       *       foo(it.next());
    288       *     }
    289       *   }}</pre>
    290       *
    291       * Failure to follow this advice may result in non-deterministic behavior.
    292       *
    293       * <p>The returned bimap will be serializable if the specified bimap is
    294       * serializable.
    295       *
    296       * @param bimap the bimap to be wrapped in a synchronized view
    297       * @return a sychronized view of the specified bimap
    298       */
    299      public static <K, V> BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) {
    300        return Synchronized.biMap(bimap, null);
    301      }
    302
    303      /**
    304       * Computes the difference between two maps. This difference is an immutable
    305       * snapshot of the state of the maps at the time this method is called. It
    306       * will never change, even if the maps change at a later time.
    307       *
    308       * <p>Since this method uses {@code HashMap} instances internally, the keys of
    309       * the supplied maps must be well-behaved with respect to
    310       * {@link Object#equals} and {@link Object#hashCode}.
    311       *
    312       * <p><b>Note:</b>If you only need to know whether two maps have the same
    313       * mappings, call {@code left.equals(right)} instead of this method.
    314       *
    315       * @param left the map to treat as the "left" map for purposes of comparison
    316       * @param right the map to treat as the "right" map for purposes of comparison
    317       * @return the difference between the two maps
    318       */
    319      public static <K, V> MapDifference<K, V> difference(
    320          Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) {
    321        return difference(left, right, Equivalences.equals());
    322      }
    323
    324      /**
    325       * Computes the difference between two maps. This difference is an immutable
    326       * snapshot of the state of the maps at the time this method is called. It
    327       * will never change, even if the maps change at a later time.
    328       *
    329       * <p>Values are compared using a provided equivalence, in the case of
    330       * equality, the value on the 'left' is returned in the difference.
    331       *
    332       * <p>Since this method uses {@code HashMap} instances internally, the keys of
    333       * the supplied maps must be well-behaved with respect to
    334       * {@link Object#equals} and {@link Object#hashCode}.
    335       *
    336       * @param left the map to treat as the "left" map for purposes of comparison
    337       * @param right the map to treat as the "right" map for purposes of comparison
    338       * @param valueEquivalence the equivalence relationship to use to compare
    339       *    values
    340       * @return the difference between the two maps
    341       * @since 10.0
    342       */
    343      @Beta
    344      public static <K, V> MapDifference<K, V> difference(
    345          Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right,
    346          Equivalence<? super V> valueEquivalence) {
    347        Preconditions.checkNotNull(valueEquivalence);
    348
    349        Map<K, V> onlyOnLeft = newHashMap();
    350        Map<K, V> onlyOnRight = new HashMap<K, V>(right); // will whittle it down
    351        Map<K, V> onBoth = newHashMap();
    352        Map<K, MapDifference.ValueDifference<V>> differences = newHashMap();
    353        boolean eq = true;
    354
    355        for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
    356          K leftKey = entry.getKey();
    357          V leftValue = entry.getValue();
    358          if (right.containsKey(leftKey)) {
    359            V rightValue = onlyOnRight.remove(leftKey);
    360            if (valueEquivalence.equivalent(leftValue, rightValue)) {
    361              onBoth.put(leftKey, leftValue);
    362            } else {
    363              eq = false;
    364              differences.put(
    365                  leftKey, ValueDifferenceImpl.create(leftValue, rightValue));
    366            }
    367          } else {
    368            eq = false;
    369            onlyOnLeft.put(leftKey, leftValue);
    370          }
    371        }
    372
    373        boolean areEqual = eq && onlyOnRight.isEmpty();
    374        return mapDifference(
    375            areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
    376      }
    377
    378      private static <K, V> MapDifference<K, V> mapDifference(boolean areEqual,
    379          Map<K, V> onlyOnLeft, Map<K, V> onlyOnRight, Map<K, V> onBoth,
    380          Map<K, ValueDifference<V>> differences) {
    381        return new MapDifferenceImpl<K, V>(areEqual,
    382            Collections.unmodifiableMap(onlyOnLeft),
    383            Collections.unmodifiableMap(onlyOnRight),
    384            Collections.unmodifiableMap(onBoth),
    385            Collections.unmodifiableMap(differences));
    386      }
    387
    388      static class MapDifferenceImpl<K, V> implements MapDifference<K, V> {
    389        final boolean areEqual;
    390        final Map<K, V> onlyOnLeft;
    391        final Map<K, V> onlyOnRight;
    392        final Map<K, V> onBoth;
    393        final Map<K, ValueDifference<V>> differences;
    394
    395        MapDifferenceImpl(boolean areEqual, Map<K, V> onlyOnLeft,
    396            Map<K, V> onlyOnRight, Map<K, V> onBoth,
    397            Map<K, ValueDifference<V>> differences) {
    398          this.areEqual = areEqual;
    399          this.onlyOnLeft = onlyOnLeft;
    400          this.onlyOnRight = onlyOnRight;
    401          this.onBoth = onBoth;
    402          this.differences = differences;
    403        }
    404
    405        @Override
    406        public boolean areEqual() {
    407          return areEqual;
    408        }
    409
    410        @Override
    411        public Map<K, V> entriesOnlyOnLeft() {
    412          return onlyOnLeft;
    413        }
    414
    415        @Override
    416        public Map<K, V> entriesOnlyOnRight() {
    417          return onlyOnRight;
    418        }
    419
    420        @Override
    421        public Map<K, V> entriesInCommon() {
    422          return onBoth;
    423        }
    424
    425        @Override
    426        public Map<K, ValueDifference<V>> entriesDiffering() {
    427          return differences;
    428        }
    429
    430        @Override public boolean equals(Object object) {
    431          if (object == this) {
    432            return true;
    433          }
    434          if (object instanceof MapDifference) {
    435            MapDifference<?, ?> other = (MapDifference<?, ?>) object;
    436            return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft())
    437                && entriesOnlyOnRight().equals(other.entriesOnlyOnRight())
    438                && entriesInCommon().equals(other.entriesInCommon())
    439                && entriesDiffering().equals(other.entriesDiffering());
    440          }
    441          return false;
    442        }
    443
    444        @Override public int hashCode() {
    445          return Objects.hashCode(entriesOnlyOnLeft(), entriesOnlyOnRight(),
    446              entriesInCommon(), entriesDiffering());
    447        }
    448
    449        @Override public String toString() {
    450          if (areEqual) {
    451            return "equal";
    452          }
    453
    454          StringBuilder result = new StringBuilder("not equal");
    455          if (!onlyOnLeft.isEmpty()) {
    456            result.append(": only on left=").append(onlyOnLeft);
    457          }
    458          if (!onlyOnRight.isEmpty()) {
    459            result.append(": only on right=").append(onlyOnRight);
    460          }
    461          if (!differences.isEmpty()) {
    462            result.append(": value differences=").append(differences);
    463          }
    464          return result.toString();
    465        }
    466      }
    467
    468      static class ValueDifferenceImpl<V>
    469          implements MapDifference.ValueDifference<V> {
    470        private final V left;
    471        private final V right;
    472
    473        static <V> ValueDifference<V> create(@Nullable V left, @Nullable V right) {
    474          return new ValueDifferenceImpl<V>(left, right);
    475        }
    476
    477        private ValueDifferenceImpl(@Nullable V left, @Nullable V right) {
    478          this.left = left;
    479          this.right = right;
    480        }
    481
    482        @Override
    483        public V leftValue() {
    484          return left;
    485        }
    486
    487        @Override
    488        public V rightValue() {
    489          return right;
    490        }
    491
    492        @Override public boolean equals(@Nullable Object object) {
    493          if (object instanceof MapDifference.ValueDifference<?>) {
    494            MapDifference.ValueDifference<?> that =
    495                (MapDifference.ValueDifference<?>) object;
    496            return Objects.equal(this.left, that.leftValue())
    497                && Objects.equal(this.right, that.rightValue());
    498          }
    499          return false;
    500        }
    501
    502        @Override public int hashCode() {
    503          return Objects.hashCode(left, right);
    504        }
    505
    506        @Override public String toString() {
    507          return "(" + left + ", " + right + ")";
    508        }
    509      }
    510
    511      /**
    512       * Returns an immutable map for which the {@link Map#values} are the given
    513       * elements in the given order, and each key is the product of invoking a
    514       * supplied function on its corresponding value.
    515       *
    516       * @param values the values to use when constructing the {@code Map}
    517       * @param keyFunction the function used to produce the key for each value
    518       * @return a map mapping the result of evaluating the function {@code
    519       *         keyFunction} on each value in the input collection to that value
    520       * @throws IllegalArgumentException if {@code keyFunction} produces the same
    521       *         key for more than one value in the input collection
    522       * @throws NullPointerException if any elements of {@code values} is null, or
    523       *         if {@code keyFunction} produces {@code null} for any value
    524       */
    525      public static <K, V> ImmutableMap<K, V> uniqueIndex(
    526          Iterable<V> values, Function<? super V, K> keyFunction) {
    527        return uniqueIndex(values.iterator(), keyFunction);
    528      }
    529
    530      /**
    531       * <b>Deprecated.</b>
    532       *
    533       * @since 10.0
    534       * @deprecated use {@link #uniqueIndex(Iterator, Function)} by casting {@code
    535       *     values} to {@code Iterator<V>}, or better yet, by implementing only
    536       *     {@code Iterator} and not {@code Iterable}. <b>This method is scheduled
    537       *     for deletion in March 2012.</b>
    538       */
    539      @Beta
    540      @Deprecated
    541      public static <K, V, I extends Object & Iterable<V> & Iterator<V>>
    542          ImmutableMap<K, V> uniqueIndex(
    543              I values, Function<? super V, K> keyFunction) {
    544        Iterable<V> valuesIterable = checkNotNull(values);
    545        return uniqueIndex(valuesIterable, keyFunction);
    546      }
    547
    548      /**
    549       * Returns an immutable map for which the {@link Map#values} are the given
    550       * elements in the given order, and each key is the product of invoking a
    551       * supplied function on its corresponding value.
    552       *
    553       * @param values the values to use when constructing the {@code Map}
    554       * @param keyFunction the function used to produce the key for each value
    555       * @return a map mapping the result of evaluating the function {@code
    556       *         keyFunction} on each value in the input collection to that value
    557       * @throws IllegalArgumentException if {@code keyFunction} produces the same
    558       *         key for more than one value in the input collection
    559       * @throws NullPointerException if any elements of {@code values} is null, or
    560       *         if {@code keyFunction} produces {@code null} for any value
    561       * @since 10.0
    562       */
    563      public static <K, V> ImmutableMap<K, V> uniqueIndex(
    564          Iterator<V> values, Function<? super V, K> keyFunction) {
    565        checkNotNull(keyFunction);
    566        ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
    567        while (values.hasNext()) {
    568          V value = values.next();
    569          builder.put(keyFunction.apply(value), value);
    570        }
    571        return builder.build();
    572      }
    573
    574      /**
    575       * Creates an {@code ImmutableMap<String, String>} from a {@code Properties}
    576       * instance. Properties normally derive from {@code Map<Object, Object>}, but
    577       * they typically contain strings, which is awkward. This method lets you get
    578       * a plain-old-{@code Map} out of a {@code Properties}.
    579       *
    580       * @param properties a {@code Properties} object to be converted
    581       * @return an immutable map containing all the entries in {@code properties}
    582       * @throws ClassCastException if any key in {@code Properties} is not a {@code
    583       *         String}
    584       * @throws NullPointerException if any key or value in {@code Properties} is
    585       *         null
    586       */
    587      @GwtIncompatible("java.util.Properties")
    588      public static ImmutableMap<String, String> fromProperties(
    589          Properties properties) {
    590        ImmutableMap.Builder<String, String> builder = ImmutableMap.builder();
    591
    592        for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements();) {
    593          String key = (String) e.nextElement();
    594          builder.put(key, properties.getProperty(key));
    595        }
    596
    597        return builder.build();
    598      }
    599
    600      /**
    601       * Returns an immutable map entry with the specified key and value. The {@link
    602       * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
    603       *
    604       * <p>The returned entry is serializable.
    605       *
    606       * @param key the key to be associated with the returned entry
    607       * @param value the value to be associated with the returned entry
    608       */
    609      @GwtCompatible(serializable = true)
    610      public static <K, V> Entry<K, V> immutableEntry(
    611          @Nullable K key, @Nullable V value) {
    612        return new ImmutableEntry<K, V>(key, value);
    613      }
    614
    615      /**
    616       * Returns an unmodifiable view of the specified set of entries. The {@link
    617       * Entry#setValue} operation throws an {@link UnsupportedOperationException},
    618       * as do any operations that would modify the returned set.
    619       *
    620       * @param entrySet the entries for which to return an unmodifiable view
    621       * @return an unmodifiable view of the entries
    622       */
    623      static <K, V> Set<Entry<K, V>> unmodifiableEntrySet(
    624          Set<Entry<K, V>> entrySet) {
    625        return new UnmodifiableEntrySet<K, V>(
    626            Collections.unmodifiableSet(entrySet));
    627      }
    628
    629      /**
    630       * Returns an unmodifiable view of the specified map entry. The {@link
    631       * Entry#setValue} operation throws an {@link UnsupportedOperationException}.
    632       * This also has the side-effect of redefining {@code equals} to comply with
    633       * the Entry contract, to avoid a possible nefarious implementation of equals.
    634       *
    635       * @param entry the entry for which to return an unmodifiable view
    636       * @return an unmodifiable view of the entry
    637       */
    638      static <K, V> Entry<K, V> unmodifiableEntry(final Entry<K, V> entry) {
    639        checkNotNull(entry);
    640        return new AbstractMapEntry<K, V>() {
    641          @Override public K getKey() {
    642            return entry.getKey();
    643          }
    644
    645          @Override public V getValue() {
    646            return entry.getValue();
    647          }
    648        };
    649      }
    650
    651      /** @see Multimaps#unmodifiableEntries */
    652      static class UnmodifiableEntries<K, V>
    653          extends ForwardingCollection<Entry<K, V>> {
    654        private final Collection<Entry<K, V>> entries;
    655
    656        UnmodifiableEntries(Collection<Entry<K, V>> entries) {
    657          this.entries = entries;
    658        }
    659
    660        @Override protected Collection<Entry<K, V>> delegate() {
    661          return entries;
    662        }
    663
    664        @Override public Iterator<Entry<K, V>> iterator() {
    665          final Iterator<Entry<K, V>> delegate = super.iterator();
    666          return new ForwardingIterator<Entry<K, V>>() {
    667            @Override public Entry<K, V> next() {
    668              return unmodifiableEntry(super.next());
    669            }
    670
    671            @Override public void remove() {
    672              throw new UnsupportedOperationException();
    673            }
    674
    675            @Override protected Iterator<Entry<K, V>> delegate() {
    676              return delegate;
    677            }
    678          };
    679        }
    680
    681        // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
    682
    683        @Override public boolean add(Entry<K, V> element) {
    684          throw new UnsupportedOperationException();
    685        }
    686
    687        @Override public boolean addAll(
    688            Collection<? extends Entry<K, V>> collection) {
    689          throw new UnsupportedOperationException();
    690        }
    691
    692        @Override public void clear() {
    693          throw new UnsupportedOperationException();
    694        }
    695
    696        @Override public boolean remove(Object object) {
    697          throw new UnsupportedOperationException();
    698        }
    699
    700        @Override public boolean removeAll(Collection<?> collection) {
    701          throw new UnsupportedOperationException();
    702        }
    703
    704        @Override public boolean retainAll(Collection<?> collection) {
    705          throw new UnsupportedOperationException();
    706        }
    707
    708        @Override public Object[] toArray() {
    709          return standardToArray();
    710        }
    711
    712        @Override public <T> T[] toArray(T[] array) {
    713          return standardToArray(array);
    714        }
    715      }
    716
    717      /** @see Maps#unmodifiableEntrySet(Set) */
    718      static class UnmodifiableEntrySet<K, V>
    719          extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> {
    720        UnmodifiableEntrySet(Set<Entry<K, V>> entries) {
    721          super(entries);
    722        }
    723
    724        // See java.util.Collections.UnmodifiableEntrySet for details on attacks.
    725
    726        @Override public boolean equals(@Nullable Object object) {
    727          return Sets.equalsImpl(this, object);
    728        }
    729
    730        @Override public int hashCode() {
    731          return Sets.hashCodeImpl(this);
    732        }
    733      }
    734
    735      /**
    736       * Returns an unmodifiable view of the specified bimap. This method allows
    737       * modules to provide users with "read-only" access to internal bimaps. Query
    738       * operations on the returned bimap "read through" to the specified bimap, and
    739       * attemps to modify the returned map, whether direct or via its collection
    740       * views, result in an {@code UnsupportedOperationException}.
    741       *
    742       * <p>The returned bimap will be serializable if the specified bimap is
    743       * serializable.
    744       *
    745       * @param bimap the bimap for which an unmodifiable view is to be returned
    746       * @return an unmodifiable view of the specified bimap
    747       */
    748      public static <K, V> BiMap<K, V> unmodifiableBiMap(
    749          BiMap<? extends K, ? extends V> bimap) {
    750        return new UnmodifiableBiMap<K, V>(bimap, null);
    751      }
    752
    753      /** @see Maps#unmodifiableBiMap(BiMap) */
    754      private static class UnmodifiableBiMap<K, V>
    755          extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable {
    756        final Map<K, V> unmodifiableMap;
    757        final BiMap<? extends K, ? extends V> delegate;
    758        transient BiMap<V, K> inverse;
    759        transient Set<V> values;
    760
    761        UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate,
    762            @Nullable BiMap<V, K> inverse) {
    763          unmodifiableMap = Collections.unmodifiableMap(delegate);
    764          this.delegate = delegate;
    765          this.inverse = inverse;
    766        }
    767
    768        @Override protected Map<K, V> delegate() {
    769          return unmodifiableMap;
    770        }
    771
    772        @Override
    773        public V forcePut(K key, V value) {
    774          throw new UnsupportedOperationException();
    775        }
    776
    777        @Override
    778        public BiMap<V, K> inverse() {
    779          BiMap<V, K> result = inverse;
    780          return (result == null)
    781              ? inverse = new UnmodifiableBiMap<V, K>(delegate.inverse(), this)
    782              : result;
    783        }
    784
    785        @Override public Set<V> values() {
    786          Set<V> result = values;
    787          return (result == null)
    788              ? values = Collections.unmodifiableSet(delegate.values())
    789              : result;
    790        }
    791
    792        private static final long serialVersionUID = 0;
    793      }
    794
    795      /**
    796       * Returns a view of a map where each value is transformed by a function. All
    797       * other properties of the map, such as iteration order, are left intact. For
    798       * example, the code: <pre>   {@code
    799       *
    800       *   Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9);
    801       *   Function<Integer, Double> sqrt =
    802       *       new Function<Integer, Double>() {
    803       *         public Double apply(Integer in) {
    804       *           return Math.sqrt((int) in);
    805       *         }
    806       *       };
    807       *   Map<String, Double> transformed = Maps.transformValues(map, sqrt);
    808       *   System.out.println(transformed);}</pre>
    809       *
    810       * ... prints {@code {a=2.0, b=3.0}}.
    811       *
    812       * <p>Changes in the underlying map are reflected in this view. Conversely,
    813       * this view supports removal operations, and these are reflected in the
    814       * underlying map.
    815       *
    816       * <p>It's acceptable for the underlying map to contain null keys, and even
    817       * null values provided that the function is capable of accepting null input.
    818       * The transformed map might contain null values, if the function sometimes
    819       * gives a null result.
    820       *
    821       * <p>The returned map is not thread-safe or serializable, even if the
    822       * underlying map is.
    823       *
    824       * <p>The function is applied lazily, invoked when needed. This is necessary
    825       * for the returned map to be a view, but it means that the function will be
    826       * applied many times for bulk operations like {@link Map#containsValue} and
    827       * {@code Map.toString()}. For this to perform well, {@code function} should
    828       * be fast. To avoid lazy evaluation when the returned map doesn't need to be
    829       * a view, copy the returned map into a new map of your choosing.
    830       */
    831      public static <K, V1, V2> Map<K, V2> transformValues(
    832          Map<K, V1> fromMap, final Function<? super V1, V2> function) {
    833        checkNotNull(function);
    834        EntryTransformer<K, V1, V2> transformer =
    835            new EntryTransformer<K, V1, V2>() {
    836              @Override
    837              public V2 transformEntry(K key, V1 value) {
    838                return function.apply(value);
    839              }
    840            };
    841        return transformEntries(fromMap, transformer);
    842      }
    843
    844      /**
    845       * Returns a view of a map whose values are derived from the original map's
    846       * entries. In contrast to {@link #transformValues}, this method's
    847       * entry-transformation logic may depend on the key as well as the value.
    848       *
    849       * <p>All other properties of the transformed map, such as iteration order,
    850       * are left intact. For example, the code: <pre>   {@code
    851       *
    852       *   Map<String, Boolean> options =
    853       *       ImmutableMap.of("verbose", true, "sort", false);
    854       *   EntryTransformer<String, Boolean, String> flagPrefixer =
    855       *       new EntryTransformer<String, Boolean, String>() {
    856       *         public String transformEntry(String key, Boolean value) {
    857       *           return value ? key : "no" + key;
    858       *         }
    859       *       };
    860       *   Map<String, String> transformed =
    861       *       Maps.transformEntries(options, flagPrefixer);
    862       *   System.out.println(transformed);}</pre>
    863       *
    864       * ... prints {@code {verbose=verbose, sort=nosort}}.
    865       *
    866       * <p>Changes in the underlying map are reflected in this view. Conversely,
    867       * this view supports removal operations, and these are reflected in the
    868       * underlying map.
    869       *
    870       * <p>It's acceptable for the underlying map to contain null keys and null
    871       * values provided that the transformer is capable of accepting null inputs.
    872       * The transformed map might contain null values if the transformer sometimes
    873       * gives a null result.
    874       *
    875       * <p>The returned map is not thread-safe or serializable, even if the
    876       * underlying map is.
    877       *
    878       * <p>The transformer is applied lazily, invoked when needed. This is
    879       * necessary for the returned map to be a view, but it means that the
    880       * transformer will be applied many times for bulk operations like {@link
    881       * Map#containsValue} and {@link Object#toString}. For this to perform well,
    882       * {@code transformer} should be fast. To avoid lazy evaluation when the
    883       * returned map doesn't need to be a view, copy the returned map into a new
    884       * map of your choosing.
    885       *
    886       * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
    887       * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
    888       * that {@code k2} is also of type {@code K}. Using an {@code
    889       * EntryTransformer} key type for which this may not hold, such as {@code
    890       * ArrayList}, may risk a {@code ClassCastException} when calling methods on
    891       * the transformed map.
    892       *
    893       * @since 7.0
    894       */
    895      public static <K, V1, V2> Map<K, V2> transformEntries(
    896          Map<K, V1> fromMap,
    897          EntryTransformer<? super K, ? super V1, V2> transformer) {
    898        return new TransformedEntriesMap<K, V1, V2>(fromMap, transformer);
    899      }
    900
    901      /**
    902       * A transformation of the value of a key-value pair, using both key and value
    903       * as inputs. To apply the transformation to a map, use
    904       * {@link Maps#transformEntries(Map, EntryTransformer)}.
    905       *
    906       * @param <K> the key type of the input and output entries
    907       * @param <V1> the value type of the input entry
    908       * @param <V2> the value type of the output entry
    909       * @since 7.0
    910       */
    911      public interface EntryTransformer<K, V1, V2> {
    912        /**
    913         * Determines an output value based on a key-value pair. This method is
    914         * <i>generally expected</i>, but not absolutely required, to have the
    915         * following properties:
    916         *
    917         * <ul>
    918         * <li>Its execution does not cause any observable side effects.
    919         * <li>The computation is <i>consistent with equals</i>; that is,
    920         *     {@link Objects#equal Objects.equal}{@code (k1, k2) &&}
    921         *     {@link Objects#equal}{@code (v1, v2)} implies that {@code
    922         *     Objects.equal(transformer.transform(k1, v1),
    923         *     transformer.transform(k2, v2))}.
    924         * </ul>
    925         *
    926         * @throws NullPointerException if the key or value is null and this
    927         *     transformer does not accept null arguments
    928         */
    929        V2 transformEntry(@Nullable K key, @Nullable V1 value);
    930      }
    931
    932      static class TransformedEntriesMap<K, V1, V2>
    933          extends AbstractMap<K, V2> {
    934        final Map<K, V1> fromMap;
    935        final EntryTransformer<? super K, ? super V1, V2> transformer;
    936
    937        TransformedEntriesMap(
    938            Map<K, V1> fromMap,
    939            EntryTransformer<? super K, ? super V1, V2> transformer) {
    940          this.fromMap = checkNotNull(fromMap);
    941          this.transformer = checkNotNull(transformer);
    942        }
    943
    944        @Override public int size() {
    945          return fromMap.size();
    946        }
    947
    948        @Override public boolean containsKey(Object key) {
    949          return fromMap.containsKey(key);
    950        }
    951
    952        // safe as long as the user followed the <b>Warning</b> in the javadoc
    953        @SuppressWarnings("unchecked")
    954        @Override public V2 get(Object key) {
    955          V1 value = fromMap.get(key);
    956          return (value != null || fromMap.containsKey(key))
    957              ? transformer.transformEntry((K) key, value)
    958              : null;
    959        }
    960
    961        // safe as long as the user followed the <b>Warning</b> in the javadoc
    962        @SuppressWarnings("unchecked")
    963        @Override public V2 remove(Object key) {
    964          return fromMap.containsKey(key)
    965              ? transformer.transformEntry((K) key, fromMap.remove(key))
    966              : null;
    967        }
    968
    969        @Override public void clear() {
    970          fromMap.clear();
    971        }
    972
    973        @Override public Set<K> keySet() {
    974          return fromMap.keySet();
    975        }
    976
    977        Set<Entry<K, V2>> entrySet;
    978
    979        @Override public Set<Entry<K, V2>> entrySet() {
    980          Set<Entry<K, V2>> result = entrySet;
    981          if (result == null) {
    982            entrySet = result = new EntrySet<K, V2>() {
    983              @Override Map<K, V2> map() {
    984                return TransformedEntriesMap.this;
    985              }
    986
    987              @Override public Iterator<Entry<K, V2>> iterator() {
    988                final Iterator<Entry<K, V1>> backingIterator =
    989                    fromMap.entrySet().iterator();
    990                return Iterators.transform(backingIterator,
    991                    new Function<Entry<K, V1>, Entry<K, V2>>() {
    992                      @Override public Entry<K, V2> apply(Entry<K, V1> entry) {
    993                        return immutableEntry(
    994                            entry.getKey(),
    995                            transformer.transformEntry(entry.getKey(),
    996                                entry.getValue()));
    997                      }
    998                    });
    999              }
    1000            };
    1001          }
    1002          return result;
    1003        }
    1004
    1005        Collection<V2> values;
    1006
    1007        @Override public Collection<V2> values() {
    1008          Collection<V2> result = values;
    1009          if (result == null) {
    1010            return values = new Values<K, V2>() {
    1011              @Override Map<K, V2> map() {
    1012                return TransformedEntriesMap.this;
    1013              }
    1014            };
    1015          }
    1016          return result;
    1017        }
    1018      }
    1019
    1020      /**
    1021       * Returns a map containing the mappings in {@code unfiltered} whose keys
    1022       * satisfy a predicate. The returned map is a live view of {@code unfiltered};
    1023       * changes to one affect the other.
    1024       *
    1025       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
    1026       * values()} views have iterators that don't support {@code remove()}, but all
    1027       * other methods are supported by the map and its views. When given a key that
    1028       * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
    1029       * methods throw an {@link IllegalArgumentException}.
    1030       *
    1031       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
    1032       * on the filtered map or its views, only mappings whose keys satisfy the
    1033       * filter will be removed from the underlying map.
    1034       *
    1035       * <p>The returned map isn't threadsafe or serializable, even if {@code
    1036       * unfiltered} is.
    1037       *
    1038       * <p>Many of the filtered map's methods, such as {@code size()},
    1039       * iterate across every key/value mapping in the underlying map and determine
    1040       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
    1041       * faster to copy the filtered map and use the copy.
    1042       *
    1043       * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
    1044       * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
    1045       * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
    1046       * inconsistent with equals.
    1047       */
    1048      public static <K, V> Map<K, V> filterKeys(
    1049          Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
    1050        checkNotNull(keyPredicate);
    1051        Predicate<Entry<K, V>> entryPredicate =
    1052            new Predicate<Entry<K, V>>() {
    1053              @Override
    1054              public boolean apply(Entry<K, V> input) {
    1055                return keyPredicate.apply(input.getKey());
    1056              }
    1057            };
    1058        return (unfiltered instanceof AbstractFilteredMap)
    1059            ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
    1060            : new FilteredKeyMap<K, V>(
    1061                checkNotNull(unfiltered), keyPredicate, entryPredicate);
    1062      }
    1063
    1064      /**
    1065       * Returns a map containing the mappings in {@code unfiltered} whose values
    1066       * satisfy a predicate. The returned map is a live view of {@code unfiltered};
    1067       * changes to one affect the other.
    1068       *
    1069       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
    1070       * values()} views have iterators that don't support {@code remove()}, but all
    1071       * other methods are supported by the map and its views. When given a value
    1072       * that doesn't satisfy the predicate, the map's {@code put()}, {@code
    1073       * putAll()}, and {@link Entry#setValue} methods throw an {@link
    1074       * IllegalArgumentException}.
    1075       *
    1076       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
    1077       * on the filtered map or its views, only mappings whose values satisfy the
    1078       * filter will be removed from the underlying map.
    1079       *
    1080       * <p>The returned map isn't threadsafe or serializable, even if {@code
    1081       * unfiltered} is.
    1082       *
    1083       * <p>Many of the filtered map's methods, such as {@code size()},
    1084       * iterate across every key/value mapping in the underlying map and determine
    1085       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
    1086       * faster to copy the filtered map and use the copy.
    1087       *
    1088       * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
    1089       * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
    1090       * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
    1091       * inconsistent with equals.
    1092       */
    1093      public static <K, V> Map<K, V> filterValues(
    1094          Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
    1095        checkNotNull(valuePredicate);
    1096        Predicate<Entry<K, V>> entryPredicate =
    1097            new Predicate<Entry<K, V>>() {
    1098              @Override
    1099              public boolean apply(Entry<K, V> input) {
    1100                return valuePredicate.apply(input.getValue());
    1101              }
    1102            };
    1103        return filterEntries(unfiltered, entryPredicate);
    1104      }
    1105
    1106      /**
    1107       * Returns a map containing the mappings in {@code unfiltered} that satisfy a
    1108       * predicate. The returned map is a live view of {@code unfiltered}; changes
    1109       * to one affect the other.
    1110       *
    1111       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
    1112       * values()} views have iterators that don't support {@code remove()}, but all
    1113       * other methods are supported by the map and its views. When given a
    1114       * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
    1115       * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
    1116       * Similarly, the map's entries have a {@link Entry#setValue} method that
    1117       * throws an {@link IllegalArgumentException} when the existing key and the
    1118       * provided value don't satisfy the predicate.
    1119       *
    1120       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
    1121       * on the filtered map or its views, only mappings that satisfy the filter
    1122       * will be removed from the underlying map.
    1123       *
    1124       * <p>The returned map isn't threadsafe or serializable, even if {@code
    1125       * unfiltered} is.
    1126       *
    1127       * <p>Many of the filtered map's methods, such as {@code size()},
    1128       * iterate across every key/value mapping in the underlying map and determine
    1129       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
    1130       * faster to copy the filtered map and use the copy.
    1131       *
    1132       * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
    1133       * equals</i>, as documented at {@link Predicate#apply}.
    1134       */
    1135      public static <K, V> Map<K, V> filterEntries(
    1136          Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
    1137        checkNotNull(entryPredicate);
    1138        return (unfiltered instanceof AbstractFilteredMap)
    1139            ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate)
    1140            : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate);
    1141      }
    1142
    1143      /**
    1144       * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
    1145       * filtering a filtered map.
    1146       */
    1147      private static <K, V> Map<K, V> filterFiltered(AbstractFilteredMap<K, V> map,
    1148          Predicate<? super Entry<K, V>> entryPredicate) {
    1149        Predicate<Entry<K, V>> predicate =
    1150            Predicates.and(map.predicate, entryPredicate);
    1151        return new FilteredEntryMap<K, V>(map.unfiltered, predicate);
    1152      }
    1153
    1154      private abstract static class AbstractFilteredMap<K, V>
    1155          extends AbstractMap<K, V> {
    1156        final Map<K, V> unfiltered;
    1157        final Predicate<? super Entry<K, V>> predicate;
    1158
    1159        AbstractFilteredMap(
    1160            Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) {
    1161          this.unfiltered = unfiltered;
    1162          this.predicate = predicate;
    1163        }
    1164
    1165        boolean apply(Object key, V value) {
    1166          // This method is called only when the key is in the map, implying that
    1167          // key is a K.
    1168          @SuppressWarnings("unchecked")
    1169          K k = (K) key;
    1170          return predicate.apply(Maps.immutableEntry(k, value));
    1171        }
    1172
    1173        @Override public V put(K key, V value) {
    1174          checkArgument(apply(key, value));
    1175          return unfiltered.put(key, value);
    1176        }
    1177
    1178        @Override public void putAll(Map<? extends K, ? extends V> map) {
    1179          for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
    1180            checkArgument(apply(entry.getKey(), entry.getValue()));
    1181          }
    1182          unfiltered.putAll(map);
    1183        }
    1184
    1185        @Override public boolean containsKey(Object key) {
    1186          return unfiltered.containsKey(key) && apply(key, unfiltered.get(key));
    1187        }
    1188
    1189        @Override public V get(Object key) {
    1190          V value = unfiltered.get(key);
    1191          return ((value != null) && apply(key, value)) ? value : null;
    1192        }
    1193
    1194        @Override public boolean isEmpty() {
    1195          return entrySet().isEmpty();
    1196        }
    1197
    1198        @Override public V remove(Object key) {
    1199          return containsKey(key) ? unfiltered.remove(key) : null;
    1200        }
    1201
    1202        Collection<V> values;
    1203
    1204        @Override public Collection<V> values() {
    1205          Collection<V> result = values;
    1206          return (result == null) ? values = new Values() : result;
    1207        }
    1208
    1209        class Values extends AbstractCollection<V> {
    1210          @Override public Iterator<V> iterator() {
    1211            final Iterator<Entry<K, V>> entryIterator = entrySet().iterator();
    1212            return new UnmodifiableIterator<V>() {
    1213              @Override
    1214              public boolean hasNext() {
    1215                return entryIterator.hasNext();
    1216              }
    1217
    1218              @Override
    1219              public V next() {
    1220                return entryIterator.next().getValue();
    1221              }
    1222            };
    1223          }
    1224
    1225          @Override public int size() {
    1226            return entrySet().size();
    1227          }
    1228
    1229          @Override public void clear() {
    1230            entrySet().clear();
    1231          }
    1232
    1233          @Override public boolean isEmpty() {
    1234            return entrySet().isEmpty();
    1235          }
    1236
    1237          @Override public boolean remove(Object o) {
    1238            Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
    1239            while (iterator.hasNext()) {
    1240              Entry<K, V> entry = iterator.next();
    1241              if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) {
    1242                iterator.remove();
    1243                return true;
    1244              }
    1245            }
    1246            return false;
    1247          }
    1248
    1249          @Override public boolean removeAll(Collection<?> collection) {
    1250            checkNotNull(collection);
    1251            boolean changed = false;
    1252            Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
    1253            while (iterator.hasNext()) {
    1254              Entry<K, V> entry = iterator.next();
    1255              if (collection.contains(entry.getValue()) && predicate.apply(entry)) {
    1256                iterator.remove();
    1257                changed = true;
    1258              }
    1259            }
    1260            return changed;
    1261          }
    1262
    1263          @Override public boolean retainAll(Collection<?> collection) {
    1264            checkNotNull(collection);
    1265            boolean changed = false;
    1266            Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
    1267            while (iterator.hasNext()) {
    1268              Entry<K, V> entry = iterator.next();
    1269              if (!collection.contains(entry.getValue())
    1270                  && predicate.apply(entry)) {
    1271                iterator.remove();
    1272                changed = true;
    1273              }
    1274            }
    1275            return changed;
    1276          }
    1277
    1278          @Override public Object[] toArray() {
    1279            // creating an ArrayList so filtering happens once
    1280            return Lists.newArrayList(iterator()).toArray();
    1281          }
    1282
    1283          @Override public <T> T[] toArray(T[] array) {
    1284            return Lists.newArrayList(iterator()).toArray(array);
    1285          }
    1286        }
    1287      }
    1288
    1289      private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> {
    1290        Predicate<? super K> keyPredicate;
    1291
    1292        FilteredKeyMap(Map<K, V> unfiltered, Predicate<? super K> keyPredicate,
    1293            Predicate<Entry<K, V>> entryPredicate) {
    1294          super(unfiltered, entryPredicate);
    1295          this.keyPredicate = keyPredicate;
    1296        }
    1297
    1298        Set<Entry<K, V>> entrySet;
    1299
    1300        @Override public Set<Entry<K, V>> entrySet() {
    1301          Set<Entry<K, V>> result = entrySet;
    1302          return (result == null)
    1303              ? entrySet = Sets.filter(unfiltered.entrySet(), predicate)
    1304              : result;
    1305        }
    1306
    1307        Set<K> keySet;
    1308
    1309        @Override public Set<K> keySet() {
    1310          Set<K> result = keySet;
    1311          return (result == null)
    1312              ? keySet = Sets.filter(unfiltered.keySet(), keyPredicate)
    1313              : result;
    1314        }
    1315
    1316        // The cast is called only when the key is in the unfiltered map, implying
    1317        // that key is a K.
    1318        @Override
    1319        @SuppressWarnings("unchecked")
    1320        public boolean containsKey(Object key) {
    1321          return unfiltered.containsKey(key) && keyPredicate.apply((K) key);
    1322        }
    1323      }
    1324
    1325      static class FilteredEntryMap<K, V> extends AbstractFilteredMap<K, V> {
    1326        /**
    1327         * Entries in this set satisfy the predicate, but they don't validate the
    1328         * input to {@code Entry.setValue()}.
    1329         */
    1330        final Set<Entry<K, V>> filteredEntrySet;
    1331
    1332        FilteredEntryMap(
    1333            Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) {
    1334          super(unfiltered, entryPredicate);
    1335          filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate);
    1336        }
    1337
    1338        Set<Entry<K, V>> entrySet;
    1339
    1340        @Override public Set<Entry<K, V>> entrySet() {
    1341          Set<Entry<K, V>> result = entrySet;
    1342          return (result == null) ? entrySet = new EntrySet() : result;
    1343        }
    1344
    1345        private class EntrySet extends ForwardingSet<Entry<K, V>> {
    1346          @Override protected Set<Entry<K, V>> delegate() {
    1347            return filteredEntrySet;
    1348          }
    1349
    1350          @Override public Iterator<Entry<K, V>> iterator() {
    1351            final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
    1352            return new UnmodifiableIterator<Entry<K, V>>() {
    1353              @Override
    1354              public boolean hasNext() {
    1355                return iterator.hasNext();
    1356              }
    1357
    1358              @Override
    1359              public Entry<K, V> next() {
    1360                final Entry<K, V> entry = iterator.next();
    1361                return new ForwardingMapEntry<K, V>() {
    1362                  @Override protected Entry<K, V> delegate() {
    1363                    return entry;
    1364                  }
    1365
    1366                  @Override public V setValue(V value) {
    1367                    checkArgument(apply(entry.getKey(), value));
    1368                    return super.setValue(value);
    1369                  }
    1370                };
    1371              }
    1372            };
    1373          }
    1374        }
    1375
    1376        Set<K> keySet;
    1377
    1378        @Override public Set<K> keySet() {
    1379          Set<K> result = keySet;
    1380          return (result == null) ? keySet = new KeySet() : result;
    1381        }
    1382
    1383        private class KeySet extends AbstractSet<K> {
    1384          @Override public Iterator<K> iterator() {
    1385            final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator();
    1386            return new UnmodifiableIterator<K>() {
    1387              @Override
    1388              public boolean hasNext() {
    1389                return iterator.hasNext();
    1390              }
    1391
    1392              @Override
    1393              public K next() {
    1394                return iterator.next().getKey();
    1395              }
    1396            };
    1397          }
    1398
    1399          @Override public int size() {
    1400            return filteredEntrySet.size();
    1401          }
    1402
    1403          @Override public void clear() {
    1404            filteredEntrySet.clear();
    1405          }
    1406
    1407          @Override public boolean contains(Object o) {
    1408            return containsKey(o);
    1409          }
    1410
    1411          @Override public boolean remove(Object o) {
    1412            if (containsKey(o)) {
    1413              unfiltered.remove(o);
    1414              return true;
    1415            }
    1416            return false;
    1417          }
    1418
    1419          @Override public boolean removeAll(Collection<?> collection) {
    1420            checkNotNull(collection); // for GWT
    1421            boolean changed = false;
    1422            for (Object obj : collection) {
    1423              changed |= remove(obj);
    1424            }
    1425            return changed;
    1426          }
    1427
    1428          @Override public boolean retainAll(Collection<?> collection) {
    1429            checkNotNull(collection); // for GWT
    1430            boolean changed = false;
    1431            Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator();
    1432            while (iterator.hasNext()) {
    1433              Entry<K, V> entry = iterator.next();
    1434              if (!collection.contains(entry.getKey()) && predicate.apply(entry)) {
    1435                iterator.remove();
    1436                changed = true;
    1437              }
    1438            }
    1439            return changed;
    1440          }
    1441
    1442          @Override public Object[] toArray() {
    1443            // creating an ArrayList so filtering happens once
    1444            return Lists.newArrayList(iterator()).toArray();
    1445          }
    1446
    1447          @Override public <T> T[] toArray(T[] array) {
    1448            return Lists.newArrayList(iterator()).toArray(array);
    1449          }
    1450        }
    1451      }
    1452
    1453      /**
    1454       * {@code AbstractMap} extension that implements {@link #isEmpty()} as {@code
    1455       * entrySet().isEmpty()} instead of {@code size() == 0} to speed up
    1456       * implementations where {@code size()} is O(n), and it delegates the {@code
    1457       * isEmpty()} methods of its key set and value collection to this
    1458       * implementation.
    1459       */
    1460      @GwtCompatible
    1461      static abstract class ImprovedAbstractMap<K, V> extends AbstractMap<K, V> {
    1462        /**
    1463         * Creates the entry set to be returned by {@link #entrySet()}. This method
    1464         * is invoked at most once on a given map, at the time when {@code entrySet}
    1465         * is first called.
    1466         */
    1467        protected abstract Set<Entry<K, V>> createEntrySet();
    1468
    1469        private Set<Entry<K, V>> entrySet;
    1470
    1471        @Override public Set<Entry<K, V>> entrySet() {
    1472          Set<Entry<K, V>> result = entrySet;
    1473          if (result == null) {
    1474            entrySet = result = createEntrySet();
    1475          }
    1476          return result;
    1477        }
    1478
    1479        private Set<K> keySet;
    1480
    1481        @Override public Set<K> keySet() {
    1482          Set<K> result = keySet;
    1483          if (result == null) {
    1484            return keySet = new KeySet<K, V>() {
    1485              @Override Map<K, V> map() {
    1486                return ImprovedAbstractMap.this;
    1487              }
    1488            };
    1489          }
    1490          return result;
    1491        }
    1492
    1493        private Collection<V> values;
    1494
    1495        @Override public Collection<V> values() {
    1496          Collection<V> result = values;
    1497          if (result == null) {
    1498            return values = new Values<K, V>(){
    1499              @Override Map<K, V> map() {
    1500                return ImprovedAbstractMap.this;
    1501              }
    1502            };
    1503          }
    1504          return result;
    1505        }
    1506
    1507        /**
    1508         * Returns {@code true} if this map contains no key-value mappings.
    1509         *
    1510         * <p>The implementation returns {@code entrySet().isEmpty()}.
    1511         *
    1512         * @return {@code true} if this map contains no key-value mappings
    1513         */
    1514        @Override public boolean isEmpty() {
    1515          return entrySet().isEmpty();
    1516        }
    1517      }
    1518
    1519      static final MapJoiner STANDARD_JOINER =
    1520          Collections2.STANDARD_JOINER.withKeyValueSeparator("=");
    1521
    1522      /**
    1523       * Delegates to {@link Map#get}. Returns {@code null} on {@code
    1524       * ClassCastException}.
    1525       */
    1526      static <V> V safeGet(Map<?, V> map, Object key) {
    1527        try {
    1528          return map.get(key);
    1529        } catch (ClassCastException e) {
    1530          return null;
    1531        }
    1532      }
    1533
    1534      /**
    1535       * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code
    1536       * ClassCastException}
    1537       */
    1538      static boolean safeContainsKey(Map<?, ?> map, Object key) {
    1539        try {
    1540          return map.containsKey(key);
    1541        } catch (ClassCastException e) {
    1542          return false;
    1543        }
    1544      }
    1545
    1546      /**
    1547       * Implements {@code Collection.contains} safely for forwarding collections of
    1548       * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
    1549       * wrapped using {@link #unmodifiableEntry} to protect against a possible
    1550       * nefarious equals method.
    1551       *
    1552       * <p>Note that {@code c} is the backing (delegate) collection, rather than
    1553       * the forwarding collection.
    1554       *
    1555       * @param c the delegate (unwrapped) collection of map entries
    1556       * @param o the object that might be contained in {@code c}
    1557       * @return {@code true} if {@code c} contains {@code o}
    1558       */
    1559      static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) {
    1560        if (!(o instanceof Entry)) {
    1561          return false;
    1562        }
    1563        return c.contains(unmodifiableEntry((Entry<?, ?>) o));
    1564      }
    1565
    1566      /**
    1567       * Implements {@code Collection.remove} safely for forwarding collections of
    1568       * map entries. If {@code o} is an instance of {@code Map.Entry}, it is
    1569       * wrapped using {@link #unmodifiableEntry} to protect against a possible
    1570       * nefarious equals method.
    1571       *
    1572       * <p>Note that {@code c} is backing (delegate) collection, rather than the
    1573       * forwarding collection.
    1574       *
    1575       * @param c the delegate (unwrapped) collection of map entries
    1576       * @param o the object to remove from {@code c}
    1577       * @return {@code true} if {@code c} was changed
    1578       */
    1579      static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) {
    1580        if (!(o instanceof Entry)) {
    1581          return false;
    1582        }
    1583        return c.remove(unmodifiableEntry((Entry<?, ?>) o));
    1584      }
    1585
    1586      /**
    1587       * An implementation of {@link Map#equals}.
    1588       */
    1589      static boolean equalsImpl(Map<?, ?> map, Object object) {
    1590        if (map == object) {
    1591          return true;
    1592        }
    1593        if (object instanceof Map) {
    1594          Map<?, ?> o = (Map<?, ?>) object;
    1595          return map.entrySet().equals(o.entrySet());
    1596        }
    1597        return false;
    1598      }
    1599
    1600      /**
    1601       * An implementation of {@link Map#hashCode}.
    1602       */
    1603      static int hashCodeImpl(Map<?, ?> map) {
    1604        return Sets.hashCodeImpl(map.entrySet());
    1605      }
    1606
    1607      /**
    1608       * An implementation of {@link Map#toString}.
    1609       */
    1610      static String toStringImpl(Map<?, ?> map) {
    1611        StringBuilder sb
    1612            = Collections2.newStringBuilderForCollection(map.size()).append('{');
    1613        STANDARD_JOINER.appendTo(sb, map);
    1614        return sb.append('}').toString();
    1615      }
    1616
    1617      /**
    1618       * An implementation of {@link Map#putAll}.
    1619       */
    1620      static <K, V> void putAllImpl(
    1621          Map<K, V> self, Map<? extends K, ? extends V> map) {
    1622        for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) {
    1623          self.put(entry.getKey(), entry.getValue());
    1624        }
    1625      }
    1626
    1627      /**
    1628       * An admittedly inefficient implementation of {@link Map#containsKey}.
    1629       */
    1630      static boolean containsKeyImpl(Map<?, ?> map, @Nullable Object key) {
    1631        for (Entry<?, ?> entry : map.entrySet()) {
    1632          if (Objects.equal(entry.getKey(), key)) {
    1633            return true;
    1634          }
    1635        }
    1636        return false;
    1637      }
    1638
    1639      /**
    1640       * An implementation of {@link Map#containsValue}.
    1641       */
    1642      static boolean containsValueImpl(Map<?, ?> map, @Nullable Object value) {
    1643        for (Entry<?, ?> entry : map.entrySet()) {
    1644          if (Objects.equal(entry.getValue(), value)) {
    1645            return true;
    1646          }
    1647        }
    1648        return false;
    1649      }
    1650
    1651      abstract static class KeySet<K, V> extends AbstractSet<K> {
    1652        abstract Map<K, V> map();
    1653
    1654        @Override public Iterator<K> iterator() {
    1655          return Iterators.transform(map().entrySet().iterator(),
    1656              new Function<Map.Entry<K, V>, K>() {
    1657                @Override public K apply(Entry<K, V> entry) {
    1658                  return entry.getKey();
    1659                }
    1660              });
    1661        }
    1662
    1663        @Override public int size() {
    1664          return map().size();
    1665        }
    1666
    1667        @Override public boolean isEmpty() {
    1668          return map().isEmpty();
    1669        }
    1670
    1671        @Override public boolean contains(Object o) {
    1672          return map().containsKey(o);
    1673        }
    1674
    1675        @Override public boolean remove(Object o) {
    1676          if (contains(o)) {
    1677            map().remove(o);
    1678            return true;
    1679          }
    1680          return false;
    1681        }
    1682
    1683        @Override
    1684        public boolean removeAll(Collection<?> c) {
    1685          // TODO(user): find out why this is necessary to make GWT tests pass.
    1686          return super.removeAll(checkNotNull(c));
    1687        }
    1688
    1689        @Override public void clear() {
    1690          map().clear();
    1691        }
    1692      }
    1693
    1694      abstract static class Values<K, V> extends AbstractCollection<V> {
    1695        abstract Map<K, V> map();
    1696
    1697        @Override public Iterator<V> iterator() {
    1698          return Iterators.transform(map().entrySet().iterator(),
    1699              new Function<Entry<K, V>, V>() {
    1700                @Override public V apply(Entry<K, V> entry) {
    1701                  return entry.getValue();
    1702                }
    1703              });
    1704        }
    1705
    1706        @Override public boolean remove(Object o) {
    1707          try {
    1708            return super.remove(o);
    1709          } catch (UnsupportedOperationException e) {
    1710            for (Entry<K, V> entry : map().entrySet()) {
    1711              if (Objects.equal(o, entry.getValue())) {
    1712                map().remove(entry.getKey());
    1713                return true;
    1714              }
    1715            }
    1716            return false;
    1717          }
    1718        }
    1719
    1720        @Override public boolean removeAll(Collection<?> c) {
    1721          try {
    1722            return super.removeAll(checkNotNull(c));
    1723          } catch (UnsupportedOperationException e) {
    1724            Set<K> toRemove = Sets.newHashSet();
    1725            for (Entry<K, V> entry : map().entrySet()) {
    1726              if (c.contains(entry.getValue())) {
    1727                toRemove.add(entry.getKey());
    1728              }
    1729            }
    1730            return map().keySet().removeAll(toRemove);
    1731          }
    1732        }
    1733
    1734        @Override public boolean retainAll(Collection<?> c) {
    1735          try {
    1736            return super.retainAll(checkNotNull(c));
    1737          } catch (UnsupportedOperationException e) {
    1738            Set<K> toRetain = Sets.newHashSet();
    1739            for (Entry<K, V> entry : map().entrySet()) {
    1740              if (c.contains(entry.getValue())) {
    1741                toRetain.add(entry.getKey());
    1742              }
    1743            }
    1744            return map().keySet().retainAll(toRetain);
    1745          }
    1746        }
    1747
    1748        @Override public int size() {
    1749          return map().size();
    1750        }
    1751
    1752        @Override public boolean isEmpty() {
    1753          return map().isEmpty();
    1754        }
    1755
    1756        @Override public boolean contains(@Nullable Object o) {
    1757          return map().containsValue(o);
    1758        }
    1759
    1760        @Override public void clear() {
    1761          map().clear();
    1762        }
    1763      }
    1764
    1765      abstract static class EntrySet<K, V> extends AbstractSet<Entry<K, V>> {
    1766        abstract Map<K, V> map();
    1767
    1768        @Override public int size() {
    1769          return map().size();
    1770        }
    1771
    1772        @Override public void clear() {
    1773          map().clear();
    1774        }
    1775
    1776        @Override public boolean contains(Object o) {
    1777          if (o instanceof Entry) {
    1778            Entry<?, ?> entry = (Entry<?, ?>) o;
    1779            Object key = entry.getKey();
    1780            V value = map().get(key);
    1781            return Objects.equal(value, entry.getValue())
    1782                && (value != null || map().containsKey(key));
    1783          }
    1784          return false;
    1785        }
    1786
    1787        @Override public boolean isEmpty() {
    1788          return map().isEmpty();
    1789        }
    1790
    1791        @Override public boolean remove(Object o) {
    1792          if (contains(o)) {
    1793            Entry<?, ?> entry = (Entry<?, ?>) o;
    1794            return map().keySet().remove(entry.getKey());
    1795          }
    1796          return false;
    1797        }
    1798
    1799        @Override public boolean removeAll(Collection<?> c) {
    1800          try {
    1801            return super.removeAll(checkNotNull(c));
    1802          } catch (UnsupportedOperationException e) {
    1803            // if the iterators don't support remove
    1804            boolean changed = true;
    1805            for (Object o : c) {
    1806              changed |= remove(o);
    1807            }
    1808            return changed;
    1809          }
    1810        }
    1811
    1812        @Override public boolean retainAll(Collection<?> c) {
    1813          try {
    1814            return super.retainAll(checkNotNull(c));
    1815          } catch (UnsupportedOperationException e) {
    1816            // if the iterators don't support remove
    1817            Set<Object> keys = Sets.newHashSetWithExpectedSize(c.size());
    1818            for (Object o : c) {
    1819              if (contains(o)) {
    1820                Entry<?, ?> entry = (Entry<?, ?>) o;
    1821                keys.add(entry.getKey());
    1822              }
    1823            }
    1824            return map().keySet().retainAll(keys);
    1825          }
    1826        }
    1827      }
    1828    }