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