001/*
002 * Copyright (C) 2009 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021import static com.google.common.collect.Maps.keyOrNull;
022
023import com.google.common.annotations.GwtCompatible;
024
025import java.util.Arrays;
026import java.util.Collection;
027import java.util.Collections;
028import java.util.Comparator;
029import java.util.List;
030import java.util.Map;
031import java.util.NavigableMap;
032import java.util.SortedMap;
033import java.util.TreeMap;
034
035import 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)
061public 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}