0
|
1 /*
|
|
2 * Copyright 2000 Sun Microsystems, Inc. All Rights Reserved.
|
|
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
|
|
4 *
|
|
5 * This code is free software; you can redistribute it and/or modify it
|
|
6 * under the terms of the GNU General Public License version 2 only, as
|
|
7 * published by the Free Software Foundation.
|
|
8 *
|
|
9 * This code is distributed in the hope that it will be useful, but WITHOUT
|
|
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
12 * version 2 for more details (a copy is included in the LICENSE file that
|
|
13 * accompanied this code).
|
|
14 *
|
|
15 * You should have received a copy of the GNU General Public License version
|
|
16 * 2 along with this work; if not, write to the Free Software Foundation,
|
|
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
|
|
18 *
|
|
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
|
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or
|
|
21 * have any questions.
|
|
22 *
|
|
23 */
|
|
24
|
|
25 package sun.jvm.hotspot.utilities;
|
|
26
|
|
27 /** This class implements a node in a red-black tree. It provides
|
|
28 accessors for the left and right children as well as the color of
|
|
29 the node. */
|
|
30
|
|
31 public class RBNode {
|
|
32 private Object data;
|
|
33 private RBNode left;
|
|
34 private RBNode right;
|
|
35 private RBNode parent;
|
|
36 private RBColor color;
|
|
37
|
|
38 /** Newly-created nodes are colored red */
|
|
39 public RBNode(Object data) {
|
|
40 this.data = data;
|
|
41 color = RBColor.RED;
|
|
42 }
|
|
43
|
|
44 public Object getData() {
|
|
45 return data;
|
|
46 }
|
|
47
|
|
48 /** Must copy all user-defined fields from the given node. For
|
|
49 example, the base implementation copies the "data" field.
|
|
50 However, it does not (and must not) copy the link fields
|
|
51 (parent, left child, right child). It also does not need to copy
|
|
52 any computed information for the node, as the node will be
|
|
53 updated when necessary. Subclasses must be careful to call the
|
|
54 superclass implementation. */
|
|
55 public void copyFrom(RBNode arg) {
|
|
56 this.data = arg.data;
|
|
57 }
|
|
58
|
|
59 /** This is called by the base RBTree's insertion and deletion
|
|
60 methods when necessary. Subclasses can use this to update any
|
|
61 computed information based on the information in their left or
|
|
62 right children. For multi-node updates it is guaranteed that
|
|
63 this method will be called in the correct order. This should
|
|
64 return true if an update actually occurred, false if not. */
|
|
65 public boolean update() {
|
|
66 return false;
|
|
67 }
|
|
68
|
|
69 public RBColor getColor() { return color; }
|
|
70 public void setColor(RBColor color) { this.color = color; }
|
|
71
|
|
72 public RBNode getParent() { return parent; }
|
|
73 public void setParent(RBNode parent) { this.parent = parent; }
|
|
74
|
|
75 /** Access to left child */
|
|
76 public RBNode getLeft() { return left; }
|
|
77 public void setLeft(RBNode left) { this.left = left; }
|
|
78
|
|
79 /** Access to right child */
|
|
80 public RBNode getRight() { return right; }
|
|
81 public void setRight(RBNode right) { this.right = right; }
|
|
82 }
|