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 017 package com.google.common.collect; 018 019 import static com.google.common.base.Preconditions.checkArgument; 020 import static com.google.common.base.Preconditions.checkNotNull; 021 import static com.google.common.collect.SortedLists.Relation.CEILING; 022 import static com.google.common.collect.SortedLists.Relation.EQUAL; 023 024 import com.google.common.annotations.GwtCompatible; 025 import com.google.common.base.Function; 026 027 import java.io.Serializable; 028 import java.util.Arrays; 029 import java.util.Collections; 030 import java.util.Comparator; 031 import java.util.List; 032 import java.util.Map; 033 import java.util.NoSuchElementException; 034 import java.util.SortedMap; 035 import java.util.TreeMap; 036 037 import javax.annotation.Nullable; 038 039 /** 040 * An immutable {@link SortedMap}. Does not permit null keys or values. 041 * 042 * <p>Unlike {@link Collections#unmodifiableSortedMap}, which is a <i>view</i> 043 * of a separate map which can still change, an instance of {@code 044 * ImmutableSortedMap} contains its own data and will <i>never</i> change. 045 * {@code ImmutableSortedMap} is convenient for {@code public static final} maps 046 * ("constant maps") and also lets you easily make a "defensive copy" of a map 047 * provided to your class by a caller. 048 * 049 * <p><b>Note</b>: Although this class is not final, it cannot be subclassed as 050 * it has no public or protected constructors. Thus, instances of this class are 051 * guaranteed to be immutable. 052 * 053 * @author Jared Levy 054 * @author Louis Wasserman 055 * @since 2 (imported from Google Collections Library) 056 */ 057 @GwtCompatible(serializable = true, emulated = true) 058 public class ImmutableSortedMap<K, V> 059 extends ImmutableSortedMapFauxverideShim<K, V> implements SortedMap<K, V> { 060 /* 061 * TODO(kevinb): Confirm that ImmutableSortedMap is faster to construct and 062 * uses less memory than TreeMap; then say so in the class Javadoc. 063 * 064 * TODO(kevinb): Create separate subclasses for empty, single-entry, and 065 * multiple-entry instances, if it's deemed beneficial. 066 */ 067 068 private static final Comparator<Comparable> NATURAL_ORDER = 069 Ordering.natural(); 070 071 private static final ImmutableSortedMap<Comparable, Object> 072 NATURAL_EMPTY_MAP = 073 new ImmutableSortedMap<Comparable, Object>( 074 ImmutableList.<Entry<Comparable, Object>>of(), NATURAL_ORDER); 075 076 /** 077 * Returns the empty sorted map. 078 */ 079 @SuppressWarnings("unchecked") 080 // unsafe, comparator() returns a comparator on the specified type 081 // TODO(kevinb): evaluate whether or not of().comparator() should return null 082 public static <K, V> ImmutableSortedMap<K, V> of() { 083 return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP; 084 } 085 086 @SuppressWarnings("unchecked") 087 private static <K, V> ImmutableSortedMap<K, V> emptyMap( 088 Comparator<? super K> comparator) { 089 if (NATURAL_ORDER.equals(comparator)) { 090 return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP; 091 } else { 092 return new ImmutableSortedMap<K, V>( 093 ImmutableList.<Entry<K, V>>of(), comparator); 094 } 095 } 096 097 /** 098 * Returns an immutable map containing a single entry. 099 */ 100 public static <K extends Comparable<? super K>, V> 101 ImmutableSortedMap<K, V> of(K k1, V v1) { 102 return new ImmutableSortedMap<K, V>( 103 ImmutableList.of(entryOf(k1, v1)), Ordering.natural()); 104 } 105 106 /** 107 * Returns an immutable sorted map containing the given entries, sorted by the 108 * natural ordering of their keys. 109 * 110 * @throws IllegalArgumentException if the two keys are equal according to 111 * their natural ordering 112 */ 113 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> 114 of(K k1, V v1, K k2, V v2) { 115 return new Builder<K, V>(Ordering.natural()) 116 .put(k1, v1).put(k2, v2).build(); 117 } 118 119 /** 120 * Returns an immutable sorted map containing the given entries, sorted by the 121 * natural ordering of their keys. 122 * 123 * @throws IllegalArgumentException if any two keys are equal according to 124 * their natural ordering 125 */ 126 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> 127 of(K k1, V v1, K k2, V v2, K k3, V v3) { 128 return new Builder<K, V>(Ordering.natural()) 129 .put(k1, v1).put(k2, v2).put(k3, v3).build(); 130 } 131 132 /** 133 * Returns an immutable sorted map containing the given entries, sorted by the 134 * natural ordering of their keys. 135 * 136 * @throws IllegalArgumentException if any two keys are equal according to 137 * their natural ordering 138 */ 139 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> 140 of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) { 141 return new Builder<K, V>(Ordering.natural()) 142 .put(k1, v1).put(k2, v2).put(k3, v3).put(k4, v4).build(); 143 } 144 145 /** 146 * Returns an immutable sorted map containing the given entries, sorted by the 147 * natural ordering of their keys. 148 * 149 * @throws IllegalArgumentException if any two keys are equal according to 150 * their natural ordering 151 */ 152 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> 153 of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) { 154 return new Builder<K, V>(Ordering.natural()) 155 .put(k1, v1).put(k2, v2).put(k3, v3).put(k4, v4).put(k5, v5).build(); 156 } 157 158 /** 159 * Returns an immutable map containing the same entries as {@code map}, sorted 160 * by the natural ordering of the keys. 161 * 162 * <p>Despite the method name, this method attempts to avoid actually copying 163 * the data when it is safe to do so. The exact circumstances under which a 164 * copy will or will not be performed are undocumented and subject to change. 165 * 166 * <p>This method is not type-safe, as it may be called on a map with keys 167 * that are not mutually comparable. 168 * 169 * @throws ClassCastException if the keys in {@code map} are not mutually 170 * comparable 171 * @throws NullPointerException if any key or value in {@code map} is null 172 * @throws IllegalArgumentException if any two keys are equal according to 173 * their natural ordering 174 */ 175 public static <K, V> ImmutableSortedMap<K, V> copyOf( 176 Map<? extends K, ? extends V> map) { 177 // Hack around K not being a subtype of Comparable. 178 // Unsafe, see ImmutableSortedSetFauxverideShim. 179 @SuppressWarnings("unchecked") 180 Ordering<K> naturalOrder = (Ordering<K>) Ordering.<Comparable>natural(); 181 return copyOfInternal(map, naturalOrder); 182 } 183 184 /** 185 * Returns an immutable map containing the same entries as {@code map}, with 186 * keys sorted by the provided comparator. 187 * 188 * <p>Despite the method name, this method attempts to avoid actually copying 189 * the data when it is safe to do so. The exact circumstances under which a 190 * copy will or will not be performed are undocumented and subject to change. 191 * 192 * @throws NullPointerException if any key or value in {@code map} is null 193 * @throws IllegalArgumentException if any two keys are equal according to the 194 * comparator 195 */ 196 public static <K, V> ImmutableSortedMap<K, V> copyOf( 197 Map<? extends K, ? extends V> map, Comparator<? super K> comparator) { 198 return copyOfInternal(map, checkNotNull(comparator)); 199 } 200 201 /** 202 * Returns an immutable map containing the same entries as the provided sorted 203 * map, with the same ordering. 204 * 205 * <p>Despite the method name, this method attempts to avoid actually copying 206 * the data when it is safe to do so. The exact circumstances under which a 207 * copy will or will not be performed are undocumented and subject to change. 208 * 209 * @throws NullPointerException if any key or value in {@code map} is null 210 */ 211 @SuppressWarnings("unchecked") 212 public static <K, V> ImmutableSortedMap<K, V> copyOfSorted( 213 SortedMap<K, ? extends V> map) { 214 Comparator<? super K> comparator = map.comparator(); 215 if (comparator == null) { 216 // If map has a null comparator, the keys should have a natural ordering, 217 // even though K doesn't explicitly implement Comparable. 218 comparator = (Comparator<? super K>) NATURAL_ORDER; 219 } 220 return copyOfInternal(map, comparator); 221 } 222 223 private static <K, V> ImmutableSortedMap<K, V> copyOfInternal( 224 Map<? extends K, ? extends V> map, Comparator<? super K> comparator) { 225 boolean sameComparator = false; 226 if (map instanceof SortedMap) { 227 SortedMap<?, ?> sortedMap = (SortedMap<?, ?>) map; 228 Comparator<?> comparator2 = sortedMap.comparator(); 229 sameComparator = (comparator2 == null) 230 ? comparator == NATURAL_ORDER 231 : comparator.equals(comparator2); 232 } 233 234 if (sameComparator && (map instanceof ImmutableSortedMap)) { 235 // TODO(kevinb): Prove that this cast is safe, even though 236 // Collections.unmodifiableSortedMap requires the same key type. 237 @SuppressWarnings("unchecked") 238 ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map; 239 if (!kvMap.isPartialView()) { 240 return kvMap; 241 } 242 } 243 244 // "adding" type params to an array of a raw type should be safe as 245 // long as no one can ever cast that same array instance back to a 246 // raw type. 247 @SuppressWarnings("unchecked") 248 Entry<K, V>[] entries = map.entrySet().toArray(new Entry[0]); 249 250 for (int i = 0; i < entries.length; i++) { 251 Entry<K, V> entry = entries[i]; 252 entries[i] = entryOf(entry.getKey(), entry.getValue()); 253 } 254 255 List<Entry<K, V>> list = Arrays.asList(entries); 256 257 if (!sameComparator) { 258 sortEntries(list, comparator); 259 validateEntries(list, comparator); 260 } 261 262 return new ImmutableSortedMap<K, V>(ImmutableList.copyOf(list), comparator); 263 } 264 265 private static <K, V> void sortEntries( 266 List<Entry<K, V>> entries, final Comparator<? super K> comparator) { 267 Comparator<Entry<K, V>> entryComparator = new Comparator<Entry<K, V>>() { 268 269 @Override public int compare(Entry<K, V> entry1, Entry<K, V> entry2) { 270 return comparator.compare(entry1.getKey(), entry2.getKey()); 271 } 272 }; 273 274 Collections.sort(entries, entryComparator); 275 } 276 277 private static <K, V> void validateEntries(List<Entry<K, V>> entries, 278 Comparator<? super K> comparator) { 279 for (int i = 1; i < entries.size(); i++) { 280 if (comparator.compare( 281 entries.get(i - 1).getKey(), entries.get(i).getKey()) == 0) { 282 throw new IllegalArgumentException( 283 "Duplicate keys in mappings " + entries.get(i - 1) + " and " 284 + entries.get(i)); 285 } 286 } 287 } 288 289 /** 290 * Returns a builder that creates immutable sorted maps whose keys are 291 * ordered by their natural ordering. The sorted maps use {@link 292 * Ordering#natural()} as the comparator. 293 * 294 * <p>Note: the type parameter {@code K} extends {@code Comparable<K>} rather 295 * than {@code Comparable<? super K>} as a workaround for javac <a 296 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 297 * 6468354</a>. 298 */ 299 public static <K extends Comparable<K>, V> Builder<K, V> naturalOrder() { 300 return new Builder<K, V>(Ordering.natural()); 301 } 302 303 /** 304 * Returns a builder that creates immutable sorted maps with an explicit 305 * comparator. If the comparator has a more general type than the map's keys, 306 * such as creating a {@code SortedMap<Integer, String>} with a {@code 307 * Comparator<Number>}, use the {@link Builder} constructor instead. 308 * 309 * @throws NullPointerException if {@code comparator} is null 310 */ 311 public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) { 312 return new Builder<K, V>(comparator); 313 } 314 315 /** 316 * Returns a builder that creates immutable sorted maps whose keys are 317 * ordered by the reverse of their natural ordering. 318 * 319 * <p>Note: the type parameter {@code K} extends {@code Comparable<K>} rather 320 * than {@code Comparable<? super K>} as a workaround for javac <a 321 * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug 322 * 6468354</a>. 323 */ 324 public static <K extends Comparable<K>, V> Builder<K, V> reverseOrder() { 325 return new Builder<K, V>(Ordering.natural().reverse()); 326 } 327 328 /** 329 * A builder for creating immutable sorted map instances, especially {@code 330 * public static final} maps ("constant maps"). Example: <pre> {@code 331 * 332 * static final ImmutableSortedMap<Integer, String> INT_TO_WORD = 333 * new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural()) 334 * .put(1, "one") 335 * .put(2, "two") 336 * .put(3, "three") 337 * .build();}</pre> 338 * 339 * For <i>small</i> immutable sorted maps, the {@code ImmutableSortedMap.of()} 340 * methods are even more convenient. 341 * 342 * <p>Builder instances can be reused - it is safe to call {@link #build} 343 * multiple times to build multiple maps in series. Each map is a superset of 344 * the maps created before it. 345 * 346 * @since 2 (imported from Google Collections Library) 347 */ 348 public static class Builder<K, V> extends ImmutableMap.Builder<K, V> { 349 private final Comparator<? super K> comparator; 350 351 /** 352 * Creates a new builder. The returned builder is equivalent to the builder 353 * generated by {@link ImmutableSortedMap#orderedBy}. 354 */ 355 public Builder(Comparator<? super K> comparator) { 356 this.comparator = checkNotNull(comparator); 357 } 358 359 /** 360 * Associates {@code key} with {@code value} in the built map. Duplicate 361 * keys, according to the comparator (which might be the keys' natural 362 * order), are not allowed, and will cause {@link #build} to fail. 363 */ 364 @Override public Builder<K, V> put(K key, V value) { 365 entries.add(entryOf(key, value)); 366 return this; 367 } 368 369 /** 370 * Associates all of the given map's keys and values in the built map. 371 * Duplicate keys, according to the comparator (which might be the keys' 372 * natural order), are not allowed, and will cause {@link #build} to fail. 373 * 374 * @throws NullPointerException if any key or value in {@code map} is null 375 */ 376 @Override public Builder<K, V> putAll(Map<? extends K, ? extends V> map) { 377 for (Entry<? extends K, ? extends V> entry : map.entrySet()) { 378 put(entry.getKey(), entry.getValue()); 379 } 380 return this; 381 } 382 383 /** 384 * Returns a newly-created immutable sorted map. 385 * 386 * @throws IllegalArgumentException if any two keys are equal according to 387 * the comparator (which might be the keys' natural order) 388 */ 389 @Override public ImmutableSortedMap<K, V> build() { 390 sortEntries(entries, comparator); 391 validateEntries(entries, comparator); 392 return new ImmutableSortedMap<K, V>( 393 ImmutableList.copyOf(entries), comparator); 394 } 395 } 396 397 final transient ImmutableList<Entry<K, V>> entries; 398 private final transient Comparator<? super K> comparator; 399 400 ImmutableSortedMap( 401 ImmutableList<Entry<K, V>> entries, Comparator<? super K> comparator) { 402 this.entries = entries; 403 this.comparator = comparator; 404 } 405 406 @Override 407 public int size() { 408 return entries.size(); 409 } 410 411 transient final Function<Entry<K, V>, K> keyFunction = 412 new Function<Entry<K, V>, K>() { 413 414 @Override public K apply(Entry<K, V> entry) { 415 return entry.getKey(); 416 } 417 }; 418 419 // Pretend the comparator can compare anything. If it turns out it can't 420 // compare two elements, it'll throw a CCE. Only methods that are specified to 421 // throw CCE should call this. 422 @SuppressWarnings("unchecked") 423 Comparator<Object> unsafeComparator() { 424 return (Comparator<Object>) comparator; 425 } 426 427 @Override public V get(@Nullable Object key) { 428 if (key == null) { 429 return null; 430 } 431 int i; 432 try { 433 i = SortedLists.binarySearch(Lists.transform(entries, keyFunction), key, 434 unsafeComparator(), EQUAL, false); 435 } catch (ClassCastException e) { 436 return null; 437 } 438 return i >= 0 ? entries.get(i).getValue() : null; 439 } 440 441 @Override public boolean containsValue(@Nullable Object value) { 442 if (value == null) { 443 return false; 444 } 445 return Iterators.contains(valueIterator(), value); 446 } 447 448 @Override boolean isPartialView() { 449 return entries.isPartialView(); 450 } 451 452 private transient ImmutableSet<Entry<K, V>> entrySet; 453 454 /** 455 * Returns an immutable set of the mappings in this map, sorted by the key 456 * ordering. 457 */ 458 @Override public ImmutableSet<Entry<K, V>> entrySet() { 459 ImmutableSet<Entry<K, V>> es = entrySet; 460 return (es == null) ? (entrySet = createEntrySet()) : es; 461 } 462 463 private ImmutableSet<Entry<K, V>> createEntrySet() { 464 return isEmpty() ? ImmutableSet.<Entry<K, V>>of() 465 : new EntrySet<K, V>(this); 466 } 467 468 @SuppressWarnings("serial") // uses writeReplace(), not default serialization 469 private static class EntrySet<K, V> extends ImmutableSet<Entry<K, V>> { 470 final transient ImmutableSortedMap<K, V> map; 471 472 EntrySet(ImmutableSortedMap<K, V> map) { 473 this.map = map; 474 } 475 476 @Override boolean isPartialView() { 477 return map.isPartialView(); 478 } 479 480 @Override 481 public int size() { 482 return map.size(); 483 } 484 485 @Override public UnmodifiableIterator<Entry<K, V>> iterator() { 486 return map.entries.iterator(); 487 } 488 489 @Override public boolean contains(Object target) { 490 if (target instanceof Entry) { 491 Entry<?, ?> entry = (Entry<?, ?>) target; 492 V mappedValue = map.get(entry.getKey()); 493 return mappedValue != null && mappedValue.equals(entry.getValue()); 494 } 495 return false; 496 } 497 498 @Override Object writeReplace() { 499 return new EntrySetSerializedForm<K, V>(map); 500 } 501 } 502 503 private static class EntrySetSerializedForm<K, V> implements Serializable { 504 final ImmutableSortedMap<K, V> map; 505 EntrySetSerializedForm(ImmutableSortedMap<K, V> map) { 506 this.map = map; 507 } 508 Object readResolve() { 509 return map.entrySet(); 510 } 511 private static final long serialVersionUID = 0; 512 } 513 514 private transient ImmutableSortedSet<K> keySet; 515 516 /** 517 * Returns an immutable sorted set of the keys in this map. 518 */ 519 @Override public ImmutableSortedSet<K> keySet() { 520 ImmutableSortedSet<K> ks = keySet; 521 return (ks == null) ? (keySet = createKeySet()) : ks; 522 } 523 524 @SuppressWarnings("serial") // does not use default serialization 525 private ImmutableSortedSet<K> createKeySet() { 526 if (isEmpty()) { 527 return ImmutableSortedSet.emptySet(comparator); 528 } 529 530 return new RegularImmutableSortedSet<K>( 531 new TransformedImmutableList<Entry<K, V>, K>(entries) { 532 533 @Override K transform(Entry<K, V> entry) { 534 return entry.getKey(); 535 } 536 }, comparator); 537 } 538 539 private transient ImmutableCollection<V> values; 540 541 /** 542 * Returns an immutable collection of the values in this map, sorted by the 543 * ordering of the corresponding keys. 544 */ 545 @Override public ImmutableCollection<V> values() { 546 ImmutableCollection<V> v = values; 547 return (v == null) ? (values = new Values<V>(this)) : v; 548 } 549 550 UnmodifiableIterator<V> valueIterator(){ 551 final UnmodifiableIterator<Entry<K, V>> entryIterator = entries.iterator(); 552 return new UnmodifiableIterator<V>() { 553 554 @Override public boolean hasNext() { 555 return entryIterator.hasNext(); 556 } 557 558 @Override public V next() { 559 return entryIterator.next().getValue(); 560 } 561 }; 562 } 563 564 @SuppressWarnings("serial") // uses writeReplace(), not default serialization 565 private static class Values<V> extends ImmutableCollection<V> { 566 private final ImmutableSortedMap<?, V> map; 567 568 Values(ImmutableSortedMap<?, V> map) { 569 this.map = map; 570 } 571 572 @Override 573 public int size() { 574 return map.size(); 575 } 576 577 @Override public UnmodifiableIterator<V> iterator() { 578 return map.valueIterator(); 579 } 580 581 @Override public boolean contains(Object target) { 582 return map.containsValue(target); 583 } 584 585 @Override boolean isPartialView() { 586 return true; 587 } 588 589 @Override Object writeReplace() { 590 return new ValuesSerializedForm<V>(map); 591 } 592 } 593 594 private static class ValuesSerializedForm<V> implements Serializable { 595 final ImmutableSortedMap<?, V> map; 596 ValuesSerializedForm(ImmutableSortedMap<?, V> map) { 597 this.map = map; 598 } 599 Object readResolve() { 600 return map.values(); 601 } 602 private static final long serialVersionUID = 0; 603 } 604 605 /** 606 * Returns the comparator that orders the keys, which is 607 * {@link Ordering#natural()} when the natural ordering of the keys is used. 608 * Note that its behavior is not consistent with {@link TreeMap#comparator()}, 609 * which returns {@code null} to indicate natural ordering. 610 */ 611 @Override 612 public Comparator<? super K> comparator() { 613 return comparator; 614 } 615 616 @Override 617 public K firstKey() { 618 if (isEmpty()) { 619 throw new NoSuchElementException(); 620 } 621 return entries.get(0).getKey(); 622 } 623 624 @Override 625 public K lastKey() { 626 if (isEmpty()) { 627 throw new NoSuchElementException(); 628 } 629 return entries.get(size() - 1).getKey(); 630 } 631 632 /** 633 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 634 * whose keys are less than {@code toKey}. 635 * 636 * <p>The {@link SortedMap#headMap} documentation states that a submap of a 637 * submap throws an {@link IllegalArgumentException} if passed a {@code toKey} 638 * greater than an earlier {@code toKey}. However, this method doesn't throw 639 * an exception in that situation, but instead keeps the original {@code 640 * toKey}. 641 */ 642 @Override 643 public ImmutableSortedMap<K, V> headMap(K toKey) { 644 int newToIndex = findSubmapIndex(checkNotNull(toKey)); 645 return createSubmap(0, newToIndex); 646 } 647 648 /** 649 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 650 * whose keys ranges from {@code fromKey}, inclusive, to {@code toKey}, 651 * exclusive. 652 * 653 * <p>The {@link SortedMap#subMap} documentation states that a submap of a 654 * submap throws an {@link IllegalArgumentException} if passed a {@code 655 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 656 * throw an exception in that situation, but instead keeps the original {@code 657 * fromKey}. Similarly, this method keeps the original {@code toKey}, instead 658 * of throwing an exception, if passed a {@code toKey} greater than an earlier 659 * {@code toKey}. 660 */ 661 @Override 662 public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) { 663 checkNotNull(fromKey); 664 checkNotNull(toKey); 665 checkArgument(comparator.compare(fromKey, toKey) <= 0); 666 int newFromIndex = findSubmapIndex(fromKey); 667 int newToIndex = findSubmapIndex(toKey); 668 return createSubmap(newFromIndex, newToIndex); 669 } 670 671 /** 672 * This method returns a {@code ImmutableSortedMap}, consisting of the entries 673 * whose keys are greater than or equals to {@code fromKey}. 674 * 675 * <p>The {@link SortedMap#tailMap} documentation states that a submap of a 676 * submap throws an {@link IllegalArgumentException} if passed a {@code 677 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't 678 * throw an exception in that situation, but instead keeps the original {@code 679 * fromKey}. 680 */ 681 @Override 682 public ImmutableSortedMap<K, V> tailMap(K fromKey) { 683 int newFromIndex = findSubmapIndex(checkNotNull(fromKey)); 684 return createSubmap(newFromIndex, size()); 685 } 686 687 private int findSubmapIndex(K key) { 688 return SortedLists.binarySearch( 689 Lists.transform(entries, keyFunction), key, comparator, CEILING, false); 690 } 691 692 private ImmutableSortedMap<K, V> createSubmap( 693 int newFromIndex, int newToIndex) { 694 if (newFromIndex < newToIndex) { 695 return new ImmutableSortedMap<K, V>( 696 entries.subList(newFromIndex, newToIndex), comparator); 697 } else { 698 return emptyMap(comparator); 699 } 700 } 701 702 /** 703 * Serialized type for all ImmutableSortedMap instances. It captures the 704 * logical contents and they are reconstructed using public factory methods. 705 * This ensures that the implementation types remain as implementation 706 * details. 707 */ 708 private static class SerializedForm extends ImmutableMap.SerializedForm { 709 private final Comparator<Object> comparator; 710 @SuppressWarnings("unchecked") 711 SerializedForm(ImmutableSortedMap<?, ?> sortedMap) { 712 super(sortedMap); 713 comparator = (Comparator<Object>) sortedMap.comparator(); 714 } 715 @Override Object readResolve() { 716 Builder<Object, Object> builder = new Builder<Object, Object>(comparator); 717 return createMap(builder); 718 } 719 private static final long serialVersionUID = 0; 720 } 721 722 @Override Object writeReplace() { 723 return new SerializedForm(this); 724 } 725 726 // This class is never actually serialized directly, but we have to make the 727 // warning go away (and suppressing would suppress for all nested classes too) 728 private static final long serialVersionUID = 0; 729 }