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