Author: jbellis Date: Wed Sep 7 18:31:32 2011 New Revision: 1166305 URL: http://svn.apache.org/viewvc?rev=1166305&view=rev Log: intervaltree cleanup patch by Paul Cannon; reviewed by Ben Coverston for CASSANDRA-3146
Modified: cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree/IntervalNode.java cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree/IntervalTree.java Modified: cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree/IntervalNode.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree/IntervalNode.java?rev=1166305&r1=1166304&r2=1166305&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree/IntervalNode.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree/IntervalNode.java Wed Sep 7 18:31:32 2011 @@ -7,12 +7,11 @@ import com.google.common.collect.Immutab public class IntervalNode { - Interval interval; Comparable v_pt; Comparable v_min; Comparable v_max; - List<Interval> v_left; - List<Interval> v_right; + List<Interval> intersects_left; + List<Interval> intersects_right; IntervalNode left = null; IntervalNode right = null; @@ -21,9 +20,10 @@ public class IntervalNode if (toBisect.size() > 0) { findMinMedianMax(toBisect); - v_left = interval.minOrdering.sortedCopy(getIntersectingIntervals(toBisect)); - v_right = interval.maxOrdering.reverse().sortedCopy(getIntersectingIntervals(toBisect)); - //if i.min < v_pt then it goes to the left subtree + List<Interval> intersects = getIntersectingIntervals(toBisect); + intersects_left = Interval.minOrdering.sortedCopy(intersects); + intersects_right = Interval.maxOrdering.reverse().sortedCopy(intersects); + //if i.max < v_pt then it goes to the left subtree List<Interval> leftSegment = getLeftIntervals(toBisect); List<Interval> rightSegment = getRightIntervals(toBisect); if (leftSegment.size() > 0) @@ -84,5 +84,4 @@ public class IntervalNode v_max = allEndpoints.get(allEndpoints.size() - 1); } } - } Modified: cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree/IntervalTree.java URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree/IntervalTree.java?rev=1166305&r1=1166304&r2=1166305&view=diff ============================================================================== --- cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree/IntervalTree.java (original) +++ cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree/IntervalTree.java Wed Sep 7 18:31:32 2011 @@ -1,6 +1,5 @@ package org.apache.cassandra.utils.IntervalTree; -import java.util.Collections; import java.util.LinkedList; import java.util.List; @@ -28,7 +27,7 @@ public class IntervalTree<T> return head.v_min; } - public List<T> search(Interval searchInterval) + public List<T> search(Interval<T> searchInterval) { List<T> retlist = new LinkedList<T>(); searchInternal(head, searchInterval, retlist); @@ -41,14 +40,12 @@ public class IntervalTree<T> return; if (null == node || node.v_pt == null) return; - if (null == node) - return; //if searchInterval.contains(node.v_pt) //then add every interval contained in this node to the result set then search left and right for further //overlapping intervals if (searchInterval.contains(node.v_pt)) { - for (Interval<T> interval : node.v_left) + for (Interval<T> interval : node.intersects_left) { retList.add(interval.Data); } @@ -59,12 +56,12 @@ public class IntervalTree<T> } //if v.pt < searchInterval.left - //add intervals in v with v[i].right >= searchitnerval.left + //add intervals in v with v[i].right >= searchInterval.left //L contains no overlaps //R May if (node.v_pt.compareTo(searchInterval.min) < 0) { - for (Interval<T> interval : node.v_right) + for (Interval<T> interval : node.intersects_right) { if (interval.max.compareTo(searchInterval.min) >= 0) { @@ -77,12 +74,12 @@ public class IntervalTree<T> } //if v.pt > searchInterval.right - //add intervals in v with [i].left <= searchitnerval.right + //add intervals in v with [i].left <= searchInterval.right //R contains no overlaps //L May if (node.v_pt.compareTo(searchInterval.max) > 0) { - for (Interval<T> interval : node.v_left) + for (Interval<T> interval : node.intersects_left) { if (interval.min.compareTo(searchInterval.max) <= 0) {