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