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