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