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