1 /*
2 * Copyright (C) 2009 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 package com.google.common.collect;
18
19 import static com.google.common.base.Preconditions.checkArgument;
20 import static com.google.common.base.Preconditions.checkNotNull;
21 import static com.google.common.collect.CollectPreconditions.checkEntryNotNull;
22 import static com.google.common.collect.Maps.keyOrNull;
23
24 import com.google.common.annotations.Beta;
25 import com.google.common.annotations.GwtCompatible;
26 import com.google.errorprone.annotations.CanIgnoreReturnValue;
27 import com.google.errorprone.annotations.DoNotCall;
28 import java.util.AbstractMap;
29 import java.util.Arrays;
30 import java.util.Comparator;
31 import java.util.Map;
32 import java.util.NavigableMap;
33 import java.util.SortedMap;
34 import java.util.Spliterator;
35 import java.util.TreeMap;
36 import java.util.function.BiConsumer;
37 import java.util.function.BinaryOperator;
38 import java.util.function.Consumer;
39 import java.util.function.Function;
40 import java.util.stream.Collector;
41 import java.util.stream.Collectors;
42 import org.checkerframework.checker.nullness.qual.Nullable;
43
44 /**
45 * A {@link NavigableMap} whose contents will never change, with many other important properties
46 * detailed at {@link ImmutableCollection}.
47 *
48 * <p><b>Warning:</b> as with any sorted collection, you are strongly advised not to use a {@link
49 * Comparator} or {@link Comparable} type whose comparison behavior is <i>inconsistent with
50 * equals</i>. That is, {@code a.compareTo(b)} or {@code comparator.compare(a, b)} should equal zero
51 * <i>if and only if</i> {@code a.equals(b)}. If this advice is not followed, the resulting map will
52 * not correctly obey its specification.
53 *
54 * <p>See the Guava User Guide article on <a href=
55 * "https://github.com/google/guava/wiki/ImmutableCollectionsExplained"> immutable collections</a>.
56 *
57 * @author Jared Levy
58 * @author Louis Wasserman
59 * @since 2.0 (implements {@code NavigableMap} since 12.0)
60 */
61 @GwtCompatible(serializable = true, emulated = true)
62 public final class ImmutableSortedMap<K, V> extends ImmutableSortedMapFauxverideShim<K, V>
63 implements NavigableMap<K, V> {
64 /**
65 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose
66 * keys and values are the result of applying the provided mapping functions to the input
67 * elements. The generated map is sorted by the specified comparator.
68 *
69 * <p>If the mapped keys contain duplicates (according to the specified comparator), an {@code
70 * IllegalArgumentException} is thrown when the collection operation is performed. (This differs
71 * from the {@code Collector} returned by {@link Collectors#toMap(Function, Function)}, which
72 * throws an {@code IllegalStateException}.)
73 *
74 * @since 21.0
75 */
76 public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap(
77 Comparator<? super K> comparator,
78 Function<? super T, ? extends K> keyFunction,
79 Function<? super T, ? extends V> valueFunction) {
80 return CollectCollectors.toImmutableSortedMap(comparator, keyFunction, valueFunction);
81 }
82
83 /**
84 * Returns a {@link Collector} that accumulates elements into an {@code ImmutableSortedMap} whose
85 * keys and values are the result of applying the provided mapping functions to the input
86 * elements.
87 *
88 * <p>If the mapped keys contain duplicates (according to the comparator), the the values are
89 * merged using the specified merging function. Entries will appear in the encounter order of the
90 * first occurrence of the key.
91 *
92 * @since 21.0
93 */
94 public static <T, K, V> Collector<T, ?, ImmutableSortedMap<K, V>> toImmutableSortedMap(
95 Comparator<? super K> comparator,
96 Function<? super T, ? extends K> keyFunction,
97 Function<? super T, ? extends V> valueFunction,
98 BinaryOperator<V> mergeFunction) {
99 return CollectCollectors.toImmutableSortedMap(
100 comparator, keyFunction, valueFunction, mergeFunction);
101 }
102
103 /*
104 * TODO(kevinb): Confirm that ImmutableSortedMap is faster to construct and
105 * uses less memory than TreeMap; then say so in the class Javadoc.
106 */
107 private static final Comparator<Comparable> NATURAL_ORDER = Ordering.natural();
108
109 private static final ImmutableSortedMap<Comparable, Object> NATURAL_EMPTY_MAP =
110 new ImmutableSortedMap<>(
111 ImmutableSortedSet.emptySet(Ordering.natural()), ImmutableList.<Object>of());
112
113 static <K, V> ImmutableSortedMap<K, V> emptyMap(Comparator<? super K> comparator) {
114 if (Ordering.natural().equals(comparator)) {
115 return of();
116 } else {
117 return new ImmutableSortedMap<>(
118 ImmutableSortedSet.emptySet(comparator), ImmutableList.<V>of());
119 }
120 }
121
122 /**
123 * Returns the empty sorted map.
124 *
125 * <p><b>Performance note:</b> the instance returned is a singleton.
126 */
127 @SuppressWarnings("unchecked")
128 // unsafe, comparator() returns a comparator on the specified type
129 // TODO(kevinb): evaluate whether or not of().comparator() should return null
130 public static <K, V> ImmutableSortedMap<K, V> of() {
131 return (ImmutableSortedMap<K, V>) NATURAL_EMPTY_MAP;
132 }
133
134 /** Returns an immutable map containing a single entry. */
135 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(K k1, V v1) {
136 return of(Ordering.natural(), k1, v1);
137 }
138
139 /** Returns an immutable map containing a single entry. */
140 private static <K, V> ImmutableSortedMap<K, V> of(Comparator<? super K> comparator, K k1, V v1) {
141 return new ImmutableSortedMap<>(
142 new RegularImmutableSortedSet<K>(ImmutableList.of(k1), checkNotNull(comparator)),
143 ImmutableList.of(v1));
144 }
145
146 /**
147 * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
148 * their keys.
149 *
150 * @throws IllegalArgumentException if the two keys are equal according to their natural ordering
151 */
152 @SuppressWarnings("unchecked")
153 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
154 K k1, V v1, K k2, V v2) {
155 return ofEntries(entryOf(k1, v1), entryOf(k2, v2));
156 }
157
158 /**
159 * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
160 * their keys.
161 *
162 * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
163 */
164 @SuppressWarnings("unchecked")
165 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
166 K k1, V v1, K k2, V v2, K k3, V v3) {
167 return ofEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3));
168 }
169
170 /**
171 * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
172 * their keys.
173 *
174 * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
175 */
176 @SuppressWarnings("unchecked")
177 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
178 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4) {
179 return ofEntries(entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4));
180 }
181
182 /**
183 * Returns an immutable sorted map containing the given entries, sorted by the natural ordering of
184 * their keys.
185 *
186 * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
187 */
188 @SuppressWarnings("unchecked")
189 public static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> of(
190 K k1, V v1, K k2, V v2, K k3, V v3, K k4, V v4, K k5, V v5) {
191 return ofEntries(
192 entryOf(k1, v1), entryOf(k2, v2), entryOf(k3, v3), entryOf(k4, v4), entryOf(k5, v5));
193 }
194
195 private static <K extends Comparable<? super K>, V> ImmutableSortedMap<K, V> ofEntries(
196 Entry<K, V>... entries) {
197 return fromEntries(Ordering.natural(), false, entries, entries.length);
198 }
199
200 /**
201 * Returns an immutable map containing the same entries as {@code map}, sorted by the natural
202 * ordering of the keys.
203 *
204 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
205 * safe to do so. The exact circumstances under which a copy will or will not be performed are
206 * undocumented and subject to change.
207 *
208 * <p>This method is not type-safe, as it may be called on a map with keys that are not mutually
209 * comparable.
210 *
211 * @throws ClassCastException if the keys in {@code map} are not mutually comparable
212 * @throws NullPointerException if any key or value in {@code map} is null
213 * @throws IllegalArgumentException if any two keys are equal according to their natural ordering
214 */
215 public static <K, V> ImmutableSortedMap<K, V> copyOf(Map<? extends K, ? extends V> map) {
216 // Hack around K not being a subtype of Comparable.
217 // Unsafe, see ImmutableSortedSetFauxverideShim.
218 @SuppressWarnings("unchecked")
219 Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER;
220 return copyOfInternal(map, naturalOrder);
221 }
222
223 /**
224 * Returns an immutable map containing the same entries as {@code map}, with keys sorted by the
225 * provided comparator.
226 *
227 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
228 * safe to do so. The exact circumstances under which a copy will or will not be performed are
229 * undocumented and subject to change.
230 *
231 * @throws NullPointerException if any key or value in {@code map} is null
232 * @throws IllegalArgumentException if any two keys are equal according to the comparator
233 */
234 public static <K, V> ImmutableSortedMap<K, V> copyOf(
235 Map<? extends K, ? extends V> map, Comparator<? super K> comparator) {
236 return copyOfInternal(map, checkNotNull(comparator));
237 }
238
239 /**
240 * Returns an immutable map containing the given entries, with keys sorted by their natural
241 * ordering.
242 *
243 * <p>This method is not type-safe, as it may be called on a map with keys that are not mutually
244 * comparable.
245 *
246 * @throws NullPointerException if any key or value in {@code map} is null
247 * @throws IllegalArgumentException if any two keys are equal according to the comparator
248 * @since 19.0
249 */
250 @Beta
251 public static <K, V> ImmutableSortedMap<K, V> copyOf(
252 Iterable<? extends Entry<? extends K, ? extends V>> entries) {
253 // Hack around K not being a subtype of Comparable.
254 // Unsafe, see ImmutableSortedSetFauxverideShim.
255 @SuppressWarnings("unchecked")
256 Ordering<K> naturalOrder = (Ordering<K>) NATURAL_ORDER;
257 return copyOf(entries, naturalOrder);
258 }
259
260 /**
261 * Returns an immutable map containing the given entries, with keys sorted by the provided
262 * comparator.
263 *
264 * @throws NullPointerException if any key or value in {@code map} is null
265 * @throws IllegalArgumentException if any two keys are equal according to the comparator
266 * @since 19.0
267 */
268 @Beta
269 public static <K, V> ImmutableSortedMap<K, V> copyOf(
270 Iterable<? extends Entry<? extends K, ? extends V>> entries,
271 Comparator<? super K> comparator) {
272 return fromEntries(checkNotNull(comparator), false, entries);
273 }
274
275 /**
276 * Returns an immutable map containing the same entries as the provided sorted map, with the same
277 * ordering.
278 *
279 * <p>Despite the method name, this method attempts to avoid actually copying the data when it is
280 * safe to do so. The exact circumstances under which a copy will or will not be performed are
281 * undocumented and subject to change.
282 *
283 * @throws NullPointerException if any key or value in {@code map} is null
284 */
285 @SuppressWarnings("unchecked")
286 public static <K, V> ImmutableSortedMap<K, V> copyOfSorted(SortedMap<K, ? extends V> map) {
287 Comparator<? super K> comparator = map.comparator();
288 if (comparator == null) {
289 // If map has a null comparator, the keys should have a natural ordering,
290 // even though K doesn't explicitly implement Comparable.
291 comparator = (Comparator<? super K>) NATURAL_ORDER;
292 }
293 if (map instanceof ImmutableSortedMap) {
294 // TODO(kevinb): Prove that this cast is safe, even though
295 // Collections.unmodifiableSortedMap requires the same key type.
296 @SuppressWarnings("unchecked")
297 ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map;
298 if (!kvMap.isPartialView()) {
299 return kvMap;
300 }
301 }
302 return fromEntries(comparator, true, map.entrySet());
303 }
304
305 private static <K, V> ImmutableSortedMap<K, V> copyOfInternal(
306 Map<? extends K, ? extends V> map, Comparator<? super K> comparator) {
307 boolean sameComparator = false;
308 if (map instanceof SortedMap) {
309 SortedMap<?, ?> sortedMap = (SortedMap<?, ?>) map;
310 Comparator<?> comparator2 = sortedMap.comparator();
311 sameComparator =
312 (comparator2 == null) ? comparator == NATURAL_ORDER : comparator.equals(comparator2);
313 }
314
315 if (sameComparator && (map instanceof ImmutableSortedMap)) {
316 // TODO(kevinb): Prove that this cast is safe, even though
317 // Collections.unmodifiableSortedMap requires the same key type.
318 @SuppressWarnings("unchecked")
319 ImmutableSortedMap<K, V> kvMap = (ImmutableSortedMap<K, V>) map;
320 if (!kvMap.isPartialView()) {
321 return kvMap;
322 }
323 }
324 return fromEntries(comparator, sameComparator, map.entrySet());
325 }
326
327 /**
328 * Accepts a collection of possibly-null entries. If {@code sameComparator}, then it is assumed
329 * that they do not need to be sorted or checked for dupes.
330 */
331 private static <K, V> ImmutableSortedMap<K, V> fromEntries(
332 Comparator<? super K> comparator,
333 boolean sameComparator,
334 Iterable<? extends Entry<? extends K, ? extends V>> entries) {
335 // "adding" type params to an array of a raw type should be safe as
336 // long as no one can ever cast that same array instance back to a
337 // raw type.
338 @SuppressWarnings("unchecked")
339 Entry<K, V>[] entryArray = (Entry[]) Iterables.toArray(entries, EMPTY_ENTRY_ARRAY);
340 return fromEntries(comparator, sameComparator, entryArray, entryArray.length);
341 }
342
343 private static <K, V> ImmutableSortedMap<K, V> fromEntries(
344 final Comparator<? super K> comparator,
345 boolean sameComparator,
346 Entry<K, V>[] entryArray,
347 int size) {
348 switch (size) {
349 case 0:
350 return emptyMap(comparator);
351 case 1:
352 return ImmutableSortedMap.<K, V>of(
353 comparator, entryArray[0].getKey(), entryArray[0].getValue());
354 default:
355 Object[] keys = new Object[size];
356 Object[] values = new Object[size];
357 if (sameComparator) {
358 // Need to check for nulls, but don't need to sort or validate.
359 for (int i = 0; i < size; i++) {
360 Object key = entryArray[i].getKey();
361 Object value = entryArray[i].getValue();
362 checkEntryNotNull(key, value);
363 keys[i] = key;
364 values[i] = value;
365 }
366 } else {
367 // Need to sort and check for nulls and dupes.
368 // Inline the Comparator implementation rather than transforming with a Function
369 // to save code size.
370 Arrays.sort(
371 entryArray,
372 0,
373 size,
374 new Comparator<Entry<K, V>>() {
375 @Override
376 public int compare(Entry<K, V> e1, Entry<K, V> e2) {
377 return comparator.compare(e1.getKey(), e2.getKey());
378 }
379 });
380 K prevKey = entryArray[0].getKey();
381 keys[0] = prevKey;
382 values[0] = entryArray[0].getValue();
383 checkEntryNotNull(keys[0], values[0]);
384 for (int i = 1; i < size; i++) {
385 K key = entryArray[i].getKey();
386 V value = entryArray[i].getValue();
387 checkEntryNotNull(key, value);
388 keys[i] = key;
389 values[i] = value;
390 checkNoConflict(
391 comparator.compare(prevKey, key) != 0, "key", entryArray[i - 1], entryArray[i]);
392 prevKey = key;
393 }
394 }
395 return new ImmutableSortedMap<>(
396 new RegularImmutableSortedSet<K>(new RegularImmutableList<K>(keys), comparator),
397 new RegularImmutableList<V>(values));
398 }
399 }
400
401 /**
402 * Returns a builder that creates immutable sorted maps whose keys are ordered by their natural
403 * ordering. The sorted maps use {@link Ordering#natural()} as the comparator.
404 */
405 public static <K extends Comparable<?>, V> Builder<K, V> naturalOrder() {
406 return new Builder<>(Ordering.natural());
407 }
408
409 /**
410 * Returns a builder that creates immutable sorted maps with an explicit comparator. If the
411 * comparator has a more general type than the map's keys, such as creating a {@code
412 * SortedMap<Integer, String>} with a {@code Comparator<Number>}, use the {@link Builder}
413 * constructor instead.
414 *
415 * @throws NullPointerException if {@code comparator} is null
416 */
417 public static <K, V> Builder<K, V> orderedBy(Comparator<K> comparator) {
418 return new Builder<>(comparator);
419 }
420
421 /**
422 * Returns a builder that creates immutable sorted maps whose keys are ordered by the reverse of
423 * their natural ordering.
424 */
425 public static <K extends Comparable<?>, V> Builder<K, V> reverseOrder() {
426 return new Builder<>(Ordering.natural().reverse());
427 }
428
429 /**
430 * A builder for creating immutable sorted map instances, especially {@code public static final}
431 * maps ("constant maps"). Example:
432 *
433 * <pre>{@code
434 * static final ImmutableSortedMap<Integer, String> INT_TO_WORD =
435 * new ImmutableSortedMap.Builder<Integer, String>(Ordering.natural())
436 * .put(1, "one")
437 * .put(2, "two")
438 * .put(3, "three")
439 * .build();
440 * }</pre>
441 *
442 * <p>For <i>small</i> immutable sorted maps, the {@code ImmutableSortedMap.of()} methods are even
443 * more convenient.
444 *
445 * <p>Builder instances can be reused - it is safe to call {@link #build} multiple times to build
446 * multiple maps in series. Each map is a superset of the maps created before it.
447 *
448 * @since 2.0
449 */
450 public static class Builder<K, V> extends ImmutableMap.Builder<K, V> {
451 private final Comparator<? super K> comparator;
452
453 /**
454 * Creates a new builder. The returned builder is equivalent to the builder generated by {@link
455 * ImmutableSortedMap#orderedBy}.
456 */
457 @SuppressWarnings("unchecked")
458 public Builder(Comparator<? super K> comparator) {
459 this.comparator = checkNotNull(comparator);
460 }
461
462 /**
463 * Associates {@code key} with {@code value} in the built map. Duplicate keys, according to the
464 * comparator (which might be the keys' natural order), are not allowed, and will cause {@link
465 * #build} to fail.
466 */
467 @CanIgnoreReturnValue
468 @Override
469 public Builder<K, V> put(K key, V value) {
470 super.put(key, value);
471 return this;
472 }
473
474 /**
475 * Adds the given {@code entry} to the map, making it immutable if necessary. Duplicate keys,
476 * according to the comparator (which might be the keys' natural order), are not allowed, and
477 * will cause {@link #build} to fail.
478 *
479 * @since 11.0
480 */
481 @CanIgnoreReturnValue
482 @Override
483 public Builder<K, V> put(Entry<? extends K, ? extends V> entry) {
484 super.put(entry);
485 return this;
486 }
487
488 /**
489 * Associates all of the given map's keys and values in the built map. Duplicate keys, according
490 * to the comparator (which might be the keys' natural order), are not allowed, and will cause
491 * {@link #build} to fail.
492 *
493 * @throws NullPointerException if any key or value in {@code map} is null
494 */
495 @CanIgnoreReturnValue
496 @Override
497 public Builder<K, V> putAll(Map<? extends K, ? extends V> map) {
498 super.putAll(map);
499 return this;
500 }
501
502 /**
503 * Adds all the given entries to the built map. Duplicate keys, according to the comparator
504 * (which might be the keys' natural order), are not allowed, and will cause {@link #build} to
505 * fail.
506 *
507 * @throws NullPointerException if any key, value, or entry is null
508 * @since 19.0
509 */
510 @CanIgnoreReturnValue
511 @Beta
512 @Override
513 public Builder<K, V> putAll(Iterable<? extends Entry<? extends K, ? extends V>> entries) {
514 super.putAll(entries);
515 return this;
516 }
517
518 /**
519 * Throws an {@code UnsupportedOperationException}.
520 *
521 * @since 19.0
522 * @deprecated Unsupported by ImmutableSortedMap.Builder.
523 */
524 @CanIgnoreReturnValue
525 @Beta
526 @Override
527 @Deprecated
528 @DoNotCall("Always throws UnsupportedOperationException")
529 public final Builder<K, V> orderEntriesByValue(Comparator<? super V> valueComparator) {
530 throw new UnsupportedOperationException("Not available on ImmutableSortedMap.Builder");
531 }
532
533 @Override
534 Builder<K, V> combine(ImmutableMap.Builder<K, V> other) {
535 super.combine(other);
536 return this;
537 }
538
539 /**
540 * Returns a newly-created immutable sorted map.
541 *
542 * @throws IllegalArgumentException if any two keys are equal according to the comparator (which
543 * might be the keys' natural order)
544 */
545 @Override
546 public ImmutableSortedMap<K, V> build() {
547 switch (size) {
548 case 0:
549 return emptyMap(comparator);
550 case 1:
551 return of(comparator, entries[0].getKey(), entries[0].getValue());
552 default:
553 return fromEntries(comparator, false, entries, size);
554 }
555 }
556 }
557
558 private final transient RegularImmutableSortedSet<K> keySet;
559 private final transient ImmutableList<V> valueList;
560 private transient ImmutableSortedMap<K, V> descendingMap;
561
562 ImmutableSortedMap(RegularImmutableSortedSet<K> keySet, ImmutableList<V> valueList) {
563 this(keySet, valueList, null);
564 }
565
566 ImmutableSortedMap(
567 RegularImmutableSortedSet<K> keySet,
568 ImmutableList<V> valueList,
569 ImmutableSortedMap<K, V> descendingMap) {
570 this.keySet = keySet;
571 this.valueList = valueList;
572 this.descendingMap = descendingMap;
573 }
574
575 @Override
576 public int size() {
577 return valueList.size();
578 }
579
580 @Override
581 public void forEach(BiConsumer<? super K, ? super V> action) {
582 checkNotNull(action);
583 ImmutableList<K> keyList = keySet.asList();
584 for (int i = 0; i < size(); i++) {
585 action.accept(keyList.get(i), valueList.get(i));
586 }
587 }
588
589 @Override
590 public V get(@Nullable Object key) {
591 int index = keySet.indexOf(key);
592 return (index == -1) ? null : valueList.get(index);
593 }
594
595 @Override
596 boolean isPartialView() {
597 return keySet.isPartialView() || valueList.isPartialView();
598 }
599
600 /** Returns an immutable set of the mappings in this map, sorted by the key ordering. */
601 @Override
602 public ImmutableSet<Entry<K, V>> entrySet() {
603 return super.entrySet();
604 }
605
606 @Override
607 ImmutableSet<Entry<K, V>> createEntrySet() {
608 class EntrySet extends ImmutableMapEntrySet<K, V> {
609 @Override
610 public UnmodifiableIterator<Entry<K, V>> iterator() {
611 return asList().iterator();
612 }
613
614 @Override
615 public Spliterator<Entry<K, V>> spliterator() {
616 return asList().spliterator();
617 }
618
619 @Override
620 public void forEach(Consumer<? super Entry<K, V>> action) {
621 asList().forEach(action);
622 }
623
624 @Override
625 ImmutableList<Entry<K, V>> createAsList() {
626 return new ImmutableAsList<Entry<K, V>>() {
627 @Override
628 public Entry<K, V> get(int index) {
629 return new AbstractMap.SimpleImmutableEntry<>(
630 keySet.asList().get(index), valueList.get(index));
631 }
632
633 @Override
634 public Spliterator<Entry<K, V>> spliterator() {
635 return CollectSpliterators.indexed(
636 size(), ImmutableSet.SPLITERATOR_CHARACTERISTICS, this::get);
637 }
638
639 @Override
640 ImmutableCollection<Entry<K, V>> delegateCollection() {
641 return EntrySet.this;
642 }
643 };
644 }
645
646 @Override
647 ImmutableMap<K, V> map() {
648 return ImmutableSortedMap.this;
649 }
650 }
651 return isEmpty() ? ImmutableSet.<Entry<K, V>>of() : new EntrySet();
652 }
653
654 /** Returns an immutable sorted set of the keys in this map. */
655 @Override
656 public ImmutableSortedSet<K> keySet() {
657 return keySet;
658 }
659
660 @Override
661 ImmutableSet<K> createKeySet() {
662 throw new AssertionError("should never be called");
663 }
664
665 /**
666 * Returns an immutable collection of the values in this map, sorted by the ordering of the
667 * corresponding keys.
668 */
669 @Override
670 public ImmutableCollection<V> values() {
671 return valueList;
672 }
673
674 @Override
675 ImmutableCollection<V> createValues() {
676 throw new AssertionError("should never be called");
677 }
678
679 /**
680 * Returns the comparator that orders the keys, which is {@link Ordering#natural()} when the
681 * natural ordering of the keys is used. Note that its behavior is not consistent with {@link
682 * TreeMap#comparator()}, which returns {@code null} to indicate natural ordering.
683 */
684 @Override
685 public Comparator<? super K> comparator() {
686 return keySet().comparator();
687 }
688
689 @Override
690 public K firstKey() {
691 return keySet().first();
692 }
693
694 @Override
695 public K lastKey() {
696 return keySet().last();
697 }
698
699 private ImmutableSortedMap<K, V> getSubMap(int fromIndex, int toIndex) {
700 if (fromIndex == 0 && toIndex == size()) {
701 return this;
702 } else if (fromIndex == toIndex) {
703 return emptyMap(comparator());
704 } else {
705 return new ImmutableSortedMap<>(
706 keySet.getSubSet(fromIndex, toIndex), valueList.subList(fromIndex, toIndex));
707 }
708 }
709
710 /**
711 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are less
712 * than {@code toKey}.
713 *
714 * <p>The {@link SortedMap#headMap} documentation states that a submap of a submap throws an
715 * {@link IllegalArgumentException} if passed a {@code toKey} greater than an earlier {@code
716 * toKey}. However, this method doesn't throw an exception in that situation, but instead keeps
717 * the original {@code toKey}.
718 */
719 @Override
720 public ImmutableSortedMap<K, V> headMap(K toKey) {
721 return headMap(toKey, false);
722 }
723
724 /**
725 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are less
726 * than (or equal to, if {@code inclusive}) {@code toKey}.
727 *
728 * <p>The {@link SortedMap#headMap} documentation states that a submap of a submap throws an
729 * {@link IllegalArgumentException} if passed a {@code toKey} greater than an earlier {@code
730 * toKey}. However, this method doesn't throw an exception in that situation, but instead keeps
731 * the original {@code toKey}.
732 *
733 * @since 12.0
734 */
735 @Override
736 public ImmutableSortedMap<K, V> headMap(K toKey, boolean inclusive) {
737 return getSubMap(0, keySet.headIndex(checkNotNull(toKey), inclusive));
738 }
739
740 /**
741 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys ranges
742 * from {@code fromKey}, inclusive, to {@code toKey}, exclusive.
743 *
744 * <p>The {@link SortedMap#subMap} documentation states that a submap of a submap throws an {@link
745 * IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code fromKey}.
746 * However, this method doesn't throw an exception in that situation, but instead keeps the
747 * original {@code fromKey}. Similarly, this method keeps the original {@code toKey}, instead of
748 * throwing an exception, if passed a {@code toKey} greater than an earlier {@code toKey}.
749 */
750 @Override
751 public ImmutableSortedMap<K, V> subMap(K fromKey, K toKey) {
752 return subMap(fromKey, true, toKey, false);
753 }
754
755 /**
756 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys ranges
757 * from {@code fromKey} to {@code toKey}, inclusive or exclusive as indicated by the boolean
758 * flags.
759 *
760 * <p>The {@link SortedMap#subMap} documentation states that a submap of a submap throws an {@link
761 * IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code fromKey}.
762 * However, this method doesn't throw an exception in that situation, but instead keeps the
763 * original {@code fromKey}. Similarly, this method keeps the original {@code toKey}, instead of
764 * throwing an exception, if passed a {@code toKey} greater than an earlier {@code toKey}.
765 *
766 * @since 12.0
767 */
768 @Override
769 public ImmutableSortedMap<K, V> subMap(
770 K fromKey, boolean fromInclusive, K toKey, boolean toInclusive) {
771 checkNotNull(fromKey);
772 checkNotNull(toKey);
773 checkArgument(
774 comparator().compare(fromKey, toKey) <= 0,
775 "expected fromKey <= toKey but %s > %s",
776 fromKey,
777 toKey);
778 return headMap(toKey, toInclusive).tailMap(fromKey, fromInclusive);
779 }
780
781 /**
782 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are
783 * greater than or equals to {@code fromKey}.
784 *
785 * <p>The {@link SortedMap#tailMap} documentation states that a submap of a submap throws an
786 * {@link IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code
787 * fromKey}. However, this method doesn't throw an exception in that situation, but instead keeps
788 * the original {@code fromKey}.
789 */
790 @Override
791 public ImmutableSortedMap<K, V> tailMap(K fromKey) {
792 return tailMap(fromKey, true);
793 }
794
795 /**
796 * This method returns a {@code ImmutableSortedMap}, consisting of the entries whose keys are
797 * greater than (or equal to, if {@code inclusive}) {@code fromKey}.
798 *
799 * <p>The {@link SortedMap#tailMap} documentation states that a submap of a submap throws an
800 * {@link IllegalArgumentException} if passed a {@code fromKey} less than an earlier {@code
801 * fromKey}. However, this method doesn't throw an exception in that situation, but instead keeps
802 * the original {@code fromKey}.
803 *
804 * @since 12.0
805 */
806 @Override
807 public ImmutableSortedMap<K, V> tailMap(K fromKey, boolean inclusive) {
808 return getSubMap(keySet.tailIndex(checkNotNull(fromKey), inclusive), size());
809 }
810
811 @Override
812 public Entry<K, V> lowerEntry(K key) {
813 return headMap(key, false).lastEntry();
814 }
815
816 @Override
817 public K lowerKey(K key) {
818 return keyOrNull(lowerEntry(key));
819 }
820
821 @Override
822 public Entry<K, V> floorEntry(K key) {
823 return headMap(key, true).lastEntry();
824 }
825
826 @Override
827 public K floorKey(K key) {
828 return keyOrNull(floorEntry(key));
829 }
830
831 @Override
832 public Entry<K, V> ceilingEntry(K key) {
833 return tailMap(key, true).firstEntry();
834 }
835
836 @Override
837 public K ceilingKey(K key) {
838 return keyOrNull(ceilingEntry(key));
839 }
840
841 @Override
842 public Entry<K, V> higherEntry(K key) {
843 return tailMap(key, false).firstEntry();
844 }
845
846 @Override
847 public K higherKey(K key) {
848 return keyOrNull(higherEntry(key));
849 }
850
851 @Override
852 public Entry<K, V> firstEntry() {
853 return isEmpty() ? null : entrySet().asList().get(0);
854 }
855
856 @Override
857 public Entry<K, V> lastEntry() {
858 return isEmpty() ? null : entrySet().asList().get(size() - 1);
859 }
860
861 /**
862 * Guaranteed to throw an exception and leave the map unmodified.
863 *
864 * @throws UnsupportedOperationException always
865 * @deprecated Unsupported operation.
866 */
867 @CanIgnoreReturnValue
868 @Deprecated
869 @Override
870 @DoNotCall("Always throws UnsupportedOperationException")
871 public final Entry<K, V> pollFirstEntry() {
872 throw new UnsupportedOperationException();
873 }
874
875 /**
876 * Guaranteed to throw an exception and leave the map unmodified.
877 *
878 * @throws UnsupportedOperationException always
879 * @deprecated Unsupported operation.
880 */
881 @CanIgnoreReturnValue
882 @Deprecated
883 @Override
884 @DoNotCall("Always throws UnsupportedOperationException")
885 public final Entry<K, V> pollLastEntry() {
886 throw new UnsupportedOperationException();
887 }
888
889 @Override
890 public ImmutableSortedMap<K, V> descendingMap() {
891 // TODO(kevinb): the descendingMap is never actually cached at all. Either it should be or the
892 // code below simplified.
893 ImmutableSortedMap<K, V> result = descendingMap;
894 if (result == null) {
895 if (isEmpty()) {
896 return result = emptyMap(Ordering.from(comparator()).reverse());
897 } else {
898 return result =
899 new ImmutableSortedMap<>(
900 (RegularImmutableSortedSet<K>) keySet.descendingSet(), valueList.reverse(), this);
901 }
902 }
903 return result;
904 }
905
906 @Override
907 public ImmutableSortedSet<K> navigableKeySet() {
908 return keySet;
909 }
910
911 @Override
912 public ImmutableSortedSet<K> descendingKeySet() {
913 return keySet.descendingSet();
914 }
915
916 /**
917 * Serialized type for all ImmutableSortedMap instances. It captures the logical contents and they
918 * are reconstructed using public factory methods. This ensures that the implementation types
919 * remain as implementation details.
920 */
921 private static class SerializedForm<K, V> extends ImmutableMap.SerializedForm<K, V> {
922 private final Comparator<? super K> comparator;
923
924 SerializedForm(ImmutableSortedMap<K, V> sortedMap) {
925 super(sortedMap);
926 comparator = sortedMap.comparator();
927 }
928
929 @Override
930 Builder<K, V> makeBuilder(int size) {
931 return new Builder<>(comparator);
932 }
933
934 private static final long serialVersionUID = 0;
935 }
936
937 @Override
938 Object writeReplace() {
939 return new SerializedForm<>(this);
940 }
941
942 // This class is never actually serialized directly, but we have to make the
943 // warning go away (and suppressing would suppress for all nested classes too)
944 private static final long serialVersionUID = 0;
945 }