0
|
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 }
|