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.Arrays.sort;
024import static java.util.Objects.requireNonNull;
025
026import com.google.common.annotations.GwtCompatible;
027import com.google.common.annotations.GwtIncompatible;
028import com.google.common.annotations.J2ktIncompatible;
029import com.google.errorprone.annotations.CanIgnoreReturnValue;
030import com.google.errorprone.annotations.DoNotCall;
031import java.io.InvalidObjectException;
032import java.io.ObjectInputStream;
033import java.util.AbstractMap;
034import java.util.Comparator;
035import java.util.Map;
036import java.util.NavigableMap;
037import java.util.SortedMap;
038import java.util.Spliterator;
039import java.util.TreeMap;
040import java.util.function.BiConsumer;
041import java.util.function.BinaryOperator;
042import java.util.function.Consumer;
043import java.util.function.Function;
044import java.util.stream.Collector;
045import java.util.stream.Collectors;
046import org.jspecify.annotations.Nullable;
047
048/**
049 * A {@link NavigableMap} whose contents will never change, with many other important properties
050 * detailed at {@link ImmutableCollection}.
051 *
052 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
053 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
054 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
055 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting map will
056 * not correctly obey its specification.
057 *
058 * <p>See the Guava User Guide article on <a href=
059 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained">immutable collections</a>.
060 *
061 * @author Jared Levy
062 * @author Louis Wasserman
063 * @since 2.0 (implements {@code NavigableMap} since 12.0)
064 */
065@GwtCompatible(serializable = true, emulated = true)
066public final class ImmutableSortedMap<K, V> extends ImmutableMap<K, V>
067    implements NavigableMap<K, V> {
068  /**
069   * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose
070   * keys and values are the result of applying the provided mapping functions to the input
071   * elements. The generated map is sorted by the specified comparator.
072   *
073   * <p>If the mapped keys contain duplicates (according to the specified comparator), an {@code
074   * IllegalArgumentException} is thrown when the collection operation is performed. (This differs
075   * from the {@code Collector} returned by {@link Collectors#toMap(Function, Function)}, which
076   * throws an {@code IllegalStateException}.)
077   *
078   * @since 21.0
079   */
080  public static <T extends @Nullable Object, K, V>
081      Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap(
082          Comparator<? super K> comparator,
083          Function<? super T, ? extends K> keyFunction,
084          Function<? super T, ? extends V> valueFunction) {
085    return CollectCollectors.toImmutableSortedMap(comparator, keyFunction, valueFunction);
086  }
087
088  /**
089   * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose
090   * keys and values are the result of applying the provided mapping functions to the input
091   * elements.
092   *
093   * <p>If the mapped keys contain duplicates (according to the comparator), the values are merged
094   * using the specified merging function. Entries will appear in the encounter order of the first
095   * occurrence of the key.
096   *
097   * @since 21.0
098   */
099  public static <T extends @Nullable Object, K, V>
100      Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap(
101          Comparator<? super K> comparator,
102          Function<? super T, ? extends K> keyFunction,
103          Function<? super T, ? extends V> valueFunction,
104          BinaryOperator<V> mergeFunction) {
105    return CollectCollectors.toImmutableSortedMap(
106        comparator, keyFunction, valueFunction, mergeFunction);
107  }
108
109  /*
110   * TODO(kevinb): Confirm that ImmutableSortedMap is faster to construct and
111   * uses less memory than TreeMap; then say so in the class Javadoc.
112   */
113  private static final Comparator<?> NATURAL_ORDER = Ordering.natural();
114
115  private static final ImmutableSortedMap<Comparable<?>, Object> NATURAL_EMPTY_MAP =
116      new ImmutableSortedMap<>(
117          ImmutableSortedSet.emptySet(Ordering.natural()), ImmutableList.<Object>of());
118
119  static <K, V> ImmutableSortedMap<K, V> emptyMap(Comparator<? super K> comparator) {
120    if (Ordering.natural().equals(comparator)) {
121      return of();
122    } else {
123      return new ImmutableSortedMap<>(
124          ImmutableSortedSet.emptySet(comparator), ImmutableList.<V>of());
125    }
126  }
127
128  /**
129   * Returns the empty sorted map.
130   *
131   * <p><b>Performance note:</b> the instance returned is a singleton.
132   */
133  @SuppressWarnings("unchecked")
134  // unsafe, comparator() returns a comparator on the specified type
135  // TODO(kevinb): evaluate whether or not of().comparator() should return null
136  public static <K, V> ImmutableSortedMap<K, V> of() {
137    return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP;
138  }
139
140  /** Returns an immutable map containing a single entry. */
141  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(K k1, V v1) {
142    return of(Ordering.natural(), k1, v1);
143  }
144
145  /** Returns an immutable map containing a single entry. */
146  private static <K, V> ImmutableSortedMap<K, V> of(Comparator<? super K> comparator, K k1, V v1) {
147    return new ImmutableSortedMap<>(
148        new RegularImmutableSortedSet<K>(ImmutableList.of(k1), checkNotNull(comparator)),
149        ImmutableList.of(v1));
150  }
151
152  /**
153   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
154   * their keys.
155   *
156   * @throws IllegalArgumentException if the two keys are equal according to their natural ordering
157   */
158  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
159      K k1, V v1, K k2, V v2) {
160    return fromEntries(entryOf(k1, v1), entryOf(k2, v2));
161  }
162
163  /**
164   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
165   * their keys.
166   *
167   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
168   */
169  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
170      K k1, V v1, K k2, V v2, K k3, V v3) {
171    return fromEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
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   */
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) {
182    return fromEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
183  }
184
185  /**
186   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
187   * their keys.
188   *
189   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
190   */
191  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
192      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
193    return fromEntries(
194        entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
195  }
196
197  /**
198   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
199   * their keys.
200   *
201   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
202   * @since 31.0
203   */
204  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
205      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6) {
206    return fromEntries(
207        entryOf(k1, v1),
208        entryOf(k2, v2),
209        entryOf(k3, v3),
210        entryOf(k4, v4),
211        entryOf(k5, v5),
212        entryOf(k6, v6));
213  }
214
215  /**
216   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
217   * their keys.
218   *
219   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
220   * @since 31.0
221   */
222  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
223      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) {
224    return fromEntries(
225        entryOf(k1, v1),
226        entryOf(k2, v2),
227        entryOf(k3, v3),
228        entryOf(k4, v4),
229        entryOf(k5, v5),
230        entryOf(k6, v6),
231        entryOf(k7, v7));
232  }
233
234  /**
235   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
236   * their keys.
237   *
238   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
239   * @since 31.0
240   */
241  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
242      K k1,
243      V v1,
244      K k2,
245      V v2,
246      K k3,
247      V v3,
248      K k4,
249      V v4,
250      K k5,
251      V v5,
252      K k6,
253      V v6,
254      K k7,
255      V v7,
256      K k8,
257      V v8) {
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  }
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  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
277      K k1,
278      V v1,
279      K k2,
280      V v2,
281      K k3,
282      V v3,
283      K k4,
284      V v4,
285      K k5,
286      V v5,
287      K k6,
288      V v6,
289      K k7,
290      V v7,
291      K k8,
292      V v8,
293      K k9,
294      V v9) {
295    /*
296     * This explicit type parameter works around what seems to be a javac bug in certain
297     * configurations: b/339186525#comment6
298     */
299    return ImmutableSortedMap.<K, V>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  }
310
311  /**
312   * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
313   * their keys.
314   *
315   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
316   * @since 31.0
317   */
318  public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
319      K k1,
320      V v1,
321      K k2,
322      V v2,
323      K k3,
324      V v3,
325      K k4,
326      V v4,
327      K k5,
328      V v5,
329      K k6,
330      V v6,
331      K k7,
332      V v7,
333      K k8,
334      V v8,
335      K k9,
336      V v9,
337      K k10,
338      V v10) {
339    return fromEntries(
340        entryOf(k1, v1),
341        entryOf(k2, v2),
342        entryOf(k3, v3),
343        entryOf(k4, v4),
344        entryOf(k5, v5),
345        entryOf(k6, v6),
346        entryOf(k7, v7),
347        entryOf(k8, v8),
348        entryOf(k9, v9),
349        entryOf(k10, v10));
350  }
351
352  /**
353   * Returns an immutable map containing the same entries as {@code map}, sorted by the natural
354   * ordering of the keys.
355   *
356   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
357   * safe to do so. The exact circumstances under which a copy will or will not be performed are
358   * undocumented and subject to change.
359   *
360   * <p>This method is not type-safe, as it may be called on a map with keys that are not mutually
361   * comparable.
362   *
363   * @throws ClassCastException if the keys in {@code map} are not mutually comparable
364   * @throws NullPointerException if any key or value in {@code map} is null
365   * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
366   */
367  public static <K, V> ImmutableSortedMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
368    // Hack around K not being a subtype of Comparable.
369    // Unsafe, see ImmutableSortedSetFauxverideShim.
370    @SuppressWarnings("unchecked")
371    Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER;
372    return copyOfInternal(map, naturalOrder);
373  }
374
375  /**
376   * Returns an immutable map containing the same entries as {@code map}, with keys sorted by the
377   * provided comparator.
378   *
379   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
380   * safe to do so. The exact circumstances under which a copy will or will not be performed are
381   * undocumented and subject to change.
382   *
383   * @throws NullPointerException if any key or value in {@code map} is null
384   * @throws IllegalArgumentException if any two keys are equal according to the comparator
385   */
386  public static <K, V> ImmutableSortedMap<K, V> copyOf(
387      Map<? extends K, ? extends V> map, Comparator<? super K> comparator) {
388    return copyOfInternal(map, checkNotNull(comparator));
389  }
390
391  /**
392   * Returns an immutable map containing the given entries, with keys sorted by their natural
393   * ordering.
394   *
395   * <p>This method is not type-safe, as it may be called on a map with keys that are not mutually
396   * comparable.
397   *
398   * @throws NullPointerException if any key or value in {@code map} is null
399   * @throws IllegalArgumentException if any two keys are equal according to the comparator
400   * @since 19.0
401   */
402  public static <K, V> ImmutableSortedMap<K, V> copyOf(
403      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
404    // Hack around K not being a subtype of Comparable.
405    // Unsafe, see ImmutableSortedSetFauxverideShim.
406    @SuppressWarnings("unchecked")
407    Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER;
408    return copyOf(entries, naturalOrder);
409  }
410
411  /**
412   * Returns an immutable map containing the given entries, with keys sorted by the provided
413   * comparator.
414   *
415   * @throws NullPointerException if any key or value in {@code map} is null
416   * @throws IllegalArgumentException if any two keys are equal according to the comparator
417   * @since 19.0
418   */
419  public static <K, V> ImmutableSortedMap<K, V> copyOf(
420      Iterable<? extends Entry<? extends K, ? extends V>> entries,
421      Comparator<? super K> comparator) {
422    return fromEntries(checkNotNull(comparator), false, entries);
423  }
424
425  /**
426   * Returns an immutable map containing the same entries as the provided sorted map, with the same
427   * ordering.
428   *
429   * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
430   * safe to do so. The exact circumstances under which a copy will or will not be performed are
431   * undocumented and subject to change.
432   *
433   * @throws NullPointerException if any key or value in {@code map} is null
434   */
435  @SuppressWarnings("unchecked")
436  public static <K, V> ImmutableSortedMap<K, V> copyOfSorted(SortedMap<K, ? extends V> map) {
437    Comparator<? super K> comparator = map.comparator();
438    if (comparator == null) {
439      // If map has a null comparator, the keys should have a natural ordering,
440      // even though K doesn't explicitly implement Comparable.
441      comparator = (Comparator<? super K>) NATURAL_ORDER;
442    }
443    if (map instanceof ImmutableSortedMap) {
444      // TODO(kevinb): Prove that this cast is safe, even though
445      // Collections.unmodifiableSortedMap requires the same key type.
446      @SuppressWarnings("unchecked")
447      ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map;
448      if (!kvMap.isPartialView()) {
449        return kvMap;
450      }
451    }
452    return fromEntries(comparator, true, map.entrySet());
453  }
454
455  private static <K, V> ImmutableSortedMap<K, V> copyOfInternal(
456      Map<? extends K, ? extends V> map, Comparator<? super K> comparator) {
457    boolean sameComparator = false;
458    if (map instanceof SortedMap) {
459      SortedMap<?, ?> sortedMap = (SortedMap<?, ?>) map;
460      Comparator<?> comparator2 = sortedMap.comparator();
461      sameComparator =
462          (comparator2 == null) ? comparator == NATURAL_ORDER : comparator.equals(comparator2);
463    }
464
465    if (sameComparator && (map instanceof ImmutableSortedMap)) {
466      // TODO(kevinb): Prove that this cast is safe, even though
467      // Collections.unmodifiableSortedMap requires the same key type.
468      @SuppressWarnings("unchecked")
469      ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map;
470      if (!kvMap.isPartialView()) {
471        return kvMap;
472      }
473    }
474    return fromEntries(comparator, sameComparator, map.entrySet());
475  }
476
477  private static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> fromEntries(
478      Entry<K, V>... entries) {
479    return fromEntries(Ordering.natural(), false, entries, entries.length);
480  }
481
482  /**
483   * Accepts a collection of possibly-null entries. If {@code sameComparator}, then it is assumed
484   * that they do not need to be sorted or checked for dupes.
485   */
486  private static <K, V> ImmutableSortedMap<K, V> fromEntries(
487      Comparator<? super K> comparator,
488      boolean sameComparator,
489      Iterable<? extends Entry<? extends K, ? extends V>> entries) {
490    // "adding" type params to an array of a raw type should be safe as
491    // long as no one can ever cast that same array instance back to a
492    // raw type.
493    @SuppressWarnings("unchecked")
494    Entry<K, V>[] entryArray = (Entry[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY);
495    return fromEntries(comparator, sameComparator, entryArray, entryArray.length);
496  }
497
498  private static <K, V> ImmutableSortedMap<K, V> fromEntries(
499      final Comparator<? super K> comparator,
500      boolean sameComparator,
501      @Nullable Entry<K, V>[] entryArray,
502      int size) {
503    switch (size) {
504      case 0:
505        return emptyMap(comparator);
506      case 1:
507        // requireNonNull is safe because the first `size` elements have been filled in.
508        Entry<K, V> onlyEntry = requireNonNull(entryArray[0]);
509        return of(comparator, onlyEntry.getKey(), onlyEntry.getValue());
510      default:
511        Object[] keys = new Object[size];
512        Object[] values = new Object[size];
513        if (sameComparator) {
514          // Need to check for nulls, but don't need to sort or validate.
515          for (int i = 0; i < size; i++) {
516            // requireNonNull is safe because the first `size` elements have been filled in.
517            Entry<K, V> entry = requireNonNull(entryArray[i]);
518            Object key = entry.getKey();
519            Object value = entry.getValue();
520            checkEntryNotNull(key, value);
521            keys[i] = key;
522            values[i] = value;
523          }
524        } else {
525          // Need to sort and check for nulls and dupes.
526          // Inline the Comparator implementation rather than transforming with a Function
527          // to save code size.
528          sort(
529              entryArray,
530              0,
531              size,
532              (e1, e2) -> {
533                // requireNonNull is safe because the first `size` elements have been filled in.
534                requireNonNull(e1);
535                requireNonNull(e2);
536                return comparator.compare(e1.getKey(), e2.getKey());
537              });
538          // requireNonNull is safe because the first `size` elements have been filled in.
539          Entry<K, V> firstEntry = requireNonNull(entryArray[0]);
540          K prevKey = firstEntry.getKey();
541          keys[0] = prevKey;
542          values[0] = firstEntry.getValue();
543          checkEntryNotNull(keys[0], values[0]);
544          for (int i = 1; i < size; i++) {
545            // requireNonNull is safe because the first `size` elements have been filled in.
546            Entry<K, V> prevEntry = requireNonNull(entryArray[i - 1]);
547            Entry<K, V> entry = requireNonNull(entryArray[i]);
548            K key = entry.getKey();
549            V value = entry.getValue();
550            checkEntryNotNull(key, value);
551            keys[i] = key;
552            values[i] = value;
553            checkNoConflict(comparator.compare(prevKey, key) != 0, "key", prevEntry, entry);
554            prevKey = key;
555          }
556        }
557        return new ImmutableSortedMap<>(
558            new RegularImmutableSortedSet<K>(new RegularImmutableList<K>(keys), comparator),
559            new RegularImmutableList<V>(values));
560    }
561  }
562
563  /**
564   * Returns a builder that creates immutable sorted maps whose keys are ordered by their natural
565   * ordering. The sorted maps use {@link Ordering#natural()} as the comparator.
566   */
567  public static <K extends Comparable<?>, V> Builder<K, V> naturalOrder() {
568    return new Builder<>(Ordering.natural());
569  }
570
571  /**
572   * Returns a builder that creates immutable sorted maps with an explicit comparator. If the
573   * comparator has a more general type than the map's keys, such as creating a {@code
574   * SortedMap<Integer, String>} with a {@code Comparator<Number>}, use the {@link Builder}
575   * constructor instead.
576   *
577   * @throws NullPointerException if {@code comparator} is null
578   */
579  public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) {
580    return new Builder<>(comparator);
581  }
582
583  /**
584   * Returns a builder that creates immutable sorted maps whose keys are ordered by the reverse of
585   * their natural ordering.
586   */
587  public static <K extends Comparable<?>, V> Builder<K, V> reverseOrder() {
588    return new Builder<>(Ordering.<K>natural().reverse());
589  }
590
591  /**
592   * A builder for creating immutable sorted map instances, especially {@code public static final}
593   * maps ("constant maps"). Example:
594   *
595   * <pre>{@code
596   * static final ImmutableSortedMap<Integer, String> INT_TO_WORD =
597   *     new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural())
598   *         .put(1, "one")
599   *         .put(2, "two")
600   *         .put(3, "three")
601   *         .buildOrThrow();
602   * }</pre>
603   *
604   * <p>For <i>small</i> immutable sorted maps, the {@code ImmutableSortedMap.of()} methods are even
605   * more convenient.
606   *
607   * <p>Builder instances can be reused - it is safe to call {@link #buildOrThrow} multiple times to
608   * build multiple maps in series. Each map is a superset of the maps created before it.
609   *
610   * @since 2.0
611   */
612  public static class Builder<K, V> extends ImmutableMap.Builder<K, V> {
613    private final Comparator<? super K> comparator;
614
615    /**
616     * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
617     * ImmutableSortedMap#orderedBy}.
618     */
619    public Builder(Comparator<? super K> comparator) {
620      this.comparator = checkNotNull(comparator);
621    }
622
623    /**
624     * Associates {@code key} with {@code value} in the built map. Duplicate keys, according to the
625     * comparator (which might be the keys' natural order), are not allowed, and will cause {@link
626     * #build} to fail.
627     */
628    @CanIgnoreReturnValue
629    @Override
630    public Builder<K, V> put(K key, V value) {
631      super.put(key, value);
632      return this;
633    }
634
635    /**
636     * Adds the given {@code entry} to the map, making it immutable if necessary. Duplicate keys,
637     * according to the comparator (which might be the keys' natural order), are not allowed, and
638     * will cause {@link #build} to fail.
639     *
640     * @since 11.0
641     */
642    @CanIgnoreReturnValue
643    @Override
644    public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
645      super.put(entry);
646      return this;
647    }
648
649    /**
650     * Associates all of the given map's keys and values in the built map. Duplicate keys, according
651     * to the comparator (which might be the keys' natural order), are not allowed, and will cause
652     * {@link #build} to fail.
653     *
654     * @throws NullPointerException if any key or value in {@code map} is null
655     */
656    @CanIgnoreReturnValue
657    @Override
658    public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
659      super.putAll(map);
660      return this;
661    }
662
663    /**
664     * Adds all the given entries to the built map. Duplicate keys, according to the comparator
665     * (which might be the keys' natural order), are not allowed, and will cause {@link #build} to
666     * fail.
667     *
668     * @throws NullPointerException if any key, value, or entry is null
669     * @since 19.0
670     */
671    @CanIgnoreReturnValue
672    @Override
673    public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
674      super.putAll(entries);
675      return this;
676    }
677
678    /**
679     * Throws an {@code UnsupportedOperationException}.
680     *
681     * @since 19.0
682     * @deprecated Unsupported by ImmutableSortedMap.Builder.
683     */
684    @CanIgnoreReturnValue
685    @Override
686    @Deprecated
687    @DoNotCall("Always throws UnsupportedOperationException")
688    public final Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) {
689      throw new UnsupportedOperationException("Not available on ImmutableSortedMap.Builder");
690    }
691
692    @Override
693    Builder<K, V> combine(ImmutableMap.Builder<K, V> other) {
694      super.combine(other);
695      return this;
696    }
697
698    /**
699     * Returns a newly-created immutable sorted map.
700     *
701     * <p>Prefer the equivalent method {@link #buildOrThrow()} to make it explicit that the method
702     * will throw an exception if there are duplicate keys. The {@code build()} method will soon be
703     * deprecated.
704     *
705     * @throws IllegalArgumentException if any two keys are equal according to the comparator (which
706     *     might be the keys' natural order)
707     */
708    @Override
709    public ImmutableSortedMap<K, V> build() {
710      return buildOrThrow();
711    }
712
713    /**
714     * Returns a newly-created immutable sorted map, or throws an exception if any two keys are
715     * equal.
716     *
717     * @throws IllegalArgumentException if any two keys are equal according to the comparator (which
718     *     might be the keys' natural order)
719     * @since 31.0
720     */
721    @Override
722    public ImmutableSortedMap<K, V> buildOrThrow() {
723      switch (size) {
724        case 0:
725          return emptyMap(comparator);
726        case 1:
727          // requireNonNull is safe because the first `size` elements have been filled in.
728          Entry<K, V> onlyEntry = requireNonNull(entries[0]);
729          return of(comparator, onlyEntry.getKey(), onlyEntry.getValue());
730        default:
731          return fromEntries(comparator, false, entries, size);
732      }
733    }
734
735    /**
736     * Throws UnsupportedOperationException. A future version may support this operation. Then the
737     * value for any given key will be the one that was last supplied in a {@code put} operation for
738     * that key.
739     *
740     * @throws UnsupportedOperationException always
741     * @since 31.1
742     * @deprecated This method is not currently implemented, and may never be.
743     */
744    @DoNotCall
745    @Deprecated
746    @Override
747    public final ImmutableSortedMap<K, V> buildKeepingLast() {
748      // TODO(emcmanus): implement
749      throw new UnsupportedOperationException(
750          "ImmutableSortedMap.Builder does not yet implement buildKeepingLast()");
751    }
752  }
753
754  private final transient RegularImmutableSortedSet<K> keySet;
755  private final transient ImmutableList<V> valueList;
756  private transient @Nullable ImmutableSortedMap<K, V> descendingMap;
757
758  ImmutableSortedMap(RegularImmutableSortedSet<K> keySet, ImmutableList<V> valueList) {
759    this(keySet, valueList, null);
760  }
761
762  ImmutableSortedMap(
763      RegularImmutableSortedSet<K> keySet,
764      ImmutableList<V> valueList,
765      @Nullable ImmutableSortedMap<K, V> descendingMap) {
766    this.keySet = keySet;
767    this.valueList = valueList;
768    this.descendingMap = descendingMap;
769  }
770
771  @Override
772  public int size() {
773    return valueList.size();
774  }
775
776  @Override
777  public void forEach(BiConsumer<? super K, ? super V> action) {
778    checkNotNull(action);
779    ImmutableList<K> keyList = keySet.asList();
780    for (int i = 0; i < size(); i++) {
781      action.accept(keyList.get(i), valueList.get(i));
782    }
783  }
784
785  @Override
786  public @Nullable V get(@Nullable Object key) {
787    int index = keySet.indexOf(key);
788    return (index == -1) ? null : valueList.get(index);
789  }
790
791  @Override
792  boolean isPartialView() {
793    return keySet.isPartialView() || valueList.isPartialView();
794  }
795
796  /** Returns an immutable set of the mappings in this map, sorted by the key ordering. */
797  @Override
798  public ImmutableSet<Entry<K, V>> entrySet() {
799    return super.entrySet();
800  }
801
802  @Override
803  ImmutableSet<Entry<K, V>> createEntrySet() {
804    class EntrySet extends ImmutableMapEntrySet<K, V> {
805      @Override
806      public UnmodifiableIterator<Entry<K, V>> iterator() {
807        return asList().iterator();
808      }
809
810      @Override
811      public Spliterator<Entry<K, V>> spliterator() {
812        return asList().spliterator();
813      }
814
815      @Override
816      public void forEach(Consumer<? super Entry<K, V>> action) {
817        asList().forEach(action);
818      }
819
820      @Override
821      ImmutableList<Entry<K, V>> createAsList() {
822        return new ImmutableAsList<Entry<K, V>>() {
823          @Override
824          public Entry<K, V> get(int index) {
825            return new AbstractMap.SimpleImmutableEntry<>(
826                keySet.asList().get(index), valueList.get(index));
827          }
828
829          @Override
830          public Spliterator<Entry<K, V>> spliterator() {
831            return CollectSpliterators.indexed(
832                size(), ImmutableSet.SPLITERATOR_CHARACTERISTICS, this::get);
833          }
834
835          @Override
836          ImmutableCollection<Entry<K, V>> delegateCollection() {
837            return EntrySet.this;
838          }
839
840          // redeclare to help optimizers with b/310253115
841          @SuppressWarnings("RedundantOverride")
842          @Override
843          @J2ktIncompatible // serialization
844          @GwtIncompatible // serialization
845          Object writeReplace() {
846            return super.writeReplace();
847          }
848        };
849      }
850
851      @Override
852      ImmutableMap<K, V> map() {
853        return ImmutableSortedMap.this;
854      }
855
856      // redeclare to help optimizers with b/310253115
857      @SuppressWarnings("RedundantOverride")
858      @Override
859      @J2ktIncompatible // serialization
860      @GwtIncompatible // serialization
861      Object writeReplace() {
862        return super.writeReplace();
863      }
864    }
865    return isEmpty() ? ImmutableSet.<Entry<K, V>>of() : new EntrySet();
866  }
867
868  /** Returns an immutable sorted set of the keys in this map. */
869  @Override
870  public ImmutableSortedSet<K> keySet() {
871    return keySet;
872  }
873
874  @Override
875  ImmutableSet<K> createKeySet() {
876    throw new AssertionError("should never be called");
877  }
878
879  /**
880   * Returns an immutable collection of the values in this map, sorted by the ordering of the
881   * corresponding keys.
882   */
883  @Override
884  public ImmutableCollection<V> values() {
885    return valueList;
886  }
887
888  @Override
889  ImmutableCollection<V> createValues() {
890    throw new AssertionError("should never be called");
891  }
892
893  /**
894   * Returns the comparator that orders the keys, which is {@link Ordering#natural()} when the
895   * natural ordering of the keys is used. Note that its behavior is not consistent with {@link
896   * TreeMap#comparator()}, which returns {@code null} to indicate natural ordering.
897   */
898  @Override
899  public Comparator<? super K> comparator() {
900    return keySet().comparator();
901  }
902
903  @Override
904  public K firstKey() {
905    return keySet().first();
906  }
907
908  @Override
909  public K lastKey() {
910    return keySet().last();
911  }
912
913  private ImmutableSortedMap<K, V> getSubMap(int fromIndex, int toIndex) {
914    if (fromIndex == 0 && toIndex == size()) {
915      return this;
916    } else if (fromIndex == toIndex) {
917      return emptyMap(comparator());
918    } else {
919      return new ImmutableSortedMap<>(
920          keySet.getSubSet(fromIndex, toIndex), valueList.subList(fromIndex, toIndex));
921    }
922  }
923
924  /**
925   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are less
926   * than {@code toKey}.
927   *
928   * <p>The {@link SortedMap#headMap} documentation states that a submap of a submap throws an
929   * {@link IllegalArgumentException} if passed a {@code toKey} greater than an earlier {@code
930   * toKey}. However, this method doesn't throw an exception in that situation, but instead keeps
931   * the original {@code toKey}.
932   */
933  @Override
934  public ImmutableSortedMap<K, V> headMap(K toKey) {
935    return headMap(toKey, false);
936  }
937
938  /**
939   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are less
940   * than (or equal to, if {@code inclusive}) {@code toKey}.
941   *
942   * <p>The {@link SortedMap#headMap} documentation states that a submap of a submap throws an
943   * {@link IllegalArgumentException} if passed a {@code toKey} greater than an earlier {@code
944   * toKey}. However, this method doesn't throw an exception in that situation, but instead keeps
945   * the original {@code toKey}.
946   *
947   * @since 12.0
948   */
949  @Override
950  public ImmutableSortedMap<K, V> headMap(K toKey, boolean inclusive) {
951    return getSubMap(0, keySet.headIndex(checkNotNull(toKey), inclusive));
952  }
953
954  /**
955   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys ranges
956   * from {@code fromKey}, inclusive, to {@code toKey}, exclusive.
957   *
958   * <p>The {@link SortedMap#subMap} documentation states that a submap of a submap throws an {@link
959   * IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code fromKey}.
960   * However, this method doesn't throw an exception in that situation, but instead keeps the
961   * original {@code fromKey}. Similarly, this method keeps the original {@code toKey}, instead of
962   * throwing an exception, if passed a {@code toKey} greater than an earlier {@code toKey}.
963   */
964  @Override
965  public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) {
966    return subMap(fromKey, true, toKey, false);
967  }
968
969  /**
970   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys ranges
971   * from {@code fromKey} to {@code toKey}, inclusive or exclusive as indicated by the boolean
972   * flags.
973   *
974   * <p>The {@link SortedMap#subMap} documentation states that a submap of a submap throws an {@link
975   * IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code fromKey}.
976   * However, this method doesn't throw an exception in that situation, but instead keeps the
977   * original {@code fromKey}. Similarly, this method keeps the original {@code toKey}, instead of
978   * throwing an exception, if passed a {@code toKey} greater than an earlier {@code toKey}.
979   *
980   * @since 12.0
981   */
982  @Override
983  public ImmutableSortedMap<K, V> subMap(
984      K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
985    checkNotNull(fromKey);
986    checkNotNull(toKey);
987    checkArgument(
988        comparator().compare(fromKey, toKey) <= 0,
989        "expected fromKey <= toKey but %s > %s",
990        fromKey,
991        toKey);
992    return headMap(toKey, toInclusive).tailMap(fromKey, fromInclusive);
993  }
994
995  /**
996   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are
997   * greater than or equals to {@code fromKey}.
998   *
999   * <p>The {@link SortedMap#tailMap} documentation states that a submap of a submap throws an
1000   * {@link IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code
1001   * fromKey}. However, this method doesn't throw an exception in that situation, but instead keeps
1002   * the original {@code fromKey}.
1003   */
1004  @Override
1005  public ImmutableSortedMap<K, V> tailMap(K fromKey) {
1006    return tailMap(fromKey, true);
1007  }
1008
1009  /**
1010   * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are
1011   * greater than (or equal to, if {@code inclusive}) {@code fromKey}.
1012   *
1013   * <p>The {@link SortedMap#tailMap} documentation states that a submap of a submap throws an
1014   * {@link IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code
1015   * fromKey}. However, this method doesn't throw an exception in that situation, but instead keeps
1016   * the original {@code fromKey}.
1017   *
1018   * @since 12.0
1019   */
1020  @Override
1021  public ImmutableSortedMap<K, V> tailMap(K fromKey, boolean inclusive) {
1022    return getSubMap(keySet.tailIndex(checkNotNull(fromKey), inclusive), size());
1023  }
1024
1025  @Override
1026  public @Nullable Entry<K, V> lowerEntry(K key) {
1027    return headMap(key, false).lastEntry();
1028  }
1029
1030  @Override
1031  public @Nullable K lowerKey(K key) {
1032    return keyOrNull(lowerEntry(key));
1033  }
1034
1035  @Override
1036  public @Nullable Entry<K, V> floorEntry(K key) {
1037    return headMap(key, true).lastEntry();
1038  }
1039
1040  @Override
1041  public @Nullable K floorKey(K key) {
1042    return keyOrNull(floorEntry(key));
1043  }
1044
1045  @Override
1046  public @Nullable Entry<K, V> ceilingEntry(K key) {
1047    return tailMap(key, true).firstEntry();
1048  }
1049
1050  @Override
1051  public @Nullable K ceilingKey(K key) {
1052    return keyOrNull(ceilingEntry(key));
1053  }
1054
1055  @Override
1056  public @Nullable Entry<K, V> higherEntry(K key) {
1057    return tailMap(key, false).firstEntry();
1058  }
1059
1060  @Override
1061  public @Nullable K higherKey(K key) {
1062    return keyOrNull(higherEntry(key));
1063  }
1064
1065  @Override
1066  public @Nullable Entry<K, V> firstEntry() {
1067    return isEmpty() ? null : entrySet().asList().get(0);
1068  }
1069
1070  @Override
1071  public @Nullable Entry<K, V> lastEntry() {
1072    return isEmpty() ? null : entrySet().asList().get(size() - 1);
1073  }
1074
1075  /**
1076   * Guaranteed to throw an exception and leave the map unmodified.
1077   *
1078   * @throws UnsupportedOperationException always
1079   * @deprecated Unsupported operation.
1080   */
1081  @CanIgnoreReturnValue
1082  @Deprecated
1083  @Override
1084  @DoNotCall("Always throws UnsupportedOperationException")
1085  public final @Nullable Entry<K, V> pollFirstEntry() {
1086    throw new UnsupportedOperationException();
1087  }
1088
1089  /**
1090   * Guaranteed to throw an exception and leave the map unmodified.
1091   *
1092   * @throws UnsupportedOperationException always
1093   * @deprecated Unsupported operation.
1094   */
1095  @CanIgnoreReturnValue
1096  @Deprecated
1097  @Override
1098  @DoNotCall("Always throws UnsupportedOperationException")
1099  public final @Nullable Entry<K, V> pollLastEntry() {
1100    throw new UnsupportedOperationException();
1101  }
1102
1103  @Override
1104  public ImmutableSortedMap<K, V> descendingMap() {
1105    // TODO(kevinb): The descendingMap is never actually cached at all. Either:
1106    //
1107    // - Cache it, and annotate the field with @LazyInit.
1108    // - Simplify the code below, and consider eliminating the field (b/287198172), which is also
1109    //   set by one of the constructors.
1110    ImmutableSortedMap<K, V> result = descendingMap;
1111    if (result == null) {
1112      if (isEmpty()) {
1113        return emptyMap(Ordering.from(comparator()).reverse());
1114      } else {
1115        return new ImmutableSortedMap<>(
1116            (RegularImmutableSortedSet<K>) keySet.descendingSet(), valueList.reverse(), this);
1117      }
1118    }
1119    return result;
1120  }
1121
1122  @Override
1123  public ImmutableSortedSet<K> navigableKeySet() {
1124    return keySet;
1125  }
1126
1127  @Override
1128  public ImmutableSortedSet<K> descendingKeySet() {
1129    return keySet.descendingSet();
1130  }
1131
1132  /**
1133   * Serialized type for all ImmutableSortedMap instances. It captures the logical contents and they
1134   * are reconstructed using public factory methods. This ensures that the implementation types
1135   * remain as implementation details.
1136   */
1137  @J2ktIncompatible // serialization
1138  private static class SerializedForm<K, V> extends ImmutableMap.SerializedForm<K, V> {
1139    private final Comparator<? super K> comparator;
1140
1141    SerializedForm(ImmutableSortedMap<K, V> sortedMap) {
1142      super(sortedMap);
1143      comparator = sortedMap.comparator();
1144    }
1145
1146    @Override
1147    Builder<K, V> makeBuilder(int size) {
1148      return new Builder<>(comparator);
1149    }
1150
1151    private static final long serialVersionUID = 0;
1152  }
1153
1154  @Override
1155  @J2ktIncompatible // serialization
1156  Object writeReplace() {
1157    return new SerializedForm<>(this);
1158  }
1159
1160  @J2ktIncompatible // java.io.ObjectInputStream
1161  private void readObject(ObjectInputStream stream) throws InvalidObjectException {
1162    throw new InvalidObjectException("Use SerializedForm");
1163  }
1164
1165  // This class is never actually serialized directly, but we have to make the
1166  // warning go away (and suppressing would suppress for all nested classes too)
1167  private static final long serialVersionUID = 0;
1168
1169  /**
1170   * Not supported. Use {@link #toImmutableSortedMap}, which offers better type-safety, instead.
1171   * This method exists only to hide {@link ImmutableMap#toImmutableMap} from consumers of {@code
1172   * ImmutableSortedMap}.
1173   *
1174   * @throws UnsupportedOperationException always
1175   * @deprecated Use {@link ImmutableSortedMap#toImmutableSortedMap}.
1176   */
1177  @DoNotCall("Use toImmutableSortedMap")
1178  @Deprecated
1179  public static <T extends @Nullable Object, K, V>
1180      Collector<T, ?, ImmutableMap<K, V>> toImmutableMap(
1181          Function<? super T, ? extends K> keyFunction,
1182          Function<? super T, ? extends V> valueFunction) {
1183    throw new UnsupportedOperationException();
1184  }
1185
1186  /**
1187   * Not supported. Use {@link #toImmutableSortedMap}, which offers better type-safety, instead.
1188   * This method exists only to hide {@link ImmutableMap#toImmutableMap} from consumers of {@code
1189   * ImmutableSortedMap}.
1190   *
1191   * @throws UnsupportedOperationException always
1192   * @deprecated Use {@link ImmutableSortedMap#toImmutableSortedMap}.
1193   */
1194  @DoNotCall("Use toImmutableSortedMap")
1195  @Deprecated
1196  public static <T extends @Nullable Object, K, V>
1197      Collector<T, ?, ImmutableMap<K, V>> toImmutableMap(
1198          Function<? super T, ? extends K> keyFunction,
1199          Function<? super T, ? extends V> valueFunction,
1200          BinaryOperator<V> mergeFunction) {
1201    throw new UnsupportedOperationException();
1202  }
1203
1204  /**
1205   * Not supported. Use {@link #naturalOrder}, which offers better type-safety, instead. This method
1206   * exists only to hide {@link ImmutableMap#builder} from consumers of {@code ImmutableSortedMap}.
1207   *
1208   * @throws UnsupportedOperationException always
1209   * @deprecated Use {@link ImmutableSortedMap#naturalOrder}, which offers better type-safety.
1210   */
1211  @DoNotCall("Use naturalOrder")
1212  @Deprecated
1213  public static <K, V> ImmutableSortedMap.Builder<K, V> builder() {
1214    throw new UnsupportedOperationException();
1215  }
1216
1217  /**
1218   * Not supported for ImmutableSortedMap.
1219   *
1220   * @throws UnsupportedOperationException always
1221   * @deprecated Not supported for ImmutableSortedMap.
1222   */
1223  @DoNotCall("Use naturalOrder (which does not accept an expected size)")
1224  @Deprecated
1225  public static <K, V> ImmutableSortedMap.Builder<K, V> builderWithExpectedSize(int expectedSize) {
1226    throw new UnsupportedOperationException();
1227  }
1228
1229  /**
1230   * Not supported. <b>You are attempting to create a map that may contain a non-{@code Comparable}
1231   * key.</b> Proper calls will resolve to the version in {@code ImmutableSortedMap}, not this dummy
1232   * version.
1233   *
1234   * @throws UnsupportedOperationException always
1235   * @deprecated <b>Pass a key of type {@code Comparable} to use {@link
1236   *     ImmutableSortedMap#of(Comparable, Object)}.</b>
1237   */
1238  @DoNotCall("Pass a key of type Comparable")
1239  @Deprecated
1240  public static <K, V> ImmutableSortedMap<K, V> of(K k1, V v1) {
1241    throw new UnsupportedOperationException();
1242  }
1243
1244  /**
1245   * Not supported. <b>You are attempting to create a map that may contain non-{@code Comparable}
1246   * keys.</b> Proper calls will resolve to the version in {@code ImmutableSortedMap}, not this
1247   * dummy version.
1248   *
1249   * @throws UnsupportedOperationException always
1250   * @deprecated <b>Pass keys of type {@code Comparable} to use {@link
1251   *     ImmutableSortedMap#of(Comparable, Object, Comparable, Object)}.</b>
1252   */
1253  @DoNotCall("Pass keys of type Comparable")
1254  @Deprecated
1255  public static <K, V> ImmutableSortedMap<K, V> of(K k1, V v1, K k2, V v2) {
1256    throw new UnsupportedOperationException();
1257  }
1258
1259  /**
1260   * Not supported. <b>You are attempting to create a map that may contain non-{@code Comparable}
1261   * keys.</b> Proper calls to will resolve to the version in {@code ImmutableSortedMap}, not this
1262   * dummy version.
1263   *
1264   * @throws UnsupportedOperationException always
1265   * @deprecated <b>Pass keys of type {@code Comparable} to use {@link
1266   *     ImmutableSortedMap#of(Comparable, Object, Comparable, Object, Comparable, Object)}.</b>
1267   */
1268  @DoNotCall("Pass keys of type Comparable")
1269  @Deprecated
1270  public static <K, V> ImmutableSortedMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3) {
1271    throw new UnsupportedOperationException();
1272  }
1273
1274  /**
1275   * Not supported. <b>You are attempting to create a map that may contain non-{@code Comparable}
1276   * keys.</b> Proper calls will resolve to the version in {@code ImmutableSortedMap}, not this
1277   * dummy version.
1278   *
1279   * @throws UnsupportedOperationException always
1280   * @deprecated <b>Pass keys of type {@code Comparable} to use {@link
1281   *     ImmutableSortedMap#of(Comparable, Object, Comparable, Object, Comparable, Object,
1282   *     Comparable, Object)}.</b>
1283   */
1284  @DoNotCall("Pass keys of type Comparable")
1285  @Deprecated
1286  public static <K, V> ImmutableSortedMap<K, V> of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
1287    throw new UnsupportedOperationException();
1288  }
1289
1290  /**
1291   * Not supported. <b>You are attempting to create a map that may contain non-{@code Comparable}
1292   * keys.</b> Proper calls will resolve to the version in {@code ImmutableSortedMap}, not this
1293   * dummy version.
1294   *
1295   * @throws UnsupportedOperationException always
1296   * @deprecated <b>Pass keys of type {@code Comparable} to use {@link
1297   *     ImmutableSortedMap#of(Comparable, Object, Comparable, Object, Comparable, Object,
1298   *     Comparable, Object, Comparable, Object)}.</b>
1299   */
1300  @DoNotCall("Pass keys of type Comparable")
1301  @Deprecated
1302  public static <K, V> ImmutableSortedMap<K, V> of(
1303      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
1304    throw new UnsupportedOperationException();
1305  }
1306
1307  /**
1308   * Not supported. <b>You are attempting to create a map that may contain non-{@code Comparable}
1309   * keys.</b> Proper calls will resolve to the version in {@code ImmutableSortedMap}, not this
1310   * dummy version.
1311   *
1312   * @throws UnsupportedOperationException always
1313   * @deprecated <b>Pass keys of type {@code Comparable} to use {@link
1314   *     ImmutableSortedMap#of(Comparable, Object, Comparable, Object, Comparable, Object,
1315   *     Comparable, Object, Comparable, Object)}.</b>
1316   */
1317  @DoNotCall("Pass keys of type Comparable")
1318  @Deprecated
1319  public static <K, V> ImmutableSortedMap<K, V> of(
1320      K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5, K k6, V v6) {
1321    throw new UnsupportedOperationException();
1322  }
1323
1324  /**
1325   * Not supported. <b>You are attempting to create a map that may contain non-{@code Comparable}
1326   * keys.</b> Proper calls will resolve to the version in {@code ImmutableSortedMap}, not this
1327   * dummy version.
1328   *
1329   * @throws UnsupportedOperationException always
1330   * @deprecated <b>Pass keys of type {@code Comparable} to use {@link
1331   *     ImmutableSortedMap#of(Comparable, Object, Comparable, Object, Comparable, Object,
1332   *     Comparable, Object, Comparable, Object)}.</b>
1333   */
1334  @DoNotCall("Pass keys of type Comparable")
1335  @Deprecated
1336  public static <K, V> ImmutableSortedMap<K, V> of(
1337      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) {
1338    throw new UnsupportedOperationException();
1339  }
1340
1341  /**
1342   * Not supported. <b>You are attempting to create a map that may contain non-{@code Comparable}
1343   * keys.</b> Proper calls will resolve to the version in {@code ImmutableSortedMap}, not this
1344   * dummy version.
1345   *
1346   * @throws UnsupportedOperationException always
1347   * @deprecated <b>Pass keys of type {@code Comparable} to use {@link
1348   *     ImmutableSortedMap#of(Comparable, Object, Comparable, Object, Comparable, Object,
1349   *     Comparable, Object, Comparable, Object)}.</b>
1350   */
1351  @DoNotCall("Pass keys of type Comparable")
1352  @Deprecated
1353  public static <K, V> ImmutableSortedMap<K, V> of(
1354      K k1,
1355      V v1,
1356      K k2,
1357      V v2,
1358      K k3,
1359      V v3,
1360      K k4,
1361      V v4,
1362      K k5,
1363      V v5,
1364      K k6,
1365      V v6,
1366      K k7,
1367      V v7,
1368      K k8,
1369      V v8) {
1370    throw new UnsupportedOperationException();
1371  }
1372
1373  /**
1374   * Not supported. <b>You are attempting to create a map that may contain non-{@code Comparable}
1375   * keys.</b> Proper calls will resolve to the version in {@code ImmutableSortedMap}, not this
1376   * dummy version.
1377   *
1378   * @throws UnsupportedOperationException always
1379   * @deprecated <b>Pass keys of type {@code Comparable} to use {@link
1380   *     ImmutableSortedMap#of(Comparable, Object, Comparable, Object, Comparable, Object,
1381   *     Comparable, Object, Comparable, Object)}.</b>
1382   */
1383  @DoNotCall("Pass keys of type Comparable")
1384  @Deprecated
1385  public static <K, V> ImmutableSortedMap<K, V> of(
1386      K k1,
1387      V v1,
1388      K k2,
1389      V v2,
1390      K k3,
1391      V v3,
1392      K k4,
1393      V v4,
1394      K k5,
1395      V v5,
1396      K k6,
1397      V v6,
1398      K k7,
1399      V v7,
1400      K k8,
1401      V v8,
1402      K k9,
1403      V v9) {
1404    throw new UnsupportedOperationException();
1405  }
1406
1407  /**
1408   * Not supported. <b>You are attempting to create a map that may contain non-{@code Comparable}
1409   * keys.</b> Proper calls will resolve to the version in {@code ImmutableSortedMap}, not this
1410   * dummy version.
1411   *
1412   * @throws UnsupportedOperationException always
1413   * @deprecated <b>Pass keys of type {@code Comparable} to use {@link
1414   *     ImmutableSortedMap#of(Comparable, Object, Comparable, Object, Comparable, Object,
1415   *     Comparable, Object, Comparable, Object)}.</b>
1416   */
1417  @DoNotCall("Pass keys of type Comparable")
1418  @Deprecated
1419  public static <K, V> ImmutableSortedMap<K, V> of(
1420      K k1,
1421      V v1,
1422      K k2,
1423      V v2,
1424      K k3,
1425      V v3,
1426      K k4,
1427      V v4,
1428      K k5,
1429      V v5,
1430      K k6,
1431      V v6,
1432      K k7,
1433      V v7,
1434      K k8,
1435      V v8,
1436      K k9,
1437      V v9,
1438      K k10,
1439      V v10) {
1440    throw new UnsupportedOperationException();
1441  }
1442
1443  /**
1444   * Not supported. Use {@code ImmutableSortedMap.copyOf(ImmutableMap.ofEntries(...))}.
1445   *
1446   * @deprecated Use {@code ImmutableSortedMap.copyOf(ImmutableMap.ofEntries(...))}.
1447   */
1448  @DoNotCall("ImmutableSortedMap.ofEntries not currently available; use ImmutableSortedMap.copyOf")
1449  @Deprecated
1450  @SafeVarargs
1451  public static <K, V> ImmutableSortedMap<K, V> ofEntries(
1452      Entry<? extends K, ? extends V>... entries) {
1453    throw new UnsupportedOperationException();
1454  }
1455}