001/*
002 * Copyright (C) 2009 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkArgument;
020import static com.google.common.base.Preconditions.checkNotNull;
021import static com.google.common.collect.SortedLists.Relation.CEILING;
022import static com.google.common.collect.SortedLists.Relation.EQUAL;
023
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.base.Function;
026
027import java.io.Serializable;
028import java.util.Arrays;
029import java.util.Collections;
030import java.util.Comparator;
031import java.util.List;
032import java.util.Map;
033import java.util.NoSuchElementException;
034import java.util.SortedMap;
035import java.util.TreeMap;
036
037import 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)
058public 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}