svn commit: r907171 - in /incubator/cassandra/trunk: src/java/org/apache/cassandra/dht/Range.java test/unit/org/apache/cassandra/dht/RangeTest.java

[jb...@apache.org]

Author: jbellis
Date: Sat Feb  6 04:14:44 2010
New Revision: 907171

URL: http://svn.apache.org/viewvc?rev=907171&view=rev
Log:
add Range.intersectsWith.  patch by jbellis; reviewed by Stu Hood for CASSANDRA-763

Modified:
    incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/Range.java
    incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/RangeTest.java

Modified: incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/Range.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/Range.java?rev=907171&r1=907170&r2=907171&view=diff
==============================================================================
--- incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/Range.java (original)
+++ incubator/cassandra/trunk/src/java/org/apache/cassandra/dht/Range.java Sat Feb  6 04:14:44 2010
@@ -22,6 +22,12 @@
 import java.io.DataOutputStream;
 import java.io.IOException;
 import java.io.Serializable;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
+import org.apache.commons.lang.ObjectUtils;
 
 import org.apache.cassandra.io.ICompactSerializer;
 
@@ -109,31 +115,54 @@
     }
 
     /**
-     * @param range range to check for intersection
+     * @param that range to check for intersection
      * @return true if the given range intersects with this range.
      */
     public boolean intersects(Range that)
     {
+        return intersectionWith(that).size() > 0;
+    }
+
+    public List<Range> intersectionWith(Range that)
+    {
         boolean thiswraps = isWrapAround(left, right);
         boolean thatwraps = isWrapAround(that.left, that.right);
         if (thiswraps && thatwraps)
-            // both (must contain the minimum token)
-            return true;
-        else if (!thiswraps && !thatwraps)
-            // neither
-            return left.compareTo(that.right) < 0 &&
-                that.left.compareTo(right) < 0;
-        else
-            // either
-            return left.compareTo(that.right) < 0 ||
-                that.left.compareTo(right) < 0;
+        {
+            // there is always an intersection when both wrap
+            return Arrays.asList(new Range((Token)ObjectUtils.max(this.left, that.left),
+                                           (Token)ObjectUtils.min(this.right, that.right)));
+        }
+        if (!thiswraps && !thatwraps)
+        {
+            if (!(left.compareTo(that.right) < 0 && that.left.compareTo(right) < 0))
+                return Collections.emptyList();
+            return Arrays.asList(new Range((Token)ObjectUtils.max(this.left, that.left),
+                                           (Token)ObjectUtils.min(this.right, that.right)));
+        }
+        if (thiswraps && !thatwraps)
+            return intersectionOneWrapping(this, that);
+        assert (!thiswraps && thatwraps);
+        return intersectionOneWrapping(that, this);
+    }
+
+    private static List<Range> intersectionOneWrapping(Range wrapping, Range other)
+    {
+        List<Range> intersection = new ArrayList<Range>(2);
+        if (wrapping.contains(other))
+        {
+            return Arrays.asList(other);
+        }
+        if (other.contains(wrapping.right) || other.left.equals(wrapping.left))
+            intersection.add(new Range(other.left, wrapping.right));
+        if (other.contains(wrapping.left) && wrapping.left.compareTo(other.right) < 0)
+            intersection.add(new Range(wrapping.left, other.right));
+        return Collections.unmodifiableList(intersection);
     }
 
     /**
      * Tells if the given range is a wrap around.
-     * @param range
-     * @return
-     */
+         */
     public static boolean isWrapAround(Token left, Token right)
     {
         return left.compareTo(right) >= 0;

Modified: incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/RangeTest.java
URL: http://svn.apache.org/viewvc/incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/RangeTest.java?rev=907171&r1=907170&r2=907171&view=diff
==============================================================================
--- incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/RangeTest.java (original)
+++ incubator/cassandra/trunk/test/unit/org/apache/cassandra/dht/RangeTest.java Sat Feb  6 04:14:44 2010
@@ -101,10 +101,14 @@
     @Test
     public void testIntersects()
     {
+        Range all = new Range(new BigIntegerToken("0"), new BigIntegerToken("0")); // technically, this is a wrapping range
         Range one = new Range(new BigIntegerToken("2"), new BigIntegerToken("10"));
         Range two = new Range(new BigIntegerToken("0"), new BigIntegerToken("8"));
         Range not = new Range(new BigIntegerToken("10"), new BigIntegerToken("12"));
 
+        assert all.intersects(one);
+        assert all.intersects(two);
+
         assert one.intersects(two);
         assert two.intersects(one);
 
@@ -119,9 +123,14 @@
     public void testIntersectsWrapping()
     {
         Range onewrap = new Range(new BigIntegerToken("10"), new BigIntegerToken("2"));
+        Range onecomplement = new Range(onewrap.right, onewrap.left);
+        Range oneadjoins = new Range(onewrap.left, new BigIntegerToken("12"));
         Range twowrap = new Range(new BigIntegerToken("5"), new BigIntegerToken("3"));
         Range not = new Range(new BigIntegerToken("2"), new BigIntegerToken("6"));
 
+        assert !onewrap.intersects(onecomplement);
+        assert onewrap.intersects(oneadjoins);
+
         assert onewrap.intersects(twowrap);
         assert twowrap.intersects(onewrap);