Java example source code file (IntervalTree.java)

This example Java source code file (IntervalTree.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

arraylist, debugging, interval, intervalcomparator, intervalnode, intervaltree, list, node\'s, object, printstream, rbtree, runtimeexception, util, verbose

The IntervalTree.java Java example source code

/*
 * Copyright (c) 2000, 2003, Oracle and/or its affiliates. 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.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);
  }
}