Mercurial > hg > truffle
comparison agent/src/share/classes/sun/jvm/hotspot/utilities/IntervalTree.java @ 0:a61af66fc99e jdk7-b24
Initial load
author | duke |
---|---|
date | Sat, 01 Dec 2007 00:00:00 +0000 |
parents | |
children | c18cbe5936b8 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a61af66fc99e |
---|---|
1 /* | |
2 * Copyright 2000-2003 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 /** Derived from the example in Section 15.3 of CLR. */ | |
28 | |
29 import java.io.PrintStream; | |
30 import java.util.ArrayList; | |
31 import java.util.Comparator; | |
32 import java.util.List; | |
33 | |
34 public class IntervalTree extends RBTree { | |
35 private Comparator endpointComparator; | |
36 | |
37 /** This constructor takes only one comparator: one which operates | |
38 upon the endpoints of the Intervals this tree will store. It | |
39 constructs an internal "interval comparator" out of this one. */ | |
40 public IntervalTree(Comparator endpointComparator) { | |
41 super(new IntervalComparator(endpointComparator)); | |
42 this.endpointComparator = endpointComparator; | |
43 } | |
44 | |
45 public void insert(Interval interval, Object data) { | |
46 IntervalNode node = new IntervalNode(interval, endpointComparator, data); | |
47 insertNode(node); | |
48 } | |
49 | |
50 /** Returns a List<IntervalNode> indicating which nodes' | |
51 intervals were intersected by the given query interval. It is | |
52 guaranteed that these nodes will be returned sorted by | |
53 increasing low endpoint. */ | |
54 public List findAllNodesIntersecting(Interval interval) { | |
55 List retList = new ArrayList(); | |
56 searchForIntersectingNodesFrom((IntervalNode) getRoot(), interval, retList); | |
57 return retList; | |
58 } | |
59 | |
60 public void print() { | |
61 printOn(System.out); | |
62 } | |
63 | |
64 public void printOn(PrintStream tty) { | |
65 printFromNode(getRoot(), tty, 0); | |
66 } | |
67 | |
68 //---------------------------------------------------------------------- | |
69 // Overridden internal functionality | |
70 | |
71 protected Object getNodeValue(RBNode node) { | |
72 return ((IntervalNode) node).getInterval(); | |
73 } | |
74 | |
75 protected void verify() { | |
76 super.verify(); | |
77 verifyFromNode(getRoot()); | |
78 } | |
79 | |
80 //---------------------------------------------------------------------- | |
81 // Internals only below this point | |
82 // | |
83 | |
84 private void verifyFromNode(RBNode node) { | |
85 if (node == null) { | |
86 return; | |
87 } | |
88 | |
89 // We already know that the red/black structure has been verified. | |
90 // What we need to find out is whether this node has been updated | |
91 // properly -- i.e., whether its notion of the maximum endpoint is | |
92 // correct. | |
93 IntervalNode intNode = (IntervalNode) node; | |
94 if (!intNode.getMaxEndpoint().equals(intNode.computeMaxEndpoint())) { | |
95 if (DEBUGGING && VERBOSE) { | |
96 print(); | |
97 } | |
98 throw new RuntimeException("Node's max endpoint was not updated properly"); | |
99 } | |
100 if (!intNode.getMinEndpoint().equals(intNode.computeMinEndpoint())) { | |
101 if (DEBUGGING && VERBOSE) { | |
102 print(); | |
103 } | |
104 throw new RuntimeException("Node's min endpoint was not updated properly"); | |
105 } | |
106 | |
107 verifyFromNode(node.getLeft()); | |
108 verifyFromNode(node.getRight()); | |
109 } | |
110 | |
111 static class IntervalComparator implements Comparator { | |
112 private Comparator endpointComparator; | |
113 | |
114 public IntervalComparator(Comparator endpointComparator) { | |
115 this.endpointComparator = endpointComparator; | |
116 } | |
117 | |
118 public int compare(Object o1, Object o2) { | |
119 Interval i1 = (Interval) o1; | |
120 Interval i2 = (Interval) o2; | |
121 return endpointComparator.compare(i1.getLowEndpoint(), i2.getLowEndpoint()); | |
122 } | |
123 } | |
124 | |
125 private void searchForIntersectingNodesFrom(IntervalNode node, | |
126 Interval interval, | |
127 List resultList) { | |
128 if (node == null) { | |
129 return; | |
130 } | |
131 | |
132 // Inorder traversal (very important to guarantee sorted order) | |
133 | |
134 // Check to see whether we have to traverse the left subtree | |
135 IntervalNode left = (IntervalNode) node.getLeft(); | |
136 if ((left != null) && | |
137 (endpointComparator.compare(left.getMaxEndpoint(), | |
138 interval.getLowEndpoint()) > 0)) { | |
139 searchForIntersectingNodesFrom(left, interval, resultList); | |
140 } | |
141 | |
142 // Check for intersection with current node | |
143 if (node.getInterval().overlaps(interval, endpointComparator)) { | |
144 resultList.add(node); | |
145 } | |
146 | |
147 // Check to see whether we have to traverse the left subtree | |
148 IntervalNode right = (IntervalNode) node.getRight(); | |
149 if ((right != null) && | |
150 (endpointComparator.compare(interval.getHighEndpoint(), | |
151 right.getMinEndpoint()) > 0)) { | |
152 searchForIntersectingNodesFrom(right, interval, resultList); | |
153 } | |
154 } | |
155 | |
156 /** Debugging */ | |
157 private void printFromNode(RBNode node, PrintStream tty, int indentDepth) { | |
158 for (int i = 0; i < indentDepth; i++) { | |
159 tty.print(" "); | |
160 } | |
161 | |
162 tty.print("-"); | |
163 if (node == null) { | |
164 tty.println(); | |
165 return; | |
166 } | |
167 | |
168 tty.println(" " + node + | |
169 " (min " + ((IntervalNode) node).getMinEndpoint() + | |
170 ", max " + ((IntervalNode) node).getMaxEndpoint() + ")" + | |
171 ((node.getColor() == RBColor.RED) ? " (red)" : " (black)")); | |
172 if (node.getLeft() != null) printFromNode(node.getLeft(), tty, indentDepth + 2); | |
173 if (node.getRight() != null) printFromNode(node.getRight(), tty, indentDepth + 2); | |
174 } | |
175 } |