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.
5 This file is part of GNU Classpath.
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)
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.
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
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
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. */
42 import java
.io
.Serializable
;
43 import java
.io
.ObjectOutputStream
;
44 import java
.io
.ObjectInputStream
;
45 import java
.io
.IOException
;
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.
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.
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
68 * This implementation is not synchronized. If you need to share this between
69 * multiple threads, do something like:<br>
71 * = Collections.synchronizedSortedMap(new TreeMap(...));</code><p>
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.
79 * @author Jon Zeppieri
80 * @author Bryce McKinlay
81 * @author Eric Blake <ebb9@email.byu.edu>
89 * @see Collections#synchronizedSortedMap(SortedMap)
91 * @status updated to 1.4
93 public class TreeMap
extends AbstractMap
94 implements SortedMap
, Cloneable
, Serializable
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).
104 * Compatible with JDK 1.2.
106 private static final long serialVersionUID
= 919286545866124006L;
109 * Color status of a node. Package visible for use by nested classes.
111 static final int RED
= -1,
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.
121 static final Node nil
= new Node(null, null, BLACK
);
124 // Nil is self-referential, so we must initialize it after creation.
131 * The root node of this TreeMap.
133 private transient Node root
= nil
;
136 * The size of this TreeMap. Package visible for use by nested classes.
141 * The cache for {@link #entrySet()}.
143 private transient Set entries
;
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.
150 transient int modCount
;
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
157 final Comparator comparator
;
160 * Class to represent an entry in the tree. Holds a single key-value pair,
161 * plus pointers to parent and child nodes.
163 * @author Eric Blake <ebb9@email.byu.edu>
165 private static final class Node
extends AbstractMap
.BasicMapEntry
167 // All fields package visible for use by nested classes.
168 /** The color of this node. */
171 /** The left child node. */
173 /** The right child node. */
175 /** The parent node. */
179 * Simple constructor.
181 * @param value the value
183 Node(Object key
, Object value
, int color
)
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}.
201 this((Comparator
) null);
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}.
210 * @param comparator the sort order for the keys of this map, or null
211 * for the natural order
213 public TreeMap(Comparator c
)
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}.
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
229 * @throws NullPointerException if map is null
232 public TreeMap(Map map
)
234 this((Comparator
) null);
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.
243 * @param sm a SortedMap, whose entries will be put into this TreeMap
244 * @throws NullPointerException if sm is null
246 public TreeMap(SortedMap sm
)
248 this(sm
.comparator());
250 Iterator itr
= sm
.entrySet().iterator();
253 Node node
= firstNode();
257 Map
.Entry me
= (Map
.Entry
) itr
.next();
258 node
.key
= me
.getKey();
259 node
.value
= me
.getValue();
260 node
= successor(node
);
265 * Clears the Map so it has no keys. This is O(1).
278 * Returns a shallow clone of this TreeMap. The Map itself is cloned,
279 * but its contents are not.
283 public Object
clone()
288 copy
= (TreeMap
) super.clone();
290 catch (CloneNotSupportedException x
)
294 copy
.fabricateTree(size
);
296 Node node
= firstNode();
297 Node cnode
= copy
.firstNode();
301 cnode
.key
= node
.key
;
302 cnode
.value
= node
.value
;
303 node
= successor(node
);
304 cnode
= copy
.successor(cnode
);
310 * Return the comparator used to sort this map, or null if it is by
313 * @return the map's comparator
315 public Comparator
comparator()
321 * Returns true if the map contains a mapping for the given key.
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
329 public boolean containsKey(Object key
)
331 return getNode(key
) != nil
;
335 * Returns true if the map contains at least one mapping to the given value.
336 * This requires linear time.
338 * @param value the value to look for
339 * @return true if the value appears in a mapping
341 public boolean containsValue(Object value
)
343 Node node
= firstNode();
346 if (equals(value
, node
.value
))
348 node
= successor(node
);
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>
358 * Note that the iterators for all three views, from keySet(), entrySet(),
359 * and values(), traverse the TreeMap in sorted sequence.
361 * @return a set view of the entries
366 public Set
entrySet()
369 // Create an AbstractSet with custom implementations of those methods
370 // that can be overriden easily and efficiently.
371 entries
= new AbstractSet()
378 public Iterator
iterator()
380 return new TreeIterator(ENTRIES
);
385 TreeMap
.this.clear();
388 public boolean contains(Object o
)
390 if (! (o
instanceof Map
.Entry
))
392 Map
.Entry me
= (Map
.Entry
) o
;
393 Node n
= getNode(me
.getKey());
394 return n
!= nil
&& AbstractSet
.equals(me
.getValue(), n
.value
);
397 public boolean remove(Object o
)
399 if (! (o
instanceof Map
.Entry
))
401 Map
.Entry me
= (Map
.Entry
) o
;
402 Node n
= getNode(me
.getKey());
403 if (n
!= nil
&& AbstractSet
.equals(me
.getValue(), n
.value
))
415 * Returns the first (lowest) key in the map.
417 * @return the first key
418 * @throws NoSuchElementException if the map is empty
420 public Object
firstKey()
423 throw new NoSuchElementException();
424 return firstNode().key
;
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.
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
438 * @see #put(Object, Object)
439 * @see #containsKey(Object)
441 public Object
get(Object key
)
443 // Exploit fact that nil.value == null.
444 return getNode(key
).value
;
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.
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
462 public SortedMap
headMap(Object toKey
)
464 return new SubMap(nil
, toKey
);
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.
472 * @return a set view of the keys
479 // Create an AbstractSet with custom implementations of those methods
480 // that can be overriden easily and efficiently.
481 keys
= new AbstractSet()
488 public Iterator
iterator()
490 return new TreeIterator(KEYS
);
495 TreeMap
.this.clear();
498 public boolean contains(Object o
)
500 return containsKey(o
);
503 public boolean remove(Object key
)
505 Node n
= getNode(key
);
516 * Returns the last (highest) key in the map.
518 * @return the last key
519 * @throws NoSuchElementException if the map is empty
521 public Object
lastKey()
524 throw new NoSuchElementException("empty");
525 return lastNode().key
;
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
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
542 * @see Object#equals(Object)
544 public Object
put(Object key
, Object value
)
550 // Find new node's parent.
551 while (current
!= nil
)
554 comparison
= compare(key
, current
.key
);
556 current
= current
.right
;
557 else if (comparison
< 0)
558 current
= current
.left
;
559 else // Key already in tree.
560 return current
.setValue(value
);
564 Node n
= new Node(key
, value
, RED
);
567 // Insert node in tree.
572 // Special case inserting into an empty tree.
581 // Rebalance after insert.
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
591 * @param m the map to be hashed into this
592 * @throws ClassCastException if a key in m is not comparable with keys
594 * @throws NullPointerException if a key in m is null, and the comparator
595 * does not tolerate nulls
597 public void putAll(Map m
)
599 Iterator itr
= m
.entrySet().iterator();
603 Map
.Entry e
= (Map
.Entry
) itr
.next();
604 put(e
.getKey(), e
.getValue());
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.
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
621 public Object
remove(Object key
)
623 Node n
= getNode(key
);
626 // Note: removeNode can alter the contents of n, so save value now.
627 Object result
= n
.value
;
633 * Returns the number of key-value mappings currently in this Map.
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.
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
661 public SortedMap
subMap(Object fromKey
, Object toKey
)
663 return new SubMap(fromKey
, toKey
);
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.
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
681 public SortedMap
tailMap(Object fromKey
)
683 return new SubMap(fromKey
, nil
);
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
692 * @return a bag view of the values
696 public Collection
values()
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()
708 public Iterator
iterator()
710 return new TreeIterator(VALUES
);
715 TreeMap
.this.clear();
722 * Compares two elements by the set comparator, or by natural ordering.
723 * Package visible for use by nested classes.
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
731 final int compare(Object o1
, Object o2
)
733 return (comparator
== null
734 ?
((Comparable
) o1
).compareTo(o2
)
735 : comparator
.compare(o1
, o2
));
739 * Maintain red-black balance after deleting a node.
741 * @param node the child of the node just deleted, possibly nil
742 * @param parent the parent of the node just deleted, never nil
744 private void deleteFixup(Node node
, Node parent
)
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
)
753 if (node
== parent
.left
)
755 // Rebalance left side.
756 Node sibling
= parent
.right
;
757 // if (sibling == nil)
758 // throw new InternalError();
759 if (sibling
.color
== RED
)
761 // Case 1: Sibling is red.
762 // Recolor sibling and parent, and rotate parent left.
763 sibling
.color
= BLACK
;
766 sibling
= parent
.right
;
769 if (sibling
.left
.color
== BLACK
&& sibling
.right
.color
== BLACK
)
771 // Case 2: Sibling has no red children.
772 // Recolor sibling, and move to parent.
775 parent
= parent
.parent
;
779 if (sibling
.right
.color
== BLACK
)
781 // Case 3: Sibling has red left child.
782 // Recolor sibling and left child, rotate sibling right.
783 sibling
.left
.color
= BLACK
;
785 rotateRight(sibling
);
786 sibling
= parent
.right
;
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
;
794 node
= root
; // Finished.
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
)
805 // Case 1: Sibling is red.
806 // Recolor sibling and parent, and rotate parent right.
807 sibling
.color
= BLACK
;
810 sibling
= parent
.left
;
813 if (sibling
.right
.color
== BLACK
&& sibling
.left
.color
== BLACK
)
815 // Case 2: Sibling has no red children.
816 // Recolor sibling, and move to parent.
819 parent
= parent
.parent
;
823 if (sibling
.left
.color
== BLACK
)
825 // Case 3: Sibling has red right child.
826 // Recolor sibling and right child, rotate sibling left.
827 sibling
.right
.color
= BLACK
;
830 sibling
= parent
.left
;
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
;
838 node
= root
; // Finished.
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.
849 * @param count the number of blank nodes, non-negative
851 private void fabricateTree(final int count
)
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.
861 // Make the root node.
862 root
= new Node(null, null, BLACK
);
867 // Fill each row that is completely full of nodes.
868 for (rowsize
= 2; rowsize
+ rowsize
<= count
; rowsize
<<= 1)
872 for (int i
= 0; i
< rowsize
; i
+= 2)
874 Node left
= new Node(null, null, BLACK
);
875 Node right
= new Node(null, null, BLACK
);
876 left
.parent
= parent
;
878 right
.parent
= parent
;
880 Node next
= parent
.right
;
881 parent
.right
= right
;
890 // Now do the partial final row in red.
891 int overflow
= count
- rowsize
;
894 for (i
= 0; i
< overflow
; i
+= 2)
896 Node left
= new Node(null, null, RED
);
897 Node right
= new Node(null, null, RED
);
898 left
.parent
= parent
;
899 right
.parent
= parent
;
901 Node next
= parent
.right
;
902 parent
.right
= right
;
905 // Add a lone left node if necessary.
906 if (i
- overflow
== 0)
908 Node left
= new Node(null, null, RED
);
909 left
.parent
= parent
;
911 parent
= parent
.right
;
912 left
.parent
.right
= nil
;
914 // Unlink the remaining nodes of the previous row.
915 while (parent
!= nil
)
917 Node next
= parent
.right
;
924 * Returns the first sorted node in the map, or nil if empty. Package
925 * visible for use by nested classes.
927 * @return the first node
929 final Node
firstNode()
931 // Exploit fact that nil.left == nil.
933 while (node
.left
!= nil
)
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.
942 * @param key the key to search for
943 * @return the node where the key is found, or nil
945 final Node
getNode(Object key
)
948 while (current
!= nil
)
950 int comparison
= compare(key
, current
.key
);
952 current
= current
.right
;
953 else if (comparison
< 0)
954 current
= current
.left
;
962 * Find the "highest" node which is < key. If key is nil, return last
963 * node. Package visible for use by nested classes.
965 * @param key the upper bound, exclusive
966 * @return the previous node
968 final Node
highestLessThan(Object key
)
977 while (current
!= nil
)
980 comparison
= compare(key
, current
.key
);
982 current
= current
.right
;
983 else if (comparison
< 0)
984 current
= current
.left
;
986 return predecessor(last
);
988 return comparison
<= 0 ?
predecessor(last
) : last
;
992 * Maintain red-black balance after inserting a new node.
994 * @param n the newly inserted node
996 private void insertFixup(Node n
)
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
)
1003 if (n
.parent
== n
.parent
.parent
.left
)
1005 Node uncle
= n
.parent
.parent
.right
;
1006 // Uncle may be nil, in which case it is BLACK.
1007 if (uncle
.color
== RED
)
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
;
1018 if (n
== n
.parent
.right
)
1020 // Case 2. Uncle is BLACK and x is right child.
1021 // Move n to parent, and rotate n left.
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
);
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
)
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
;
1048 if (n
== n
.parent
.left
)
1050 // Case 2. Uncle is BLACK and x is left child.
1051 // Move n to parent, and rotate n right.
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
);
1067 * Returns the last sorted node in the map, or nil if empty.
1069 * @return the last node
1071 private Node
lastNode()
1073 // Exploit fact that nil.right == nil.
1075 while (node
.right
!= nil
)
1081 * Find the "lowest" node which is >= 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.
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
1089 final Node
lowestGreaterThan(Object key
, boolean first
)
1092 return first ?
firstNode() : nil
;
1095 Node current
= root
;
1098 while (current
!= nil
)
1101 comparison
= compare(key
, current
.key
);
1103 current
= current
.right
;
1104 else if (comparison
< 0)
1105 current
= current
.left
;
1109 return comparison
> 0 ?
successor(last
) : last
;
1113 * Return the node preceding the given one, or nil if there isn't one.
1115 * @param node the current node, not nil
1116 * @return the prior node in sorted order
1118 private Node
predecessor(Node node
)
1120 if (node
.left
!= nil
)
1123 while (node
.right
!= nil
)
1128 Node parent
= node
.parent
;
1129 // Exploit fact that nil.left == nil and node is non-nil.
1130 while (node
== parent
.left
)
1133 parent
= node
.parent
;
1139 * Construct a tree from sorted keys in linear time. Package visible for
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)
1150 final void putFromObjStream(ObjectInputStream s
, int count
,
1152 throws IOException
, ClassNotFoundException
1154 fabricateTree(count
);
1155 Node node
= firstNode();
1157 while (--count
>= 0)
1159 node
.key
= s
.readObject();
1160 node
.value
= readValues ? s
.readObject() : "";
1161 node
= successor(node
);
1166 * Construct a tree from sorted keys in linear time, with values of "".
1167 * Package visible for use by TreeSet.
1169 * @param keys the iterator over the sorted keys
1170 * @param count the number of nodes to insert
1171 * @see TreeSet#TreeSet(SortedSet)
1173 final void putKeysLinear(Iterator keys
, int count
)
1175 fabricateTree(count
);
1176 Node node
= firstNode();
1178 while (--count
>= 0)
1180 node
.key
= keys
.next();
1182 node
= successor(node
);
1187 * Deserializes this object from the given stream.
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
1195 private void readObject(ObjectInputStream s
)
1196 throws IOException
, ClassNotFoundException
1198 s
.defaultReadObject();
1199 int size
= s
.readInt();
1200 putFromObjStream(s
, size
, true);
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.
1207 * @param node the node to remove
1209 final void removeNode(Node node
)
1217 // Find splice, the node at the position to actually remove from the tree.
1218 if (node
.left
== nil
)
1220 // Node to be deleted has 0 or 1 children.
1224 else if (node
.right
== nil
)
1226 // Node to be deleted has 1 child.
1232 // Node has 2 children. Splice is node's predecessor, and we swap
1233 // its contents into node.
1235 while (splice
.right
!= nil
)
1236 splice
= splice
.right
;
1237 child
= splice
.left
;
1238 node
.key
= splice
.key
;
1239 node
.value
= splice
.value
;
1242 // Unlink splice from the tree.
1243 Node parent
= splice
.parent
;
1245 child
.parent
= parent
;
1248 // Special case for 0 or 1 node remaining.
1252 if (splice
== parent
.left
)
1253 parent
.left
= child
;
1255 parent
.right
= child
;
1257 if (splice
.color
== BLACK
)
1258 deleteFixup(child
, parent
);
1262 * Rotate node n to the left.
1264 * @param node the node to rotate
1266 private void rotateLeft(Node node
)
1268 Node child
= node
.right
;
1269 // if (node == nil || child == nil)
1270 // throw new InternalError();
1272 // Establish node.right link.
1273 node
.right
= child
.left
;
1274 if (child
.left
!= nil
)
1275 child
.left
.parent
= node
;
1277 // Establish child->parent link.
1278 child
.parent
= node
.parent
;
1279 if (node
.parent
!= nil
)
1281 if (node
== node
.parent
.left
)
1282 node
.parent
.left
= child
;
1284 node
.parent
.right
= child
;
1289 // Link n and child.
1291 node
.parent
= child
;
1295 * Rotate node n to the right.
1297 * @param node the node to rotate
1299 private void rotateRight(Node node
)
1301 Node child
= node
.left
;
1302 // if (node == nil || child == nil)
1303 // throw new InternalError();
1305 // Establish node.left link.
1306 node
.left
= child
.right
;
1307 if (child
.right
!= nil
)
1308 child
.right
.parent
= node
;
1310 // Establish child->parent link.
1311 child
.parent
= node
.parent
;
1312 if (node
.parent
!= nil
)
1314 if (node
== node
.parent
.right
)
1315 node
.parent
.right
= child
;
1317 node
.parent
.left
= child
;
1322 // Link n and child.
1324 node
.parent
= child
;
1328 * Return the node following the given one, or nil if there isn't one.
1329 * Package visible for use by nested classes.
1331 * @param node the current node, not nil
1332 * @return the next node in sorted order
1334 final Node
successor(Node node
)
1336 if (node
.right
!= nil
)
1339 while (node
.left
!= nil
)
1344 Node parent
= node
.parent
;
1345 // Exploit fact that nil.right == nil and node is non-nil.
1346 while (node
== parent
.right
)
1349 parent
= parent
.parent
;
1355 * Serializes this object to the given stream.
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
1362 private void writeObject(ObjectOutputStream s
) throws IOException
1364 s
.defaultWriteObject();
1366 Node node
= firstNode();
1370 s
.writeObject(node
.key
);
1371 s
.writeObject(node
.value
);
1372 node
= successor(node
);
1377 * Iterate over HashMap's entries. This implementation is parameterized
1378 * to give a sequential view of keys, values, or entries.
1380 * @author Eric Blake <ebb9@email.byu.edu>
1382 private final class TreeIterator
implements Iterator
1385 * The type of this Iterator: {@link #KEYS}, {@link #VALUES},
1386 * or {@link #ENTRIES}.
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. */
1393 /** The next entry that should be returned by next(). */
1396 * The last node visible to this iterator. This is used when iterating
1399 private final Node max
;
1402 * Construct a new TreeIterator with the supplied type.
1403 * @param type {@link #KEYS}, {@link #VALUES}, or {@link #ENTRIES}
1405 TreeIterator(int type
)
1407 // FIXME gcj cannot handle this. Bug java/4695
1408 // this(type, firstNode(), nil);
1410 this.next
= firstNode();
1415 * Construct a new TreeIterator with the supplied type. Iteration will
1416 * be from "first" (inclusive) to "max" (exclusive).
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
1422 TreeIterator(int type
, Node first
, Node max
)
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
1434 public boolean hasNext()
1436 if (knownMod
!= modCount
)
1437 throw new ConcurrentModificationException();
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
1447 public Object
next()
1449 if (knownMod
!= modCount
)
1450 throw new ConcurrentModificationException();
1452 throw new NoSuchElementException();
1454 next
= successor(last
);
1458 else if (type
== KEYS
)
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
1469 public void remove()
1472 throw new IllegalStateException();
1473 if (knownMod
!= modCount
)
1474 throw new ConcurrentModificationException();
1480 } // class TreeIterator
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.
1488 * @author Eric Blake <ebb9@email.byu.edu>
1490 private final class SubMap
extends AbstractMap
implements SortedMap
1493 * The lower range of this view, inclusive, or nil for unbounded.
1494 * Package visible for use by nested classes.
1496 final Object minKey
;
1499 * The upper range of this view, exclusive, or nil for unbounded.
1500 * Package visible for use by nested classes.
1502 final Object maxKey
;
1505 * The cache for {@link #entrySet()}.
1507 private Set entries
;
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).
1514 * @param minKey the lower bound
1515 * @param maxKey the upper bound
1516 * @throws IllegalArgumentException if minKey > maxKey
1518 SubMap(Object minKey
, Object maxKey
)
1520 if (minKey
!= nil
&& maxKey
!= nil
&& compare(minKey
, maxKey
) > 0)
1521 throw new IllegalArgumentException("fromKey > toKey");
1522 this.minKey
= minKey
;
1523 this.maxKey
= maxKey
;
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.
1531 * @param key the key to check
1532 * @return true if the key is in range
1534 final boolean keyInRange(Object key
)
1536 return ((minKey
== nil
|| compare(key
, minKey
) >= 0)
1537 && (maxKey
== nil
|| compare(key
, maxKey
) < 0));
1542 Node next
= lowestGreaterThan(minKey
, true);
1543 Node max
= lowestGreaterThan(maxKey
, false);
1546 Node current
= next
;
1547 next
= successor(current
);
1548 removeNode(current
);
1552 public Comparator
comparator()
1557 public boolean containsKey(Object key
)
1559 return keyInRange(key
) && TreeMap
.this.containsKey(key
);
1562 public boolean containsValue(Object value
)
1564 Node node
= lowestGreaterThan(minKey
, true);
1565 Node max
= lowestGreaterThan(maxKey
, false);
1568 if (equals(value
, node
.getValue()))
1570 node
= successor(node
);
1575 public Set
entrySet()
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()
1584 return SubMap
.this.size();
1587 public Iterator
iterator()
1589 Node first
= lowestGreaterThan(minKey
, true);
1590 Node max
= lowestGreaterThan(maxKey
, false);
1591 return new TreeIterator(ENTRIES
, first
, max
);
1596 SubMap
.this.clear();
1599 public boolean contains(Object o
)
1601 if (! (o
instanceof Map
.Entry
))
1603 Map
.Entry me
= (Map
.Entry
) o
;
1604 Object key
= me
.getKey();
1605 if (! keyInRange(key
))
1607 Node n
= getNode(key
);
1608 return n
!= nil
&& AbstractSet
.equals(me
.getValue(), n
.value
);
1611 public boolean remove(Object o
)
1613 if (! (o
instanceof Map
.Entry
))
1615 Map
.Entry me
= (Map
.Entry
) o
;
1616 Object key
= me
.getKey();
1617 if (! keyInRange(key
))
1619 Node n
= getNode(key
);
1620 if (n
!= nil
&& AbstractSet
.equals(me
.getValue(), n
.value
))
1631 public Object
firstKey()
1633 Node node
= lowestGreaterThan(minKey
, true);
1634 if (node
== nil
|| ! keyInRange(node
.key
))
1635 throw new NoSuchElementException();
1639 public Object
get(Object key
)
1641 if (keyInRange(key
))
1642 return TreeMap
.this.get(key
);
1646 public SortedMap
headMap(Object toKey
)
1648 if (! keyInRange(toKey
))
1649 throw new IllegalArgumentException("key outside range");
1650 return new SubMap(minKey
, toKey
);
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()
1662 return SubMap
.this.size();
1665 public Iterator
iterator()
1667 Node first
= lowestGreaterThan(minKey
, true);
1668 Node max
= lowestGreaterThan(maxKey
, false);
1669 return new TreeIterator(KEYS
, first
, max
);
1674 SubMap
.this.clear();
1677 public boolean contains(Object o
)
1679 if (! keyInRange(o
))
1681 return getNode(o
) != nil
;
1684 public boolean remove(Object o
)
1686 if (! keyInRange(o
))
1688 Node n
= getNode(o
);
1700 public Object
lastKey()
1702 Node node
= highestLessThan(maxKey
);
1703 if (node
== nil
|| ! keyInRange(node
.key
))
1704 throw new NoSuchElementException();
1708 public Object
put(Object key
, Object value
)
1710 if (! keyInRange(key
))
1711 throw new IllegalArgumentException("Key outside range");
1712 return TreeMap
.this.put(key
, value
);
1715 public Object
remove(Object key
)
1717 if (keyInRange(key
))
1718 return TreeMap
.this.remove(key
);
1724 Node node
= lowestGreaterThan(minKey
, true);
1725 Node max
= lowestGreaterThan(maxKey
, false);
1730 node
= successor(node
);
1735 public SortedMap
subMap(Object fromKey
, Object toKey
)
1737 if (! keyInRange(fromKey
) || ! keyInRange(toKey
))
1738 throw new IllegalArgumentException("key outside range");
1739 return new SubMap(fromKey
, toKey
);
1742 public SortedMap
tailMap(Object fromKey
)
1744 if (! keyInRange(fromKey
))
1745 throw new IllegalArgumentException("key outside range");
1746 return new SubMap(fromKey
, maxKey
);
1749 public Collection
values()
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()
1758 return SubMap
.this.size();
1761 public Iterator
iterator()
1763 Node first
= lowestGreaterThan(minKey
, true);
1764 Node max
= lowestGreaterThan(maxKey
, false);
1765 return new TreeIterator(VALUES
, first
, max
);
1770 SubMap
.this.clear();