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