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 synchronized boolean replace(K key, V oldValue, V newValue) {
952 Entry<K,V> p = getEntry(key);
953 if (p!=null && Objects.equals(oldValue, p.value)) {
954 p.value = newValue;
955 return true;
956 }
957 return false;
958 }
959
960 @Override
961 public synchronized V replace(K key, V value) {
962 Entry<K,V> p = getEntry(key);
963 if (p!=null) {
964 V oldValue = p.value;
965 p.value = value;
966 return oldValue;
967 }
968 return null;
969 }
970
971 @Override
972 public void forEach(BiConsumer<? super K, ? super V> action) {
973 Objects.requireNonNull(action);
974 int expectedModCount = modCount;
975 for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
976 action.accept(e.key, e.value);
977
978 if (expectedModCount != modCount) {
979 throw new ConcurrentModificationException();
980 }
981 }
982 }
983
984 @Override
985 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
986 Objects.requireNonNull(function);
987 int expectedModCount = modCount;
988
989 for (Entry<K, V> e = getFirstEntry(); e != null; e = successor(e)) {
990 e.value = function.apply(e.key, e.value);
991
992 if (expectedModCount != modCount) {
993 throw new ConcurrentModificationException();
994 }
995 }
996 }
997
998 // View class support
999
1000 class Values extends AbstractCollection<V> {
1001 public Iterator<V> iterator() {
1002 return new ValueIterator(getFirstEntry());
1003 }
1004
1005 public int size() {
1006 return TreeMap.this.size();
1007 }
1008
1009 public boolean contains(Object o) {
1010 return TreeMap.this.containsValue(o);
1011 }
1012
1013 public boolean remove(Object o) {
1014 for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
1015 if (valEquals(e.getValue(), o)) {
1016 deleteEntry(e);
1017 return true;
1018 }
1019 }
1020 return false;
1021 }
1022
1023 public void clear() {
1024 TreeMap.this.clear();
1025 }
1026
1027 public Spliterator<V> spliterator() {
1028 return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
1029 }
1030 }
1031
1032 class EntrySet extends AbstractSet<Map.Entry<K,V>> {
1033 public Iterator<Map.Entry<K,V>> iterator() {
1034 return new EntryIterator(getFirstEntry());
1035 }
1036
1037 public boolean contains(Object o) {
1038 if (!(o instanceof Map.Entry))
1039 return false;
1040 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1041 Object value = entry.getValue();
1042 Entry<K,V> p = getEntry(entry.getKey());
1043 return p != null && valEquals(p.getValue(), value);
1044 }
1045
1046 public boolean remove(Object o) {
1047 if (!(o instanceof Map.Entry))
1048 return false;
1049 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1050 Object value = entry.getValue();
1051 Entry<K,V> p = getEntry(entry.getKey());
1052 if (p != null && valEquals(p.getValue(), value)) {
1053 deleteEntry(p);
1054 return true;
1055 }
1056 return false;
1057 }
1058
1059 public int size() {
1060 return TreeMap.this.size();
1061 }
1062
1063 public void clear() {
1064 TreeMap.this.clear();
1065 }
1066
1067 public Spliterator<Map.Entry<K,V>> spliterator() {
1068 return new EntrySpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
1069 }
1070 }
1071
1072 /*
1073 * Unlike Values and EntrySet, the KeySet class is static,
1074 * delegating to a NavigableMap to allow use by SubMaps, which
1075 * outweighs the ugliness of needing type-tests for the following
1076 * Iterator methods that are defined appropriately in main versus
1077 * submap classes.
1078 */
1079
1080 Iterator<K> keyIterator() {
1081 return new KeyIterator(getFirstEntry());
1082 }
1083
1084 Iterator<K> descendingKeyIterator() {
1085 return new DescendingKeyIterator(getLastEntry());
1086 }
1087
1088 static final class KeySet<E> extends AbstractSet<E> implements NavigableSet<E> {
1089 private final NavigableMap<E, ?> m;
1090 KeySet(NavigableMap<E,?> map) { m = map; }
1091
1092 public Iterator<E> iterator() {
1093 if (m instanceof TreeMap)
1094 return ((TreeMap<E,?>)m).keyIterator();
1095 else
1096 return ((TreeMap.NavigableSubMap<E,?>)m).keyIterator();
1097 }
1098
1099 public Iterator<E> descendingIterator() {
1100 if (m instanceof TreeMap)
1101 return ((TreeMap<E,?>)m).descendingKeyIterator();
1102 else
1103 return ((TreeMap.NavigableSubMap<E,?>)m).descendingKeyIterator();
1104 }
1105
1106 public int size() { return m.size(); }
1107 public boolean isEmpty() { return m.isEmpty(); }
1108 public boolean contains(Object o) { return m.containsKey(o); }
1109 public void clear() { m.clear(); }
1110 public E lower(E e) { return m.lowerKey(e); }
1111 public E floor(E e) { return m.floorKey(e); }
1112 public E ceiling(E e) { return m.ceilingKey(e); }
1113 public E higher(E e) { return m.higherKey(e); }
1114 public E first() { return m.firstKey(); }
1115 public E last() { return m.lastKey(); }
1116 public Comparator<? super E> comparator() { return m.comparator(); }
1117 public E pollFirst() {
1118 Map.Entry<E,?> e = m.pollFirstEntry();
1119 return (e == null) ? null : e.getKey();
1120 }
1121 public E pollLast() {
1122 Map.Entry<E,?> e = m.pollLastEntry();
1123 return (e == null) ? null : e.getKey();
1124 }
1125 public boolean remove(Object o) {
1126 int oldSize = size();
1127 m.remove(o);
1128 return size() != oldSize;
1129 }
1130 public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
1131 E toElement, boolean toInclusive) {
1132 return new KeySet<>(m.subMap(fromElement, fromInclusive,
1133 toElement, toInclusive));
1134 }
1135 public NavigableSet<E> headSet(E toElement, boolean inclusive) {
1136 return new KeySet<>(m.headMap(toElement, inclusive));
1137 }
1138 public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
1139 return new KeySet<>(m.tailMap(fromElement, inclusive));
1140 }
1141 public SortedSet<E> subSet(E fromElement, E toElement) {
1142 return subSet(fromElement, true, toElement, false);
1143 }
1144 public SortedSet<E> headSet(E toElement) {
1145 return headSet(toElement, false);
1146 }
1147 public SortedSet<E> tailSet(E fromElement) {
1148 return tailSet(fromElement, true);
1149 }
1150 public NavigableSet<E> descendingSet() {
1151 return new KeySet<>(m.descendingMap());
1152 }
1153
1154 public Spliterator<E> spliterator() {
1155 return keySpliteratorFor(m);
1156 }
1157 }
1158
1159 /**
1160 * Base class for TreeMap Iterators
1161 */
1162 abstract class PrivateEntryIterator<T> implements Iterator<T> {
1163 Entry<K,V> next;
1164 Entry<K,V> lastReturned;
1165 int expectedModCount;
1166
1167 PrivateEntryIterator(Entry<K,V> first) {
1168 expectedModCount = modCount;
1169 lastReturned = null;
1170 next = first;
1171 }
1172
1173 public final boolean hasNext() {
1174 return next != null;
1175 }
1176
1177 final Entry<K,V> nextEntry() {
1178 Entry<K,V> e = next;
1179 if (e == null)
1180 throw new NoSuchElementException();
1181 if (modCount != expectedModCount)
1182 throw new ConcurrentModificationException();
1183 next = successor(e);
1184 lastReturned = e;
1185 return e;
1186 }
1187
1188 final Entry<K,V> prevEntry() {
1189 Entry<K,V> e = next;
1190 if (e == null)
1191 throw new NoSuchElementException();
1192 if (modCount != expectedModCount)
1193 throw new ConcurrentModificationException();
1194 next = predecessor(e);
1195 lastReturned = e;
1196 return e;
1197 }
1198
1199 public void remove() {
1200 if (lastReturned == null)
1201 throw new IllegalStateException();
1202 if (modCount != expectedModCount)
1203 throw new ConcurrentModificationException();
1204 // deleted entries are replaced by their successors
1205 if (lastReturned.left != null && lastReturned.right != null)
1206 next = lastReturned;
1207 deleteEntry(lastReturned);
1208 expectedModCount = modCount;
1209 lastReturned = null;
1210 }
1211 }
1212
1213 final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {
1214 EntryIterator(Entry<K,V> first) {
1215 super(first);
1216 }
1217 public Map.Entry<K,V> next() {
1218 return nextEntry();
1219 }
1220 }
1221
1222 final class ValueIterator extends PrivateEntryIterator<V> {
1223 ValueIterator(Entry<K,V> first) {
1224 super(first);
1225 }
1226 public V next() {
1227 return nextEntry().value;
1228 }
1229 }
1230
1231 final class KeyIterator extends PrivateEntryIterator<K> {
1232 KeyIterator(Entry<K,V> first) {
1233 super(first);
1234 }
1235 public K next() {
1236 return nextEntry().key;
1237 }
1238 }
1239
1240 final class DescendingKeyIterator extends PrivateEntryIterator<K> {
1241 DescendingKeyIterator(Entry<K,V> first) {
1242 super(first);
1243 }
1244 public K next() {
1245 return prevEntry().key;
1246 }
1247 }
1248
1249 // Little utilities
1250
1251 /**
1252 * Compares two keys using the correct comparison method for this TreeMap.
1253 */
1254 @SuppressWarnings("unchecked")
1255 final int compare(Object k1, Object k2) {
1256 return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
1257 : comparator.compare((K)k1, (K)k2);
1258 }
1259
1260 /**
1261 * Test two values for equality. Differs from o1.equals(o2) only in
1262 * that it copes with {@code null} o1 properly.
1263 */
1264 static final boolean valEquals(Object o1, Object o2) {
1265 return (o1==null ? o2==null : o1.equals(o2));
1266 }
1267
1268 /**
1269 * Return SimpleImmutableEntry for entry, or null if null
1270 */
1271 static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
1272 return (e == null) ? null :
1273 new AbstractMap.SimpleImmutableEntry<>(e);
1274 }
1275
1276 /**
1277 * Return key for entry, or null if null
1278 */
1279 static <K,V> K keyOrNull(TreeMap.Entry<K,V> e) {
1280 return (e == null) ? null : e.key;
1281 }
1282
1283 /**
1284 * Returns the key corresponding to the specified Entry.
1285 * @throws NoSuchElementException if the Entry is null
1286 */
1287 static <K> K key(Entry<K,?> e) {
1288 if (e==null)
1289 throw new NoSuchElementException();
1290 return e.key;
1291 }
1292
1293
1294 // SubMaps
1295
1296 /**
1297 * Dummy value serving as unmatchable fence key for unbounded
1298 * SubMapIterators
1299 */
1300 private static final Object UNBOUNDED = new Object();
1301
1302 /**
1303 * @serial include
1304 */
1305 abstract static class NavigableSubMap<K,V> extends AbstractMap<K,V>
1306 implements NavigableMap<K,V>, java.io.Serializable {
1307 /**
1308 * The backing map.
1309 */
1310 final TreeMap<K,V> m;
1311
1312 /**
1313 * Endpoints are represented as triples (fromStart, lo,
1314 * loInclusive) and (toEnd, hi, hiInclusive). If fromStart is
1315 * true, then the low (absolute) bound is the start of the
1316 * backing map, and the other values are ignored. Otherwise,
1317 * if loInclusive is true, lo is the inclusive bound, else lo
1318 * is the exclusive bound. Similarly for the upper bound.
1319 */
1320 final K lo, hi;
1321 final boolean fromStart, toEnd;
1322 final boolean loInclusive, hiInclusive;
1323
1324 NavigableSubMap(TreeMap<K,V> m,
1325 boolean fromStart, K lo, boolean loInclusive,
1326 boolean toEnd, K hi, boolean hiInclusive) {
1327 if (!fromStart && !toEnd) {
1328 if (m.compare(lo, hi) > 0)
1329 throw new IllegalArgumentException("fromKey > toKey");
1330 } else {
1331 if (!fromStart) // type check
1332 m.compare(lo, lo);
1333 if (!toEnd)
1334 m.compare(hi, hi);
1335 }
1336
1337 this.m = m;
1338 this.fromStart = fromStart;
1339 this.lo = lo;
1340 this.loInclusive = loInclusive;
1341 this.toEnd = toEnd;
1342 this.hi = hi;
1343 this.hiInclusive = hiInclusive;
1344 }
1345
1346 // internal utilities
1347
1348 final boolean tooLow(Object key) {
1349 if (!fromStart) {
1350 int c = m.compare(key, lo);
1351 if (c < 0 || (c == 0 && !loInclusive))
1352 return true;
1353 }
1354 return false;
1355 }
1356
1357 final boolean tooHigh(Object key) {
1358 if (!toEnd) {
1359 int c = m.compare(key, hi);
1360 if (c > 0 || (c == 0 && !hiInclusive))
1361 return true;
1362 }
1363 return false;
1364 }
1365
1366 final boolean inRange(Object key) {
1367 return !tooLow(key) && !tooHigh(key);
1368 }
1369
1370 final boolean inClosedRange(Object key) {
1371 return (fromStart || m.compare(key, lo) >= 0)
1372 && (toEnd || m.compare(hi, key) >= 0);
1373 }
1374
1375 final boolean inRange(Object key, boolean inclusive) {
1376 return inclusive ? inRange(key) : inClosedRange(key);
1377 }
1378
1379 /*
1380 * Absolute versions of relation operations.
1381 * Subclasses map to these using like-named "sub"
1382 * versions that invert senses for descending maps
1383 */
1384
1385 final TreeMap.Entry<K,V> absLowest() {
1386 TreeMap.Entry<K,V> e =
1387 (fromStart ? m.getFirstEntry() :
1388 (loInclusive ? m.getCeilingEntry(lo) :
1389 m.getHigherEntry(lo)));
1390 return (e == null || tooHigh(e.key)) ? null : e;
1391 }
1392
1393 final TreeMap.Entry<K,V> absHighest() {
1394 TreeMap.Entry<K,V> e =
1395 (toEnd ? m.getLastEntry() :
1396 (hiInclusive ? m.getFloorEntry(hi) :
1397 m.getLowerEntry(hi)));
1398 return (e == null || tooLow(e.key)) ? null : e;
1399 }
1400
1401 final TreeMap.Entry<K,V> absCeiling(K key) {
1402 if (tooLow(key))
1403 return absLowest();
1404 TreeMap.Entry<K,V> e = m.getCeilingEntry(key);
1405 return (e == null || tooHigh(e.key)) ? null : e;
1406 }
1407
1408 final TreeMap.Entry<K,V> absHigher(K key) {
1409 if (tooLow(key))
1410 return absLowest();
1411 TreeMap.Entry<K,V> e = m.getHigherEntry(key);
1412 return (e == null || tooHigh(e.key)) ? null : e;
1413 }
1414
1415 final TreeMap.Entry<K,V> absFloor(K key) {
1416 if (tooHigh(key))
1417 return absHighest();
1418 TreeMap.Entry<K,V> e = m.getFloorEntry(key);
1419 return (e == null || tooLow(e.key)) ? null : e;
1420 }
1421
1422 final TreeMap.Entry<K,V> absLower(K key) {
1423 if (tooHigh(key))
1424 return absHighest();
1425 TreeMap.Entry<K,V> e = m.getLowerEntry(key);
1426 return (e == null || tooLow(e.key)) ? null : e;
1427 }
1428
1429 /** Returns the absolute high fence for ascending traversal */
1430 final TreeMap.Entry<K,V> absHighFence() {
1431 return (toEnd ? null : (hiInclusive ?
1432 m.getHigherEntry(hi) :
1433 m.getCeilingEntry(hi)));
1434 }
1435
1436 /** Return the absolute low fence for descending traversal */
1437 final TreeMap.Entry<K,V> absLowFence() {
1438 return (fromStart ? null : (loInclusive ?
1439 m.getLowerEntry(lo) :
1440 m.getFloorEntry(lo)));
1441 }
1442
1443 // Abstract methods defined in ascending vs descending classes
1444 // These relay to the appropriate absolute versions
1445
1446 abstract TreeMap.Entry<K,V> subLowest();
1447 abstract TreeMap.Entry<K,V> subHighest();
1448 abstract TreeMap.Entry<K,V> subCeiling(K key);
1449 abstract TreeMap.Entry<K,V> subHigher(K key);
1450 abstract TreeMap.Entry<K,V> subFloor(K key);
1451 abstract TreeMap.Entry<K,V> subLower(K key);
1452
1453 /** Returns ascending iterator from the perspective of this submap */
1454 abstract Iterator<K> keyIterator();
1455
1456 abstract Spliterator<K> keySpliterator();
1457
1458 /** Returns descending iterator from the perspective of this submap */
1459 abstract Iterator<K> descendingKeyIterator();
1460
1461 // public methods
1462
1463 public boolean isEmpty() {
1464 return (fromStart && toEnd) ? m.isEmpty() : entrySet().isEmpty();
1465 }
1466
1467 public int size() {
1468 return (fromStart && toEnd) ? m.size() : entrySet().size();
1469 }
1470
1471 public final boolean containsKey(Object key) {
1472 return inRange(key) && m.containsKey(key);
1473 }
1474
1475 public final V put(K key, V value) {
1476 if (!inRange(key))
1477 throw new IllegalArgumentException("key out of range");
1478 return m.put(key, value);
1479 }
1480
1481 public final V get(Object key) {
1482 return !inRange(key) ? null : m.get(key);
1483 }
1484
1485 public final V remove(Object key) {
1486 return !inRange(key) ? null : m.remove(key);
1487 }
1488
1489 public final Map.Entry<K,V> ceilingEntry(K key) {
1490 return exportEntry(subCeiling(key));
1491 }
1492
1493 public final K ceilingKey(K key) {
1494 return keyOrNull(subCeiling(key));
1495 }
1496
1497 public final Map.Entry<K,V> higherEntry(K key) {
1498 return exportEntry(subHigher(key));
1499 }
1500
1501 public final K higherKey(K key) {
1502 return keyOrNull(subHigher(key));
1503 }
1504
1505 public final Map.Entry<K,V> floorEntry(K key) {
1506 return exportEntry(subFloor(key));
1507 }
1508
1509 public final K floorKey(K key) {
1510 return keyOrNull(subFloor(key));
1511 }
1512
1513 public final Map.Entry<K,V> lowerEntry(K key) {
1514 return exportEntry(subLower(key));
1515 }
1516
1517 public final K lowerKey(K key) {
1518 return keyOrNull(subLower(key));
1519 }
1520
1521 public final K firstKey() {
1522 return key(subLowest());
1523 }
1524
1525 public final K lastKey() {
1526 return key(subHighest());
1527 }
1528
1529 public final Map.Entry<K,V> firstEntry() {
1530 return exportEntry(subLowest());
1531 }
1532
1533 public final Map.Entry<K,V> lastEntry() {
1534 return exportEntry(subHighest());
1535 }
1536
1537 public final Map.Entry<K,V> pollFirstEntry() {
1538 TreeMap.Entry<K,V> e = subLowest();
1539 Map.Entry<K,V> result = exportEntry(e);
1540 if (e != null)
1541 m.deleteEntry(e);
1542 return result;
1543 }
1544
1545 public final Map.Entry<K,V> pollLastEntry() {
1546 TreeMap.Entry<K,V> e = subHighest();
1547 Map.Entry<K,V> result = exportEntry(e);
1548 if (e != null)
1549 m.deleteEntry(e);
1550 return result;
1551 }
1552
1553 // Views
1554 transient NavigableMap<K,V> descendingMapView = null;
1555 transient EntrySetView entrySetView = null;
1556 transient KeySet<K> navigableKeySetView = null;
1557
1558 public final NavigableSet<K> navigableKeySet() {
1559 KeySet<K> nksv = navigableKeySetView;
1560 return (nksv != null) ? nksv :
1561 (navigableKeySetView = new TreeMap.KeySet<>(this));
1562 }
1563
1564 public final Set<K> keySet() {
1565 return navigableKeySet();
1566 }
1567
1568 public NavigableSet<K> descendingKeySet() {
1569 return descendingMap().navigableKeySet();
1570 }
1571
1572 public final SortedMap<K,V> subMap(K fromKey, K toKey) {
1573 return subMap(fromKey, true, toKey, false);
1574 }
1575
1576 public final SortedMap<K,V> headMap(K toKey) {
1577 return headMap(toKey, false);
1578 }
1579
1580 public final SortedMap<K,V> tailMap(K fromKey) {
1581 return tailMap(fromKey, true);
1582 }
1583
1584 // View classes
1585
1586 abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
1587 private transient int size = -1, sizeModCount;
1588
1589 public int size() {
1590 if (fromStart && toEnd)
1591 return m.size();
1592 if (size == -1 || sizeModCount != m.modCount) {
1593 sizeModCount = m.modCount;
1594 size = 0;
1595 Iterator<?> i = iterator();
1596 while (i.hasNext()) {
1597 size++;
1598 i.next();
1599 }
1600 }
1601 return size;
1602 }
1603
1604 public boolean isEmpty() {
1605 TreeMap.Entry<K,V> n = absLowest();
1606 return n == null || tooHigh(n.key);
1607 }
1608
1609 public boolean contains(Object o) {
1610 if (!(o instanceof Map.Entry))
1611 return false;
1612 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1613 Object key = entry.getKey();
1614 if (!inRange(key))
1615 return false;
1616 TreeMap.Entry<?,?> node = m.getEntry(key);
1617 return node != null &&
1618 valEquals(node.getValue(), entry.getValue());
1619 }
1620
1621 public boolean remove(Object o) {
1622 if (!(o instanceof Map.Entry))
1623 return false;
1624 Map.Entry<?,?> entry = (Map.Entry<?,?>) o;
1625 Object key = entry.getKey();
1626 if (!inRange(key))
1627 return false;
1628 TreeMap.Entry<K,V> node = m.getEntry(key);
1629 if (node!=null && valEquals(node.getValue(),
1630 entry.getValue())) {
1631 m.deleteEntry(node);
1632 return true;
1633 }
1634 return false;
1635 }
1636 }
1637
1638 /**
1639 * Iterators for SubMaps
1640 */
1641 abstract class SubMapIterator<T> implements Iterator<T> {
1642 TreeMap.Entry<K,V> lastReturned;
1643 TreeMap.Entry<K,V> next;
1644 final Object fenceKey;
1645 int expectedModCount;
1646
1647 SubMapIterator(TreeMap.Entry<K,V> first,
1648 TreeMap.Entry<K,V> fence) {
1649 expectedModCount = m.modCount;
1650 lastReturned = null;
1651 next = first;
1652 fenceKey = fence == null ? UNBOUNDED : fence.key;
1653 }
1654
1655 public final boolean hasNext() {
1656 return next != null && next.key != fenceKey;
1657 }
1658
1659 final TreeMap.Entry<K,V> nextEntry() {
1660 TreeMap.Entry<K,V> e = next;
1661 if (e == null || e.key == fenceKey)
1662 throw new NoSuchElementException();
1663 if (m.modCount != expectedModCount)
1664 throw new ConcurrentModificationException();
1665 next = successor(e);
1666 lastReturned = e;
1667 return e;
1668 }
1669
1670 final TreeMap.Entry<K,V> prevEntry() {
1671 TreeMap.Entry<K,V> e = next;
1672 if (e == null || e.key == fenceKey)
1673 throw new NoSuchElementException();
1674 if (m.modCount != expectedModCount)
1675 throw new ConcurrentModificationException();
1676 next = predecessor(e);
1677 lastReturned = e;
1678 return e;
1679 }
1680
1681 final void removeAscending() {
1682 if (lastReturned == null)
1683 throw new IllegalStateException();
1684 if (m.modCount != expectedModCount)
1685 throw new ConcurrentModificationException();
1686 // deleted entries are replaced by their successors
1687 if (lastReturned.left != null && lastReturned.right != null)
1688 next = lastReturned;
1689 m.deleteEntry(lastReturned);
1690 lastReturned = null;
1691 expectedModCount = m.modCount;
1692 }
1693
1694 final void removeDescending() {
1695 if (lastReturned == null)
1696 throw new IllegalStateException();
1697 if (m.modCount != expectedModCount)
1698 throw new ConcurrentModificationException();
1699 m.deleteEntry(lastReturned);
1700 lastReturned = null;
1701 expectedModCount = m.modCount;
1702 }
1703
1704 }
1705
1706 final class SubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1707 SubMapEntryIterator(TreeMap.Entry<K,V> first,
1708 TreeMap.Entry<K,V> fence) {
1709 super(first, fence);
1710 }
1711 public Map.Entry<K,V> next() {
1712 return nextEntry();
1713 }
1714 public void remove() {
1715 removeAscending();
1716 }
1717 }
1718
1719 final class DescendingSubMapEntryIterator extends SubMapIterator<Map.Entry<K,V>> {
1720 DescendingSubMapEntryIterator(TreeMap.Entry<K,V> last,
1721 TreeMap.Entry<K,V> fence) {
1722 super(last, fence);
1723 }
1724
1725 public Map.Entry<K,V> next() {
1726 return prevEntry();
1727 }
1728 public void remove() {
1729 removeDescending();
1730 }
1731 }
1732
1733 // Implement minimal Spliterator as KeySpliterator backup
1734 final class SubMapKeyIterator extends SubMapIterator<K>
1735 implements Spliterator<K> {
1736 SubMapKeyIterator(TreeMap.Entry<K,V> first,
1737 TreeMap.Entry<K,V> fence) {
1738 super(first, fence);
1739 }
1740 public K next() {
1741 return nextEntry().key;
1742 }
1743 public void remove() {
1744 removeAscending();
1745 }
1746 public Spliterator<K> trySplit() {
1747 return null;
1748 }
1749 public void forEachRemaining(Consumer<? super K> action) {
1750 while (hasNext())
1751 action.accept(next());
1752 }
1753 public boolean tryAdvance(Consumer<? super K> action) {
1754 if (hasNext()) {
1755 action.accept(next());
1756 return true;
1757 }
1758 return false;
1759 }
1760 public long estimateSize() {
1761 return Long.MAX_VALUE;
1762 }
1763 public int characteristics() {
1764 return Spliterator.DISTINCT | Spliterator.ORDERED |
1765 Spliterator.SORTED;
1766 }
1767 public final Comparator<? super K> getComparator() {
1768 return NavigableSubMap.this.comparator();
1769 }
1770 }
1771
1772 final class DescendingSubMapKeyIterator extends SubMapIterator<K>
1773 implements Spliterator<K> {
1774 DescendingSubMapKeyIterator(TreeMap.Entry<K,V> last,
1775 TreeMap.Entry<K,V> fence) {
1776 super(last, fence);
1777 }
1778 public K next() {
1779 return prevEntry().key;
1780 }
1781 public void remove() {
1782 removeDescending();
1783 }
1784 public Spliterator<K> trySplit() {
1785 return null;
1786 }
1787 public void forEachRemaining(Consumer<? super K> action) {
1788 while (hasNext())
1789 action.accept(next());
1790 }
1791 public boolean tryAdvance(Consumer<? super K> action) {
1792 if (hasNext()) {
1793 action.accept(next());
1794 return true;
1795 }
1796 return false;
1797 }
1798 public long estimateSize() {
1799 return Long.MAX_VALUE;
1800 }
1801 public int characteristics() {
1802 return Spliterator.DISTINCT | Spliterator.ORDERED;
1803 }
1804 }
1805 }
1806
1807 /**
1808 * @serial include
1809 */
1810 static final class AscendingSubMap<K,V> extends NavigableSubMap<K,V> {
1811 private static final long serialVersionUID = 912986545866124060L;
1812
1813 AscendingSubMap(TreeMap<K,V> m,
1814 boolean fromStart, K lo, boolean loInclusive,
1815 boolean toEnd, K hi, boolean hiInclusive) {
1816 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1817 }
1818
1819 public Comparator<? super K> comparator() {
1820 return m.comparator();
1821 }
1822
1823 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1824 K toKey, boolean toInclusive) {
1825 if (!inRange(fromKey, fromInclusive))
1826 throw new IllegalArgumentException("fromKey out of range");
1827 if (!inRange(toKey, toInclusive))
1828 throw new IllegalArgumentException("toKey out of range");
1829 return new AscendingSubMap<>(m,
1830 false, fromKey, fromInclusive,
1831 false, toKey, toInclusive);
1832 }
1833
1834 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1835 if (!inRange(toKey, inclusive))
1836 throw new IllegalArgumentException("toKey out of range");
1837 return new AscendingSubMap<>(m,
1838 fromStart, lo, loInclusive,
1839 false, toKey, inclusive);
1840 }
1841
1842 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1843 if (!inRange(fromKey, inclusive))
1844 throw new IllegalArgumentException("fromKey out of range");
1845 return new AscendingSubMap<>(m,
1846 false, fromKey, inclusive,
1847 toEnd, hi, hiInclusive);
1848 }
1849
1850 public NavigableMap<K,V> descendingMap() {
1851 NavigableMap<K,V> mv = descendingMapView;
1852 return (mv != null) ? mv :
1853 (descendingMapView =
1854 new DescendingSubMap<>(m,
1855 fromStart, lo, loInclusive,
1856 toEnd, hi, hiInclusive));
1857 }
1858
1859 Iterator<K> keyIterator() {
1860 return new SubMapKeyIterator(absLowest(), absHighFence());
1861 }
1862
1863 Spliterator<K> keySpliterator() {
1864 return new SubMapKeyIterator(absLowest(), absHighFence());
1865 }
1866
1867 Iterator<K> descendingKeyIterator() {
1868 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1869 }
1870
1871 final class AscendingEntrySetView extends EntrySetView {
1872 public Iterator<Map.Entry<K,V>> iterator() {
1873 return new SubMapEntryIterator(absLowest(), absHighFence());
1874 }
1875 }
1876
1877 public Set<Map.Entry<K,V>> entrySet() {
1878 EntrySetView es = entrySetView;
1879 return (es != null) ? es : (entrySetView = new AscendingEntrySetView());
1880 }
1881
1882 TreeMap.Entry<K,V> subLowest() { return absLowest(); }
1883 TreeMap.Entry<K,V> subHighest() { return absHighest(); }
1884 TreeMap.Entry<K,V> subCeiling(K key) { return absCeiling(key); }
1885 TreeMap.Entry<K,V> subHigher(K key) { return absHigher(key); }
1886 TreeMap.Entry<K,V> subFloor(K key) { return absFloor(key); }
1887 TreeMap.Entry<K,V> subLower(K key) { return absLower(key); }
1888 }
1889
1890 /**
1891 * @serial include
1892 */
1893 static final class DescendingSubMap<K,V> extends NavigableSubMap<K,V> {
1894 private static final long serialVersionUID = 912986545866120460L;
1895 DescendingSubMap(TreeMap<K,V> m,
1896 boolean fromStart, K lo, boolean loInclusive,
1897 boolean toEnd, K hi, boolean hiInclusive) {
1898 super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
1899 }
1900
1901 private final Comparator<? super K> reverseComparator =
1902 Collections.reverseOrder(m.comparator);
1903
1904 public Comparator<? super K> comparator() {
1905 return reverseComparator;
1906 }
1907
1908 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1909 K toKey, boolean toInclusive) {
1910 if (!inRange(fromKey, fromInclusive))
1911 throw new IllegalArgumentException("fromKey out of range");
1912 if (!inRange(toKey, toInclusive))
1913 throw new IllegalArgumentException("toKey out of range");
1914 return new DescendingSubMap<>(m,
1915 false, toKey, toInclusive,
1916 false, fromKey, fromInclusive);
1917 }
1918
1919 public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
1920 if (!inRange(toKey, inclusive))
1921 throw new IllegalArgumentException("toKey out of range");
1922 return new DescendingSubMap<>(m,
1923 false, toKey, inclusive,
1924 toEnd, hi, hiInclusive);
1925 }
1926
1927 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive) {
1928 if (!inRange(fromKey, inclusive))
1929 throw new IllegalArgumentException("fromKey out of range");
1930 return new DescendingSubMap<>(m,
1931 fromStart, lo, loInclusive,
1932 false, fromKey, inclusive);
1933 }
1934
1935 public NavigableMap<K,V> descendingMap() {
1936 NavigableMap<K,V> mv = descendingMapView;
1937 return (mv != null) ? mv :
1938 (descendingMapView =
1939 new AscendingSubMap<>(m,
1940 fromStart, lo, loInclusive,
1941 toEnd, hi, hiInclusive));
1942 }
1943
1944 Iterator<K> keyIterator() {
1945 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1946 }
1947
1948 Spliterator<K> keySpliterator() {
1949 return new DescendingSubMapKeyIterator(absHighest(), absLowFence());
1950 }
1951
1952 Iterator<K> descendingKeyIterator() {
1953 return new SubMapKeyIterator(absLowest(), absHighFence());
1954 }
1955
1956 final class DescendingEntrySetView extends EntrySetView {
1957 public Iterator<Map.Entry<K,V>> iterator() {
1958 return new DescendingSubMapEntryIterator(absHighest(), absLowFence());
1959 }
1960 }
1961
1962 public Set<Map.Entry<K,V>> entrySet() {
1963 EntrySetView es = entrySetView;
1964 return (es != null) ? es : (entrySetView = new DescendingEntrySetView());
1965 }
1966
1967 TreeMap.Entry<K,V> subLowest() { return absHighest(); }
1968 TreeMap.Entry<K,V> subHighest() { return absLowest(); }
1969 TreeMap.Entry<K,V> subCeiling(K key) { return absFloor(key); }
1970 TreeMap.Entry<K,V> subHigher(K key) { return absLower(key); }
1971 TreeMap.Entry<K,V> subFloor(K key) { return absCeiling(key); }
1972 TreeMap.Entry<K,V> subLower(K key) { return absHigher(key); }
1973 }
1974
1975 /**
1976 * This class exists solely for the sake of serialization
1977 * compatibility with previous releases of TreeMap that did not
1978 * support NavigableMap. It translates an old-version SubMap into
1979 * a new-version AscendingSubMap. This class is never otherwise
1980 * used.
1981 *
1982 * @serial include
1983 */
1984 private class SubMap extends AbstractMap<K,V>
1985 implements SortedMap<K,V>, java.io.Serializable {
1986 private static final long serialVersionUID = -6520786458950516097L;
1987 private boolean fromStart = false, toEnd = false;
1988 private K fromKey, toKey;
1989 private Object readResolve() {
1990 return new AscendingSubMap<>(TreeMap.this,
1991 fromStart, fromKey, true,
1992 toEnd, toKey, false);
1993 }
1994 public Set<Map.Entry<K,V>> entrySet() { throw new InternalError(); }
1995 public K lastKey() { throw new InternalError(); }
1996 public K firstKey() { throw new InternalError(); }
1997 public SortedMap<K,V> subMap(K fromKey, K toKey) { throw new InternalError(); }
1998 public SortedMap<K,V> headMap(K toKey) { throw new InternalError(); }
1999 public SortedMap<K,V> tailMap(K fromKey) { throw new InternalError(); }
2000 public Comparator<? super K> comparator() { throw new InternalError(); }
2001 }
2002
2003
2004 // Red-black mechanics
2005
2006 private static final boolean RED = false;
2007 private static final boolean BLACK = true;
2008
2009 /**
2010 * Node in the Tree. Doubles as a means to pass key-value pairs back to
2011 * user (see Map.Entry).
2012 */
2013
2014 static final class Entry<K,V> implements Map.Entry<K,V> {
2015 K key;
2016 V value;
2017 Entry<K,V> left = null;
2018 Entry<K,V> right = null;
2019 Entry<K,V> parent;
2020 boolean color = BLACK;
2021
2022 /**
2023 * Make a new cell with given key, value, and parent, and with
2024 * {@code null} child links, and BLACK color.
2025 */
2026 Entry(K key, V value, Entry<K,V> parent) {
2027 this.key = key;
2028 this.value = value;
2029 this.parent = parent;
2030 }
2031
2032 /**
2033 * Returns the key.
2034 *
2035 * @return the key
2036 */
2037 public K getKey() {
2038 return key;
2039 }
2040
2041 /**
2042 * Returns the value associated with the key.
2043 *
2044 * @return the value associated with the key
2045 */
2046 public V getValue() {
2047 return value;
2048 }
2049
2050 /**
2051 * Replaces the value currently associated with the key with the given
2052 * value.
2053 *
2054 * @return the value associated with the key before this method was
2055 * called
2056 */
2057 public V setValue(V value) {
2058 V oldValue = this.value;
2059 this.value = value;
2060 return oldValue;
2061 }
2062
2063 public boolean equals(Object o) {
2064 if (!(o instanceof Map.Entry))
2065 return false;
2066 Map.Entry<?,?> e = (Map.Entry<?,?>)o;
2067
2068 return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
2069 }
2070
2071 public int hashCode() {
2072 int keyHash = (key==null ? 0 : key.hashCode());
2073 int valueHash = (value==null ? 0 : value.hashCode());
2074 return keyHash ^ valueHash;
2075 }
2076
2077 public String toString() {
2078 return key + "=" + value;
2079 }
2080 }
2081
2082 /**
2083 * Returns the first Entry in the TreeMap (according to the TreeMap's
2084 * key-sort function). Returns null if the TreeMap is empty.
2085 */
2086 final Entry<K,V> getFirstEntry() {
2087 Entry<K,V> p = root;
2088 if (p != null)
2089 while (p.left != null)
2090 p = p.left;
2091 return p;
2092 }
2093
2094 /**
2095 * Returns the last Entry in the TreeMap (according to the TreeMap's
2096 * key-sort function). Returns null if the TreeMap is empty.
2097 */
2098 final Entry<K,V> getLastEntry() {
2099 Entry<K,V> p = root;
2100 if (p != null)
2101 while (p.right != null)
2102 p = p.right;
2103 return p;
2104 }
2105
2106 /**
2107 * Returns the successor of the specified Entry, or null if no such.
2108 */
2109 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
2110 if (t == null)
2111 return null;
2112 else if (t.right != null) {
2113 Entry<K,V> p = t.right;
2114 while (p.left != null)
2115 p = p.left;
2116 return p;
2117 } else {
2118 Entry<K,V> p = t.parent;
2119 Entry<K,V> ch = t;
2120 while (p != null && ch == p.right) {
2121 ch = p;
2122 p = p.parent;
2123 }
2124 return p;
2125 }
2126 }
2127
2128 /**
2129 * Returns the predecessor of the specified Entry, or null if no such.
2130 */
2131 static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
2132 if (t == null)
2133 return null;
2134 else if (t.left != null) {
2135 Entry<K,V> p = t.left;
2136 while (p.right != null)
2137 p = p.right;
2138 return p;
2139 } else {
2140 Entry<K,V> p = t.parent;
2141 Entry<K,V> ch = t;
2142 while (p != null && ch == p.left) {
2143 ch = p;
2144 p = p.parent;
2145 }
2146 return p;
2147 }
2148 }
2149
2150 /**
2151 * Balancing operations.
2152 *
2153 * Implementations of rebalancings during insertion and deletion are
2154 * slightly different than the CLR version. Rather than using dummy
2155 * nilnodes, we use a set of accessors that deal properly with null. They
2156 * are used to avoid messiness surrounding nullness checks in the main
2157 * algorithms.
2158 */
2159
2160 private static <K,V> boolean colorOf(Entry<K,V> p) {
2161 return (p == null ? BLACK : p.color);
2162 }
2163
2164 private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
2165 return (p == null ? null: p.parent);
2166 }
2167
2168 private static <K,V> void setColor(Entry<K,V> p, boolean c) {
2169 if (p != null)
2170 p.color = c;
2171 }
2172
2173 private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
2174 return (p == null) ? null: p.left;
2175 }
2176
2177 private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
2178 return (p == null) ? null: p.right;
2179 }
2180
2181 /** From CLR */
2182 private void rotateLeft(Entry<K,V> p) {
2183 if (p != null) {
2184 Entry<K,V> r = p.right;
2185 p.right = r.left;
2186 if (r.left != null)
2187 r.left.parent = p;
2188 r.parent = p.parent;
2189 if (p.parent == null)
2190 root = r;
2191 else if (p.parent.left == p)
2192 p.parent.left = r;
2193 else
2194 p.parent.right = r;
2195 r.left = p;
2196 p.parent = r;
2197 }
2198 }
2199
2200 /** From CLR */
2201 private void rotateRight(Entry<K,V> p) {
2202 if (p != null) {
2203 Entry<K,V> l = p.left;
2204 p.left = l.right;
2205 if (l.right != null) l.right.parent = p;
2206 l.parent = p.parent;
2207 if (p.parent == null)
2208 root = l;
2209 else if (p.parent.right == p)
2210 p.parent.right = l;
2211 else p.parent.left = l;
2212 l.right = p;
2213 p.parent = l;
2214 }
2215 }
2216
2217 /** From CLR */
2218 private void fixAfterInsertion(Entry<K,V> x) {
2219 x.color = RED;
2220
2221 while (x != null && x != root && x.parent.color == RED) {
2222 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
2223 Entry<K,V> y = rightOf(parentOf(parentOf(x)));
2224 if (colorOf(y) == RED) {
2225 setColor(parentOf(x), BLACK);
2226 setColor(y, BLACK);
2227 setColor(parentOf(parentOf(x)), RED);
2228 x = parentOf(parentOf(x));
2229 } else {
2230 if (x == rightOf(parentOf(x))) {
2231 x = parentOf(x);
2232 rotateLeft(x);
2233 }
2234 setColor(parentOf(x), BLACK);
2235 setColor(parentOf(parentOf(x)), RED);
2236 rotateRight(parentOf(parentOf(x)));
2237 }
2238 } else {
2239 Entry<K,V> y = leftOf(parentOf(parentOf(x)));
2240 if (colorOf(y) == RED) {
2241 setColor(parentOf(x), BLACK);
2242 setColor(y, BLACK);
2243 setColor(parentOf(parentOf(x)), RED);
2244 x = parentOf(parentOf(x));
2245 } else {
2246 if (x == leftOf(parentOf(x))) {
2247 x = parentOf(x);
2248 rotateRight(x);
2249 }
2250 setColor(parentOf(x), BLACK);
2251 setColor(parentOf(parentOf(x)), RED);
2252 rotateLeft(parentOf(parentOf(x)));
2253 }
2254 }
2255 }
2256 root.color = BLACK;
2257 }
2258
2259 /**
2260 * Delete node p, and then rebalance the tree.
2261 */
2262 private void deleteEntry(Entry<K,V> p) {
2263 modCount++;
2264 size--;
2265
2266 // If strictly internal, copy successor's element to p and then make p
2267 // point to successor.
2268 if (p.left != null && p.right != null) {
2269 Entry<K,V> s = successor(p);
2270 p.key = s.key;
2271 p.value = s.value;
2272 p = s;
2273 } // p has 2 children
2274
2275 // Start fixup at replacement node, if it exists.
2276 Entry<K,V> replacement = (p.left != null ? p.left : p.right);
2277
2278 if (replacement != null) {
2279 // Link replacement to parent
2280 replacement.parent = p.parent;
2281 if (p.parent == null)
2282 root = replacement;
2283 else if (p == p.parent.left)
2284 p.parent.left = replacement;
2285 else
2286 p.parent.right = replacement;
2287
2288 // Null out links so they are OK to use by fixAfterDeletion.
2289 p.left = p.right = p.parent = null;
2290
2291 // Fix replacement
2292 if (p.color == BLACK)
2293 fixAfterDeletion(replacement);
2294 } else if (p.parent == null) { // return if we are the only node.
2295 root = null;
2296 } else { // No children. Use self as phantom replacement and unlink.
2297 if (p.color == BLACK)
2298 fixAfterDeletion(p);
2299
2300 if (p.parent != null) {
2301 if (p == p.parent.left)
2302 p.parent.left = null;
2303 else if (p == p.parent.right)
2304 p.parent.right = null;
2305 p.parent = null;
2306 }
2307 }
2308 }
2309
2310 /** From CLR */
2311 private void fixAfterDeletion(Entry<K,V> x) {
2312 while (x != root && colorOf(x) == BLACK) {
2313 if (x == leftOf(parentOf(x))) {
2314 Entry<K,V> sib = rightOf(parentOf(x));
2315
2316 if (colorOf(sib) == RED) {
2317 setColor(sib, BLACK);
2318 setColor(parentOf(x), RED);
2319 rotateLeft(parentOf(x));
2320 sib = rightOf(parentOf(x));
2321 }
2322
2323 if (colorOf(leftOf(sib)) == BLACK &&
2324 colorOf(rightOf(sib)) == BLACK) {
2325 setColor(sib, RED);
2326 x = parentOf(x);
2327 } else {
2328 if (colorOf(rightOf(sib)) == BLACK) {
2329 setColor(leftOf(sib), BLACK);
2330 setColor(sib, RED);
2331 rotateRight(sib);
2332 sib = rightOf(parentOf(x));
2333 }
2334 setColor(sib, colorOf(parentOf(x)));
2335 setColor(parentOf(x), BLACK);
2336 setColor(rightOf(sib), BLACK);
2337 rotateLeft(parentOf(x));
2338 x = root;
2339 }
2340 } else { // symmetric
2341 Entry<K,V> sib = leftOf(parentOf(x));
2342
2343 if (colorOf(sib) == RED) {
2344 setColor(sib, BLACK);
2345 setColor(parentOf(x), RED);
2346 rotateRight(parentOf(x));
2347 sib = leftOf(parentOf(x));
2348 }
2349
2350 if (colorOf(rightOf(sib)) == BLACK &&
2351 colorOf(leftOf(sib)) == BLACK) {
2352 setColor(sib, RED);
2353 x = parentOf(x);
2354 } else {
2355 if (colorOf(leftOf(sib)) == BLACK) {
2356 setColor(rightOf(sib), BLACK);
2357 setColor(sib, RED);
2358 rotateLeft(sib);
2359 sib = leftOf(parentOf(x));
2360 }
2361 setColor(sib, colorOf(parentOf(x)));
2362 setColor(parentOf(x), BLACK);
2363 setColor(leftOf(sib), BLACK);
2364 rotateRight(parentOf(x));
2365 x = root;
2366 }
2367 }
2368 }
2369
2370 setColor(x, BLACK);
2371 }
2372
2373 private static final long serialVersionUID = 919286545866124006L;
2374
2375 /**
2376 * Save the state of the {@code TreeMap} instance to a stream (i.e.,
2377 * serialize it).
2378 *
2379 * @serialData The <em>size</em> of the TreeMap (the number of key-value
2380 * mappings) is emitted (int), followed by the key (Object)
2381 * and value (Object) for each key-value mapping represented
2382 * by the TreeMap. The key-value mappings are emitted in
2383 * key-order (as determined by the TreeMap's Comparator,
2384 * or by the keys' natural ordering if the TreeMap has no
2385 * Comparator).
2386 */
2387 private void writeObject(java.io.ObjectOutputStream s)
2388 throws java.io.IOException {
2389 // Write out the Comparator and any hidden stuff
2390 s.defaultWriteObject();
2391
2392 // Write out size (number of Mappings)
2393 s.writeInt(size);
2394
2395 // Write out keys and values (alternating)
2396 for (Iterator<Map.Entry<K,V>> i = entrySet().iterator(); i.hasNext(); ) {
2397 Map.Entry<K,V> e = i.next();
2398 s.writeObject(e.getKey());
2399 s.writeObject(e.getValue());
2400 }
2401 }
2402
2403 /**
2404 * Reconstitute the {@code TreeMap} instance from a stream (i.e.,
2405 * deserialize it).
2406 */
2407 private void readObject(final java.io.ObjectInputStream s)
2408 throws java.io.IOException, ClassNotFoundException {
2409 // Read in the Comparator and any hidden stuff
2410 s.defaultReadObject();
2411
2412 // Read in size
2413 int size = s.readInt();
2414
2415 buildFromSorted(size, null, s, null);
2416 }
2417
2418 /** Intended to be called only from TreeSet.readObject */
2419 void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
2420 throws java.io.IOException, ClassNotFoundException {
2421 buildFromSorted(size, null, s, defaultVal);
2422 }
2423
2424 /** Intended to be called only from TreeSet.addAll */
2425 void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
2426 try {
2427 buildFromSorted(set.size(), set.iterator(), null, defaultVal);
2428 } catch (java.io.IOException cannotHappen) {
2429 } catch (ClassNotFoundException cannotHappen) {
2430 }
2431 }
2432
2433
2434 /**
2435 * Linear time tree building algorithm from sorted data. Can accept keys
2436 * and/or values from iterator or stream. This leads to too many
2437 * parameters, but seems better than alternatives. The four formats
2438 * that this method accepts are:
2439 *
2440 * 1) An iterator of Map.Entries. (it != null, defaultVal == null).
2441 * 2) An iterator of keys. (it != null, defaultVal != null).
2442 * 3) A stream of alternating serialized keys and values.
2443 * (it == null, defaultVal == null).
2444 * 4) A stream of serialized keys. (it == null, defaultVal != null).
2445 *
2446 * It is assumed that the comparator of the TreeMap is already set prior
2447 * to calling this method.
2448 *
2449 * @param size the number of keys (or key-value pairs) to be read from
2450 * the iterator or stream
2451 * @param it If non-null, new entries are created from entries
2452 * or keys read from this iterator.
2453 * @param str If non-null, new entries are created from keys and
2454 * possibly values read from this stream in serialized form.
2455 * Exactly one of it and str should be non-null.
2456 * @param defaultVal if non-null, this default value is used for
2457 * each value in the map. If null, each value is read from
2458 * iterator or stream, as described above.
2459 * @throws java.io.IOException propagated from stream reads. This cannot
2460 * occur if str is null.
2461 * @throws ClassNotFoundException propagated from readObject.
2462 * This cannot occur if str is null.
2463 */
2464 private void buildFromSorted(int size, Iterator<?> it,
2465 java.io.ObjectInputStream str,
2466 V defaultVal)
2467 throws java.io.IOException, ClassNotFoundException {
2468 this.size = size;
2469 root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
2470 it, str, defaultVal);
2471 }
2472
2473 /**
2474 * Recursive "helper method" that does the real work of the
2475 * previous method. Identically named parameters have
2476 * identical definitions. Additional parameters are documented below.
2477 * It is assumed that the comparator and size fields of the TreeMap are
2478 * already set prior to calling this method. (It ignores both fields.)
2479 *
2480 * @param level the current level of tree. Initial call should be 0.
2481 * @param lo the first element index of this subtree. Initial should be 0.
2482 * @param hi the last element index of this subtree. Initial should be
2483 * size-1.
2484 * @param redLevel the level at which nodes should be red.
2485 * Must be equal to computeRedLevel for tree of this size.
2486 */
2487 @SuppressWarnings("unchecked")
2488 private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
2489 int redLevel,
2490 Iterator<?> it,
2491 java.io.ObjectInputStream str,
2492 V defaultVal)
2493 throws java.io.IOException, ClassNotFoundException {
2494 /*
2495 * Strategy: The root is the middlemost element. To get to it, we
2496 * have to first recursively construct the entire left subtree,
2497 * so as to grab all of its elements. We can then proceed with right
2498 * subtree.
2499 *
2500 * The lo and hi arguments are the minimum and maximum
2501 * indices to pull out of the iterator or stream for current subtree.
2502 * They are not actually indexed, we just proceed sequentially,
2503 * ensuring that items are extracted in corresponding order.
2504 */
2505
2506 if (hi < lo) return null;
2507
2508 int mid = (lo + hi) >>> 1;
2509
2510 Entry<K,V> left = null;
2511 if (lo < mid)
2512 left = buildFromSorted(level+1, lo, mid - 1, redLevel,
2513 it, str, defaultVal);
2514
2515 // extract key and/or value from iterator or stream
2516 K key;
2517 V value;
2518 if (it != null) {
2519 if (defaultVal==null) {
2520 Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
2521 key = (K)entry.getKey();
2522 value = (V)entry.getValue();
2523 } else {
2524 key = (K)it.next();
2525 value = defaultVal;
2526 }
2527 } else { // use stream
2528 key = (K) str.readObject();
2529 value = (defaultVal != null ? defaultVal : (V) str.readObject());
2530 }
2531
2532 Entry<K,V> middle = new Entry<>(key, value, null);
2533
2534 // color nodes in non-full bottommost level red
2535 if (level == redLevel)
2536 middle.color = RED;
2537
2538 if (left != null) {
2539 middle.left = left;
2540 left.parent = middle;
2541 }
2542
2543 if (mid < hi) {
2544 Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
2545 it, str, defaultVal);
2546 middle.right = right;
2547 right.parent = middle;
2548 }
2549
2550 return middle;
2551 }
2552
2553 /**
2554 * Find the level down to which to assign all nodes BLACK. This is the
2555 * last `full' level of the complete binary tree produced by
2556 * buildTree. The remaining nodes are colored RED. (This makes a `nice'
2557 * set of color assignments wrt future insertions.) This level number is
2558 * computed by finding the number of splits needed to reach the zeroeth
2559 * node. (The answer is ~lg(N), but in any case must be computed by same
2560 * quick O(lg(N)) loop.)
2561 */
2562 private static int computeRedLevel(int sz) {
2563 int level = 0;
2564 for (int m = sz - 1; m >= 0; m = m / 2 - 1)
2565 level++;
2566 return level;
2567 }
2568
2569 /**
2570 * Currently, we support Spliterator-based versions only for the
2571 * full map, in either plain of descending form, otherwise relying
2572 * on defaults because size estimation for submaps would dominate
2573 * costs. The type tests needed to check these for key views are
2574 * not very nice but avoid disrupting existing class
2575 * structures. Callers must use plain default spliterators if this
2576 * returns null.
2577 */
2578 static <K> Spliterator<K> keySpliteratorFor(NavigableMap<K,?> m) {
2579 if (m instanceof TreeMap) {
2580 @SuppressWarnings("unchecked") TreeMap<K,Object> t =
2581 (TreeMap<K,Object>) m;
2582 return t.keySpliterator();
2583 }
2584 if (m instanceof DescendingSubMap) {
2585 @SuppressWarnings("unchecked") DescendingSubMap<K,?> dm =
2586 (DescendingSubMap<K,?>) m;
2587 TreeMap<K,?> tm = dm.m;
2588 if (dm == tm.descendingMap) {
2589 @SuppressWarnings("unchecked") TreeMap<K,Object> t =
2590 (TreeMap<K,Object>) tm;
2591 return t.descendingKeySpliterator();
2592 }
2593 }
2594 @SuppressWarnings("unchecked") NavigableSubMap<K,?> sm =
2595 (NavigableSubMap<K,?>) m;
2596 return sm.keySpliterator();
2597 }
2598
2599 final Spliterator<K> keySpliterator() {
2600 return new KeySpliterator<K,V>(this, null, null, 0, -1, 0);
2601 }
2602
2603 final Spliterator<K> descendingKeySpliterator() {
2604 return new DescendingKeySpliterator<K,V>(this, null, null, 0, -2, 0);
2605 }
2606
2607 /**
2608 * Base class for spliterators. Iteration starts at a given
2609 * origin and continues up to but not including a given fence (or
2610 * null for end). At top-level, for ascending cases, the first
2611 * split uses the root as left-fence/right-origin. From there,
2612 * right-hand splits replace the current fence with its left
2613 * child, also serving as origin for the split-off spliterator.
2614 * Left-hands are symmetric. Descending versions place the origin
2615 * at the end and invert ascending split rules. This base class
2616 * is non-commital about directionality, or whether the top-level
2617 * spliterator covers the whole tree. This means that the actual
2618 * split mechanics are located in subclasses. Some of the subclass
2619 * trySplit methods are identical (except for return types), but
2620 * not nicely factorable.
2621 *
2622 * Currently, subclass versions exist only for the full map
2623 * (including descending keys via its descendingMap). Others are
2624 * possible but currently not worthwhile because submaps require
2625 * O(n) computations to determine size, which substantially limits
2626 * potential speed-ups of using custom Spliterators versus default
2627 * mechanics.
2628 *
2629 * To boostrap initialization, external constructors use
2630 * negative size estimates: -1 for ascend, -2 for descend.
2631 */
2632 static class TreeMapSpliterator<K,V> {
2633 final TreeMap<K,V> tree;
2634 TreeMap.Entry<K,V> current; // traverser; initially first node in range
2635 TreeMap.Entry<K,V> fence; // one past last, or null
2636 int side; // 0: top, -1: is a left split, +1: right
2637 int est; // size estimate (exact only for top-level)
2638 int expectedModCount; // for CME checks
2639
2640 TreeMapSpliterator(TreeMap<K,V> tree,
2641 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2642 int side, int est, int expectedModCount) {
2643 this.tree = tree;
2644 this.current = origin;
2645 this.fence = fence;
2646 this.side = side;
2647 this.est = est;
2648 this.expectedModCount = expectedModCount;
2649 }
2650
2651 final int getEstimate() { // force initialization
2652 int s; TreeMap<K,V> t;
2653 if ((s = est) < 0) {
2654 if ((t = tree) != null) {
2655 current = (s == -1) ? t.getFirstEntry() : t.getLastEntry();
2656 s = est = t.size;
2657 expectedModCount = t.modCount;
2658 }
2659 else
2660 s = est = 0;
2661 }
2662 return s;
2663 }
2664
2665 public final long estimateSize() {
2666 return (long)getEstimate();
2667 }
2668 }
2669
2670 static final class KeySpliterator<K,V>
2671 extends TreeMapSpliterator<K,V>
2672 implements Spliterator<K> {
2673 KeySpliterator(TreeMap<K,V> tree,
2674 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2675 int side, int est, int expectedModCount) {
2676 super(tree, origin, fence, side, est, expectedModCount);
2677 }
2678
2679 public KeySpliterator<K,V> trySplit() {
2680 if (est < 0)
2681 getEstimate(); // force initialization
2682 int d = side;
2683 TreeMap.Entry<K,V> e = current, f = fence,
2684 s = ((e == null || e == f) ? null : // empty
2685 (d == 0) ? tree.root : // was top
2686 (d > 0) ? e.right : // was right
2687 (d < 0 && f != null) ? f.left : // was left
2688 null);
2689 if (s != null && s != e && s != f &&
2690 tree.compare(e.key, s.key) < 0) { // e not already past s
2691 side = 1;
2692 return new KeySpliterator<>
2693 (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2694 }
2695 return null;
2696 }
2697
2698 public void forEachRemaining(Consumer<? super K> action) {
2699 if (action == null)
2700 throw new NullPointerException();
2701 if (est < 0)
2702 getEstimate(); // force initialization
2703 TreeMap.Entry<K,V> f = fence, e, p, pl;
2704 if ((e = current) != null && e != f) {
2705 current = f; // exhaust
2706 do {
2707 action.accept(e.key);
2708 if ((p = e.right) != null) {
2709 while ((pl = p.left) != null)
2710 p = pl;
2711 }
2712 else {
2713 while ((p = e.parent) != null && e == p.right)
2714 e = p;
2715 }
2716 } while ((e = p) != null && e != f);
2717 if (tree.modCount != expectedModCount)
2718 throw new ConcurrentModificationException();
2719 }
2720 }
2721
2722 public boolean tryAdvance(Consumer<? super K> action) {
2723 TreeMap.Entry<K,V> e;
2724 if (action == null)
2725 throw new NullPointerException();
2726 if (est < 0)
2727 getEstimate(); // force initialization
2728 if ((e = current) == null || e == fence)
2729 return false;
2730 current = successor(e);
2731 action.accept(e.key);
2732 if (tree.modCount != expectedModCount)
2733 throw new ConcurrentModificationException();
2734 return true;
2735 }
2736
2737 public int characteristics() {
2738 return (side == 0 ? Spliterator.SIZED : 0) |
2739 Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
2740 }
2741
2742 public final Comparator<? super K> getComparator() {
2743 return tree.comparator;
2744 }
2745
2746 }
2747
2748 static final class DescendingKeySpliterator<K,V>
2749 extends TreeMapSpliterator<K,V>
2750 implements Spliterator<K> {
2751 DescendingKeySpliterator(TreeMap<K,V> tree,
2752 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2753 int side, int est, int expectedModCount) {
2754 super(tree, origin, fence, side, est, expectedModCount);
2755 }
2756
2757 public DescendingKeySpliterator<K,V> trySplit() {
2758 if (est < 0)
2759 getEstimate(); // force initialization
2760 int d = side;
2761 TreeMap.Entry<K,V> e = current, f = fence,
2762 s = ((e == null || e == f) ? null : // empty
2763 (d == 0) ? tree.root : // was top
2764 (d < 0) ? e.left : // was left
2765 (d > 0 && f != null) ? f.right : // was right
2766 null);
2767 if (s != null && s != e && s != f &&
2768 tree.compare(e.key, s.key) > 0) { // e not already past s
2769 side = 1;
2770 return new DescendingKeySpliterator<>
2771 (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2772 }
2773 return null;
2774 }
2775
2776 public void forEachRemaining(Consumer<? super K> action) {
2777 if (action == null)
2778 throw new NullPointerException();
2779 if (est < 0)
2780 getEstimate(); // force initialization
2781 TreeMap.Entry<K,V> f = fence, e, p, pr;
2782 if ((e = current) != null && e != f) {
2783 current = f; // exhaust
2784 do {
2785 action.accept(e.key);
2786 if ((p = e.left) != null) {
2787 while ((pr = p.right) != null)
2788 p = pr;
2789 }
2790 else {
2791 while ((p = e.parent) != null && e == p.left)
2792 e = p;
2793 }
2794 } while ((e = p) != null && e != f);
2795 if (tree.modCount != expectedModCount)
2796 throw new ConcurrentModificationException();
2797 }
2798 }
2799
2800 public boolean tryAdvance(Consumer<? super K> action) {
2801 TreeMap.Entry<K,V> e;
2802 if (action == null)
2803 throw new NullPointerException();
2804 if (est < 0)
2805 getEstimate(); // force initialization
2806 if ((e = current) == null || e == fence)
2807 return false;
2808 current = predecessor(e);
2809 action.accept(e.key);
2810 if (tree.modCount != expectedModCount)
2811 throw new ConcurrentModificationException();
2812 return true;
2813 }
2814
2815 public int characteristics() {
2816 return (side == 0 ? Spliterator.SIZED : 0) |
2817 Spliterator.DISTINCT | Spliterator.ORDERED;
2818 }
2819 }
2820
2821 static final class ValueSpliterator<K,V>
2822 extends TreeMapSpliterator<K,V>
2823 implements Spliterator<V> {
2824 ValueSpliterator(TreeMap<K,V> tree,
2825 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2826 int side, int est, int expectedModCount) {
2827 super(tree, origin, fence, side, est, expectedModCount);
2828 }
2829
2830 public ValueSpliterator<K,V> trySplit() {
2831 if (est < 0)
2832 getEstimate(); // force initialization
2833 int d = side;
2834 TreeMap.Entry<K,V> e = current, f = fence,
2835 s = ((e == null || e == f) ? null : // empty
2836 (d == 0) ? tree.root : // was top
2837 (d > 0) ? e.right : // was right
2838 (d < 0 && f != null) ? f.left : // was left
2839 null);
2840 if (s != null && s != e && s != f &&
2841 tree.compare(e.key, s.key) < 0) { // e not already past s
2842 side = 1;
2843 return new ValueSpliterator<>
2844 (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2845 }
2846 return null;
2847 }
2848
2849 public void forEachRemaining(Consumer<? super V> action) {
2850 if (action == null)
2851 throw new NullPointerException();
2852 if (est < 0)
2853 getEstimate(); // force initialization
2854 TreeMap.Entry<K,V> f = fence, e, p, pl;
2855 if ((e = current) != null && e != f) {
2856 current = f; // exhaust
2857 do {
2858 action.accept(e.value);
2859 if ((p = e.right) != null) {
2860 while ((pl = p.left) != null)
2861 p = pl;
2862 }
2863 else {
2864 while ((p = e.parent) != null && e == p.right)
2865 e = p;
2866 }
2867 } while ((e = p) != null && e != f);
2868 if (tree.modCount != expectedModCount)
2869 throw new ConcurrentModificationException();
2870 }
2871 }
2872
2873 public boolean tryAdvance(Consumer<? super V> action) {
2874 TreeMap.Entry<K,V> e;
2875 if (action == null)
2876 throw new NullPointerException();
2877 if (est < 0)
2878 getEstimate(); // force initialization
2879 if ((e = current) == null || e == fence)
2880 return false;
2881 current = successor(e);
2882 action.accept(e.value);
2883 if (tree.modCount != expectedModCount)
2884 throw new ConcurrentModificationException();
2885 return true;
2886 }
2887
2888 public int characteristics() {
2889 return (side == 0 ? Spliterator.SIZED : 0);
2890 }
2891 }
2892
2893 static final class EntrySpliterator<K,V>
2894 extends TreeMapSpliterator<K,V>
2895 implements Spliterator<Map.Entry<K,V>> {
2896 EntrySpliterator(TreeMap<K,V> tree,
2897 TreeMap.Entry<K,V> origin, TreeMap.Entry<K,V> fence,
2898 int side, int est, int expectedModCount) {
2899 super(tree, origin, fence, side, est, expectedModCount);
2900 }
2901
2902 public EntrySpliterator<K,V> trySplit() {
2903 if (est < 0)
2904 getEstimate(); // force initialization
2905 int d = side;
2906 TreeMap.Entry<K,V> e = current, f = fence,
2907 s = ((e == null || e == f) ? null : // empty
2908 (d == 0) ? tree.root : // was top
2909 (d > 0) ? e.right : // was right
2910 (d < 0 && f != null) ? f.left : // was left
2911 null);
2912 if (s != null && s != e && s != f &&
2913 tree.compare(e.key, s.key) < 0) { // e not already past s
2914 side = 1;
2915 return new EntrySpliterator<>
2916 (tree, e, current = s, -1, est >>>= 1, expectedModCount);
2917 }
2918 return null;
2919 }
2920
2921 public void forEachRemaining(Consumer<? super Map.Entry<K, V>> action) {
2922 if (action == null)
2923 throw new NullPointerException();
2924 if (est < 0)
2925 getEstimate(); // force initialization
2926 TreeMap.Entry<K,V> f = fence, e, p, pl;
2927 if ((e = current) != null && e != f) {
2928 current = f; // exhaust
2929 do {
2930 action.accept(e);
2931 if ((p = e.right) != null) {
2932 while ((pl = p.left) != null)
2933 p = pl;
2934 }
2935 else {
2936 while ((p = e.parent) != null && e == p.right)
2937 e = p;
2938 }
2939 } while ((e = p) != null && e != f);
2940 if (tree.modCount != expectedModCount)
2941 throw new ConcurrentModificationException();
2942 }
2943 }
2944
2945 public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
2946 TreeMap.Entry<K,V> e;
2947 if (action == null)
2948 throw new NullPointerException();
2949 if (est < 0)
2950 getEstimate(); // force initialization
2951 if ((e = current) == null || e == fence)
2952 return false;
2953 current = successor(e);
2954 action.accept(e);
2955 if (tree.modCount != expectedModCount)
2956 throw new ConcurrentModificationException();
2957 return true;
2958 }
2959
2960 public int characteristics() {
2961 return (side == 0 ? Spliterator.SIZED : 0) |
2962 Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED;
2963 }
2964
2965 @Override
2966 public Comparator<? super Map.Entry<K, V>> getComparator() {
2967 return tree.comparator != null ?
2968 Map.Entry.comparingByKey(tree.comparator) : null;
2969 }
2970 }
2971 }