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