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