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