001/* 002 * Copyright (C) 2009 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect; 018 019import static com.google.common.base.Preconditions.checkArgument; 020import static com.google.common.base.Preconditions.checkNotNull; 021import static com.google.common.collect.CollectPreconditions.checkEntryNotNull; 022import static com.google.common.collect.Maps.keyOrNull; 023 024import com.google.common.annotations.Beta; 025import com.google.common.annotations.GwtCompatible; 026import com.google.errorprone.annotations.CanIgnoreReturnValue; 027import com.google.j2objc.annotations.WeakOuter; 028import java.util.AbstractMap; 029import java.util.Arrays; 030import java.util.Comparator; 031import java.util.Map; 032import java.util.NavigableMap; 033import java.util.SortedMap; 034import java.util.Spliterator; 035import java.util.TreeMap; 036import java.util.function.BiConsumer; 037import java.util.function.BinaryOperator; 038import java.util.function.Consumer; 039import java.util.function.Function; 040import java.util.stream.Collector; 041import java.util.stream.Collectors; 042import javax.annotation.Nullable; 043 044/** 045 * A {@link NavigableMap} whose contents will never change, with many other important properties 046 * detailed at {@link ImmutableCollection}. 047 * 048 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link 049 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with 050 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero 051 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting map will 052 * not correctly obey its specification. 053 * 054 * <p>See the Guava User Guide article on <a href= 055 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> 056 * immutable collections</a>. 057 * 058 * @author Jared Levy 059 * @author Louis Wasserman 060 * @since 2.0 (implements {@code NavigableMap} since 12.0) 061 */ 062@GwtCompatible(serializable = true, emulated = true) 063public final class ImmutableSortedMap<K, V> extends ImmutableSortedMapFauxverideShim<K, V> 064 implements NavigableMap<K, V> { 065 /** 066 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} 067 * whose keys and values are the result of applying the provided mapping functions to the input 068 * elements. The generated map is sorted by the specified comparator. 069 * 070 * <p>If the mapped keys contain duplicates (according to the specified comparator), an 071 * {@code IllegalArgumentException} is thrown when the collection operation is performed. 072 * (This differs from the {@code Collector} returned by 073 * {@link Collectors#toMap(Function, Function)}, which throws an {@code IllegalStateException}.) 074 * 075 * @since 21.0 076 */ 077 @Beta 078 public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap( 079 Comparator<? super K> comparator, 080 Function<? super T, ? extends K> keyFunction, 081 Function<? super T, ? extends V> valueFunction) { 082 return CollectCollectors.toImmutableSortedMap(comparator, keyFunction, valueFunction); 083 } 084 085 /** 086 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose 087 * keys and values are the result of applying the provided mapping functions to the input 088 * elements. 089 * 090 * <p>If the mapped keys contain duplicates (according to the comparator), the the values are 091 * merged using the specified merging function. Entries will appear in the encounter order of the 092 * first occurrence of the key. 093 * 094 * @since 21.0 095 */ 096 @Beta 097 public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap( 098 Comparator<? super K> comparator, 099 Function<? super T, ? extends K> keyFunction, 100 Function<? super T, ? extends V> valueFunction, 101 BinaryOperator<V> mergeFunction) { 102 checkNotNull(comparator); 103 checkNotNull(keyFunction); 104 checkNotNull(valueFunction); 105 checkNotNull(mergeFunction); 106 return Collectors.collectingAndThen( 107 Collectors.toMap( 108 keyFunction, valueFunction, mergeFunction, () -> new TreeMap<K, V>(comparator)), 109 ImmutableSortedMap::copyOfSorted); 110 } 111 112 /* 113 * TODO(kevinb): Confirm that ImmutableSortedMap is faster to construct and 114 * uses less memory than TreeMap; then say so in the class Javadoc. 115 */ 116 private static final Comparator<Comparable> NATURAL_ORDER = Ordering.natural(); 117 118 private static final ImmutableSortedMap<Comparable, Object> NATURAL_EMPTY_MAP = 119 new ImmutableSortedMap<>( 120 ImmutableSortedSet.emptySet(Ordering.natural()), ImmutableList.<Object>of()); 121 122 static <K, V> ImmutableSortedMap<K, V> emptyMap(Comparator<? super K> comparator) { 123 if (Ordering.natural().equals(comparator)) { 124 return of(); 125 } else { 126 return new ImmutableSortedMap<>( 127 ImmutableSortedSet.emptySet(comparator), ImmutableList.<V>of()); 128 } 129 } 130 131 /** 132 * Returns the empty sorted map. 133 */ 134 @SuppressWarnings("unchecked") 135 // unsafe, comparator() returns a comparator on the specified type 136 // TODO(kevinb): evaluate whether or not of().comparator() should return null 137 public static <K, V> ImmutableSortedMap<K, V> of() { 138 return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP; 139 } 140 141 /** 142 * Returns an immutable map containing a single entry. 143 */ 144 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(K k1, V v1) { 145 return of(Ordering.natural(), k1, v1); 146 } 147 148 /** 149 * Returns an immutable map containing a single entry. 150 */ 151 private static <K, V> ImmutableSortedMap<K, V> of(Comparator<? super K> comparator, K k1, V v1) { 152 return new ImmutableSortedMap<>( 153 new RegularImmutableSortedSet<K>(ImmutableList.of(k1), checkNotNull(comparator)), 154 ImmutableList.of(v1)); 155 } 156 157 private static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> ofEntries( 158 Entry<K, V>... entries) { 159 return fromEntries(Ordering.natural(), false, entries, entries.length); 160 } 161 162 /** 163 * Returns an immutable sorted map containing the given entries, sorted by the 164 * natural ordering of their keys. 165 * 166 * @throws IllegalArgumentException if the two keys are equal according to 167 * their natural ordering 168 */ 169 @SuppressWarnings("unchecked") 170 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 171 K k1, V v1, K k2, V v2) { 172 return ofEntries(entryOf(k1, v1), entryOf(k2, v2)); 173 } 174 175 /** 176 * Returns an immutable sorted map containing the given entries, sorted by the 177 * natural ordering of their keys. 178 * 179 * @throws IllegalArgumentException if any two keys are equal according to 180 * their natural ordering 181 */ 182 @SuppressWarnings("unchecked") 183 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 184 K k1, V v1, K k2, V v2, K k3, V v3) { 185 return ofEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3)); 186 } 187 188 /** 189 * Returns an immutable sorted map containing the given entries, sorted by the 190 * natural ordering of their keys. 191 * 192 * @throws IllegalArgumentException if any two keys are equal according to 193 * their natural ordering 194 */ 195 @SuppressWarnings("unchecked") 196 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 197 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 198 return ofEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4)); 199 } 200 201 /** 202 * Returns an immutable sorted map containing the given entries, sorted by the 203 * natural ordering of their keys. 204 * 205 * @throws IllegalArgumentException if any two keys are equal according to 206 * their natural ordering 207 */ 208 @SuppressWarnings("unchecked") 209 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of( 210 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 211 return ofEntries( 212 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5)); 213 } 214 215 /** 216 * Returns an immutable map containing the same entries as {@code map}, sorted 217 * by the natural ordering of the keys. 218 * 219 * <p>Despite the method name, this method attempts to avoid actually copying 220 * the data when it is safe to do so. The exact circumstances under which a 221 * copy will or will not be performed are undocumented and subject to change. 222 * 223 * <p>This method is not type-safe, as it may be called on a map with keys 224 * that are not mutually comparable. 225 * 226 * @throws ClassCastException if the keys in {@code map} are not mutually 227 * comparable 228 * @throws NullPointerException if any key or value in {@code map} is null 229 * @throws IllegalArgumentException if any two keys are equal according to 230 * their natural ordering 231 */ 232 public static <K, V> ImmutableSortedMap<K, V> copyOf(Map<? extends K, ? extends V> map) { 233 // Hack around K not being a subtype of Comparable. 234 // Unsafe, see ImmutableSortedSetFauxverideShim. 235 @SuppressWarnings("unchecked") 236 Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER; 237 return copyOfInternal(map, naturalOrder); 238 } 239 240 /** 241 * Returns an immutable map containing the same entries as {@code map}, with 242 * keys sorted by the provided comparator. 243 * 244 * <p>Despite the method name, this method attempts to avoid actually copying 245 * the data when it is safe to do so. The exact circumstances under which a 246 * copy will or will not be performed are undocumented and subject to change. 247 * 248 * @throws NullPointerException if any key or value in {@code map} is null 249 * @throws IllegalArgumentException if any two keys are equal according to the 250 * comparator 251 */ 252 public static <K, V> ImmutableSortedMap<K, V> copyOf( 253 Map<? extends K, ? extends V> map, Comparator<? super K> comparator) { 254 return copyOfInternal(map, checkNotNull(comparator)); 255 } 256 257 /** 258 * Returns an immutable map containing the given entries, with keys sorted 259 * by the provided comparator. 260 * 261 * <p>This method is not type-safe, as it may be called on a map with keys 262 * that are not mutually comparable. 263 * 264 * @throws NullPointerException if any key or value in {@code map} is null 265 * @throws IllegalArgumentException if any two keys are equal according to the 266 * comparator 267 * @since 19.0 268 */ 269 @Beta 270 public static <K, V> ImmutableSortedMap<K, V> copyOf( 271 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 272 // Hack around K not being a subtype of Comparable. 273 // Unsafe, see ImmutableSortedSetFauxverideShim. 274 @SuppressWarnings("unchecked") 275 Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER; 276 return copyOf(entries, naturalOrder); 277 } 278 279 /** 280 * Returns an immutable map containing the given entries, with keys sorted 281 * by the provided comparator. 282 * 283 * @throws NullPointerException if any key or value in {@code map} is null 284 * @throws IllegalArgumentException if any two keys are equal according to the 285 * comparator 286 * @since 19.0 287 */ 288 @Beta 289 public static <K, V> ImmutableSortedMap<K, V> copyOf( 290 Iterable<? extends Entry<? extends K, ? extends V>> entries, 291 Comparator<? super K> comparator) { 292 return fromEntries(checkNotNull(comparator), false, entries); 293 } 294 295 /** 296 * Returns an immutable map containing the same entries as the provided sorted 297 * map, with the same ordering. 298 * 299 * <p>Despite the method name, this method attempts to avoid actually copying 300 * the data when it is safe to do so. The exact circumstances under which a 301 * copy will or will not be performed are undocumented and subject to change. 302 * 303 * @throws NullPointerException if any key or value in {@code map} is null 304 */ 305 @SuppressWarnings("unchecked") 306 public static <K, V> ImmutableSortedMap<K, V> copyOfSorted(SortedMap<K, ? extends V> map) { 307 Comparator<? super K> comparator = map.comparator(); 308 if (comparator == null) { 309 // If map has a null comparator, the keys should have a natural ordering, 310 // even though K doesn't explicitly implement Comparable. 311 comparator = (Comparator<? super K>) NATURAL_ORDER; 312 } 313 if (map instanceof ImmutableSortedMap) { 314 // TODO(kevinb): Prove that this cast is safe, even though 315 // Collections.unmodifiableSortedMap requires the same key type. 316 @SuppressWarnings("unchecked") 317 ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map; 318 if (!kvMap.isPartialView()) { 319 return kvMap; 320 } 321 } 322 return fromEntries(comparator, true, map.entrySet()); 323 } 324 325 private static <K, V> ImmutableSortedMap<K, V> copyOfInternal( 326 Map<? extends K, ? extends V> map, Comparator<? super K> comparator) { 327 boolean sameComparator = false; 328 if (map instanceof SortedMap) { 329 SortedMap<?, ?> sortedMap = (SortedMap<?, ?>) map; 330 Comparator<?> comparator2 = sortedMap.comparator(); 331 sameComparator = 332 (comparator2 == null) 333 ? comparator == NATURAL_ORDER 334 : comparator.equals(comparator2); 335 } 336 337 if (sameComparator && (map instanceof ImmutableSortedMap)) { 338 // TODO(kevinb): Prove that this cast is safe, even though 339 // Collections.unmodifiableSortedMap requires the same key type. 340 @SuppressWarnings("unchecked") 341 ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map; 342 if (!kvMap.isPartialView()) { 343 return kvMap; 344 } 345 } 346 return fromEntries(comparator, sameComparator, map.entrySet()); 347 } 348 349 /** 350 * Accepts a collection of possibly-null entries. If {@code sameComparator}, then it is assumed 351 * that they do not need to be sorted or checked for dupes. 352 */ 353 private static <K, V> ImmutableSortedMap<K, V> fromEntries( 354 Comparator<? super K> comparator, 355 boolean sameComparator, 356 Iterable<? extends Entry<? extends K, ? extends V>> entries) { 357 // "adding" type params to an array of a raw type should be safe as 358 // long as no one can ever cast that same array instance back to a 359 // raw type. 360 @SuppressWarnings("unchecked") 361 Entry<K, V>[] entryArray = (Entry[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY); 362 return fromEntries(comparator, sameComparator, entryArray, entryArray.length); 363 } 364 365 private static <K, V> ImmutableSortedMap<K, V> fromEntries( 366 final Comparator<? super K> comparator, 367 boolean sameComparator, 368 Entry<K, V>[] entryArray, 369 int size) { 370 switch (size) { 371 case 0: 372 return emptyMap(comparator); 373 case 1: 374 return ImmutableSortedMap.<K, V>of( 375 comparator, entryArray[0].getKey(), entryArray[0].getValue()); 376 default: 377 Object[] keys = new Object[size]; 378 Object[] values = new Object[size]; 379 if (sameComparator) { 380 // Need to check for nulls, but don't need to sort or validate. 381 for (int i = 0; i < size; i++) { 382 Object key = entryArray[i].getKey(); 383 Object value = entryArray[i].getValue(); 384 checkEntryNotNull(key, value); 385 keys[i] = key; 386 values[i] = value; 387 } 388 } else { 389 // Need to sort and check for nulls and dupes. 390 // Inline the Comparator implementation rather than transforming with a Function 391 // to save code size. 392 Arrays.sort( 393 entryArray, 394 0, 395 size, 396 new Comparator<Entry<K, V>>() { 397 @Override 398 public int compare(Entry<K, V> e1, Entry<K, V> e2) { 399 return comparator.compare(e1.getKey(), e2.getKey()); 400 } 401 }); 402 K prevKey = entryArray[0].getKey(); 403 keys[0] = prevKey; 404 values[0] = entryArray[0].getValue(); 405 for (int i = 1; i < size; i++) { 406 K key = entryArray[i].getKey(); 407 V value = entryArray[i].getValue(); 408 checkEntryNotNull(key, value); 409 keys[i] = key; 410 values[i] = value; 411 checkNoConflict( 412 comparator.compare(prevKey, key) != 0, "key", entryArray[i - 1], entryArray[i]); 413 prevKey = key; 414 } 415 } 416 return new ImmutableSortedMap<>( 417 new RegularImmutableSortedSet<K>(new RegularImmutableList<K>(keys), comparator), 418 new RegularImmutableList<V>(values)); 419 } 420 } 421 422 /** 423 * Returns a builder that creates immutable sorted maps whose keys are 424 * ordered by their natural ordering. The sorted maps use {@link 425 * Ordering#natural()} as the comparator. 426 */ 427 public static <K extends Comparable<?>, V> Builder<K, V> naturalOrder() { 428 return new Builder<>(Ordering.natural()); 429 } 430 431 /** 432 * Returns a builder that creates immutable sorted maps with an explicit 433 * comparator. If the comparator has a more general type than the map's keys, 434 * such as creating a {@code SortedMap<Integer, String>} with a {@code 435 * Comparator<Number>}, use the {@link Builder} constructor instead. 436 * 437 * @throws NullPointerException if {@code comparator} is null 438 */ 439 public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) { 440 return new Builder<>(comparator); 441 } 442 443 /** 444 * Returns a builder that creates immutable sorted maps whose keys are 445 * ordered by the reverse of their natural ordering. 446 */ 447 public static <K extends Comparable<?>, V> Builder<K, V> reverseOrder() { 448 return new Builder<>(Ordering.natural().reverse()); 449 } 450 451 /** 452 * A builder for creating immutable sorted map instances, especially {@code 453 * public static final} maps ("constant maps"). Example: <pre> {@code 454 * 455 * static final ImmutableSortedMap<Integer, String> INT_TO_WORD = 456 * new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural()) 457 * .put(1, "one") 458 * .put(2, "two") 459 * .put(3, "three") 460 * .build();}</pre> 461 * 462 * <p>For <i>small</i> immutable sorted maps, the {@code ImmutableSortedMap.of()} 463 * methods are even more convenient. 464 * 465 * <p>Builder instances can be reused - it is safe to call {@link #build} 466 * multiple times to build multiple maps in series. Each map is a superset of 467 * the maps created before it. 468 * 469 * @since 2.0 470 */ 471 public static class Builder<K, V> extends ImmutableMap.Builder<K, V> { 472 private final Comparator<? super K> comparator; 473 474 /** 475 * Creates a new builder. The returned builder is equivalent to the builder 476 * generated by {@link ImmutableSortedMap#orderedBy}. 477 */ 478 @SuppressWarnings("unchecked") 479 public Builder(Comparator<? super K> comparator) { 480 this.comparator = checkNotNull(comparator); 481 } 482 483 /** 484 * Associates {@code key} with {@code value} in the built map. Duplicate 485 * keys, according to the comparator (which might be the keys' natural 486 * order), are not allowed, and will cause {@link #build} to fail. 487 */ 488 @CanIgnoreReturnValue 489 @Override 490 public Builder<K, V> put(K key, V value) { 491 super.put(key, value); 492 return this; 493 } 494 495 /** 496 * Adds the given {@code entry} to the map, making it immutable if 497 * necessary. Duplicate keys, according to the comparator (which might be 498 * the keys' natural order), are not allowed, and will cause {@link #build} 499 * to fail. 500 * 501 * @since 11.0 502 */ 503 @CanIgnoreReturnValue 504 @Override 505 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) { 506 super.put(entry); 507 return this; 508 } 509 510 /** 511 * Associates all of the given map's keys and values in the built map. 512 * Duplicate keys, according to the comparator (which might be the keys' 513 * natural order), are not allowed, and will cause {@link #build} to fail. 514 * 515 * @throws NullPointerException if any key or value in {@code map} is null 516 */ 517 @CanIgnoreReturnValue 518 @Override 519 public Builder<K, V> putAll(Map<? extends K, ? extends V> map) { 520 super.putAll(map); 521 return this; 522 } 523 524 /** 525 * Adds all the given entries to the built map. Duplicate keys, according 526 * to the comparator (which might be the keys' natural order), are not 527 * allowed, and will cause {@link #build} to fail. 528 * 529 * @throws NullPointerException if any key, value, or entry is null 530 * @since 19.0 531 */ 532 @CanIgnoreReturnValue 533 @Beta 534 @Override 535 public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) { 536 super.putAll(entries); 537 return this; 538 } 539 540 /** 541 * Throws an {@code UnsupportedOperationException}. 542 * 543 * @since 19.0 544 * @deprecated Unsupported by ImmutableSortedMap.Builder. 545 */ 546 @CanIgnoreReturnValue 547 @Beta 548 @Override 549 @Deprecated 550 public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) { 551 throw new UnsupportedOperationException("Not available on ImmutableSortedMap.Builder"); 552 } 553 554 @Override 555 Builder<K, V> combine(ImmutableMap.Builder<K, V> other) { 556 super.combine(other); 557 return this; 558 } 559 560 /** 561 * Returns a newly-created immutable sorted map. 562 * 563 * @throws IllegalArgumentException if any two keys are equal according to 564 * the comparator (which might be the keys' natural order) 565 */ 566 @Override 567 public ImmutableSortedMap<K, V> build() { 568 switch (size) { 569 case 0: 570 return emptyMap(comparator); 571 case 1: 572 return of(comparator, entries[0].getKey(), entries[0].getValue()); 573 default: 574 return fromEntries(comparator, false, entries, size); 575 } 576 } 577 } 578 579 private final transient RegularImmutableSortedSet<K> keySet; 580 private final transient ImmutableList<V> valueList; 581 private transient ImmutableSortedMap<K, V> descendingMap; 582 583 ImmutableSortedMap(RegularImmutableSortedSet<K> keySet, ImmutableList<V> valueList) { 584 this(keySet, valueList, null); 585 } 586 587 ImmutableSortedMap( 588 RegularImmutableSortedSet<K> keySet, 589 ImmutableList<V> valueList, 590 ImmutableSortedMap<K, V> descendingMap) { 591 this.keySet = keySet; 592 this.valueList = valueList; 593 this.descendingMap = descendingMap; 594 } 595 596 @Override 597 public int size() { 598 return valueList.size(); 599 } 600 601 @Override 602 public void forEach(BiConsumer<? super K, ? super V> action) { 603 checkNotNull(action); 604 ImmutableList<K> keyList = keySet.asList(); 605 for (int i = 0; i < size(); i++) { 606 action.accept(keyList.get(i), valueList.get(i)); 607 } 608 } 609 610 @Override 611 public V get(@Nullable Object key) { 612 int index = keySet.indexOf(key); 613 return (index == -1) ? null : valueList.get(index); 614 } 615 616 @Override 617 boolean isPartialView() { 618 return keySet.isPartialView() || valueList.isPartialView(); 619 } 620 621 /** 622 * Returns an immutable set of the mappings in this map, sorted by the key 623 * ordering. 624 */ 625 @Override 626 public ImmutableSet<Entry<K, V>> entrySet() { 627 return super.entrySet(); 628 } 629 630 @Override 631 ImmutableSet<Entry<K, V>> createEntrySet() { 632 @WeakOuter 633 class EntrySet extends ImmutableMapEntrySet<K, V> { 634 @Override 635 public UnmodifiableIterator<Entry<K, V>> iterator() { 636 return asList().iterator(); 637 } 638 639 @Override 640 public Spliterator<Entry<K, V>> spliterator() { 641 return asList().spliterator(); 642 } 643 644 @Override 645 public void forEach(Consumer<? super Entry<K, V>> action) { 646 asList().forEach(action); 647 } 648 649 @Override 650 ImmutableList<Entry<K, V>> createAsList() { 651 return new ImmutableAsList<Entry<K, V>>() { 652 @Override 653 public Entry<K, V> get(int index) { 654 return new AbstractMap.SimpleImmutableEntry<>( 655 keySet.asList().get(index), valueList.get(index)); 656 } 657 658 @Override 659 public Spliterator<Entry<K, V>> spliterator() { 660 return CollectSpliterators.indexed( 661 size(), ImmutableSet.SPLITERATOR_CHARACTERISTICS, this::get); 662 } 663 664 @Override 665 ImmutableCollection<Entry<K, V>> delegateCollection() { 666 return EntrySet.this; 667 } 668 }; 669 } 670 671 @Override 672 ImmutableMap<K, V> map() { 673 return ImmutableSortedMap.this; 674 } 675 } 676 return isEmpty() ? ImmutableSet.<Entry<K, V>>of() : new EntrySet(); 677 } 678 679 /** 680 * Returns an immutable sorted set of the keys in this map. 681 */ 682 @Override 683 public ImmutableSortedSet<K> keySet() { 684 return keySet; 685 } 686 687 @Override 688 ImmutableSet<K> createKeySet() { 689 throw new AssertionError("should never be called"); 690 } 691 692 /** 693 * Returns an immutable collection of the values in this map, sorted by the 694 * ordering of the corresponding keys. 695 */ 696 @Override 697 public ImmutableCollection<V> values() { 698 return valueList; 699 } 700 701 @Override 702 ImmutableCollection<V> createValues() { 703 throw new AssertionError("should never be called"); 704 } 705 706 /** 707 * Returns the comparator that orders the keys, which is 708 * {@link Ordering#natural()} when the natural ordering of the keys is used. 709 * Note that its behavior is not consistent with {@link TreeMap#comparator()}, 710 * which returns {@code null} to indicate natural ordering. 711 */ 712 @Override 713 public Comparator<? super K> comparator() { 714 return keySet().comparator(); 715 } 716 717 @Override 718 public K firstKey() { 719 return keySet().first(); 720 } 721 722 @Override 723 public K lastKey() { 724 return keySet().last(); 725 } 726 727 private ImmutableSortedMap<K, V> getSubMap(int fromIndex, int toIndex) { 728 if (fromIndex == 0 && toIndex == size()) { 729 return this; 730 } else if (fromIndex == toIndex) { 731 return emptyMap(comparator()); 732 } else { 733 return new ImmutableSortedMap<>( 734 keySet.getSubSet(fromIndex, toIndex), valueList.subList(fromIndex, toIndex)); 735 } 736 } 737 738 /** 739 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 740 * whose keys are less than {@code toKey}. 741 * 742 * <p>The {@link SortedMap#headMap} documentation states that a submap of a 743 * submap throws an {@link IllegalArgumentException} if passed a {@code toKey} 744 * greater than an earlier {@code toKey}. However, this method doesn't throw 745 * an exception in that situation, but instead keeps the original {@code 746 * toKey}. 747 */ 748 @Override 749 public ImmutableSortedMap<K, V> headMap(K toKey) { 750 return headMap(toKey, false); 751 } 752 753 /** 754 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 755 * whose keys are less than (or equal to, if {@code inclusive}) {@code toKey}. 756 * 757 * <p>The {@link SortedMap#headMap} documentation states that a submap of a 758 * submap throws an {@link IllegalArgumentException} if passed a {@code toKey} 759 * greater than an earlier {@code toKey}. However, this method doesn't throw 760 * an exception in that situation, but instead keeps the original {@code 761 * toKey}. 762 * 763 * @since 12.0 764 */ 765 @Override 766 public ImmutableSortedMap<K, V> headMap(K toKey, boolean inclusive) { 767 return getSubMap(0, keySet.headIndex(checkNotNull(toKey), inclusive)); 768 } 769 770 /** 771 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 772 * whose keys ranges from {@code fromKey}, inclusive, to {@code toKey}, 773 * exclusive. 774 * 775 * <p>The {@link SortedMap#subMap} documentation states that a submap of a 776 * submap throws an {@link IllegalArgumentException} if passed a {@code 777 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 778 * throw an exception in that situation, but instead keeps the original {@code 779 * fromKey}. Similarly, this method keeps the original {@code toKey}, instead 780 * of throwing an exception, if passed a {@code toKey} greater than an earlier 781 * {@code toKey}. 782 */ 783 @Override 784 public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) { 785 return subMap(fromKey, true, toKey, false); 786 } 787 788 /** 789 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 790 * whose keys ranges from {@code fromKey} to {@code toKey}, inclusive or 791 * exclusive as indicated by the boolean flags. 792 * 793 * <p>The {@link SortedMap#subMap} documentation states that a submap of a 794 * submap throws an {@link IllegalArgumentException} if passed a {@code 795 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 796 * throw an exception in that situation, but instead keeps the original {@code 797 * fromKey}. Similarly, this method keeps the original {@code toKey}, instead 798 * of throwing an exception, if passed a {@code toKey} greater than an earlier 799 * {@code toKey}. 800 * 801 * @since 12.0 802 */ 803 @Override 804 public ImmutableSortedMap<K, V> subMap( 805 K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) { 806 checkNotNull(fromKey); 807 checkNotNull(toKey); 808 checkArgument( 809 comparator().compare(fromKey, toKey) <= 0, 810 "expected fromKey <= toKey but %s > %s", 811 fromKey, 812 toKey); 813 return headMap(toKey, toInclusive).tailMap(fromKey, fromInclusive); 814 } 815 816 /** 817 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 818 * whose keys are greater than or equals to {@code fromKey}. 819 * 820 * <p>The {@link SortedMap#tailMap} documentation states that a submap of a 821 * submap throws an {@link IllegalArgumentException} if passed a {@code 822 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 823 * throw an exception in that situation, but instead keeps the original {@code 824 * fromKey}. 825 */ 826 @Override 827 public ImmutableSortedMap<K, V> tailMap(K fromKey) { 828 return tailMap(fromKey, true); 829 } 830 831 /** 832 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 833 * whose keys are greater than (or equal to, if {@code inclusive}) 834 * {@code fromKey}. 835 * 836 * <p>The {@link SortedMap#tailMap} documentation states that a submap of a 837 * submap throws an {@link IllegalArgumentException} if passed a {@code 838 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 839 * throw an exception in that situation, but instead keeps the original {@code 840 * fromKey}. 841 * 842 * @since 12.0 843 */ 844 @Override 845 public ImmutableSortedMap<K, V> tailMap(K fromKey, boolean inclusive) { 846 return getSubMap(keySet.tailIndex(checkNotNull(fromKey), inclusive), size()); 847 } 848 849 @Override 850 public Entry<K, V> lowerEntry(K key) { 851 return headMap(key, false).lastEntry(); 852 } 853 854 @Override 855 public K lowerKey(K key) { 856 return keyOrNull(lowerEntry(key)); 857 } 858 859 @Override 860 public Entry<K, V> floorEntry(K key) { 861 return headMap(key, true).lastEntry(); 862 } 863 864 @Override 865 public K floorKey(K key) { 866 return keyOrNull(floorEntry(key)); 867 } 868 869 @Override 870 public Entry<K, V> ceilingEntry(K key) { 871 return tailMap(key, true).firstEntry(); 872 } 873 874 @Override 875 public K ceilingKey(K key) { 876 return keyOrNull(ceilingEntry(key)); 877 } 878 879 @Override 880 public Entry<K, V> higherEntry(K key) { 881 return tailMap(key, false).firstEntry(); 882 } 883 884 @Override 885 public K higherKey(K key) { 886 return keyOrNull(higherEntry(key)); 887 } 888 889 @Override 890 public Entry<K, V> firstEntry() { 891 return isEmpty() ? null : entrySet().asList().get(0); 892 } 893 894 @Override 895 public Entry<K, V> lastEntry() { 896 return isEmpty() ? null : entrySet().asList().get(size() - 1); 897 } 898 899 /** 900 * Guaranteed to throw an exception and leave the map unmodified. 901 * 902 * @throws UnsupportedOperationException always 903 * @deprecated Unsupported operation. 904 */ 905 @CanIgnoreReturnValue 906 @Deprecated 907 @Override 908 public final Entry<K, V> pollFirstEntry() { 909 throw new UnsupportedOperationException(); 910 } 911 912 /** 913 * Guaranteed to throw an exception and leave the map unmodified. 914 * 915 * @throws UnsupportedOperationException always 916 * @deprecated Unsupported operation. 917 */ 918 @CanIgnoreReturnValue 919 @Deprecated 920 @Override 921 public final Entry<K, V> pollLastEntry() { 922 throw new UnsupportedOperationException(); 923 } 924 925 @Override 926 public ImmutableSortedMap<K, V> descendingMap() { 927 // TODO(kevinb): the descendingMap is never actually cached at all. Either it should be or the 928 // code below simplified. 929 ImmutableSortedMap<K, V> result = descendingMap; 930 if (result == null) { 931 if (isEmpty()) { 932 return result = emptyMap(Ordering.from(comparator()).reverse()); 933 } else { 934 return result = 935 new ImmutableSortedMap<>( 936 (RegularImmutableSortedSet<K>) keySet.descendingSet(), valueList.reverse(), this); 937 } 938 } 939 return result; 940 } 941 942 @Override 943 public ImmutableSortedSet<K> navigableKeySet() { 944 return keySet; 945 } 946 947 @Override 948 public ImmutableSortedSet<K> descendingKeySet() { 949 return keySet.descendingSet(); 950 } 951 952 /** 953 * Serialized type for all ImmutableSortedMap instances. It captures the 954 * logical contents and they are reconstructed using public factory methods. 955 * This ensures that the implementation types remain as implementation 956 * details. 957 */ 958 private static class SerializedForm extends ImmutableMap.SerializedForm { 959 private final Comparator<Object> comparator; 960 961 @SuppressWarnings("unchecked") 962 SerializedForm(ImmutableSortedMap<?, ?> sortedMap) { 963 super(sortedMap); 964 comparator = (Comparator<Object>) sortedMap.comparator(); 965 } 966 967 @Override 968 Object readResolve() { 969 Builder<Object, Object> builder = new Builder<>(comparator); 970 return createMap(builder); 971 } 972 973 private static final long serialVersionUID = 0; 974 } 975 976 @Override 977 Object writeReplace() { 978 return new SerializedForm(this); 979 } 980 981 // This class is never actually serialized directly, but we have to make the 982 // warning go away (and suppressing would suppress for all nested classes too) 983 private static final long serialVersionUID = 0; 984}