1 /*
2 * Copyright (c) 1997, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 import java.io.Serializable;
29 import java.util.function.BiConsumer;
30 import java.util.function.BiFunction;
31 import java.util.function.Consumer;
32 import java.util.function.Function;
33
34 /**
35 * A Red-Black tree based {@link NavigableMap} implementation.
36 * The map is sorted according to the {@linkplain Comparable natural
37 * ordering} of its keys, or by a {@link Comparator} provided at map
38 * creation time, depending on which constructor is used.
39 *
40 * <p>This implementation provides guaranteed log(n) time cost for the
41 * {@code containsKey}, {@code get}, {@code put} and {@code remove}
42 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
43 * Rivest's <em>Introduction to Algorithms</em>.
44 *
45 * <p>Note that the ordering maintained by a tree map, like any sorted map, and
46 * whether or not an explicit comparator is provided, must be <em>consistent
47 * with {@code equals}</em> if this sorted map is to correctly implement the
48 * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
49 * precise definition of <em>consistent with equals</em>.) This is so because
50 * the {@code Map} interface is defined in terms of the {@code equals}
51 * operation, but a sorted map performs all key comparisons using its {@code
52 * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
53 * this method are, from the standpoint of the sorted map, equal. The behavior
54 * of a sorted map <em>is</em> well-defined even if its ordering is
55 * inconsistent with {@code equals}; it just fails to obey the general contract
56 * of the {@code Map} interface.
57 *
58 * <p><strong>Note that this implementation is not synchronized.</strong>
59 * If multiple threads access a map concurrently, and at least one of the
60 * threads modifies the map structurally, it <em>must</em> be synchronized
61 * externally. (A structural modification is any operation that adds or
62 * deletes one or more mappings; merely changing the value associated
63 * with an existing key is not a structural modification.) This is
64 * typically accomplished by synchronizing on some object that naturally
65 * encapsulates the map.
66 * If no such object exists, the map should be "wrapped" using the
67 * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
68 * method. This is best done at creation time, to prevent accidental
69 * unsynchronized access to the map: <pre>
70 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
71 *
72 * <p>The iterators returned by the {@code iterator} method of the collections
73 * returned by all of this class's "collection view methods" are
74 * <em>fail-fast</em>: if the map is structurally modified at any time after
75 * the iterator is created, in any way except through the iterator's own
76 * {@code remove} method, the iterator will throw a {@link
77 * ConcurrentModificationException}. Thus, in the face of concurrent
78 * modification, the iterator fails quickly and cleanly, rather than risking
79 * arbitrary, non-deterministic behavior at an undetermined time in the future.
80 *
81 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
82 * as it is, generally speaking, impossible to make any hard guarantees in the
83 * presence of unsynchronized concurrent modification. Fail-fast iterators
84 * throw {@code ConcurrentModificationException} on a best-effort basis.
85 * Therefore, it would be wrong to write a program that depended on this
86 * exception for its correctness: <em>the fail-fast behavior of iterators
87 * should be used only to detect bugs.</em>
88 *
89 * <p>All {@code Map.Entry} pairs returned by methods in this class
90 * and its views represent snapshots of mappings at the time they were
91 * produced. They do <strong>not</strong> support the {@code Entry.setValue}
92 * method. (Note however that it is possible to change mappings in the
93 * associated map using {@code put}.)
94 *
95 * <p>This class is a member of the
96 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
97 * Java Collections Framework</a>.
98 *
99 * @param <K> the type of keys maintained by this map
100 * @param <V> the type of mapped values
101 *
102 * @author Josh Bloch and Doug Lea
103 * @see Map
104 * @see HashMap
105 * @see Hashtable
106 * @see Comparable
107 * @see Comparator
108 * @see Collection
109 * @since 1.2
110 */
111
112 public class TreeMap<K,V>
113 extends AbstractMap<K,V>
114 implements NavigableMap<K,V>, Cloneable, java.io.Serializable
115 {
116 /**
117 * The comparator used to maintain order in this tree map, or
118 * null if it uses the natural ordering of its keys.
119 *
120 * @serial
121 */
122 private final Comparator<? super K> comparator;
123
124 private transient Entry<K,V> root;
125
126 /**
127 * The number of entries in the tree
128 */
129 private transient int size = 0;
130
131 /**
132 * The number of structural modifications to the tree.
133 */
134 private transient int modCount = 0;
135
136 /**
137 * Constructs a new, empty tree map, using the natural ordering of its
138 * keys. All keys inserted into the map must implement the {@link
139 * Comparable} interface. Furthermore, all such keys must be
140 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
141 * a {@code ClassCastException} for any keys {@code k1} and
142 * {@code k2} in the map. If the user attempts to put a key into the
143 * map that violates this constraint (for example, the user attempts to
144 * put a string key into a map whose keys are integers), the
145 * {@code put(Object key, Object value)} call will throw a
146 * {@code ClassCastException}.
147 */
148 public TreeMap() {
149 comparator = null;
150 }
151
152 /**
153 * Constructs a new, empty tree map, ordered according to the given
154 * comparator. All keys inserted into the map must be <em>mutually
155 * comparable</em> by the given comparator: {@code comparator.compare(k1,
156 * k2)} must not throw a {@code ClassCastException} for any keys
157 * {@code k1} and {@code k2} in the map. If the user attempts to put
158 * a key into the map that violates this constraint, the {@code put(Object
159 * key, Object value)} call will throw a
160 * {@code ClassCastException}.
161 *
162 * @param comparator the comparator that will be used to order this map.
163 * If {@code null}, the {@linkplain Comparable natural
164 * ordering} of the keys will be used.
165 */
166 public TreeMap(Comparator<? super K> comparator) {
167 this.comparator = comparator;
168 }
169
170 /**
171 * Constructs a new tree map containing the same mappings as the given
172 * map, ordered according to the <em>natural ordering</em> of its keys.
173 * All keys inserted into the new map must implement the {@link
174 * Comparable} interface. Furthermore, all such keys must be
175 * <em>mutually comparable</em>: {@code k1.compareTo(k2)} must not throw
176 * a {@code ClassCastException} for any keys {@code k1} and
177 * {@code k2} in the map. This method runs in n*log(n) time.
178 *
179 * @param m the map whose mappings are to be placed in this map
180 * @throws ClassCastException if the keys in m are not {@link Comparable},
181 * or are not mutually comparable
182 * @throws NullPointerException if the specified map is null
183 */
184 public TreeMap(Map<? extends K, ? extends V> m) {
185 comparator = null;
186 putAll(m);
187 }
188
189 /**
190 * Constructs a new tree map containing the same mappings and
191 * using the same ordering as the specified sorted map. This
192 * method runs in linear time.
193 *
194 * @param m the sorted map whose mappings are to be placed in this map,
195 * and whose comparator is to be used to sort this map
196 * @throws NullPointerException if the specified map is null
197 */
198 public TreeMap(SortedMap<K, ? extends V> m) {
199 comparator = m.comparator();
200 try {
201 buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
202 } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
203 }
204 }
205
206
207 // Query Operations
208
209 /**
210 * Returns the number of key-value mappings in this map.
211 *
212 * @return the number of key-value mappings in this map
213 */
214 public int size() {
215 return size;
216 }
217
218 /**
219 * Returns {@code true} if this map contains a mapping for the specified
220 * key.
221 *
222 * @param key key whose presence in this map is to be tested
223 * @return {@code true} if this map contains a mapping for the
224 * specified key
225 * @throws ClassCastException if the specified key cannot be compared
226 * with the keys currently in the map
227 * @throws NullPointerException if the specified key is null
228 * and this map uses natural ordering, or its comparator
229 * does not permit null keys
230 */
231 public boolean containsKey(Object key) {
232 return getEntry(key) != null;
233 }
234
235 /**
236 * Returns {@code true} if this map maps one or more keys to the
237 * specified value. More formally, returns {@code true} if and only if
238 * this map contains at least one mapping to a value {@code v} such
239 * that {@code (value==null ? v==null : value.equals(v))}. This
240 * operation will probably require time linear in the map size for
241 * most implementations.
242 *
243 * @param value value whose presence in this map is to be tested
244 * @return {@code true} if a mapping to {@code value} exists;
245 * {@code false} otherwise
246 * @since 1.2
247 */
248 public boolean containsValue(Object value) {
249 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))
250 if (valEquals(value, e.value))
251 return true;
252 return false;
253 }
254
255 /**
256 * Returns the value to which the specified key is mapped,
257 * or {@code null} if this map contains no mapping for the key.
258 *
259 * <p>More formally, if this map contains a mapping from a key
260 * {@code k} to a value {@code v} such that {@code key} compares
261 * equal to {@code k} according to the map's ordering, then this
262 * method returns {@code v}; otherwise it returns {@code null}.
263 * (There can be at most one such mapping.)
264 *
265 * <p>A return value of {@code null} does not <em>necessarily</em>
266 * indicate that the map contains no mapping for the key; it's also
267 * possible that the map explicitly maps the key to {@code null}.
268 * The {@link #containsKey containsKey} operation may be used to
269 * distinguish these two cases.
270 *
271 * @throws ClassCastException if the specified key cannot be compared
272 * with the keys currently in the map
273 * @throws NullPointerException if the specified key is null
274 * and this map uses natural ordering, or its comparator
275 * does not permit null keys
276 */
277 public V get(Object key) {
278 Entry<K,V> p = getEntry(key);
279 return (p==null ? null : p.value);
280 }
281
282 public Comparator<? super K> comparator() {
283 return comparator;
284 }
285
286 /**
287 * @throws NoSuchElementException {@inheritDoc}
288 */
289 public K firstKey() {
290 return key(getFirstEntry());
291 }
292
293 /**
294 * @throws NoSuchElementException {@inheritDoc}
295 */
296 public K lastKey() {
297 return key(getLastEntry());
298 }
299
300 /**
301 * Copies all of the mappings from the specified map to this map.
302 * These mappings replace any mappings that this map had for any
303 * of the keys currently in the specified map.
304 *
305 * @param map mappings to be stored in this map
306 * @throws ClassCastException if the class of a key or value in
307 * the specified map prevents it from being stored in this map
308 * @throws NullPointerException if the specified map is null or
309 * the specified map contains a null key and this map does not
310 * permit null keys
311 */
312 public void putAll(Map<? extends K, ? extends V> map) {
313 int mapSize = map.size();
314 if (size==0 && mapSize!=0 && map instanceof SortedMap) {
315 Comparator<?> c = ((SortedMap<?,?>)map).comparator();
316 if (c == comparator || (c != null && c.equals(comparator))) {
317 ++modCount;
318 try {
319 buildFromSorted(mapSize, map.entrySet().iterator(),
320 null, null);
321 } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
322 }
323 return;
324 }
325 }
326 super.putAll(map);
327 }
328
329 /**
330 * Returns this map's entry for the given key, or {@code null} if the map
331 * does not contain an entry for the key.
332 *
333 * @return this map's entry for the given key, or {@code null} if the map
334 * does not contain an entry for the key
335 * @throws ClassCastException if the specified key cannot be compared
336 * with the keys currently in the map
337 * @throws NullPointerException if the specified key is null
338 * and this map uses natural ordering, or its comparator
339 * does not permit null keys
340 */
341 final Entry<K,V> getEntry(Object key) {
342 // Offload comparator-based version for sake of performance
343 if (comparator != null)
344 return getEntryUsingComparator(key);
345 if (key == null)
346 throw new NullPointerException();
347 @SuppressWarnings("unchecked")
348 Comparable<? super K> k = (Comparable<? super K>) key;
349 Entry<K,V> p = root;
350 while (p != null) {
351 int cmp = k.compareTo(p.key);
352 if (cmp < 0)
353 p = p.left;
354 else if (cmp > 0)
355 p = p.right;
356 else
357 return p;
358 }
359 return null;
360 }
361
362 /**
363 * Version of getEntry using comparator. Split off from getEntry
364 * for performance. (This is not worth doing for most methods,
365 * that are less dependent on comparator performance, but is
366 * worthwhile here.)
367 */
368 final Entry<K,V> getEntryUsingComparator(Object key) {
369 @SuppressWarnings("unchecked")
370 K k = (K) key;
371 Comparator<? super K> cpr = comparator;
372 if (cpr != null) {
373 Entry<K,V> p = root;
374 while (p != null) {
375 int cmp = cpr.compare(k, p.key);
376 if (cmp < 0)
377 p = p.left;
378 else if (cmp > 0)
379 p = p.right;
380 else
381 return p;
382 }
383 }
384 return null;
385 }
386
387 /**
388 * Gets the entry corresponding to the specified key; if no such entry
389 * exists, returns the entry for the least key greater than the specified
390 * key; if no such entry exists (i.e., the greatest key in the Tree is less
391 * than the specified key), returns {@code null}.
392 */
393 final Entry<K,V> getCeilingEntry(K key) {
394 Entry<K,V> p = root;
395 while (p != null) {
396 int cmp = compare(key, p.key);
397 if (cmp < 0) {
398 if (p.left != null)
399 p = p.left;
400 else
401 return p;
402 } else if (cmp > 0) {
403 if (p.right != null) {
404 p = p.right;
405 } else {
406 Entry<K,V> parent = p.parent;
407 Entry<K,V> ch = p;
408 while (parent != null && ch == parent.right) {
409 ch = parent;
410 parent = parent.parent;
411 }
412 return parent;
413 }
414 } else
415 return p;
416 }
417 return null;
418 }
419
420 /**
421 * Gets the entry corresponding to the specified key; if no such entry
422 * exists, returns the entry for the greatest key less than the specified
423 * key; if no such entry exists, returns {@code null}.
424 */
425 final Entry<K,V> getFloorEntry(K key) {
426 Entry<K,V> p = root;
427 while (p != null) {
428 int cmp = compare(key, p.key);
429 if (cmp > 0) {
430 if (p.right != null)
431 p = p.right;
432 else
433 return p;
434 } else if (cmp < 0) {
435 if (p.left != null) {
436 p = p.left;
437 } else {
438 Entry<K,V> parent = p.parent;
439 Entry<K,V> ch = p;
440 while (parent != null && ch == parent.left) {
441 ch = parent;
442 parent = parent.parent;
443 }
444 return parent;
445 }
446 } else
447 return p;
448
449 }
450 return null;
451 }
452
453 /**
454 * Gets the entry for the least key greater than the specified
455 * key; if no such entry exists, returns the entry for the least
456 * key greater than the specified key; if no such entry exists
457 * returns {@code null}.
458 */
459 final Entry<K,V> getHigherEntry(K key) {
460 Entry<K,V> p = root;
461 while (p != null) {
462 int cmp = compare(key, p.key);
463 if (cmp < 0) {
464 if (p.left != null)
465 p = p.left;
466 else
467 return p;
468 } else {
469 if (p.right != null) {
470 p = p.right;
471 } else {
472 Entry<K,V> parent = p.parent;
473 Entry<K,V> ch = p;
474 while (parent != null && ch == parent.right) {
475 ch = parent;
476 parent = parent.parent;
477 }
478 return parent;
479 }
480 }
481 }
482 return null;
483 }
484
485 /**
486 * Returns the entry for the greatest key less than the specified key; if
487 * no such entry exists (i.e., the least key in the Tree is greater than
488 * the specified key), returns {@code null}.
489 */
490 final Entry<K,V> getLowerEntry(K key) {
491 Entry<K,V> p = root;
492 while (p != null) {
493 int cmp = compare(key, p.key);
494 if (cmp > 0) {
495 if (p.right != null)
496 p = p.right;
497 else
498 return p;
499 } else {
500 if (p.left != null) {
501 p = p.left;
502 } else {
503 Entry<K,V> parent = p.parent;
504 Entry<K,V> ch = p;
505 while (parent != null && ch == parent.left) {
506 ch = parent;
507 parent = parent.parent;
508 }
509 return parent;
510 }
511 }
512 }
513 return null;
514 }
515
516 /**
517 * Associates the specified value with the specified key in this map.
518 * If the map previously contained a mapping for the key, the old
519 * value is replaced.
520 *
521 * @param key key with which the specified value is to be associated
522 * @param value value to be associated with the specified key
523 *
524 * @return the previous value associated with {@code key}, or
525 * {@code null} if there was no mapping for {@code key}.
526 * (A {@code null} return can also indicate that the map
527 * previously associated {@code null} with {@code key}.)
528 * @throws ClassCastException if the specified key cannot be compared
529 * with the keys currently in the map
530 * @throws NullPointerException if the specified key is null
531 * and this map uses natural ordering, or its comparator
532 * does not permit null keys
533 */
534 public V put(K key, V value) {
535 return put(key, value, true);
536 }
537
538 private void addEntry(K key, V value, int cmp, Entry<K, V> parent) {
539 Entry<K, V> e = new Entry<>(key, value, parent);
540 if (cmp < 0)
541 parent.left = e;
542 else
543 parent.right = e;
544 fixAfterInsertion(e);
545 size++;
546 modCount++;
547 }
548
549 private void addEntryToEmptyMap(K key, V value) {
550 compare(key, key); // type (and possibly null) check
551 root = new Entry<>(key, value, null);
552 size = 1;
553 modCount++;
554 }
555
556 private V put(K key, V value, boolean replaceOld) {
557 Entry<K, V> t = root;
558 if (t == null) {
559 addEntryToEmptyMap(key, value);
560 return null;
561 }
562 int cmp;
563 Entry<K, V> parent;
564 // split comparator and comparable paths
565 Comparator<? super K> cpr = comparator;
566 if (cpr != null) {
567 do {
568 parent = t;
569 cmp = cpr.compare(key, t.key);
570 if (cmp < 0)
571 t = t.left;
572 else if (cmp > 0)
573 t = t.right;
574 else {
575 V oldValue = t.value;
576 if (replaceOld || oldValue == null) {
577 t.value = value;
578 }
579 return oldValue;
580 }
581 } while (t != null);
582 } else {
583 if (key == null)
584 throw new NullPointerException();
585 @SuppressWarnings("unchecked")
586 Comparable<? super K> k = (Comparable<? super K>) key;
587 do {
588 parent = t;
589 cmp = k.compareTo(t.key);
590 if (cmp < 0)
591 t = t.left;
592 else if (cmp > 0)
593 t = t.right;
594 else {
595 V oldValue = t.value;
596 if (replaceOld || oldValue == null) {
597 t.value = value;
598 }
599 return oldValue;
600 }
601 } while (t != null);
602 }
603 addEntry(key, value, cmp, parent);
604 return null;
605 }
606
607 @Override
608 public V putIfAbsent(K key, V value) {
609 return put(key, value, false);
610 }
611
612 /**
613 * {@inheritDoc}
614 *
615 * <p>This method will, on a best-effort basis, throw a
616 * {@link ConcurrentModificationException} if it is detected that the
617 * remapping function modifies this map during computation.
618 *
619 * @throws ConcurrentModificationException if it is detected that the
620 * remapping function modified this map
621 */
622 @Override
623 public V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
624 Objects.requireNonNull(mappingFunction);
625 V newValue;
626 Entry<K, V> t = root;
627 if (t == null) {
628 newValue = getNewValueAndCheckModification(key, mappingFunction);
629 if (newValue != null) {
630 addEntryToEmptyMap(key, newValue);
631 return newValue;
632 } else {
633 return null;
634 }
635 }
636 int cmp;
637 Entry<K, V> parent;
638 // split comparator and comparable paths
639 Comparator<? super K> cpr = comparator;
640 if (cpr != null) {
641 do {
642 parent = t;
643 cmp = cpr.compare(key, t.key);
644 if (cmp < 0)
645 t = t.left;
646 else if (cmp > 0)
647 t = t.right;
648 else
649 return t.value;
650 } while (t != null);
651 } else {
652 if (key == null)
653 throw new NullPointerException();
654 @SuppressWarnings("unchecked")
655 Comparable<? super K> k = (Comparable<? super K>) key;
656 do {
657 parent = t;
658 cmp = k.compareTo(t.key);
659 if (cmp < 0)
660 t = t.left;
661 else if (cmp > 0)
662 t = t.right;
663 else
664 return t.value;
665 } while (t != null);
666 }
667 newValue = getNewValueAndCheckModification(key, mappingFunction);
668 if (newValue != null) {
669 addEntry(key, newValue, cmp, parent);
670 return newValue;
671 }
672 return null;
673 }
674
675 private V getNewValueAndCheckModification(K key, Function<? super K, ? extends V> mappingFunction) {
676 V newValue;
677 int mc = modCount;
678 newValue = mappingFunction.apply(key);
679 if (mc != modCount) {
680 throw new ConcurrentModificationException();
681 }
682 return newValue;
683 }
684
685 /**
686 * {@inheritDoc}
687 *
688 * <p>This method will, on a best-effort basis, throw a
689 * {@link ConcurrentModificationException} if it is detected that the
690 * remapping function modifies this map during computation.
691 *
692 * @throws ConcurrentModificationException if it is detected that the
693 * remapping function modified this map
694 */
695 @Override
696 public V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
697 Objects.requireNonNull(remappingFunction);
698 Entry<K, V> oldEntry = getEntry(key);
699 if (oldEntry != null && oldEntry.value != null) {
700 return remapValue(oldEntry, key, remappingFunction);
701 } else {
702 return null;
703 }
704 }
705
706 private V remapValue(Entry<K, V> t, K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
707 V newValue = getNewValueAndCheckModification(key, t.value, remappingFunction);
708 if (newValue == null) {
709 deleteEntry(t);
710 return null;
711 } else {
712 // replace old mapping
713 t.value = newValue;
714 return newValue;
715 }
716 }
717
718 private V getNewValueAndCheckModification(K key, V oldValue, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
719 int mc = modCount;
720 V newValue = remappingFunction.apply(key, oldValue);
721 if (mc != modCount) {
722 throw new ConcurrentModificationException();
723 }
724 return newValue;
725 }
726
727 /**
728 * {@inheritDoc}
729 *
730 * <p>This method will, on a best-effort basis, throw a
731 * {@link ConcurrentModificationException} if it is detected that the
732 * remapping function modifies this map during computation.
733 *
734 * @throws ConcurrentModificationException if it is detected that the
735 * remapping function modified this map
736 */
737 @Override
738 public V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
739 Objects.requireNonNull(remappingFunction);
740 V newValue;
741 Entry<K, V> t = root;
742 if (t == null) {
743 newValue = getNewValueAndCheckModification(key, null, remappingFunction);
744 if (newValue != null) {
745 addEntryToEmptyMap(key, newValue);
746 return newValue;
747 } else {
748 return null;
749 }
750 }
751 int cmp;
752 Entry<K, V> parent;
753 // split comparator and comparable paths
754 Comparator<? super K> cpr = comparator;
755 if (cpr != null) {
756 do {
757 parent = t;
758 cmp = cpr.compare(key, t.key);
759 if (cmp < 0)
760 t = t.left;
761 else if (cmp > 0)
762 t = t.right;
763 else
764 return remapValue(t, key, remappingFunction);
765 } while (t != null);
766 } else {
767 if (key == null)
768 throw new NullPointerException();
769 @SuppressWarnings("unchecked")
770 Comparable<? super K> k = (Comparable<? super K>) key;
771 do {
772 parent = t;
773 cmp = k.compareTo(t.key);
774 if (cmp < 0)
775 t = t.left;
776 else if (cmp > 0)
777 t = t.right;
778 else
779 return remapValue(t, key, remappingFunction);
780 } while (t != null);
781 }
782 newValue = getNewValueAndCheckModification(key, null, remappingFunction);
783 if (newValue != null) {
784 addEntry(key, newValue, cmp, parent);
785 return newValue;
786 }
787 return null;
788 }
789
790 /**
791 * {@inheritDoc}
792 *
793 * <p>This method will, on a best-effort basis, throw a
794 * {@link ConcurrentModificationException} if it is detected that the
795 * remapping function modifies this map during computation.
796 *
797 * @throws ConcurrentModificationException if it is detected that the
798 * remapping function modified this map
799 */
800 @Override
801 public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
802 Objects.requireNonNull(remappingFunction);
803 Objects.requireNonNull(value);
804 Entry<K, V> t = root;
805 if (t == null) {
806 addEntryToEmptyMap(key, value);
807 return value;
808 }
809 int cmp;
810 Entry<K, V> parent;
811 // split comparator and comparable paths
812 Comparator<? super K> cpr = comparator;
813 if (cpr != null) {
814 do {
815 parent = t;
816 cmp = cpr.compare(key, t.key);
817 if (cmp < 0)
818 t = t.left;
819 else if (cmp > 0)
820 t = t.right;
821 else return mergeValue(t, value, remappingFunction);
822 } while (t != null);
823 } else {
824 if (key == null)
825 throw new NullPointerException();
826 @SuppressWarnings("unchecked")
827 Comparable<? super K> k = (Comparable<? super K>) key;
828 do {
829 parent = t;
830 cmp = k.compareTo(t.key);
831 if (cmp < 0)
832 t = t.left;
833 else if (cmp > 0)
834 t = t.right;
835 else return mergeValue(t, value, remappingFunction);
836 } while (t != null);
837 }
838 addEntry(key, value, cmp, parent);
839 return value;
840 }
841
842 private V mergeValue(Entry<K, V> t, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
843 V oldValue = t.value;
844 V newValue;
845 if (t.value == null) {
846 newValue = value;
847 } else {
848 int mc = modCount;
849 newValue = remappingFunction.apply(oldValue, value);
850 if (mc != modCount) {
851 throw new ConcurrentModificationException();
852 }
853 }
854 if (newValue == null) {
855 deleteEntry(t);
856 return null;
857 } else {
858 // replace old mapping
859 t.value = newValue;
860 return newValue;
861 }
862 }
863
864 /**
865 * Removes the mapping for this key from this TreeMap if present.
866 *
867 * @param key key for which mapping should be removed
868 * @return the previous value associated with {@code key}, or
869 * {@code null} if there was no mapping for {@code key}.
870 * (A {@code null} return can also indicate that the map
871 * previously associated {@code null} with {@code key}.)
872 * @throws ClassCastException if the specified key cannot be compared
873 * with the keys currently in the map
874 * @throws NullPointerException if the specified key is null
875 * and this map uses natural ordering, or its comparator
876 * does not permit null keys
877 */
878 public V remove(Object key) {
879 Entry<K,V> p = getEntry(key);
880 if (p == null)
881 return null;
882
883 V oldValue = p.value;
884 deleteEntry(p);
885 return oldValue;
886 }
887
888 /**
889 * Removes all of the mappings from this map.
890 * The map will be empty after this call returns.
891 */
892 public void clear() {
893 modCount++;
894 size = 0;
895 root = null;
896 }
897
898 /**
899 * Returns a shallow copy of this {@code TreeMap} instance. (The keys and
900 * values themselves are not cloned.)
901 *
902 * @return a shallow copy of this map
903 */
904 public Object clone() {
905 TreeMap<?,?> clone;
906 try {
907 clone = (TreeMap<?,?>) super.clone();
908 } catch (CloneNotSupportedException e) {
909 throw new InternalError(e);
910 }
911
912 // Put clone into "virgin" state (except for comparator)
913 clone.root = null;
914 clone.size = 0;
915 clone.modCount = 0;
916 clone.entrySet = null;
917 clone.navigableKeySet = null;
918 clone.descendingMap = null;
919
920 // Initialize clone with our mappings
921 try {
922 clone.buildFromSorted(size, entrySet().iterator(), null, null);
923 } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
924 }
925
926 return clone;
927 }
928
929 // NavigableMap API methods
930
931 /**
932 * @since 1.6
933 */
934 public Map.Entry<K,V> firstEntry() {
935 return exportEntry(getFirstEntry());
936 }
937
938 /**
939 * @since 1.6
940 */
941 public Map.Entry<K,V> lastEntry() {
942 return exportEntry(getLastEntry());
943 }
944
945 /**
946 * @since 1.6
947 */
948 public Map.Entry<K,V> pollFirstEntry() {
949 Entry<K,V> p = getFirstEntry();
950 Map.Entry<K,V> result = exportEntry(p);
951 if (p != null)
952 deleteEntry(p);
953 return result;
954 }
955
956 /**
957 * @since 1.6
958 */
959 public Map.Entry<K,V> pollLastEntry() {
960 Entry<K,V> p = getLastEntry();
961 Map.Entry<K,V> result = exportEntry(p);
962 if (p != null)
963 deleteEntry(p);
964 return result;
965 }
966
967 /**
968 * @throws ClassCastException {@inheritDoc}
969 * @throws NullPointerException if the specified key is null
970 * and this map uses natural ordering, or its comparator
971 * does not permit null keys
972 * @since 1.6
973 */
974 public Map.Entry<K,V> lowerEntry(K key) {
975 return exportEntry(getLowerEntry(key));
976 }
977
978 /**
979 * @throws ClassCastException {@inheritDoc}
980 * @throws NullPointerException if the specified key is null
981 * and this map uses natural ordering, or its comparator
982 * does not permit null keys
983 * @since 1.6
984 */
985 public K lowerKey(K key) {
986 return keyOrNull(getLowerEntry(key));
987 }
988
989 /**
990 * @throws ClassCastException {@inheritDoc}
991 * @throws NullPointerException if the specified key is null
992 * and this map uses natural ordering, or its comparator
993 * does not permit null keys
994 * @since 1.6
995 */
996 public Map.Entry<K,V> floorEntry(K key) {
997 return exportEntry(getFloorEntry(key));
998 }
999
1000 /**
1001 * @throws ClassCastException {@inheritDoc}
1002 * @throws NullPointerException if the specified key is null
1003 * and this map uses natural ordering, or its comparator
1004 * does not permit null keys
1005 * @since 1.6
1006 */
1007 public K floorKey(K key) {
1008 return keyOrNull(getFloorEntry(key));
1009 }
1010
1011 /**
1012 * @throws ClassCastException {@inheritDoc}
1013 * @throws NullPointerException if the specified key is null
1014 * and this map uses natural ordering, or its comparator
1015 * does not permit null keys
1016 * @since 1.6
1017 */
1018 public Map.Entry<K,V> ceilingEntry(K key) {
1019 return exportEntry(getCeilingEntry(key));
1020 }
1021
1022 /**
1023 * @throws ClassCastException {@inheritDoc}
1024 * @throws NullPointerException if the specified key is null
1025 * and this map uses natural ordering, or its comparator
1026 * does not permit null keys
1027 * @since 1.6
1028 */
1029 public K ceilingKey(K key) {
1030 return keyOrNull(getCeilingEntry(key));
1031 }
1032
1033 /**
1034 * @throws ClassCastException {@inheritDoc}
1035 * @throws NullPointerException if the specified key is null
1036 * and this map uses natural ordering, or its comparator
1037 * does not permit null keys
1038 * @since 1.6
1039 */
1040 public Map.Entry<K,V> higherEntry(K key) {
1041 return exportEntry(getHigherEntry(key));
1042 }
1043
1044 /**
1045 * @throws ClassCastException {@inheritDoc}
1046 * @throws NullPointerException if the specified key is null
1047 * and this map uses natural ordering, or its comparator
1048 * does not permit null keys
1049 * @since 1.6
1050 */
1051 public K higherKey(K key) {
1052 return keyOrNull(getHigherEntry(key));
1053 }
1054
1055 // Views
1056
1057 /**
1058 * Fields initialized to contain an instance of the entry set view
1059 * the first time this view is requested. Views are stateless, so
1060 * there's no reason to create more than one.
1061 */
1062 private transient EntrySet entrySet;
1063 private transient KeySet<K> navigableKeySet;
1064 private transient NavigableMap<K,V> descendingMap;
1065
1066 /**
1067 * Returns a {@link Set} view of the keys contained in this map.
1068 *
1069 * <p>The set's iterator returns the keys in ascending order.
1070 * The set's spliterator is
1071 * <em><a href="Spliterator.html#binding">late-binding</a></em>,
1072 * <em>fail-fast</em>, and additionally reports {@link Spliterator#SORTED}
1073 * and {@link Spliterator#ORDERED} with an encounter order that is ascending
1074 * key order. The spliterator's comparator (see
1075 * {@link java.util.Spliterator#getComparator()}) is {@code null} if
1076 * the tree map's comparator (see {@link #comparator()}) is {@code null}.
1077 * Otherwise, the spliterator's comparator is the same as or imposes the
1078 * same total ordering as the tree map's comparator.
1079 *
1080 * <p>The set is backed by the map, so changes to the map are
1081 * reflected in the set, and vice-versa. If the map is modified
1082 * while an iteration over the set is in progress (except through
1083 * the iterator's own {@code remove} operation), the results of
1084 * the iteration are undefined. The set supports element removal,
1085 * which removes the corresponding mapping from the map, via the
1086 * {@code Iterator.remove}, {@code Set.remove},
1087 * {@code removeAll}, {@code retainAll}, and {@code clear}
1088 * operations. It does not support the {@code add} or {@code addAll}
1089 * operations.
1090 */
1091 public Set<K> keySet() {
1092 return navigableKeySet();
1093 }
1094
1095 /**
1096 * @since 1.6
1097 */
1098 public NavigableSet<K> navigableKeySet() {
1099 KeySet<K> nks = navigableKeySet;
1100 return (nks != null) ? nks : (navigableKeySet = new KeySet<>(this));
1101 }
1102
1103 /**
1104 * @since 1.6
1105 */
1106 public NavigableSet<K> descendingKeySet() {
1107 return descendingMap().navigableKeySet();
1108 }
1109
1110 /**
1111 * Returns a {@link Collection} view of the values contained in this map.
1112 *
1113 * <p>The collection's iterator returns the values in ascending order
1114 * of the corresponding keys. The collection's spliterator is
1115 * <em><a href="Spliterator.html#binding">late-binding</a></em>,
1116 * <em>fail-fast</em>, and additionally reports {@link Spliterator#ORDERED}
1117 * with an encounter order that is ascending order of the corresponding
1118 * keys.
1119 *
1120 * <p>The collection is backed by the map, so changes to the map are
1121 * reflected in the collection, and vice-versa. If the map is
1122 * modified while an iteration over the collection is in progress
1123 * (except through the iterator's own {@code remove} operation),
1124 * the results of the iteration are undefined. The collection
1125 * supports element removal, which removes the corresponding
1126 * mapping from the map, via the {@code Iterator.remove},
1127 * {@code Collection.remove}, {@code removeAll},
1128 * {@code retainAll} and {@code clear} operations. It does not
1129 * support the {@code add} or {@code addAll} operations.
1130 */
1131 public Collection<V> values() {
1132 Collection<V> vs = values;
1133 if (vs == null) {
1134 vs = new Values();
1135 values = vs;
1136 }
1137 return vs;
1138 }
1139
1140 /**
1141 * Returns a {@link Set} view of the mappings contained in this map.
1142 *
1143 * <p>The set's iterator returns the entries in ascending key order. The
1144 * set's spliterator is
1145 * <em><a href="Spliterator.html#binding">late-binding</a></em>,
1146 * <em>fail-fast</em>, and additionally reports {@link Spliterator#SORTED} and
1147 * {@link Spliterator#ORDERED} with an encounter order that is ascending key
1148 * order.
1149 *
1150 * <p>The set is backed by the map, so changes to the map are
1151 * reflected in the set, and vice-versa. If the map is modified
1152 * while an iteration over the set is in progress (except through
1153 * the iterator's own {@code remove} operation, or through the
1154 * {@code setValue} operation on a map entry returned by the
1155 * iterator) the results of the iteration are undefined. The set
1156 * supports element removal, which removes the corresponding
1157 * mapping from the map, via the {@code Iterator.remove},
1158 * {@code Set.remove}, {@code removeAll}, {@code retainAll} and
1159 * {@code clear} operations. It does not support the
1160 * {@code add} or {@code addAll} operations.
1161 */
1162 public Set<Map.Entry<K,V>> entrySet() {
1163 EntrySet es = entrySet;
1164 return (es != null) ? es : (entrySet = new EntrySet());
1165 }
1166
1167 /**
1168 * @since 1.6
1169 */
1170 public NavigableMap<K, V> descendingMap() {
1171 NavigableMap<K, V> km = descendingMap;
1172 return (km != null) ? km :
1173 (descendingMap = new DescendingSubMap<>(this,
1174 true, null, true,
1175 true, null, true));
1176 }
1177
1178 /**
1179 * @throws ClassCastException {@inheritDoc}
1180 * @throws NullPointerException if {@code fromKey} or {@code toKey} is
1181 * null and this map uses natural ordering, or its comparator
1182 * does not permit null keys
1183 * @throws IllegalArgumentException {@inheritDoc}
1184 * @since 1.6
1185 */
1186 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1187 K toKey, boolean toInclusive) {
1188 return new AscendingSubMap<>(this,
1189 false, fromKey, fromInclusive,
1190 false, toKey, toInclusive);
1191 }
1192
1193 /**
1194 * @throws ClassCastException {@inheritDoc}
1195 * @throws NullPointerException if {@code toKey} is null
1196 * and this map uses natural ordering, or its comparator
1197 * does not permit null keys
1198 * @throws IllegalArgumentException {@inheritDoc}
1199 * @since 1.6
1200 */
1201 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1202 return new AscendingSubMap<>(this,
1203 true, null, true,
1204 false, toKey, inclusive);
1205 }
1206
1207 /**
1208 * @throws ClassCastException {@inheritDoc}
1209 * @throws NullPointerException if {@code fromKey} is null
1210 * and this map uses natural ordering, or its comparator
1211 * does not permit null keys
1212 * @throws IllegalArgumentException {@inheritDoc}
1213 * @since 1.6
1214 */
1215 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1216 return new AscendingSubMap<>(this,
1217 false, fromKey, inclusive,
1218 true, null, true);
1219 }
1220
1221 /**
1222 * @throws ClassCastException {@inheritDoc}
1223 * @throws NullPointerException if {@code fromKey} or {@code toKey} is
1224 * null and this map uses natural ordering, or its comparator
1225 * does not permit null keys
1226 * @throws IllegalArgumentException {@inheritDoc}
1227 */
1228 public SortedMap<K,V> subMap(K fromKey, K toKey) {
1229 return subMap(fromKey, true, toKey, false);
1230 }
1231
1232 /**
1233 * @throws ClassCastException {@inheritDoc}
1234 * @throws NullPointerException if {@code toKey} is null
1235 * and this map uses natural ordering, or its comparator
1236 * does not permit null keys
1237 * @throws IllegalArgumentException {@inheritDoc}
1238 */
1239 public SortedMap<K,V> headMap(K toKey) {
1240 return headMap(toKey, false);
1241 }
1242
1243 /**
1244 * @throws ClassCastException {@inheritDoc}
1245 * @throws NullPointerException if {@code fromKey} is null
1246 * and this map uses natural ordering, or its comparator
1247 * does not permit null keys
1248 * @throws IllegalArgumentException {@inheritDoc}
1249 */
1250 public SortedMap<K,V> tailMap(K fromKey) {
1251 return tailMap(fromKey, true);
1252 }
1253
1254 @Override
1255 public boolean replace(K key, V oldValue, V newValue) {
1256 Entry<K,V> p = getEntry(key);
1257 if (p!=null && Objects.equals(oldValue, p.value)) {
1258 p.value = newValue;
1259 return true;
1260 }
1261 return false;
1262 }
1263
1264 @Override
1265 public V replace(K key, V value) {
1266 Entry<K,V> p = getEntry(key);
1267 if (p!=null) {
1268 V oldValue = p.value;
1269 p.value = value;
1270 return oldValue;
1271 }
1272 return null;
1273 }
1274
1275 @Override
1276 public void forEach(BiConsumer<? super K, ? super V> action) {
1277 Objects.requireNonNull(action);
1278 int expectedModCount = modCount;
1279 for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
1280 action.accept(e.key, e.value);
1281
1282 if (expectedModCount != modCount) {
1283 throw new ConcurrentModificationException();
1284 }
1285 }
1286 }
1287
1288 @Override
1289 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
1290 Objects.requireNonNull(function);
1291 int expectedModCount = modCount;
1292
1293 for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
1294 e.value = function.apply(e.key, e.value);
1295
1296 if (expectedModCount != modCount) {
1297 throw new ConcurrentModificationException();
1298 }
1299 }
1300 }
1301
1302 // View class support
1303
1304 class Values extends AbstractCollection<V> {
1305 public Iterator<V> iterator() {
1306 return new ValueIterator(getFirstEntry());
1307 }
1308
1309 public int size() {
1310 return TreeMap.this.size();
1311 }
1312
1313 public boolean contains(Object o) {
1314 return TreeMap.this.containsValue(o);
1315 }
1316
1317 public boolean remove(Object o) {
1318 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
1319 if (valEquals(e.getValue(), o)) {
1320 deleteEntry(e);
1321 return true;
1322 }
1323 }
1324 return false;
1325 }
1326
1327 public void clear() {
1328 TreeMap.this.clear();
1329 }
1330
1331 public Spliterator<V> spliterator() {
1332 return new ValueSpliterator<>(TreeMap.this, null, null, 0, -1, 0);
1333 }
1334 }
1335
1336 class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1337 public Iterator<Map.Entry<K,V>> iterator() {
1338 return new EntryIterator(getFirstEntry());
1339 }
1340
1341 public boolean contains(Object o) {
1342 if (!(o instanceof Map.Entry))
1343 return false;
1344 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1345 Object value = entry.getValue();
1346 Entry<K,V> p = getEntry(entry.getKey());
1347 return p != null && valEquals(p.getValue(), value);
1348 }
1349
1350 public boolean remove(Object o) {
1351 if (!(o instanceof Map.Entry))
1352 return false;
1353 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1354 Object value = entry.getValue();
1355 Entry<K,V> p = getEntry(entry.getKey());
1356 if (p != null && valEquals(p.getValue(), value)) {
1357 deleteEntry(p);
1358 return true;
1359 }
1360 return false;
1361 }
1362
1363 public int size() {
1364 return TreeMap.this.size();
1365 }
1366
1367 public void clear() {
1368 TreeMap.this.clear();
1369 }
1370
1371 public Spliterator<Map.Entry<K,V>> spliterator() {
1372 return new EntrySpliterator<>(TreeMap.this, null, null, 0, -1, 0);
1373 }
1374 }
1375
1376 /*
1377 * Unlike Values and EntrySet, the KeySet class is static,
1378 * delegating to a NavigableMap to allow use by SubMaps, which
1379 * outweighs the ugliness of needing type-tests for the following
1380 * Iterator methods that are defined appropriately in main versus
1381 * submap classes.
1382 */
1383
1384 Iterator<K> keyIterator() {
1385 return new KeyIterator(getFirstEntry());
1386 }
1387
1388 Iterator<K> descendingKeyIterator() {
1389 return new DescendingKeyIterator(getLastEntry());
1390 }
1391
1392 static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1393 private final NavigableMap<E, ?> m;
1394 KeySet(NavigableMap<E,?> map) { m = map; }
1395
1396 public Iterator<E> iterator() {
1397 if (m instanceof TreeMap)
1398 return ((TreeMap<E,?>)m).keyIterator();
1399 else
1400 return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
1401 }
1402
1403 public Iterator<E> descendingIterator() {
1404 if (m instanceof TreeMap)
1405 return ((TreeMap<E,?>)m).descendingKeyIterator();
1406 else
1407 return ((TreeMap.NavigableSubMap<E,?>)m).descendingKeyIterator();
1408 }
1409
1410 public int size() { return m.size(); }
1411 public boolean isEmpty() { return m.isEmpty(); }
1412 public boolean contains(Object o) { return m.containsKey(o); }
1413 public void clear() { m.clear(); }
1414 public E lower(E e) { return m.lowerKey(e); }
1415 public E floor(E e) { return m.floorKey(e); }
1416 public E ceiling(E e) { return m.ceilingKey(e); }
1417 public E higher(E e) { return m.higherKey(e); }
1418 public E first() { return m.firstKey(); }
1419 public E last() { return m.lastKey(); }
1420 public Comparator<? super E> comparator() { return m.comparator(); }
1421 public E pollFirst() {
1422 Map.Entry<E,?> e = m.pollFirstEntry();
1423 return (e == null) ? null : e.getKey();
1424 }
1425 public E pollLast() {
1426 Map.Entry<E,?> e = m.pollLastEntry();
1427 return (e == null) ? null : e.getKey();
1428 }
1429 public boolean remove(Object o) {
1430 int oldSize = size();
1431 m.remove(o);
1432 return size() != oldSize;
1433 }
1434 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1435 E toElement, boolean toInclusive) {
1436 return new KeySet<>(m.subMap(fromElement, fromInclusive,
1437 toElement, toInclusive));
1438 }
1439 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1440 return new KeySet<>(m.headMap(toElement, inclusive));
1441 }
1442 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1443 return new KeySet<>(m.tailMap(fromElement, inclusive));
1444 }
1445 public SortedSet<E> subSet(E fromElement, E toElement) {
1446 return subSet(fromElement, true, toElement, false);
1447 }
1448 public SortedSet<E> headSet(E toElement) {
1449 return headSet(toElement, false);
1450 }
1451 public SortedSet<E> tailSet(E fromElement) {
1452 return tailSet(fromElement, true);
1453 }
1454 public NavigableSet<E> descendingSet() {
1455 return new KeySet<>(m.descendingMap());
1456 }
1457
1458 public Spliterator<E> spliterator() {
1459 return keySpliteratorFor(m);
1460 }
1461 }
1462
1463 /**
1464 * Base class for TreeMap Iterators
1465 */
1466 abstract class PrivateEntryIterator<T> implements Iterator<T> {
1467 Entry<K,V> next;
1468 Entry<K,V> lastReturned;
1469 int expectedModCount;
1470
1471 PrivateEntryIterator(Entry<K,V> first) {
1472 expectedModCount = modCount;
1473 lastReturned = null;
1474 next = first;
1475 }
1476
1477 public final boolean hasNext() {
1478 return next != null;
1479 }
1480
1481 final Entry<K,V> nextEntry() {
1482 Entry<K,V> e = next;
1483 if (e == null)
1484 throw new NoSuchElementException();
1485 if (modCount != expectedModCount)
1486 throw new ConcurrentModificationException();
1487 next = successor(e);
1488 lastReturned = e;
1489 return e;
1490 }
1491
1492 final Entry<K,V> prevEntry() {
1493 Entry<K,V> e = next;
1494 if (e == null)
1495 throw new NoSuchElementException();
1496 if (modCount != expectedModCount)
1497 throw new ConcurrentModificationException();
1498 next = predecessor(e);
1499 lastReturned = e;
1500 return e;
1501 }
1502
1503 public void remove() {
1504 if (lastReturned == null)
1505 throw new IllegalStateException();
1506 if (modCount != expectedModCount)
1507 throw new ConcurrentModificationException();
1508 // deleted entries are replaced by their successors
1509 if (lastReturned.left != null && lastReturned.right != null)
1510 next = lastReturned;
1511 deleteEntry(lastReturned);
1512 expectedModCount = modCount;
1513 lastReturned = null;
1514 }
1515 }
1516
1517 final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1518 EntryIterator(Entry<K,V> first) {
1519 super(first);
1520 }
1521 public Map.Entry<K,V> next() {
1522 return nextEntry();
1523 }
1524 }
1525
1526 final class ValueIterator extends PrivateEntryIterator<V> {
1527 ValueIterator(Entry<K,V> first) {
1528 super(first);
1529 }
1530 public V next() {
1531 return nextEntry().value;
1532 }
1533 }
1534
1535 final class KeyIterator extends PrivateEntryIterator<K> {
1536 KeyIterator(Entry<K,V> first) {
1537 super(first);
1538 }
1539 public K next() {
1540 return nextEntry().key;
1541 }
1542 }
1543
1544 final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1545 DescendingKeyIterator(Entry<K,V> first) {
1546 super(first);
1547 }
1548 public K next() {
1549 return prevEntry().key;
1550 }
1551 public void remove() {
1552 if (lastReturned == null)
1553 throw new IllegalStateException();
1554 if (modCount != expectedModCount)
1555 throw new ConcurrentModificationException();
1556 deleteEntry(lastReturned);
1557 lastReturned = null;
1558 expectedModCount = modCount;
1559 }
1560 }
1561
1562 // Little utilities
1563
1564 /**
1565 * Compares two keys using the correct comparison method for this TreeMap.
1566 */
1567 @SuppressWarnings("unchecked")
1568 final int compare(Object k1, Object k2) {
1569 return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1570 : comparator.compare((K)k1, (K)k2);
1571 }
1572
1573 /**
1574 * Test two values for equality. Differs from o1.equals(o2) only in
1575 * that it copes with {@code null} o1 properly.
1576 */
1577 static final boolean valEquals(Object o1, Object o2) {
1578 return (o1==null ? o2==null : o1.equals(o2));
1579 }
1580
1581 /**
1582 * Return SimpleImmutableEntry for entry, or null if null
1583 */
1584 static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1585 return (e == null) ? null :
1586 new AbstractMap.SimpleImmutableEntry<>(e);
1587 }
1588
1589 /**
1590 * Return key for entry, or null if null
1591 */
1592 static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1593 return (e == null) ? null : e.key;
1594 }
1595
1596 /**
1597 * Returns the key corresponding to the specified Entry.
1598 * @throws NoSuchElementException if the Entry is null
1599 */
1600 static <K> K key(Entry<K,?> e) {
1601 if (e==null)
1602 throw new NoSuchElementException();
1603 return e.key;
1604 }
1605
1606
1607 // SubMaps
1608
1609 /**
1610 * Dummy value serving as unmatchable fence key for unbounded
1611 * SubMapIterators
1612 */
1613 private static final Object UNBOUNDED = new Object();
1614
1615 /**
1616 * @serial include
1617 */
1618 abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1619 implements NavigableMap<K,V>, java.io.Serializable {
1620 private static final long serialVersionUID = -2102997345730753016L;
1621 /**
1622 * The backing map.
1623 */
1624 final TreeMap<K,V> m;
1625
1626 /**
1627 * Endpoints are represented as triples (fromStart, lo,
1628 * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1629 * true, then the low (absolute) bound is the start of the
1630 * backing map, and the other values are ignored. Otherwise,
1631 * if loInclusive is true, lo is the inclusive bound, else lo
1632 * is the exclusive bound. Similarly for the upper bound.
1633 */
1634 final K lo, hi;
1635 final boolean fromStart, toEnd;
1636 final boolean loInclusive, hiInclusive;
1637
1638 NavigableSubMap(TreeMap<K,V> m,
1639 boolean fromStart, K lo, boolean loInclusive,
1640 boolean toEnd, K hi, boolean hiInclusive) {
1641 if (!fromStart && !toEnd) {
1642 if (m.compare(lo, hi) > 0)
1643 throw new IllegalArgumentException("fromKey > toKey");
1644 } else {
1645 if (!fromStart) // type check
1646 m.compare(lo, lo);
1647 if (!toEnd)
1648 m.compare(hi, hi);
1649 }
1650
1651 this.m = m;
1652 this.fromStart = fromStart;
1653 this.lo = lo;
1654 this.loInclusive = loInclusive;
1655 this.toEnd = toEnd;
1656 this.hi = hi;
1657 this.hiInclusive = hiInclusive;
1658 }
1659
1660 // internal utilities
1661
1662 final boolean tooLow(Object key) {
1663 if (!fromStart) {
1664 int c = m.compare(key, lo);
1665 if (c < 0 || (c == 0 && !loInclusive))
1666 return true;
1667 }
1668 return false;
1669 }
1670
1671 final boolean tooHigh(Object key) {
1672 if (!toEnd) {
1673 int c = m.compare(key, hi);
1674 if (c > 0 || (c == 0 && !hiInclusive))
1675 return true;
1676 }
1677 return false;
1678 }
1679
1680 final boolean inRange(Object key) {
1681 return !tooLow(key) && !tooHigh(key);
1682 }
1683
1684 final boolean inClosedRange(Object key) {
1685 return (fromStart || m.compare(key, lo) >= 0)
1686 && (toEnd || m.compare(hi, key) >= 0);
1687 }
1688
1689 final boolean inRange(Object key, boolean inclusive) {
1690 return inclusive ? inRange(key) : inClosedRange(key);
1691 }
1692
1693 /*
1694 * Absolute versions of relation operations.
1695 * Subclasses map to these using like-named "sub"
1696 * versions that invert senses for descending maps
1697 */
1698
1699 final TreeMap.Entry<K,V> absLowest() {
1700 TreeMap.Entry<K,V> e =
1701 (fromStart ? m.getFirstEntry() :
1702 (loInclusive ? m.getCeilingEntry(lo) :
1703 m.getHigherEntry(lo)));
1704 return (e == null || tooHigh(e.key)) ? null : e;
1705 }
1706
1707 final TreeMap.Entry<K,V> absHighest() {
1708 TreeMap.Entry<K,V> e =
1709 (toEnd ? m.getLastEntry() :
1710 (hiInclusive ? m.getFloorEntry(hi) :
1711 m.getLowerEntry(hi)));
1712 return (e == null || tooLow(e.key)) ? null : e;
1713 }
1714
1715 final TreeMap.Entry<K,V> absCeiling(K key) {
1716 if (tooLow(key))
1717 return absLowest();
1718 TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1719 return (e == null || tooHigh(e.key)) ? null : e;
1720 }
1721
1722 final TreeMap.Entry<K,V> absHigher(K key) {
1723 if (tooLow(key))
1724 return absLowest();
1725 TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1726 return (e == null || tooHigh(e.key)) ? null : e;
1727 }
1728
1729 final TreeMap.Entry<K,V> absFloor(K key) {
1730 if (tooHigh(key))
1731 return absHighest();
1732 TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1733 return (e == null || tooLow(e.key)) ? null : e;
1734 }
1735
1736 final TreeMap.Entry<K,V> absLower(K key) {
1737 if (tooHigh(key))
1738 return absHighest();
1739 TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1740 return (e == null || tooLow(e.key)) ? null : e;
1741 }
1742
1743 /** Returns the absolute high fence for ascending traversal */
1744 final TreeMap.Entry<K,V> absHighFence() {
1745 return (toEnd ? null : (hiInclusive ?
1746 m.getHigherEntry(hi) :
1747 m.getCeilingEntry(hi)));
1748 }
1749
1750 /** Return the absolute low fence for descending traversal */
1751 final TreeMap.Entry<K,V> absLowFence() {
1752 return (fromStart ? null : (loInclusive ?
1753 m.getLowerEntry(lo) :
1754 m.getFloorEntry(lo)));
1755 }
1756
1757 // Abstract methods defined in ascending vs descending classes
1758 // These relay to the appropriate absolute versions
1759
1760 abstract TreeMap.Entry<K,V> subLowest();
1761 abstract TreeMap.Entry<K,V> subHighest();
1762 abstract TreeMap.Entry<K,V> subCeiling(K key);
1763 abstract TreeMap.Entry<K,V> subHigher(K key);
1764 abstract TreeMap.Entry<K,V> subFloor(K key);
1765 abstract TreeMap.Entry<K,V> subLower(K key);
1766
1767 /** Returns ascending iterator from the perspective of this submap */
1768 abstract Iterator<K> keyIterator();
1769
1770 abstract Spliterator<K> keySpliterator();
1771
1772 /** Returns descending iterator from the perspective of this submap */
1773 abstract Iterator<K> descendingKeyIterator();
1774
1775 // public methods
1776
1777 public boolean isEmpty() {
1778 return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1779 }
1780
1781 public int size() {
1782 return (fromStart && toEnd) ? m.size() : entrySet().size();
1783 }
1784
1785 public final boolean containsKey(Object key) {
1786 return inRange(key) && m.containsKey(key);
1787 }
1788
1789 public final V put(K key, V value) {
1790 if (!inRange(key))
1791 throw new IllegalArgumentException("key out of range");
1792 return m.put(key, value);
1793 }
1794
1795 public final V get(Object key) {
1796 return !inRange(key) ? null : m.get(key);
1797 }
1798
1799 public final V remove(Object key) {
1800 return !inRange(key) ? null : m.remove(key);
1801 }
1802
1803 public final Map.Entry<K,V> ceilingEntry(K key) {
1804 return exportEntry(subCeiling(key));
1805 }
1806
1807 public final K ceilingKey(K key) {
1808 return keyOrNull(subCeiling(key));
1809 }
1810
1811 public final Map.Entry<K,V> higherEntry(K key) {
1812 return exportEntry(subHigher(key));
1813 }
1814
1815 public final K higherKey(K key) {
1816 return keyOrNull(subHigher(key));
1817 }
1818
1819 public final Map.Entry<K,V> floorEntry(K key) {
1820 return exportEntry(subFloor(key));
1821 }
1822
1823 public final K floorKey(K key) {
1824 return keyOrNull(subFloor(key));
1825 }
1826
1827 public final Map.Entry<K,V> lowerEntry(K key) {
1828 return exportEntry(subLower(key));
1829 }
1830
1831 public final K lowerKey(K key) {
1832 return keyOrNull(subLower(key));
1833 }
1834
1835 public final K firstKey() {
1836 return key(subLowest());
1837 }
1838
1839 public final K lastKey() {
1840 return key(subHighest());
1841 }
1842
1843 public final Map.Entry<K,V> firstEntry() {
1844 return exportEntry(subLowest());
1845 }
1846
1847 public final Map.Entry<K,V> lastEntry() {
1848 return exportEntry(subHighest());
1849 }
1850
1851 public final Map.Entry<K,V> pollFirstEntry() {
1852 TreeMap.Entry<K,V> e = subLowest();
1853 Map.Entry<K,V> result = exportEntry(e);
1854 if (e != null)
1855 m.deleteEntry(e);
1856 return result;
1857 }
1858
1859 public final Map.Entry<K,V> pollLastEntry() {
1860 TreeMap.Entry<K,V> e = subHighest();
1861 Map.Entry<K,V> result = exportEntry(e);
1862 if (e != null)
1863 m.deleteEntry(e);
1864 return result;
1865 }
1866
1867 // Views
1868 transient NavigableMap<K,V> descendingMapView;
1869 transient EntrySetView entrySetView;
1870 transient KeySet<K> navigableKeySetView;
1871
1872 public final NavigableSet<K> navigableKeySet() {
1873 KeySet<K> nksv = navigableKeySetView;
1874 return (nksv != null) ? nksv :
1875 (navigableKeySetView = new TreeMap.KeySet<>(this));
1876 }
1877
1878 public final Set<K> keySet() {
1879 return navigableKeySet();
1880 }
1881
1882 public NavigableSet<K> descendingKeySet() {
1883 return descendingMap().navigableKeySet();
1884 }
1885
1886 public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1887 return subMap(fromKey, true, toKey, false);
1888 }
1889
1890 public final SortedMap<K,V> headMap(K toKey) {
1891 return headMap(toKey, false);
1892 }
1893
1894 public final SortedMap<K,V> tailMap(K fromKey) {
1895 return tailMap(fromKey, true);
1896 }
1897
1898 // View classes
1899
1900 abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1901 private transient int size = -1, sizeModCount;
1902
1903 public int size() {
1904 if (fromStart && toEnd)
1905 return m.size();
1906 if (size == -1 || sizeModCount != m.modCount) {
1907 sizeModCount = m.modCount;
1908 size = 0;
1909 Iterator<?> i = iterator();
1910 while (i.hasNext()) {
1911 size++;
1912 i.next();
1913 }
1914 }
1915 return size;
1916 }
1917
1918 public boolean isEmpty() {
1919 TreeMap.Entry<K,V> n = absLowest();
1920 return n == null || tooHigh(n.key);
1921 }
1922
1923 public boolean contains(Object o) {
1924 if (!(o instanceof Map.Entry))
1925 return false;
1926 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1927 Object key = entry.getKey();
1928 if (!inRange(key))
1929 return false;
1930 TreeMap.Entry<?,?> node = m.getEntry(key);
1931 return node != null &&
1932 valEquals(node.getValue(), entry.getValue());
1933 }
1934
1935 public boolean remove(Object o) {
1936 if (!(o instanceof Map.Entry))
1937 return false;
1938 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1939 Object key = entry.getKey();
1940 if (!inRange(key))
1941 return false;
1942 TreeMap.Entry<K,V> node = m.getEntry(key);
1943 if (node!=null && valEquals(node.getValue(),
1944 entry.getValue())) {
1945 m.deleteEntry(node);
1946 return true;
1947 }
1948 return false;
1949 }
1950 }
1951
1952 /**
1953 * Iterators for SubMaps
1954 */
1955 abstract class SubMapIterator<T> implements Iterator<T> {
1956 TreeMap.Entry<K,V> lastReturned;
1957 TreeMap.Entry<K,V> next;
1958 final Object fenceKey;
1959 int expectedModCount;
1960
1961 SubMapIterator(TreeMap.Entry<K,V> first,
1962 TreeMap.Entry<K,V> fence) {
1963 expectedModCount = m.modCount;
1964 lastReturned = null;
1965 next = first;
1966 fenceKey = fence == null ? UNBOUNDED : fence.key;
1967 }
1968
1969 public final boolean hasNext() {
1970 return next != null && next.key != fenceKey;
1971 }
1972
1973 final TreeMap.Entry<K,V> nextEntry() {
1974 TreeMap.Entry<K,V> e = next;
1975 if (e == null || e.key == fenceKey)
1976 throw new NoSuchElementException();
1977 if (m.modCount != expectedModCount)
1978 throw new ConcurrentModificationException();
1979 next = successor(e);
1980 lastReturned = e;
1981 return e;
1982 }
1983
1984 final TreeMap.Entry<K,V> prevEntry() {
1985 TreeMap.Entry<K,V> e = next;
1986 if (e == null || e.key == fenceKey)
1987 throw new NoSuchElementException();
1988 if (m.modCount != expectedModCount)
1989 throw new ConcurrentModificationException();
1990 next = predecessor(e);
1991 lastReturned = e;
1992 return e;
1993 }
1994
1995 final void removeAscending() {
1996 if (lastReturned == null)
1997 throw new IllegalStateException();
1998 if (m.modCount != expectedModCount)
1999 throw new ConcurrentModificationException();
2000 // deleted entries are replaced by their successors
2001 if (lastReturned.left != null && lastReturned.right != null)
2002 next = lastReturned;
2003 m.deleteEntry(lastReturned);
2004 lastReturned = null;
2005 expectedModCount = m.modCount;
2006 }
2007
2008 final void removeDescending() {
2009 if (lastReturned == null)
2010 throw new IllegalStateException();
2011 if (m.modCount != expectedModCount)
2012 throw new ConcurrentModificationException();
2013 m.deleteEntry(lastReturned);
2014 lastReturned = null;
2015 expectedModCount = m.modCount;
2016 }
2017
2018 }
2019
2020 final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
2021 SubMapEntryIterator(TreeMap.Entry<K,V> first,
2022 TreeMap.Entry<K,V> fence) {
2023 super(first, fence);
2024 }
2025 public Map.Entry<K,V> next() {
2026 return nextEntry();
2027 }
2028 public void remove() {
2029 removeAscending();
2030 }
2031 }
2032
2033 final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
2034 DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
2035 TreeMap.Entry<K,V> fence) {
2036 super(last, fence);
2037 }
2038
2039 public Map.Entry<K,V> next() {
2040 return prevEntry();
2041 }
2042 public void remove() {
2043 removeDescending();
2044 }
2045 }
2046
2047 // Implement minimal Spliterator as KeySpliterator backup
2048 final class SubMapKeyIterator extends SubMapIterator<K>
2049 implements Spliterator<K> {
2050 SubMapKeyIterator(TreeMap.Entry<K,V> first,
2051 TreeMap.Entry<K,V> fence) {
2052 super(first, fence);
2053 }
2054 public K next() {
2055 return nextEntry().key;
2056 }
2057 public void remove() {
2058 removeAscending();
2059 }
2060 public Spliterator<K> trySplit() {
2061 return null;
2062 }
2063 public void forEachRemaining(Consumer<? super K> action) {
2064 while (hasNext())
2065 action.accept(next());
2066 }
2067 public boolean tryAdvance(Consumer<? super K> action) {
2068 if (hasNext()) {
2069 action.accept(next());
2070 return true;
2071 }
2072 return false;
2073 }
2074 public long estimateSize() {
2075 return Long.MAX_VALUE;
2076 }
2077 public int characteristics() {
2078 return Spliterator.DISTINCT | Spliterator.ORDERED |
2079 Spliterator.SORTED;
2080 }
2081 public final Comparator<? super K> getComparator() {
2082 return NavigableSubMap.this.comparator();
2083 }
2084 }
2085
2086 final class DescendingSubMapKeyIterator extends SubMapIterator<K>
2087 implements Spliterator<K> {
2088 DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
2089 TreeMap.Entry<K,V> fence) {
2090 super(last, fence);
2091 }
2092 public K next() {
2093 return prevEntry().key;
2094 }
2095 public void remove() {
2096 removeDescending();
2097 }
2098 public Spliterator<K> trySplit() {
2099 return null;
2100 }
2101 public void forEachRemaining(Consumer<? super K> action) {
2102 while (hasNext())
2103 action.accept(next());
2104 }
2105 public boolean tryAdvance(Consumer<? super K> action) {
2106 if (hasNext()) {
2107 action.accept(next());
2108 return true;
2109 }
2110 return false;
2111 }
2112 public long estimateSize() {
2113 return Long.MAX_VALUE;
2114 }
2115 public int characteristics() {
2116 return Spliterator.DISTINCT | Spliterator.ORDERED;
2117 }
2118 }
2119 }
2120
2121 /**
2122 * @serial include
2123 */
2124 static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
2125 private static final long serialVersionUID = 912986545866124060L;
2126
2127 AscendingSubMap(TreeMap<K,V> m,
2128 boolean fromStart, K lo, boolean loInclusive,
2129 boolean toEnd, K hi, boolean hiInclusive) {
2130 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
2131 }
2132
2133 public Comparator<? super K> comparator() {
2134 return m.comparator();
2135 }
2136
2137 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
2138 K toKey, boolean toInclusive) {
2139 if (!inRange(fromKey, fromInclusive))
2140 throw new IllegalArgumentException("fromKey out of range");
2141 if (!inRange(toKey, toInclusive))
2142 throw new IllegalArgumentException("toKey out of range");
2143 return new AscendingSubMap<>(m,
2144 false, fromKey, fromInclusive,
2145 false, toKey, toInclusive);
2146 }
2147
2148 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
2149 if (!inRange(toKey, inclusive))
2150 throw new IllegalArgumentException("toKey out of range");
2151 return new AscendingSubMap<>(m,
2152 fromStart, lo, loInclusive,
2153 false, toKey, inclusive);
2154 }
2155
2156 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
2157 if (!inRange(fromKey, inclusive))
2158 throw new IllegalArgumentException("fromKey out of range");
2159 return new AscendingSubMap<>(m,
2160 false, fromKey, inclusive,
2161 toEnd, hi, hiInclusive);
2162 }
2163
2164 public NavigableMap<K,V> descendingMap() {
2165 NavigableMap<K,V> mv = descendingMapView;
2166 return (mv != null) ? mv :
2167 (descendingMapView =
2168 new DescendingSubMap<>(m,
2169 fromStart, lo, loInclusive,
2170 toEnd, hi, hiInclusive));
2171 }
2172
2173 Iterator<K> keyIterator() {
2174 return new SubMapKeyIterator(absLowest(), absHighFence());
2175 }
2176
2177 Spliterator<K> keySpliterator() {
2178 return new SubMapKeyIterator(absLowest(), absHighFence());
2179 }
2180
2181 Iterator<K> descendingKeyIterator() {
2182 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
2183 }
2184
2185 final class AscendingEntrySetView extends EntrySetView {
2186 public Iterator<Map.Entry<K,V>> iterator() {
2187 return new SubMapEntryIterator(absLowest(), absHighFence());
2188 }
2189 }
2190
2191 public Set<Map.Entry<K,V>> entrySet() {
2192 EntrySetView es = entrySetView;
2193 return (es != null) ? es : (entrySetView = new AscendingEntrySetView());
2194 }
2195
2196 TreeMap.Entry<K,V> subLowest() { return absLowest(); }
2197 TreeMap.Entry<K,V> subHighest() { return absHighest(); }
2198 TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
2199 TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); }
2200 TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); }
2201 TreeMap.Entry<K,V> subLower(K key) { return absLower(key); }
2202 }
2203
2204 /**
2205 * @serial include
2206 */
2207 static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
2208 private static final long serialVersionUID = 912986545866120460L;
2209 DescendingSubMap(TreeMap<K,V> m,
2210 boolean fromStart, K lo, boolean loInclusive,
2211 boolean toEnd, K hi, boolean hiInclusive) {
2212 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
2213 }
2214
2215 private final Comparator<? super K> reverseComparator =
2216 Collections.reverseOrder(m.comparator);
2217
2218 public Comparator<? super K> comparator() {
2219 return reverseComparator;
2220 }
2221
2222 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
2223 K toKey, boolean toInclusive) {
2224 if (!inRange(fromKey, fromInclusive))
2225 throw new IllegalArgumentException("fromKey out of range");
2226 if (!inRange(toKey, toInclusive))
2227 throw new IllegalArgumentException("toKey out of range");
2228 return new DescendingSubMap<>(m,
2229 false, toKey, toInclusive,
2230 false, fromKey, fromInclusive);
2231 }
2232
2233 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
2234 if (!inRange(toKey, inclusive))
2235 throw new IllegalArgumentException("toKey out of range");
2236 return new DescendingSubMap<>(m,
2237 false, toKey, inclusive,
2238 toEnd, hi, hiInclusive);
2239 }
2240
2241 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
2242 if (!inRange(fromKey, inclusive))
2243 throw new IllegalArgumentException("fromKey out of range");
2244 return new DescendingSubMap<>(m,
2245 fromStart, lo, loInclusive,
2246 false, fromKey, inclusive);
2247 }
2248
2249 public NavigableMap<K,V> descendingMap() {
2250 NavigableMap<K,V> mv = descendingMapView;
2251 return (mv != null) ? mv :
2252 (descendingMapView =
2253 new AscendingSubMap<>(m,
2254 fromStart, lo, loInclusive,
2255 toEnd, hi, hiInclusive));
2256 }
2257
2258 Iterator<K> keyIterator() {
2259 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
2260 }
2261
2262 Spliterator<K> keySpliterator() {
2263 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
2264 }
2265
2266 Iterator<K> descendingKeyIterator() {
2267 return new SubMapKeyIterator(absLowest(), absHighFence());
2268 }
2269
2270 final class DescendingEntrySetView extends EntrySetView {
2271 public Iterator<Map.Entry<K,V>> iterator() {
2272 return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
2273 }
2274 }
2275
2276 public Set<Map.Entry<K,V>> entrySet() {
2277 EntrySetView es = entrySetView;
2278 return (es != null) ? es : (entrySetView = new DescendingEntrySetView());
2279 }
2280
2281 TreeMap.Entry<K,V> subLowest() { return absHighest(); }
2282 TreeMap.Entry<K,V> subHighest() { return absLowest(); }
2283 TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
2284 TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
2285 TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
2286 TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
2287 }
2288
2289 /**
2290 * This class exists solely for the sake of serialization
2291 * compatibility with previous releases of TreeMap that did not
2292 * support NavigableMap. It translates an old-version SubMap into
2293 * a new-version AscendingSubMap. This class is never otherwise
2294 * used.
2295 *
2296 * @serial include
2297 */
2298 private class SubMap extends AbstractMap<K,V>
2299 implements SortedMap<K,V>, java.io.Serializable {
2300 private static final long serialVersionUID = -6520786458950516097L;
2301 private boolean fromStart = false, toEnd = false;
2302 private K fromKey, toKey;
2303 private Object readResolve() {
2304 return new AscendingSubMap<>(TreeMap.this,
2305 fromStart, fromKey, true,
2306 toEnd, toKey, false);
2307 }
2308 public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
2309 public K lastKey() { throw new InternalError(); }
2310 public K firstKey() { throw new InternalError(); }
2311 public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
2312 public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
2313 public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
2314 public Comparator<? super K> comparator() { throw new InternalError(); }
2315 }
2316
2317
2318 // Red-black mechanics
2319
2320 private static final boolean RED = false;
2321 private static final boolean BLACK = true;
2322
2323 /**
2324 * Node in the Tree. Doubles as a means to pass key-value pairs back to
2325 * user (see Map.Entry).
2326 */
2327
2328 static final class Entry<K,V> implements Map.Entry<K,V> {
2329 K key;
2330 V value;
2331 Entry<K,V> left;
2332 Entry<K,V> right;
2333 Entry<K,V> parent;
2334 boolean color = BLACK;
2335
2336 /**
2337 * Make a new cell with given key, value, and parent, and with
2338 * {@code null} child links, and BLACK color.
2339 */
2340 Entry(K key, V value, Entry<K,V> parent) {
2341 this.key = key;
2342 this.value = value;
2343 this.parent = parent;
2344 }
2345
2346 /**
2347 * Returns the key.
2348 *
2349 * @return the key
2350 */
2351 public K getKey() {
2352 return key;
2353 }
2354
2355 /**
2356 * Returns the value associated with the key.
2357 *
2358 * @return the value associated with the key
2359 */
2360 public V getValue() {
2361 return value;
2362 }
2363
2364 /**
2365 * Replaces the value currently associated with the key with the given
2366 * value.
2367 *
2368 * @return the value associated with the key before this method was
2369 * called
2370 */
2371 public V setValue(V value) {
2372 V oldValue = this.value;
2373 this.value = value;
2374 return oldValue;
2375 }
2376
2377 public boolean equals(Object o) {
2378 if (!(o instanceof Map.Entry))
2379 return false;
2380 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2381
2382 return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
2383 }
2384
2385 public int hashCode() {
2386 int keyHash = (key==null ? 0 : key.hashCode());
2387 int valueHash = (value==null ? 0 : value.hashCode());
2388 return keyHash ^ valueHash;
2389 }
2390
2391 public String toString() {
2392 return key + "=" + value;
2393 }
2394 }
2395
2396 /**
2397 * Returns the first Entry in the TreeMap (according to the TreeMap's
2398 * key-sort function). Returns null if the TreeMap is empty.
2399 */
2400 final Entry<K,V> getFirstEntry() {
2401 Entry<K,V> p = root;
2402 if (p != null)
2403 while (p.left != null)
2404 p = p.left;
2405 return p;
2406 }
2407
2408 /**
2409 * Returns the last Entry in the TreeMap (according to the TreeMap's
2410 * key-sort function). Returns null if the TreeMap is empty.
2411 */
2412 final Entry<K,V> getLastEntry() {
2413 Entry<K,V> p = root;
2414 if (p != null)
2415 while (p.right != null)
2416 p = p.right;
2417 return p;
2418 }
2419
2420 /**
2421 * Returns the successor of the specified Entry, or null if no such.
2422 */
2423 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2424 if (t == null)
2425 return null;
2426 else if (t.right != null) {
2427 Entry<K,V> p = t.right;
2428 while (p.left != null)
2429 p = p.left;
2430 return p;
2431 } else {
2432 Entry<K,V> p = t.parent;
2433 Entry<K,V> ch = t;
2434 while (p != null && ch == p.right) {
2435 ch = p;
2436 p = p.parent;
2437 }
2438 return p;
2439 }
2440 }
2441
2442 /**
2443 * Returns the predecessor of the specified Entry, or null if no such.
2444 */
2445 static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2446 if (t == null)
2447 return null;
2448 else if (t.left != null) {
2449 Entry<K,V> p = t.left;
2450 while (p.right != null)
2451 p = p.right;
2452 return p;
2453 } else {
2454 Entry<K,V> p = t.parent;
2455 Entry<K,V> ch = t;
2456 while (p != null && ch == p.left) {
2457 ch = p;
2458 p = p.parent;
2459 }
2460 return p;
2461 }
2462 }
2463
2464 /**
2465 * Balancing operations.
2466 *
2467 * Implementations of rebalancings during insertion and deletion are
2468 * slightly different than the CLR version. Rather than using dummy
2469 * nilnodes, we use a set of accessors that deal properly with null. They
2470 * are used to avoid messiness surrounding nullness checks in the main
2471 * algorithms.
2472 */
2473
2474 private static <K,V> boolean colorOf(Entry<K,V> p) {
2475 return (p == null ? BLACK : p.color);
2476 }
2477
2478 private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
2479 return (p == null ? null: p.parent);
2480 }
2481
2482 private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2483 if (p != null)
2484 p.color = c;
2485 }
2486
2487 private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
2488 return (p == null) ? null: p.left;
2489 }
2490
2491 private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
2492 return (p == null) ? null: p.right;
2493 }
2494
2495 /** From CLR */
2496 private void rotateLeft(Entry<K,V> p) {
2497 if (p != null) {
2498 Entry<K,V> r = p.right;
2499 p.right = r.left;
2500 if (r.left != null)
2501 r.left.parent = p;
2502 r.parent = p.parent;
2503 if (p.parent == null)
2504 root = r;
2505 else if (p.parent.left == p)
2506 p.parent.left = r;
2507 else
2508 p.parent.right = r;
2509 r.left = p;
2510 p.parent = r;
2511 }
2512 }
2513
2514 /** From CLR */
2515 private void rotateRight(Entry<K,V> p) {
2516 if (p != null) {
2517 Entry<K,V> l = p.left;
2518 p.left = l.right;
2519 if (l.right != null) l.right.parent = p;
2520 l.parent = p.parent;
2521 if (p.parent == null)
2522 root = l;
2523 else if (p.parent.right == p)
2524 p.parent.right = l;
2525 else p.parent.left = l;
2526 l.right = p;
2527 p.parent = l;
2528 }
2529 }
2530
2531 /** From CLR */
2532 private void fixAfterInsertion(Entry<K,V> x) {
2533 x.color = RED;
2534
2535 while (x != null && x != root && x.parent.color == RED) {
2536 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
2537 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
2538 if (colorOf(y) == RED) {
2539 setColor(parentOf(x), BLACK);
2540 setColor(y, BLACK);
2541 setColor(parentOf(parentOf(x)), RED);
2542 x = parentOf(parentOf(x));
2543 } else {
2544 if (x == rightOf(parentOf(x))) {
2545 x = parentOf(x);
2546 rotateLeft(x);
2547 }
2548 setColor(parentOf(x), BLACK);
2549 setColor(parentOf(parentOf(x)), RED);
2550 rotateRight(parentOf(parentOf(x)));
2551 }
2552 } else {
2553 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
2554 if (colorOf(y) == RED) {
2555 setColor(parentOf(x), BLACK);
2556 setColor(y, BLACK);
2557 setColor(parentOf(parentOf(x)), RED);
2558 x = parentOf(parentOf(x));
2559 } else {
2560 if (x == leftOf(parentOf(x))) {
2561 x = parentOf(x);
2562 rotateRight(x);
2563 }
2564 setColor(parentOf(x), BLACK);
2565 setColor(parentOf(parentOf(x)), RED);
2566 rotateLeft(parentOf(parentOf(x)));
2567 }
2568 }
2569 }
2570 root.color = BLACK;
2571 }
2572
2573 /**
2574 * Delete node p, and then rebalance the tree.
2575 */
2576 private void deleteEntry(Entry<K,V> p) {
2577 modCount++;
2578 size--;
2579
2580 // If strictly internal, copy successor's element to p and then make p
2581 // point to successor.
2582 if (p.left != null && p.right != null) {
2583 Entry<K,V> s = successor(p);
2584 p.key = s.key;
2585 p.value = s.value;
2586 p = s;
2587 } // p has 2 children
2588
2589 // Start fixup at replacement node, if it exists.
2590 Entry<K,V> replacement = (p.left != null ? p.left : p.right);
2591
2592 if (replacement != null) {
2593 // Link replacement to parent
2594 replacement.parent = p.parent;
2595 if (p.parent == null)
2596 root = replacement;
2597 else if (p == p.parent.left)
2598 p.parent.left = replacement;
2599 else
2600 p.parent.right = replacement;
2601
2602 // Null out links so they are OK to use by fixAfterDeletion.
2603 p.left = p.right = p.parent = null;
2604
2605 // Fix replacement
2606 if (p.color == BLACK)
2607 fixAfterDeletion(replacement);
2608 } else if (p.parent == null) { // return if we are the only node.
2609 root = null;
2610 } else { // No children. Use self as phantom replacement and unlink.
2611 if (p.color == BLACK)
2612 fixAfterDeletion(p);
2613
2614 if (p.parent != null) {
2615 if (p == p.parent.left)
2616 p.parent.left = null;
2617 else if (p == p.parent.right)
2618 p.parent.right = null;
2619 p.parent = null;
2620 }
2621 }
2622 }
2623
2624 /** From CLR */
2625 private void fixAfterDeletion(Entry<K,V> x) {
2626 while (x != root && colorOf(x) == BLACK) {
2627 if (x == leftOf(parentOf(x))) {
2628 Entry<K,V> sib = rightOf(parentOf(x));
2629
2630 if (colorOf(sib) == RED) {
2631 setColor(sib, BLACK);
2632 setColor(parentOf(x), RED);
2633 rotateLeft(parentOf(x));
2634 sib = rightOf(parentOf(x));
2635 }
2636
2637 if (colorOf(leftOf(sib)) == BLACK &&
2638 colorOf(rightOf(sib)) == BLACK) {
2639 setColor(sib, RED);
2640 x = parentOf(x);
2641 } else {
2642 if (colorOf(rightOf(sib)) == BLACK) {
2643 setColor(leftOf(sib), BLACK);
2644 setColor(sib, RED);
2645 rotateRight(sib);
2646 sib = rightOf(parentOf(x));
2647 }
2648 setColor(sib, colorOf(parentOf(x)));
2649 setColor(parentOf(x), BLACK);
2650 setColor(rightOf(sib), BLACK);
2651 rotateLeft(parentOf(x));
2652 x = root;
2653 }
2654 } else { // symmetric
2655 Entry<K,V> sib = leftOf(parentOf(x));
2656
2657 if (colorOf(sib) == RED) {
2658 setColor(sib, BLACK);
2659 setColor(parentOf(x), RED);
2660 rotateRight(parentOf(x));
2661 sib = leftOf(parentOf(x));
2662 }
2663
2664 if (colorOf(rightOf(sib)) == BLACK &&
2665 colorOf(leftOf(sib)) == BLACK) {
2666 setColor(sib, RED);
2667 x = parentOf(x);
2668 } else {
2669 if (colorOf(leftOf(sib)) == BLACK) {
2670 setColor(rightOf(sib), BLACK);
2671 setColor(sib, RED);
2672 rotateLeft(sib);
2673 sib = leftOf(parentOf(x));
2674 }
2675 setColor(sib, colorOf(parentOf(x)));
2676 setColor(parentOf(x), BLACK);
2677 setColor(leftOf(sib), BLACK);
2678 rotateRight(parentOf(x));
2679 x = root;
2680 }
2681 }
2682 }
2683
2684 setColor(x, BLACK);
2685 }
2686
2687 private static final long serialVersionUID = 919286545866124006L;
2688
2689 /**
2690 * Save the state of the {@code TreeMap} instance to a stream (i.e.,
2691 * serialize it).
2692 *
2693 * @serialData The <em>size</em> of the TreeMap (the number of key-value
2694 * mappings) is emitted (int), followed by the key (Object)
2695 * and value (Object) for each key-value mapping represented
2696 * by the TreeMap. The key-value mappings are emitted in
2697 * key-order (as determined by the TreeMap's Comparator,
2698 * or by the keys' natural ordering if the TreeMap has no
2699 * Comparator).
2700 */
2701 private void writeObject(java.io.ObjectOutputStream s)
2702 throws java.io.IOException {
2703 // Write out the Comparator and any hidden stuff
2704 s.defaultWriteObject();
2705
2706 // Write out size (number of Mappings)
2707 s.writeInt(size);
2708
2709 // Write out keys and values (alternating)
2710 for (Map.Entry<K, V> e : entrySet()) {
2711 s.writeObject(e.getKey());
2712 s.writeObject(e.getValue());
2713 }
2714 }
2715
2716 /**
2717 * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
2718 * deserialize it).
2719 */
2720 private void readObject(final java.io.ObjectInputStream s)
2721 throws java.io.IOException, ClassNotFoundException {
2722 // Read in the Comparator and any hidden stuff
2723 s.defaultReadObject();
2724
2725 // Read in size
2726 int size = s.readInt();
2727
2728 buildFromSorted(size, null, s, null);
2729 }
2730
2731 /** Intended to be called only from TreeSet.readObject */
2732 void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2733 throws java.io.IOException, ClassNotFoundException {
2734 buildFromSorted(size, null, s, defaultVal);
2735 }
2736
2737 /** Intended to be called only from TreeSet.addAll */
2738 void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2739 try {
2740 buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2741 } catch (java.io.IOException | ClassNotFoundException cannotHappen) {
2742 }
2743 }
2744
2745
2746 /**
2747 * Linear time tree building algorithm from sorted data. Can accept keys
2748 * and/or values from iterator or stream. This leads to too many
2749 * parameters, but seems better than alternatives. The four formats
2750 * that this method accepts are:
2751 *
2752 * 1) An iterator of Map.Entries. (it != null, defaultVal == null).
2753 * 2) An iterator of keys. (it != null, defaultVal != null).
2754 * 3) A stream of alternating serialized keys and values.
2755 * (it == null, defaultVal == null).
2756 * 4) A stream of serialized keys. (it == null, defaultVal != null).
2757 *
2758 * It is assumed that the comparator of the TreeMap is already set prior
2759 * to calling this method.
2760 *
2761 * @param size the number of keys (or key-value pairs) to be read from
2762 * the iterator or stream
2763 * @param it If non-null, new entries are created from entries
2764 * or keys read from this iterator.
2765 * @param str If non-null, new entries are created from keys and
2766 * possibly values read from this stream in serialized form.
2767 * Exactly one of it and str should be non-null.
2768 * @param defaultVal if non-null, this default value is used for
2769 * each value in the map. If null, each value is read from
2770 * iterator or stream, as described above.
2771 * @throws java.io.IOException propagated from stream reads. This cannot
2772 * occur if str is null.
2773 * @throws ClassNotFoundException propagated from readObject.
2774 * This cannot occur if str is null.
2775 */
2776 private void buildFromSorted(int size, Iterator<?> it,
2777 java.io.ObjectInputStream str,
2778 V defaultVal)
2779 throws java.io.IOException, ClassNotFoundException {
2780 this.size = size;
2781 root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2782 it, str, defaultVal);
2783 }
2784
2785 /**
2786 * Recursive "helper method" that does the real work of the
2787 * previous method. Identically named parameters have
2788 * identical definitions. Additional parameters are documented below.
2789 * It is assumed that the comparator and size fields of the TreeMap are
2790 * already set prior to calling this method. (It ignores both fields.)
2791 *
2792 * @param level the current level of tree. Initial call should be 0.
2793 * @param lo the first element index of this subtree. Initial should be 0.
2794 * @param hi the last element index of this subtree. Initial should be
2795 * size-1.
2796 * @param redLevel the level at which nodes should be red.
2797 * Must be equal to computeRedLevel for tree of this size.
2798 */
2799 @SuppressWarnings("unchecked")
2800 private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2801 int redLevel,
2802 Iterator<?> it,
2803 java.io.ObjectInputStream str,
2804 V defaultVal)
2805 throws java.io.IOException, ClassNotFoundException {
2806 /*
2807 * Strategy: The root is the middlemost element. To get to it, we
2808 * have to first recursively construct the entire left subtree,
2809 * so as to grab all of its elements. We can then proceed with right
2810 * subtree.
2811 *
2812 * The lo and hi arguments are the minimum and maximum
2813 * indices to pull out of the iterator or stream for current subtree.
2814 * They are not actually indexed, we just proceed sequentially,
2815 * ensuring that items are extracted in corresponding order.
2816 */
2817
2818 if (hi < lo) return null;
2819
2820 int mid = (lo + hi) >>> 1;
2821
2822 Entry<K,V> left = null;
2823 if (lo < mid)
2824 left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2825 it, str, defaultVal);
2826
2827 // extract key and/or value from iterator or stream
2828 K key;
2829 V value;
2830 if (it != null) {
2831 if (defaultVal==null) {
2832 Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
2833 key = (K)entry.getKey();
2834 value = (V)entry.getValue();
2835 } else {
2836 key = (K)it.next();
2837 value = defaultVal;
2838 }
2839 } else { // use stream
2840 key = (K) str.readObject();
2841 value = (defaultVal != null ? defaultVal : (V) str.readObject());
2842 }
2843
2844 Entry<K,V> middle = new Entry<>(key, value, null);
2845
2846 // color nodes in non-full bottommost level red
2847 if (level == redLevel)
2848 middle.color = RED;
2849
2850 if (left != null) {
2851 middle.left = left;
2852 left.parent = middle;
2853 }
2854
2855 if (mid < hi) {
2856 Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2857 it, str, defaultVal);
2858 middle.right = right;
2859 right.parent = middle;
2860 }
2861
2862 return middle;
2863 }
2864
2865 /**
2866 * Finds the level down to which to assign all nodes BLACK. This is the
2867 * last `full' level of the complete binary tree produced by buildTree.
2868 * The remaining nodes are colored RED. (This makes a `nice' set of
2869 * color assignments wrt future insertions.) This level number is
2870 * computed by finding the number of splits needed to reach the zeroeth
2871 * node.
2872 *
2873 * @param size the (non-negative) number of keys in the tree to be built
2874 */
2875 private static int computeRedLevel(int size) {
2876 return 31 - Integer.numberOfLeadingZeros(size + 1);
2877 }
2878
2879 /**
2880 * Currently, we support Spliterator-based versions only for the
2881 * full map, in either plain of descending form, otherwise relying
2882 * on defaults because size estimation for submaps would dominate
2883 * costs. The type tests needed to check these for key views are
2884 * not very nice but avoid disrupting existing class
2885 * structures. Callers must use plain default spliterators if this
2886 * returns null.
2887 */
2888 static <K> Spliterator<K> keySpliteratorFor(NavigableMap<K,?> m) {
2889 if (m instanceof TreeMap) {
2890 @SuppressWarnings("unchecked") TreeMap<K,Object> t =
2891 (TreeMap<K,Object>) m;
2892 return t.keySpliterator();
2893 }
2894 if (m instanceof DescendingSubMap) {
2895 @SuppressWarnings("unchecked") DescendingSubMap<K,?> dm =
2896 (DescendingSubMap<K,?>) m;
2897 TreeMap<K,?> tm = dm.m;
2898 if (dm == tm.descendingMap) {
2899 @SuppressWarnings("unchecked") TreeMap<K,Object> t =
2900 (TreeMap<K,Object>) tm;
2901 return t.descendingKeySpliterator();
2902 }
2903 }
2904 @SuppressWarnings("unchecked") NavigableSubMap<K,?> sm =
2905 (NavigableSubMap<K,?>) m;
2906 return sm.keySpliterator();
2907 }
2908
2909 final Spliterator<K> keySpliterator() {
2910 return new KeySpliterator<>(this, null, null, 0, -1, 0);
2911 }
2912
2913 final Spliterator<K> descendingKeySpliterator() {
2914 return new DescendingKeySpliterator<>(this, null, null, 0, -2, 0);
2915 }
2916
2917 /**
2918 * Base class for spliterators. Iteration starts at a given
2919 * origin and continues up to but not including a given fence (or
2920 * null for end). At top-level, for ascending cases, the first
2921 * split uses the root as left-fence/right-origin. From there,
2922 * right-hand splits replace the current fence with its left
2923 * child, also serving as origin for the split-off spliterator.
2924 * Left-hands are symmetric. Descending versions place the origin
2925 * at the end and invert ascending split rules. This base class
2926 * is non-committal about directionality, or whether the top-level
2927 * spliterator covers the whole tree. This means that the actual
2928 * split mechanics are located in subclasses. Some of the subclass
2929 * trySplit methods are identical (except for return types), but
2930 * not nicely factorable.
2931 *
2932 * Currently, subclass versions exist only for the full map
2933 * (including descending keys via its descendingMap). Others are
2934 * possible but currently not worthwhile because submaps require
2935 * O(n) computations to determine size, which substantially limits
2936 * potential speed-ups of using custom Spliterators versus default
2937 * mechanics.
2938 *
2939 * To boostrap initialization, external constructors use
2940 * negative size estimates: -1 for ascend, -2 for descend.
2941 */
2942 static class TreeMapSpliterator<K,V> {
2943 final TreeMap<K,V> tree;
2944 TreeMap.Entry<K,V> current; // traverser; initially first node in range
2945 TreeMap.Entry<K,V> fence; // one past last, or null
2946 int side; // 0: top, -1: is a left split, +1: right
2947 int est; // size estimate (exact only for top-level)
2948 int expectedModCount; // for CME checks
2949
2950 TreeMapSpliterator(TreeMap<K,V> tree,
2951 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2952 int side, int est, int expectedModCount) {
2953 this.tree = tree;
2954 this.current = origin;
2955 this.fence = fence;
2956 this.side = side;
2957 this.est = est;
2958 this.expectedModCount = expectedModCount;
2959 }
2960
2961 final int getEstimate() { // force initialization
2962 int s; TreeMap<K,V> t;
2963 if ((s = est) < 0) {
2964 if ((t = tree) != null) {
2965 current = (s == -1) ? t.getFirstEntry() : t.getLastEntry();
2966 s = est = t.size;
2967 expectedModCount = t.modCount;
2968 }
2969 else
2970 s = est = 0;
2971 }
2972 return s;
2973 }
2974
2975 public final long estimateSize() {
2976 return (long)getEstimate();
2977 }
2978 }
2979
2980 static final class KeySpliterator<K,V>
2981 extends TreeMapSpliterator<K,V>
2982 implements Spliterator<K> {
2983 KeySpliterator(TreeMap<K,V> tree,
2984 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2985 int side, int est, int expectedModCount) {
2986 super(tree, origin, fence, side, est, expectedModCount);
2987 }
2988
2989 public KeySpliterator<K,V> trySplit() {
2990 if (est < 0)
2991 getEstimate(); // force initialization
2992 int d = side;
2993 TreeMap.Entry<K,V> e = current, f = fence,
2994 s = ((e == null || e == f) ? null : // empty
2995 (d == 0) ? tree.root : // was top
2996 (d > 0) ? e.right : // was right
2997 (d < 0 && f != null) ? f.left : // was left
2998 null);
2999 if (s != null && s != e && s != f &&
3000 tree.compare(e.key, s.key) < 0) { // e not already past s
3001 side = 1;
3002 return new KeySpliterator<>
3003 (tree, e, current = s, -1, est >>>= 1, expectedModCount);
3004 }
3005 return null;
3006 }
3007
3008 public void forEachRemaining(Consumer<? super K> action) {
3009 if (action == null)
3010 throw new NullPointerException();
3011 if (est < 0)
3012 getEstimate(); // force initialization
3013 TreeMap.Entry<K,V> f = fence, e, p, pl;
3014 if ((e = current) != null && e != f) {
3015 current = f; // exhaust
3016 do {
3017 action.accept(e.key);
3018 if ((p = e.right) != null) {
3019 while ((pl = p.left) != null)
3020 p = pl;
3021 }
3022 else {
3023 while ((p = e.parent) != null && e == p.right)
3024 e = p;
3025 }
3026 } while ((e = p) != null && e != f);
3027 if (tree.modCount != expectedModCount)
3028 throw new ConcurrentModificationException();
3029 }
3030 }
3031
3032 public boolean tryAdvance(Consumer<? super K> action) {
3033 TreeMap.Entry<K,V> e;
3034 if (action == null)
3035 throw new NullPointerException();
3036 if (est < 0)
3037 getEstimate(); // force initialization
3038 if ((e = current) == null || e == fence)
3039 return false;
3040 current = successor(e);
3041 action.accept(e.key);
3042 if (tree.modCount != expectedModCount)
3043 throw new ConcurrentModificationException();
3044 return true;
3045 }
3046
3047 public int characteristics() {
3048 return (side == 0 ? Spliterator.SIZED : 0) |
3049 Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
3050 }
3051
3052 public final Comparator<? super K> getComparator() {
3053 return tree.comparator;
3054 }
3055
3056 }
3057
3058 static final class DescendingKeySpliterator<K,V>
3059 extends TreeMapSpliterator<K,V>
3060 implements Spliterator<K> {
3061 DescendingKeySpliterator(TreeMap<K,V> tree,
3062 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
3063 int side, int est, int expectedModCount) {
3064 super(tree, origin, fence, side, est, expectedModCount);
3065 }
3066
3067 public DescendingKeySpliterator<K,V> trySplit() {
3068 if (est < 0)
3069 getEstimate(); // force initialization
3070 int d = side;
3071 TreeMap.Entry<K,V> e = current, f = fence,
3072 s = ((e == null || e == f) ? null : // empty
3073 (d == 0) ? tree.root : // was top
3074 (d < 0) ? e.left : // was left
3075 (d > 0 && f != null) ? f.right : // was right
3076 null);
3077 if (s != null && s != e && s != f &&
3078 tree.compare(e.key, s.key) > 0) { // e not already past s
3079 side = 1;
3080 return new DescendingKeySpliterator<>
3081 (tree, e, current = s, -1, est >>>= 1, expectedModCount);
3082 }
3083 return null;
3084 }
3085
3086 public void forEachRemaining(Consumer<? super K> action) {
3087 if (action == null)
3088 throw new NullPointerException();
3089 if (est < 0)
3090 getEstimate(); // force initialization
3091 TreeMap.Entry<K,V> f = fence, e, p, pr;
3092 if ((e = current) != null && e != f) {
3093 current = f; // exhaust
3094 do {
3095 action.accept(e.key);
3096 if ((p = e.left) != null) {
3097 while ((pr = p.right) != null)
3098 p = pr;
3099 }
3100 else {
3101 while ((p = e.parent) != null && e == p.left)
3102 e = p;
3103 }
3104 } while ((e = p) != null && e != f);
3105 if (tree.modCount != expectedModCount)
3106 throw new ConcurrentModificationException();
3107 }
3108 }
3109
3110 public boolean tryAdvance(Consumer<? super K> action) {
3111 TreeMap.Entry<K,V> e;
3112 if (action == null)
3113 throw new NullPointerException();
3114 if (est < 0)
3115 getEstimate(); // force initialization
3116 if ((e = current) == null || e == fence)
3117 return false;
3118 current = predecessor(e);
3119 action.accept(e.key);
3120 if (tree.modCount != expectedModCount)
3121 throw new ConcurrentModificationException();
3122 return true;
3123 }
3124
3125 public int characteristics() {
3126 return (side == 0 ? Spliterator.SIZED : 0) |
3127 Spliterator.DISTINCT | Spliterator.ORDERED;
3128 }
3129 }
3130
3131 static final class ValueSpliterator<K,V>
3132 extends TreeMapSpliterator<K,V>
3133 implements Spliterator<V> {
3134 ValueSpliterator(TreeMap<K,V> tree,
3135 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
3136 int side, int est, int expectedModCount) {
3137 super(tree, origin, fence, side, est, expectedModCount);
3138 }
3139
3140 public ValueSpliterator<K,V> trySplit() {
3141 if (est < 0)
3142 getEstimate(); // force initialization
3143 int d = side;
3144 TreeMap.Entry<K,V> e = current, f = fence,
3145 s = ((e == null || e == f) ? null : // empty
3146 (d == 0) ? tree.root : // was top
3147 (d > 0) ? e.right : // was right
3148 (d < 0 && f != null) ? f.left : // was left
3149 null);
3150 if (s != null && s != e && s != f &&
3151 tree.compare(e.key, s.key) < 0) { // e not already past s
3152 side = 1;
3153 return new ValueSpliterator<>
3154 (tree, e, current = s, -1, est >>>= 1, expectedModCount);
3155 }
3156 return null;
3157 }
3158
3159 public void forEachRemaining(Consumer<? super V> action) {
3160 if (action == null)
3161 throw new NullPointerException();
3162 if (est < 0)
3163 getEstimate(); // force initialization
3164 TreeMap.Entry<K,V> f = fence, e, p, pl;
3165 if ((e = current) != null && e != f) {
3166 current = f; // exhaust
3167 do {
3168 action.accept(e.value);
3169 if ((p = e.right) != null) {
3170 while ((pl = p.left) != null)
3171 p = pl;
3172 }
3173 else {
3174 while ((p = e.parent) != null && e == p.right)
3175 e = p;
3176 }
3177 } while ((e = p) != null && e != f);
3178 if (tree.modCount != expectedModCount)
3179 throw new ConcurrentModificationException();
3180 }
3181 }
3182
3183 public boolean tryAdvance(Consumer<? super V> action) {
3184 TreeMap.Entry<K,V> e;
3185 if (action == null)
3186 throw new NullPointerException();
3187 if (est < 0)
3188 getEstimate(); // force initialization
3189 if ((e = current) == null || e == fence)
3190 return false;
3191 current = successor(e);
3192 action.accept(e.value);
3193 if (tree.modCount != expectedModCount)
3194 throw new ConcurrentModificationException();
3195 return true;
3196 }
3197
3198 public int characteristics() {
3199 return (side == 0 ? Spliterator.SIZED : 0) | Spliterator.ORDERED;
3200 }
3201 }
3202
3203 static final class EntrySpliterator<K,V>
3204 extends TreeMapSpliterator<K,V>
3205 implements Spliterator<Map.Entry<K,V>> {
3206 EntrySpliterator(TreeMap<K,V> tree,
3207 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
3208 int side, int est, int expectedModCount) {
3209 super(tree, origin, fence, side, est, expectedModCount);
3210 }
3211
3212 public EntrySpliterator<K,V> trySplit() {
3213 if (est < 0)
3214 getEstimate(); // force initialization
3215 int d = side;
3216 TreeMap.Entry<K,V> e = current, f = fence,
3217 s = ((e == null || e == f) ? null : // empty
3218 (d == 0) ? tree.root : // was top
3219 (d > 0) ? e.right : // was right
3220 (d < 0 && f != null) ? f.left : // was left
3221 null);
3222 if (s != null && s != e && s != f &&
3223 tree.compare(e.key, s.key) < 0) { // e not already past s
3224 side = 1;
3225 return new EntrySpliterator<>
3226 (tree, e, current = s, -1, est >>>= 1, expectedModCount);
3227 }
3228 return null;
3229 }
3230
3231 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
3232 if (action == null)
3233 throw new NullPointerException();
3234 if (est < 0)
3235 getEstimate(); // force initialization
3236 TreeMap.Entry<K,V> f = fence, e, p, pl;
3237 if ((e = current) != null && e != f) {
3238 current = f; // exhaust
3239 do {
3240 action.accept(e);
3241 if ((p = e.right) != null) {
3242 while ((pl = p.left) != null)
3243 p = pl;
3244 }
3245 else {
3246 while ((p = e.parent) != null && e == p.right)
3247 e = p;
3248 }
3249 } while ((e = p) != null && e != f);
3250 if (tree.modCount != expectedModCount)
3251 throw new ConcurrentModificationException();
3252 }
3253 }
3254
3255 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
3256 TreeMap.Entry<K,V> e;
3257 if (action == null)
3258 throw new NullPointerException();
3259 if (est < 0)
3260 getEstimate(); // force initialization
3261 if ((e = current) == null || e == fence)
3262 return false;
3263 current = successor(e);
3264 action.accept(e);
3265 if (tree.modCount != expectedModCount)
3266 throw new ConcurrentModificationException();
3267 return true;
3268 }
3269
3270 public int characteristics() {
3271 return (side == 0 ? Spliterator.SIZED : 0) |
3272 Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
3273 }
3274
3275 @Override
3276 public Comparator<Map.Entry<K, V>> getComparator() {
3277 // Adapt or create a key-based comparator
3278 if (tree.comparator != null) {
3279 return Map.Entry.comparingByKey(tree.comparator);
3280 }
3281 else {
3282 return (Comparator<Map.Entry<K, V>> & Serializable) (e1, e2) -> {
3283 @SuppressWarnings("unchecked")
3284 Comparable<? super K> k1 = (Comparable<? super K>) e1.getKey();
3285 return k1.compareTo(e2.getKey());
3286 };
3287 }
3288 }
3289 }
3290 }