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