You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by jb...@apache.org on 2011/09/07 20:31:32 UTC
svn commit: r1166305 - in
/cassandra/trunk/src/java/org/apache/cassandra/utils/IntervalTree:
IntervalNode.java IntervalTree.java
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)
{