001 /* TreeMap.java -- a class providing a basic Red-Black Tree data structure,
002 mapping Object --> Object
003 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005, 2006 Free Software Foundation, Inc.
004
005 This file is part of GNU Classpath.
006
007 GNU Classpath is free software; you can redistribute it and/or modify
008 it under the terms of the GNU General Public License as published by
009 the Free Software Foundation; either version 2, or (at your option)
010 any later version.
011
012 GNU Classpath is distributed in the hope that it will be useful, but
013 WITHOUT ANY WARRANTY; without even the implied warranty of
014 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
015 General Public License for more details.
016
017 You should have received a copy of the GNU General Public License
018 along with GNU Classpath; see the file COPYING. If not, write to the
019 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
020 02110-1301 USA.
021
022 Linking this library statically or dynamically with other modules is
023 making a combined work based on this library. Thus, the terms and
024 conditions of the GNU General Public License cover the whole
025 combination.
026
027 As a special exception, the copyright holders of this library give you
028 permission to link this library with independent modules to produce an
029 executable, regardless of the license terms of these independent
030 modules, and to copy and distribute the resulting executable under
031 terms of your choice, provided that you also meet, for each linked
032 independent module, the terms and conditions of the license of that
033 module. An independent module is a module which is not derived from
034 or based on this library. If you modify this library, you may extend
035 this exception to your version of the library, but you are not
036 obligated to do so. If you do not wish to do so, delete this
037 exception statement from your version. */
038
039
040 package java.util;
041
042 import java.io.IOException;
043 import java.io.ObjectInputStream;
044 import java.io.ObjectOutputStream;
045 import java.io.Serializable;
046
047 /**
048 * This class provides a red-black tree implementation of the SortedMap
049 * interface. Elements in the Map will be sorted by either a user-provided
050 * Comparator object, or by the natural ordering of the keys.
051 *
052 * The algorithms are adopted from Corman, Leiserson, and Rivest's
053 * <i>Introduction to Algorithms.</i> TreeMap guarantees O(log n)
054 * insertion and deletion of elements. That being said, there is a large
055 * enough constant coefficient in front of that "log n" (overhead involved
056 * in keeping the tree balanced), that TreeMap may not be the best choice
057 * for small collections. If something is already sorted, you may want to
058 * just use a LinkedHashMap to maintain the order while providing O(1) access.
059 *
060 * TreeMap is a part of the JDK1.2 Collections API. Null keys are allowed
061 * only if a Comparator is used which can deal with them; natural ordering
062 * cannot cope with null. Null values are always allowed. Note that the
063 * ordering must be <i>consistent with equals</i> to correctly implement
064 * the Map interface. If this condition is violated, the map is still
065 * well-behaved, but you may have suprising results when comparing it to
066 * other maps.<p>
067 *
068 * This implementation is not synchronized. If you need to share this between
069 * multiple threads, do something like:<br>
070 * <code>SortedMap m
071 * = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
072 *
073 * The iterators are <i>fail-fast</i>, meaning that any structural
074 * modification, except for <code>remove()</code> called on the iterator
075 * itself, cause the iterator to throw a
076 * <code>ConcurrentModificationException</code> rather than exhibit
077 * non-deterministic behavior.
078 *
079 * @author Jon Zeppieri
080 * @author Bryce McKinlay
081 * @author Eric Blake (ebb9@email.byu.edu)
082 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
083 * @see Map
084 * @see HashMap
085 * @see Hashtable
086 * @see LinkedHashMap
087 * @see Comparable
088 * @see Comparator
089 * @see Collection
090 * @see Collections#synchronizedSortedMap(SortedMap)
091 * @since 1.2
092 * @status updated to 1.6
093 */
094 public class TreeMap<K, V> extends AbstractMap<K, V>
095 implements NavigableMap<K, V>, Cloneable, Serializable
096 {
097 // Implementation note:
098 // A red-black tree is a binary search tree with the additional properties
099 // that all paths to a leaf node visit the same number of black nodes,
100 // and no red node has red children. To avoid some null-pointer checks,
101 // we use the special node nil which is always black, has no relatives,
102 // and has key and value of null (but is not equal to a mapping of null).
103
104 /**
105 * Compatible with JDK 1.2.
106 */
107 private static final long serialVersionUID = 919286545866124006L;
108
109 /**
110 * Color status of a node. Package visible for use by nested classes.
111 */
112 static final int RED = -1,
113 BLACK = 1;
114
115 /**
116 * Sentinal node, used to avoid null checks for corner cases and make the
117 * delete rebalance code simpler. The rebalance code must never assign
118 * the parent, left, or right of nil, but may safely reassign the color
119 * to be black. This object must never be used as a key in a TreeMap, or
120 * it will break bounds checking of a SubMap.
121 */
122 static final Node nil = new Node(null, null, BLACK);
123 static
124 {
125 // Nil is self-referential, so we must initialize it after creation.
126 nil.parent = nil;
127 nil.left = nil;
128 nil.right = nil;
129 }
130
131 /**
132 * The root node of this TreeMap.
133 */
134 private transient Node root;
135
136 /**
137 * The size of this TreeMap. Package visible for use by nested classes.
138 */
139 transient int size;
140
141 /**
142 * The cache for {@link #entrySet()}.
143 */
144 private transient Set<Map.Entry<K,V>> entries;
145
146 /**
147 * The cache for {@link #descendingMap()}.
148 */
149 private transient NavigableMap<K,V> descendingMap;
150
151 /**
152 * The cache for {@link #navigableKeySet()}.
153 */
154 private transient NavigableSet<K> nKeys;
155
156 /**
157 * Counts the number of modifications this TreeMap has undergone, used
158 * by Iterators to know when to throw ConcurrentModificationExceptions.
159 * Package visible for use by nested classes.
160 */
161 transient int modCount;
162
163 /**
164 * This TreeMap's comparator, or null for natural ordering.
165 * Package visible for use by nested classes.
166 * @serial the comparator ordering this tree, or null
167 */
168 final Comparator<? super K> comparator;
169
170 /**
171 * Class to represent an entry in the tree. Holds a single key-value pair,
172 * plus pointers to parent and child nodes.
173 *
174 * @author Eric Blake (ebb9@email.byu.edu)
175 */
176 private static final class Node<K, V> extends AbstractMap.SimpleEntry<K, V>
177 {
178 // All fields package visible for use by nested classes.
179 /** The color of this node. */
180 int color;
181
182 /** The left child node. */
183 Node<K, V> left = nil;
184 /** The right child node. */
185 Node<K, V> right = nil;
186 /** The parent node. */
187 Node<K, V> parent = nil;
188
189 /**
190 * Simple constructor.
191 * @param key the key
192 * @param value the value
193 */
194 Node(K key, V value, int color)
195 {
196 super(key, value);
197 this.color = color;
198 }
199 }
200
201 /**
202 * Instantiate a new TreeMap with no elements, using the keys' natural
203 * ordering to sort. All entries in the map must have a key which implements
204 * Comparable, and which are <i>mutually comparable</i>, otherwise map
205 * operations may throw a {@link ClassCastException}. Attempts to use
206 * a null key will throw a {@link NullPointerException}.
207 *
208 * @see Comparable
209 */
210 public TreeMap()
211 {
212 this((Comparator) null);
213 }
214
215 /**
216 * Instantiate a new TreeMap with no elements, using the provided comparator
217 * to sort. All entries in the map must have keys which are mutually
218 * comparable by the Comparator, otherwise map operations may throw a
219 * {@link ClassCastException}.
220 *
221 * @param c the sort order for the keys of this map, or null
222 * for the natural order
223 */
224 public TreeMap(Comparator<? super K> c)
225 {
226 comparator = c;
227 fabricateTree(0);
228 }
229
230 /**
231 * Instantiate a new TreeMap, initializing it with all of the elements in
232 * the provided Map. The elements will be sorted using the natural
233 * ordering of the keys. This algorithm runs in n*log(n) time. All entries
234 * in the map must have keys which implement Comparable and are mutually
235 * comparable, otherwise map operations may throw a
236 * {@link ClassCastException}.
237 *
238 * @param map a Map, whose entries will be put into this TreeMap
239 * @throws ClassCastException if the keys in the provided Map are not
240 * comparable
241 * @throws NullPointerException if map is null
242 * @see Comparable
243 */
244 public TreeMap(Map<? extends K, ? extends V> map)
245 {
246 this((Comparator) null);
247 putAll(map);
248 }
249
250 /**
251 * Instantiate a new TreeMap, initializing it with all of the elements in
252 * the provided SortedMap. The elements will be sorted using the same
253 * comparator as in the provided SortedMap. This runs in linear time.
254 *
255 * @param sm a SortedMap, whose entries will be put into this TreeMap
256 * @throws NullPointerException if sm is null
257 */
258 public TreeMap(SortedMap<K, ? extends V> sm)
259 {
260 this(sm.comparator());
261 int pos = sm.size();
262 Iterator itr = sm.entrySet().iterator();
263
264 fabricateTree(pos);
265 Node node = firstNode();
266
267 while (--pos >= 0)
268 {
269 Map.Entry me = (Map.Entry) itr.next();
270 node.key = me.getKey();
271 node.value = me.getValue();
272 node = successor(node);
273 }
274 }
275
276 /**
277 * Clears the Map so it has no keys. This is O(1).
278 */
279 public void clear()
280 {
281 if (size > 0)
282 {
283 modCount++;
284 root = nil;
285 size = 0;
286 }
287 }
288
289 /**
290 * Returns a shallow clone of this TreeMap. The Map itself is cloned,
291 * but its contents are not.
292 *
293 * @return the clone
294 */
295 public Object clone()
296 {
297 TreeMap copy = null;
298 try
299 {
300 copy = (TreeMap) super.clone();
301 }
302 catch (CloneNotSupportedException x)
303 {
304 }
305 copy.entries = null;
306 copy.fabricateTree(size);
307
308 Node node = firstNode();
309 Node cnode = copy.firstNode();
310
311 while (node != nil)
312 {
313 cnode.key = node.key;
314 cnode.value = node.value;
315 node = successor(node);
316 cnode = copy.successor(cnode);
317 }
318 return copy;
319 }
320
321 /**
322 * Return the comparator used to sort this map, or null if it is by
323 * natural order.
324 *
325 * @return the map's comparator
326 */
327 public Comparator<? super K> comparator()
328 {
329 return comparator;
330 }
331
332 /**
333 * Returns true if the map contains a mapping for the given key.
334 *
335 * @param key the key to look for
336 * @return true if the key has a mapping
337 * @throws ClassCastException if key is not comparable to map elements
338 * @throws NullPointerException if key is null and the comparator is not
339 * tolerant of nulls
340 */
341 public boolean containsKey(Object key)
342 {
343 return getNode((K) key) != nil;
344 }
345
346 /**
347 * Returns true if the map contains at least one mapping to the given value.
348 * This requires linear time.
349 *
350 * @param value the value to look for
351 * @return true if the value appears in a mapping
352 */
353 public boolean containsValue(Object value)
354 {
355 Node node = firstNode();
356 while (node != nil)
357 {
358 if (equals(value, node.value))
359 return true;
360 node = successor(node);
361 }
362 return false;
363 }
364
365 /**
366 * Returns a "set view" of this TreeMap's entries. The set is backed by
367 * the TreeMap, so changes in one show up in the other. The set supports
368 * element removal, but not element addition.<p>
369 *
370 * Note that the iterators for all three views, from keySet(), entrySet(),
371 * and values(), traverse the TreeMap in sorted sequence.
372 *
373 * @return a set view of the entries
374 * @see #keySet()
375 * @see #values()
376 * @see Map.Entry
377 */
378 public Set<Map.Entry<K,V>> entrySet()
379 {
380 if (entries == null)
381 // Create an AbstractSet with custom implementations of those methods
382 // that can be overriden easily and efficiently.
383 entries = new NavigableEntrySet();
384 return entries;
385 }
386
387 /**
388 * Returns the first (lowest) key in the map.
389 *
390 * @return the first key
391 * @throws NoSuchElementException if the map is empty
392 */
393 public K firstKey()
394 {
395 if (root == nil)
396 throw new NoSuchElementException();
397 return firstNode().key;
398 }
399
400 /**
401 * Return the value in this TreeMap associated with the supplied key,
402 * or <code>null</code> if the key maps to nothing. NOTE: Since the value
403 * could also be null, you must use containsKey to see if this key
404 * actually maps to something.
405 *
406 * @param key the key for which to fetch an associated value
407 * @return what the key maps to, if present
408 * @throws ClassCastException if key is not comparable to elements in the map
409 * @throws NullPointerException if key is null but the comparator does not
410 * tolerate nulls
411 * @see #put(Object, Object)
412 * @see #containsKey(Object)
413 */
414 public V get(Object key)
415 {
416 // Exploit fact that nil.value == null.
417 return getNode((K) key).value;
418 }
419
420 /**
421 * Returns a view of this Map including all entries with keys less than
422 * <code>toKey</code>. The returned map is backed by the original, so changes
423 * in one appear in the other. The submap will throw an
424 * {@link IllegalArgumentException} for any attempt to access or add an
425 * element beyond the specified cutoff. The returned map does not include
426 * the endpoint; if you want inclusion, pass the successor element
427 * or call <code>headMap(toKey, true)</code>. This is equivalent to
428 * calling <code>headMap(toKey, false)</code>.
429 *
430 * @param toKey the (exclusive) cutoff point
431 * @return a view of the map less than the cutoff
432 * @throws ClassCastException if <code>toKey</code> is not compatible with
433 * the comparator (or is not Comparable, for natural ordering)
434 * @throws NullPointerException if toKey is null, but the comparator does not
435 * tolerate null elements
436 */
437 public SortedMap<K, V> headMap(K toKey)
438 {
439 return headMap(toKey, false);
440 }
441
442 /**
443 * Returns a view of this Map including all entries with keys less than
444 * (or equal to, if <code>inclusive</code> is true) <code>toKey</code>.
445 * The returned map is backed by the original, so changes in one appear
446 * in the other. The submap will throw an {@link IllegalArgumentException}
447 * for any attempt to access or add an element beyond the specified cutoff.
448 *
449 * @param toKey the cutoff point
450 * @param inclusive true if the cutoff point should be included.
451 * @return a view of the map less than (or equal to, if <code>inclusive</code>
452 * is true) the cutoff.
453 * @throws ClassCastException if <code>toKey</code> is not compatible with
454 * the comparator (or is not Comparable, for natural ordering)
455 * @throws NullPointerException if toKey is null, but the comparator does not
456 * tolerate null elements
457 */
458 public NavigableMap<K, V> headMap(K toKey, boolean inclusive)
459 {
460 return new SubMap((K)(Object)nil, inclusive
461 ? successor(getNode(toKey)).key : toKey);
462 }
463
464 /**
465 * Returns a "set view" of this TreeMap's keys. The set is backed by the
466 * TreeMap, so changes in one show up in the other. The set supports
467 * element removal, but not element addition.
468 *
469 * @return a set view of the keys
470 * @see #values()
471 * @see #entrySet()
472 */
473 public Set<K> keySet()
474 {
475 if (keys == null)
476 // Create an AbstractSet with custom implementations of those methods
477 // that can be overriden easily and efficiently.
478 keys = new KeySet();
479 return keys;
480 }
481
482 /**
483 * Returns the last (highest) key in the map.
484 *
485 * @return the last key
486 * @throws NoSuchElementException if the map is empty
487 */
488 public K lastKey()
489 {
490 if (root == nil)
491 throw new NoSuchElementException("empty");
492 return lastNode().key;
493 }
494
495 /**
496 * Puts the supplied value into the Map, mapped by the supplied key.
497 * The value may be retrieved by any object which <code>equals()</code>
498 * this key. NOTE: Since the prior value could also be null, you must
499 * first use containsKey if you want to see if you are replacing the
500 * key's mapping.
501 *
502 * @param key the key used to locate the value
503 * @param value the value to be stored in the Map
504 * @return the prior mapping of the key, or null if there was none
505 * @throws ClassCastException if key is not comparable to current map keys
506 * @throws NullPointerException if key is null, but the comparator does
507 * not tolerate nulls
508 * @see #get(Object)
509 * @see Object#equals(Object)
510 */
511 public V put(K key, V value)
512 {
513 Node<K,V> current = root;
514 Node<K,V> parent = nil;
515 int comparison = 0;
516
517 // Find new node's parent.
518 while (current != nil)
519 {
520 parent = current;
521 comparison = compare(key, current.key);
522 if (comparison > 0)
523 current = current.right;
524 else if (comparison < 0)
525 current = current.left;
526 else // Key already in tree.
527 return current.setValue(value);
528 }
529
530 // Set up new node.
531 Node n = new Node(key, value, RED);
532 n.parent = parent;
533
534 // Insert node in tree.
535 modCount++;
536 size++;
537 if (parent == nil)
538 {
539 // Special case inserting into an empty tree.
540 root = n;
541 return null;
542 }
543 if (comparison > 0)
544 parent.right = n;
545 else
546 parent.left = n;
547
548 // Rebalance after insert.
549 insertFixup(n);
550 return null;
551 }
552
553 /**
554 * Copies all elements of the given map into this TreeMap. If this map
555 * already has a mapping for a key, the new mapping replaces the current
556 * one.
557 *
558 * @param m the map to be added
559 * @throws ClassCastException if a key in m is not comparable with keys
560 * in the map
561 * @throws NullPointerException if a key in m is null, and the comparator
562 * does not tolerate nulls
563 */
564 public void putAll(Map<? extends K, ? extends V> m)
565 {
566 Iterator itr = m.entrySet().iterator();
567 int pos = m.size();
568 while (--pos >= 0)
569 {
570 Map.Entry<K,V> e = (Map.Entry<K,V>) itr.next();
571 put(e.getKey(), e.getValue());
572 }
573 }
574
575 /**
576 * Removes from the TreeMap and returns the value which is mapped by the
577 * supplied key. If the key maps to nothing, then the TreeMap remains
578 * unchanged, and <code>null</code> is returned. NOTE: Since the value
579 * could also be null, you must use containsKey to see if you are
580 * actually removing a mapping.
581 *
582 * @param key the key used to locate the value to remove
583 * @return whatever the key mapped to, if present
584 * @throws ClassCastException if key is not comparable to current map keys
585 * @throws NullPointerException if key is null, but the comparator does
586 * not tolerate nulls
587 */
588 public V remove(Object key)
589 {
590 Node<K, V> n = getNode((K)key);
591 if (n == nil)
592 return null;
593 // Note: removeNode can alter the contents of n, so save value now.
594 V result = n.value;
595 removeNode(n);
596 return result;
597 }
598
599 /**
600 * Returns the number of key-value mappings currently in this Map.
601 *
602 * @return the size
603 */
604 public int size()
605 {
606 return size;
607 }
608
609 /**
610 * Returns a view of this Map including all entries with keys greater or
611 * equal to <code>fromKey</code> and less than <code>toKey</code> (a
612 * half-open interval). The returned map is backed by the original, so
613 * changes in one appear in the other. The submap will throw an
614 * {@link IllegalArgumentException} for any attempt to access or add an
615 * element beyond the specified cutoffs. The returned map includes the low
616 * endpoint but not the high; if you want to reverse this behavior on
617 * either end, pass in the successor element or call
618 * {@link #subMap(K,boolean,K,boolean)}. This call is equivalent to
619 * <code>subMap(fromKey, true, toKey, false)</code>.
620 *
621 * @param fromKey the (inclusive) low cutoff point
622 * @param toKey the (exclusive) high cutoff point
623 * @return a view of the map between the cutoffs
624 * @throws ClassCastException if either cutoff is not compatible with
625 * the comparator (or is not Comparable, for natural ordering)
626 * @throws NullPointerException if fromKey or toKey is null, but the
627 * comparator does not tolerate null elements
628 * @throws IllegalArgumentException if fromKey is greater than toKey
629 */
630 public SortedMap<K, V> subMap(K fromKey, K toKey)
631 {
632 return subMap(fromKey, true, toKey, false);
633 }
634
635 /**
636 * Returns a view of this Map including all entries with keys greater (or
637 * equal to, if <code>fromInclusive</code> is true) <code>fromKey</code> and
638 * less than (or equal to, if <code>toInclusive</code> is true)
639 * <code>toKey</code>. The returned map is backed by the original, so
640 * changes in one appear in the other. The submap will throw an
641 * {@link IllegalArgumentException} for any attempt to access or add an
642 * element beyond the specified cutoffs.
643 *
644 * @param fromKey the low cutoff point
645 * @param fromInclusive true if the low cutoff point should be included.
646 * @param toKey the high cutoff point
647 * @param toInclusive true if the high cutoff point should be included.
648 * @return a view of the map for the specified range.
649 * @throws ClassCastException if either cutoff is not compatible with
650 * the comparator (or is not Comparable, for natural ordering)
651 * @throws NullPointerException if fromKey or toKey is null, but the
652 * comparator does not tolerate null elements
653 * @throws IllegalArgumentException if fromKey is greater than toKey
654 */
655 public NavigableMap<K, V> subMap(K fromKey, boolean fromInclusive,
656 K toKey, boolean toInclusive)
657 {
658 return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key,
659 toInclusive ? successor(getNode(toKey)).key : toKey);
660 }
661
662 /**
663 * Returns a view of this Map including all entries with keys greater or
664 * equal to <code>fromKey</code>. The returned map is backed by the
665 * original, so changes in one appear in the other. The submap will throw an
666 * {@link IllegalArgumentException} for any attempt to access or add an
667 * element beyond the specified cutoff. The returned map includes the
668 * endpoint; if you want to exclude it, pass in the successor element.
669 * This is equivalent to calling <code>tailMap(fromKey, true)</code>.
670 *
671 * @param fromKey the (inclusive) low cutoff point
672 * @return a view of the map above the cutoff
673 * @throws ClassCastException if <code>fromKey</code> is not compatible with
674 * the comparator (or is not Comparable, for natural ordering)
675 * @throws NullPointerException if fromKey is null, but the comparator
676 * does not tolerate null elements
677 */
678 public SortedMap<K, V> tailMap(K fromKey)
679 {
680 return tailMap(fromKey, true);
681 }
682
683 /**
684 * Returns a view of this Map including all entries with keys greater or
685 * equal to <code>fromKey</code>. The returned map is backed by the
686 * original, so changes in one appear in the other. The submap will throw an
687 * {@link IllegalArgumentException} for any attempt to access or add an
688 * element beyond the specified cutoff. The returned map includes the
689 * endpoint; if you want to exclude it, pass in the successor element.
690 *
691 * @param fromKey the low cutoff point
692 * @param inclusive true if the cutoff point should be included.
693 * @return a view of the map above the cutoff
694 * @throws ClassCastException if <code>fromKey</code> is not compatible with
695 * the comparator (or is not Comparable, for natural ordering)
696 * @throws NullPointerException if fromKey is null, but the comparator
697 * does not tolerate null elements
698 */
699 public NavigableMap<K, V> tailMap(K fromKey, boolean inclusive)
700 {
701 return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
702 (K)(Object)nil);
703 }
704
705 /**
706 * Returns a "collection view" (or "bag view") of this TreeMap's values.
707 * The collection is backed by the TreeMap, so changes in one show up
708 * in the other. The collection supports element removal, but not element
709 * addition.
710 *
711 * @return a bag view of the values
712 * @see #keySet()
713 * @see #entrySet()
714 */
715 public Collection<V> values()
716 {
717 if (values == null)
718 // We don't bother overriding many of the optional methods, as doing so
719 // wouldn't provide any significant performance advantage.
720 values = new AbstractCollection<V>()
721 {
722 public int size()
723 {
724 return size;
725 }
726
727 public Iterator<V> iterator()
728 {
729 return new TreeIterator(VALUES);
730 }
731
732 public void clear()
733 {
734 TreeMap.this.clear();
735 }
736 };
737 return values;
738 }
739
740 /**
741 * Compares two elements by the set comparator, or by natural ordering.
742 * Package visible for use by nested classes.
743 *
744 * @param o1 the first object
745 * @param o2 the second object
746 * @throws ClassCastException if o1 and o2 are not mutually comparable,
747 * or are not Comparable with natural ordering
748 * @throws NullPointerException if o1 or o2 is null with natural ordering
749 */
750 final int compare(K o1, K o2)
751 {
752 return (comparator == null
753 ? ((Comparable) o1).compareTo(o2)
754 : comparator.compare(o1, o2));
755 }
756
757 /**
758 * Maintain red-black balance after deleting a node.
759 *
760 * @param node the child of the node just deleted, possibly nil
761 * @param parent the parent of the node just deleted, never nil
762 */
763 private void deleteFixup(Node<K,V> node, Node<K,V> parent)
764 {
765 // if (parent == nil)
766 // throw new InternalError();
767 // If a black node has been removed, we need to rebalance to avoid
768 // violating the "same number of black nodes on any path" rule. If
769 // node is red, we can simply recolor it black and all is well.
770 while (node != root && node.color == BLACK)
771 {
772 if (node == parent.left)
773 {
774 // Rebalance left side.
775 Node<K,V> sibling = parent.right;
776 // if (sibling == nil)
777 // throw new InternalError();
778 if (sibling.color == RED)
779 {
780 // Case 1: Sibling is red.
781 // Recolor sibling and parent, and rotate parent left.
782 sibling.color = BLACK;
783 parent.color = RED;
784 rotateLeft(parent);
785 sibling = parent.right;
786 }
787
788 if (sibling.left.color == BLACK && sibling.right.color == BLACK)
789 {
790 // Case 2: Sibling has no red children.
791 // Recolor sibling, and move to parent.
792 sibling.color = RED;
793 node = parent;
794 parent = parent.parent;
795 }
796 else
797 {
798 if (sibling.right.color == BLACK)
799 {
800 // Case 3: Sibling has red left child.
801 // Recolor sibling and left child, rotate sibling right.
802 sibling.left.color = BLACK;
803 sibling.color = RED;
804 rotateRight(sibling);
805 sibling = parent.right;
806 }
807 // Case 4: Sibling has red right child. Recolor sibling,
808 // right child, and parent, and rotate parent left.
809 sibling.color = parent.color;
810 parent.color = BLACK;
811 sibling.right.color = BLACK;
812 rotateLeft(parent);
813 node = root; // Finished.
814 }
815 }
816 else
817 {
818 // Symmetric "mirror" of left-side case.
819 Node<K,V> sibling = parent.left;
820 // if (sibling == nil)
821 // throw new InternalError();
822 if (sibling.color == RED)
823 {
824 // Case 1: Sibling is red.
825 // Recolor sibling and parent, and rotate parent right.
826 sibling.color = BLACK;
827 parent.color = RED;
828 rotateRight(parent);
829 sibling = parent.left;
830 }
831
832 if (sibling.right.color == BLACK && sibling.left.color == BLACK)
833 {
834 // Case 2: Sibling has no red children.
835 // Recolor sibling, and move to parent.
836 sibling.color = RED;
837 node = parent;
838 parent = parent.parent;
839 }
840 else
841 {
842 if (sibling.left.color == BLACK)
843 {
844 // Case 3: Sibling has red right child.
845 // Recolor sibling and right child, rotate sibling left.
846 sibling.right.color = BLACK;
847 sibling.color = RED;
848 rotateLeft(sibling);
849 sibling = parent.left;
850 }
851 // Case 4: Sibling has red left child. Recolor sibling,
852 // left child, and parent, and rotate parent right.
853 sibling.color = parent.color;
854 parent.color = BLACK;
855 sibling.left.color = BLACK;
856 rotateRight(parent);
857 node = root; // Finished.
858 }
859 }
860 }
861 node.color = BLACK;
862 }
863
864 /**
865 * Construct a perfectly balanced tree consisting of n "blank" nodes. This
866 * permits a tree to be generated from pre-sorted input in linear time.
867 *
868 * @param count the number of blank nodes, non-negative
869 */
870 private void fabricateTree(final int count)
871 {
872 if (count == 0)
873 {
874 root = nil;
875 size = 0;
876 return;
877 }
878
879 // We color every row of nodes black, except for the overflow nodes.
880 // I believe that this is the optimal arrangement. We construct the tree
881 // in place by temporarily linking each node to the next node in the row,
882 // then updating those links to the children when working on the next row.
883
884 // Make the root node.
885 root = new Node(null, null, BLACK);
886 size = count;
887 Node row = root;
888 int rowsize;
889
890 // Fill each row that is completely full of nodes.
891 for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1)
892 {
893 Node parent = row;
894 Node last = null;
895 for (int i = 0; i < rowsize; i += 2)
896 {
897 Node left = new Node(null, null, BLACK);
898 Node right = new Node(null, null, BLACK);
899 left.parent = parent;
900 left.right = right;
901 right.parent = parent;
902 parent.left = left;
903 Node next = parent.right;
904 parent.right = right;
905 parent = next;
906 if (last != null)
907 last.right = left;
908 last = right;
909 }
910 row = row.left;
911 }
912
913 // Now do the partial final row in red.
914 int overflow = count - rowsize;
915 Node parent = row;
916 int i;
917 for (i = 0; i < overflow; i += 2)
918 {
919 Node left = new Node(null, null, RED);
920 Node right = new Node(null, null, RED);
921 left.parent = parent;
922 right.parent = parent;
923 parent.left = left;
924 Node next = parent.right;
925 parent.right = right;
926 parent = next;
927 }
928 // Add a lone left node if necessary.
929 if (i - overflow == 0)
930 {
931 Node left = new Node(null, null, RED);
932 left.parent = parent;
933 parent.left = left;
934 parent = parent.right;
935 left.parent.right = nil;
936 }
937 // Unlink the remaining nodes of the previous row.
938 while (parent != nil)
939 {
940 Node next = parent.right;
941 parent.right = nil;
942 parent = next;
943 }
944 }
945
946 /**
947 * Returns the first sorted node in the map, or nil if empty. Package
948 * visible for use by nested classes.
949 *
950 * @return the first node
951 */
952 final Node<K, V> firstNode()
953 {
954 // Exploit fact that nil.left == nil.
955 Node node = root;
956 while (node.left != nil)
957 node = node.left;
958 return node;
959 }
960
961 /**
962 * Return the TreeMap.Node associated with key, or the nil node if no such
963 * node exists in the tree. Package visible for use by nested classes.
964 *
965 * @param key the key to search for
966 * @return the node where the key is found, or nil
967 */
968 final Node<K, V> getNode(K key)
969 {
970 Node<K,V> current = root;
971 while (current != nil)
972 {
973 int comparison = compare(key, current.key);
974 if (comparison > 0)
975 current = current.right;
976 else if (comparison < 0)
977 current = current.left;
978 else
979 return current;
980 }
981 return current;
982 }
983
984 /**
985 * Find the "highest" node which is < key. If key is nil, return last
986 * node. Package visible for use by nested classes.
987 *
988 * @param key the upper bound, exclusive
989 * @return the previous node
990 */
991 final Node<K,V> highestLessThan(K key)
992 {
993 return highestLessThan(key, false);
994 }
995
996 /**
997 * Find the "highest" node which is < (or equal to,
998 * if <code>equal</code> is true) key. If key is nil,
999 * return last node. Package visible for use by nested
1000 * classes.
1001 *
1002 * @param key the upper bound, exclusive
1003 * @param equal true if the key should be returned if found.
1004 * @return the previous node
1005 */
1006 final Node<K,V> highestLessThan(K key, boolean equal)
1007 {
1008 if (key == nil)
1009 return lastNode();
1010
1011 Node<K,V> last = nil;
1012 Node<K,V> current = root;
1013 int comparison = 0;
1014
1015 while (current != nil)
1016 {
1017 last = current;
1018 comparison = compare(key, current.key);
1019 if (comparison > 0)
1020 current = current.right;
1021 else if (comparison < 0)
1022 current = current.left;
1023 else // Exact match.
1024 return (equal ? last : predecessor(last));
1025 }
1026 return comparison < 0 ? predecessor(last) : last;
1027 }
1028
1029 /**
1030 * Maintain red-black balance after inserting a new node.
1031 *
1032 * @param n the newly inserted node
1033 */
1034 private void insertFixup(Node<K,V> n)
1035 {
1036 // Only need to rebalance when parent is a RED node, and while at least
1037 // 2 levels deep into the tree (ie: node has a grandparent). Remember
1038 // that nil.color == BLACK.
1039 while (n.parent.color == RED && n.parent.parent != nil)
1040 {
1041 if (n.parent == n.parent.parent.left)
1042 {
1043 Node uncle = n.parent.parent.right;
1044 // Uncle may be nil, in which case it is BLACK.
1045 if (uncle.color == RED)
1046 {
1047 // Case 1. Uncle is RED: Change colors of parent, uncle,
1048 // and grandparent, and move n to grandparent.
1049 n.parent.color = BLACK;
1050 uncle.color = BLACK;
1051 uncle.parent.color = RED;
1052 n = uncle.parent;
1053 }
1054 else
1055 {
1056 if (n == n.parent.right)
1057 {
1058 // Case 2. Uncle is BLACK and x is right child.
1059 // Move n to parent, and rotate n left.
1060 n = n.parent;
1061 rotateLeft(n);
1062 }
1063 // Case 3. Uncle is BLACK and x is left child.
1064 // Recolor parent, grandparent, and rotate grandparent right.
1065 n.parent.color = BLACK;
1066 n.parent.parent.color = RED;
1067 rotateRight(n.parent.parent);
1068 }
1069 }
1070 else
1071 {
1072 // Mirror image of above code.
1073 Node uncle = n.parent.parent.left;
1074 // Uncle may be nil, in which case it is BLACK.
1075 if (uncle.color == RED)
1076 {
1077 // Case 1. Uncle is RED: Change colors of parent, uncle,
1078 // and grandparent, and move n to grandparent.
1079 n.parent.color = BLACK;
1080 uncle.color = BLACK;
1081 uncle.parent.color = RED;
1082 n = uncle.parent;
1083 }
1084 else
1085 {
1086 if (n == n.parent.left)
1087 {
1088 // Case 2. Uncle is BLACK and x is left child.
1089 // Move n to parent, and rotate n right.
1090 n = n.parent;
1091 rotateRight(n);
1092 }
1093 // Case 3. Uncle is BLACK and x is right child.
1094 // Recolor parent, grandparent, and rotate grandparent left.
1095 n.parent.color = BLACK;
1096 n.parent.parent.color = RED;
1097 rotateLeft(n.parent.parent);
1098 }
1099 }
1100 }
1101 root.color = BLACK;
1102 }
1103
1104 /**
1105 * Returns the last sorted node in the map, or nil if empty.
1106 *
1107 * @return the last node
1108 */
1109 private Node<K,V> lastNode()
1110 {
1111 // Exploit fact that nil.right == nil.
1112 Node node = root;
1113 while (node.right != nil)
1114 node = node.right;
1115 return node;
1116 }
1117
1118 /**
1119 * Find the "lowest" node which is >= key. If key is nil, return either
1120 * nil or the first node, depending on the parameter first. Package visible
1121 * for use by nested classes.
1122 *
1123 * @param key the lower bound, inclusive
1124 * @param first true to return the first element instead of nil for nil key
1125 * @return the next node
1126 */
1127 final Node<K,V> lowestGreaterThan(K key, boolean first)
1128 {
1129 return lowestGreaterThan(key, first, true);
1130 }
1131
1132 /**
1133 * Find the "lowest" node which is > (or equal to, if <code>equal</code>
1134 * is true) key. If key is nil, return either nil or the first node, depending
1135 * on the parameter first. Package visible for use by nested classes.
1136 *
1137 * @param key the lower bound, inclusive
1138 * @param first true to return the first element instead of nil for nil key
1139 * @param equal true if the key should be returned if found.
1140 * @return the next node
1141 */
1142 final Node<K,V> lowestGreaterThan(K key, boolean first, boolean equal)
1143 {
1144 if (key == nil)
1145 return first ? firstNode() : nil;
1146
1147 Node<K,V> last = nil;
1148 Node<K,V> current = root;
1149 int comparison = 0;
1150
1151 while (current != nil)
1152 {
1153 last = current;
1154 comparison = compare(key, current.key);
1155 if (comparison > 0)
1156 current = current.right;
1157 else if (comparison < 0)
1158 current = current.left;
1159 else
1160 return (equal ? current : successor(current));
1161 }
1162 return comparison > 0 ? successor(last) : last;
1163 }
1164
1165 /**
1166 * Return the node preceding the given one, or nil if there isn't one.
1167 *
1168 * @param node the current node, not nil
1169 * @return the prior node in sorted order
1170 */
1171 private Node<K,V> predecessor(Node<K,V> node)
1172 {
1173 if (node.left != nil)
1174 {
1175 node = node.left;
1176 while (node.right != nil)
1177 node = node.right;
1178 return node;
1179 }
1180
1181 Node parent = node.parent;
1182 // Exploit fact that nil.left == nil and node is non-nil.
1183 while (node == parent.left)
1184 {
1185 node = parent;
1186 parent = node.parent;
1187 }
1188 return parent;
1189 }
1190
1191 /**
1192 * Construct a tree from sorted keys in linear time. Package visible for
1193 * use by TreeSet.
1194 *
1195 * @param s the stream to read from
1196 * @param count the number of keys to read
1197 * @param readValues true to read values, false to insert "" as the value
1198 * @throws ClassNotFoundException if the underlying stream fails
1199 * @throws IOException if the underlying stream fails
1200 * @see #readObject(ObjectInputStream)
1201 * @see TreeSet#readObject(ObjectInputStream)
1202 */
1203 final void putFromObjStream(ObjectInputStream s, int count,
1204 boolean readValues)
1205 throws IOException, ClassNotFoundException
1206 {
1207 fabricateTree(count);
1208 Node node = firstNode();
1209
1210 while (--count >= 0)
1211 {
1212 node.key = s.readObject();
1213 node.value = readValues ? s.readObject() : "";
1214 node = successor(node);
1215 }
1216 }
1217
1218 /**
1219 * Construct a tree from sorted keys in linear time, with values of "".
1220 * Package visible for use by TreeSet, which uses a value type of String.
1221 *
1222 * @param keys the iterator over the sorted keys
1223 * @param count the number of nodes to insert
1224 * @see TreeSet#TreeSet(SortedSet)
1225 */
1226 final void putKeysLinear(Iterator<K> keys, int count)
1227 {
1228 fabricateTree(count);
1229 Node<K,V> node = firstNode();
1230
1231 while (--count >= 0)
1232 {
1233 node.key = keys.next();
1234 node.value = (V) "";
1235 node = successor(node);
1236 }
1237 }
1238
1239 /**
1240 * Deserializes this object from the given stream.
1241 *
1242 * @param s the stream to read from
1243 * @throws ClassNotFoundException if the underlying stream fails
1244 * @throws IOException if the underlying stream fails
1245 * @serialData the <i>size</i> (int), followed by key (Object) and value
1246 * (Object) pairs in sorted order
1247 */
1248 private void readObject(ObjectInputStream s)
1249 throws IOException, ClassNotFoundException
1250 {
1251 s.defaultReadObject();
1252 int size = s.readInt();
1253 putFromObjStream(s, size, true);
1254 }
1255
1256 /**
1257 * Remove node from tree. This will increment modCount and decrement size.
1258 * Node must exist in the tree. Package visible for use by nested classes.
1259 *
1260 * @param node the node to remove
1261 */
1262 final void removeNode(Node<K,V> node)
1263 {
1264 Node<K,V> splice;
1265 Node<K,V> child;
1266
1267 modCount++;
1268 size--;
1269
1270 // Find splice, the node at the position to actually remove from the tree.
1271 if (node.left == nil)
1272 {
1273 // Node to be deleted has 0 or 1 children.
1274 splice = node;
1275 child = node.right;
1276 }
1277 else if (node.right == nil)
1278 {
1279 // Node to be deleted has 1 child.
1280 splice = node;
1281 child = node.left;
1282 }
1283 else
1284 {
1285 // Node has 2 children. Splice is node's predecessor, and we swap
1286 // its contents into node.
1287 splice = node.left;
1288 while (splice.right != nil)
1289 splice = splice.right;
1290 child = splice.left;
1291 node.key = splice.key;
1292 node.value = splice.value;
1293 }
1294
1295 // Unlink splice from the tree.
1296 Node parent = splice.parent;
1297 if (child != nil)
1298 child.parent = parent;
1299 if (parent == nil)
1300 {
1301 // Special case for 0 or 1 node remaining.
1302 root = child;
1303 return;
1304 }
1305 if (splice == parent.left)
1306 parent.left = child;
1307 else
1308 parent.right = child;
1309
1310 if (splice.color == BLACK)
1311 deleteFixup(child, parent);
1312 }
1313
1314 /**
1315 * Rotate node n to the left.
1316 *
1317 * @param node the node to rotate
1318 */
1319 private void rotateLeft(Node<K,V> node)
1320 {
1321 Node child = node.right;
1322 // if (node == nil || child == nil)
1323 // throw new InternalError();
1324
1325 // Establish node.right link.
1326 node.right = child.left;
1327 if (child.left != nil)
1328 child.left.parent = node;
1329
1330 // Establish child->parent link.
1331 child.parent = node.parent;
1332 if (node.parent != nil)
1333 {
1334 if (node == node.parent.left)
1335 node.parent.left = child;
1336 else
1337 node.parent.right = child;
1338 }
1339 else
1340 root = child;
1341
1342 // Link n and child.
1343 child.left = node;
1344 node.parent = child;
1345 }
1346
1347 /**
1348 * Rotate node n to the right.
1349 *
1350 * @param node the node to rotate
1351 */
1352 private void rotateRight(Node<K,V> node)
1353 {
1354 Node child = node.left;
1355 // if (node == nil || child == nil)
1356 // throw new InternalError();
1357
1358 // Establish node.left link.
1359 node.left = child.right;
1360 if (child.right != nil)
1361 child.right.parent = node;
1362
1363 // Establish child->parent link.
1364 child.parent = node.parent;
1365 if (node.parent != nil)
1366 {
1367 if (node == node.parent.right)
1368 node.parent.right = child;
1369 else
1370 node.parent.left = child;
1371 }
1372 else
1373 root = child;
1374
1375 // Link n and child.
1376 child.right = node;
1377 node.parent = child;
1378 }
1379
1380 /**
1381 * Return the node following the given one, or nil if there isn't one.
1382 * Package visible for use by nested classes.
1383 *
1384 * @param node the current node, not nil
1385 * @return the next node in sorted order
1386 */
1387 final Node<K,V> successor(Node<K,V> node)
1388 {
1389 if (node.right != nil)
1390 {
1391 node = node.right;
1392 while (node.left != nil)
1393 node = node.left;
1394 return node;
1395 }
1396
1397 Node<K,V> parent = node.parent;
1398 // Exploit fact that nil.right == nil and node is non-nil.
1399 while (node == parent.right)
1400 {
1401 node = parent;
1402 parent = parent.parent;
1403 }
1404 return parent;
1405 }
1406
1407 /**
1408 * Serializes this object to the given stream.
1409 *
1410 * @param s the stream to write to
1411 * @throws IOException if the underlying stream fails
1412 * @serialData the <i>size</i> (int), followed by key (Object) and value
1413 * (Object) pairs in sorted order
1414 */
1415 private void writeObject(ObjectOutputStream s) throws IOException
1416 {
1417 s.defaultWriteObject();
1418
1419 Node node = firstNode();
1420 s.writeInt(size);
1421 while (node != nil)
1422 {
1423 s.writeObject(node.key);
1424 s.writeObject(node.value);
1425 node = successor(node);
1426 }
1427 }
1428
1429 /**
1430 * Iterate over TreeMap's entries. This implementation is parameterized
1431 * to give a sequential view of keys, values, or entries.
1432 *
1433 * @author Eric Blake (ebb9@email.byu.edu)
1434 */
1435 private final class TreeIterator implements Iterator
1436 {
1437 /**
1438 * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
1439 * or {@link #ENTRIES}.
1440 */
1441 private final int type;
1442 /** The number of modifications to the backing Map that we know about. */
1443 private int knownMod = modCount;
1444 /** The last Entry returned by a next() call. */
1445 private Node last;
1446 /** The next entry that should be returned by next(). */
1447 private Node next;
1448 /**
1449 * The last node visible to this iterator. This is used when iterating
1450 * on a SubMap.
1451 */
1452 private final Node max;
1453
1454 /**
1455 * Construct a new TreeIterator with the supplied type.
1456 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1457 */
1458 TreeIterator(int type)
1459 {
1460 this(type, firstNode(), nil);
1461 }
1462
1463 /**
1464 * Construct a new TreeIterator with the supplied type. Iteration will
1465 * be from "first" (inclusive) to "max" (exclusive).
1466 *
1467 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1468 * @param first where to start iteration, nil for empty iterator
1469 * @param max the cutoff for iteration, nil for all remaining nodes
1470 */
1471 TreeIterator(int type, Node first, Node max)
1472 {
1473 this.type = type;
1474 this.next = first;
1475 this.max = max;
1476 }
1477
1478 /**
1479 * Returns true if the Iterator has more elements.
1480 * @return true if there are more elements
1481 */
1482 public boolean hasNext()
1483 {
1484 return next != max;
1485 }
1486
1487 /**
1488 * Returns the next element in the Iterator's sequential view.
1489 * @return the next element
1490 * @throws ConcurrentModificationException if the TreeMap was modified
1491 * @throws NoSuchElementException if there is none
1492 */
1493 public Object next()
1494 {
1495 if (knownMod != modCount)
1496 throw new ConcurrentModificationException();
1497 if (next == max)
1498 throw new NoSuchElementException();
1499 last = next;
1500 next = successor(last);
1501
1502 if (type == VALUES)
1503 return last.value;
1504 else if (type == KEYS)
1505 return last.key;
1506 return last;
1507 }
1508
1509 /**
1510 * Removes from the backing TreeMap the last element which was fetched
1511 * with the <code>next()</code> method.
1512 * @throws ConcurrentModificationException if the TreeMap was modified
1513 * @throws IllegalStateException if called when there is no last element
1514 */
1515 public void remove()
1516 {
1517 if (last == null)
1518 throw new IllegalStateException();
1519 if (knownMod != modCount)
1520 throw new ConcurrentModificationException();
1521
1522 removeNode(last);
1523 last = null;
1524 knownMod++;
1525 }
1526 } // class TreeIterator
1527
1528 /**
1529 * Implementation of {@link #subMap(Object, Object)} and other map
1530 * ranges. This class provides a view of a portion of the original backing
1531 * map, and throws {@link IllegalArgumentException} for attempts to
1532 * access beyond that range.
1533 *
1534 * @author Eric Blake (ebb9@email.byu.edu)
1535 */
1536 private final class SubMap
1537 extends AbstractMap<K,V>
1538 implements NavigableMap<K,V>
1539 {
1540 /**
1541 * The lower range of this view, inclusive, or nil for unbounded.
1542 * Package visible for use by nested classes.
1543 */
1544 final K minKey;
1545
1546 /**
1547 * The upper range of this view, exclusive, or nil for unbounded.
1548 * Package visible for use by nested classes.
1549 */
1550 final K maxKey;
1551
1552 /**
1553 * The cache for {@link #entrySet()}.
1554 */
1555 private Set<Map.Entry<K,V>> entries;
1556
1557 /**
1558 * The cache for {@link #descendingMap()}.
1559 */
1560 private NavigableMap<K,V> descendingMap;
1561
1562 /**
1563 * The cache for {@link #navigableKeySet()}.
1564 */
1565 private NavigableSet<K> nKeys;
1566
1567 /**
1568 * Create a SubMap representing the elements between minKey (inclusive)
1569 * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
1570 * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
1571 *
1572 * @param minKey the lower bound
1573 * @param maxKey the upper bound
1574 * @throws IllegalArgumentException if minKey > maxKey
1575 */
1576 SubMap(K minKey, K maxKey)
1577 {
1578 if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
1579 throw new IllegalArgumentException("fromKey > toKey");
1580 this.minKey = minKey;
1581 this.maxKey = maxKey;
1582 }
1583
1584 /**
1585 * Check if "key" is in within the range bounds for this SubMap. The
1586 * lower ("from") SubMap range is inclusive, and the upper ("to") bound
1587 * is exclusive. Package visible for use by nested classes.
1588 *
1589 * @param key the key to check
1590 * @return true if the key is in range
1591 */
1592 boolean keyInRange(K key)
1593 {
1594 return ((minKey == nil || compare(key, minKey) >= 0)
1595 && (maxKey == nil || compare(key, maxKey) < 0));
1596 }
1597
1598 public Entry<K,V> ceilingEntry(K key)
1599 {
1600 Entry<K,V> n = TreeMap.this.ceilingEntry(key);
1601 if (n != null && keyInRange(n.getKey()))
1602 return n;
1603 return null;
1604 }
1605
1606 public K ceilingKey(K key)
1607 {
1608 K found = TreeMap.this.ceilingKey(key);
1609 if (keyInRange(found))
1610 return found;
1611 else
1612 return null;
1613 }
1614
1615 public NavigableSet<K> descendingKeySet()
1616 {
1617 return descendingMap().navigableKeySet();
1618 }
1619
1620 public NavigableMap<K,V> descendingMap()
1621 {
1622 if (descendingMap == null)
1623 descendingMap = new DescendingMap(this);
1624 return descendingMap;
1625 }
1626
1627 public void clear()
1628 {
1629 Node next = lowestGreaterThan(minKey, true);
1630 Node max = lowestGreaterThan(maxKey, false);
1631 while (next != max)
1632 {
1633 Node current = next;
1634 next = successor(current);
1635 removeNode(current);
1636 }
1637 }
1638
1639 public Comparator<? super K> comparator()
1640 {
1641 return comparator;
1642 }
1643
1644 public boolean containsKey(Object key)
1645 {
1646 return keyInRange((K) key) && TreeMap.this.containsKey(key);
1647 }
1648
1649 public boolean containsValue(Object value)
1650 {
1651 Node node = lowestGreaterThan(minKey, true);
1652 Node max = lowestGreaterThan(maxKey, false);
1653 while (node != max)
1654 {
1655 if (equals(value, node.getValue()))
1656 return true;
1657 node = successor(node);
1658 }
1659 return false;
1660 }
1661
1662 public Set<Map.Entry<K,V>> entrySet()
1663 {
1664 if (entries == null)
1665 // Create an AbstractSet with custom implementations of those methods
1666 // that can be overriden easily and efficiently.
1667 entries = new SubMap.NavigableEntrySet();
1668 return entries;
1669 }
1670
1671 public Entry<K,V> firstEntry()
1672 {
1673 Node<K,V> node = lowestGreaterThan(minKey, true);
1674 if (node == nil || ! keyInRange(node.key))
1675 return null;
1676 return node;
1677 }
1678
1679 public K firstKey()
1680 {
1681 Entry<K,V> e = firstEntry();
1682 if (e == null)
1683 throw new NoSuchElementException();
1684 return e.getKey();
1685 }
1686
1687 public Entry<K,V> floorEntry(K key)
1688 {
1689 Entry<K,V> n = TreeMap.this.floorEntry(key);
1690 if (n != null && keyInRange(n.getKey()))
1691 return n;
1692 return null;
1693 }
1694
1695 public K floorKey(K key)
1696 {
1697 K found = TreeMap.this.floorKey(key);
1698 if (keyInRange(found))
1699 return found;
1700 else
1701 return null;
1702 }
1703
1704 public V get(Object key)
1705 {
1706 if (keyInRange((K) key))
1707 return TreeMap.this.get(key);
1708 return null;
1709 }
1710
1711 public SortedMap<K,V> headMap(K toKey)
1712 {
1713 return headMap(toKey, false);
1714 }
1715
1716 public NavigableMap<K,V> headMap(K toKey, boolean inclusive)
1717 {
1718 if (!keyInRange(toKey))
1719 throw new IllegalArgumentException("Key outside submap range");
1720 return new SubMap(minKey, (inclusive ?
1721 successor(getNode(toKey)).key : toKey));
1722 }
1723
1724 public Set<K> keySet()
1725 {
1726 if (this.keys == null)
1727 // Create an AbstractSet with custom implementations of those methods
1728 // that can be overriden easily and efficiently.
1729 this.keys = new SubMap.KeySet();
1730 return this.keys;
1731 }
1732
1733 public Entry<K,V> higherEntry(K key)
1734 {
1735 Entry<K,V> n = TreeMap.this.higherEntry(key);
1736 if (n != null && keyInRange(n.getKey()))
1737 return n;
1738 return null;
1739 }
1740
1741 public K higherKey(K key)
1742 {
1743 K found = TreeMap.this.higherKey(key);
1744 if (keyInRange(found))
1745 return found;
1746 else
1747 return null;
1748 }
1749
1750 public Entry<K,V> lastEntry()
1751 {
1752 return lowerEntry(maxKey);
1753 }
1754
1755 public K lastKey()
1756 {
1757 Entry<K,V> e = lastEntry();
1758 if (e == null)
1759 throw new NoSuchElementException();
1760 return e.getKey();
1761 }
1762
1763 public Entry<K,V> lowerEntry(K key)
1764 {
1765 Entry<K,V> n = TreeMap.this.lowerEntry(key);
1766 if (n != null && keyInRange(n.getKey()))
1767 return n;
1768 return null;
1769 }
1770
1771 public K lowerKey(K key)
1772 {
1773 K found = TreeMap.this.lowerKey(key);
1774 if (keyInRange(found))
1775 return found;
1776 else
1777 return null;
1778 }
1779
1780 public NavigableSet<K> navigableKeySet()
1781 {
1782 if (this.nKeys == null)
1783 // Create an AbstractSet with custom implementations of those methods
1784 // that can be overriden easily and efficiently.
1785 this.nKeys = new SubMap.NavigableKeySet();
1786 return this.nKeys;
1787 }
1788
1789 public Entry<K,V> pollFirstEntry()
1790 {
1791 Entry<K,V> e = firstEntry();
1792 if (e != null)
1793 removeNode((Node<K,V>) e);
1794 return e;
1795 }
1796
1797 public Entry<K,V> pollLastEntry()
1798 {
1799 Entry<K,V> e = lastEntry();
1800 if (e != null)
1801 removeNode((Node<K,V>) e);
1802 return e;
1803 }
1804
1805 public V put(K key, V value)
1806 {
1807 if (! keyInRange(key))
1808 throw new IllegalArgumentException("Key outside range");
1809 return TreeMap.this.put(key, value);
1810 }
1811
1812 public V remove(Object key)
1813 {
1814 if (keyInRange((K)key))
1815 return TreeMap.this.remove(key);
1816 return null;
1817 }
1818
1819 public int size()
1820 {
1821 Node node = lowestGreaterThan(minKey, true);
1822 Node max = lowestGreaterThan(maxKey, false);
1823 int count = 0;
1824 while (node != max)
1825 {
1826 count++;
1827 node = successor(node);
1828 }
1829 return count;
1830 }
1831
1832 public SortedMap<K,V> subMap(K fromKey, K toKey)
1833 {
1834 return subMap(fromKey, true, toKey, false);
1835 }
1836
1837 public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
1838 K toKey, boolean toInclusive)
1839 {
1840 if (! keyInRange(fromKey) || ! keyInRange(toKey))
1841 throw new IllegalArgumentException("key outside range");
1842 return new SubMap(fromInclusive ? fromKey : successor(getNode(fromKey)).key,
1843 toInclusive ? successor(getNode(toKey)).key : toKey);
1844 }
1845
1846 public SortedMap<K, V> tailMap(K fromKey)
1847 {
1848 return tailMap(fromKey, true);
1849 }
1850
1851 public NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)
1852 {
1853 if (! keyInRange(fromKey))
1854 throw new IllegalArgumentException("key outside range");
1855 return new SubMap(inclusive ? fromKey : successor(getNode(fromKey)).key,
1856 maxKey);
1857 }
1858
1859 public Collection<V> values()
1860 {
1861 if (this.values == null)
1862 // Create an AbstractCollection with custom implementations of those
1863 // methods that can be overriden easily and efficiently.
1864 this.values = new AbstractCollection()
1865 {
1866 public int size()
1867 {
1868 return SubMap.this.size();
1869 }
1870
1871 public Iterator<V> iterator()
1872 {
1873 Node first = lowestGreaterThan(minKey, true);
1874 Node max = lowestGreaterThan(maxKey, false);
1875 return new TreeIterator(VALUES, first, max);
1876 }
1877
1878 public void clear()
1879 {
1880 SubMap.this.clear();
1881 }
1882 };
1883 return this.values;
1884 }
1885
1886 private class KeySet
1887 extends AbstractSet<K>
1888 {
1889 public int size()
1890 {
1891 return SubMap.this.size();
1892 }
1893
1894 public Iterator<K> iterator()
1895 {
1896 Node first = lowestGreaterThan(minKey, true);
1897 Node max = lowestGreaterThan(maxKey, false);
1898 return new TreeIterator(KEYS, first, max);
1899 }
1900
1901 public void clear()
1902 {
1903 SubMap.this.clear();
1904 }
1905
1906 public boolean contains(Object o)
1907 {
1908 if (! keyInRange((K) o))
1909 return false;
1910 return getNode((K) o) != nil;
1911 }
1912
1913 public boolean remove(Object o)
1914 {
1915 if (! keyInRange((K) o))
1916 return false;
1917 Node n = getNode((K) o);
1918 if (n != nil)
1919 {
1920 removeNode(n);
1921 return true;
1922 }
1923 return false;
1924 }
1925
1926 } // class SubMap.KeySet
1927
1928 private final class NavigableKeySet
1929 extends KeySet
1930 implements NavigableSet<K>
1931 {
1932
1933 public K ceiling(K k)
1934 {
1935 return SubMap.this.ceilingKey(k);
1936 }
1937
1938 public Comparator<? super K> comparator()
1939 {
1940 return comparator;
1941 }
1942
1943 public Iterator<K> descendingIterator()
1944 {
1945 return descendingSet().iterator();
1946 }
1947
1948 public NavigableSet<K> descendingSet()
1949 {
1950 return new DescendingSet(this);
1951 }
1952
1953 public K first()
1954 {
1955 return SubMap.this.firstKey();
1956 }
1957
1958 public K floor(K k)
1959 {
1960 return SubMap.this.floorKey(k);
1961 }
1962
1963 public SortedSet<K> headSet(K to)
1964 {
1965 return headSet(to, false);
1966 }
1967
1968 public NavigableSet<K> headSet(K to, boolean inclusive)
1969 {
1970 return SubMap.this.headMap(to, inclusive).navigableKeySet();
1971 }
1972
1973 public K higher(K k)
1974 {
1975 return SubMap.this.higherKey(k);
1976 }
1977
1978 public K last()
1979 {
1980 return SubMap.this.lastKey();
1981 }
1982
1983 public K lower(K k)
1984 {
1985 return SubMap.this.lowerKey(k);
1986 }
1987
1988 public K pollFirst()
1989 {
1990 return SubMap.this.pollFirstEntry().getKey();
1991 }
1992
1993 public K pollLast()
1994 {
1995 return SubMap.this.pollLastEntry().getKey();
1996 }
1997
1998 public SortedSet<K> subSet(K from, K to)
1999 {
2000 return subSet(from, true, to, false);
2001 }
2002
2003 public NavigableSet<K> subSet(K from, boolean fromInclusive,
2004 K to, boolean toInclusive)
2005 {
2006 return SubMap.this.subMap(from, fromInclusive,
2007 to, toInclusive).navigableKeySet();
2008 }
2009
2010 public SortedSet<K> tailSet(K from)
2011 {
2012 return tailSet(from, true);
2013 }
2014
2015 public NavigableSet<K> tailSet(K from, boolean inclusive)
2016 {
2017 return SubMap.this.tailMap(from, inclusive).navigableKeySet();
2018 }
2019
2020 } // class SubMap.NavigableKeySet
2021
2022 /**
2023 * Implementation of {@link #entrySet()}.
2024 */
2025 private class EntrySet
2026 extends AbstractSet<Entry<K,V>>
2027 {
2028
2029 public int size()
2030 {
2031 return SubMap.this.size();
2032 }
2033
2034 public Iterator<Map.Entry<K,V>> iterator()
2035 {
2036 Node first = lowestGreaterThan(minKey, true);
2037 Node max = lowestGreaterThan(maxKey, false);
2038 return new TreeIterator(ENTRIES, first, max);
2039 }
2040
2041 public void clear()
2042 {
2043 SubMap.this.clear();
2044 }
2045
2046 public boolean contains(Object o)
2047 {
2048 if (! (o instanceof Map.Entry))
2049 return false;
2050 Map.Entry<K,V> me = (Map.Entry<K,V>) o;
2051 K key = me.getKey();
2052 if (! keyInRange(key))
2053 return false;
2054 Node<K,V> n = getNode(key);
2055 return n != nil && AbstractSet.equals(me.getValue(), n.value);
2056 }
2057
2058 public boolean remove(Object o)
2059 {
2060 if (! (o instanceof Map.Entry))
2061 return false;
2062 Map.Entry<K,V> me = (Map.Entry<K,V>) o;
2063 K key = me.getKey();
2064 if (! keyInRange(key))
2065 return false;
2066 Node<K,V> n = getNode(key);
2067 if (n != nil && AbstractSet.equals(me.getValue(), n.value))
2068 {
2069 removeNode(n);
2070 return true;
2071 }
2072 return false;
2073 }
2074 } // class SubMap.EntrySet
2075
2076 private final class NavigableEntrySet
2077 extends EntrySet
2078 implements NavigableSet<Entry<K,V>>
2079 {
2080
2081 public Entry<K,V> ceiling(Entry<K,V> e)
2082 {
2083 return SubMap.this.ceilingEntry(e.getKey());
2084 }
2085
2086 public Comparator<? super Entry<K,V>> comparator()
2087 {
2088 return new Comparator<Entry<K,V>>()
2089 {
2090 public int compare(Entry<K,V> t1, Entry<K,V> t2)
2091 {
2092 return comparator.compare(t1.getKey(), t2.getKey());
2093 }
2094 };
2095 }
2096
2097 public Iterator<Entry<K,V>> descendingIterator()
2098 {
2099 return descendingSet().iterator();
2100 }
2101
2102 public NavigableSet<Entry<K,V>> descendingSet()
2103 {
2104 return new DescendingSet(this);
2105 }
2106
2107 public Entry<K,V> first()
2108 {
2109 return SubMap.this.firstEntry();
2110 }
2111
2112 public Entry<K,V> floor(Entry<K,V> e)
2113 {
2114 return SubMap.this.floorEntry(e.getKey());
2115 }
2116
2117 public SortedSet<Entry<K,V>> headSet(Entry<K,V> to)
2118 {
2119 return headSet(to, false);
2120 }
2121
2122 public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive)
2123 {
2124 return (NavigableSet<Entry<K,V>>)
2125 SubMap.this.headMap(to.getKey(), inclusive).entrySet();
2126 }
2127
2128 public Entry<K,V> higher(Entry<K,V> e)
2129 {
2130 return SubMap.this.higherEntry(e.getKey());
2131 }
2132
2133 public Entry<K,V> last()
2134 {
2135 return SubMap.this.lastEntry();
2136 }
2137
2138 public Entry<K,V> lower(Entry<K,V> e)
2139 {
2140 return SubMap.this.lowerEntry(e.getKey());
2141 }
2142
2143 public Entry<K,V> pollFirst()
2144 {
2145 return SubMap.this.pollFirstEntry();
2146 }
2147
2148 public Entry<K,V> pollLast()
2149 {
2150 return SubMap.this.pollLastEntry();
2151 }
2152
2153 public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to)
2154 {
2155 return subSet(from, true, to, false);
2156 }
2157
2158 public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive,
2159 Entry<K,V> to, boolean toInclusive)
2160 {
2161 return (NavigableSet<Entry<K,V>>)
2162 SubMap.this.subMap(from.getKey(), fromInclusive,
2163 to.getKey(), toInclusive).entrySet();
2164 }
2165
2166 public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from)
2167 {
2168 return tailSet(from, true);
2169 }
2170
2171 public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
2172 {
2173 return (NavigableSet<Entry<K,V>>)
2174 SubMap.this.tailMap(from.getKey(), inclusive).navigableKeySet();
2175 }
2176
2177 } // class SubMap.NavigableEntrySet
2178
2179 } // class SubMap
2180
2181 /**
2182 * Returns the entry associated with the least or lowest key
2183 * that is greater than or equal to the specified key, or
2184 * <code>null</code> if there is no such key.
2185 *
2186 * @param key the key relative to the returned entry.
2187 * @return the entry with the least key greater than or equal
2188 * to the given key, or <code>null</code> if there is
2189 * no such key.
2190 * @throws ClassCastException if the specified key can not
2191 * be compared with those in the map.
2192 * @throws NullPointerException if the key is <code>null</code>
2193 * and this map either uses natural
2194 * ordering or a comparator that does
2195 * not permit null keys.
2196 * @since 1.6
2197 */
2198 public Entry<K,V> ceilingEntry(K key)
2199 {
2200 Node<K,V> n = lowestGreaterThan(key, false);
2201 return (n == nil) ? null : n;
2202 }
2203
2204 /**
2205 * Returns the the least or lowest key that is greater than
2206 * or equal to the specified key, or <code>null</code> if
2207 * there is no such key.
2208 *
2209 * @param key the key relative to the returned entry.
2210 * @return the least key greater than or equal to the given key,
2211 * or <code>null</code> if there is no such key.
2212 * @throws ClassCastException if the specified key can not
2213 * be compared with those in the map.
2214 * @throws NullPointerException if the key is <code>null</code>
2215 * and this map either uses natural
2216 * ordering or a comparator that does
2217 * not permit null keys.
2218 * @since 1.6
2219 */
2220 public K ceilingKey(K key)
2221 {
2222 Entry<K,V> e = ceilingEntry(key);
2223 return (e == null) ? null : e.getKey();
2224 }
2225
2226 /**
2227 * Returns a reverse ordered {@link NavigableSet} view of this
2228 * map's keys. The set is backed by the {@link TreeMap}, so changes
2229 * in one show up in the other. The set supports element removal,
2230 * but not element addition.
2231 *
2232 * @return a reverse ordered set view of the keys.
2233 * @since 1.6
2234 * @see #descendingMap()
2235 */
2236 public NavigableSet<K> descendingKeySet()
2237 {
2238 return descendingMap().navigableKeySet();
2239 }
2240
2241 /**
2242 * Returns a view of the map in reverse order. The descending map
2243 * is backed by the original map, so that changes affect both maps.
2244 * Any changes occurring to either map while an iteration is taking
2245 * place (with the exception of a {@link Iterator#remove()} operation)
2246 * result in undefined behaviour from the iteration. The ordering
2247 * of the descending map is the same as for a map with a
2248 * {@link Comparator} given by {@link Collections#reverseOrder()},
2249 * and calling {@link #descendingMap()} on the descending map itself
2250 * results in a view equivalent to the original map.
2251 *
2252 * @return a reverse order view of the map.
2253 * @since 1.6
2254 */
2255 public NavigableMap<K,V> descendingMap()
2256 {
2257 if (descendingMap == null)
2258 descendingMap = new DescendingMap<K,V>(this);
2259 return descendingMap;
2260 }
2261
2262 /**
2263 * Returns the entry associated with the least or lowest key
2264 * in the map, or <code>null</code> if the map is empty.
2265 *
2266 * @return the lowest entry, or <code>null</code> if the map
2267 * is empty.
2268 * @since 1.6
2269 */
2270 public Entry<K,V> firstEntry()
2271 {
2272 Node<K,V> n = firstNode();
2273 return (n == nil) ? null : n;
2274 }
2275
2276 /**
2277 * Returns the entry associated with the greatest or highest key
2278 * that is less than or equal to the specified key, or
2279 * <code>null</code> if there is no such key.
2280 *
2281 * @param key the key relative to the returned entry.
2282 * @return the entry with the greatest key less than or equal
2283 * to the given key, or <code>null</code> if there is
2284 * no such key.
2285 * @throws ClassCastException if the specified key can not
2286 * be compared with those in the map.
2287 * @throws NullPointerException if the key is <code>null</code>
2288 * and this map either uses natural
2289 * ordering or a comparator that does
2290 * not permit null keys.
2291 * @since 1.6
2292 */
2293 public Entry<K,V> floorEntry(K key)
2294 {
2295 Node<K,V> n = highestLessThan(key, true);
2296 return (n == nil) ? null : n;
2297 }
2298
2299 /**
2300 * Returns the the greatest or highest key that is less than
2301 * or equal to the specified key, or <code>null</code> if
2302 * there is no such key.
2303 *
2304 * @param key the key relative to the returned entry.
2305 * @return the greatest key less than or equal to the given key,
2306 * or <code>null</code> if there is no such key.
2307 * @throws ClassCastException if the specified key can not
2308 * be compared with those in the map.
2309 * @throws NullPointerException if the key is <code>null</code>
2310 * and this map either uses natural
2311 * ordering or a comparator that does
2312 * not permit null keys.
2313 * @since 1.6
2314 */
2315 public K floorKey(K key)
2316 {
2317 Entry<K,V> e = floorEntry(key);
2318 return (e == null) ? null : e.getKey();
2319 }
2320
2321 /**
2322 * Returns the entry associated with the least or lowest key
2323 * that is strictly greater than the specified key, or
2324 * <code>null</code> if there is no such key.
2325 *
2326 * @param key the key relative to the returned entry.
2327 * @return the entry with the least key greater than
2328 * the given key, or <code>null</code> if there is
2329 * no such key.
2330 * @throws ClassCastException if the specified key can not
2331 * be compared with those in the map.
2332 * @throws NullPointerException if the key is <code>null</code>
2333 * and this map either uses natural
2334 * ordering or a comparator that does
2335 * not permit null keys.
2336 * @since 1.6
2337 */
2338 public Entry<K,V> higherEntry(K key)
2339 {
2340 Node<K,V> n = lowestGreaterThan(key, false, false);
2341 return (n == nil) ? null : n;
2342 }
2343
2344 /**
2345 * Returns the the least or lowest key that is strictly
2346 * greater than the specified key, or <code>null</code> if
2347 * there is no such key.
2348 *
2349 * @param key the key relative to the returned entry.
2350 * @return the least key greater than the given key,
2351 * or <code>null</code> if there is no such key.
2352 * @throws ClassCastException if the specified key can not
2353 * be compared with those in the map.
2354 * @throws NullPointerException if the key is <code>null</code>
2355 * and this map either uses natural
2356 * ordering or a comparator that does
2357 * not permit null keys.
2358 * @since 1.6
2359 */
2360 public K higherKey(K key)
2361 {
2362 Entry<K,V> e = higherEntry(key);
2363 return (e == null) ? null : e.getKey();
2364 }
2365
2366 /**
2367 * Returns the entry associated with the greatest or highest key
2368 * in the map, or <code>null</code> if the map is empty.
2369 *
2370 * @return the highest entry, or <code>null</code> if the map
2371 * is empty.
2372 * @since 1.6
2373 */
2374 public Entry<K,V> lastEntry()
2375 {
2376 Node<K,V> n = lastNode();
2377 return (n == nil) ? null : n;
2378 }
2379
2380 /**
2381 * Returns the entry associated with the greatest or highest key
2382 * that is strictly less than the specified key, or
2383 * <code>null</code> if there is no such key.
2384 *
2385 * @param key the key relative to the returned entry.
2386 * @return the entry with the greatest key less than
2387 * the given key, or <code>null</code> if there is
2388 * no such key.
2389 * @throws ClassCastException if the specified key can not
2390 * be compared with those in the map.
2391 * @throws NullPointerException if the key is <code>null</code>
2392 * and this map either uses natural
2393 * ordering or a comparator that does
2394 * not permit null keys.
2395 * @since 1.6
2396 */
2397 public Entry<K,V> lowerEntry(K key)
2398 {
2399 Node<K,V> n = highestLessThan(key);
2400 return (n == nil) ? null : n;
2401 }
2402
2403 /**
2404 * Returns the the greatest or highest key that is strictly
2405 * less than the specified key, or <code>null</code> if
2406 * there is no such key.
2407 *
2408 * @param key the key relative to the returned entry.
2409 * @return the greatest key less than the given key,
2410 * or <code>null</code> if there is no such key.
2411 * @throws ClassCastException if the specified key can not
2412 * be compared with those in the map.
2413 * @throws NullPointerException if the key is <code>null</code>
2414 * and this map either uses natural
2415 * ordering or a comparator that does
2416 * not permit null keys.
2417 * @since 1.6
2418 */
2419 public K lowerKey(K key)
2420 {
2421 Entry<K,V> e = lowerEntry(key);
2422 return (e == null) ? null : e.getKey();
2423 }
2424
2425 /**
2426 * Returns a {@link NavigableSet} view of this map's keys. The set is
2427 * backed by the {@link TreeMap}, so changes in one show up in the other.
2428 * Any changes occurring to either while an iteration is taking
2429 * place (with the exception of a {@link Iterator#remove()} operation)
2430 * result in undefined behaviour from the iteration. The ordering
2431 * The set supports element removal, but not element addition.
2432 *
2433 * @return a {@link NavigableSet} view of the keys.
2434 * @since 1.6
2435 */
2436 public NavigableSet<K> navigableKeySet()
2437 {
2438 if (nKeys == null)
2439 nKeys = new NavigableKeySet();
2440 return nKeys;
2441 }
2442
2443 /**
2444 * Removes and returns the entry associated with the least
2445 * or lowest key in the map, or <code>null</code> if the map
2446 * is empty.
2447 *
2448 * @return the removed first entry, or <code>null</code> if the
2449 * map is empty.
2450 * @since 1.6
2451 */
2452 public Entry<K,V> pollFirstEntry()
2453 {
2454 Entry<K,V> e = firstEntry();
2455 if (e != null)
2456 removeNode((Node<K,V>)e);
2457 return e;
2458 }
2459
2460 /**
2461 * Removes and returns the entry associated with the greatest
2462 * or highest key in the map, or <code>null</code> if the map
2463 * is empty.
2464 *
2465 * @return the removed last entry, or <code>null</code> if the
2466 * map is empty.
2467 * @since 1.6
2468 */
2469 public Entry<K,V> pollLastEntry()
2470 {
2471 Entry<K,V> e = lastEntry();
2472 if (e != null)
2473 removeNode((Node<K,V>)e);
2474 return e;
2475 }
2476
2477 /**
2478 * Implementation of {@link #descendingMap()} and associated
2479 * derivatives. This class provides a view of the
2480 * original backing map in reverse order, and throws
2481 * {@link IllegalArgumentException} for attempts to
2482 * access beyond that range.
2483 *
2484 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
2485 */
2486 private static final class DescendingMap<DK,DV>
2487 implements NavigableMap<DK,DV>
2488 {
2489
2490 /**
2491 * The cache for {@link #entrySet()}.
2492 */
2493 private Set<Map.Entry<DK,DV>> entries;
2494
2495 /**
2496 * The cache for {@link #keySet()}.
2497 */
2498 private Set<DK> keys;
2499
2500 /**
2501 * The cache for {@link #navigableKeySet()}.
2502 */
2503 private NavigableSet<DK> nKeys;
2504
2505 /**
2506 * The cache for {@link #values()}.
2507 */
2508 private Collection<DV> values;
2509
2510 /**
2511 * The backing {@link NavigableMap}.
2512 */
2513 private NavigableMap<DK,DV> map;
2514
2515 /**
2516 * Create a {@link DescendingMap} around the specified
2517 * map.
2518 *
2519 * @param map the map to wrap.
2520 */
2521 public DescendingMap(NavigableMap<DK,DV> map)
2522 {
2523 this.map = map;
2524 }
2525
2526 public Map.Entry<DK,DV> ceilingEntry(DK key)
2527 {
2528 return map.floorEntry(key);
2529 }
2530
2531 public DK ceilingKey(DK key)
2532 {
2533 return map.floorKey(key);
2534 }
2535
2536 public void clear()
2537 {
2538 map.clear();
2539 }
2540
2541 public Comparator<? super DK> comparator()
2542 {
2543 return Collections.reverseOrder(map.comparator());
2544 }
2545
2546 public boolean containsKey(Object o)
2547 {
2548 return map.containsKey(o);
2549 }
2550
2551 public boolean containsValue(Object o)
2552 {
2553 return map.containsValue(o);
2554 }
2555
2556 public NavigableSet<DK> descendingKeySet()
2557 {
2558 return descendingMap().navigableKeySet();
2559 }
2560
2561 public NavigableMap<DK,DV> descendingMap()
2562 {
2563 return map;
2564 }
2565
2566 public Set<Entry<DK,DV>> entrySet()
2567 {
2568 if (entries == null)
2569 entries =
2570 new DescendingSet<Entry<DK,DV>>((NavigableSet<Entry<DK,DV>>)
2571 map.entrySet());
2572 return entries;
2573 }
2574
2575 public boolean equals(Object o)
2576 {
2577 return map.equals(o);
2578 }
2579
2580 public Entry<DK,DV> firstEntry()
2581 {
2582 return map.lastEntry();
2583 }
2584
2585 public DK firstKey()
2586 {
2587 return map.lastKey();
2588 }
2589
2590 public Entry<DK,DV> floorEntry(DK key)
2591 {
2592 return map.ceilingEntry(key);
2593 }
2594
2595 public DK floorKey(DK key)
2596 {
2597 return map.ceilingKey(key);
2598 }
2599
2600 public DV get(Object key)
2601 {
2602 return map.get(key);
2603 }
2604
2605 public int hashCode()
2606 {
2607 return map.hashCode();
2608 }
2609
2610 public SortedMap<DK,DV> headMap(DK toKey)
2611 {
2612 return headMap(toKey, false);
2613 }
2614
2615 public NavigableMap<DK,DV> headMap(DK toKey, boolean inclusive)
2616 {
2617 return new DescendingMap(map.tailMap(toKey, inclusive));
2618 }
2619
2620 public Entry<DK,DV> higherEntry(DK key)
2621 {
2622 return map.lowerEntry(key);
2623 }
2624
2625 public DK higherKey(DK key)
2626 {
2627 return map.lowerKey(key);
2628 }
2629
2630 public Set<DK> keySet()
2631 {
2632 if (keys == null)
2633 keys = new DescendingSet<DK>(map.navigableKeySet());
2634 return keys;
2635 }
2636
2637 public boolean isEmpty()
2638 {
2639 return map.isEmpty();
2640 }
2641
2642 public Entry<DK,DV> lastEntry()
2643 {
2644 return map.firstEntry();
2645 }
2646
2647 public DK lastKey()
2648 {
2649 return map.firstKey();
2650 }
2651
2652 public Entry<DK,DV> lowerEntry(DK key)
2653 {
2654 return map.higherEntry(key);
2655 }
2656
2657 public DK lowerKey(DK key)
2658 {
2659 return map.higherKey(key);
2660 }
2661
2662 public NavigableSet<DK> navigableKeySet()
2663 {
2664 if (nKeys == null)
2665 nKeys = new DescendingSet<DK>(map.navigableKeySet());
2666 return nKeys;
2667 }
2668
2669 public Entry<DK,DV> pollFirstEntry()
2670 {
2671 return pollLastEntry();
2672 }
2673
2674 public Entry<DK,DV> pollLastEntry()
2675 {
2676 return pollFirstEntry();
2677 }
2678
2679 public DV put(DK key, DV value)
2680 {
2681 return map.put(key, value);
2682 }
2683
2684 public void putAll(Map<? extends DK, ? extends DV> m)
2685 {
2686 map.putAll(m);
2687 }
2688
2689 public DV remove(Object key)
2690 {
2691 return map.remove(key);
2692 }
2693
2694 public int size()
2695 {
2696 return map.size();
2697 }
2698
2699 public SortedMap<DK,DV> subMap(DK fromKey, DK toKey)
2700 {
2701 return subMap(fromKey, true, toKey, false);
2702 }
2703
2704 public NavigableMap<DK,DV> subMap(DK fromKey, boolean fromInclusive,
2705 DK toKey, boolean toInclusive)
2706 {
2707 return new DescendingMap(map.subMap(fromKey, fromInclusive,
2708 toKey, toInclusive));
2709 }
2710
2711 public SortedMap<DK,DV> tailMap(DK fromKey)
2712 {
2713 return tailMap(fromKey, true);
2714 }
2715
2716 public NavigableMap<DK,DV> tailMap(DK fromKey, boolean inclusive)
2717 {
2718 return new DescendingMap(map.headMap(fromKey, inclusive));
2719 }
2720
2721 public String toString()
2722 {
2723 StringBuilder r = new StringBuilder("{");
2724 final Iterator<Entry<DK,DV>> it = entrySet().iterator();
2725 while (it.hasNext())
2726 {
2727 final Entry<DK,DV> e = it.next();
2728 r.append(e.getKey());
2729 r.append('=');
2730 r.append(e.getValue());
2731 r.append(", ");
2732 }
2733 r.replace(r.length() - 2, r.length(), "}");
2734 return r.toString();
2735 }
2736
2737 public Collection<DV> values()
2738 {
2739 if (values == null)
2740 // Create an AbstractCollection with custom implementations of those
2741 // methods that can be overriden easily and efficiently.
2742 values = new AbstractCollection()
2743 {
2744 public int size()
2745 {
2746 return size();
2747 }
2748
2749 public Iterator<DV> iterator()
2750 {
2751 return new Iterator<DV>()
2752 {
2753 /** The last Entry returned by a next() call. */
2754 private Entry<DK,DV> last;
2755
2756 /** The next entry that should be returned by next(). */
2757 private Entry<DK,DV> next = firstEntry();
2758
2759 public boolean hasNext()
2760 {
2761 return next != null;
2762 }
2763
2764 public DV next()
2765 {
2766 if (next == null)
2767 throw new NoSuchElementException();
2768 last = next;
2769 next = higherEntry(last.getKey());
2770
2771 return last.getValue();
2772 }
2773
2774 public void remove()
2775 {
2776 if (last == null)
2777 throw new IllegalStateException();
2778
2779 DescendingMap.this.remove(last.getKey());
2780 last = null;
2781 }
2782 };
2783 }
2784
2785 public void clear()
2786 {
2787 clear();
2788 }
2789 };
2790 return values;
2791 }
2792
2793 } // class DescendingMap
2794
2795 /**
2796 * Implementation of {@link #keySet()}.
2797 */
2798 private class KeySet
2799 extends AbstractSet<K>
2800 {
2801
2802 public int size()
2803 {
2804 return size;
2805 }
2806
2807 public Iterator<K> iterator()
2808 {
2809 return new TreeIterator(KEYS);
2810 }
2811
2812 public void clear()
2813 {
2814 TreeMap.this.clear();
2815 }
2816
2817 public boolean contains(Object o)
2818 {
2819 return containsKey(o);
2820 }
2821
2822 public boolean remove(Object key)
2823 {
2824 Node<K,V> n = getNode((K) key);
2825 if (n == nil)
2826 return false;
2827 removeNode(n);
2828 return true;
2829 }
2830 } // class KeySet
2831
2832 /**
2833 * Implementation of {@link #navigableKeySet()}.
2834 *
2835 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
2836 */
2837 private final class NavigableKeySet
2838 extends KeySet
2839 implements NavigableSet<K>
2840 {
2841
2842 public K ceiling(K k)
2843 {
2844 return ceilingKey(k);
2845 }
2846
2847 public Comparator<? super K> comparator()
2848 {
2849 return comparator;
2850 }
2851
2852 public Iterator<K> descendingIterator()
2853 {
2854 return descendingSet().iterator();
2855 }
2856
2857 public NavigableSet<K> descendingSet()
2858 {
2859 return new DescendingSet<K>(this);
2860 }
2861
2862 public K first()
2863 {
2864 return firstKey();
2865 }
2866
2867 public K floor(K k)
2868 {
2869 return floorKey(k);
2870 }
2871
2872 public SortedSet<K> headSet(K to)
2873 {
2874 return headSet(to, false);
2875 }
2876
2877 public NavigableSet<K> headSet(K to, boolean inclusive)
2878 {
2879 return headMap(to, inclusive).navigableKeySet();
2880 }
2881
2882 public K higher(K k)
2883 {
2884 return higherKey(k);
2885 }
2886
2887 public K last()
2888 {
2889 return lastKey();
2890 }
2891
2892 public K lower(K k)
2893 {
2894 return lowerKey(k);
2895 }
2896
2897 public K pollFirst()
2898 {
2899 return pollFirstEntry().getKey();
2900 }
2901
2902 public K pollLast()
2903 {
2904 return pollLastEntry().getKey();
2905 }
2906
2907 public SortedSet<K> subSet(K from, K to)
2908 {
2909 return subSet(from, true, to, false);
2910 }
2911
2912 public NavigableSet<K> subSet(K from, boolean fromInclusive,
2913 K to, boolean toInclusive)
2914 {
2915 return subMap(from, fromInclusive,
2916 to, toInclusive).navigableKeySet();
2917 }
2918
2919 public SortedSet<K> tailSet(K from)
2920 {
2921 return tailSet(from, true);
2922 }
2923
2924 public NavigableSet<K> tailSet(K from, boolean inclusive)
2925 {
2926 return tailMap(from, inclusive).navigableKeySet();
2927 }
2928
2929
2930 } // class NavigableKeySet
2931
2932 /**
2933 * Implementation of {@link #descendingSet()} and associated
2934 * derivatives. This class provides a view of the
2935 * original backing set in reverse order, and throws
2936 * {@link IllegalArgumentException} for attempts to
2937 * access beyond that range.
2938 *
2939 * @author Andrew John Hughes (gnu_andrew@member.fsf.org)
2940 */
2941 private static final class DescendingSet<D>
2942 implements NavigableSet<D>
2943 {
2944
2945 /**
2946 * The backing {@link NavigableSet}.
2947 */
2948 private NavigableSet<D> set;
2949
2950 /**
2951 * Create a {@link DescendingSet} around the specified
2952 * set.
2953 *
2954 * @param map the set to wrap.
2955 */
2956 public DescendingSet(NavigableSet<D> set)
2957 {
2958 this.set = set;
2959 }
2960
2961 public boolean add(D e)
2962 {
2963 return set.add(e);
2964 }
2965
2966 public boolean addAll(Collection<? extends D> c)
2967 {
2968 return set.addAll(c);
2969 }
2970
2971 public D ceiling(D e)
2972 {
2973 return set.floor(e);
2974 }
2975
2976 public void clear()
2977 {
2978 set.clear();
2979 }
2980
2981 public Comparator<? super D> comparator()
2982 {
2983 return Collections.reverseOrder(set.comparator());
2984 }
2985
2986 public boolean contains(Object o)
2987 {
2988 return set.contains(o);
2989 }
2990
2991 public boolean containsAll(Collection<?> c)
2992 {
2993 return set.containsAll(c);
2994 }
2995
2996 public Iterator<D> descendingIterator()
2997 {
2998 return descendingSet().iterator();
2999 }
3000
3001 public NavigableSet<D> descendingSet()
3002 {
3003 return set;
3004 }
3005
3006 public boolean equals(Object o)
3007 {
3008 return set.equals(o);
3009 }
3010
3011 public D first()
3012 {
3013 return set.last();
3014 }
3015
3016 public D floor(D e)
3017 {
3018 return set.ceiling(e);
3019 }
3020
3021 public int hashCode()
3022 {
3023 return set.hashCode();
3024 }
3025
3026 public SortedSet<D> headSet(D to)
3027 {
3028 return headSet(to, false);
3029 }
3030
3031 public NavigableSet<D> headSet(D to, boolean inclusive)
3032 {
3033 return new DescendingSet(set.tailSet(to, inclusive));
3034 }
3035
3036 public D higher(D e)
3037 {
3038 return set.lower(e);
3039 }
3040
3041 public boolean isEmpty()
3042 {
3043 return set.isEmpty();
3044 }
3045
3046 public Iterator<D> iterator()
3047 {
3048 return new Iterator<D>()
3049 {
3050
3051 /** The last element returned by a next() call. */
3052 private D last;
3053
3054 /** The next element that should be returned by next(). */
3055 private D next = first();
3056
3057 public boolean hasNext()
3058 {
3059 return next != null;
3060 }
3061
3062 public D next()
3063 {
3064 if (next == null)
3065 throw new NoSuchElementException();
3066 last = next;
3067 next = higher(last);
3068
3069 return last;
3070 }
3071
3072 public void remove()
3073 {
3074 if (last == null)
3075 throw new IllegalStateException();
3076
3077 DescendingSet.this.remove(last);
3078 last = null;
3079 }
3080 };
3081 }
3082
3083 public D last()
3084 {
3085 return set.first();
3086 }
3087
3088 public D lower(D e)
3089 {
3090 return set.higher(e);
3091 }
3092
3093 public D pollFirst()
3094 {
3095 return set.pollLast();
3096 }
3097
3098 public D pollLast()
3099 {
3100 return set.pollFirst();
3101 }
3102
3103 public boolean remove(Object o)
3104 {
3105 return set.remove(o);
3106 }
3107
3108 public boolean removeAll(Collection<?> c)
3109 {
3110 return set.removeAll(c);
3111 }
3112
3113 public boolean retainAll(Collection<?> c)
3114 {
3115 return set.retainAll(c);
3116 }
3117
3118 public int size()
3119 {
3120 return set.size();
3121 }
3122
3123 public SortedSet<D> subSet(D from, D to)
3124 {
3125 return subSet(from, true, to, false);
3126 }
3127
3128 public NavigableSet<D> subSet(D from, boolean fromInclusive,
3129 D to, boolean toInclusive)
3130 {
3131 return new DescendingSet(set.subSet(from, fromInclusive,
3132 to, toInclusive));
3133 }
3134
3135 public SortedSet<D> tailSet(D from)
3136 {
3137 return tailSet(from, true);
3138 }
3139
3140 public NavigableSet<D> tailSet(D from, boolean inclusive)
3141 {
3142 return new DescendingSet(set.headSet(from, inclusive));
3143 }
3144
3145 public Object[] toArray()
3146 {
3147 D[] array = (D[]) set.toArray();
3148 Arrays.sort(array, comparator());
3149 return array;
3150 }
3151
3152 public <T> T[] toArray(T[] a)
3153 {
3154 T[] array = set.toArray(a);
3155 Arrays.sort(array, (Comparator<? super T>) comparator());
3156 return array;
3157 }
3158
3159 public String toString()
3160 {
3161 StringBuilder r = new StringBuilder("[");
3162 final Iterator<D> it = iterator();
3163 while (it.hasNext())
3164 {
3165 final D o = it.next();
3166 if (o == this)
3167 r.append("<this>");
3168 else
3169 r.append(o);
3170 r.append(", ");
3171 }
3172 r.replace(r.length() - 2, r.length(), "]");
3173 return r.toString();
3174 }
3175
3176 } // class DescendingSet
3177
3178 private class EntrySet
3179 extends AbstractSet<Entry<K,V>>
3180 {
3181 public int size()
3182 {
3183 return size;
3184 }
3185
3186 public Iterator<Map.Entry<K,V>> iterator()
3187 {
3188 return new TreeIterator(ENTRIES);
3189 }
3190
3191 public void clear()
3192 {
3193 TreeMap.this.clear();
3194 }
3195
3196 public boolean contains(Object o)
3197 {
3198 if (! (o instanceof Map.Entry))
3199 return false;
3200 Map.Entry<K,V> me = (Map.Entry<K,V>) o;
3201 Node<K,V> n = getNode(me.getKey());
3202 return n != nil && AbstractSet.equals(me.getValue(), n.value);
3203 }
3204
3205 public boolean remove(Object o)
3206 {
3207 if (! (o instanceof Map.Entry))
3208 return false;
3209 Map.Entry<K,V> me = (Map.Entry<K,V>) o;
3210 Node<K,V> n = getNode(me.getKey());
3211 if (n != nil && AbstractSet.equals(me.getValue(), n.value))
3212 {
3213 removeNode(n);
3214 return true;
3215 }
3216 return false;
3217 }
3218 }
3219
3220 private final class NavigableEntrySet
3221 extends EntrySet
3222 implements NavigableSet<Entry<K,V>>
3223 {
3224
3225 public Entry<K,V> ceiling(Entry<K,V> e)
3226 {
3227 return ceilingEntry(e.getKey());
3228 }
3229
3230 public Comparator<? super Entry<K,V>> comparator()
3231 {
3232 return new Comparator<Entry<K,V>>()
3233 {
3234 public int compare(Entry<K,V> t1, Entry<K,V> t2)
3235 {
3236 return comparator.compare(t1.getKey(), t2.getKey());
3237 }
3238 };
3239 }
3240
3241 public Iterator<Entry<K,V>> descendingIterator()
3242 {
3243 return descendingSet().iterator();
3244 }
3245
3246 public NavigableSet<Entry<K,V>> descendingSet()
3247 {
3248 return new DescendingSet(this);
3249 }
3250
3251 public Entry<K,V> first()
3252 {
3253 return firstEntry();
3254 }
3255
3256 public Entry<K,V> floor(Entry<K,V> e)
3257 {
3258 return floorEntry(e.getKey());
3259 }
3260
3261 public SortedSet<Entry<K,V>> headSet(Entry<K,V> to)
3262 {
3263 return headSet(to, false);
3264 }
3265
3266 public NavigableSet<Entry<K,V>> headSet(Entry<K,V> to, boolean inclusive)
3267 {
3268 return (NavigableSet<Entry<K,V>>) headMap(to.getKey(), inclusive).entrySet();
3269 }
3270
3271 public Entry<K,V> higher(Entry<K,V> e)
3272 {
3273 return higherEntry(e.getKey());
3274 }
3275
3276 public Entry<K,V> last()
3277 {
3278 return lastEntry();
3279 }
3280
3281 public Entry<K,V> lower(Entry<K,V> e)
3282 {
3283 return lowerEntry(e.getKey());
3284 }
3285
3286 public Entry<K,V> pollFirst()
3287 {
3288 return pollFirstEntry();
3289 }
3290
3291 public Entry<K,V> pollLast()
3292 {
3293 return pollLastEntry();
3294 }
3295
3296 public SortedSet<Entry<K,V>> subSet(Entry<K,V> from, Entry<K,V> to)
3297 {
3298 return subSet(from, true, to, false);
3299 }
3300
3301 public NavigableSet<Entry<K,V>> subSet(Entry<K,V> from, boolean fromInclusive,
3302 Entry<K,V> to, boolean toInclusive)
3303 {
3304 return (NavigableSet<Entry<K,V>>) subMap(from.getKey(), fromInclusive,
3305 to.getKey(), toInclusive).entrySet();
3306 }
3307
3308 public SortedSet<Entry<K,V>> tailSet(Entry<K,V> from)
3309 {
3310 return tailSet(from, true);
3311 }
3312
3313 public NavigableSet<Entry<K,V>> tailSet(Entry<K,V> from, boolean inclusive)
3314 {
3315 return (NavigableSet<Entry<K,V>>) tailMap(from.getKey(), inclusive).navigableKeySet();
3316 }
3317
3318 } // class NavigableEntrySet
3319
3320 } // class TreeMap