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