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