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 017 package com.google.common.collect; 018 019 import static com.google.common.base.Preconditions.checkArgument; 020 import static com.google.common.base.Preconditions.checkNotNull; 021 022 import com.google.common.annotations.Beta; 023 import com.google.common.annotations.GwtCompatible; 024 import com.google.common.annotations.GwtIncompatible; 025 import com.google.common.base.Equivalence; 026 import com.google.common.base.Function; 027 import com.google.common.base.Joiner.MapJoiner; 028 import com.google.common.base.Objects; 029 import com.google.common.base.Preconditions; 030 import com.google.common.base.Predicate; 031 import com.google.common.base.Predicates; 032 import com.google.common.collect.MapDifference.ValueDifference; 033 import com.google.common.primitives.Ints; 034 035 import java.io.Serializable; 036 import java.util.AbstractCollection; 037 import java.util.AbstractMap; 038 import java.util.Collection; 039 import java.util.Collections; 040 import java.util.Comparator; 041 import java.util.EnumMap; 042 import java.util.Enumeration; 043 import java.util.HashMap; 044 import java.util.IdentityHashMap; 045 import java.util.Iterator; 046 import java.util.LinkedHashMap; 047 import java.util.Map; 048 import java.util.Map.Entry; 049 import java.util.NavigableMap; 050 import java.util.NavigableSet; 051 import java.util.Properties; 052 import java.util.Set; 053 import java.util.SortedMap; 054 import java.util.SortedSet; 055 import java.util.TreeMap; 056 import java.util.concurrent.ConcurrentMap; 057 058 import javax.annotation.Nullable; 059 060 /** 061 * Static utility methods pertaining to {@link Map} instances (including instances of 062 * {@link SortedMap}, {@link BiMap}, etc.). Also see this class's counterparts 063 * {@link Lists}, {@link Sets} and {@link Queues}. 064 * 065 * <p>See the Guava User Guide article on <a href= 066 * "http://code.google.com/p/guava-libraries/wiki/CollectionUtilitiesExplained#Maps"> 067 * {@code Maps}</a>. 068 * 069 * @author Kevin Bourrillion 070 * @author Mike Bostock 071 * @author Isaac Shum 072 * @author Louis Wasserman 073 * @since 2.0 (imported from Google Collections Library) 074 */ 075 @GwtCompatible(emulated = true) 076 public final class Maps { 077 private Maps() {} 078 079 /** 080 * Creates a <i>mutable</i>, empty {@code HashMap} instance. 081 * 082 * <p><b>Note:</b> if mutability is not required, use {@link 083 * ImmutableMap#of()} instead. 084 * 085 * <p><b>Note:</b> if {@code K} is an {@code enum} type, use {@link 086 * #newEnumMap} instead. 087 * 088 * @return a new, empty {@code HashMap} 089 */ 090 public static <K, V> HashMap<K, V> newHashMap() { 091 return new HashMap<K, V>(); 092 } 093 094 /** 095 * Creates a {@code HashMap} instance, with a high enough "initial capacity" 096 * that it <i>should</i> hold {@code expectedSize} elements without growth. 097 * This behavior cannot be broadly guaranteed, but it is observed to be true 098 * for OpenJDK 1.6. It also can't be guaranteed that the method isn't 099 * inadvertently <i>oversizing</i> the returned map. 100 * 101 * @param expectedSize the number of elements you expect to add to the 102 * returned map 103 * @return a new, empty {@code HashMap} with enough capacity to hold {@code 104 * expectedSize} elements without resizing 105 * @throws IllegalArgumentException if {@code expectedSize} is negative 106 */ 107 public static <K, V> HashMap<K, V> newHashMapWithExpectedSize( 108 int expectedSize) { 109 return new HashMap<K, V>(capacity(expectedSize)); 110 } 111 112 /** 113 * Returns a capacity that is sufficient to keep the map from being resized as 114 * long as it grows no larger than expectedSize and the load factor is >= its 115 * default (0.75). 116 */ 117 static int capacity(int expectedSize) { 118 if (expectedSize < 3) { 119 checkArgument(expectedSize >= 0); 120 return expectedSize + 1; 121 } 122 if (expectedSize < Ints.MAX_POWER_OF_TWO) { 123 return expectedSize + expectedSize / 3; 124 } 125 return Integer.MAX_VALUE; // any large value 126 } 127 128 /** 129 * Creates a <i>mutable</i> {@code HashMap} instance with the same mappings as 130 * the specified map. 131 * 132 * <p><b>Note:</b> if mutability is not required, use {@link 133 * ImmutableMap#copyOf(Map)} instead. 134 * 135 * <p><b>Note:</b> if {@code K} is an {@link Enum} type, use {@link 136 * #newEnumMap} instead. 137 * 138 * @param map the mappings to be placed in the new map 139 * @return a new {@code HashMap} initialized with the mappings from {@code 140 * map} 141 */ 142 public static <K, V> HashMap<K, V> newHashMap( 143 Map<? extends K, ? extends V> map) { 144 return new HashMap<K, V>(map); 145 } 146 147 /** 148 * Creates a <i>mutable</i>, empty, insertion-ordered {@code LinkedHashMap} 149 * instance. 150 * 151 * <p><b>Note:</b> if mutability is not required, use {@link 152 * ImmutableMap#of()} instead. 153 * 154 * @return a new, empty {@code LinkedHashMap} 155 */ 156 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap() { 157 return new LinkedHashMap<K, V>(); 158 } 159 160 /** 161 * Creates a <i>mutable</i>, insertion-ordered {@code LinkedHashMap} instance 162 * with the same mappings as the specified map. 163 * 164 * <p><b>Note:</b> if mutability is not required, use {@link 165 * ImmutableMap#copyOf(Map)} instead. 166 * 167 * @param map the mappings to be placed in the new map 168 * @return a new, {@code LinkedHashMap} initialized with the mappings from 169 * {@code map} 170 */ 171 public static <K, V> LinkedHashMap<K, V> newLinkedHashMap( 172 Map<? extends K, ? extends V> map) { 173 return new LinkedHashMap<K, V>(map); 174 } 175 176 /** 177 * Returns a general-purpose instance of {@code ConcurrentMap}, which supports 178 * all optional operations of the ConcurrentMap interface. It does not permit 179 * null keys or values. It is serializable. 180 * 181 * <p>This is currently accomplished by calling {@link MapMaker#makeMap()}. 182 * 183 * <p>It is preferable to use {@code MapMaker} directly (rather than through 184 * this method), as it presents numerous useful configuration options, 185 * such as the concurrency level, load factor, key/value reference types, 186 * and value computation. 187 * 188 * @return a new, empty {@code ConcurrentMap} 189 * @since 3.0 190 */ 191 public static <K, V> ConcurrentMap<K, V> newConcurrentMap() { 192 return new MapMaker().<K, V>makeMap(); 193 } 194 195 /** 196 * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the natural 197 * ordering of its elements. 198 * 199 * <p><b>Note:</b> if mutability is not required, use {@link 200 * ImmutableSortedMap#of()} instead. 201 * 202 * @return a new, empty {@code TreeMap} 203 */ 204 public static <K extends Comparable, V> TreeMap<K, V> newTreeMap() { 205 return new TreeMap<K, V>(); 206 } 207 208 /** 209 * Creates a <i>mutable</i> {@code TreeMap} instance with the same mappings as 210 * the specified map and using the same ordering as the specified map. 211 * 212 * <p><b>Note:</b> if mutability is not required, use {@link 213 * ImmutableSortedMap#copyOfSorted(SortedMap)} instead. 214 * 215 * @param map the sorted map whose mappings are to be placed in the new map 216 * and whose comparator is to be used to sort the new map 217 * @return a new {@code TreeMap} initialized with the mappings from {@code 218 * map} and using the comparator of {@code map} 219 */ 220 public static <K, V> TreeMap<K, V> newTreeMap(SortedMap<K, ? extends V> map) { 221 return new TreeMap<K, V>(map); 222 } 223 224 /** 225 * Creates a <i>mutable</i>, empty {@code TreeMap} instance using the given 226 * comparator. 227 * 228 * <p><b>Note:</b> if mutability is not required, use {@code 229 * ImmutableSortedMap.orderedBy(comparator).build()} instead. 230 * 231 * @param comparator the comparator to sort the keys with 232 * @return a new, empty {@code TreeMap} 233 */ 234 public static <C, K extends C, V> TreeMap<K, V> newTreeMap( 235 @Nullable Comparator<C> comparator) { 236 // Ideally, the extra type parameter "C" shouldn't be necessary. It is a 237 // work-around of a compiler type inference quirk that prevents the 238 // following code from being compiled: 239 // Comparator<Class<?>> comparator = null; 240 // Map<Class<? extends Throwable>, String> map = newTreeMap(comparator); 241 return new TreeMap<K, V>(comparator); 242 } 243 244 /** 245 * Creates an {@code EnumMap} instance. 246 * 247 * @param type the key type for this map 248 * @return a new, empty {@code EnumMap} 249 */ 250 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap(Class<K> type) { 251 return new EnumMap<K, V>(checkNotNull(type)); 252 } 253 254 /** 255 * Creates an {@code EnumMap} with the same mappings as the specified map. 256 * 257 * @param map the map from which to initialize this {@code EnumMap} 258 * @return a new {@code EnumMap} initialized with the mappings from {@code 259 * map} 260 * @throws IllegalArgumentException if {@code m} is not an {@code EnumMap} 261 * instance and contains no mappings 262 */ 263 public static <K extends Enum<K>, V> EnumMap<K, V> newEnumMap( 264 Map<K, ? extends V> map) { 265 return new EnumMap<K, V>(map); 266 } 267 268 /** 269 * Creates an {@code IdentityHashMap} instance. 270 * 271 * @return a new, empty {@code IdentityHashMap} 272 */ 273 public static <K, V> IdentityHashMap<K, V> newIdentityHashMap() { 274 return new IdentityHashMap<K, V>(); 275 } 276 277 /** 278 * Computes the difference between two maps. This difference is an immutable 279 * snapshot of the state of the maps at the time this method is called. It 280 * will never change, even if the maps change at a later time. 281 * 282 * <p>Since this method uses {@code HashMap} instances internally, the keys of 283 * the supplied maps must be well-behaved with respect to 284 * {@link Object#equals} and {@link Object#hashCode}. 285 * 286 * <p><b>Note:</b>If you only need to know whether two maps have the same 287 * mappings, call {@code left.equals(right)} instead of this method. 288 * 289 * @param left the map to treat as the "left" map for purposes of comparison 290 * @param right the map to treat as the "right" map for purposes of comparison 291 * @return the difference between the two maps 292 */ 293 @SuppressWarnings("unchecked") 294 public static <K, V> MapDifference<K, V> difference( 295 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right) { 296 if (left instanceof SortedMap) { 297 SortedMap<K, ? extends V> sortedLeft = (SortedMap<K, ? extends V>) left; 298 SortedMapDifference<K, V> result = difference(sortedLeft, right); 299 return result; 300 } 301 return difference(left, right, Equivalence.equals()); 302 } 303 304 /** 305 * Computes the difference between two maps. This difference is an immutable 306 * snapshot of the state of the maps at the time this method is called. It 307 * will never change, even if the maps change at a later time. 308 * 309 * <p>Values are compared using a provided equivalence, in the case of 310 * equality, the value on the 'left' is returned in the difference. 311 * 312 * <p>Since this method uses {@code HashMap} instances internally, the keys of 313 * the supplied maps must be well-behaved with respect to 314 * {@link Object#equals} and {@link Object#hashCode}. 315 * 316 * @param left the map to treat as the "left" map for purposes of comparison 317 * @param right the map to treat as the "right" map for purposes of comparison 318 * @param valueEquivalence the equivalence relationship to use to compare 319 * values 320 * @return the difference between the two maps 321 * @since 10.0 322 */ 323 @Beta 324 public static <K, V> MapDifference<K, V> difference( 325 Map<? extends K, ? extends V> left, Map<? extends K, ? extends V> right, 326 Equivalence<? super V> valueEquivalence) { 327 Preconditions.checkNotNull(valueEquivalence); 328 329 Map<K, V> onlyOnLeft = newHashMap(); 330 Map<K, V> onlyOnRight = new HashMap<K, V>(right); // will whittle it down 331 Map<K, V> onBoth = newHashMap(); 332 Map<K, MapDifference.ValueDifference<V>> differences = newHashMap(); 333 boolean eq = true; 334 335 for (Entry<? extends K, ? extends V> entry : left.entrySet()) { 336 K leftKey = entry.getKey(); 337 V leftValue = entry.getValue(); 338 if (right.containsKey(leftKey)) { 339 V rightValue = onlyOnRight.remove(leftKey); 340 if (valueEquivalence.equivalent(leftValue, rightValue)) { 341 onBoth.put(leftKey, leftValue); 342 } else { 343 eq = false; 344 differences.put( 345 leftKey, ValueDifferenceImpl.create(leftValue, rightValue)); 346 } 347 } else { 348 eq = false; 349 onlyOnLeft.put(leftKey, leftValue); 350 } 351 } 352 353 boolean areEqual = eq && onlyOnRight.isEmpty(); 354 return mapDifference( 355 areEqual, onlyOnLeft, onlyOnRight, onBoth, differences); 356 } 357 358 private static <K, V> MapDifference<K, V> mapDifference(boolean areEqual, 359 Map<K, V> onlyOnLeft, Map<K, V> onlyOnRight, Map<K, V> onBoth, 360 Map<K, ValueDifference<V>> differences) { 361 return new MapDifferenceImpl<K, V>(areEqual, 362 Collections.unmodifiableMap(onlyOnLeft), 363 Collections.unmodifiableMap(onlyOnRight), 364 Collections.unmodifiableMap(onBoth), 365 Collections.unmodifiableMap(differences)); 366 } 367 368 static class MapDifferenceImpl<K, V> implements MapDifference<K, V> { 369 final boolean areEqual; 370 final Map<K, V> onlyOnLeft; 371 final Map<K, V> onlyOnRight; 372 final Map<K, V> onBoth; 373 final Map<K, ValueDifference<V>> differences; 374 375 MapDifferenceImpl(boolean areEqual, Map<K, V> onlyOnLeft, 376 Map<K, V> onlyOnRight, Map<K, V> onBoth, 377 Map<K, ValueDifference<V>> differences) { 378 this.areEqual = areEqual; 379 this.onlyOnLeft = onlyOnLeft; 380 this.onlyOnRight = onlyOnRight; 381 this.onBoth = onBoth; 382 this.differences = differences; 383 } 384 385 @Override 386 public boolean areEqual() { 387 return areEqual; 388 } 389 390 @Override 391 public Map<K, V> entriesOnlyOnLeft() { 392 return onlyOnLeft; 393 } 394 395 @Override 396 public Map<K, V> entriesOnlyOnRight() { 397 return onlyOnRight; 398 } 399 400 @Override 401 public Map<K, V> entriesInCommon() { 402 return onBoth; 403 } 404 405 @Override 406 public Map<K, ValueDifference<V>> entriesDiffering() { 407 return differences; 408 } 409 410 @Override public boolean equals(Object object) { 411 if (object == this) { 412 return true; 413 } 414 if (object instanceof MapDifference) { 415 MapDifference<?, ?> other = (MapDifference<?, ?>) object; 416 return entriesOnlyOnLeft().equals(other.entriesOnlyOnLeft()) 417 && entriesOnlyOnRight().equals(other.entriesOnlyOnRight()) 418 && entriesInCommon().equals(other.entriesInCommon()) 419 && entriesDiffering().equals(other.entriesDiffering()); 420 } 421 return false; 422 } 423 424 @Override public int hashCode() { 425 return Objects.hashCode(entriesOnlyOnLeft(), entriesOnlyOnRight(), 426 entriesInCommon(), entriesDiffering()); 427 } 428 429 @Override public String toString() { 430 if (areEqual) { 431 return "equal"; 432 } 433 434 StringBuilder result = new StringBuilder("not equal"); 435 if (!onlyOnLeft.isEmpty()) { 436 result.append(": only on left=").append(onlyOnLeft); 437 } 438 if (!onlyOnRight.isEmpty()) { 439 result.append(": only on right=").append(onlyOnRight); 440 } 441 if (!differences.isEmpty()) { 442 result.append(": value differences=").append(differences); 443 } 444 return result.toString(); 445 } 446 } 447 448 static class ValueDifferenceImpl<V> 449 implements MapDifference.ValueDifference<V> { 450 private final V left; 451 private final V right; 452 453 static <V> ValueDifference<V> create(@Nullable V left, @Nullable V right) { 454 return new ValueDifferenceImpl<V>(left, right); 455 } 456 457 private ValueDifferenceImpl(@Nullable V left, @Nullable V right) { 458 this.left = left; 459 this.right = right; 460 } 461 462 @Override 463 public V leftValue() { 464 return left; 465 } 466 467 @Override 468 public V rightValue() { 469 return right; 470 } 471 472 @Override public boolean equals(@Nullable Object object) { 473 if (object instanceof MapDifference.ValueDifference) { 474 MapDifference.ValueDifference<?> that = 475 (MapDifference.ValueDifference<?>) object; 476 return Objects.equal(this.left, that.leftValue()) 477 && Objects.equal(this.right, that.rightValue()); 478 } 479 return false; 480 } 481 482 @Override public int hashCode() { 483 return Objects.hashCode(left, right); 484 } 485 486 @Override public String toString() { 487 return "(" + left + ", " + right + ")"; 488 } 489 } 490 491 /** 492 * Computes the difference between two sorted maps, using the comparator of 493 * the left map, or {@code Ordering.natural()} if the left map uses the 494 * natural ordering of its elements. This difference is an immutable snapshot 495 * of the state of the maps at the time this method is called. It will never 496 * change, even if the maps change at a later time. 497 * 498 * <p>Since this method uses {@code TreeMap} instances internally, the keys of 499 * the right map must all compare as distinct according to the comparator 500 * of the left map. 501 * 502 * <p><b>Note:</b>If you only need to know whether two sorted maps have the 503 * same mappings, call {@code left.equals(right)} instead of this method. 504 * 505 * @param left the map to treat as the "left" map for purposes of comparison 506 * @param right the map to treat as the "right" map for purposes of comparison 507 * @return the difference between the two maps 508 * @since 11.0 509 */ 510 public static <K, V> SortedMapDifference<K, V> difference( 511 SortedMap<K, ? extends V> left, Map<? extends K, ? extends V> right) { 512 checkNotNull(left); 513 checkNotNull(right); 514 Comparator<? super K> comparator = orNaturalOrder(left.comparator()); 515 SortedMap<K, V> onlyOnLeft = Maps.newTreeMap(comparator); 516 SortedMap<K, V> onlyOnRight = Maps.newTreeMap(comparator); 517 onlyOnRight.putAll(right); // will whittle it down 518 SortedMap<K, V> onBoth = Maps.newTreeMap(comparator); 519 SortedMap<K, MapDifference.ValueDifference<V>> differences = 520 Maps.newTreeMap(comparator); 521 boolean eq = true; 522 523 for (Entry<? extends K, ? extends V> entry : left.entrySet()) { 524 K leftKey = entry.getKey(); 525 V leftValue = entry.getValue(); 526 if (right.containsKey(leftKey)) { 527 V rightValue = onlyOnRight.remove(leftKey); 528 if (Objects.equal(leftValue, rightValue)) { 529 onBoth.put(leftKey, leftValue); 530 } else { 531 eq = false; 532 differences.put( 533 leftKey, ValueDifferenceImpl.create(leftValue, rightValue)); 534 } 535 } else { 536 eq = false; 537 onlyOnLeft.put(leftKey, leftValue); 538 } 539 } 540 541 boolean areEqual = eq && onlyOnRight.isEmpty(); 542 return sortedMapDifference( 543 areEqual, onlyOnLeft, onlyOnRight, onBoth, differences); 544 } 545 546 private static <K, V> SortedMapDifference<K, V> sortedMapDifference( 547 boolean areEqual, SortedMap<K, V> onlyOnLeft, SortedMap<K, V> onlyOnRight, 548 SortedMap<K, V> onBoth, SortedMap<K, ValueDifference<V>> differences) { 549 return new SortedMapDifferenceImpl<K, V>(areEqual, 550 Collections.unmodifiableSortedMap(onlyOnLeft), 551 Collections.unmodifiableSortedMap(onlyOnRight), 552 Collections.unmodifiableSortedMap(onBoth), 553 Collections.unmodifiableSortedMap(differences)); 554 } 555 556 static class SortedMapDifferenceImpl<K, V> extends MapDifferenceImpl<K, V> 557 implements SortedMapDifference<K, V> { 558 SortedMapDifferenceImpl(boolean areEqual, SortedMap<K, V> onlyOnLeft, 559 SortedMap<K, V> onlyOnRight, SortedMap<K, V> onBoth, 560 SortedMap<K, ValueDifference<V>> differences) { 561 super(areEqual, onlyOnLeft, onlyOnRight, onBoth, differences); 562 } 563 564 @Override public SortedMap<K, ValueDifference<V>> entriesDiffering() { 565 return (SortedMap<K, ValueDifference<V>>) super.entriesDiffering(); 566 } 567 568 @Override public SortedMap<K, V> entriesInCommon() { 569 return (SortedMap<K, V>) super.entriesInCommon(); 570 } 571 572 @Override public SortedMap<K, V> entriesOnlyOnLeft() { 573 return (SortedMap<K, V>) super.entriesOnlyOnLeft(); 574 } 575 576 @Override public SortedMap<K, V> entriesOnlyOnRight() { 577 return (SortedMap<K, V>) super.entriesOnlyOnRight(); 578 } 579 } 580 581 /** 582 * Returns the specified comparator if not null; otherwise returns {@code 583 * Ordering.natural()}. This method is an abomination of generics; the only 584 * purpose of this method is to contain the ugly type-casting in one place. 585 */ 586 @SuppressWarnings("unchecked") 587 static <E> Comparator<? super E> orNaturalOrder( 588 @Nullable Comparator<? super E> comparator) { 589 if (comparator != null) { // can't use ? : because of javac bug 5080917 590 return comparator; 591 } 592 return (Comparator<E>) Ordering.natural(); 593 } 594 595 /** 596 * Returns a view of the set as a map, mapping keys from the set according to 597 * the specified function. 598 * 599 * <p>Specifically, for each {@code k} in the backing set, the returned map 600 * has an entry mapping {@code k} to {@code function.apply(k)}. The {@code 601 * keySet}, {@code values}, and {@code entrySet} views of the returned map 602 * iterate in the same order as the backing set. 603 * 604 * <p>Modifications to the backing set are read through to the returned map. 605 * The returned map supports removal operations if the backing set does. 606 * Removal operations write through to the backing set. The returned map 607 * does not support put operations. 608 * 609 * <p><b>Warning</b>: If the function rejects {@code null}, caution is 610 * required to make sure the set does not contain {@code null}, because the 611 * view cannot stop {@code null} from being added to the set. 612 * 613 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of 614 * key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also 615 * of type {@code K}. Using a key type for which this may not hold, such as 616 * {@code ArrayList}, may risk a {@code ClassCastException} when calling 617 * methods on the resulting map view. 618 */ 619 @Beta 620 static <K, V> Map<K, V> asMap( 621 Set<K> set, Function<? super K, V> function) { 622 if (set instanceof SortedSet) { 623 return asMap((SortedSet<K>) set, function); 624 } else { 625 return new AsMapView<K, V>(set, function); 626 } 627 } 628 629 /** 630 * Returns a view of the sorted set as a map, mapping keys from the set 631 * according to the specified function. 632 * 633 * <p>Specifically, for each {@code k} in the backing set, the returned map 634 * has an entry mapping {@code k} to {@code function.apply(k)}. The {@code 635 * keySet}, {@code values}, and {@code entrySet} views of the returned map 636 * iterate in the same order as the backing set. 637 * 638 * <p>Modifications to the backing set are read through to the returned map. 639 * The returned map supports removal operations if the backing set does. 640 * Removal operations write through to the backing set. The returned map does 641 * not support put operations. 642 * 643 * <p><b>Warning</b>: If the function rejects {@code null}, caution is 644 * required to make sure the set does not contain {@code null}, because the 645 * view cannot stop {@code null} from being added to the set. 646 * 647 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of 648 * key type {@code K}, {@code k.equals(k2)} implies that {@code k2} is also of 649 * type {@code K}. Using a key type for which this may not hold, such as 650 * {@code ArrayList}, may risk a {@code ClassCastException} when calling 651 * methods on the resulting map view. 652 */ 653 @Beta 654 static <K, V> SortedMap<K, V> asMap( 655 SortedSet<K> set, Function<? super K, V> function) { 656 // TODO: NavigableSet overloads 657 return new SortedAsMapView<K, V>(set, function); 658 } 659 660 private static class AsMapView<K, V> extends ImprovedAbstractMap<K, V> { 661 662 private final Set<K> set; 663 final Function<? super K, V> function; 664 665 Set<K> backingSet() { 666 return set; 667 } 668 669 AsMapView(Set<K> set, Function<? super K, V> function) { 670 this.set = checkNotNull(set); 671 this.function = checkNotNull(function); 672 } 673 674 @Override 675 public Set<K> keySet() { 676 // probably not worth caching 677 return new ForwardingSet<K>() { 678 @Override 679 protected Set<K> delegate() { 680 return set; 681 } 682 683 @Override 684 public boolean add(K element) { 685 throw new UnsupportedOperationException(); 686 } 687 688 @Override 689 public boolean addAll(Collection<? extends K> collection) { 690 throw new UnsupportedOperationException(); 691 } 692 }; 693 } 694 695 @Override 696 public Collection<V> values() { 697 // probably not worth caching 698 return Collections2.transform(set, function); 699 } 700 701 @Override 702 public int size() { 703 return set.size(); 704 } 705 706 @Override 707 public boolean containsKey(@Nullable Object key) { 708 return set.contains(key); 709 } 710 711 @Override 712 public V get(@Nullable Object key) { 713 if (set.contains(key)) { 714 @SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it 715 K k = (K) key; 716 return function.apply(k); 717 } else { 718 return null; 719 } 720 } 721 722 @Override 723 public V remove(@Nullable Object key) { 724 if (set.remove(key)) { 725 @SuppressWarnings("unchecked") // unsafe, but Javadoc warns about it 726 K k = (K) key; 727 return function.apply(k); 728 } else { 729 return null; 730 } 731 } 732 733 @Override 734 public void clear() { 735 set.clear(); 736 } 737 738 @Override 739 protected Set<Entry<K, V>> createEntrySet() { 740 return new EntrySet<K, V>() { 741 @Override 742 Map<K, V> map() { 743 return AsMapView.this; 744 } 745 746 @Override 747 public Iterator<Entry<K, V>> iterator() { 748 final Iterator<K> backingIterator = set.iterator(); 749 return new Iterator<Entry<K, V>>() { 750 @Override 751 public boolean hasNext() { 752 return backingIterator.hasNext(); 753 } 754 755 @Override 756 public Entry<K, V> next() { 757 K k = backingIterator.next(); 758 return Maps.immutableEntry(k, function.apply(k)); 759 } 760 761 @Override 762 public void remove() { 763 backingIterator.remove(); 764 } 765 }; 766 } 767 }; 768 } 769 } 770 771 private static final class SortedAsMapView<K, V> extends AsMapView<K, V> 772 implements SortedMap<K, V> { 773 774 SortedAsMapView(SortedSet<K> set, Function<? super K, V> function) { 775 super(set, function); 776 } 777 778 @Override 779 public Comparator<? super K> comparator() { 780 return backingSet().comparator(); 781 } 782 783 @Override 784 public SortedMap<K, V> subMap(K fromKey, K toKey) { 785 return asMap(backingSet().subSet(fromKey, toKey), function); 786 } 787 788 @Override 789 public SortedMap<K, V> headMap(K toKey) { 790 return asMap(backingSet().headSet(toKey), function); 791 } 792 793 @Override 794 public SortedMap<K, V> tailMap(K fromKey) { 795 return asMap(backingSet().tailSet(fromKey), function); 796 } 797 798 @Override 799 public K firstKey() { 800 return backingSet().first(); 801 } 802 803 @Override 804 public K lastKey() { 805 return backingSet().last(); 806 } 807 808 @Override 809 SortedSet<K> backingSet() { 810 return (SortedSet<K>) super.backingSet(); 811 } 812 } 813 814 /** 815 * Returns an immutable map for which the {@link Map#values} are the given 816 * elements in the given order, and each key is the product of invoking a 817 * supplied function on its corresponding value. 818 * 819 * @param values the values to use when constructing the {@code Map} 820 * @param keyFunction the function used to produce the key for each value 821 * @return a map mapping the result of evaluating the function {@code 822 * keyFunction} on each value in the input collection to that value 823 * @throws IllegalArgumentException if {@code keyFunction} produces the same 824 * key for more than one value in the input collection 825 * @throws NullPointerException if any elements of {@code values} is null, or 826 * if {@code keyFunction} produces {@code null} for any value 827 */ 828 public static <K, V> ImmutableMap<K, V> uniqueIndex( 829 Iterable<V> values, Function<? super V, K> keyFunction) { 830 return uniqueIndex(values.iterator(), keyFunction); 831 } 832 833 /** 834 * Returns an immutable map for which the {@link Map#values} are the given 835 * elements in the given order, and each key is the product of invoking a 836 * supplied function on its corresponding value. 837 * 838 * @param values the values to use when constructing the {@code Map} 839 * @param keyFunction the function used to produce the key for each value 840 * @return a map mapping the result of evaluating the function {@code 841 * keyFunction} on each value in the input collection to that value 842 * @throws IllegalArgumentException if {@code keyFunction} produces the same 843 * key for more than one value in the input collection 844 * @throws NullPointerException if any elements of {@code values} is null, or 845 * if {@code keyFunction} produces {@code null} for any value 846 * @since 10.0 847 */ 848 public static <K, V> ImmutableMap<K, V> uniqueIndex( 849 Iterator<V> values, Function<? super V, K> keyFunction) { 850 checkNotNull(keyFunction); 851 ImmutableMap.Builder<K, V> builder = ImmutableMap.builder(); 852 while (values.hasNext()) { 853 V value = values.next(); 854 builder.put(keyFunction.apply(value), value); 855 } 856 return builder.build(); 857 } 858 859 /** 860 * Creates an {@code ImmutableMap<String, String>} from a {@code Properties} 861 * instance. Properties normally derive from {@code Map<Object, Object>}, but 862 * they typically contain strings, which is awkward. This method lets you get 863 * a plain-old-{@code Map} out of a {@code Properties}. 864 * 865 * @param properties a {@code Properties} object to be converted 866 * @return an immutable map containing all the entries in {@code properties} 867 * @throws ClassCastException if any key in {@code Properties} is not a {@code 868 * String} 869 * @throws NullPointerException if any key or value in {@code Properties} is 870 * null 871 */ 872 @GwtIncompatible("java.util.Properties") 873 public static ImmutableMap<String, String> fromProperties( 874 Properties properties) { 875 ImmutableMap.Builder<String, String> builder = ImmutableMap.builder(); 876 877 for (Enumeration<?> e = properties.propertyNames(); e.hasMoreElements();) { 878 String key = (String) e.nextElement(); 879 builder.put(key, properties.getProperty(key)); 880 } 881 882 return builder.build(); 883 } 884 885 /** 886 * Returns an immutable map entry with the specified key and value. The {@link 887 * Entry#setValue} operation throws an {@link UnsupportedOperationException}. 888 * 889 * <p>The returned entry is serializable. 890 * 891 * @param key the key to be associated with the returned entry 892 * @param value the value to be associated with the returned entry 893 */ 894 @GwtCompatible(serializable = true) 895 public static <K, V> Entry<K, V> immutableEntry( 896 @Nullable K key, @Nullable V value) { 897 return new ImmutableEntry<K, V>(key, value); 898 } 899 900 /** 901 * Returns an unmodifiable view of the specified set of entries. The {@link 902 * Entry#setValue} operation throws an {@link UnsupportedOperationException}, 903 * as do any operations that would modify the returned set. 904 * 905 * @param entrySet the entries for which to return an unmodifiable view 906 * @return an unmodifiable view of the entries 907 */ 908 static <K, V> Set<Entry<K, V>> unmodifiableEntrySet( 909 Set<Entry<K, V>> entrySet) { 910 return new UnmodifiableEntrySet<K, V>( 911 Collections.unmodifiableSet(entrySet)); 912 } 913 914 /** 915 * Returns an unmodifiable view of the specified map entry. The {@link 916 * Entry#setValue} operation throws an {@link UnsupportedOperationException}. 917 * This also has the side-effect of redefining {@code equals} to comply with 918 * the Entry contract, to avoid a possible nefarious implementation of equals. 919 * 920 * @param entry the entry for which to return an unmodifiable view 921 * @return an unmodifiable view of the entry 922 */ 923 static <K, V> Entry<K, V> unmodifiableEntry(final Entry<K, V> entry) { 924 checkNotNull(entry); 925 return new AbstractMapEntry<K, V>() { 926 @Override public K getKey() { 927 return entry.getKey(); 928 } 929 930 @Override public V getValue() { 931 return entry.getValue(); 932 } 933 }; 934 } 935 936 /** @see Multimaps#unmodifiableEntries */ 937 static class UnmodifiableEntries<K, V> 938 extends ForwardingCollection<Entry<K, V>> { 939 private final Collection<Entry<K, V>> entries; 940 941 UnmodifiableEntries(Collection<Entry<K, V>> entries) { 942 this.entries = entries; 943 } 944 945 @Override protected Collection<Entry<K, V>> delegate() { 946 return entries; 947 } 948 949 @Override public Iterator<Entry<K, V>> iterator() { 950 final Iterator<Entry<K, V>> delegate = super.iterator(); 951 return new ForwardingIterator<Entry<K, V>>() { 952 @Override public Entry<K, V> next() { 953 return unmodifiableEntry(super.next()); 954 } 955 956 @Override public void remove() { 957 throw new UnsupportedOperationException(); 958 } 959 960 @Override protected Iterator<Entry<K, V>> delegate() { 961 return delegate; 962 } 963 }; 964 } 965 966 // See java.util.Collections.UnmodifiableEntrySet for details on attacks. 967 968 @Override public boolean add(Entry<K, V> element) { 969 throw new UnsupportedOperationException(); 970 } 971 972 @Override public boolean addAll( 973 Collection<? extends Entry<K, V>> collection) { 974 throw new UnsupportedOperationException(); 975 } 976 977 @Override public void clear() { 978 throw new UnsupportedOperationException(); 979 } 980 981 @Override public boolean remove(Object object) { 982 throw new UnsupportedOperationException(); 983 } 984 985 @Override public boolean removeAll(Collection<?> collection) { 986 throw new UnsupportedOperationException(); 987 } 988 989 @Override public boolean retainAll(Collection<?> collection) { 990 throw new UnsupportedOperationException(); 991 } 992 993 @Override public Object[] toArray() { 994 return standardToArray(); 995 } 996 997 @Override public <T> T[] toArray(T[] array) { 998 return standardToArray(array); 999 } 1000 } 1001 1002 /** @see Maps#unmodifiableEntrySet(Set) */ 1003 static class UnmodifiableEntrySet<K, V> 1004 extends UnmodifiableEntries<K, V> implements Set<Entry<K, V>> { 1005 UnmodifiableEntrySet(Set<Entry<K, V>> entries) { 1006 super(entries); 1007 } 1008 1009 // See java.util.Collections.UnmodifiableEntrySet for details on attacks. 1010 1011 @Override public boolean equals(@Nullable Object object) { 1012 return Sets.equalsImpl(this, object); 1013 } 1014 1015 @Override public int hashCode() { 1016 return Sets.hashCodeImpl(this); 1017 } 1018 } 1019 1020 /** 1021 * Returns a synchronized (thread-safe) bimap backed by the specified bimap. 1022 * In order to guarantee serial access, it is critical that <b>all</b> access 1023 * to the backing bimap is accomplished through the returned bimap. 1024 * 1025 * <p>It is imperative that the user manually synchronize on the returned map 1026 * when accessing any of its collection views: <pre> {@code 1027 * 1028 * BiMap<Long, String> map = Maps.synchronizedBiMap( 1029 * HashBiMap.<Long, String>create()); 1030 * ... 1031 * Set<Long> set = map.keySet(); // Needn't be in synchronized block 1032 * ... 1033 * synchronized (map) { // Synchronizing on map, not set! 1034 * Iterator<Long> it = set.iterator(); // Must be in synchronized block 1035 * while (it.hasNext()) { 1036 * foo(it.next()); 1037 * } 1038 * }}</pre> 1039 * 1040 * Failure to follow this advice may result in non-deterministic behavior. 1041 * 1042 * <p>The returned bimap will be serializable if the specified bimap is 1043 * serializable. 1044 * 1045 * @param bimap the bimap to be wrapped in a synchronized view 1046 * @return a sychronized view of the specified bimap 1047 */ 1048 public static <K, V> BiMap<K, V> synchronizedBiMap(BiMap<K, V> bimap) { 1049 return Synchronized.biMap(bimap, null); 1050 } 1051 1052 /** 1053 * Returns an unmodifiable view of the specified bimap. This method allows 1054 * modules to provide users with "read-only" access to internal bimaps. Query 1055 * operations on the returned bimap "read through" to the specified bimap, and 1056 * attempts to modify the returned map, whether direct or via its collection 1057 * views, result in an {@code UnsupportedOperationException}. 1058 * 1059 * <p>The returned bimap will be serializable if the specified bimap is 1060 * serializable. 1061 * 1062 * @param bimap the bimap for which an unmodifiable view is to be returned 1063 * @return an unmodifiable view of the specified bimap 1064 */ 1065 public static <K, V> BiMap<K, V> unmodifiableBiMap( 1066 BiMap<? extends K, ? extends V> bimap) { 1067 return new UnmodifiableBiMap<K, V>(bimap, null); 1068 } 1069 1070 /** @see Maps#unmodifiableBiMap(BiMap) */ 1071 private static class UnmodifiableBiMap<K, V> 1072 extends ForwardingMap<K, V> implements BiMap<K, V>, Serializable { 1073 final Map<K, V> unmodifiableMap; 1074 final BiMap<? extends K, ? extends V> delegate; 1075 BiMap<V, K> inverse; 1076 transient Set<V> values; 1077 1078 UnmodifiableBiMap(BiMap<? extends K, ? extends V> delegate, 1079 @Nullable BiMap<V, K> inverse) { 1080 unmodifiableMap = Collections.unmodifiableMap(delegate); 1081 this.delegate = delegate; 1082 this.inverse = inverse; 1083 } 1084 1085 @Override protected Map<K, V> delegate() { 1086 return unmodifiableMap; 1087 } 1088 1089 @Override 1090 public V forcePut(K key, V value) { 1091 throw new UnsupportedOperationException(); 1092 } 1093 1094 @Override 1095 public BiMap<V, K> inverse() { 1096 BiMap<V, K> result = inverse; 1097 return (result == null) 1098 ? inverse = new UnmodifiableBiMap<V, K>(delegate.inverse(), this) 1099 : result; 1100 } 1101 1102 @Override public Set<V> values() { 1103 Set<V> result = values; 1104 return (result == null) 1105 ? values = Collections.unmodifiableSet(delegate.values()) 1106 : result; 1107 } 1108 1109 private static final long serialVersionUID = 0; 1110 } 1111 1112 /** 1113 * Returns a view of a map where each value is transformed by a function. All 1114 * other properties of the map, such as iteration order, are left intact. For 1115 * example, the code: <pre> {@code 1116 * 1117 * Map<String, Integer> map = ImmutableMap.of("a", 4, "b", 9); 1118 * Function<Integer, Double> sqrt = 1119 * new Function<Integer, Double>() { 1120 * public Double apply(Integer in) { 1121 * return Math.sqrt((int) in); 1122 * } 1123 * }; 1124 * Map<String, Double> transformed = Maps.transformValues(map, sqrt); 1125 * System.out.println(transformed);}</pre> 1126 * 1127 * ... prints {@code {a=2.0, b=3.0}}. 1128 * 1129 * <p>Changes in the underlying map are reflected in this view. Conversely, 1130 * this view supports removal operations, and these are reflected in the 1131 * underlying map. 1132 * 1133 * <p>It's acceptable for the underlying map to contain null keys, and even 1134 * null values provided that the function is capable of accepting null input. 1135 * The transformed map might contain null values, if the function sometimes 1136 * gives a null result. 1137 * 1138 * <p>The returned map is not thread-safe or serializable, even if the 1139 * underlying map is. 1140 * 1141 * <p>The function is applied lazily, invoked when needed. This is necessary 1142 * for the returned map to be a view, but it means that the function will be 1143 * applied many times for bulk operations like {@link Map#containsValue} and 1144 * {@code Map.toString()}. For this to perform well, {@code function} should 1145 * be fast. To avoid lazy evaluation when the returned map doesn't need to be 1146 * a view, copy the returned map into a new map of your choosing. 1147 */ 1148 public static <K, V1, V2> Map<K, V2> transformValues( 1149 Map<K, V1> fromMap, Function<? super V1, V2> function) { 1150 return transformEntries(fromMap, asEntryTransformer(function)); 1151 } 1152 1153 /** 1154 * Returns a view of a sorted map where each value is transformed by a 1155 * function. All other properties of the map, such as iteration order, are 1156 * left intact. For example, the code: <pre> {@code 1157 * 1158 * SortedMap<String, Integer> map = ImmutableSortedMap.of("a", 4, "b", 9); 1159 * Function<Integer, Double> sqrt = 1160 * new Function<Integer, Double>() { 1161 * public Double apply(Integer in) { 1162 * return Math.sqrt((int) in); 1163 * } 1164 * }; 1165 * SortedMap<String, Double> transformed = 1166 * Maps.transformSortedValues(map, sqrt); 1167 * System.out.println(transformed);}</pre> 1168 * 1169 * ... prints {@code {a=2.0, b=3.0}}. 1170 * 1171 * <p>Changes in the underlying map are reflected in this view. Conversely, 1172 * this view supports removal operations, and these are reflected in the 1173 * underlying map. 1174 * 1175 * <p>It's acceptable for the underlying map to contain null keys, and even 1176 * null values provided that the function is capable of accepting null input. 1177 * The transformed map might contain null values, if the function sometimes 1178 * gives a null result. 1179 * 1180 * <p>The returned map is not thread-safe or serializable, even if the 1181 * underlying map is. 1182 * 1183 * <p>The function is applied lazily, invoked when needed. This is necessary 1184 * for the returned map to be a view, but it means that the function will be 1185 * applied many times for bulk operations like {@link Map#containsValue} and 1186 * {@code Map.toString()}. For this to perform well, {@code function} should 1187 * be fast. To avoid lazy evaluation when the returned map doesn't need to be 1188 * a view, copy the returned map into a new map of your choosing. 1189 * 1190 * @since 11.0 1191 */ 1192 @Beta 1193 public static <K, V1, V2> SortedMap<K, V2> transformValues( 1194 SortedMap<K, V1> fromMap, Function<? super V1, V2> function) { 1195 return transformEntries(fromMap, asEntryTransformer(function)); 1196 } 1197 1198 /** 1199 * Returns a view of a navigable map where each value is transformed by a 1200 * function. All other properties of the map, such as iteration order, are 1201 * left intact. For example, the code: <pre> {@code 1202 * 1203 * NavigableMap<String, Integer> map = Maps.newTreeMap(); 1204 * map.put("a", 4); 1205 * map.put("b", 9); 1206 * Function<Integer, Double> sqrt = 1207 * new Function<Integer, Double>() { 1208 * public Double apply(Integer in) { 1209 * return Math.sqrt((int) in); 1210 * } 1211 * }; 1212 * NavigableMap<String, Double> transformed = 1213 * Maps.transformNavigableValues(map, sqrt); 1214 * System.out.println(transformed);}</pre> 1215 * 1216 * ... prints {@code {a=2.0, b=3.0}}. 1217 * 1218 * Changes in the underlying map are reflected in this view. 1219 * Conversely, this view supports removal operations, and these are reflected 1220 * in the underlying map. 1221 * 1222 * <p>It's acceptable for the underlying map to contain null keys, and even 1223 * null values provided that the function is capable of accepting null input. 1224 * The transformed map might contain null values, if the function sometimes 1225 * gives a null result. 1226 * 1227 * <p>The returned map is not thread-safe or serializable, even if the 1228 * underlying map is. 1229 * 1230 * <p>The function is applied lazily, invoked when needed. This is necessary 1231 * for the returned map to be a view, but it means that the function will be 1232 * applied many times for bulk operations like {@link Map#containsValue} and 1233 * {@code Map.toString()}. For this to perform well, {@code function} should 1234 * be fast. To avoid lazy evaluation when the returned map doesn't need to be 1235 * a view, copy the returned map into a new map of your choosing. 1236 * 1237 * @since 13.0 1238 */ 1239 @Beta 1240 @GwtIncompatible("NavigableMap") 1241 public static <K, V1, V2> NavigableMap<K, V2> transformValues( 1242 NavigableMap<K, V1> fromMap, Function<? super V1, V2> function) { 1243 return transformEntries(fromMap, asEntryTransformer(function)); 1244 } 1245 1246 private static <K, V1, V2> EntryTransformer<K, V1, V2> 1247 asEntryTransformer(final Function<? super V1, V2> function) { 1248 checkNotNull(function); 1249 return new EntryTransformer<K, V1, V2>() { 1250 @Override 1251 public V2 transformEntry(K key, V1 value) { 1252 return function.apply(value); 1253 } 1254 }; 1255 } 1256 1257 /** 1258 * Returns a view of a map whose values are derived from the original map's 1259 * entries. In contrast to {@link #transformValues}, this method's 1260 * entry-transformation logic may depend on the key as well as the value. 1261 * 1262 * <p>All other properties of the transformed map, such as iteration order, 1263 * are left intact. For example, the code: <pre> {@code 1264 * 1265 * Map<String, Boolean> options = 1266 * ImmutableMap.of("verbose", true, "sort", false); 1267 * EntryTransformer<String, Boolean, String> flagPrefixer = 1268 * new EntryTransformer<String, Boolean, String>() { 1269 * public String transformEntry(String key, Boolean value) { 1270 * return value ? key : "no" + key; 1271 * } 1272 * }; 1273 * Map<String, String> transformed = 1274 * Maps.transformEntries(options, flagPrefixer); 1275 * System.out.println(transformed);}</pre> 1276 * 1277 * ... prints {@code {verbose=verbose, sort=nosort}}. 1278 * 1279 * <p>Changes in the underlying map are reflected in this view. Conversely, 1280 * this view supports removal operations, and these are reflected in the 1281 * underlying map. 1282 * 1283 * <p>It's acceptable for the underlying map to contain null keys and null 1284 * values provided that the transformer is capable of accepting null inputs. 1285 * The transformed map might contain null values if the transformer sometimes 1286 * gives a null result. 1287 * 1288 * <p>The returned map is not thread-safe or serializable, even if the 1289 * underlying map is. 1290 * 1291 * <p>The transformer is applied lazily, invoked when needed. This is 1292 * necessary for the returned map to be a view, but it means that the 1293 * transformer will be applied many times for bulk operations like {@link 1294 * Map#containsValue} and {@link Object#toString}. For this to perform well, 1295 * {@code transformer} should be fast. To avoid lazy evaluation when the 1296 * returned map doesn't need to be a view, copy the returned map into a new 1297 * map of your choosing. 1298 * 1299 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of 1300 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies 1301 * that {@code k2} is also of type {@code K}. Using an {@code 1302 * EntryTransformer} key type for which this may not hold, such as {@code 1303 * ArrayList}, may risk a {@code ClassCastException} when calling methods on 1304 * the transformed map. 1305 * 1306 * @since 7.0 1307 */ 1308 public static <K, V1, V2> Map<K, V2> transformEntries( 1309 Map<K, V1> fromMap, 1310 EntryTransformer<? super K, ? super V1, V2> transformer) { 1311 if (fromMap instanceof SortedMap) { 1312 return transformEntries((SortedMap<K, V1>) fromMap, transformer); 1313 } 1314 return new TransformedEntriesMap<K, V1, V2>(fromMap, transformer); 1315 } 1316 1317 /** 1318 * Returns a view of a sorted map whose values are derived from the original 1319 * sorted map's entries. In contrast to {@link #transformValues}, this 1320 * method's entry-transformation logic may depend on the key as well as the 1321 * value. 1322 * 1323 * <p>All other properties of the transformed map, such as iteration order, 1324 * are left intact. For example, the code: <pre> {@code 1325 * 1326 * Map<String, Boolean> options = 1327 * ImmutableSortedMap.of("verbose", true, "sort", false); 1328 * EntryTransformer<String, Boolean, String> flagPrefixer = 1329 * new EntryTransformer<String, Boolean, String>() { 1330 * public String transformEntry(String key, Boolean value) { 1331 * return value ? key : "yes" + key; 1332 * } 1333 * }; 1334 * SortedMap<String, String> transformed = 1335 * LabsMaps.transformSortedEntries(options, flagPrefixer); 1336 * System.out.println(transformed);}</pre> 1337 * 1338 * ... prints {@code {sort=yessort, verbose=verbose}}. 1339 * 1340 * <p>Changes in the underlying map are reflected in this view. Conversely, 1341 * this view supports removal operations, and these are reflected in the 1342 * underlying map. 1343 * 1344 * <p>It's acceptable for the underlying map to contain null keys and null 1345 * values provided that the transformer is capable of accepting null inputs. 1346 * The transformed map might contain null values if the transformer sometimes 1347 * gives a null result. 1348 * 1349 * <p>The returned map is not thread-safe or serializable, even if the 1350 * underlying map is. 1351 * 1352 * <p>The transformer is applied lazily, invoked when needed. This is 1353 * necessary for the returned map to be a view, but it means that the 1354 * transformer will be applied many times for bulk operations like {@link 1355 * Map#containsValue} and {@link Object#toString}. For this to perform well, 1356 * {@code transformer} should be fast. To avoid lazy evaluation when the 1357 * returned map doesn't need to be a view, copy the returned map into a new 1358 * map of your choosing. 1359 * 1360 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of 1361 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies 1362 * that {@code k2} is also of type {@code K}. Using an {@code 1363 * EntryTransformer} key type for which this may not hold, such as {@code 1364 * ArrayList}, may risk a {@code ClassCastException} when calling methods on 1365 * the transformed map. 1366 * 1367 * @since 11.0 1368 */ 1369 @Beta 1370 public static <K, V1, V2> SortedMap<K, V2> transformEntries( 1371 SortedMap<K, V1> fromMap, 1372 EntryTransformer<? super K, ? super V1, V2> transformer) { 1373 return Platform.mapsTransformEntriesSortedMap(fromMap, transformer); 1374 } 1375 1376 /** 1377 * Returns a view of a navigable map whose values are derived from the 1378 * original navigable map's entries. In contrast to {@link 1379 * #transformValues}, this method's entry-transformation logic may 1380 * depend on the key as well as the value. 1381 * 1382 * <p>All other properties of the transformed map, such as iteration order, 1383 * are left intact. For example, the code: <pre> {@code 1384 * 1385 * NavigableMap<String, Boolean> options = Maps.newTreeMap(); 1386 * options.put("verbose", false); 1387 * options.put("sort", true); 1388 * EntryTransformer<String, Boolean, String> flagPrefixer = 1389 * new EntryTransformer<String, Boolean, String>() { 1390 * public String transformEntry(String key, Boolean value) { 1391 * return value ? key : ("yes" + key); 1392 * } 1393 * }; 1394 * NavigableMap<String, String> transformed = 1395 * LabsMaps.transformNavigableEntries(options, flagPrefixer); 1396 * System.out.println(transformed);}</pre> 1397 * 1398 * ... prints {@code {sort=yessort, verbose=verbose}}. 1399 * 1400 * <p>Changes in the underlying map are reflected in this view. 1401 * Conversely, this view supports removal operations, and these are reflected 1402 * in the underlying map. 1403 * 1404 * <p>It's acceptable for the underlying map to contain null keys and null 1405 * values provided that the transformer is capable of accepting null inputs. 1406 * The transformed map might contain null values if the transformer sometimes 1407 * gives a null result. 1408 * 1409 * <p>The returned map is not thread-safe or serializable, even if the 1410 * underlying map is. 1411 * 1412 * <p>The transformer is applied lazily, invoked when needed. This is 1413 * necessary for the returned map to be a view, but it means that the 1414 * transformer will be applied many times for bulk operations like {@link 1415 * Map#containsValue} and {@link Object#toString}. For this to perform well, 1416 * {@code transformer} should be fast. To avoid lazy evaluation when the 1417 * returned map doesn't need to be a view, copy the returned map into a new 1418 * map of your choosing. 1419 * 1420 * <p><b>Warning:</b> This method assumes that for any instance {@code k} of 1421 * {@code EntryTransformer} key type {@code K}, {@code k.equals(k2)} implies 1422 * that {@code k2} is also of type {@code K}. Using an {@code 1423 * EntryTransformer} key type for which this may not hold, such as {@code 1424 * ArrayList}, may risk a {@code ClassCastException} when calling methods on 1425 * the transformed map. 1426 * 1427 * @since 13.0 1428 */ 1429 @Beta 1430 @GwtIncompatible("NavigableMap") 1431 public static <K, V1, V2> NavigableMap<K, V2> transformEntries( 1432 final NavigableMap<K, V1> fromMap, 1433 EntryTransformer<? super K, ? super V1, V2> transformer) { 1434 return new TransformedEntriesNavigableMap<K, V1, V2>(fromMap, transformer); 1435 } 1436 1437 static <K, V1, V2> SortedMap<K, V2> transformEntriesIgnoreNavigable( 1438 SortedMap<K, V1> fromMap, 1439 EntryTransformer<? super K, ? super V1, V2> transformer) { 1440 return new TransformedEntriesSortedMap<K, V1, V2>(fromMap, transformer); 1441 } 1442 1443 /** 1444 * A transformation of the value of a key-value pair, using both key and value 1445 * as inputs. To apply the transformation to a map, use 1446 * {@link Maps#transformEntries(Map, EntryTransformer)}. 1447 * 1448 * @param <K> the key type of the input and output entries 1449 * @param <V1> the value type of the input entry 1450 * @param <V2> the value type of the output entry 1451 * @since 7.0 1452 */ 1453 public interface EntryTransformer<K, V1, V2> { 1454 /** 1455 * Determines an output value based on a key-value pair. This method is 1456 * <i>generally expected</i>, but not absolutely required, to have the 1457 * following properties: 1458 * 1459 * <ul> 1460 * <li>Its execution does not cause any observable side effects. 1461 * <li>The computation is <i>consistent with equals</i>; that is, 1462 * {@link Objects#equal Objects.equal}{@code (k1, k2) &&} 1463 * {@link Objects#equal}{@code (v1, v2)} implies that {@code 1464 * Objects.equal(transformer.transform(k1, v1), 1465 * transformer.transform(k2, v2))}. 1466 * </ul> 1467 * 1468 * @throws NullPointerException if the key or value is null and this 1469 * transformer does not accept null arguments 1470 */ 1471 V2 transformEntry(@Nullable K key, @Nullable V1 value); 1472 } 1473 1474 static class TransformedEntriesMap<K, V1, V2> 1475 extends AbstractMap<K, V2> { 1476 final Map<K, V1> fromMap; 1477 final EntryTransformer<? super K, ? super V1, V2> transformer; 1478 1479 TransformedEntriesMap( 1480 Map<K, V1> fromMap, 1481 EntryTransformer<? super K, ? super V1, V2> transformer) { 1482 this.fromMap = checkNotNull(fromMap); 1483 this.transformer = checkNotNull(transformer); 1484 } 1485 1486 @Override public int size() { 1487 return fromMap.size(); 1488 } 1489 1490 @Override public boolean containsKey(Object key) { 1491 return fromMap.containsKey(key); 1492 } 1493 1494 // safe as long as the user followed the <b>Warning</b> in the javadoc 1495 @SuppressWarnings("unchecked") 1496 @Override public V2 get(Object key) { 1497 V1 value = fromMap.get(key); 1498 return (value != null || fromMap.containsKey(key)) 1499 ? transformer.transformEntry((K) key, value) 1500 : null; 1501 } 1502 1503 // safe as long as the user followed the <b>Warning</b> in the javadoc 1504 @SuppressWarnings("unchecked") 1505 @Override public V2 remove(Object key) { 1506 return fromMap.containsKey(key) 1507 ? transformer.transformEntry((K) key, fromMap.remove(key)) 1508 : null; 1509 } 1510 1511 @Override public void clear() { 1512 fromMap.clear(); 1513 } 1514 1515 @Override public Set<K> keySet() { 1516 return fromMap.keySet(); 1517 } 1518 1519 Set<Entry<K, V2>> entrySet; 1520 1521 @Override public Set<Entry<K, V2>> entrySet() { 1522 Set<Entry<K, V2>> result = entrySet; 1523 if (result == null) { 1524 entrySet = result = new EntrySet<K, V2>() { 1525 @Override Map<K, V2> map() { 1526 return TransformedEntriesMap.this; 1527 } 1528 1529 @Override public Iterator<Entry<K, V2>> iterator() { 1530 return new TransformedIterator<Entry<K, V1>, Entry<K, V2>>( 1531 fromMap.entrySet().iterator()) { 1532 @Override 1533 Entry<K, V2> transform(final Entry<K, V1> entry) { 1534 return new AbstractMapEntry<K, V2>() { 1535 @Override 1536 public K getKey() { 1537 return entry.getKey(); 1538 } 1539 1540 @Override 1541 public V2 getValue() { 1542 return transformer.transformEntry(entry.getKey(), entry.getValue()); 1543 } 1544 }; 1545 } 1546 }; 1547 } 1548 }; 1549 } 1550 return result; 1551 } 1552 1553 Collection<V2> values; 1554 1555 @Override public Collection<V2> values() { 1556 Collection<V2> result = values; 1557 if (result == null) { 1558 return values = new Values<K, V2>() { 1559 @Override Map<K, V2> map() { 1560 return TransformedEntriesMap.this; 1561 } 1562 }; 1563 } 1564 return result; 1565 } 1566 } 1567 1568 static class TransformedEntriesSortedMap<K, V1, V2> 1569 extends TransformedEntriesMap<K, V1, V2> implements SortedMap<K, V2> { 1570 1571 protected SortedMap<K, V1> fromMap() { 1572 return (SortedMap<K, V1>) fromMap; 1573 } 1574 1575 TransformedEntriesSortedMap(SortedMap<K, V1> fromMap, 1576 EntryTransformer<? super K, ? super V1, V2> transformer) { 1577 super(fromMap, transformer); 1578 } 1579 1580 @Override public Comparator<? super K> comparator() { 1581 return fromMap().comparator(); 1582 } 1583 1584 @Override public K firstKey() { 1585 return fromMap().firstKey(); 1586 } 1587 1588 @Override public SortedMap<K, V2> headMap(K toKey) { 1589 return transformEntries(fromMap().headMap(toKey), transformer); 1590 } 1591 1592 @Override public K lastKey() { 1593 return fromMap().lastKey(); 1594 } 1595 1596 @Override public SortedMap<K, V2> subMap(K fromKey, K toKey) { 1597 return transformEntries( 1598 fromMap().subMap(fromKey, toKey), transformer); 1599 } 1600 1601 @Override public SortedMap<K, V2> tailMap(K fromKey) { 1602 return transformEntries(fromMap().tailMap(fromKey), transformer); 1603 } 1604 } 1605 1606 @GwtIncompatible("NavigableMap") 1607 private static class TransformedEntriesNavigableMap<K, V1, V2> 1608 extends TransformedEntriesSortedMap<K, V1, V2> 1609 implements NavigableMap<K, V2> { 1610 1611 TransformedEntriesNavigableMap(NavigableMap<K, V1> fromMap, 1612 EntryTransformer<? super K, ? super V1, V2> transformer) { 1613 super(fromMap, transformer); 1614 } 1615 1616 @Override public Entry<K, V2> ceilingEntry(K key) { 1617 return transformEntry(fromMap().ceilingEntry(key)); 1618 } 1619 1620 @Override public K ceilingKey(K key) { 1621 return fromMap().ceilingKey(key); 1622 } 1623 1624 @Override public NavigableSet<K> descendingKeySet() { 1625 return fromMap().descendingKeySet(); 1626 } 1627 1628 @Override public NavigableMap<K, V2> descendingMap() { 1629 return transformEntries(fromMap().descendingMap(), transformer); 1630 } 1631 1632 @Override public Entry<K, V2> firstEntry() { 1633 return transformEntry(fromMap().firstEntry()); 1634 } 1635 @Override public Entry<K, V2> floorEntry(K key) { 1636 return transformEntry(fromMap().floorEntry(key)); 1637 } 1638 1639 @Override public K floorKey(K key) { 1640 return fromMap().floorKey(key); 1641 } 1642 1643 @Override public NavigableMap<K, V2> headMap(K toKey) { 1644 return headMap(toKey, false); 1645 } 1646 1647 @Override public NavigableMap<K, V2> headMap(K toKey, boolean inclusive) { 1648 return transformEntries( 1649 fromMap().headMap(toKey, inclusive), transformer); 1650 } 1651 1652 @Override public Entry<K, V2> higherEntry(K key) { 1653 return transformEntry(fromMap().higherEntry(key)); 1654 } 1655 1656 @Override public K higherKey(K key) { 1657 return fromMap().higherKey(key); 1658 } 1659 1660 @Override public Entry<K, V2> lastEntry() { 1661 return transformEntry(fromMap().lastEntry()); 1662 } 1663 1664 @Override public Entry<K, V2> lowerEntry(K key) { 1665 return transformEntry(fromMap().lowerEntry(key)); 1666 } 1667 1668 @Override public K lowerKey(K key) { 1669 return fromMap().lowerKey(key); 1670 } 1671 1672 @Override public NavigableSet<K> navigableKeySet() { 1673 return fromMap().navigableKeySet(); 1674 } 1675 1676 @Override public Entry<K, V2> pollFirstEntry() { 1677 return transformEntry(fromMap().pollFirstEntry()); 1678 } 1679 1680 @Override public Entry<K, V2> pollLastEntry() { 1681 return transformEntry(fromMap().pollLastEntry()); 1682 } 1683 1684 @Override public NavigableMap<K, V2> subMap( 1685 K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 1686 return transformEntries( 1687 fromMap().subMap(fromKey, fromInclusive, toKey, toInclusive), 1688 transformer); 1689 } 1690 1691 @Override public NavigableMap<K, V2> subMap(K fromKey, K toKey) { 1692 return subMap(fromKey, true, toKey, false); 1693 } 1694 1695 @Override public NavigableMap<K, V2> tailMap(K fromKey) { 1696 return tailMap(fromKey, true); 1697 } 1698 1699 @Override public NavigableMap<K, V2> tailMap(K fromKey, boolean inclusive) { 1700 return transformEntries( 1701 fromMap().tailMap(fromKey, inclusive), transformer); 1702 } 1703 1704 private Entry<K, V2> transformEntry(Entry<K, V1> entry) { 1705 if (entry == null) { 1706 return null; 1707 } 1708 K key = entry.getKey(); 1709 V2 v2 = transformer.transformEntry(key, entry.getValue()); 1710 return Maps.immutableEntry(key, v2); 1711 } 1712 1713 @Override protected NavigableMap<K, V1> fromMap() { 1714 return (NavigableMap<K, V1>) super.fromMap(); 1715 } 1716 } 1717 1718 /** 1719 * Returns a map containing the mappings in {@code unfiltered} whose keys 1720 * satisfy a predicate. The returned map is a live view of {@code unfiltered}; 1721 * changes to one affect the other. 1722 * 1723 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code 1724 * values()} views have iterators that don't support {@code remove()}, but all 1725 * other methods are supported by the map and its views. When given a key that 1726 * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()} 1727 * methods throw an {@link IllegalArgumentException}. 1728 * 1729 * <p>When methods such as {@code removeAll()} and {@code clear()} are called 1730 * on the filtered map or its views, only mappings whose keys satisfy the 1731 * filter will be removed from the underlying map. 1732 * 1733 * <p>The returned map isn't threadsafe or serializable, even if {@code 1734 * unfiltered} is. 1735 * 1736 * <p>Many of the filtered map's methods, such as {@code size()}, 1737 * iterate across every key/value mapping in the underlying map and determine 1738 * which satisfy the filter. When a live view is <i>not</i> needed, it may be 1739 * faster to copy the filtered map and use the copy. 1740 * 1741 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with 1742 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a 1743 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is 1744 * inconsistent with equals. 1745 */ 1746 public static <K, V> Map<K, V> filterKeys( 1747 Map<K, V> unfiltered, final Predicate<? super K> keyPredicate) { 1748 if (unfiltered instanceof SortedMap) { 1749 return filterKeys((SortedMap<K, V>) unfiltered, keyPredicate); 1750 } 1751 checkNotNull(keyPredicate); 1752 Predicate<Entry<K, V>> entryPredicate = 1753 new Predicate<Entry<K, V>>() { 1754 @Override 1755 public boolean apply(Entry<K, V> input) { 1756 return keyPredicate.apply(input.getKey()); 1757 } 1758 }; 1759 return (unfiltered instanceof AbstractFilteredMap) 1760 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate) 1761 : new FilteredKeyMap<K, V>( 1762 checkNotNull(unfiltered), keyPredicate, entryPredicate); 1763 } 1764 1765 /** 1766 * Returns a sorted map containing the mappings in {@code unfiltered} whose 1767 * keys satisfy a predicate. The returned map is a live view of {@code 1768 * unfiltered}; changes to one affect the other. 1769 * 1770 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code 1771 * values()} views have iterators that don't support {@code remove()}, but all 1772 * other methods are supported by the map and its views. When given a key that 1773 * doesn't satisfy the predicate, the map's {@code put()} and {@code putAll()} 1774 * methods throw an {@link IllegalArgumentException}. 1775 * 1776 * <p>When methods such as {@code removeAll()} and {@code clear()} are called 1777 * on the filtered map or its views, only mappings whose keys satisfy the 1778 * filter will be removed from the underlying map. 1779 * 1780 * <p>The returned map isn't threadsafe or serializable, even if {@code 1781 * unfiltered} is. 1782 * 1783 * <p>Many of the filtered map's methods, such as {@code size()}, 1784 * iterate across every key/value mapping in the underlying map and determine 1785 * which satisfy the filter. When a live view is <i>not</i> needed, it may be 1786 * faster to copy the filtered map and use the copy. 1787 * 1788 * <p><b>Warning:</b> {@code keyPredicate} must be <i>consistent with 1789 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a 1790 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is 1791 * inconsistent with equals. 1792 * 1793 * @since 11.0 1794 */ 1795 public static <K, V> SortedMap<K, V> filterKeys( 1796 SortedMap<K, V> unfiltered, final Predicate<? super K> keyPredicate) { 1797 // TODO: Return a subclass of Maps.FilteredKeyMap for slightly better 1798 // performance. 1799 checkNotNull(keyPredicate); 1800 Predicate<Entry<K, V>> entryPredicate = new Predicate<Entry<K, V>>() { 1801 @Override 1802 public boolean apply(Entry<K, V> input) { 1803 return keyPredicate.apply(input.getKey()); 1804 } 1805 }; 1806 return filterEntries(unfiltered, entryPredicate); 1807 } 1808 1809 /** 1810 * Returns a map containing the mappings in {@code unfiltered} whose values 1811 * satisfy a predicate. The returned map is a live view of {@code unfiltered}; 1812 * changes to one affect the other. 1813 * 1814 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code 1815 * values()} views have iterators that don't support {@code remove()}, but all 1816 * other methods are supported by the map and its views. When given a value 1817 * that doesn't satisfy the predicate, the map's {@code put()}, {@code 1818 * putAll()}, and {@link Entry#setValue} methods throw an {@link 1819 * IllegalArgumentException}. 1820 * 1821 * <p>When methods such as {@code removeAll()} and {@code clear()} are called 1822 * on the filtered map or its views, only mappings whose values satisfy the 1823 * filter will be removed from the underlying map. 1824 * 1825 * <p>The returned map isn't threadsafe or serializable, even if {@code 1826 * unfiltered} is. 1827 * 1828 * <p>Many of the filtered map's methods, such as {@code size()}, 1829 * iterate across every key/value mapping in the underlying map and determine 1830 * which satisfy the filter. When a live view is <i>not</i> needed, it may be 1831 * faster to copy the filtered map and use the copy. 1832 * 1833 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with 1834 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a 1835 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is 1836 * inconsistent with equals. 1837 */ 1838 public static <K, V> Map<K, V> filterValues( 1839 Map<K, V> unfiltered, final Predicate<? super V> valuePredicate) { 1840 if (unfiltered instanceof SortedMap) { 1841 return filterValues((SortedMap<K, V>) unfiltered, valuePredicate); 1842 } 1843 checkNotNull(valuePredicate); 1844 Predicate<Entry<K, V>> entryPredicate = 1845 new Predicate<Entry<K, V>>() { 1846 @Override 1847 public boolean apply(Entry<K, V> input) { 1848 return valuePredicate.apply(input.getValue()); 1849 } 1850 }; 1851 return filterEntries(unfiltered, entryPredicate); 1852 } 1853 1854 /** 1855 * Returns a sorted map containing the mappings in {@code unfiltered} whose 1856 * values satisfy a predicate. The returned map is a live view of {@code 1857 * unfiltered}; changes to one affect the other. 1858 * 1859 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code 1860 * values()} views have iterators that don't support {@code remove()}, but all 1861 * other methods are supported by the map and its views. When given a value 1862 * that doesn't satisfy the predicate, the map's {@code put()}, {@code 1863 * putAll()}, and {@link Entry#setValue} methods throw an {@link 1864 * IllegalArgumentException}. 1865 * 1866 * <p>When methods such as {@code removeAll()} and {@code clear()} are called 1867 * on the filtered map or its views, only mappings whose values satisfy the 1868 * filter will be removed from the underlying map. 1869 * 1870 * <p>The returned map isn't threadsafe or serializable, even if {@code 1871 * unfiltered} is. 1872 * 1873 * <p>Many of the filtered map's methods, such as {@code size()}, 1874 * iterate across every key/value mapping in the underlying map and determine 1875 * which satisfy the filter. When a live view is <i>not</i> needed, it may be 1876 * faster to copy the filtered map and use the copy. 1877 * 1878 * <p><b>Warning:</b> {@code valuePredicate} must be <i>consistent with 1879 * equals</i>, as documented at {@link Predicate#apply}. Do not provide a 1880 * predicate such as {@code Predicates.instanceOf(ArrayList.class)}, which is 1881 * inconsistent with equals. 1882 * 1883 * @since 11.0 1884 */ 1885 public static <K, V> SortedMap<K, V> filterValues( 1886 SortedMap<K, V> unfiltered, final Predicate<? super V> valuePredicate) { 1887 checkNotNull(valuePredicate); 1888 Predicate<Entry<K, V>> entryPredicate = 1889 new Predicate<Entry<K, V>>() { 1890 @Override 1891 public boolean apply(Entry<K, V> input) { 1892 return valuePredicate.apply(input.getValue()); 1893 } 1894 }; 1895 return filterEntries(unfiltered, entryPredicate); 1896 } 1897 1898 /** 1899 * Returns a map containing the mappings in {@code unfiltered} that satisfy a 1900 * predicate. The returned map is a live view of {@code unfiltered}; changes 1901 * to one affect the other. 1902 * 1903 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code 1904 * values()} views have iterators that don't support {@code remove()}, but all 1905 * other methods are supported by the map and its views. When given a 1906 * key/value pair that doesn't satisfy the predicate, the map's {@code put()} 1907 * and {@code putAll()} methods throw an {@link IllegalArgumentException}. 1908 * Similarly, the map's entries have a {@link Entry#setValue} method that 1909 * throws an {@link IllegalArgumentException} when the existing key and the 1910 * provided value don't satisfy the predicate. 1911 * 1912 * <p>When methods such as {@code removeAll()} and {@code clear()} are called 1913 * on the filtered map or its views, only mappings that satisfy the filter 1914 * will be removed from the underlying map. 1915 * 1916 * <p>The returned map isn't threadsafe or serializable, even if {@code 1917 * unfiltered} is. 1918 * 1919 * <p>Many of the filtered map's methods, such as {@code size()}, 1920 * iterate across every key/value mapping in the underlying map and determine 1921 * which satisfy the filter. When a live view is <i>not</i> needed, it may be 1922 * faster to copy the filtered map and use the copy. 1923 * 1924 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with 1925 * equals</i>, as documented at {@link Predicate#apply}. 1926 */ 1927 public static <K, V> Map<K, V> filterEntries( 1928 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) { 1929 if (unfiltered instanceof SortedMap) { 1930 return filterEntries((SortedMap<K, V>) unfiltered, entryPredicate); 1931 } 1932 checkNotNull(entryPredicate); 1933 return (unfiltered instanceof AbstractFilteredMap) 1934 ? filterFiltered((AbstractFilteredMap<K, V>) unfiltered, entryPredicate) 1935 : new FilteredEntryMap<K, V>(checkNotNull(unfiltered), entryPredicate); 1936 } 1937 1938 /** 1939 * Returns a sorted map containing the mappings in {@code unfiltered} that 1940 * satisfy a predicate. The returned map is a live view of {@code unfiltered}; 1941 * changes to one affect the other. 1942 * 1943 * <p>The resulting map's {@code keySet()}, {@code entrySet()}, and {@code 1944 * values()} views have iterators that don't support {@code remove()}, but all 1945 * other methods are supported by the map and its views. When given a 1946 * key/value pair that doesn't satisfy the predicate, the map's {@code put()} 1947 * and {@code putAll()} methods throw an {@link IllegalArgumentException}. 1948 * Similarly, the map's entries have a {@link Entry#setValue} method that 1949 * throws an {@link IllegalArgumentException} when the existing key and the 1950 * provided value don't satisfy the predicate. 1951 * 1952 * <p>When methods such as {@code removeAll()} and {@code clear()} are called 1953 * on the filtered map or its views, only mappings that satisfy the filter 1954 * will be removed from the underlying map. 1955 * 1956 * <p>The returned map isn't threadsafe or serializable, even if {@code 1957 * unfiltered} is. 1958 * 1959 * <p>Many of the filtered map's methods, such as {@code size()}, 1960 * iterate across every key/value mapping in the underlying map and determine 1961 * which satisfy the filter. When a live view is <i>not</i> needed, it may be 1962 * faster to copy the filtered map and use the copy. 1963 * 1964 * <p><b>Warning:</b> {@code entryPredicate} must be <i>consistent with 1965 * equals</i>, as documented at {@link Predicate#apply}. 1966 * 1967 * @since 11.0 1968 */ 1969 public static <K, V> SortedMap<K, V> filterEntries( 1970 SortedMap<K, V> unfiltered, 1971 Predicate<? super Entry<K, V>> entryPredicate) { 1972 checkNotNull(entryPredicate); 1973 return (unfiltered instanceof FilteredEntrySortedMap) 1974 ? filterFiltered((FilteredEntrySortedMap<K, V>) unfiltered, entryPredicate) 1975 : new FilteredEntrySortedMap<K, V>(checkNotNull(unfiltered), entryPredicate); 1976 } 1977 1978 /** 1979 * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when 1980 * filtering a filtered map. 1981 */ 1982 private static <K, V> Map<K, V> filterFiltered(AbstractFilteredMap<K, V> map, 1983 Predicate<? super Entry<K, V>> entryPredicate) { 1984 Predicate<Entry<K, V>> predicate = 1985 Predicates.and(map.predicate, entryPredicate); 1986 return new FilteredEntryMap<K, V>(map.unfiltered, predicate); 1987 } 1988 1989 private abstract static class AbstractFilteredMap<K, V> 1990 extends AbstractMap<K, V> { 1991 final Map<K, V> unfiltered; 1992 final Predicate<? super Entry<K, V>> predicate; 1993 1994 AbstractFilteredMap( 1995 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> predicate) { 1996 this.unfiltered = unfiltered; 1997 this.predicate = predicate; 1998 } 1999 2000 boolean apply(Object key, V value) { 2001 // This method is called only when the key is in the map, implying that 2002 // key is a K. 2003 @SuppressWarnings("unchecked") 2004 K k = (K) key; 2005 return predicate.apply(Maps.immutableEntry(k, value)); 2006 } 2007 2008 @Override public V put(K key, V value) { 2009 checkArgument(apply(key, value)); 2010 return unfiltered.put(key, value); 2011 } 2012 2013 @Override public void putAll(Map<? extends K, ? extends V> map) { 2014 for (Entry<? extends K, ? extends V> entry : map.entrySet()) { 2015 checkArgument(apply(entry.getKey(), entry.getValue())); 2016 } 2017 unfiltered.putAll(map); 2018 } 2019 2020 @Override public boolean containsKey(Object key) { 2021 return unfiltered.containsKey(key) && apply(key, unfiltered.get(key)); 2022 } 2023 2024 @Override public V get(Object key) { 2025 V value = unfiltered.get(key); 2026 return ((value != null) && apply(key, value)) ? value : null; 2027 } 2028 2029 @Override public boolean isEmpty() { 2030 return entrySet().isEmpty(); 2031 } 2032 2033 @Override public V remove(Object key) { 2034 return containsKey(key) ? unfiltered.remove(key) : null; 2035 } 2036 2037 Collection<V> values; 2038 2039 @Override public Collection<V> values() { 2040 Collection<V> result = values; 2041 return (result == null) ? values = new Values() : result; 2042 } 2043 2044 class Values extends AbstractCollection<V> { 2045 @Override public Iterator<V> iterator() { 2046 final Iterator<Entry<K, V>> entryIterator = entrySet().iterator(); 2047 return new UnmodifiableIterator<V>() { 2048 @Override 2049 public boolean hasNext() { 2050 return entryIterator.hasNext(); 2051 } 2052 2053 @Override 2054 public V next() { 2055 return entryIterator.next().getValue(); 2056 } 2057 }; 2058 } 2059 2060 @Override public int size() { 2061 return entrySet().size(); 2062 } 2063 2064 @Override public void clear() { 2065 entrySet().clear(); 2066 } 2067 2068 @Override public boolean isEmpty() { 2069 return entrySet().isEmpty(); 2070 } 2071 2072 @Override public boolean remove(Object o) { 2073 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator(); 2074 while (iterator.hasNext()) { 2075 Entry<K, V> entry = iterator.next(); 2076 if (Objects.equal(o, entry.getValue()) && predicate.apply(entry)) { 2077 iterator.remove(); 2078 return true; 2079 } 2080 } 2081 return false; 2082 } 2083 2084 @Override public boolean removeAll(Collection<?> collection) { 2085 checkNotNull(collection); 2086 boolean changed = false; 2087 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator(); 2088 while (iterator.hasNext()) { 2089 Entry<K, V> entry = iterator.next(); 2090 if (collection.contains(entry.getValue()) && predicate.apply(entry)) { 2091 iterator.remove(); 2092 changed = true; 2093 } 2094 } 2095 return changed; 2096 } 2097 2098 @Override public boolean retainAll(Collection<?> collection) { 2099 checkNotNull(collection); 2100 boolean changed = false; 2101 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator(); 2102 while (iterator.hasNext()) { 2103 Entry<K, V> entry = iterator.next(); 2104 if (!collection.contains(entry.getValue()) 2105 && predicate.apply(entry)) { 2106 iterator.remove(); 2107 changed = true; 2108 } 2109 } 2110 return changed; 2111 } 2112 2113 @Override public Object[] toArray() { 2114 // creating an ArrayList so filtering happens once 2115 return Lists.newArrayList(iterator()).toArray(); 2116 } 2117 2118 @Override public <T> T[] toArray(T[] array) { 2119 return Lists.newArrayList(iterator()).toArray(array); 2120 } 2121 } 2122 } 2123 /** 2124 * Support {@code clear()}, {@code removeAll()}, and {@code retainAll()} when 2125 * filtering a filtered sorted map. 2126 */ 2127 private static <K, V> SortedMap<K, V> filterFiltered( 2128 FilteredEntrySortedMap<K, V> map, 2129 Predicate<? super Entry<K, V>> entryPredicate) { 2130 Predicate<Entry<K, V>> predicate 2131 = Predicates.and(map.predicate, entryPredicate); 2132 return new FilteredEntrySortedMap<K, V>(map.sortedMap(), predicate); 2133 } 2134 2135 private static class FilteredEntrySortedMap<K, V> 2136 extends FilteredEntryMap<K, V> implements SortedMap<K, V> { 2137 2138 FilteredEntrySortedMap(SortedMap<K, V> unfiltered, 2139 Predicate<? super Entry<K, V>> entryPredicate) { 2140 super(unfiltered, entryPredicate); 2141 } 2142 2143 SortedMap<K, V> sortedMap() { 2144 return (SortedMap<K, V>) unfiltered; 2145 } 2146 2147 @Override public Comparator<? super K> comparator() { 2148 return sortedMap().comparator(); 2149 } 2150 2151 @Override public K firstKey() { 2152 // correctly throws NoSuchElementException when filtered map is empty. 2153 return keySet().iterator().next(); 2154 } 2155 2156 @Override public K lastKey() { 2157 SortedMap<K, V> headMap = sortedMap(); 2158 while (true) { 2159 // correctly throws NoSuchElementException when filtered map is empty. 2160 K key = headMap.lastKey(); 2161 if (apply(key, unfiltered.get(key))) { 2162 return key; 2163 } 2164 headMap = sortedMap().headMap(key); 2165 } 2166 } 2167 2168 @Override public SortedMap<K, V> headMap(K toKey) { 2169 return new FilteredEntrySortedMap<K, V>(sortedMap().headMap(toKey), predicate); 2170 } 2171 2172 @Override public SortedMap<K, V> subMap(K fromKey, K toKey) { 2173 return new FilteredEntrySortedMap<K, V>( 2174 sortedMap().subMap(fromKey, toKey), predicate); 2175 } 2176 2177 @Override public SortedMap<K, V> tailMap(K fromKey) { 2178 return new FilteredEntrySortedMap<K, V>( 2179 sortedMap().tailMap(fromKey), predicate); 2180 } 2181 } 2182 2183 private static class FilteredKeyMap<K, V> extends AbstractFilteredMap<K, V> { 2184 Predicate<? super K> keyPredicate; 2185 2186 FilteredKeyMap(Map<K, V> unfiltered, Predicate<? super K> keyPredicate, 2187 Predicate<Entry<K, V>> entryPredicate) { 2188 super(unfiltered, entryPredicate); 2189 this.keyPredicate = keyPredicate; 2190 } 2191 2192 Set<Entry<K, V>> entrySet; 2193 2194 @Override public Set<Entry<K, V>> entrySet() { 2195 Set<Entry<K, V>> result = entrySet; 2196 return (result == null) 2197 ? entrySet = Sets.filter(unfiltered.entrySet(), predicate) 2198 : result; 2199 } 2200 2201 Set<K> keySet; 2202 2203 @Override public Set<K> keySet() { 2204 Set<K> result = keySet; 2205 return (result == null) 2206 ? keySet = Sets.filter(unfiltered.keySet(), keyPredicate) 2207 : result; 2208 } 2209 2210 // The cast is called only when the key is in the unfiltered map, implying 2211 // that key is a K. 2212 @Override 2213 @SuppressWarnings("unchecked") 2214 public boolean containsKey(Object key) { 2215 return unfiltered.containsKey(key) && keyPredicate.apply((K) key); 2216 } 2217 } 2218 2219 static class FilteredEntryMap<K, V> extends AbstractFilteredMap<K, V> { 2220 /** 2221 * Entries in this set satisfy the predicate, but they don't validate the 2222 * input to {@code Entry.setValue()}. 2223 */ 2224 final Set<Entry<K, V>> filteredEntrySet; 2225 2226 FilteredEntryMap( 2227 Map<K, V> unfiltered, Predicate<? super Entry<K, V>> entryPredicate) { 2228 super(unfiltered, entryPredicate); 2229 filteredEntrySet = Sets.filter(unfiltered.entrySet(), predicate); 2230 } 2231 2232 Set<Entry<K, V>> entrySet; 2233 2234 @Override public Set<Entry<K, V>> entrySet() { 2235 Set<Entry<K, V>> result = entrySet; 2236 return (result == null) ? entrySet = new EntrySet() : result; 2237 } 2238 2239 private class EntrySet extends ForwardingSet<Entry<K, V>> { 2240 @Override protected Set<Entry<K, V>> delegate() { 2241 return filteredEntrySet; 2242 } 2243 2244 @Override public Iterator<Entry<K, V>> iterator() { 2245 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator(); 2246 return new UnmodifiableIterator<Entry<K, V>>() { 2247 @Override 2248 public boolean hasNext() { 2249 return iterator.hasNext(); 2250 } 2251 2252 @Override 2253 public Entry<K, V> next() { 2254 final Entry<K, V> entry = iterator.next(); 2255 return new ForwardingMapEntry<K, V>() { 2256 @Override protected Entry<K, V> delegate() { 2257 return entry; 2258 } 2259 2260 @Override public V setValue(V value) { 2261 checkArgument(apply(entry.getKey(), value)); 2262 return super.setValue(value); 2263 } 2264 }; 2265 } 2266 }; 2267 } 2268 } 2269 2270 Set<K> keySet; 2271 2272 @Override public Set<K> keySet() { 2273 Set<K> result = keySet; 2274 return (result == null) ? keySet = new KeySet() : result; 2275 } 2276 2277 private class KeySet extends Sets.ImprovedAbstractSet<K> { 2278 @Override public Iterator<K> iterator() { 2279 final Iterator<Entry<K, V>> iterator = filteredEntrySet.iterator(); 2280 return new UnmodifiableIterator<K>() { 2281 @Override 2282 public boolean hasNext() { 2283 return iterator.hasNext(); 2284 } 2285 2286 @Override 2287 public K next() { 2288 return iterator.next().getKey(); 2289 } 2290 }; 2291 } 2292 2293 @Override public int size() { 2294 return filteredEntrySet.size(); 2295 } 2296 2297 @Override public void clear() { 2298 filteredEntrySet.clear(); 2299 } 2300 2301 @Override public boolean contains(Object o) { 2302 return containsKey(o); 2303 } 2304 2305 @Override public boolean remove(Object o) { 2306 if (containsKey(o)) { 2307 unfiltered.remove(o); 2308 return true; 2309 } 2310 return false; 2311 } 2312 2313 @Override public boolean retainAll(Collection<?> collection) { 2314 checkNotNull(collection); // for GWT 2315 boolean changed = false; 2316 Iterator<Entry<K, V>> iterator = unfiltered.entrySet().iterator(); 2317 while (iterator.hasNext()) { 2318 Entry<K, V> entry = iterator.next(); 2319 if (predicate.apply(entry) && !collection.contains(entry.getKey())) { 2320 iterator.remove(); 2321 changed = true; 2322 } 2323 } 2324 return changed; 2325 } 2326 2327 @Override public Object[] toArray() { 2328 // creating an ArrayList so filtering happens once 2329 return Lists.newArrayList(iterator()).toArray(); 2330 } 2331 2332 @Override public <T> T[] toArray(T[] array) { 2333 return Lists.newArrayList(iterator()).toArray(array); 2334 } 2335 } 2336 } 2337 2338 /** 2339 * Returns an unmodifiable view of the specified navigable map. Query operations on the returned 2340 * map read through to the specified map, and attempts to modify the returned map, whether direct 2341 * or via its views, result in an {@code UnsupportedOperationException}. 2342 * 2343 * <p>The returned navigable map will be serializable if the specified navigable map is 2344 * serializable. 2345 * 2346 * @param map the navigable map for which an unmodifiable view is to be returned 2347 * @return an unmodifiable view of the specified navigable map 2348 * @since 12.0 2349 */ 2350 @GwtIncompatible("NavigableMap") 2351 public static <K, V> NavigableMap<K, V> unmodifiableNavigableMap(NavigableMap<K, V> map) { 2352 checkNotNull(map); 2353 if (map instanceof UnmodifiableNavigableMap) { 2354 return map; 2355 } else { 2356 return new UnmodifiableNavigableMap<K, V>(map); 2357 } 2358 } 2359 2360 @Nullable private static <K, V> Entry<K, V> unmodifiableOrNull(@Nullable Entry<K, V> entry) { 2361 return (entry == null) ? null : Maps.unmodifiableEntry(entry); 2362 } 2363 2364 @GwtIncompatible("NavigableMap") 2365 static class UnmodifiableNavigableMap<K, V> 2366 extends ForwardingSortedMap<K, V> implements NavigableMap<K, V>, Serializable { 2367 private final NavigableMap<K, V> delegate; 2368 2369 UnmodifiableNavigableMap(NavigableMap<K, V> delegate) { 2370 this.delegate = delegate; 2371 } 2372 2373 @Override 2374 protected SortedMap<K, V> delegate() { 2375 return Collections.unmodifiableSortedMap(delegate); 2376 } 2377 2378 @Override 2379 public Entry<K, V> lowerEntry(K key) { 2380 return unmodifiableOrNull(delegate.lowerEntry(key)); 2381 } 2382 2383 @Override 2384 public K lowerKey(K key) { 2385 return delegate.lowerKey(key); 2386 } 2387 2388 @Override 2389 public Entry<K, V> floorEntry(K key) { 2390 return unmodifiableOrNull(delegate.floorEntry(key)); 2391 } 2392 2393 @Override 2394 public K floorKey(K key) { 2395 return delegate.floorKey(key); 2396 } 2397 2398 @Override 2399 public Entry<K, V> ceilingEntry(K key) { 2400 return unmodifiableOrNull(delegate.ceilingEntry(key)); 2401 } 2402 2403 @Override 2404 public K ceilingKey(K key) { 2405 return delegate.ceilingKey(key); 2406 } 2407 2408 @Override 2409 public Entry<K, V> higherEntry(K key) { 2410 return unmodifiableOrNull(delegate.higherEntry(key)); 2411 } 2412 2413 @Override 2414 public K higherKey(K key) { 2415 return delegate.higherKey(key); 2416 } 2417 2418 @Override 2419 public Entry<K, V> firstEntry() { 2420 return unmodifiableOrNull(delegate.firstEntry()); 2421 } 2422 2423 @Override 2424 public Entry<K, V> lastEntry() { 2425 return unmodifiableOrNull(delegate.lastEntry()); 2426 } 2427 2428 @Override 2429 public final Entry<K, V> pollFirstEntry() { 2430 throw new UnsupportedOperationException(); 2431 } 2432 2433 @Override 2434 public final Entry<K, V> pollLastEntry() { 2435 throw new UnsupportedOperationException(); 2436 } 2437 2438 private transient UnmodifiableNavigableMap<K, V> descendingMap; 2439 2440 @Override 2441 public NavigableMap<K, V> descendingMap() { 2442 UnmodifiableNavigableMap<K, V> result = descendingMap; 2443 if (result == null) { 2444 descendingMap = result = new UnmodifiableNavigableMap<K, V>(delegate.descendingMap()); 2445 result.descendingMap = this; 2446 } 2447 return result; 2448 } 2449 2450 @Override 2451 public Set<K> keySet() { 2452 return navigableKeySet(); 2453 } 2454 2455 @Override 2456 public NavigableSet<K> navigableKeySet() { 2457 return Sets.unmodifiableNavigableSet(delegate.navigableKeySet()); 2458 } 2459 2460 @Override 2461 public NavigableSet<K> descendingKeySet() { 2462 return Sets.unmodifiableNavigableSet(delegate.descendingKeySet()); 2463 } 2464 2465 @Override 2466 public SortedMap<K, V> subMap(K fromKey, K toKey) { 2467 return subMap(fromKey, true, toKey, false); 2468 } 2469 2470 @Override 2471 public SortedMap<K, V> headMap(K toKey) { 2472 return headMap(toKey, false); 2473 } 2474 2475 @Override 2476 public SortedMap<K, V> tailMap(K fromKey) { 2477 return tailMap(fromKey, true); 2478 } 2479 2480 @Override 2481 public 2482 NavigableMap<K, V> 2483 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 2484 return Maps.unmodifiableNavigableMap(delegate.subMap( 2485 fromKey, 2486 fromInclusive, 2487 toKey, 2488 toInclusive)); 2489 } 2490 2491 @Override 2492 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) { 2493 return Maps.unmodifiableNavigableMap(delegate.headMap(toKey, inclusive)); 2494 } 2495 2496 @Override 2497 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { 2498 return Maps.unmodifiableNavigableMap(delegate.tailMap(fromKey, inclusive)); 2499 } 2500 } 2501 2502 /** 2503 * Returns a synchronized (thread-safe) navigable map backed by the specified 2504 * navigable map. In order to guarantee serial access, it is critical that 2505 * <b>all</b> access to the backing navigable map is accomplished 2506 * through the returned navigable map (or its views). 2507 * 2508 * <p>It is imperative that the user manually synchronize on the returned 2509 * navigable map when iterating over any of its collection views, or the 2510 * collections views of any of its {@code descendingMap}, {@code subMap}, 2511 * {@code headMap} or {@code tailMap} views. <pre> {@code 2512 * 2513 * NavigableMap<K, V> map = synchronizedNavigableMap(new TreeMap<K, V>()); 2514 * 2515 * // Needn't be in synchronized block 2516 * NavigableSet<K> set = map.navigableKeySet(); 2517 * 2518 * synchronized (map) { // Synchronizing on map, not set! 2519 * Iterator<K> it = set.iterator(); // Must be in synchronized block 2520 * while (it.hasNext()){ 2521 * foo(it.next()); 2522 * } 2523 * }}</pre> 2524 * 2525 * or: <pre> {@code 2526 * 2527 * NavigableMap<K, V> map = synchronizedNavigableMap(new TreeMap<K, V>()); 2528 * NavigableMap<K, V> map2 = map.subMap(foo, false, bar, true); 2529 * 2530 * // Needn't be in synchronized block 2531 * NavigableSet<K> set2 = map2.descendingKeySet(); 2532 * 2533 * synchronized (map) { // Synchronizing on map, not map2 or set2! 2534 * Iterator<K> it = set2.iterator(); // Must be in synchronized block 2535 * while (it.hasNext()){ 2536 * foo(it.next()); 2537 * } 2538 * }}</pre> 2539 * 2540 * Failure to follow this advice may result in non-deterministic behavior. 2541 * 2542 * <p>The returned navigable map will be serializable if the specified 2543 * navigable map is serializable. 2544 * 2545 * @param navigableMap the navigable map to be "wrapped" in a synchronized 2546 * navigable map. 2547 * @return a synchronized view of the specified navigable map. 2548 * @since 13.0 2549 */ 2550 @Beta 2551 @GwtIncompatible("NavigableMap") 2552 public static <K, V> NavigableMap<K, V> synchronizedNavigableMap( 2553 NavigableMap<K, V> navigableMap) { 2554 return Synchronized.navigableMap(navigableMap); 2555 } 2556 2557 /** 2558 * {@code AbstractMap} extension that implements {@link #isEmpty()} as {@code 2559 * entrySet().isEmpty()} instead of {@code size() == 0} to speed up 2560 * implementations where {@code size()} is O(n), and it delegates the {@code 2561 * isEmpty()} methods of its key set and value collection to this 2562 * implementation. 2563 */ 2564 @GwtCompatible 2565 abstract static class ImprovedAbstractMap<K, V> extends AbstractMap<K, V> { 2566 /** 2567 * Creates the entry set to be returned by {@link #entrySet()}. This method 2568 * is invoked at most once on a given map, at the time when {@code entrySet} 2569 * is first called. 2570 */ 2571 protected abstract Set<Entry<K, V>> createEntrySet(); 2572 2573 private Set<Entry<K, V>> entrySet; 2574 2575 @Override public Set<Entry<K, V>> entrySet() { 2576 Set<Entry<K, V>> result = entrySet; 2577 if (result == null) { 2578 entrySet = result = createEntrySet(); 2579 } 2580 return result; 2581 } 2582 2583 private Set<K> keySet; 2584 2585 @Override public Set<K> keySet() { 2586 Set<K> result = keySet; 2587 if (result == null) { 2588 return keySet = new KeySet<K, V>() { 2589 @Override Map<K, V> map() { 2590 return ImprovedAbstractMap.this; 2591 } 2592 }; 2593 } 2594 return result; 2595 } 2596 2597 private Collection<V> values; 2598 2599 @Override public Collection<V> values() { 2600 Collection<V> result = values; 2601 if (result == null) { 2602 return values = new Values<K, V>() { 2603 @Override Map<K, V> map() { 2604 return ImprovedAbstractMap.this; 2605 } 2606 }; 2607 } 2608 return result; 2609 } 2610 } 2611 2612 static final MapJoiner STANDARD_JOINER = 2613 Collections2.STANDARD_JOINER.withKeyValueSeparator("="); 2614 2615 /** 2616 * Delegates to {@link Map#get}. Returns {@code null} on {@code 2617 * ClassCastException}. 2618 */ 2619 static <V> V safeGet(Map<?, V> map, Object key) { 2620 try { 2621 return map.get(key); 2622 } catch (ClassCastException e) { 2623 return null; 2624 } 2625 } 2626 2627 /** 2628 * Delegates to {@link Map#containsKey}. Returns {@code false} on {@code 2629 * ClassCastException} 2630 */ 2631 static boolean safeContainsKey(Map<?, ?> map, Object key) { 2632 try { 2633 return map.containsKey(key); 2634 } catch (ClassCastException e) { 2635 return false; 2636 } 2637 } 2638 2639 /** 2640 * Implements {@code Collection.contains} safely for forwarding collections of 2641 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is 2642 * wrapped using {@link #unmodifiableEntry} to protect against a possible 2643 * nefarious equals method. 2644 * 2645 * <p>Note that {@code c} is the backing (delegate) collection, rather than 2646 * the forwarding collection. 2647 * 2648 * @param c the delegate (unwrapped) collection of map entries 2649 * @param o the object that might be contained in {@code c} 2650 * @return {@code true} if {@code c} contains {@code o} 2651 */ 2652 static <K, V> boolean containsEntryImpl(Collection<Entry<K, V>> c, Object o) { 2653 if (!(o instanceof Entry)) { 2654 return false; 2655 } 2656 return c.contains(unmodifiableEntry((Entry<?, ?>) o)); 2657 } 2658 2659 /** 2660 * Implements {@code Collection.remove} safely for forwarding collections of 2661 * map entries. If {@code o} is an instance of {@code Map.Entry}, it is 2662 * wrapped using {@link #unmodifiableEntry} to protect against a possible 2663 * nefarious equals method. 2664 * 2665 * <p>Note that {@code c} is backing (delegate) collection, rather than the 2666 * forwarding collection. 2667 * 2668 * @param c the delegate (unwrapped) collection of map entries 2669 * @param o the object to remove from {@code c} 2670 * @return {@code true} if {@code c} was changed 2671 */ 2672 static <K, V> boolean removeEntryImpl(Collection<Entry<K, V>> c, Object o) { 2673 if (!(o instanceof Entry)) { 2674 return false; 2675 } 2676 return c.remove(unmodifiableEntry((Entry<?, ?>) o)); 2677 } 2678 2679 /** 2680 * An implementation of {@link Map#equals}. 2681 */ 2682 static boolean equalsImpl(Map<?, ?> map, Object object) { 2683 if (map == object) { 2684 return true; 2685 } 2686 if (object instanceof Map) { 2687 Map<?, ?> o = (Map<?, ?>) object; 2688 return map.entrySet().equals(o.entrySet()); 2689 } 2690 return false; 2691 } 2692 2693 /** 2694 * An implementation of {@link Map#hashCode}. 2695 */ 2696 static int hashCodeImpl(Map<?, ?> map) { 2697 return Sets.hashCodeImpl(map.entrySet()); 2698 } 2699 2700 /** 2701 * An implementation of {@link Map#toString}. 2702 */ 2703 static String toStringImpl(Map<?, ?> map) { 2704 StringBuilder sb 2705 = Collections2.newStringBuilderForCollection(map.size()).append('{'); 2706 STANDARD_JOINER.appendTo(sb, map); 2707 return sb.append('}').toString(); 2708 } 2709 2710 /** 2711 * An implementation of {@link Map#putAll}. 2712 */ 2713 static <K, V> void putAllImpl( 2714 Map<K, V> self, Map<? extends K, ? extends V> map) { 2715 for (Map.Entry<? extends K, ? extends V> entry : map.entrySet()) { 2716 self.put(entry.getKey(), entry.getValue()); 2717 } 2718 } 2719 2720 /** 2721 * An admittedly inefficient implementation of {@link Map#containsKey}. 2722 */ 2723 static boolean containsKeyImpl(Map<?, ?> map, @Nullable Object key) { 2724 for (Entry<?, ?> entry : map.entrySet()) { 2725 if (Objects.equal(entry.getKey(), key)) { 2726 return true; 2727 } 2728 } 2729 return false; 2730 } 2731 2732 /** 2733 * An implementation of {@link Map#containsValue}. 2734 */ 2735 static boolean containsValueImpl(Map<?, ?> map, @Nullable Object value) { 2736 for (Entry<?, ?> entry : map.entrySet()) { 2737 if (Objects.equal(entry.getValue(), value)) { 2738 return true; 2739 } 2740 } 2741 return false; 2742 } 2743 2744 static <K, V> Iterator<K> keyIterator(Iterator<Entry<K, V>> entryIterator) { 2745 return new TransformedIterator<Entry<K, V>, K>(entryIterator) { 2746 @Override 2747 K transform(Entry<K, V> entry) { 2748 return entry.getKey(); 2749 } 2750 }; 2751 } 2752 2753 abstract static class KeySet<K, V> extends Sets.ImprovedAbstractSet<K> { 2754 abstract Map<K, V> map(); 2755 2756 @Override public Iterator<K> iterator() { 2757 return keyIterator(map().entrySet().iterator()); 2758 } 2759 2760 @Override public int size() { 2761 return map().size(); 2762 } 2763 2764 @Override public boolean isEmpty() { 2765 return map().isEmpty(); 2766 } 2767 2768 @Override public boolean contains(Object o) { 2769 return map().containsKey(o); 2770 } 2771 2772 @Override public boolean remove(Object o) { 2773 if (contains(o)) { 2774 map().remove(o); 2775 return true; 2776 } 2777 return false; 2778 } 2779 2780 @Override public void clear() { 2781 map().clear(); 2782 } 2783 } 2784 2785 @Nullable 2786 static <K> K keyOrNull(@Nullable Entry<K, ?> entry) { 2787 return (entry == null) ? null : entry.getKey(); 2788 } 2789 2790 @GwtIncompatible("NavigableMap") 2791 abstract static class NavigableKeySet<K, V> extends KeySet<K, V> implements NavigableSet<K> { 2792 @Override 2793 abstract NavigableMap<K, V> map(); 2794 2795 @Override 2796 public Comparator<? super K> comparator() { 2797 return map().comparator(); 2798 } 2799 2800 @Override 2801 public K first() { 2802 return map().firstKey(); 2803 } 2804 2805 @Override 2806 public K last() { 2807 return map().lastKey(); 2808 } 2809 2810 @Override 2811 public K lower(K e) { 2812 return map().lowerKey(e); 2813 } 2814 2815 @Override 2816 public K floor(K e) { 2817 return map().floorKey(e); 2818 } 2819 2820 @Override 2821 public K ceiling(K e) { 2822 return map().ceilingKey(e); 2823 } 2824 2825 @Override 2826 public K higher(K e) { 2827 return map().higherKey(e); 2828 } 2829 2830 @Override 2831 public K pollFirst() { 2832 return keyOrNull(map().pollFirstEntry()); 2833 } 2834 2835 @Override 2836 public K pollLast() { 2837 return keyOrNull(map().pollLastEntry()); 2838 } 2839 2840 @Override 2841 public NavigableSet<K> descendingSet() { 2842 return map().descendingKeySet(); 2843 } 2844 2845 @Override 2846 public Iterator<K> descendingIterator() { 2847 return descendingSet().iterator(); 2848 } 2849 2850 @Override 2851 public NavigableSet<K> subSet( 2852 K fromElement, 2853 boolean fromInclusive, 2854 K toElement, 2855 boolean toInclusive) { 2856 return map().subMap(fromElement, fromInclusive, toElement, toInclusive).navigableKeySet(); 2857 } 2858 2859 @Override 2860 public NavigableSet<K> headSet(K toElement, boolean inclusive) { 2861 return map().headMap(toElement, inclusive).navigableKeySet(); 2862 } 2863 2864 @Override 2865 public NavigableSet<K> tailSet(K fromElement, boolean inclusive) { 2866 return map().tailMap(fromElement, inclusive).navigableKeySet(); 2867 } 2868 2869 @Override 2870 public SortedSet<K> subSet(K fromElement, K toElement) { 2871 return subSet(fromElement, true, toElement, false); 2872 } 2873 2874 @Override 2875 public SortedSet<K> headSet(K toElement) { 2876 return headSet(toElement, false); 2877 } 2878 2879 @Override 2880 public SortedSet<K> tailSet(K fromElement) { 2881 return tailSet(fromElement, true); 2882 } 2883 } 2884 2885 static <K, V> Iterator<V> valueIterator(Iterator<Entry<K, V>> entryIterator) { 2886 return new TransformedIterator<Entry<K, V>, V>(entryIterator) { 2887 @Override 2888 V transform(Entry<K, V> entry) { 2889 return entry.getValue(); 2890 } 2891 }; 2892 } 2893 2894 static <K, V> UnmodifiableIterator<V> valueIterator( 2895 final UnmodifiableIterator<Entry<K, V>> entryIterator) { 2896 return new UnmodifiableIterator<V>() { 2897 @Override 2898 public boolean hasNext() { 2899 return entryIterator.hasNext(); 2900 } 2901 2902 @Override 2903 public V next() { 2904 return entryIterator.next().getValue(); 2905 } 2906 }; 2907 } 2908 2909 abstract static class Values<K, V> extends AbstractCollection<V> { 2910 abstract Map<K, V> map(); 2911 2912 @Override public Iterator<V> iterator() { 2913 return valueIterator(map().entrySet().iterator()); 2914 } 2915 2916 @Override public boolean remove(Object o) { 2917 try { 2918 return super.remove(o); 2919 } catch (UnsupportedOperationException e) { 2920 for (Entry<K, V> entry : map().entrySet()) { 2921 if (Objects.equal(o, entry.getValue())) { 2922 map().remove(entry.getKey()); 2923 return true; 2924 } 2925 } 2926 return false; 2927 } 2928 } 2929 2930 @Override public boolean removeAll(Collection<?> c) { 2931 try { 2932 return super.removeAll(checkNotNull(c)); 2933 } catch (UnsupportedOperationException e) { 2934 Set<K> toRemove = Sets.newHashSet(); 2935 for (Entry<K, V> entry : map().entrySet()) { 2936 if (c.contains(entry.getValue())) { 2937 toRemove.add(entry.getKey()); 2938 } 2939 } 2940 return map().keySet().removeAll(toRemove); 2941 } 2942 } 2943 2944 @Override public boolean retainAll(Collection<?> c) { 2945 try { 2946 return super.retainAll(checkNotNull(c)); 2947 } catch (UnsupportedOperationException e) { 2948 Set<K> toRetain = Sets.newHashSet(); 2949 for (Entry<K, V> entry : map().entrySet()) { 2950 if (c.contains(entry.getValue())) { 2951 toRetain.add(entry.getKey()); 2952 } 2953 } 2954 return map().keySet().retainAll(toRetain); 2955 } 2956 } 2957 2958 @Override public int size() { 2959 return map().size(); 2960 } 2961 2962 @Override public boolean isEmpty() { 2963 return map().isEmpty(); 2964 } 2965 2966 @Override public boolean contains(@Nullable Object o) { 2967 return map().containsValue(o); 2968 } 2969 2970 @Override public void clear() { 2971 map().clear(); 2972 } 2973 } 2974 2975 abstract static class EntrySet<K, V> 2976 extends Sets.ImprovedAbstractSet<Entry<K, V>> { 2977 abstract Map<K, V> map(); 2978 2979 @Override public int size() { 2980 return map().size(); 2981 } 2982 2983 @Override public void clear() { 2984 map().clear(); 2985 } 2986 2987 @Override public boolean contains(Object o) { 2988 if (o instanceof Entry) { 2989 Entry<?, ?> entry = (Entry<?, ?>) o; 2990 Object key = entry.getKey(); 2991 V value = map().get(key); 2992 return Objects.equal(value, entry.getValue()) 2993 && (value != null || map().containsKey(key)); 2994 } 2995 return false; 2996 } 2997 2998 @Override public boolean isEmpty() { 2999 return map().isEmpty(); 3000 } 3001 3002 @Override public boolean remove(Object o) { 3003 if (contains(o)) { 3004 Entry<?, ?> entry = (Entry<?, ?>) o; 3005 return map().keySet().remove(entry.getKey()); 3006 } 3007 return false; 3008 } 3009 3010 @Override public boolean removeAll(Collection<?> c) { 3011 try { 3012 return super.removeAll(checkNotNull(c)); 3013 } catch (UnsupportedOperationException e) { 3014 // if the iterators don't support remove 3015 boolean changed = true; 3016 for (Object o : c) { 3017 changed |= remove(o); 3018 } 3019 return changed; 3020 } 3021 } 3022 3023 @Override public boolean retainAll(Collection<?> c) { 3024 try { 3025 return super.retainAll(checkNotNull(c)); 3026 } catch (UnsupportedOperationException e) { 3027 // if the iterators don't support remove 3028 Set<Object> keys = Sets.newHashSetWithExpectedSize(c.size()); 3029 for (Object o : c) { 3030 if (contains(o)) { 3031 Entry<?, ?> entry = (Entry<?, ?>) o; 3032 keys.add(entry.getKey()); 3033 } 3034 } 3035 return map().keySet().retainAll(keys); 3036 } 3037 } 3038 } 3039 3040 @GwtIncompatible("NavigableMap") 3041 abstract static class DescendingMap<K, V> extends ForwardingMap<K, V> 3042 implements NavigableMap<K, V> { 3043 3044 abstract NavigableMap<K, V> forward(); 3045 3046 @Override 3047 protected final Map<K, V> delegate() { 3048 return forward(); 3049 } 3050 3051 private transient Comparator<? super K> comparator; 3052 3053 @SuppressWarnings("unchecked") 3054 @Override 3055 public Comparator<? super K> comparator() { 3056 Comparator<? super K> result = comparator; 3057 if (result == null) { 3058 Comparator<? super K> forwardCmp = forward().comparator(); 3059 if (forwardCmp == null) { 3060 forwardCmp = (Comparator) Ordering.natural(); 3061 } 3062 result = comparator = reverse(forwardCmp); 3063 } 3064 return result; 3065 } 3066 3067 // If we inline this, we get a javac error. 3068 private static <T> Ordering<T> reverse(Comparator<T> forward) { 3069 return Ordering.from(forward).reverse(); 3070 } 3071 3072 @Override 3073 public K firstKey() { 3074 return forward().lastKey(); 3075 } 3076 3077 @Override 3078 public K lastKey() { 3079 return forward().firstKey(); 3080 } 3081 3082 @Override 3083 public Entry<K, V> lowerEntry(K key) { 3084 return forward().higherEntry(key); 3085 } 3086 3087 @Override 3088 public K lowerKey(K key) { 3089 return forward().higherKey(key); 3090 } 3091 3092 @Override 3093 public Entry<K, V> floorEntry(K key) { 3094 return forward().ceilingEntry(key); 3095 } 3096 3097 @Override 3098 public K floorKey(K key) { 3099 return forward().ceilingKey(key); 3100 } 3101 3102 @Override 3103 public Entry<K, V> ceilingEntry(K key) { 3104 return forward().floorEntry(key); 3105 } 3106 3107 @Override 3108 public K ceilingKey(K key) { 3109 return forward().floorKey(key); 3110 } 3111 3112 @Override 3113 public Entry<K, V> higherEntry(K key) { 3114 return forward().lowerEntry(key); 3115 } 3116 3117 @Override 3118 public K higherKey(K key) { 3119 return forward().lowerKey(key); 3120 } 3121 3122 @Override 3123 public Entry<K, V> firstEntry() { 3124 return forward().lastEntry(); 3125 } 3126 3127 @Override 3128 public Entry<K, V> lastEntry() { 3129 return forward().firstEntry(); 3130 } 3131 3132 @Override 3133 public Entry<K, V> pollFirstEntry() { 3134 return forward().pollLastEntry(); 3135 } 3136 3137 @Override 3138 public Entry<K, V> pollLastEntry() { 3139 return forward().pollFirstEntry(); 3140 } 3141 3142 @Override 3143 public NavigableMap<K, V> descendingMap() { 3144 return forward(); 3145 } 3146 3147 private transient Set<Entry<K, V>> entrySet; 3148 3149 @Override 3150 public Set<Entry<K, V>> entrySet() { 3151 Set<Entry<K, V>> result = entrySet; 3152 return (result == null) ? entrySet = createEntrySet() : result; 3153 } 3154 3155 abstract Iterator<Entry<K, V>> entryIterator(); 3156 3157 Set<Entry<K, V>> createEntrySet() { 3158 return new EntrySet<K, V>() { 3159 3160 @Override 3161 Map<K, V> map() { 3162 return DescendingMap.this; 3163 } 3164 3165 @Override 3166 public Iterator<Entry<K, V>> iterator() { 3167 return entryIterator(); 3168 } 3169 }; 3170 } 3171 3172 @Override 3173 public Set<K> keySet() { 3174 return navigableKeySet(); 3175 } 3176 3177 private transient NavigableSet<K> navigableKeySet; 3178 3179 @Override 3180 public NavigableSet<K> navigableKeySet() { 3181 NavigableSet<K> result = navigableKeySet; 3182 if (result == null) { 3183 result = navigableKeySet = new NavigableKeySet<K, V>() { 3184 @Override 3185 NavigableMap<K, V> map() { 3186 return DescendingMap.this; 3187 } 3188 }; 3189 } 3190 return result; 3191 } 3192 3193 @Override 3194 public NavigableSet<K> descendingKeySet() { 3195 return forward().navigableKeySet(); 3196 } 3197 3198 @Override 3199 public 3200 NavigableMap<K, V> 3201 subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 3202 return forward().subMap(toKey, toInclusive, fromKey, fromInclusive).descendingMap(); 3203 } 3204 3205 @Override 3206 public NavigableMap<K, V> headMap(K toKey, boolean inclusive) { 3207 return forward().tailMap(toKey, inclusive).descendingMap(); 3208 } 3209 3210 @Override 3211 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive) { 3212 return forward().headMap(fromKey, inclusive).descendingMap(); 3213 } 3214 3215 @Override 3216 public SortedMap<K, V> subMap(K fromKey, K toKey) { 3217 return subMap(fromKey, true, toKey, false); 3218 } 3219 3220 @Override 3221 public SortedMap<K, V> headMap(K toKey) { 3222 return headMap(toKey, false); 3223 } 3224 3225 @Override 3226 public SortedMap<K, V> tailMap(K fromKey) { 3227 return tailMap(fromKey, true); 3228 } 3229 3230 @Override 3231 public Collection<V> values() { 3232 return new Values<K, V>() { 3233 @Override 3234 Map<K, V> map() { 3235 return DescendingMap.this; 3236 } 3237 }; 3238 } 3239 } 3240 }