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