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