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