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