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