1 /* 2 * Copyright (c) 2000, 2020, 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<Object> 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. */ IntervalTree(Comparator<Object> endpointComparator)40 public IntervalTree(Comparator<Object> endpointComparator) { 41 super(new IntervalComparator(endpointComparator)); 42 this.endpointComparator = endpointComparator; 43 } 44 insert(Interval interval, Object data)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. */ findAllNodesIntersecting(Interval interval)54 public List<IntervalNode> findAllNodesIntersecting(Interval interval) { 55 List<IntervalNode> retList = new ArrayList<>(); 56 searchForIntersectingNodesFrom((IntervalNode) getRoot(), interval, retList); 57 return retList; 58 } 59 print()60 public void print() { 61 printOn(System.out); 62 } 63 printOn(PrintStream tty)64 public void printOn(PrintStream tty) { 65 printFromNode(getRoot(), tty, 0); 66 } 67 68 //---------------------------------------------------------------------- 69 // Overridden internal functionality 70 getNodeValue(RBNode node)71 protected Object getNodeValue(RBNode node) { 72 return ((IntervalNode) node).getInterval(); 73 } 74 verify()75 protected void verify() { 76 super.verify(); 77 verifyFromNode(getRoot()); 78 } 79 80 //---------------------------------------------------------------------- 81 // Internals only below this point 82 // 83 verifyFromNode(RBNode node)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<Object> { 112 private Comparator<Object> endpointComparator; 113 IntervalComparator(Comparator<Object> endpointComparator)114 public IntervalComparator(Comparator<Object> endpointComparator) { 115 this.endpointComparator = endpointComparator; 116 } 117 compare(Object o1, Object o2)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 searchForIntersectingNodesFrom(IntervalNode node, Interval interval, List<IntervalNode> resultList)125 private void searchForIntersectingNodesFrom(IntervalNode node, 126 Interval interval, 127 List<IntervalNode> 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 */ printFromNode(RBNode node, PrintStream tty, int indentDepth)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