ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/jsr166/jsr166/src/main/java/util/TreeMap.java
Revision: 1.33
Committed: Sat Apr 22 23:02:25 2006 UTC (18 years, 1 month ago) by dl
Branch: MAIN
Changes since 1.32: +120 -129 lines
Log Message:
Minor refactorings

File Contents

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