/[classpath]/classpath/java/util/TreeMap.java
ViewVC logotype

Contents of /classpath/java/util/TreeMap.java

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1.21 - (show annotations) (download)
Sat Dec 21 20:15:08 2002 UTC (21 years, 4 months ago) by ericb
Branch: MAIN
CVS Tags: classpath-0_05-release, classpath-0_06-release
Changes since 1.20: +3 -3 lines
2002-12-21  Eric Blake  <ebb9@email.byu.edu>

	* java/util/TreeMap.java (fabricateTree): Fix off-by-one error.
	(TreeIterator.remove): Prefer IllegalStateException over
	ConcurrentModificationException, to match Sun.

1 /* TreeMap.java -- a class providing a basic Red-Black Tree data structure,
2 mapping Object --> Object
3 Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
4
5 This file is part of GNU Classpath.
6
7 GNU Classpath is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GNU Classpath is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GNU Classpath; see the file COPYING. If not, write to the
19 Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
20 02111-1307 USA.
21
22 Linking this library statically or dynamically with other modules is
23 making a combined work based on this library. Thus, the terms and
24 conditions of the GNU General Public License cover the whole
25 combination.
26
27 As a special exception, the copyright holders of this library give you
28 permission to link this library with independent modules to produce an
29 executable, regardless of the license terms of these independent
30 modules, and to copy and distribute the resulting executable under
31 terms of your choice, provided that you also meet, for each linked
32 independent module, the terms and conditions of the license of that
33 module. An independent module is a module which is not derived from
34 or based on this library. If you modify this library, you may extend
35 this exception to your version of the library, but you are not
36 obligated to do so. If you do not wish to do so, delete this
37 exception statement from your version. */
38
39
40 package java.util;
41
42 import java.io.Serializable;
43 import java.io.ObjectOutputStream;
44 import java.io.ObjectInputStream;
45 import java.io.IOException;
46
47 /**
48 * This class provides a red-black tree implementation of the SortedMap
49 * interface. Elements in the Map will be sorted by either a user-provided
50 * Comparator object, or by the natural ordering of the keys.
51 *
52 * The algorithms are adopted from Corman, Leiserson, and Rivest's
53 * <i>Introduction to Algorithms.</i> TreeMap guarantees O(log n)
54 * insertion and deletion of elements. That being said, there is a large
55 * enough constant coefficient in front of that "log n" (overhead involved
56 * in keeping the tree balanced), that TreeMap may not be the best choice
57 * for small collections. If something is already sorted, you may want to
58 * just use a LinkedHashMap to maintain the order while providing O(1) access.
59 *
60 * TreeMap is a part of the JDK1.2 Collections API. Null keys are allowed
61 * only if a Comparator is used which can deal with them; natural ordering
62 * cannot cope with null. Null values are always allowed. Note that the
63 * ordering must be <i>consistent with equals</i> to correctly implement
64 * the Map interface. If this condition is violated, the map is still
65 * well-behaved, but you may have suprising results when comparing it to
66 * other maps.<p>
67 *
68 * This implementation is not synchronized. If you need to share this between
69 * multiple threads, do something like:<br>
70 * <code>SortedMap m
71 * = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
72 *
73 * The iterators are <i>fail-fast</i>, meaning that any structural
74 * modification, except for <code>remove()</code> called on the iterator
75 * itself, cause the iterator to throw a
76 * <code>ConcurrentModificationException</code> rather than exhibit
77 * non-deterministic behavior.
78 *
79 * @author Jon Zeppieri
80 * @author Bryce McKinlay
81 * @author Eric Blake <ebb9@email.byu.edu>
82 * @see Map
83 * @see HashMap
84 * @see Hashtable
85 * @see LinkedHashMap
86 * @see Comparable
87 * @see Comparator
88 * @see Collection
89 * @see Collections#synchronizedSortedMap(SortedMap)
90 * @since 1.2
91 * @status updated to 1.4
92 */
93 public class TreeMap extends AbstractMap
94 implements SortedMap, Cloneable, Serializable
95 {
96 // Implementation note:
97 // A red-black tree is a binary search tree with the additional properties
98 // that all paths to a leaf node visit the same number of black nodes,
99 // and no red node has red children. To avoid some null-pointer checks,
100 // we use the special node nil which is always black, has no relatives,
101 // and has key and value of null (but is not equal to a mapping of null).
102
103 /**
104 * Compatible with JDK 1.2.
105 */
106 private static final long serialVersionUID = 919286545866124006L;
107
108 /**
109 * Color status of a node. Package visible for use by nested classes.
110 */
111 static final int RED = -1,
112 BLACK = 1;
113
114 /**
115 * Sentinal node, used to avoid null checks for corner cases and make the
116 * delete rebalance code simpler. The rebalance code must never assign
117 * the parent, left, or right of nil, but may safely reassign the color
118 * to be black. This object must never be used as a key in a TreeMap, or
119 * it will break bounds checking of a SubMap.
120 */
121 static final Node nil = new Node(null, null, BLACK);
122 static
123 {
124 // Nil is self-referential, so we must initialize it after creation.
125 nil.parent = nil;
126 nil.left = nil;
127 nil.right = nil;
128 }
129
130 /**
131 * The root node of this TreeMap.
132 */
133 private transient Node root = nil;
134
135 /**
136 * The size of this TreeMap. Package visible for use by nested classes.
137 */
138 transient int size;
139
140 /**
141 * The cache for {@link #entrySet()}.
142 */
143 private transient Set entries;
144
145 /**
146 * Counts the number of modifications this TreeMap has undergone, used
147 * by Iterators to know when to throw ConcurrentModificationExceptions.
148 * Package visible for use by nested classes.
149 */
150 transient int modCount;
151
152 /**
153 * This TreeMap's comparator, or null for natural ordering.
154 * Package visible for use by nested classes.
155 * @serial the comparator ordering this tree, or null
156 */
157 final Comparator comparator;
158
159 /**
160 * Class to represent an entry in the tree. Holds a single key-value pair,
161 * plus pointers to parent and child nodes.
162 *
163 * @author Eric Blake <ebb9@email.byu.edu>
164 */
165 private static final class Node extends AbstractMap.BasicMapEntry
166 {
167 // All fields package visible for use by nested classes.
168 /** The color of this node. */
169 int color;
170
171 /** The left child node. */
172 Node left = nil;
173 /** The right child node. */
174 Node right = nil;
175 /** The parent node. */
176 Node parent = nil;
177
178 /**
179 * Simple constructor.
180 * @param key the key
181 * @param value the value
182 */
183 Node(Object key, Object value, int color)
184 {
185 super(key, value);
186 this.color = color;
187 }
188 }
189
190 /**
191 * Instantiate a new TreeMap with no elements, using the keys' natural
192 * ordering to sort. All entries in the map must have a key which implements
193 * Comparable, and which are <i>mutually comparable</i>, otherwise map
194 * operations may throw a {@link ClassCastException}. Attempts to use
195 * a null key will throw a {@link NullPointerException}.
196 *
197 * @see Comparable
198 */
199 public TreeMap()
200 {
201 this((Comparator) null);
202 }
203
204 /**
205 * Instantiate a new TreeMap with no elements, using the provided comparator
206 * to sort. All entries in the map must have keys which are mutually
207 * comparable by the Comparator, otherwise map operations may throw a
208 * {@link ClassCastException}.
209 *
210 * @param comparator the sort order for the keys of this map, or null
211 * for the natural order
212 */
213 public TreeMap(Comparator c)
214 {
215 comparator = c;
216 }
217
218 /**
219 * Instantiate a new TreeMap, initializing it with all of the elements in
220 * the provided Map. The elements will be sorted using the natural
221 * ordering of the keys. This algorithm runs in n*log(n) time. All entries
222 * in the map must have keys which implement Comparable and are mutually
223 * comparable, otherwise map operations may throw a
224 * {@link ClassCastException}.
225 *
226 * @param map a Map, whose entries will be put into this TreeMap
227 * @throws ClassCastException if the keys in the provided Map are not
228 * comparable
229 * @throws NullPointerException if map is null
230 * @see Comparable
231 */
232 public TreeMap(Map map)
233 {
234 this((Comparator) null);
235 putAll(map);
236 }
237
238 /**
239 * Instantiate a new TreeMap, initializing it with all of the elements in
240 * the provided SortedMap. The elements will be sorted using the same
241 * comparator as in the provided SortedMap. This runs in linear time.
242 *
243 * @param sm a SortedMap, whose entries will be put into this TreeMap
244 * @throws NullPointerException if sm is null
245 */
246 public TreeMap(SortedMap sm)
247 {
248 this(sm.comparator());
249 int pos = sm.size();
250 Iterator itr = sm.entrySet().iterator();
251
252 fabricateTree(pos);
253 Node node = firstNode();
254
255 while (--pos >= 0)
256 {
257 Map.Entry me = (Map.Entry) itr.next();
258 node.key = me.getKey();
259 node.value = me.getValue();
260 node = successor(node);
261 }
262 }
263
264 /**
265 * Clears the Map so it has no keys. This is O(1).
266 */
267 public void clear()
268 {
269 if (size > 0)
270 {
271 modCount++;
272 root = nil;
273 size = 0;
274 }
275 }
276
277 /**
278 * Returns a shallow clone of this TreeMap. The Map itself is cloned,
279 * but its contents are not.
280 *
281 * @return the clone
282 */
283 public Object clone()
284 {
285 TreeMap copy = null;
286 try
287 {
288 copy = (TreeMap) super.clone();
289 }
290 catch (CloneNotSupportedException x)
291 {
292 }
293 copy.entries = null;
294 copy.fabricateTree(size);
295
296 Node node = firstNode();
297 Node cnode = copy.firstNode();
298
299 while (node != nil)
300 {
301 cnode.key = node.key;
302 cnode.value = node.value;
303 node = successor(node);
304 cnode = copy.successor(cnode);
305 }
306 return copy;
307 }
308
309 /**
310 * Return the comparator used to sort this map, or null if it is by
311 * natural order.
312 *
313 * @return the map's comparator
314 */
315 public Comparator comparator()
316 {
317 return comparator;
318 }
319
320 /**
321 * Returns true if the map contains a mapping for the given key.
322 *
323 * @param key the key to look for
324 * @return true if the key has a mapping
325 * @throws ClassCastException if key is not comparable to map elements
326 * @throws NullPointerException if key is null and the comparator is not
327 * tolerant of nulls
328 */
329 public boolean containsKey(Object key)
330 {
331 return getNode(key) != nil;
332 }
333
334 /**
335 * Returns true if the map contains at least one mapping to the given value.
336 * This requires linear time.
337 *
338 * @param value the value to look for
339 * @return true if the value appears in a mapping
340 */
341 public boolean containsValue(Object value)
342 {
343 Node node = firstNode();
344 while (node != nil)
345 {
346 if (equals(value, node.value))
347 return true;
348 node = successor(node);
349 }
350 return false;
351 }
352
353 /**
354 * Returns a "set view" of this TreeMap's entries. The set is backed by
355 * the TreeMap, so changes in one show up in the other. The set supports
356 * element removal, but not element addition.<p>
357 *
358 * Note that the iterators for all three views, from keySet(), entrySet(),
359 * and values(), traverse the TreeMap in sorted sequence.
360 *
361 * @return a set view of the entries
362 * @see #keySet()
363 * @see #values()
364 * @see Map.Entry
365 */
366 public Set entrySet()
367 {
368 if (entries == null)
369 // Create an AbstractSet with custom implementations of those methods
370 // that can be overriden easily and efficiently.
371 entries = new AbstractSet()
372 {
373 public int size()
374 {
375 return size;
376 }
377
378 public Iterator iterator()
379 {
380 return new TreeIterator(ENTRIES);
381 }
382
383 public void clear()
384 {
385 TreeMap.this.clear();
386 }
387
388 public boolean contains(Object o)
389 {
390 if (! (o instanceof Map.Entry))
391 return false;
392 Map.Entry me = (Map.Entry) o;
393 Node n = getNode(me.getKey());
394 return n != nil && AbstractSet.equals(me.getValue(), n.value);
395 }
396
397 public boolean remove(Object o)
398 {
399 if (! (o instanceof Map.Entry))
400 return false;
401 Map.Entry me = (Map.Entry) o;
402 Node n = getNode(me.getKey());
403 if (n != nil && AbstractSet.equals(me.getValue(), n.value))
404 {
405 removeNode(n);
406 return true;
407 }
408 return false;
409 }
410 };
411 return entries;
412 }
413
414 /**
415 * Returns the first (lowest) key in the map.
416 *
417 * @return the first key
418 * @throws NoSuchElementException if the map is empty
419 */
420 public Object firstKey()
421 {
422 if (root == nil)
423 throw new NoSuchElementException();
424 return firstNode().key;
425 }
426
427 /**
428 * Return the value in this TreeMap associated with the supplied key,
429 * or <code>null</code> if the key maps to nothing. NOTE: Since the value
430 * could also be null, you must use containsKey to see if this key
431 * actually maps to something.
432 *
433 * @param key the key for which to fetch an associated value
434 * @return what the key maps to, if present
435 * @throws ClassCastException if key is not comparable to elements in the map
436 * @throws NullPointerException if key is null but the comparator does not
437 * tolerate nulls
438 * @see #put(Object, Object)
439 * @see #containsKey(Object)
440 */
441 public Object get(Object key)
442 {
443 // Exploit fact that nil.value == null.
444 return getNode(key).value;
445 }
446
447 /**
448 * Returns a view of this Map including all entries with keys less than
449 * <code>toKey</code>. The returned map is backed by the original, so changes
450 * in one appear in the other. The submap will throw an
451 * {@link IllegalArgumentException} for any attempt to access or add an
452 * element beyond the specified cutoff. The returned map does not include
453 * the endpoint; if you want inclusion, pass the successor element.
454 *
455 * @param toKey the (exclusive) cutoff point
456 * @return a view of the map less than the cutoff
457 * @throws ClassCastException if <code>toKey</code> is not compatible with
458 * the comparator (or is not Comparable, for natural ordering)
459 * @throws NullPointerException if toKey is null, but the comparator does not
460 * tolerate null elements
461 */
462 public SortedMap headMap(Object toKey)
463 {
464 return new SubMap(nil, toKey);
465 }
466
467 /**
468 * Returns a "set view" of this TreeMap's keys. The set is backed by the
469 * TreeMap, so changes in one show up in the other. The set supports
470 * element removal, but not element addition.
471 *
472 * @return a set view of the keys
473 * @see #values()
474 * @see #entrySet()
475 */
476 public Set keySet()
477 {
478 if (keys == null)
479 // Create an AbstractSet with custom implementations of those methods
480 // that can be overriden easily and efficiently.
481 keys = new AbstractSet()
482 {
483 public int size()
484 {
485 return size;
486 }
487
488 public Iterator iterator()
489 {
490 return new TreeIterator(KEYS);
491 }
492
493 public void clear()
494 {
495 TreeMap.this.clear();
496 }
497
498 public boolean contains(Object o)
499 {
500 return containsKey(o);
501 }
502
503 public boolean remove(Object key)
504 {
505 Node n = getNode(key);
506 if (n == nil)
507 return false;
508 removeNode(n);
509 return true;
510 }
511 };
512 return keys;
513 }
514
515 /**
516 * Returns the last (highest) key in the map.
517 *
518 * @return the last key
519 * @throws NoSuchElementException if the map is empty
520 */
521 public Object lastKey()
522 {
523 if (root == nil)
524 throw new NoSuchElementException("empty");
525 return lastNode().key;
526 }
527
528 /**
529 * Puts the supplied value into the Map, mapped by the supplied key.
530 * The value may be retrieved by any object which <code>equals()</code>
531 * this key. NOTE: Since the prior value could also be null, you must
532 * first use containsKey if you want to see if you are replacing the
533 * key's mapping.
534 *
535 * @param key the key used to locate the value
536 * @param value the value to be stored in the HashMap
537 * @return the prior mapping of the key, or null if there was none
538 * @throws ClassCastException if key is not comparable to current map keys
539 * @throws NullPointerException if key is null, but the comparator does
540 * not tolerate nulls
541 * @see #get(Object)
542 * @see Object#equals(Object)
543 */
544 public Object put(Object key, Object value)
545 {
546 Node current = root;
547 Node parent = nil;
548 int comparison = 0;
549
550 // Find new node's parent.
551 while (current != nil)
552 {
553 parent = current;
554 comparison = compare(key, current.key);
555 if (comparison > 0)
556 current = current.right;
557 else if (comparison < 0)
558 current = current.left;
559 else // Key already in tree.
560 return current.setValue(value);
561 }
562
563 // Set up new node.
564 Node n = new Node(key, value, RED);
565 n.parent = parent;
566
567 // Insert node in tree.
568 modCount++;
569 size++;
570 if (parent == nil)
571 {
572 // Special case inserting into an empty tree.
573 root = n;
574 return null;
575 }
576 if (comparison > 0)
577 parent.right = n;
578 else
579 parent.left = n;
580
581 // Rebalance after insert.
582 insertFixup(n);
583 return null;
584 }
585
586 /**
587 * Copies all elements of the given map into this hashtable. If this table
588 * already has a mapping for a key, the new mapping replaces the current
589 * one.
590 *
591 * @param m the map to be hashed into this
592 * @throws ClassCastException if a key in m is not comparable with keys
593 * in the map
594 * @throws NullPointerException if a key in m is null, and the comparator
595 * does not tolerate nulls
596 */
597 public void putAll(Map m)
598 {
599 Iterator itr = m.entrySet().iterator();
600 int pos = m.size();
601 while (--pos >= 0)
602 {
603 Map.Entry e = (Map.Entry) itr.next();
604 put(e.getKey(), e.getValue());
605 }
606 }
607
608 /**
609 * Removes from the TreeMap and returns the value which is mapped by the
610 * supplied key. If the key maps to nothing, then the TreeMap remains
611 * unchanged, and <code>null</code> is returned. NOTE: Since the value
612 * could also be null, you must use containsKey to see if you are
613 * actually removing a mapping.
614 *
615 * @param key the key used to locate the value to remove
616 * @return whatever the key mapped to, if present
617 * @throws ClassCastException if key is not comparable to current map keys
618 * @throws NullPointerException if key is null, but the comparator does
619 * not tolerate nulls
620 */
621 public Object remove(Object key)
622 {
623 Node n = getNode(key);
624 if (n == nil)
625 return null;
626 // Note: removeNode can alter the contents of n, so save value now.
627 Object result = n.value;
628 removeNode(n);
629 return result;
630 }
631
632 /**
633 * Returns the number of key-value mappings currently in this Map.
634 *
635 * @return the size
636 */
637 public int size()
638 {
639 return size;
640 }
641
642 /**
643 * Returns a view of this Map including all entries with keys greater or
644 * equal to <code>fromKey</code> and less than <code>toKey</code> (a
645 * half-open interval). The returned map is backed by the original, so
646 * changes in one appear in the other. The submap will throw an
647 * {@link IllegalArgumentException} for any attempt to access or add an
648 * element beyond the specified cutoffs. The returned map includes the low
649 * endpoint but not the high; if you want to reverse this behavior on
650 * either end, pass in the successor element.
651 *
652 * @param fromKey the (inclusive) low cutoff point
653 * @param toKey the (exclusive) high cutoff point
654 * @return a view of the map between the cutoffs
655 * @throws ClassCastException if either cutoff is not compatible with
656 * the comparator (or is not Comparable, for natural ordering)
657 * @throws NullPointerException if fromKey or toKey is null, but the
658 * comparator does not tolerate null elements
659 * @throws IllegalArgumentException if fromKey is greater than toKey
660 */
661 public SortedMap subMap(Object fromKey, Object toKey)
662 {
663 return new SubMap(fromKey, toKey);
664 }
665
666 /**
667 * Returns a view of this Map including all entries with keys greater or
668 * equal to <code>fromKey</code>. The returned map is backed by the
669 * original, so changes in one appear in the other. The submap will throw an
670 * {@link IllegalArgumentException} for any attempt to access or add an
671 * element beyond the specified cutoff. The returned map includes the
672 * endpoint; if you want to exclude it, pass in the successor element.
673 *
674 * @param fromKey the (inclusive) low cutoff point
675 * @return a view of the map above the cutoff
676 * @throws ClassCastException if <code>fromKey</code> is not compatible with
677 * the comparator (or is not Comparable, for natural ordering)
678 * @throws NullPointerException if fromKey is null, but the comparator
679 * does not tolerate null elements
680 */
681 public SortedMap tailMap(Object fromKey)
682 {
683 return new SubMap(fromKey, nil);
684 }
685
686 /**
687 * Returns a "collection view" (or "bag view") of this TreeMap's values.
688 * The collection is backed by the TreeMap, so changes in one show up
689 * in the other. The collection supports element removal, but not element
690 * addition.
691 *
692 * @return a bag view of the values
693 * @see #keySet()
694 * @see #entrySet()
695 */
696 public Collection values()
697 {
698 if (values == null)
699 // We don't bother overriding many of the optional methods, as doing so
700 // wouldn't provide any significant performance advantage.
701 values = new AbstractCollection()
702 {
703 public int size()
704 {
705 return size;
706 }
707
708 public Iterator iterator()
709 {
710 return new TreeIterator(VALUES);
711 }
712
713 public void clear()
714 {
715 TreeMap.this.clear();
716 }
717 };
718 return values;
719 }
720
721 /**
722 * Compares two elements by the set comparator, or by natural ordering.
723 * Package visible for use by nested classes.
724 *
725 * @param o1 the first object
726 * @param o2 the second object
727 * @throws ClassCastException if o1 and o2 are not mutually comparable,
728 * or are not Comparable with natural ordering
729 * @throws NullPointerException if o1 or o2 is null with natural ordering
730 */
731 final int compare(Object o1, Object o2)
732 {
733 return (comparator == null
734 ? ((Comparable) o1).compareTo(o2)
735 : comparator.compare(o1, o2));
736 }
737
738 /**
739 * Maintain red-black balance after deleting a node.
740 *
741 * @param node the child of the node just deleted, possibly nil
742 * @param parent the parent of the node just deleted, never nil
743 */
744 private void deleteFixup(Node node, Node parent)
745 {
746 // if (parent == nil)
747 // throw new InternalError();
748 // If a black node has been removed, we need to rebalance to avoid
749 // violating the "same number of black nodes on any path" rule. If
750 // node is red, we can simply recolor it black and all is well.
751 while (node != root && node.color == BLACK)
752 {
753 if (node == parent.left)
754 {
755 // Rebalance left side.
756 Node sibling = parent.right;
757 // if (sibling == nil)
758 // throw new InternalError();
759 if (sibling.color == RED)
760 {
761 // Case 1: Sibling is red.
762 // Recolor sibling and parent, and rotate parent left.
763 sibling.color = BLACK;
764 parent.color = RED;
765 rotateLeft(parent);
766 sibling = parent.right;
767 }
768
769 if (sibling.left.color == BLACK && sibling.right.color == BLACK)
770 {
771 // Case 2: Sibling has no red children.
772 // Recolor sibling, and move to parent.
773 sibling.color = RED;
774 node = parent;
775 parent = parent.parent;
776 }
777 else
778 {
779 if (sibling.right.color == BLACK)
780 {
781 // Case 3: Sibling has red left child.
782 // Recolor sibling and left child, rotate sibling right.
783 sibling.left.color = BLACK;
784 sibling.color = RED;
785 rotateRight(sibling);
786 sibling = parent.right;
787 }
788 // Case 4: Sibling has red right child. Recolor sibling,
789 // right child, and parent, and rotate parent left.
790 sibling.color = parent.color;
791 parent.color = BLACK;
792 sibling.right.color = BLACK;
793 rotateLeft(parent);
794 node = root; // Finished.
795 }
796 }
797 else
798 {
799 // Symmetric "mirror" of left-side case.
800 Node sibling = parent.left;
801 // if (sibling == nil)
802 // throw new InternalError();
803 if (sibling.color == RED)
804 {
805 // Case 1: Sibling is red.
806 // Recolor sibling and parent, and rotate parent right.
807 sibling.color = BLACK;
808 parent.color = RED;
809 rotateRight(parent);
810 sibling = parent.left;
811 }
812
813 if (sibling.right.color == BLACK && sibling.left.color == BLACK)
814 {
815 // Case 2: Sibling has no red children.
816 // Recolor sibling, and move to parent.
817 sibling.color = RED;
818 node = parent;
819 parent = parent.parent;
820 }
821 else
822 {
823 if (sibling.left.color == BLACK)
824 {
825 // Case 3: Sibling has red right child.
826 // Recolor sibling and right child, rotate sibling left.
827 sibling.right.color = BLACK;
828 sibling.color = RED;
829 rotateLeft(sibling);
830 sibling = parent.left;
831 }
832 // Case 4: Sibling has red left child. Recolor sibling,
833 // left child, and parent, and rotate parent right.
834 sibling.color = parent.color;
835 parent.color = BLACK;
836 sibling.left.color = BLACK;
837 rotateRight(parent);
838 node = root; // Finished.
839 }
840 }
841 }
842 node.color = BLACK;
843 }
844
845 /**
846 * Construct a perfectly balanced tree consisting of n "blank" nodes. This
847 * permits a tree to be generated from pre-sorted input in linear time.
848 *
849 * @param count the number of blank nodes, non-negative
850 */
851 private void fabricateTree(final int count)
852 {
853 if (count == 0)
854 return;
855
856 // We color every row of nodes black, except for the overflow nodes.
857 // I believe that this is the optimal arrangement. We construct the tree
858 // in place by temporarily linking each node to the next node in the row,
859 // then updating those links to the children when working on the next row.
860
861 // Make the root node.
862 root = new Node(null, null, BLACK);
863 size = count;
864 Node row = root;
865 int rowsize;
866
867 // Fill each row that is completely full of nodes.
868 for (rowsize = 2; rowsize + rowsize <= count; rowsize <<= 1)
869 {
870 Node parent = row;
871 Node last = null;
872 for (int i = 0; i < rowsize; i += 2)
873 {
874 Node left = new Node(null, null, BLACK);
875 Node right = new Node(null, null, BLACK);
876 left.parent = parent;
877 left.right = right;
878 right.parent = parent;
879 parent.left = left;
880 Node next = parent.right;
881 parent.right = right;
882 parent = next;
883 if (last != null)
884 last.right = left;
885 last = right;
886 }
887 row = row.left;
888 }
889
890 // Now do the partial final row in red.
891 int overflow = count - rowsize;
892 Node parent = row;
893 int i;
894 for (i = 0; i < overflow; i += 2)
895 {
896 Node left = new Node(null, null, RED);
897 Node right = new Node(null, null, RED);
898 left.parent = parent;
899 right.parent = parent;
900 parent.left = left;
901 Node next = parent.right;
902 parent.right = right;
903 parent = next;
904 }
905 // Add a lone left node if necessary.
906 if (i - overflow == 0)
907 {
908 Node left = new Node(null, null, RED);
909 left.parent = parent;
910 parent.left = left;
911 parent = parent.right;
912 left.parent.right = nil;
913 }
914 // Unlink the remaining nodes of the previous row.
915 while (parent != nil)
916 {
917 Node next = parent.right;
918 parent.right = nil;
919 parent = next;
920 }
921 }
922
923 /**
924 * Returns the first sorted node in the map, or nil if empty. Package
925 * visible for use by nested classes.
926 *
927 * @return the first node
928 */
929 final Node firstNode()
930 {
931 // Exploit fact that nil.left == nil.
932 Node node = root;
933 while (node.left != nil)
934 node = node.left;
935 return node;
936 }
937
938 /**
939 * Return the TreeMap.Node associated with key, or the nil node if no such
940 * node exists in the tree. Package visible for use by nested classes.
941 *
942 * @param key the key to search for
943 * @return the node where the key is found, or nil
944 */
945 final Node getNode(Object key)
946 {
947 Node current = root;
948 while (current != nil)
949 {
950 int comparison = compare(key, current.key);
951 if (comparison > 0)
952 current = current.right;
953 else if (comparison < 0)
954 current = current.left;
955 else
956 return current;
957 }
958 return current;
959 }
960
961 /**
962 * Find the "highest" node which is &lt; key. If key is nil, return last
963 * node. Package visible for use by nested classes.
964 *
965 * @param key the upper bound, exclusive
966 * @return the previous node
967 */
968 final Node highestLessThan(Object key)
969 {
970 if (key == nil)
971 return lastNode();
972
973 Node last = nil;
974 Node current = root;
975 int comparison = 0;
976
977 while (current != nil)
978 {
979 last = current;
980 comparison = compare(key, current.key);
981 if (comparison > 0)
982 current = current.right;
983 else if (comparison < 0)
984 current = current.left;
985 else // Exact match.
986 return predecessor(last);
987 }
988 return comparison <= 0 ? predecessor(last) : last;
989 }
990
991 /**
992 * Maintain red-black balance after inserting a new node.
993 *
994 * @param n the newly inserted node
995 */
996 private void insertFixup(Node n)
997 {
998 // Only need to rebalance when parent is a RED node, and while at least
999 // 2 levels deep into the tree (ie: node has a grandparent). Remember
1000 // that nil.color == BLACK.
1001 while (n.parent.color == RED && n.parent.parent != nil)
1002 {
1003 if (n.parent == n.parent.parent.left)
1004 {
1005 Node uncle = n.parent.parent.right;
1006 // Uncle may be nil, in which case it is BLACK.
1007 if (uncle.color == RED)
1008 {
1009 // Case 1. Uncle is RED: Change colors of parent, uncle,
1010 // and grandparent, and move n to grandparent.
1011 n.parent.color = BLACK;
1012 uncle.color = BLACK;
1013 uncle.parent.color = RED;
1014 n = uncle.parent;
1015 }
1016 else
1017 {
1018 if (n == n.parent.right)
1019 {
1020 // Case 2. Uncle is BLACK and x is right child.
1021 // Move n to parent, and rotate n left.
1022 n = n.parent;
1023 rotateLeft(n);
1024 }
1025 // Case 3. Uncle is BLACK and x is left child.
1026 // Recolor parent, grandparent, and rotate grandparent right.
1027 n.parent.color = BLACK;
1028 n.parent.parent.color = RED;
1029 rotateRight(n.parent.parent);
1030 }
1031 }
1032 else
1033 {
1034 // Mirror image of above code.
1035 Node uncle = n.parent.parent.left;
1036 // Uncle may be nil, in which case it is BLACK.
1037 if (uncle.color == RED)
1038 {
1039 // Case 1. Uncle is RED: Change colors of parent, uncle,
1040 // and grandparent, and move n to grandparent.
1041 n.parent.color = BLACK;
1042 uncle.color = BLACK;
1043 uncle.parent.color = RED;
1044 n = uncle.parent;
1045 }
1046 else
1047 {
1048 if (n == n.parent.left)
1049 {
1050 // Case 2. Uncle is BLACK and x is left child.
1051 // Move n to parent, and rotate n right.
1052 n = n.parent;
1053 rotateRight(n);
1054 }
1055 // Case 3. Uncle is BLACK and x is right child.
1056 // Recolor parent, grandparent, and rotate grandparent left.
1057 n.parent.color = BLACK;
1058 n.parent.parent.color = RED;
1059 rotateLeft(n.parent.parent);
1060 }
1061 }
1062 }
1063 root.color = BLACK;
1064 }
1065
1066 /**
1067 * Returns the last sorted node in the map, or nil if empty.
1068 *
1069 * @return the last node
1070 */
1071 private Node lastNode()
1072 {
1073 // Exploit fact that nil.right == nil.
1074 Node node = root;
1075 while (node.right != nil)
1076 node = node.right;
1077 return node;
1078 }
1079
1080 /**
1081 * Find the "lowest" node which is &gt;= key. If key is nil, return either
1082 * nil or the first node, depending on the parameter first.
1083 * Package visible for use by nested classes.
1084 *
1085 * @param key the lower bound, inclusive
1086 * @param first true to return the first element instead of nil for nil key
1087 * @return the next node
1088 */
1089 final Node lowestGreaterThan(Object key, boolean first)
1090 {
1091 if (key == nil)
1092 return first ? firstNode() : nil;
1093
1094 Node last = nil;
1095 Node current = root;
1096 int comparison = 0;
1097
1098 while (current != nil)
1099 {
1100 last = current;
1101 comparison = compare(key, current.key);
1102 if (comparison > 0)
1103 current = current.right;
1104 else if (comparison < 0)
1105 current = current.left;
1106 else
1107 return current;
1108 }
1109 return comparison > 0 ? successor(last) : last;
1110 }
1111
1112 /**
1113 * Return the node preceding the given one, or nil if there isn't one.
1114 *
1115 * @param node the current node, not nil
1116 * @return the prior node in sorted order
1117 */
1118 private Node predecessor(Node node)
1119 {
1120 if (node.left != nil)
1121 {
1122 node = node.left;
1123 while (node.right != nil)
1124 node = node.right;
1125 return node;
1126 }
1127
1128 Node parent = node.parent;
1129 // Exploit fact that nil.left == nil and node is non-nil.
1130 while (node == parent.left)
1131 {
1132 node = parent;
1133 parent = node.parent;
1134 }
1135 return parent;
1136 }
1137
1138 /**
1139 * Construct a tree from sorted keys in linear time. Package visible for
1140 * use by TreeSet.
1141 *
1142 * @param s the stream to read from
1143 * @param count the number of keys to read
1144 * @param readValue true to read values, false to insert "" as the value
1145 * @throws ClassNotFoundException if the underlying stream fails
1146 * @throws IOException if the underlying stream fails
1147 * @see #readObject(ObjectInputStream)
1148 * @see TreeSet#readObject(ObjectInputStream)
1149 */
1150 final void putFromObjStream(ObjectInputStream s, int count,
1151 boolean readValues)
1152 throws IOException, ClassNotFoundException
1153 {
1154 fabricateTree(count);
1155 Node node = firstNode();
1156
1157 while (--count >= 0)
1158 {
1159 node.key = s.readObject();
1160 node.value = readValues ? s.readObject() : "";
1161 node = successor(node);
1162 }
1163 }
1164
1165 /**
1166 * Construct a tree from sorted keys in linear time, with values of "".
1167 * Package visible for use by TreeSet.
1168 *
1169 * @param keys the iterator over the sorted keys
1170 * @param count the number of nodes to insert
1171 * @see TreeSet#TreeSet(SortedSet)
1172 */
1173 final void putKeysLinear(Iterator keys, int count)
1174 {
1175 fabricateTree(count);
1176 Node node = firstNode();
1177
1178 while (--count >= 0)
1179 {
1180 node.key = keys.next();
1181 node.value = "";
1182 node = successor(node);
1183 }
1184 }
1185
1186 /**
1187 * Deserializes this object from the given stream.
1188 *
1189 * @param s the stream to read from
1190 * @throws ClassNotFoundException if the underlying stream fails
1191 * @throws IOException if the underlying stream fails
1192 * @serialData the <i>size</i> (int), followed by key (Object) and value
1193 * (Object) pairs in sorted order
1194 */
1195 private void readObject(ObjectInputStream s)
1196 throws IOException, ClassNotFoundException
1197 {
1198 s.defaultReadObject();
1199 int size = s.readInt();
1200 putFromObjStream(s, size, true);
1201 }
1202
1203 /**
1204 * Remove node from tree. This will increment modCount and decrement size.
1205 * Node must exist in the tree. Package visible for use by nested classes.
1206 *
1207 * @param node the node to remove
1208 */
1209 final void removeNode(Node node)
1210 {
1211 Node splice;
1212 Node child;
1213
1214 modCount++;
1215 size--;
1216
1217 // Find splice, the node at the position to actually remove from the tree.
1218 if (node.left == nil)
1219 {
1220 // Node to be deleted has 0 or 1 children.
1221 splice = node;
1222 child = node.right;
1223 }
1224 else if (node.right == nil)
1225 {
1226 // Node to be deleted has 1 child.
1227 splice = node;
1228 child = node.left;
1229 }
1230 else
1231 {
1232 // Node has 2 children. Splice is node's predecessor, and we swap
1233 // its contents into node.
1234 splice = node.left;
1235 while (splice.right != nil)
1236 splice = splice.right;
1237 child = splice.left;
1238 node.key = splice.key;
1239 node.value = splice.value;
1240 }
1241
1242 // Unlink splice from the tree.
1243 Node parent = splice.parent;
1244 if (child != nil)
1245 child.parent = parent;
1246 if (parent == nil)
1247 {
1248 // Special case for 0 or 1 node remaining.
1249 root = child;
1250 return;
1251 }
1252 if (splice == parent.left)
1253 parent.left = child;
1254 else
1255 parent.right = child;
1256
1257 if (splice.color == BLACK)
1258 deleteFixup(child, parent);
1259 }
1260
1261 /**
1262 * Rotate node n to the left.
1263 *
1264 * @param node the node to rotate
1265 */
1266 private void rotateLeft(Node node)
1267 {
1268 Node child = node.right;
1269 // if (node == nil || child == nil)
1270 // throw new InternalError();
1271
1272 // Establish node.right link.
1273 node.right = child.left;
1274 if (child.left != nil)
1275 child.left.parent = node;
1276
1277 // Establish child->parent link.
1278 child.parent = node.parent;
1279 if (node.parent != nil)
1280 {
1281 if (node == node.parent.left)
1282 node.parent.left = child;
1283 else
1284 node.parent.right = child;
1285 }
1286 else
1287 root = child;
1288
1289 // Link n and child.
1290 child.left = node;
1291 node.parent = child;
1292 }
1293
1294 /**
1295 * Rotate node n to the right.
1296 *
1297 * @param node the node to rotate
1298 */
1299 private void rotateRight(Node node)
1300 {
1301 Node child = node.left;
1302 // if (node == nil || child == nil)
1303 // throw new InternalError();
1304
1305 // Establish node.left link.
1306 node.left = child.right;
1307 if (child.right != nil)
1308 child.right.parent = node;
1309
1310 // Establish child->parent link.
1311 child.parent = node.parent;
1312 if (node.parent != nil)
1313 {
1314 if (node == node.parent.right)
1315 node.parent.right = child;
1316 else
1317 node.parent.left = child;
1318 }
1319 else
1320 root = child;
1321
1322 // Link n and child.
1323 child.right = node;
1324 node.parent = child;
1325 }
1326
1327 /**
1328 * Return the node following the given one, or nil if there isn't one.
1329 * Package visible for use by nested classes.
1330 *
1331 * @param node the current node, not nil
1332 * @return the next node in sorted order
1333 */
1334 final Node successor(Node node)
1335 {
1336 if (node.right != nil)
1337 {
1338 node = node.right;
1339 while (node.left != nil)
1340 node = node.left;
1341 return node;
1342 }
1343
1344 Node parent = node.parent;
1345 // Exploit fact that nil.right == nil and node is non-nil.
1346 while (node == parent.right)
1347 {
1348 node = parent;
1349 parent = parent.parent;
1350 }
1351 return parent;
1352 }
1353
1354 /**
1355 * Serializes this object to the given stream.
1356 *
1357 * @param s the stream to write to
1358 * @throws IOException if the underlying stream fails
1359 * @serialData the <i>size</i> (int), followed by key (Object) and value
1360 * (Object) pairs in sorted order
1361 */
1362 private void writeObject(ObjectOutputStream s) throws IOException
1363 {
1364 s.defaultWriteObject();
1365
1366 Node node = firstNode();
1367 s.writeInt(size);
1368 while (node != nil)
1369 {
1370 s.writeObject(node.key);
1371 s.writeObject(node.value);
1372 node = successor(node);
1373 }
1374 }
1375
1376 /**
1377 * Iterate over HashMap's entries. This implementation is parameterized
1378 * to give a sequential view of keys, values, or entries.
1379 *
1380 * @author Eric Blake <ebb9@email.byu.edu>
1381 */
1382 private final class TreeIterator implements Iterator
1383 {
1384 /**
1385 * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
1386 * or {@link #ENTRIES}.
1387 */
1388 private final int type;
1389 /** The number of modifications to the backing Map that we know about. */
1390 private int knownMod = modCount;
1391 /** The last Entry returned by a next() call. */
1392 private Node last;
1393 /** The next entry that should be returned by next(). */
1394 private Node next;
1395 /**
1396 * The last node visible to this iterator. This is used when iterating
1397 * on a SubMap.
1398 */
1399 private final Node max;
1400
1401 /**
1402 * Construct a new TreeIterator with the supplied type.
1403 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1404 */
1405 TreeIterator(int type)
1406 {
1407 // FIXME gcj cannot handle this. Bug java/4695
1408 // this(type, firstNode(), nil);
1409 this.type = type;
1410 this.next = firstNode();
1411 this.max = nil;
1412 }
1413
1414 /**
1415 * Construct a new TreeIterator with the supplied type. Iteration will
1416 * be from "first" (inclusive) to "max" (exclusive).
1417 *
1418 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1419 * @param first where to start iteration, nil for empty iterator
1420 * @param max the cutoff for iteration, nil for all remaining nodes
1421 */
1422 TreeIterator(int type, Node first, Node max)
1423 {
1424 this.type = type;
1425 this.next = first;
1426 this.max = max;
1427 }
1428
1429 /**
1430 * Returns true if the Iterator has more elements.
1431 * @return true if there are more elements
1432 * @throws ConcurrentModificationException if the TreeMap was modified
1433 */
1434 public boolean hasNext()
1435 {
1436 if (knownMod != modCount)
1437 throw new ConcurrentModificationException();
1438 return next != max;
1439 }
1440
1441 /**
1442 * Returns the next element in the Iterator's sequential view.
1443 * @return the next element
1444 * @throws ConcurrentModificationException if the TreeMap was modified
1445 * @throws NoSuchElementException if there is none
1446 */
1447 public Object next()
1448 {
1449 if (knownMod != modCount)
1450 throw new ConcurrentModificationException();
1451 if (next == max)
1452 throw new NoSuchElementException();
1453 last = next;
1454 next = successor(last);
1455
1456 if (type == VALUES)
1457 return last.value;
1458 else if (type == KEYS)
1459 return last.key;
1460 return last;
1461 }
1462
1463 /**
1464 * Removes from the backing TreeMap the last element which was fetched
1465 * with the <code>next()</code> method.
1466 * @throws ConcurrentModificationException if the TreeMap was modified
1467 * @throws IllegalStateException if called when there is no last element
1468 */
1469 public void remove()
1470 {
1471 if (last == null)
1472 throw new IllegalStateException();
1473 if (knownMod != modCount)
1474 throw new ConcurrentModificationException();
1475
1476 removeNode(last);
1477 last = null;
1478 knownMod++;
1479 }
1480 } // class TreeIterator
1481
1482 /**
1483 * Implementation of {@link #subMap(Object, Object)} and other map
1484 * ranges. This class provides a view of a portion of the original backing
1485 * map, and throws {@link IllegalArgumentException} for attempts to
1486 * access beyond that range.
1487 *
1488 * @author Eric Blake <ebb9@email.byu.edu>
1489 */
1490 private final class SubMap extends AbstractMap implements SortedMap
1491 {
1492 /**
1493 * The lower range of this view, inclusive, or nil for unbounded.
1494 * Package visible for use by nested classes.
1495 */
1496 final Object minKey;
1497
1498 /**
1499 * The upper range of this view, exclusive, or nil for unbounded.
1500 * Package visible for use by nested classes.
1501 */
1502 final Object maxKey;
1503
1504 /**
1505 * The cache for {@link #entrySet()}.
1506 */
1507 private Set entries;
1508
1509 /**
1510 * Create a SubMap representing the elements between minKey (inclusive)
1511 * and maxKey (exclusive). If minKey is nil, SubMap has no lower bound
1512 * (headMap). If maxKey is nil, the SubMap has no upper bound (tailMap).
1513 *
1514 * @param minKey the lower bound
1515 * @param maxKey the upper bound
1516 * @throws IllegalArgumentException if minKey &gt; maxKey
1517 */
1518 SubMap(Object minKey, Object maxKey)
1519 {
1520 if (minKey != nil && maxKey != nil && compare(minKey, maxKey) > 0)
1521 throw new IllegalArgumentException("fromKey > toKey");
1522 this.minKey = minKey;
1523 this.maxKey = maxKey;
1524 }
1525
1526 /**
1527 * Check if "key" is in within the range bounds for this SubMap. The
1528 * lower ("from") SubMap range is inclusive, and the upper ("to") bound
1529 * is exclusive. Package visible for use by nested classes.
1530 *
1531 * @param key the key to check
1532 * @return true if the key is in range
1533 */
1534 final boolean keyInRange(Object key)
1535 {
1536 return ((minKey == nil || compare(key, minKey) >= 0)
1537 && (maxKey == nil || compare(key, maxKey) < 0));
1538 }
1539
1540 public void clear()
1541 {
1542 Node next = lowestGreaterThan(minKey, true);
1543 Node max = lowestGreaterThan(maxKey, false);
1544 while (next != max)
1545 {
1546 Node current = next;
1547 next = successor(current);
1548 removeNode(current);
1549 }
1550 }
1551
1552 public Comparator comparator()
1553 {
1554 return comparator;
1555 }
1556
1557 public boolean containsKey(Object key)
1558 {
1559 return keyInRange(key) && TreeMap.this.containsKey(key);
1560 }
1561
1562 public boolean containsValue(Object value)
1563 {
1564 Node node = lowestGreaterThan(minKey, true);
1565 Node max = lowestGreaterThan(maxKey, false);
1566 while (node != max)
1567 {
1568 if (equals(value, node.getValue()))
1569 return true;
1570 node = successor(node);
1571 }
1572 return false;
1573 }
1574
1575 public Set entrySet()
1576 {
1577 if (entries == null)
1578 // Create an AbstractSet with custom implementations of those methods
1579 // that can be overriden easily and efficiently.
1580 entries = new AbstractSet()
1581 {
1582 public int size()
1583 {
1584 return SubMap.this.size();
1585 }
1586
1587 public Iterator iterator()
1588 {
1589 Node first = lowestGreaterThan(minKey, true);
1590 Node max = lowestGreaterThan(maxKey, false);
1591 return new TreeIterator(ENTRIES, first, max);
1592 }
1593
1594 public void clear()
1595 {
1596 SubMap.this.clear();
1597 }
1598
1599 public boolean contains(Object o)
1600 {
1601 if (! (o instanceof Map.Entry))
1602 return false;
1603 Map.Entry me = (Map.Entry) o;
1604 Object key = me.getKey();
1605 if (! keyInRange(key))
1606 return false;
1607 Node n = getNode(key);
1608 return n != nil && AbstractSet.equals(me.getValue(), n.value);
1609 }
1610
1611 public boolean remove(Object o)
1612 {
1613 if (! (o instanceof Map.Entry))
1614 return false;
1615 Map.Entry me = (Map.Entry) o;
1616 Object key = me.getKey();
1617 if (! keyInRange(key))
1618 return false;
1619 Node n = getNode(key);
1620 if (n != nil && AbstractSet.equals(me.getValue(), n.value))
1621 {
1622 removeNode(n);
1623 return true;
1624 }
1625 return false;
1626 }
1627 };
1628 return entries;
1629 }
1630
1631 public Object firstKey()
1632 {
1633 Node node = lowestGreaterThan(minKey, true);
1634 if (node == nil || ! keyInRange(node.key))
1635 throw new NoSuchElementException();
1636 return node.key;
1637 }
1638
1639 public Object get(Object key)
1640 {
1641 if (keyInRange(key))
1642 return TreeMap.this.get(key);
1643 return null;
1644 }
1645
1646 public SortedMap headMap(Object toKey)
1647 {
1648 if (! keyInRange(toKey))
1649 throw new IllegalArgumentException("key outside range");
1650 return new SubMap(minKey, toKey);
1651 }
1652
1653 public Set keySet()
1654 {
1655 if (this.keys == null)
1656 // Create an AbstractSet with custom implementations of those methods
1657 // that can be overriden easily and efficiently.
1658 this.keys = new AbstractSet()
1659 {
1660 public int size()
1661 {
1662 return SubMap.this.size();
1663 }
1664
1665 public Iterator iterator()
1666 {
1667 Node first = lowestGreaterThan(minKey, true);
1668 Node max = lowestGreaterThan(maxKey, false);
1669 return new TreeIterator(KEYS, first, max);
1670 }
1671
1672 public void clear()
1673 {
1674 SubMap.this.clear();
1675 }
1676
1677 public boolean contains(Object o)
1678 {
1679 if (! keyInRange(o))
1680 return false;
1681 return getNode(o) != nil;
1682 }
1683
1684 public boolean remove(Object o)
1685 {
1686 if (! keyInRange(o))
1687 return false;
1688 Node n = getNode(o);
1689 if (n != nil)
1690 {
1691 removeNode(n);
1692 return true;
1693 }
1694 return false;
1695 }
1696 };
1697 return this.keys;
1698 }
1699
1700 public Object lastKey()
1701 {
1702 Node node = highestLessThan(maxKey);
1703 if (node == nil || ! keyInRange(node.key))
1704 throw new NoSuchElementException();
1705 return node.key;
1706 }
1707
1708 public Object put(Object key, Object value)
1709 {
1710 if (! keyInRange(key))
1711 throw new IllegalArgumentException("Key outside range");
1712 return TreeMap.this.put(key, value);
1713 }
1714
1715 public Object remove(Object key)
1716 {
1717 if (keyInRange(key))
1718 return TreeMap.this.remove(key);
1719 return null;
1720 }
1721
1722 public int size()
1723 {
1724 Node node = lowestGreaterThan(minKey, true);
1725 Node max = lowestGreaterThan(maxKey, false);
1726 int count = 0;
1727 while (node != max)
1728 {
1729 count++;
1730 node = successor(node);
1731 }
1732 return count;
1733 }
1734
1735 public SortedMap subMap(Object fromKey, Object toKey)
1736 {
1737 if (! keyInRange(fromKey) || ! keyInRange(toKey))
1738 throw new IllegalArgumentException("key outside range");
1739 return new SubMap(fromKey, toKey);
1740 }
1741
1742 public SortedMap tailMap(Object fromKey)
1743 {
1744 if (! keyInRange(fromKey))
1745 throw new IllegalArgumentException("key outside range");
1746 return new SubMap(fromKey, maxKey);
1747 }
1748
1749 public Collection values()
1750 {
1751 if (this.values == null)
1752 // Create an AbstractCollection with custom implementations of those
1753 // methods that can be overriden easily and efficiently.
1754 this.values = new AbstractCollection()
1755 {
1756 public int size()
1757 {
1758 return SubMap.this.size();
1759 }
1760
1761 public Iterator iterator()
1762 {
1763 Node first = lowestGreaterThan(minKey, true);
1764 Node max = lowestGreaterThan(maxKey, false);
1765 return new TreeIterator(VALUES, first, max);
1766 }
1767
1768 public void clear()
1769 {
1770 SubMap.this.clear();
1771 }
1772 };
1773 return this.values;
1774 }
1775 } // class SubMap
1776 } // class TreeMap

savannah-hackers-public@gnu.org
ViewVC Help
Powered by ViewVC 1.1.26