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