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