View Javadoc
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  
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 }