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