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