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