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