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