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