    001    /*
    002     * Copyright (C) 2010 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.checkNotNull;
    020
    021    import com.google.common.annotations.Beta;
    022    import com.google.common.annotations.GwtCompatible;
    023    import com.google.common.annotations.GwtIncompatible;
    024    import com.google.common.base.Function;
    025    import com.google.common.base.Objects;
    026    import com.google.common.base.Predicate;
    027    import com.google.common.base.Predicates;
    028    import com.google.common.collect.MapDifference.ValueDifference;
    029    import com.google.common.collect.Maps.EntryTransformer;
    030    import com.google.common.collect.Maps.MapDifferenceImpl;
    031    import com.google.common.collect.Maps.TransformedEntriesMap;
    032    import com.google.common.collect.Maps.ValueDifferenceImpl;
    033
    034    import java.util.Collections;
    035    import java.util.Comparator;
    036    import java.util.Map;
    037    import java.util.Map.Entry;
    038    import java.util.SortedMap;
    039
    040    import javax.annotation.Nullable;
    041
    042    /**
    043     * Static utility methods pertaining to {@link SortedMap} instances.
    044     *
    045     * @author Louis Wasserman
    046     * @since 8.0
    047     */
    048    @Beta
    049    @GwtCompatible
    050    public final class SortedMaps {
    051      private SortedMaps() {}
    052
    053      /**
    054       * Returns a view of a sorted map where each value is transformed by a
    055       * function. All other properties of the map, such as iteration order, are
    056       * left intact. For example, the code: <pre>   {@code
    057       *
    058       *   SortedMap<String, Integer> map = ImmutableSortedMap.of("a", 4, "b", 9);
    059       *   Function<Integer, Double> sqrt =
    060       *       new Function<Integer, Double>() {
    061       *         public Double apply(Integer in) {
    062       *           return Math.sqrt((int) in);
    063       *         }
    064       *       };
    065       *   SortedMap<String, Double> transformed =
    066       *        Maps.transformSortedValues(map, sqrt);
    067       *   System.out.println(transformed);}</pre>
    068       *
    069       * ... prints {@code {a=2.0, b=3.0}}.
    070       *
    071       * <p>Changes in the underlying map are reflected in this view. Conversely,
    072       * this view supports removal operations, and these are reflected in the
    073       * underlying map.
    074       *
    075       * <p>It's acceptable for the underlying map to contain null keys, and even
    076       * null values provided that the function is capable of accepting null input.
    077       * The transformed map might contain null values, if the function sometimes
    078       * gives a null result.
    079       *
    080       * <p>The returned map is not thread-safe or serializable, even if the
    081       * underlying map is.
    082       *
    083       * <p>The function is applied lazily, invoked when needed. This is necessary
    084       * for the returned map to be a view, but it means that the function will be
    085       * applied many times for bulk operations like {@link Map#containsValue} and
    086       * {@code Map.toString()}. For this to perform well, {@code function} should
    087       * be fast. To avoid lazy evaluation when the returned map doesn't need to be
    088       * a view, copy the returned map into a new map of your choosing.
    089       */
    090      public static <K, V1, V2> SortedMap<K, V2> transformValues(
    091          SortedMap<K, V1> fromMap, final Function<? super V1, V2> function) {
    092        checkNotNull(function);
    093        EntryTransformer<K, V1, V2> transformer =
    094            new EntryTransformer<K, V1, V2>() {
    095              @Override
    096              public V2 transformEntry(K key, V1 value) {
    097                return function.apply(value);
    098              }
    099            };
    100        return transformEntries(fromMap, transformer);
    101      }
    102
    103      /**
    104       * Returns a view of a sorted map whose values are derived from the original
    105       * sorted map's entries. In contrast to {@link #transformValues}, this
    106       * method's entry-transformation logic may depend on the key as well as the
    107       * value.
    108       *
    109       * <p>All other properties of the transformed map, such as iteration order,
    110       * are left intact. For example, the code: <pre>   {@code
    111       *
    112       *   Map<String, Boolean> options =
    113       *       ImmutableSortedMap.of("verbose", true, "sort", false);
    114       *   EntryTransformer<String, Boolean, String> flagPrefixer =
    115       *       new EntryTransformer<String, Boolean, String>() {
    116       *         public String transformEntry(String key, Boolean value) {
    117       *           return value ? key : "yes" + key;
    118       *         }
    119       *       };
    120       *   SortedMap<String, String> transformed =
    121       *       LabsMaps.transformSortedEntries(options, flagPrefixer);
    122       *   System.out.println(transformed);}</pre>
    123       *
    124       * ... prints {@code {sort=yessort, verbose=verbose}}.
    125       *
    126       * <p>Changes in the underlying map are reflected in this view. Conversely,
    127       * this view supports removal operations, and these are reflected in the
    128       * underlying map.
    129       *
    130       * <p>It's acceptable for the underlying map to contain null keys and null
    131       * values provided that the transformer is capable of accepting null inputs.
    132       * The transformed map might contain null values if the transformer sometimes
    133       * gives a null result.
    134       *
    135       * <p>The returned map is not thread-safe or serializable, even if the
    136       * underlying map is.
    137       *
    138       * <p>The transformer is applied lazily, invoked when needed. This is
    139       * necessary for the returned map to be a view, but it means that the
    140       * transformer will be applied many times for bulk operations like {@link
    141       * Map#containsValue} and {@link Object#toString}. For this to perform well,
    142       * {@code transformer} should be fast. To avoid lazy evaluation when the
    143       * returned map doesn't need to be a view, copy the returned map into a new
    144       * map of your choosing.
    145       *
    146       * <p><b>Warning:</b> This method assumes that for any instance {@code k} of
    147       * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies
    148       * that {@code k2} is also of type {@code K}. Using an {@code
    149       * EntryTransformer} key type for which this may not hold, such as {@code
    150       * ArrayList}, may risk a {@code ClassCastException} when calling methods on
    151       * the transformed map.
    152       */
    153      public static <K, V1, V2> SortedMap<K, V2> transformEntries(
    154          final SortedMap<K, V1> fromMap,
    155          EntryTransformer<? super K, ? super V1, V2> transformer) {
    156        return new TransformedEntriesSortedMap<K, V1, V2>(fromMap, transformer);
    157      }
    158
    159      static class TransformedEntriesSortedMap<K, V1, V2>
    160          extends TransformedEntriesMap<K, V1, V2> implements SortedMap<K, V2> {
    161
    162        protected SortedMap<K, V1> fromMap() {
    163          return (SortedMap<K, V1>) fromMap;
    164        }
    165
    166        TransformedEntriesSortedMap(SortedMap<K, V1> fromMap,
    167            EntryTransformer<? super K, ? super V1, V2> transformer) {
    168          super(fromMap, transformer);
    169        }
    170
    171        @Override public Comparator<? super K> comparator() {
    172          return fromMap().comparator();
    173        }
    174
    175        @Override public K firstKey() {
    176          return fromMap().firstKey();
    177        }
    178
    179        @Override public SortedMap<K, V2> headMap(K toKey) {
    180          return transformEntries(fromMap().headMap(toKey), transformer);
    181        }
    182
    183        @Override public K lastKey() {
    184          return fromMap().lastKey();
    185        }
    186
    187        @Override public SortedMap<K, V2> subMap(K fromKey, K toKey) {
    188          return transformEntries(
    189              fromMap().subMap(fromKey, toKey), transformer);
    190        }
    191
    192        @Override public SortedMap<K, V2> tailMap(K fromKey) {
    193          return transformEntries(fromMap().tailMap(fromKey), transformer);
    194        }
    195
    196      }
    197
    198      /**
    199       * Computes the difference between two sorted maps, using the comparator of
    200       * the left map, or {@code Ordering.natural()} if the left map uses the
    201       * natural ordering of its elements. This difference is an immutable snapshot
    202       * of the state of the maps at the time this method is called. It will never
    203       * change, even if the maps change at a later time.
    204       *
    205       * <p>Since this method uses {@code TreeMap} instances internally, the keys of
    206       * the right map must all compare as distinct according to the comparator
    207       * of the left map.
    208       *
    209       * <p><b>Note:</b>If you only need to know whether two sorted maps have the
    210       * same mappings, call {@code left.equals(right)} instead of this method.
    211       *
    212       * @param left the map to treat as the "left" map for purposes of comparison
    213       * @param right the map to treat as the "right" map for purposes of comparison
    214       * @return the difference between the two maps
    215       */
    216      public static <K, V> SortedMapDifference<K, V> difference(
    217          SortedMap<K, ? extends V> left, Map<? extends K, ? extends V> right) {
    218        Comparator<? super K> comparator = orNaturalOrder(left.comparator());
    219        SortedMap<K, V> onlyOnLeft = Maps.newTreeMap(comparator);
    220        SortedMap<K, V> onlyOnRight = Maps.newTreeMap(comparator);
    221        onlyOnRight.putAll(right); // will whittle it down
    222        SortedMap<K, V> onBoth = Maps.newTreeMap(comparator);
    223        SortedMap<K, MapDifference.ValueDifference<V>> differences =
    224            Maps.newTreeMap(comparator);
    225        boolean eq = true;
    226
    227        for (Entry<? extends K, ? extends V> entry : left.entrySet()) {
    228          K leftKey = entry.getKey();
    229          V leftValue = entry.getValue();
    230          if (right.containsKey(leftKey)) {
    231            V rightValue = onlyOnRight.remove(leftKey);
    232            if (Objects.equal(leftValue, rightValue)) {
    233              onBoth.put(leftKey, leftValue);
    234            } else {
    235              eq = false;
    236              differences.put(
    237                  leftKey, ValueDifferenceImpl.create(leftValue, rightValue));
    238            }
    239          } else {
    240            eq = false;
    241            onlyOnLeft.put(leftKey, leftValue);
    242          }
    243        }
    244
    245        boolean areEqual = eq && onlyOnRight.isEmpty();
    246        return sortedMapDifference(
    247            areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
    248      }
    249
    250      private static <K, V> SortedMapDifference<K, V> sortedMapDifference(
    251          boolean areEqual, SortedMap<K, V> onlyOnLeft, SortedMap<K, V> onlyOnRight,
    252          SortedMap<K, V> onBoth, SortedMap<K, ValueDifference<V>> differences) {
    253        return new SortedMapDifferenceImpl<K, V>(areEqual,
    254            Collections.unmodifiableSortedMap(onlyOnLeft),
    255            Collections.unmodifiableSortedMap(onlyOnRight),
    256            Collections.unmodifiableSortedMap(onBoth),
    257            Collections.unmodifiableSortedMap(differences));
    258      }
    259
    260      static class SortedMapDifferenceImpl<K, V> extends MapDifferenceImpl<K, V>
    261          implements SortedMapDifference<K, V> {
    262        SortedMapDifferenceImpl(boolean areEqual, SortedMap<K, V> onlyOnLeft,
    263            SortedMap<K, V> onlyOnRight, SortedMap<K, V> onBoth,
    264            SortedMap<K, ValueDifference<V>> differences) {
    265          super(areEqual, onlyOnLeft, onlyOnRight, onBoth, differences);
    266        }
    267
    268        @Override public SortedMap<K, ValueDifference<V>> entriesDiffering() {
    269          return (SortedMap<K, ValueDifference<V>>) super.entriesDiffering();
    270        }
    271
    272        @Override public SortedMap<K, V> entriesInCommon() {
    273          return (SortedMap<K, V>) super.entriesInCommon();
    274        }
    275
    276        @Override public SortedMap<K, V> entriesOnlyOnLeft() {
    277          return (SortedMap<K, V>) super.entriesOnlyOnLeft();
    278        }
    279
    280        @Override public SortedMap<K, V> entriesOnlyOnRight() {
    281          return (SortedMap<K, V>) super.entriesOnlyOnRight();
    282        }
    283      }
    284
    285      /**
    286       * Returns the specified comparator if not null; otherwise returns {@code
    287       * Ordering.natural()}. This method is an abomination of generics; the only
    288       * purpose of this method is to contain the ugly type-casting in one place.
    289       */
    290      @SuppressWarnings("unchecked")
    291      static <E> Comparator<? super E> orNaturalOrder(
    292          @Nullable Comparator<? super E> comparator) {
    293        if (comparator != null) { // can't use ? : because of javac bug 5080917
    294          return comparator;
    295        }
    296        return (Comparator<E>) Ordering.natural();
    297      }
    298
    299      /**
    300       * Returns a sorted map containing the mappings in {@code unfiltered} whose
    301       * keys satisfy a predicate. The returned map is a live view of {@code
    302       * unfiltered}; changes to one affect the other.
    303       *
    304       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
    305       * values()} views have iterators that don't support {@code remove()}, but all
    306       * other methods are supported by the map and its views. When given a key that
    307       * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()}
    308       * methods throw an {@link IllegalArgumentException}.
    309       *
    310       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
    311       * on the filtered map or its views, only mappings whose keys satisfy the
    312       * filter will be removed from the underlying map.
    313       *
    314       * <p>The returned map isn't threadsafe or serializable, even if {@code
    315       * unfiltered} is.
    316       *
    317       * <p>Many of the filtered map's methods, such as {@code size()},
    318       * iterate across every key/value mapping in the underlying map and determine
    319       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
    320       * faster to copy the filtered map and use the copy.
    321       *
    322       * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with
    323       * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
    324       * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
    325       * inconsistent with equals.
    326       */
    327      @GwtIncompatible("untested")
    328      public static <K, V> SortedMap<K, V> filterKeys(
    329          SortedMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) {
    330        // TODO: Return a subclass of Maps.FilteredKeyMap for slightly better
    331        // performance.
    332        checkNotNull(keyPredicate);
    333        Predicate<Entry<K, V>> entryPredicate = new Predicate<Entry<K, V>>() {
    334          @Override
    335          public boolean apply(Entry<K, V> input) {
    336            return keyPredicate.apply(input.getKey());
    337          }
    338        };
    339        return filterEntries(unfiltered, entryPredicate);
    340      }
    341
    342      /**
    343       * Returns a sorted map containing the mappings in {@code unfiltered} whose
    344       * values satisfy a predicate. The returned map is a live view of {@code
    345       * unfiltered}; changes to one affect the other.
    346       *
    347       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
    348       * values()} views have iterators that don't support {@code remove()}, but all
    349       * other methods are supported by the map and its views. When given a value
    350       * that doesn't satisfy the predicate, the map's {@code put()}, {@code
    351       * putAll()}, and {@link Entry#setValue} methods throw an {@link
    352       * IllegalArgumentException}.
    353       *
    354       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
    355       * on the filtered map or its views, only mappings whose values satisfy the
    356       * filter will be removed from the underlying map.
    357       *
    358       * <p>The returned map isn't threadsafe or serializable, even if {@code
    359       * unfiltered} is.
    360       *
    361       * <p>Many of the filtered map's methods, such as {@code size()},
    362       * iterate across every key/value mapping in the underlying map and determine
    363       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
    364       * faster to copy the filtered map and use the copy.
    365       *
    366       * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with
    367       * equals</i>, as documented at {@link Predicate#apply}. Do not provide a
    368       * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is
    369       * inconsistent with equals.
    370       */
    371      @GwtIncompatible("untested")
    372      public static <K, V> SortedMap<K, V> filterValues(
    373          SortedMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) {
    374        checkNotNull(valuePredicate);
    375        Predicate<Entry<K, V>> entryPredicate =
    376            new Predicate<Entry<K, V>>() {
    377              @Override
    378              public boolean apply(Entry<K, V> input) {
    379                return valuePredicate.apply(input.getValue());
    380              }
    381            };
    382        return filterEntries(unfiltered, entryPredicate);
    383      }
    384
    385      /**
    386       * Returns a sorted map containing the mappings in {@code unfiltered} that
    387       * satisfy a predicate. The returned map is a live view of {@code unfiltered};
    388       * changes to one affect the other.
    389       *
    390       * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code
    391       * values()} views have iterators that don't support {@code remove()}, but all
    392       * other methods are supported by the map and its views. When given a
    393       * key/value pair that doesn't satisfy the predicate, the map's {@code put()}
    394       * and {@code putAll()} methods throw an {@link IllegalArgumentException}.
    395       * Similarly, the map's entries have a {@link Entry#setValue} method that
    396       * throws an {@link IllegalArgumentException} when the existing key and the
    397       * provided value don't satisfy the predicate.
    398       *
    399       * <p>When methods such as {@code removeAll()} and {@code clear()} are called
    400       * on the filtered map or its views, only mappings that satisfy the filter
    401       * will be removed from the underlying map.
    402       *
    403       * <p>The returned map isn't threadsafe or serializable, even if {@code
    404       * unfiltered} is.
    405       *
    406       * <p>Many of the filtered map's methods, such as {@code size()},
    407       * iterate across every key/value mapping in the underlying map and determine
    408       * which satisfy the filter. When a live view is <i>not</i> needed, it may be
    409       * faster to copy the filtered map and use the copy.
    410       *
    411       * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with
    412       * equals</i>, as documented at {@link Predicate#apply}.
    413       */
    414      @GwtIncompatible("untested")
    415      public static <K, V> SortedMap<K, V> filterEntries(
    416          SortedMap<K, V> unfiltered,
    417          Predicate<? super Entry<K, V>> entryPredicate) {
    418        checkNotNull(entryPredicate);
    419        return (unfiltered instanceof FilteredSortedMap)
    420            ? filterFiltered((FilteredSortedMap<K, V>) unfiltered, entryPredicate)
    421            : new FilteredSortedMap<K, V>(checkNotNull(unfiltered), entryPredicate);
    422      }
    423
    424      /**
    425       * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when
    426       * filtering a filtered sorted map.
    427       */
    428      private static <K, V> SortedMap<K, V> filterFiltered(
    429          FilteredSortedMap<K, V> map,
    430          Predicate<? super Entry<K, V>> entryPredicate) {
    431        Predicate<Entry<K, V>> predicate
    432            = Predicates.and(map.predicate, entryPredicate);
    433        return new FilteredSortedMap<K, V>(map.sortedMap(), predicate);
    434      }
    435
    436      private static class FilteredSortedMap<K, V>
    437          extends Maps.FilteredEntryMap<K, V> implements SortedMap<K, V> {
    438
    439        FilteredSortedMap(SortedMap<K, V> unfiltered,
    440            Predicate<? super Entry<K, V>> entryPredicate) {
    441          super(unfiltered, entryPredicate);
    442        }
    443
    444        SortedMap<K, V> sortedMap() {
    445          return (SortedMap<K, V>) unfiltered;
    446        }
    447
    448        @Override public Comparator<? super K> comparator() {
    449          return sortedMap().comparator();
    450        }
    451
    452        @Override public K firstKey() {
    453          // correctly throws NoSuchElementException when filtered map is empty.
    454          return keySet().iterator().next();
    455        }
    456
    457        @Override public K lastKey() {
    458          SortedMap<K, V> headMap = sortedMap();
    459          while (true) {
    460            // correctly throws NoSuchElementException when filtered map is empty.
    461            K key = headMap.lastKey();
    462            if (apply(key, unfiltered.get(key))) {
    463              return key;
    464            }
    465            headMap = sortedMap().headMap(key);
    466          }
    467        }
    468
    469        @Override public SortedMap<K, V> headMap(K toKey) {
    470          return new FilteredSortedMap<K, V>(sortedMap().headMap(toKey), predicate);
    471        }
    472
    473        @Override public SortedMap<K, V> subMap(K fromKey, K toKey) {
    474          return new FilteredSortedMap<K, V>(
    475              sortedMap().subMap(fromKey, toKey), predicate);
    476        }
    477
    478        @Override public SortedMap<K, V> tailMap(K fromKey) {
    479          return new FilteredSortedMap<K, V>(
    480              sortedMap().tailMap(fromKey), predicate);
    481        }
    482      }
    483    }