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