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