11d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/* 21d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Copyright (C) 2010 The Guava Authors 31d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 41d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Licensed under the Apache License, Version 2.0 (the "License"); 51d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * you may not use this file except in compliance with the License. 61d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * You may obtain a copy of the License at 71d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 81d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * http://www.apache.org/licenses/LICENSE-2.0 91d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Unless required by applicable law or agreed to in writing, software 111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * distributed under the License is distributed on an "AS IS" BASIS, 121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * See the License for the specific language governing permissions and 141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * limitations under the License. 151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpackage com.google.common.collect; 181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport static com.google.common.base.Preconditions.checkNotNull; 201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Comparator; 221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map; 231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.Map.Entry; 241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport java.util.SortedMap; 251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport javax.annotation.Nullable; 271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.Beta; 291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtCompatible; 301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.annotations.GwtIncompatible; 311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Function; 321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Predicate; 331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.base.Predicates; 341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertimport com.google.common.collect.Maps.EntryTransformer; 351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert/** 371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Static utility methods pertaining to {@link SortedMap} instances. 381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @author Louis Wasserman 401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @since 8.0 411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @deprecated Use the identical methods in {@link Maps}. This class is 421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * scheduled for deletion from Guava in Guava release 12.0. 431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@Beta 451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@Deprecated 461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert@GwtCompatible 471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringertpublic final class SortedMaps { 481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private SortedMaps() {} 491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a view of a sorted map where each value is transformed by a 521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * function. All other properties of the map, such as iteration order, are 531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * left intact. For example, the code: <pre> {@code 541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * SortedMap<String, Integer> map = ImmutableSortedMap.of("a", 4, "b", 9); 561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Function<Integer, Double> sqrt = 571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * new Function<Integer, Double>() { 581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * public Double apply(Integer in) { 591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * return Math.sqrt((int) in); 601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * } 611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * }; 621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * SortedMap<String, Double> transformed = 631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Maps.transformSortedValues(map, sqrt); 641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * System.out.println(transformed);}</pre> 651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ... prints {@code {a=2.0, b=3.0}}. 671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Changes in the underlying map are reflected in this view. Conversely, 691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this view supports removal operations, and these are reflected in the 701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * underlying map. 711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>It's acceptable for the underlying map to contain null keys, and even 731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * null values provided that the function is capable of accepting null input. 741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * The transformed map might contain null values, if the function sometimes 751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * gives a null result. 761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned map is not thread-safe or serializable, even if the 781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * underlying map is. 791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The function is applied lazily, invoked when needed. This is necessary 811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * for the returned map to be a view, but it means that the function will be 821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * applied many times for bulk operations like {@link Map#containsValue} and 831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code Map.toString()}. For this to perform well, {@code function} should 841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * be fast. To avoid lazy evaluation when the returned map doesn't need to be 851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * a view, copy the returned map into a new map of your choosing. 861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @deprecated Use {@link Maps#transformValues(SortedMap, Function)} 881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Deprecated public static <K, V1, V2> SortedMap<K, V2> transformValues( 901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMap<K, V1> fromMap, final Function<? super V1, V2> function) { 911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Maps.transformValues(fromMap, function); 921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a view of a sorted map whose values are derived from the original 961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * sorted map's entries. In contrast to {@link #transformValues}, this 971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * method's entry-transformation logic may depend on the key as well as the 981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * value. 991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>All other properties of the transformed map, such as iteration order, 1011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * are left intact. For example, the code: <pre> {@code 1021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Map<String, Boolean> options = 1041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ImmutableSortedMap.of("verbose", true, "sort", false); 1051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * EntryTransformer<String, Boolean, String> flagPrefixer = 1061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * new EntryTransformer<String, Boolean, String>() { 1071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * public String transformEntry(String key, Boolean value) { 1081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * return value ? key : "yes" + key; 1091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * } 1101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * }; 1111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * SortedMap<String, String> transformed = 1121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * LabsMaps.transformSortedEntries(options, flagPrefixer); 1131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * System.out.println(transformed);}</pre> 1141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ... prints {@code {sort=yessort, verbose=verbose}}. 1161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Changes in the underlying map are reflected in this view. Conversely, 1181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * this view supports removal operations, and these are reflected in the 1191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * underlying map. 1201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>It's acceptable for the underlying map to contain null keys and null 1221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * values provided that the transformer is capable of accepting null inputs. 1231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * The transformed map might contain null values if the transformer sometimes 1241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * gives a null result. 1251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned map is not thread-safe or serializable, even if the 1271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * underlying map is. 1281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The transformer is applied lazily, invoked when needed. This is 1301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * necessary for the returned map to be a view, but it means that the 1311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * transformer will be applied many times for bulk operations like {@link 1321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Map#containsValue} and {@link Object#toString}. For this to perform well, 1331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code transformer} should be fast. To avoid lazy evaluation when the 1341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * returned map doesn't need to be a view, copy the returned map into a new 1351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * map of your choosing. 1361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Warning:</b> This method assumes that for any instance {@code k} of 1381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies 1391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * that {@code k2} is also of type {@code K}. Using an {@code 1401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * EntryTransformer} key type for which this may not hold, such as {@code 1411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * ArrayList}, may risk a {@code ClassCastException} when calling methods on 1421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the transformed map. 1431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @deprecated Use {@link Maps#transformEntries(SortedMap, EntryTransformer)} 1451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Deprecated public static <K, V1, V2> SortedMap<K, V2> transformEntries( 1471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert final SortedMap<K, V1> fromMap, 1481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert EntryTransformer<? super K, ? super V1, V2> transformer) { 1491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Maps.transformEntries(fromMap, transformer); 1501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Computes the difference between two sorted maps, using the comparator of 1541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the left map, or {@code Ordering.natural()} if the left map uses the 1551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * natural ordering of its elements. This difference is an immutable snapshot 1561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of the state of the maps at the time this method is called. It will never 1571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * change, even if the maps change at a later time. 1581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Since this method uses {@code TreeMap} instances internally, the keys of 1601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * the right map must all compare as distinct according to the comparator 1611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * of the left map. 1621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Note:</b>If you only need to know whether two sorted maps have the 1641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * same mappings, call {@code left.equals(right)} instead of this method. 1651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param left the map to treat as the "left" map for purposes of comparison 1671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @param right the map to treat as the "right" map for purposes of comparison 1681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @return the difference between the two maps 1691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * @deprecated Use {@link Maps#difference(SortedMap, Map)} 1701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Deprecated public static <K, V> SortedMapDifference<K, V> difference( 1721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMap<K, ? extends V> left, Map<? extends K, ? extends V> right) { 1731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return Maps.difference(left, right); 1741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns the specified comparator if not null; otherwise returns {@code 1781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Ordering.natural()}. This method is an abomination of generics; the only 1791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * purpose of this method is to contain the ugly type-casting in one place. 1801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 1811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @SuppressWarnings("unchecked") 1821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert static <E> Comparator<? super E> orNaturalOrder( 1831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Nullable Comparator<? super E> comparator) { 1841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (comparator != null) { // can't use ? : because of javac bug 5080917 1851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return comparator; 1861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (Comparator<E>) Ordering.natural(); 1881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 1891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 1901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 1911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a sorted map containing the mappings in {@code unfiltered} whose 1921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * keys satisfy a predicate. The returned map is a live view of {@code 1931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * unfiltered}; changes to one affect the other. 1941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 1951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code 1961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * values()} views have iterators that don't support {@code remove()}, but all 1971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * other methods are supported by the map and its views. When given a key that 1981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()} 1991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * methods throw an {@link IllegalArgumentException}. 2001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>When methods such as {@code removeAll()} and {@code clear()} are called 2021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * on the filtered map or its views, only mappings whose keys satisfy the 2031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * filter will be removed from the underlying map. 2041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned map isn't threadsafe or serializable, even if {@code 2061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * unfiltered} is. 2071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Many of the filtered map's methods, such as {@code size()}, 2091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * iterate across every key/value mapping in the underlying map and determine 2101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * which satisfy the filter. When a live view is <i>not</i> needed, it may be 2111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * faster to copy the filtered map and use the copy. 2121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with 2141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equals</i>, as documented at {@link Predicate#apply}. Do not provide a 2151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is 2161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * inconsistent with equals. 2171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("untested") 2191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <K, V> SortedMap<K, V> filterKeys( 2201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) { 2211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // TODO: Return a subclass of Maps.FilteredKeyMap for slightly better 2221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // performance. 2231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(keyPredicate); 2241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Predicate<Entry<K, V>> entryPredicate = new Predicate<Entry<K, V>>() { 2251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean apply(Entry<K, V> input) { 2271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return keyPredicate.apply(input.getKey()); 2281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 2301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return filterEntries(unfiltered, entryPredicate); 2311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a sorted map containing the mappings in {@code unfiltered} whose 2351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * values satisfy a predicate. The returned map is a live view of {@code 2361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * unfiltered}; changes to one affect the other. 2371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code 2391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * values()} views have iterators that don't support {@code remove()}, but all 2401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * other methods are supported by the map and its views. When given a value 2411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * that doesn't satisfy the predicate, the map's {@code put()}, {@code 2421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * putAll()}, and {@link Entry#setValue} methods throw an {@link 2431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * IllegalArgumentException}. 2441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>When methods such as {@code removeAll()} and {@code clear()} are called 2461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * on the filtered map or its views, only mappings whose values satisfy the 2471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * filter will be removed from the underlying map. 2481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned map isn't threadsafe or serializable, even if {@code 2501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * unfiltered} is. 2511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Many of the filtered map's methods, such as {@code size()}, 2531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * iterate across every key/value mapping in the underlying map and determine 2541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * which satisfy the filter. When a live view is <i>not</i> needed, it may be 2551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * faster to copy the filtered map and use the copy. 2561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with 2581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equals</i>, as documented at {@link Predicate#apply}. Do not provide a 2591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is 2601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * inconsistent with equals. 2611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 2621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("untested") 2631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <K, V> SortedMap<K, V> filterValues( 2641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) { 2651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(valuePredicate); 2661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Predicate<Entry<K, V>> entryPredicate = 2671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert new Predicate<Entry<K, V>>() { 2681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override 2691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public boolean apply(Entry<K, V> input) { 2701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return valuePredicate.apply(input.getValue()); 2711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert }; 2731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return filterEntries(unfiltered, entryPredicate); 2741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 2751d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 2761d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 2771d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Returns a sorted map containing the mappings in {@code unfiltered} that 2781d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * satisfy a predicate. The returned map is a live view of {@code unfiltered}; 2791d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * changes to one affect the other. 2801d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2811d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code 2821d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * values()} views have iterators that don't support {@code remove()}, but all 2831d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * other methods are supported by the map and its views. When given a 2841d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * key/value pair that doesn't satisfy the predicate, the map's {@code put()} 2851d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * and {@code putAll()} methods throw an {@link IllegalArgumentException}. 2861d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Similarly, the map's entries have a {@link Entry#setValue} method that 2871d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * throws an {@link IllegalArgumentException} when the existing key and the 2881d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * provided value don't satisfy the predicate. 2891d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2901d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>When methods such as {@code removeAll()} and {@code clear()} are called 2911d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * on the filtered map or its views, only mappings that satisfy the filter 2921d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * will be removed from the underlying map. 2931d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2941d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>The returned map isn't threadsafe or serializable, even if {@code 2951d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * unfiltered} is. 2961d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 2971d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p>Many of the filtered map's methods, such as {@code size()}, 2981d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * iterate across every key/value mapping in the underlying map and determine 2991d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * which satisfy the filter. When a live view is <i>not</i> needed, it may be 3001d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * faster to copy the filtered map and use the copy. 3011d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * 3021d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with 3031d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * equals</i>, as documented at {@link Predicate#apply}. 3041d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3051d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @GwtIncompatible("untested") 3061d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert public static <K, V> SortedMap<K, V> filterEntries( 3071d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMap<K, V> unfiltered, 3081d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Predicate<? super Entry<K, V>> entryPredicate) { 3091d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert checkNotNull(entryPredicate); 3101d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (unfiltered instanceof FilteredSortedMap) 3111d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert ? filterFiltered((FilteredSortedMap<K, V>) unfiltered, entryPredicate) 3121d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert : new FilteredSortedMap<K, V>(checkNotNull(unfiltered), entryPredicate); 3131d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3141d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3151d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert /** 3161d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when 3171d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert * filtering a filtered sorted map. 3181d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert */ 3191d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static <K, V> SortedMap<K, V> filterFiltered( 3201d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert FilteredSortedMap<K, V> map, 3211d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Predicate<? super Entry<K, V>> entryPredicate) { 3221d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Predicate<Entry<K, V>> predicate 3231d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert = Predicates.and(map.predicate, entryPredicate); 3241d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new FilteredSortedMap<K, V>(map.sortedMap(), predicate); 3251d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3261d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3271d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert private static class FilteredSortedMap<K, V> 3281d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert extends Maps.FilteredEntryMap<K, V> implements SortedMap<K, V> { 3291d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3301d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert FilteredSortedMap(SortedMap<K, V> unfiltered, 3311d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert Predicate<? super Entry<K, V>> entryPredicate) { 3321d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert super(unfiltered, entryPredicate); 3331d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3341d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3351d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMap<K, V> sortedMap() { 3361d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return (SortedMap<K, V>) unfiltered; 3371d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3381d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3391d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public Comparator<? super K> comparator() { 3401d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return sortedMap().comparator(); 3411d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3421d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3431d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public K firstKey() { 3441d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // correctly throws NoSuchElementException when filtered map is empty. 3451d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return keySet().iterator().next(); 3461d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3471d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3481d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public K lastKey() { 3491d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert SortedMap<K, V> headMap = sortedMap(); 3501d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert while (true) { 3511d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert // correctly throws NoSuchElementException when filtered map is empty. 3521d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert K key = headMap.lastKey(); 3531d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert if (apply(key, unfiltered.get(key))) { 3541d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return key; 3551d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3561d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert headMap = sortedMap().headMap(key); 3571d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3581d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3591d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3601d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public SortedMap<K, V> headMap(K toKey) { 3611d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new FilteredSortedMap<K, V>(sortedMap().headMap(toKey), predicate); 3621d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3631d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3641d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public SortedMap<K, V> subMap(K fromKey, K toKey) { 3651d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new FilteredSortedMap<K, V>( 3661d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortedMap().subMap(fromKey, toKey), predicate); 3671d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3681d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert 3691d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert @Override public SortedMap<K, V> tailMap(K fromKey) { 3701d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert return new FilteredSortedMap<K, V>( 3711d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert sortedMap().tailMap(fromKey), predicate); 3721d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3731d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert } 3741d580d0f6ee4f21eb309ba7b509d2c6d671c4044Bjorn Bringert} 375