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