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