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