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