View Javadoc
1   /*
2    * Copyright (C) 2009 The Guava Authors
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   */
16  
17  package com.google.common.collect;
18  
19  import static com.google.common.base.Preconditions.checkArgument;
20  import static com.google.common.base.Preconditions.checkNotNull;
21  import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
22  import static com.google.common.collect.Maps.keyOrNull;
23  
24  import com.google.common.annotations.Beta;
25  import com.google.common.annotations.GwtCompatible;
26  import com.google.errorprone.annotations.CanIgnoreReturnValue;
27  import com.google.j2objc.annotations.WeakOuter;
28  import java.util.AbstractMap;
29  import java.util.Arrays;
30  import java.util.Comparator;
31  import java.util.Map;
32  import java.util.NavigableMap;
33  import java.util.SortedMap;
34  import java.util.Spliterator;
35  import java.util.TreeMap;
36  import java.util.function.BiConsumer;
37  import java.util.function.BinaryOperator;
38  import java.util.function.Consumer;
39  import java.util.function.Function;
40  import java.util.stream.Collector;
41  import java.util.stream.Collectors;
42  import javax.annotation.Nullable;
43  
44  /**
45   * A {@link NavigableMap} whose contents will never change, with many other important properties
46   * detailed at {@link ImmutableCollection}.
47   *
48   * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
49   * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
50   * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
51   * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting map will
52   * not correctly obey its specification.
53   *
54   * <p>See the Guava User Guide article on <a href=
55   * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">
56   * immutable collections</a>.
57   *
58   * @author Jared Levy
59   * @author Louis Wasserman
60   * @since 2.0 (implements {@code NavigableMap} since 12.0)
61   */
62  @GwtCompatible(serializable = true, emulated = true)
63  public final class ImmutableSortedMap<K, V> extends ImmutableSortedMapFauxverideShim<K, V>
64      implements NavigableMap<K, V> {
65    /**
66     * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap}
67     * whose keys and values are the result of applying the provided mapping functions to the input
68     * elements.  The generated map is sorted by the specified comparator.
69     *
70     * <p>If the mapped keys contain duplicates (according to the specified comparator), an
71     * {@code IllegalArgumentException} is thrown when the collection operation is performed.
72     * (This differs from the {@code Collector} returned by
73     * {@link Collectors#toMap(Function, Function)}, which throws an {@code IllegalStateException}.)
74     *
75     * @since 21.0
76     */
77    @Beta
78    public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap(
79        Comparator<? super K> comparator,
80        Function<? super T, ? extends K> keyFunction,
81        Function<? super T, ? extends V> valueFunction) {
82      return CollectCollectors.toImmutableSortedMap(comparator, keyFunction, valueFunction);
83    }
84    
85    /**
86     * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose
87     * keys and values are the result of applying the provided mapping functions to the input
88     * elements.
89     *
90     * <p>If the mapped keys contain duplicates (according to the comparator), the the values are
91     * merged using the specified merging function. Entries will appear in the encounter order of the
92     * first occurrence of the key.
93     *
94     * @since 21.0
95     */
96    @Beta
97    public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap(
98        Comparator<? super K> comparator,
99        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<>(
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<>(
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<>(
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(
393               entryArray,
394               0,
395               size,
396               new Comparator<Entry<K, V>>() {
397                 @Override
398                 public int compare(Entry<K, V> e1, Entry<K, V> e2) {
399                   return comparator.compare(e1.getKey(), e2.getKey());
400                 }
401               });
402           K prevKey = entryArray[0].getKey();
403           keys[0] = prevKey;
404           values[0] = entryArray[0].getValue();
405           for (int i = 1; i < size; i++) {
406             K key = entryArray[i].getKey();
407             V value = entryArray[i].getValue();
408             checkEntryNotNull(key, value);
409             keys[i] = key;
410             values[i] = value;
411             checkNoConflict(
412                 comparator.compare(prevKey, key) != 0, "key", entryArray[i - 1], entryArray[i]);
413             prevKey = key;
414           }
415         }
416         return new ImmutableSortedMap<>(
417             new RegularImmutableSortedSet<K>(new RegularImmutableList<K>(keys), comparator),
418             new RegularImmutableList<V>(values));
419     }
420   }
421 
422   /**
423    * Returns a builder that creates immutable sorted maps whose keys are
424    * ordered by their natural ordering. The sorted maps use {@link
425    * Ordering#natural()} as the comparator.
426    */
427   public static <K extends Comparable<?>, V> Builder<K, V> naturalOrder() {
428     return new Builder<>(Ordering.natural());
429   }
430 
431   /**
432    * Returns a builder that creates immutable sorted maps with an explicit
433    * comparator. If the comparator has a more general type than the map's keys,
434    * such as creating a {@code SortedMap<Integer, String>} with a {@code
435    * Comparator<Number>}, use the {@link Builder} constructor instead.
436    *
437    * @throws NullPointerException if {@code comparator} is null
438    */
439   public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) {
440     return new Builder<>(comparator);
441   }
442 
443   /**
444    * Returns a builder that creates immutable sorted maps whose keys are
445    * ordered by the reverse of their natural ordering.
446    */
447   public static <K extends Comparable<?>, V> Builder<K, V> reverseOrder() {
448     return new Builder<>(Ordering.natural().reverse());
449   }
450 
451   /**
452    * A builder for creating immutable sorted map instances, especially {@code
453    * public static final} maps ("constant maps"). Example: <pre>   {@code
454    *
455    *   static final ImmutableSortedMap<Integer, String> INT_TO_WORD =
456    *       new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural())
457    *           .put(1, "one")
458    *           .put(2, "two")
459    *           .put(3, "three")
460    *           .build();}</pre>
461    *
462    * <p>For <i>small</i> immutable sorted maps, the {@code ImmutableSortedMap.of()}
463    * methods are even more convenient.
464    *
465    * <p>Builder instances can be reused - it is safe to call {@link #build}
466    * multiple times to build multiple maps in series. Each map is a superset of
467    * the maps created before it.
468    *
469    * @since 2.0
470    */
471   public static class Builder<K, V> extends ImmutableMap.Builder<K, V> {
472     private final Comparator<? super K> comparator;
473 
474     /**
475      * Creates a new builder. The returned builder is equivalent to the builder
476      * generated by {@link ImmutableSortedMap#orderedBy}.
477      */
478     @SuppressWarnings("unchecked")
479     public Builder(Comparator<? super K> comparator) {
480       this.comparator = checkNotNull(comparator);
481     }
482 
483     /**
484      * Associates {@code key} with {@code value} in the built map. Duplicate
485      * keys, according to the comparator (which might be the keys' natural
486      * order), are not allowed, and will cause {@link #build} to fail.
487      */
488     @CanIgnoreReturnValue
489     @Override
490     public Builder<K, V> put(K key, V value) {
491       super.put(key, value);
492       return this;
493     }
494 
495     /**
496      * Adds the given {@code entry} to the map, making it immutable if
497      * necessary. Duplicate keys, according to the comparator (which might be
498      * the keys' natural order), are not allowed, and will cause {@link #build}
499      * to fail.
500      *
501      * @since 11.0
502      */
503     @CanIgnoreReturnValue
504     @Override
505     public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
506       super.put(entry);
507       return this;
508     }
509 
510     /**
511      * Associates all of the given map's keys and values in the built map.
512      * Duplicate keys, according to the comparator (which might be the keys'
513      * natural order), are not allowed, and will cause {@link #build} to fail.
514      *
515      * @throws NullPointerException if any key or value in {@code map} is null
516      */
517     @CanIgnoreReturnValue
518     @Override
519     public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
520       super.putAll(map);
521       return this;
522     }
523 
524     /**
525      * Adds all the given entries to the built map.  Duplicate keys, according
526      * to the comparator (which might be the keys' natural order), are not
527      * allowed, and will cause {@link #build} to fail.
528      *
529      * @throws NullPointerException if any key, value, or entry is null
530      * @since 19.0
531      */
532     @CanIgnoreReturnValue
533     @Beta
534     @Override
535     public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
536       super.putAll(entries);
537       return this;
538     }
539 
540     /**
541      * Throws an {@code UnsupportedOperationException}.
542      *
543      * @since 19.0
544      * @deprecated Unsupported by ImmutableSortedMap.Builder.
545      */
546     @CanIgnoreReturnValue
547     @Beta
548     @Override
549     @Deprecated
550     public Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) {
551       throw new UnsupportedOperationException("Not available on ImmutableSortedMap.Builder");
552     }
553 
554     @Override
555     Builder<K, V> combine(ImmutableMap.Builder<K, V> other) {
556       super.combine(other);
557       return this;
558     }
559 
560     /**
561      * Returns a newly-created immutable sorted map.
562      *
563      * @throws IllegalArgumentException if any two keys are equal according to
564      *     the comparator (which might be the keys' natural order)
565      */
566     @Override
567     public ImmutableSortedMap<K, V> build() {
568       switch (size) {
569         case 0:
570           return emptyMap(comparator);
571         case 1:
572           return of(comparator, entries[0].getKey(), entries[0].getValue());
573         default:
574           return fromEntries(comparator, false, entries, size);
575       }
576     }
577   }
578 
579   private final transient RegularImmutableSortedSet<K> keySet;
580   private final transient ImmutableList<V> valueList;
581   private transient ImmutableSortedMap<K, V> descendingMap;
582 
583   ImmutableSortedMap(RegularImmutableSortedSet<K> keySet, ImmutableList<V> valueList) {
584     this(keySet, valueList, null);
585   }
586 
587   ImmutableSortedMap(
588       RegularImmutableSortedSet<K> keySet,
589       ImmutableList<V> valueList,
590       ImmutableSortedMap<K, V> descendingMap) {
591     this.keySet = keySet;
592     this.valueList = valueList;
593     this.descendingMap = descendingMap;
594   }
595 
596   @Override
597   public int size() {
598     return valueList.size();
599   }
600 
601   @Override
602   public void forEach(BiConsumer<? super K, ? super V> action) {
603     checkNotNull(action);
604     ImmutableList<K> keyList = keySet.asList();
605     for (int i = 0; i < size(); i++) {
606       action.accept(keyList.get(i), valueList.get(i));
607     }
608   }
609 
610   @Override
611   public V get(@Nullable Object key) {
612     int index = keySet.indexOf(key);
613     return (index == -1) ? null : valueList.get(index);
614   }
615 
616   @Override
617   boolean isPartialView() {
618     return keySet.isPartialView() || valueList.isPartialView();
619   }
620 
621   /**
622    * Returns an immutable set of the mappings in this map, sorted by the key
623    * ordering.
624    */
625   @Override
626   public ImmutableSet<Entry<K, V>> entrySet() {
627     return super.entrySet();
628   }
629 
630   @Override
631   ImmutableSet<Entry<K, V>> createEntrySet() {
632     @WeakOuter
633     class EntrySet extends ImmutableMapEntrySet<K, V> {
634       @Override
635       public UnmodifiableIterator<Entry<K, V>> iterator() {
636         return asList().iterator();
637       }
638 
639       @Override
640       public Spliterator<Entry<K, V>> spliterator() {
641         return asList().spliterator();
642       }
643 
644       @Override
645       public void forEach(Consumer<? super Entry<K, V>> action) {
646         asList().forEach(action);
647       }
648 
649       @Override
650       ImmutableList<Entry<K, V>> createAsList() {
651         return new ImmutableAsList<Entry<K, V>>() {
652           @Override
653           public Entry<K, V> get(int index) {
654             return new AbstractMap.SimpleImmutableEntry<>(
655                 keySet.asList().get(index), valueList.get(index));
656           }
657 
658           @Override
659           public Spliterator<Entry<K, V>> spliterator() {
660             return CollectSpliterators.indexed(
661                 size(), ImmutableSet.SPLITERATOR_CHARACTERISTICS, this::get);
662           }
663 
664           @Override
665           ImmutableCollection<Entry<K, V>> delegateCollection() {
666             return EntrySet.this;
667           }
668         };
669       }
670 
671       @Override
672       ImmutableMap<K, V> map() {
673         return ImmutableSortedMap.this;
674       }
675     }
676     return isEmpty() ? ImmutableSet.<Entry<K, V>>of() : new EntrySet();
677   }
678 
679   /**
680    * Returns an immutable sorted set of the keys in this map.
681    */
682   @Override
683   public ImmutableSortedSet<K> keySet() {
684     return keySet;
685   }
686 
687   @Override
688   ImmutableSet<K> createKeySet() {
689     throw new AssertionError("should never be called");
690   }
691 
692   /**
693    * Returns an immutable collection of the values in this map, sorted by the
694    * ordering of the corresponding keys.
695    */
696   @Override
697   public ImmutableCollection<V> values() {
698     return valueList;
699   }
700 
701   @Override
702   ImmutableCollection<V> createValues() {
703     throw new AssertionError("should never be called");
704   }
705 
706   /**
707    * Returns the comparator that orders the keys, which is
708    * {@link Ordering#natural()} when the natural ordering of the keys is used.
709    * Note that its behavior is not consistent with {@link TreeMap#comparator()},
710    * which returns {@code null} to indicate natural ordering.
711    */
712   @Override
713   public Comparator<? super K> comparator() {
714     return keySet().comparator();
715   }
716 
717   @Override
718   public K firstKey() {
719     return keySet().first();
720   }
721 
722   @Override
723   public K lastKey() {
724     return keySet().last();
725   }
726 
727   private ImmutableSortedMap<K, V> getSubMap(int fromIndex, int toIndex) {
728     if (fromIndex == 0 && toIndex == size()) {
729       return this;
730     } else if (fromIndex == toIndex) {
731       return emptyMap(comparator());
732     } else {
733       return new ImmutableSortedMap<>(
734           keySet.getSubSet(fromIndex, toIndex), valueList.subList(fromIndex, toIndex));
735     }
736   }
737 
738   /**
739    * This method returns a {@code ImmutableSortedMap}, consisting of the entries
740    * whose keys are less than {@code toKey}.
741    *
742    * <p>The {@link SortedMap#headMap} documentation states that a submap of a
743    * submap throws an {@link IllegalArgumentException} if passed a {@code toKey}
744    * greater than an earlier {@code toKey}. However, this method doesn't throw
745    * an exception in that situation, but instead keeps the original {@code
746    * toKey}.
747    */
748   @Override
749   public ImmutableSortedMap<K, V> headMap(K toKey) {
750     return headMap(toKey, false);
751   }
752 
753   /**
754    * This method returns a {@code ImmutableSortedMap}, consisting of the entries
755    * whose keys are less than (or equal to, if {@code inclusive}) {@code toKey}.
756    *
757    * <p>The {@link SortedMap#headMap} documentation states that a submap of a
758    * submap throws an {@link IllegalArgumentException} if passed a {@code toKey}
759    * greater than an earlier {@code toKey}. However, this method doesn't throw
760    * an exception in that situation, but instead keeps the original {@code
761    * toKey}.
762    *
763    * @since 12.0
764    */
765   @Override
766   public ImmutableSortedMap<K, V> headMap(K toKey, boolean inclusive) {
767     return getSubMap(0, keySet.headIndex(checkNotNull(toKey), inclusive));
768   }
769 
770   /**
771    * This method returns a {@code ImmutableSortedMap}, consisting of the entries
772    * whose keys ranges from {@code fromKey}, inclusive, to {@code toKey},
773    * exclusive.
774    *
775    * <p>The {@link SortedMap#subMap} documentation states that a submap of a
776    * submap throws an {@link IllegalArgumentException} if passed a {@code
777    * fromKey} less than an earlier {@code fromKey}. However, this method doesn't
778    * throw an exception in that situation, but instead keeps the original {@code
779    * fromKey}. Similarly, this method keeps the original {@code toKey}, instead
780    * of throwing an exception, if passed a {@code toKey} greater than an earlier
781    * {@code toKey}.
782    */
783   @Override
784   public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) {
785     return subMap(fromKey, true, toKey, false);
786   }
787 
788   /**
789    * This method returns a {@code ImmutableSortedMap}, consisting of the entries
790    * whose keys ranges from {@code fromKey} to {@code toKey}, inclusive or
791    * exclusive as indicated by the boolean flags.
792    *
793    * <p>The {@link SortedMap#subMap} documentation states that a submap of a
794    * submap throws an {@link IllegalArgumentException} if passed a {@code
795    * fromKey} less than an earlier {@code fromKey}. However, this method doesn't
796    * throw an exception in that situation, but instead keeps the original {@code
797    * fromKey}. Similarly, this method keeps the original {@code toKey}, instead
798    * of throwing an exception, if passed a {@code toKey} greater than an earlier
799    * {@code toKey}.
800    *
801    * @since 12.0
802    */
803   @Override
804   public ImmutableSortedMap<K, V> subMap(
805       K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
806     checkNotNull(fromKey);
807     checkNotNull(toKey);
808     checkArgument(
809         comparator().compare(fromKey, toKey) <= 0,
810         "expected fromKey <= toKey but %s > %s",
811         fromKey,
812         toKey);
813     return headMap(toKey, toInclusive).tailMap(fromKey, fromInclusive);
814   }
815 
816   /**
817    * This method returns a {@code ImmutableSortedMap}, consisting of the entries
818    * whose keys are greater than or equals to {@code fromKey}.
819    *
820    * <p>The {@link SortedMap#tailMap} documentation states that a submap of a
821    * submap throws an {@link IllegalArgumentException} if passed a {@code
822    * fromKey} less than an earlier {@code fromKey}. However, this method doesn't
823    * throw an exception in that situation, but instead keeps the original {@code
824    * fromKey}.
825    */
826   @Override
827   public ImmutableSortedMap<K, V> tailMap(K fromKey) {
828     return tailMap(fromKey, true);
829   }
830 
831   /**
832    * This method returns a {@code ImmutableSortedMap}, consisting of the entries
833    * whose keys are greater than (or equal to, if {@code inclusive})
834    * {@code fromKey}.
835    *
836    * <p>The {@link SortedMap#tailMap} documentation states that a submap of a
837    * submap throws an {@link IllegalArgumentException} if passed a {@code
838    * fromKey} less than an earlier {@code fromKey}. However, this method doesn't
839    * throw an exception in that situation, but instead keeps the original {@code
840    * fromKey}.
841    *
842    * @since 12.0
843    */
844   @Override
845   public ImmutableSortedMap<K, V> tailMap(K fromKey, boolean inclusive) {
846     return getSubMap(keySet.tailIndex(checkNotNull(fromKey), inclusive), size());
847   }
848 
849   @Override
850   public Entry<K, V> lowerEntry(K key) {
851     return headMap(key, false).lastEntry();
852   }
853 
854   @Override
855   public K lowerKey(K key) {
856     return keyOrNull(lowerEntry(key));
857   }
858 
859   @Override
860   public Entry<K, V> floorEntry(K key) {
861     return headMap(key, true).lastEntry();
862   }
863 
864   @Override
865   public K floorKey(K key) {
866     return keyOrNull(floorEntry(key));
867   }
868 
869   @Override
870   public Entry<K, V> ceilingEntry(K key) {
871     return tailMap(key, true).firstEntry();
872   }
873 
874   @Override
875   public K ceilingKey(K key) {
876     return keyOrNull(ceilingEntry(key));
877   }
878 
879   @Override
880   public Entry<K, V> higherEntry(K key) {
881     return tailMap(key, false).firstEntry();
882   }
883 
884   @Override
885   public K higherKey(K key) {
886     return keyOrNull(higherEntry(key));
887   }
888 
889   @Override
890   public Entry<K, V> firstEntry() {
891     return isEmpty() ? null : entrySet().asList().get(0);
892   }
893 
894   @Override
895   public Entry<K, V> lastEntry() {
896     return isEmpty() ? null : entrySet().asList().get(size() - 1);
897   }
898 
899   /**
900    * Guaranteed to throw an exception and leave the map unmodified.
901    *
902    * @throws UnsupportedOperationException always
903    * @deprecated Unsupported operation.
904    */
905   @CanIgnoreReturnValue
906   @Deprecated
907   @Override
908   public final Entry<K, V> pollFirstEntry() {
909     throw new UnsupportedOperationException();
910   }
911 
912   /**
913    * Guaranteed to throw an exception and leave the map unmodified.
914    *
915    * @throws UnsupportedOperationException always
916    * @deprecated Unsupported operation.
917    */
918   @CanIgnoreReturnValue
919   @Deprecated
920   @Override
921   public final Entry<K, V> pollLastEntry() {
922     throw new UnsupportedOperationException();
923   }
924 
925   @Override
926   public ImmutableSortedMap<K, V> descendingMap() {
927     // TODO(kevinb): the descendingMap is never actually cached at all. Either it should be or the
928     // code below simplified.
929     ImmutableSortedMap<K, V> result = descendingMap;
930     if (result == null) {
931       if (isEmpty()) {
932         return result = emptyMap(Ordering.from(comparator()).reverse());
933       } else {
934         return result =
935             new ImmutableSortedMap<>(
936                 (RegularImmutableSortedSet<K>) keySet.descendingSet(), valueList.reverse(), this);
937       }
938     }
939     return result;
940   }
941 
942   @Override
943   public ImmutableSortedSet<K> navigableKeySet() {
944     return keySet;
945   }
946 
947   @Override
948   public ImmutableSortedSet<K> descendingKeySet() {
949     return keySet.descendingSet();
950   }
951 
952   /**
953    * Serialized type for all ImmutableSortedMap instances. It captures the
954    * logical contents and they are reconstructed using public factory methods.
955    * This ensures that the implementation types remain as implementation
956    * details.
957    */
958   private static class SerializedForm extends ImmutableMap.SerializedForm {
959     private final Comparator<Object> comparator;
960 
961     @SuppressWarnings("unchecked")
962     SerializedForm(ImmutableSortedMap<?, ?> sortedMap) {
963       super(sortedMap);
964       comparator = (Comparator<Object>) sortedMap.comparator();
965     }
966 
967     @Override
968     Object readResolve() {
969       Builder<Object, Object> builder = new Builder<>(comparator);
970       return createMap(builder);
971     }
972 
973     private static final long serialVersionUID = 0;
974   }
975 
976   @Override
977   Object writeReplace() {
978     return new SerializedForm(this);
979   }
980 
981   // This class is never actually serialized directly, but we have to make the
982   // warning go away (and suppressing would suppress for all nested classes too)
983   private static final long serialVersionUID = 0;
984 }