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