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