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