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