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 * Adds the given {@code entry} to the map, making it immutable if
374 * necessary. Duplicate keys, according to the comparator (which might be
375 * the keys' natural order), are not allowed, and will cause {@link #build}
376 * to fail.
377 *
378 * @since 11.0
379 */
380 @Override public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
381 super.put(entry);
382 return this;
383 }
384
385 /**
386 * Associates all of the given map's keys and values in the built map.
387 * Duplicate keys, according to the comparator (which might be the keys'
388 * natural order), are not allowed, and will cause {@link #build} to fail.
389 *
390 * @throws NullPointerException if any key or value in {@code map} is null
391 */
392 @Override public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
393 for (Entry<? extends K, ? extends V> entry : map.entrySet()) {
394 put(entry.getKey(), entry.getValue());
395 }
396 return this;
397 }
398
399 /**
400 * Returns a newly-created immutable sorted map.
401 *
402 * @throws IllegalArgumentException if any two keys are equal according to
403 * the comparator (which might be the keys' natural order)
404 */
405 @Override public ImmutableSortedMap<K, V> build() {
406 sortEntries(entries, comparator);
407 validateEntries(entries, comparator);
408 return new ImmutableSortedMap<K, V>(
409 ImmutableList.copyOf(entries), comparator);
410 }
411 }
412
413 final transient ImmutableList<Entry<K, V>> entries;
414 private final transient Comparator<? super K> comparator;
415
416 ImmutableSortedMap(
417 ImmutableList<Entry<K, V>> entries, Comparator<? super K> comparator) {
418 this.entries = entries;
419 this.comparator = comparator;
420 }
421
422 @Override
423 public int size() {
424 return entries.size();
425 }
426
427 // Pretend the comparator can compare anything. If it turns out it can't
428 // compare two elements, it'll throw a CCE. Only methods that are specified to
429 // throw CCE should call this.
430 @SuppressWarnings("unchecked")
431 Comparator<Object> unsafeComparator() {
432 return (Comparator<Object>) comparator;
433 }
434
435 @Override public V get(@Nullable Object key) {
436 if (key == null) {
437 return null;
438 }
439 int i;
440 try {
441 i = index(key, ANY_PRESENT, INVERTED_INSERTION_INDEX);
442 } catch (ClassCastException e) {
443 return null;
444 }
445 return i >= 0 ? entries.get(i).getValue() : null;
446 }
447
448 @Override public boolean containsValue(@Nullable Object value) {
449 if (value == null) {
450 return false;
451 }
452 return Iterators.contains(valueIterator(), value);
453 }
454
455 @Override boolean isPartialView() {
456 return entries.isPartialView();
457 }
458
459 private transient ImmutableSet<Entry<K, V>> entrySet;
460
461 /**
462 * Returns an immutable set of the mappings in this map, sorted by the key
463 * ordering.
464 */
465 @Override public ImmutableSet<Entry<K, V>> entrySet() {
466 ImmutableSet<Entry<K, V>> es = entrySet;
467 return (es == null) ? (entrySet = createEntrySet()) : es;
468 }
469
470 private ImmutableSet<Entry<K, V>> createEntrySet() {
471 return isEmpty() ? ImmutableSet.<Entry<K, V>>of()
472 : new EntrySet<K, V>(this);
473 }
474
475 @SuppressWarnings("serial") // uses writeReplace(), not default serialization
476 private static class EntrySet<K, V> extends ImmutableSet<Entry<K, V>> {
477 final transient ImmutableSortedMap<K, V> map;
478
479 EntrySet(ImmutableSortedMap<K, V> map) {
480 this.map = map;
481 }
482
483 @Override boolean isPartialView() {
484 return map.isPartialView();
485 }
486
487 @Override
488 public int size() {
489 return map.size();
490 }
491
492 @Override public UnmodifiableIterator<Entry<K, V>> iterator() {
493 return map.entries.iterator();
494 }
495
496 @Override public boolean contains(Object target) {
497 if (target instanceof Entry) {
498 Entry<?, ?> entry = (Entry<?, ?>) target;
499 V mappedValue = map.get(entry.getKey());
500 return mappedValue != null && mappedValue.equals(entry.getValue());
501 }
502 return false;
503 }
504
505 @Override Object writeReplace() {
506 return new EntrySetSerializedForm<K, V>(map);
507 }
508 }
509
510 private static class EntrySetSerializedForm<K, V> implements Serializable {
511 final ImmutableSortedMap<K, V> map;
512 EntrySetSerializedForm(ImmutableSortedMap<K, V> map) {
513 this.map = map;
514 }
515 Object readResolve() {
516 return map.entrySet();
517 }
518 private static final long serialVersionUID = 0;
519 }
520
521 private transient ImmutableSortedSet<K> keySet;
522
523 /**
524 * Returns an immutable sorted set of the keys in this map.
525 */
526 @Override public ImmutableSortedSet<K> keySet() {
527 ImmutableSortedSet<K> ks = keySet;
528 return (ks == null) ? (keySet = createKeySet()) : ks;
529 }
530
531 @SuppressWarnings("serial") // does not use default serialization
532 private ImmutableSortedSet<K> createKeySet() {
533 if (isEmpty()) {
534 return ImmutableSortedSet.emptySet(comparator);
535 }
536
537 return new RegularImmutableSortedSet<K>(
538 new TransformedImmutableList<Entry<K, V>, K>(entries) {
539
540 @Override K transform(Entry<K, V> entry) {
541 return entry.getKey();
542 }
543 }, comparator);
544 }
545
546 private transient ImmutableCollection<V> values;
547
548 /**
549 * Returns an immutable collection of the values in this map, sorted by the
550 * ordering of the corresponding keys.
551 */
552 @Override public ImmutableCollection<V> values() {
553 ImmutableCollection<V> v = values;
554 return (v == null) ? (values = new Values<V>(this)) : v;
555 }
556
557 UnmodifiableIterator<V> valueIterator(){
558 final UnmodifiableIterator<Entry<K, V>> entryIterator = entries.iterator();
559 return new UnmodifiableIterator<V>() {
560
561 @Override public boolean hasNext() {
562 return entryIterator.hasNext();
563 }
564
565 @Override public V next() {
566 return entryIterator.next().getValue();
567 }
568 };
569 }
570
571 @SuppressWarnings("serial") // uses writeReplace(), not default serialization
572 private static class Values<V> extends ImmutableCollection<V> {
573 private final ImmutableSortedMap<?, V> map;
574
575 Values(ImmutableSortedMap<?, V> map) {
576 this.map = map;
577 }
578
579 @Override
580 public int size() {
581 return map.size();
582 }
583
584 @Override public UnmodifiableIterator<V> iterator() {
585 return map.valueIterator();
586 }
587
588 @Override public boolean contains(Object target) {
589 return map.containsValue(target);
590 }
591
592 @Override boolean isPartialView() {
593 return true;
594 }
595
596 @Override Object writeReplace() {
597 return new ValuesSerializedForm<V>(map);
598 }
599 }
600
601 private static class ValuesSerializedForm<V> implements Serializable {
602 final ImmutableSortedMap<?, V> map;
603 ValuesSerializedForm(ImmutableSortedMap<?, V> map) {
604 this.map = map;
605 }
606 Object readResolve() {
607 return map.values();
608 }
609 private static final long serialVersionUID = 0;
610 }
611
612 /**
613 * Returns the comparator that orders the keys, which is
614 * {@link Ordering#natural()} when the natural ordering of the keys is used.
615 * Note that its behavior is not consistent with {@link TreeMap#comparator()},
616 * which returns {@code null} to indicate natural ordering.
617 */
618 @Override
619 public Comparator<? super K> comparator() {
620 return comparator;
621 }
622
623 @Override
624 public K firstKey() {
625 if (isEmpty()) {
626 throw new NoSuchElementException();
627 }
628 return entries.get(0).getKey();
629 }
630
631 @Override
632 public K lastKey() {
633 if (isEmpty()) {
634 throw new NoSuchElementException();
635 }
636 return entries.get(size() - 1).getKey();
637 }
638
639 /**
640 * This method returns a {@code ImmutableSortedMap}, consisting of the entries
641 * whose keys are less than {@code toKey}.
642 *
643 * <p>The {@link SortedMap#headMap} documentation states that a submap of a
644 * submap throws an {@link IllegalArgumentException} if passed a {@code toKey}
645 * greater than an earlier {@code toKey}. However, this method doesn't throw
646 * an exception in that situation, but instead keeps the original {@code
647 * toKey}.
648 */
649 @Override
650 public ImmutableSortedMap<K, V> headMap(K toKey) {
651 return headMap(toKey, false);
652 }
653
654 ImmutableSortedMap<K, V> headMap(K toKey, boolean inclusive){
655 int index;
656 if (inclusive) {
657 index = index(toKey, ANY_PRESENT, NEXT_LOWER) + 1;
658 } else {
659 index = index(toKey, ANY_PRESENT, NEXT_HIGHER);
660 }
661 return createSubmap(0, index);
662 }
663
664 /**
665 * This method returns a {@code ImmutableSortedMap}, consisting of the entries
666 * whose keys ranges from {@code fromKey}, inclusive, to {@code toKey},
667 * exclusive.
668 *
669 * <p>The {@link SortedMap#subMap} documentation states that a submap of a
670 * submap throws an {@link IllegalArgumentException} if passed a {@code
671 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't
672 * throw an exception in that situation, but instead keeps the original {@code
673 * fromKey}. Similarly, this method keeps the original {@code toKey}, instead
674 * of throwing an exception, if passed a {@code toKey} greater than an earlier
675 * {@code toKey}.
676 */
677 @Override
678 public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) {
679 return subMap(fromKey, true, toKey, false);
680 }
681
682 ImmutableSortedMap<K, V> subMap(K fromKey, boolean fromInclusive, K toKey,
683 boolean toInclusive) {
684 checkNotNull(fromKey);
685 checkNotNull(toKey);
686 checkArgument(comparator.compare(fromKey, toKey) <= 0);
687 return tailMap(fromKey, fromInclusive).headMap(toKey, toInclusive);
688 }
689
690 /**
691 * This method returns a {@code ImmutableSortedMap}, consisting of the entries
692 * whose keys are greater than or equals to {@code fromKey}.
693 *
694 * <p>The {@link SortedMap#tailMap} documentation states that a submap of a
695 * submap throws an {@link IllegalArgumentException} if passed a {@code
696 * fromKey} less than an earlier {@code fromKey}. However, this method doesn't
697 * throw an exception in that situation, but instead keeps the original {@code
698 * fromKey}.
699 */
700 @Override
701 public ImmutableSortedMap<K, V> tailMap(K fromKey) {
702 return tailMap(fromKey, true);
703 }
704
705 ImmutableSortedMap<K, V> tailMap(K fromKey, boolean inclusive) {
706 int index;
707 if (inclusive) {
708 index = index(fromKey, ANY_PRESENT, NEXT_HIGHER);
709 } else {
710 index = index(fromKey, ANY_PRESENT, NEXT_LOWER) + 1;
711 }
712 return createSubmap(index, size());
713 }
714
715 private ImmutableList<K> keyList() {
716 return new TransformedImmutableList<Entry<K, V>, K>(entries) {
717 @Override
718 K transform(Entry<K, V> entry) {
719 return entry.getKey();
720 }
721 };
722 }
723
724 private int index(
725 Object key, KeyPresentBehavior presentBehavior, KeyAbsentBehavior absentBehavior) {
726 return SortedLists.binarySearch(
727 keyList(), checkNotNull(key), unsafeComparator(), presentBehavior, absentBehavior);
728 }
729
730 private ImmutableSortedMap<K, V> createSubmap(
731 int newFromIndex, int newToIndex) {
732 if (newFromIndex < newToIndex) {
733 return new ImmutableSortedMap<K, V>(
734 entries.subList(newFromIndex, newToIndex), comparator);
735 } else {
736 return emptyMap(comparator);
737 }
738 }
739
740 /**
741 * Serialized type for all ImmutableSortedMap instances. It captures the
742 * logical contents and they are reconstructed using public factory methods.
743 * This ensures that the implementation types remain as implementation
744 * details.
745 */
746 private static class SerializedForm extends ImmutableMap.SerializedForm {
747 private final Comparator<Object> comparator;
748 @SuppressWarnings("unchecked")
749 SerializedForm(ImmutableSortedMap<?, ?> sortedMap) {
750 super(sortedMap);
751 comparator = (Comparator<Object>) sortedMap.comparator();
752 }
753 @Override Object readResolve() {
754 Builder<Object, Object> builder = new Builder<Object, Object>(comparator);
755 return createMap(builder);
756 }
757 private static final long serialVersionUID = 0;
758 }
759
760 @Override Object writeReplace() {
761 return new SerializedForm(this);
762 }
763
764 // This class is never actually serialized directly, but we have to make the
765 // warning go away (and suppressing would suppress for all nested classes too)
766 private static final long serialVersionUID = 0;
767 }