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