1/*
2 * Copyright (c) 2000, 2003, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25package sun.jvm.hotspot.utilities;
26
27/** Derived from the example in Section 15.3 of CLR. */
28
29import java.io.PrintStream;
30import java.util.ArrayList;
31import java.util.Comparator;
32import java.util.List;
33
34public 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}
176