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