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 }