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