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