--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/agent/src/share/classes/sun/jvm/hotspot/utilities/IntervalTree.java	Sat Dec 01 00:00:00 2007 +0000
@@ -0,0 +1,175 @@
+/*
+ * Copyright 2000-2003 Sun Microsystems, Inc.  All Rights Reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
+ * CA 95054 USA or visit www.sun.com if you need additional information or
+ * have any questions.
+ *
+ */
+
+package sun.jvm.hotspot.utilities;
+
+/** Derived from the example in Section 15.3 of CLR. */
+
+import java.io.PrintStream;
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+
+public class IntervalTree extends RBTree {
+  private Comparator endpointComparator;
+
+  /** This constructor takes only one comparator: one which operates
+      upon the endpoints of the Intervals this tree will store. It
+      constructs an internal "interval comparator" out of this one. */
+  public IntervalTree(Comparator endpointComparator) {
+    super(new IntervalComparator(endpointComparator));
+    this.endpointComparator = endpointComparator;
+  }
+
+  public void insert(Interval interval, Object data) {
+    IntervalNode node = new IntervalNode(interval, endpointComparator, data);
+    insertNode(node);
+  }
+
+  /** Returns a List<IntervalNode> indicating which nodes'
+      intervals were intersected by the given query interval. It is
+      guaranteed that these nodes will be returned sorted by
+      increasing low endpoint. */
+  public List findAllNodesIntersecting(Interval interval) {
+    List retList = new ArrayList();
+    searchForIntersectingNodesFrom((IntervalNode) getRoot(), interval, retList);
+    return retList;
+  }
+
+  public void print() {
+    printOn(System.out);
+  }
+
+  public void printOn(PrintStream tty) {
+    printFromNode(getRoot(), tty, 0);
+  }
+
+  //----------------------------------------------------------------------
+  // Overridden internal functionality
+
+  protected Object getNodeValue(RBNode node) {
+    return ((IntervalNode) node).getInterval();
+  }
+
+  protected void verify() {
+    super.verify();
+    verifyFromNode(getRoot());
+  }
+
+  //----------------------------------------------------------------------
+  // Internals only below this point
+  //
+
+  private void verifyFromNode(RBNode node) {
+    if (node == null) {
+      return;
+    }
+
+    // We already know that the red/black structure has been verified.
+    // What we need to find out is whether this node has been updated
+    // properly -- i.e., whether its notion of the maximum endpoint is
+    // correct.
+    IntervalNode intNode = (IntervalNode) node;
+    if (!intNode.getMaxEndpoint().equals(intNode.computeMaxEndpoint())) {
+      if (DEBUGGING && VERBOSE) {
+        print();
+      }
+      throw new RuntimeException("Node's max endpoint was not updated properly");
+    }
+    if (!intNode.getMinEndpoint().equals(intNode.computeMinEndpoint())) {
+      if (DEBUGGING && VERBOSE) {
+        print();
+      }
+      throw new RuntimeException("Node's min endpoint was not updated properly");
+    }
+
+    verifyFromNode(node.getLeft());
+    verifyFromNode(node.getRight());
+  }
+
+  static class IntervalComparator implements Comparator {
+    private Comparator endpointComparator;
+
+    public IntervalComparator(Comparator endpointComparator) {
+      this.endpointComparator = endpointComparator;
+    }
+
+    public int compare(Object o1, Object o2) {
+      Interval i1 = (Interval) o1;
+      Interval i2 = (Interval) o2;
+      return endpointComparator.compare(i1.getLowEndpoint(), i2.getLowEndpoint());
+    }
+  }
+
+  private void searchForIntersectingNodesFrom(IntervalNode node,
+                                              Interval interval,
+                                              List resultList) {
+    if (node == null) {
+      return;
+    }
+
+    // Inorder traversal (very important to guarantee sorted order)
+
+    // Check to see whether we have to traverse the left subtree
+    IntervalNode left = (IntervalNode) node.getLeft();
+    if ((left != null) &&
+        (endpointComparator.compare(left.getMaxEndpoint(),
+                                    interval.getLowEndpoint()) > 0)) {
+      searchForIntersectingNodesFrom(left, interval, resultList);
+    }
+
+    // Check for intersection with current node
+    if (node.getInterval().overlaps(interval, endpointComparator)) {
+      resultList.add(node);
+    }
+
+    // Check to see whether we have to traverse the left subtree
+    IntervalNode right = (IntervalNode) node.getRight();
+    if ((right != null) &&
+        (endpointComparator.compare(interval.getHighEndpoint(),
+                                    right.getMinEndpoint()) > 0)) {
+      searchForIntersectingNodesFrom(right, interval, resultList);
+    }
+  }
+
+  /** Debugging */
+  private void printFromNode(RBNode node, PrintStream tty, int indentDepth) {
+    for (int i = 0; i < indentDepth; i++) {
+      tty.print(" ");
+    }
+
+    tty.print("-");
+    if (node == null) {
+      tty.println();
+      return;
+    }
+
+    tty.println(" " + node +
+                " (min " + ((IntervalNode) node).getMinEndpoint() +
+                ", max " + ((IntervalNode) node).getMaxEndpoint() + ")" +
+                ((node.getColor() == RBColor.RED) ? " (red)" : " (black)"));
+    if (node.getLeft()  != null) printFromNode(node.getLeft(),  tty, indentDepth + 2);
+    if (node.getRight() != null) printFromNode(node.getRight(), tty, indentDepth + 2);
+  }
+}