    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
    017    package com.google.common.collect;
    018
    019    import static com.google.common.base.Preconditions.checkArgument;
    020    import static com.google.common.base.Preconditions.checkNotNull;
    021    import static com.google.common.collect.SortedLists.KeyAbsentBehavior.INVERTED_INSERTION_INDEX;
    022    import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_HIGHER;
    023    import static com.google.common.collect.SortedLists.KeyAbsentBehavior.NEXT_LOWER;
    024    import static com.google.common.collect.SortedLists.KeyPresentBehavior.ANY_PRESENT;
    025
    026    import com.google.common.annotations.GwtCompatible;
    027    import com.google.common.collect.SortedLists.KeyAbsentBehavior;
    028    import com.google.common.collect.SortedLists.KeyPresentBehavior;
    029
    030    import java.io.Serializable;
    031    import java.util.Arrays;
    032    import java.util.Collections;
    033    import java.util.Comparator;
    034    import java.util.List;
    035    import java.util.Map;
    036    import java.util.NoSuchElementException;
    037    import java.util.SortedMap;
    038    import java.util.TreeMap;
    039
    040    import javax.annotation.Nullable;
    041
    042    /**
    043     * An immutable {@link SortedMap}. Does not permit null keys or values.
    044     *
    045     * <p>Unlike {@link Collections#unmodifiableSortedMap}, which is a <i>view</i>
    046     * of a separate map which can still change, an instance of {@code
    047     * ImmutableSortedMap} contains its own data and will <i>never</i> change.
    048     * {@code ImmutableSortedMap} is convenient for {@code public static final} maps
    049     * ("constant maps") and also lets you easily make a "defensive copy" of a map
    050     * provided to your class by a caller.
    051     *
    052     * <p><b>Note:</b> Although this class is not final, it cannot be subclassed as
    053     * it has no public or protected constructors. Thus, instances of this class are
    054     * guaranteed to be immutable.
    055     *
    056     * @author Jared Levy
    057     * @author Louis Wasserman
    058     * @since 2.0 (imported from Google Collections Library)
    059     */
    060    @GwtCompatible(serializable = true, emulated = true)
    061    public class ImmutableSortedMap<K, V>
    062        extends ImmutableSortedMapFauxverideShim<K, V> implements SortedMap<K, V> {
    063      /*
    064       * TODO(kevinb): Confirm that ImmutableSortedMap is faster to construct and
    065       * uses less memory than TreeMap; then say so in the class Javadoc.
    066       *
    067       * TODO(kevinb): Create separate subclasses for empty, single-entry, and
    068       * multiple-entry instances, if it's deemed beneficial.
    069       */
    070
    071      private static final Comparator<Comparable> NATURAL_ORDER =
    072          Ordering.natural();
    073
    074      private static final ImmutableSortedMap<Comparable, Object>
    075          NATURAL_EMPTY_MAP =
    076              new ImmutableSortedMap<Comparable, Object>(
    077                  ImmutableList.<Entry<Comparable, Object>>of(), NATURAL_ORDER);
    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      @SuppressWarnings("unchecked")
    090      private static <K, V> ImmutableSortedMap<K, V> emptyMap(
    091          Comparator<? super K> comparator) {
    092        if (NATURAL_ORDER.equals(comparator)) {
    093          return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP;
    094        } else {
    095          return new ImmutableSortedMap<K, V>(
    096              ImmutableList.<Entry<K, V>>of(), comparator);
    097        }
    098      }
    099
    100      /**
    101       * Returns an immutable map containing a single entry.
    102       */
    103      public static <K extends Comparable<? super K>, V>
    104          ImmutableSortedMap<K, V> of(K k1, V v1) {
    105        return new ImmutableSortedMap<K, V>(
    106            ImmutableList.of(entryOf(k1, v1)), Ordering.natural());
    107      }
    108
    109      /**
    110       * Returns an immutable sorted map containing the given entries, sorted by the
    111       * natural ordering of their keys.
    112       *
    113       * @throws IllegalArgumentException if the two keys are equal according to
    114       *     their natural ordering
    115       */
    116      public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V>
    117          of(K k1, V v1, K k2, V v2) {
    118        return new Builder<K, V>(Ordering.natural())
    119            .put(k1, v1).put(k2, v2).build();
    120      }
    121
    122      /**
    123       * Returns an immutable sorted map containing the given entries, sorted by the
    124       * natural ordering of their keys.
    125       *
    126       * @throws IllegalArgumentException if any two keys are equal according to
    127       *     their natural ordering
    128       */
    129      public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V>
    130          of(K k1, V v1, K k2, V v2, K k3, V v3) {
    131        return new Builder<K, V>(Ordering.natural())
    132            .put(k1, v1).put(k2, v2).put(k3, v3).build();
    133      }
    134
    135      /**
    136       * Returns an immutable sorted map containing the given entries, sorted by the
    137       * natural ordering of their keys.
    138       *
    139       * @throws IllegalArgumentException if any two keys are equal according to
    140       *     their natural ordering
    141       */
    142      public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V>
    143          of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
    144        return new Builder<K, V>(Ordering.natural())
    145            .put(k1, v1).put(k2, v2).put(k3, v3).put(k4, v4).build();
    146      }
    147
    148      /**
    149       * Returns an immutable sorted map containing the given entries, sorted by the
    150       * natural ordering of their keys.
    151       *
    152       * @throws IllegalArgumentException if any two keys are equal according to
    153       *     their natural ordering
    154       */
    155      public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V>
    156          of(K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
    157        return new Builder<K, V>(Ordering.natural())
    158            .put(k1, v1).put(k2, v2).put(k3, v3).put(k4, v4).put(k5, v5).build();
    159      }
    160
    161      /**
    162       * Returns an immutable map containing the same entries as {@code map}, sorted
    163       * by the natural ordering of the keys.
    164       *
    165       * <p>Despite the method name, this method attempts to avoid actually copying
    166       * the data when it is safe to do so. The exact circumstances under which a
    167       * copy will or will not be performed are undocumented and subject to change.
    168       *
    169       * <p>This method is not type-safe, as it may be called on a map with keys
    170       * that are not mutually comparable.
    171       *
    172       * @throws ClassCastException if the keys in {@code map} are not mutually
    173       *         comparable
    174       * @throws NullPointerException if any key or value in {@code map} is null
    175       * @throws IllegalArgumentException if any two keys are equal according to
    176       *         their natural ordering
    177       */
    178      public static <K, V> ImmutableSortedMap<K, V> copyOf(
    179          Map<? extends K, ? extends V> map) {
    180        // Hack around K not being a subtype of Comparable.
    181        // Unsafe, see ImmutableSortedSetFauxverideShim.
    182        @SuppressWarnings("unchecked")
    183        Ordering<K> naturalOrder = (Ordering<K>) Ordering.<Comparable>natural();
    184        return copyOfInternal(map, naturalOrder);
    185      }
    186
    187      /**
    188       * Returns an immutable map containing the same entries as {@code map}, with
    189       * keys sorted by the provided comparator.
    190       *
    191       * <p>Despite the method name, this method attempts to avoid actually copying
    192       * the data when it is safe to do so. The exact circumstances under which a
    193       * copy will or will not be performed are undocumented and subject to change.
    194       *
    195       * @throws NullPointerException if any key or value in {@code map} is null
    196       * @throws IllegalArgumentException if any two keys are equal according to the
    197       *         comparator
    198       */
    199      public static <K, V> ImmutableSortedMap<K, V> copyOf(
    200          Map<? extends K, ? extends V> map, Comparator<? super K> comparator) {
    201        return copyOfInternal(map, checkNotNull(comparator));
    202      }
    203
    204      /**
    205       * Returns an immutable map containing the same entries as the provided sorted
    206       * map, with the same ordering.
    207       *
    208       * <p>Despite the method name, this method attempts to avoid actually copying
    209       * the data when it is safe to do so. The exact circumstances under which a
    210       * copy will or will not be performed are undocumented and subject to change.
    211       *
    212       * @throws NullPointerException if any key or value in {@code map} is null
    213       */
    214      @SuppressWarnings("unchecked")
    215      public static <K, V> ImmutableSortedMap<K, V> copyOfSorted(
    216          SortedMap<K, ? extends V> map) {
    217        Comparator<? super K> comparator = map.comparator();
    218        if (comparator == null) {
    219          // If map has a null comparator, the keys should have a natural ordering,
    220          // even though K doesn't explicitly implement Comparable.
    221          comparator = (Comparator<? super K>) NATURAL_ORDER;
    222        }
    223        return copyOfInternal(map, comparator);
    224      }
    225
    226      private static <K, V> ImmutableSortedMap<K, V> copyOfInternal(
    227          Map<? extends K, ? extends V> map, Comparator<? super K> comparator) {
    228        boolean sameComparator = false;
    229        if (map instanceof SortedMap) {
    230          SortedMap<?, ?> sortedMap = (SortedMap<?, ?>) map;
    231          Comparator<?> comparator2 = sortedMap.comparator();
    232          sameComparator = (comparator2 == null)
    233              ? comparator == NATURAL_ORDER
    234              : comparator.equals(comparator2);
    235        }
    236
    237        if (sameComparator && (map instanceof ImmutableSortedMap)) {
    238          // TODO(kevinb): Prove that this cast is safe, even though
    239          // Collections.unmodifiableSortedMap requires the same key type.
    240          @SuppressWarnings("unchecked")
    241          ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map;
    242          if (!kvMap.isPartialView()) {
    243            return kvMap;
    244          }
    245        }
    246
    247        // "adding" type params to an array of a raw type should be safe as
    248        // long as no one can ever cast that same array instance back to a
    249        // raw type.
    250        @SuppressWarnings("unchecked")
    251        Entry<K, V>[] entries = map.entrySet().toArray(new Entry[0]);
    252
    253        for (int i = 0; i < entries.length; i++) {
    254          Entry<K, V> entry = entries[i];
    255          entries[i] = entryOf(entry.getKey(), entry.getValue());
    256        }
    257
    258        List<Entry<K, V>> list = Arrays.asList(entries);
    259
    260        if (!sameComparator) {
    261          sortEntries(list, comparator);
    262          validateEntries(list, comparator);
    263        }
    264
    265        return new ImmutableSortedMap<K, V>(ImmutableList.copyOf(list), comparator);
    266      }
    267
    268      private static <K, V> void sortEntries(
    269          List<Entry<K, V>> entries, final Comparator<? super K> comparator) {
    270        Comparator<Entry<K, V>> entryComparator = new Comparator<Entry<K, V>>() {
    271
    272          @Override public int compare(Entry<K, V> entry1, Entry<K, V> entry2) {
    273            return comparator.compare(entry1.getKey(), entry2.getKey());
    274          }
    275        };
    276
    277        Collections.sort(entries, entryComparator);
    278      }
    279
    280      private static <K, V> void validateEntries(List<Entry<K, V>> entries,
    281          Comparator<? super K> comparator) {
    282        for (int i = 1; i < entries.size(); i++) {
    283          if (comparator.compare(
    284              entries.get(i - 1).getKey(), entries.get(i).getKey()) == 0) {
    285            throw new IllegalArgumentException(
    286                "Duplicate keys in mappings " + entries.get(i - 1) + " and "
    287                    + entries.get(i));
    288          }
    289        }
    290      }
    291
    292      /**
    293       * Returns a builder that creates immutable sorted maps whose keys are
    294       * ordered by their natural ordering. The sorted maps use {@link
    295       * Ordering#natural()} as the comparator.
    296       *
    297       * <p>Note: the type parameter {@code K} extends {@code Comparable<K>} rather
    298       * than {@code Comparable<? super K>} as a workaround for javac <a
    299       * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
    300       * 6468354</a>.
    301       */
    302      public static <K extends Comparable<K>, V> Builder<K, V> naturalOrder() {
    303        return new Builder<K, V>(Ordering.natural());
    304      }
    305
    306      /**
    307       * Returns a builder that creates immutable sorted maps with an explicit
    308       * comparator. If the comparator has a more general type than the map's keys,
    309       * such as creating a {@code SortedMap<Integer, String>} with a {@code
    310       * Comparator<Number>}, use the {@link Builder} constructor instead.
    311       *
    312       * @throws NullPointerException if {@code comparator} is null
    313       */
    314      public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) {
    315        return new Builder<K, V>(comparator);
    316      }
    317
    318      /**
    319       * Returns a builder that creates immutable sorted maps whose keys are
    320       * ordered by the reverse of their natural ordering.
    321       *
    322       * <p>Note: the type parameter {@code K} extends {@code Comparable<K>} rather
    323       * than {@code Comparable<? super K>} as a workaround for javac <a
    324       * href="http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6468354">bug
    325       * 6468354</a>.
    326       */
    327      public static <K extends Comparable<K>, V> Builder<K, V> reverseOrder() {
    328        return new Builder<K, V>(Ordering.natural().reverse());
    329      }
    330
    331      /**
    332       * A builder for creating immutable sorted map instances, especially {@code
    333       * public static final} maps ("constant maps"). Example: <pre>   {@code
    334       *
    335       *   static final ImmutableSortedMap<Integer, String> INT_TO_WORD =
    336       *       new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural())
    337       *           .put(1, "one")
    338       *           .put(2, "two")
    339       *           .put(3, "three")
    340       *           .build();}</pre>
    341       *
    342       * For <i>small</i> immutable sorted maps, the {@code ImmutableSortedMap.of()}
    343       * methods are even more convenient.
    344       *
    345       * <p>Builder instances can be reused - it is safe to call {@link #build}
    346       * multiple times to build multiple maps in series. Each map is a superset of
    347       * the maps created before it.
    348       *
    349       * @since 2.0 (imported from Google Collections Library)
    350       */
    351      public static class Builder<K, V> extends ImmutableMap.Builder<K, V> {
    352        private final Comparator<? super K> comparator;
    353
    354        /**
    355         * Creates a new builder. The returned builder is equivalent to the builder
    356         * generated by {@link ImmutableSortedMap#orderedBy}.
    357         */
    358        public Builder(Comparator<? super K> comparator) {
    359          this.comparator = checkNotNull(comparator);
    360        }
    361
    362        /**
    363         * Associates {@code key} with {@code value} in the built map. Duplicate
    364         * keys, according to the comparator (which might be the keys' natural
    365         * order), are not allowed, and will cause {@link #build} to fail.
    366         */
    367        @Override public Builder<K, V> put(K key, V value) {
    368          entries.add(entryOf(key, value));
    369          return this;
    370        }
    371
    372        /**
    373         * Associates all of the given map's keys and values in the built map.
    374         * Duplicate keys, according to the comparator (which might be the keys'
    375         * natural order), are not allowed, and will cause {@link #build} to fail.
    376         *
    377         * @throws NullPointerException if any key or value in {@code map} is null
    378         */
    379        @Override public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
    380          for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
    381            put(entry.getKey(), entry.getValue());
    382          }
    383          return this;
    384        }
    385
    386        /**
    387         * Returns a newly-created immutable sorted map.
    388         *
    389         * @throws IllegalArgumentException if any two keys are equal according to
    390         *     the comparator (which might be the keys' natural order)
    391         */
    392        @Override public ImmutableSortedMap<K, V> build() {
    393          sortEntries(entries, comparator);
    394          validateEntries(entries, comparator);
    395          return new ImmutableSortedMap<K, V>(
    396              ImmutableList.copyOf(entries), comparator);
    397        }
    398      }
    399
    400      final transient ImmutableList<Entry<K, V>> entries;
    401      private final transient Comparator<? super K> comparator;
    402
    403      ImmutableSortedMap(
    404          ImmutableList<Entry<K, V>> entries, Comparator<? super K> comparator) {
    405        this.entries = entries;
    406        this.comparator = comparator;
    407      }
    408
    409      @Override
    410      public int size() {
    411        return entries.size();
    412      }
    413
    414      // Pretend the comparator can compare anything. If it turns out it can't
    415      // compare two elements, it'll throw a CCE. Only methods that are specified to
    416      // throw CCE should call this.
    417      @SuppressWarnings("unchecked")
    418      Comparator<Object> unsafeComparator() {
    419        return (Comparator<Object>) comparator;
    420      }
    421
    422      @Override public V get(@Nullable Object key) {
    423        if (key == null) {
    424          return null;
    425        }
    426        int i;
    427        try {
    428          i = index(key, ANY_PRESENT, INVERTED_INSERTION_INDEX);
    429        } catch (ClassCastException e) {
    430          return null;
    431        }
    432        return i >= 0 ? entries.get(i).getValue() : null;
    433      }
    434
    435      @Override public boolean containsValue(@Nullable Object value) {
    436        if (value == null) {
    437          return false;
    438        }
    439        return Iterators.contains(valueIterator(), value);
    440      }
    441
    442      @Override boolean isPartialView() {
    443        return entries.isPartialView();
    444      }
    445
    446      private transient ImmutableSet<Entry<K, V>> entrySet;
    447
    448      /**
    449       * Returns an immutable set of the mappings in this map, sorted by the key
    450       * ordering.
    451       */
    452      @Override public ImmutableSet<Entry<K, V>> entrySet() {
    453        ImmutableSet<Entry<K, V>> es = entrySet;
    454        return (es == null) ? (entrySet = createEntrySet()) : es;
    455      }
    456
    457      private ImmutableSet<Entry<K, V>> createEntrySet() {
    458        return isEmpty() ? ImmutableSet.<Entry<K, V>>of()
    459            : new EntrySet<K, V>(this);
    460      }
    461
    462      @SuppressWarnings("serial") // uses writeReplace(), not default serialization
    463      private static class EntrySet<K, V> extends ImmutableSet<Entry<K, V>> {
    464        final transient ImmutableSortedMap<K, V> map;
    465
    466        EntrySet(ImmutableSortedMap<K, V> map) {
    467          this.map = map;
    468        }
    469
    470        @Override boolean isPartialView() {
    471          return map.isPartialView();
    472        }
    473
    474        @Override
    475        public int size() {
    476          return map.size();
    477        }
    478
    479        @Override public UnmodifiableIterator<Entry<K, V>> iterator() {
    480          return map.entries.iterator();
    481        }
    482
    483        @Override public boolean contains(Object target) {
    484          if (target instanceof Entry) {
    485            Entry<?, ?> entry = (Entry<?, ?>) target;
    486            V mappedValue = map.get(entry.getKey());
    487            return mappedValue != null && mappedValue.equals(entry.getValue());
    488          }
    489          return false;
    490        }
    491
    492        @Override Object writeReplace() {
    493          return new EntrySetSerializedForm<K, V>(map);
    494        }
    495      }
    496
    497      private static class EntrySetSerializedForm<K, V> implements Serializable {
    498        final ImmutableSortedMap<K, V> map;
    499        EntrySetSerializedForm(ImmutableSortedMap<K, V> map) {
    500          this.map = map;
    501        }
    502        Object readResolve() {
    503          return map.entrySet();
    504        }
    505        private static final long serialVersionUID = 0;
    506      }
    507
    508      private transient ImmutableSortedSet<K> keySet;
    509
    510      /**
    511       * Returns an immutable sorted set of the keys in this map.
    512       */
    513      @Override public ImmutableSortedSet<K> keySet() {
    514        ImmutableSortedSet<K> ks = keySet;
    515        return (ks == null) ? (keySet = createKeySet()) : ks;
    516      }
    517
    518      @SuppressWarnings("serial") // does not use default serialization
    519      private ImmutableSortedSet<K> createKeySet() {
    520        if (isEmpty()) {
    521          return ImmutableSortedSet.emptySet(comparator);
    522        }
    523
    524        return new RegularImmutableSortedSet<K>(
    525            new TransformedImmutableList<Entry<K, V>, K>(entries) {
    526
    527              @Override K transform(Entry<K, V> entry) {
    528                return entry.getKey();
    529              }
    530            }, comparator);
    531      }
    532
    533      private transient ImmutableCollection<V> values;
    534
    535      /**
    536       * Returns an immutable collection of the values in this map, sorted by the
    537       * ordering of the corresponding keys.
    538       */
    539      @Override public ImmutableCollection<V> values() {
    540        ImmutableCollection<V> v = values;
    541        return (v == null) ? (values = new Values<V>(this)) : v;
    542      }
    543
    544      UnmodifiableIterator<V> valueIterator(){
    545        final UnmodifiableIterator<Entry<K, V>> entryIterator = entries.iterator();
    546        return new UnmodifiableIterator<V>() {
    547
    548          @Override public boolean hasNext() {
    549            return entryIterator.hasNext();
    550          }
    551
    552          @Override public V next() {
    553            return entryIterator.next().getValue();
    554          }
    555        };
    556      }
    557
    558      @SuppressWarnings("serial") // uses writeReplace(), not default serialization
    559      private static class Values<V> extends ImmutableCollection<V> {
    560        private final ImmutableSortedMap<?, V> map;
    561
    562        Values(ImmutableSortedMap<?, V> map) {
    563          this.map = map;
    564        }
    565
    566        @Override
    567        public int size() {
    568          return map.size();
    569        }
    570
    571        @Override public UnmodifiableIterator<V> iterator() {
    572          return map.valueIterator();
    573        }
    574
    575        @Override public boolean contains(Object target) {
    576          return map.containsValue(target);
    577        }
    578
    579        @Override boolean isPartialView() {
    580          return true;
    581        }
    582
    583        @Override Object writeReplace() {
    584          return new ValuesSerializedForm<V>(map);
    585        }
    586      }
    587
    588      private static class ValuesSerializedForm<V> implements Serializable {
    589        final ImmutableSortedMap<?, V> map;
    590        ValuesSerializedForm(ImmutableSortedMap<?, V> map) {
    591          this.map = map;
    592        }
    593        Object readResolve() {
    594          return map.values();
    595        }
    596        private static final long serialVersionUID = 0;
    597      }
    598
    599      /**
    600       * Returns the comparator that orders the keys, which is
    601       * {@link Ordering#natural()} when the natural ordering of the keys is used.
    602       * Note that its behavior is not consistent with {@link TreeMap#comparator()},
    603       * which returns {@code null} to indicate natural ordering.
    604       */
    605      @Override
    606      public Comparator<? super K> comparator() {
    607        return comparator;
    608      }
    609
    610      @Override
    611      public K firstKey() {
    612        if (isEmpty()) {
    613          throw new NoSuchElementException();
    614        }
    615        return entries.get(0).getKey();
    616      }
    617
    618      @Override
    619      public K lastKey() {
    620        if (isEmpty()) {
    621          throw new NoSuchElementException();
    622        }
    623        return entries.get(size() - 1).getKey();
    624      }
    625
    626      /**
    627       * This method returns a {@code ImmutableSortedMap}, consisting of the entries
    628       * whose keys are less than {@code toKey}.
    629       *
    630       * <p>The {@link SortedMap#headMap} documentation states that a submap of a
    631       * submap throws an {@link IllegalArgumentException} if passed a {@code toKey}
    632       * greater than an earlier {@code toKey}. However, this method doesn't throw
    633       * an exception in that situation, but instead keeps the original {@code
    634       * toKey}.
    635       */
    636      @Override
    637      public ImmutableSortedMap<K, V> headMap(K toKey) {
    638        return headMap(toKey, false);
    639      }
    640
    641      ImmutableSortedMap<K, V> headMap(K toKey, boolean inclusive){
    642        int index;
    643        if (inclusive) {
    644          index = index(toKey, ANY_PRESENT, NEXT_LOWER) + 1;
    645        } else {
    646          index = index(toKey, ANY_PRESENT, NEXT_HIGHER);
    647        }
    648        return createSubmap(0, index);
    649      }
    650
    651      /**
    652       * This method returns a {@code ImmutableSortedMap}, consisting of the entries
    653       * whose keys ranges from {@code fromKey}, inclusive, to {@code toKey},
    654       * exclusive.
    655       *
    656       * <p>The {@link SortedMap#subMap} documentation states that a submap of a
    657       * submap throws an {@link IllegalArgumentException} if passed a {@code
    658       * fromKey} less than an earlier {@code fromKey}. However, this method doesn't
    659       * throw an exception in that situation, but instead keeps the original {@code
    660       * fromKey}. Similarly, this method keeps the original {@code toKey}, instead
    661       * of throwing an exception, if passed a {@code toKey} greater than an earlier
    662       * {@code toKey}.
    663       */
    664      @Override
    665      public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) {
    666        return subMap(fromKey, true, toKey, false);
    667      }
    668
    669      ImmutableSortedMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey,
    670          boolean toInclusive) {
    671        checkNotNull(fromKey);
    672        checkNotNull(toKey);
    673        checkArgument(comparator.compare(fromKey, toKey) <= 0);
    674        return tailMap(fromKey, fromInclusive).headMap(toKey, toInclusive);
    675      }
    676
    677      /**
    678       * This method returns a {@code ImmutableSortedMap}, consisting of the entries
    679       * whose keys are greater than or equals to {@code fromKey}.
    680       *
    681       * <p>The {@link SortedMap#tailMap} documentation states that a submap of a
    682       * submap throws an {@link IllegalArgumentException} if passed a {@code
    683       * fromKey} less than an earlier {@code fromKey}. However, this method doesn't
    684       * throw an exception in that situation, but instead keeps the original {@code
    685       * fromKey}.
    686       */
    687      @Override
    688      public ImmutableSortedMap<K, V> tailMap(K fromKey) {
    689        return tailMap(fromKey, true);
    690      }
    691
    692      ImmutableSortedMap<K, V> tailMap(K fromKey, boolean inclusive) {
    693        int index;
    694        if (inclusive) {
    695          index = index(fromKey, ANY_PRESENT, NEXT_HIGHER);
    696        } else {
    697          index = index(fromKey, ANY_PRESENT, NEXT_LOWER) + 1;
    698        }
    699        return createSubmap(index, size());
    700      }
    701
    702      private ImmutableList<K> keyList() {
    703        return new TransformedImmutableList<Entry<K, V>, K>(entries) {
    704          @Override
    705          K transform(Entry<K, V> entry) {
    706            return entry.getKey();
    707          }
    708        };
    709      }
    710
    711      private int index(
    712          Object key, KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) {
    713        return SortedLists.binarySearch(
    714            keyList(), checkNotNull(key), unsafeComparator(), presentBehavior, absentBehavior);
    715      }
    716
    717      private ImmutableSortedMap<K, V> createSubmap(
    718          int newFromIndex, int newToIndex) {
    719        if (newFromIndex < newToIndex) {
    720          return new ImmutableSortedMap<K, V>(
    721              entries.subList(newFromIndex, newToIndex), comparator);
    722        } else {
    723          return emptyMap(comparator);
    724        }
    725      }
    726
    727      /**
    728       * Serialized type for all ImmutableSortedMap instances. It captures the
    729       * logical contents and they are reconstructed using public factory methods.
    730       * This ensures that the implementation types remain as implementation
    731       * details.
    732       */
    733      private static class SerializedForm extends ImmutableMap.SerializedForm {
    734        private final Comparator<Object> comparator;
    735        @SuppressWarnings("unchecked")
    736        SerializedForm(ImmutableSortedMap<?, ?> sortedMap) {
    737          super(sortedMap);
    738          comparator = (Comparator<Object>) sortedMap.comparator();
    739        }
    740        @Override Object readResolve() {
    741          Builder<Object, Object> builder = new Builder<Object, Object>(comparator);
    742          return createMap(builder);
    743        }
    744        private static final long serialVersionUID = 0;
    745      }
    746
    747      @Override Object writeReplace() {
    748        return new SerializedForm(this);
    749      }
    750
    751      // This class is never actually serialized directly, but we have to make the
    752      // warning go away (and suppressing would suppress for all nested classes too)
    753      private static final long serialVersionUID = 0;
    754    }
    755