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