svn commit: r1136008 - in /cassandra/trunk: CHANGES.txt src/java/org/apache/cassandra/dht/AbstractBounds.java test/unit/org/apache/cassandra/dht/AbstractBoundsTest.java

[sl...@apache.org]

Author: slebresne
Date: Wed Jun 15 12:01:21 2011
New Revision: 1136008

URL: http://svn.apache.org/viewvc?rev=1136008&view=rev
Log:
Make AbstractBounds.normalize de-overlapp overlapping ranges
patch by slebresne; reviewed by stuhood for CASSANDRA-2641

Added:
    cassandra/trunk/test/unit/org/apache/cassandra/dht/AbstractBoundsTest.java
Modified:
    cassandra/trunk/CHANGES.txt
    cassandra/trunk/src/java/org/apache/cassandra/dht/AbstractBounds.java

Modified: cassandra/trunk/CHANGES.txt
URL: http://svn.apache.org/viewvc/cassandra/trunk/CHANGES.txt?rev=1136008&r1=1136007&r2=1136008&view=diff
==============================================================================
--- cassandra/trunk/CHANGES.txt (original)
+++ cassandra/trunk/CHANGES.txt Wed Jun 15 12:01:21 2011
@@ -2,6 +2,7 @@
  * removed binarymemtable (CASSANDRA-2692)
  * add commitlog_total_space_in_mb to prevent fragmented logs (CASSANDRA-2427)
  * removed commitlog_rotation_threshold_in_mb configuration (CASSANDRA-2771)
+ * make AbstractBounds.normalize de-overlapp overlapping ranges (CASSANDRA-2641)
 
 
 0.8.1

Modified: cassandra/trunk/src/java/org/apache/cassandra/dht/AbstractBounds.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/src/java/org/apache/cassandra/dht/AbstractBounds.java?rev=1136008&r1=1136007&r2=1136008&view=diff
==============================================================================
--- cassandra/trunk/src/java/org/apache/cassandra/dht/AbstractBounds.java (original)
+++ cassandra/trunk/src/java/org/apache/cassandra/dht/AbstractBounds.java Wed Jun 15 12:01:21 2011
@@ -89,8 +89,8 @@ public abstract class AbstractBounds imp
     public abstract List<AbstractBounds> unwrap();
 
     /**
-     * @return A copy of the given list of non-intersecting bounds with all bounds unwrapped, sorted by bound.left.
-     * This method does not allow overlapping ranges as input.
+     * @return A copy of the given list of with all bounds unwrapped, sorted by bound.left and with overlapping bounds merged.
+     * This method does not allow allow to mix Range and Bound in the input list.
      */
     public static List<AbstractBounds> normalize(Collection<? extends AbstractBounds> bounds)
     {
@@ -107,6 +107,61 @@ public abstract class AbstractBounds imp
                 return b1.left.compareTo(b2.left);
             }
         });
+
+        // deoverlap
+        return deoverlap(output);
+    }
+
+    /**
+     * Given a list of unwrapped bounds sorted by left token, return a list a equivalent
+     * list of bounds but with no overlapping bounds.
+     */
+    private static List<AbstractBounds> deoverlap(List<AbstractBounds> bounds)
+    {
+        if (bounds.isEmpty())
+            return bounds;
+
+        List<AbstractBounds> output = new ArrayList<AbstractBounds>();
+
+        Iterator<AbstractBounds> iter = bounds.iterator();
+        AbstractBounds current = iter.next();
+        boolean isRange = current instanceof Range;
+
+        Token min = current.partitioner.getMinimumToken();
+        while (iter.hasNext())
+        {
+            if (current.right.equals(min))
+            {
+                // If one of the bound is the full range, we return only that
+                if (current.left.equals(min))
+                    return Collections.<AbstractBounds>singletonList(current);
+
+                output.add(current.createFrom(min));
+                return output;
+            }
+
+            AbstractBounds next = iter.next();
+            assert isRange ? next instanceof Range : next instanceof Bounds;
+
+            // For Ranges, if next left is equal to current right, we do not intersect per se, but replacing (A, B] and (B, C] by (A, C] is
+            // legit, and since this actually avoid special casing and will result in more "optimal" ranges, we do this transformation
+            if (next.left.compareTo(current.right) <= 0)
+            {
+                // We do overlap
+                // (we've handler current.right.equals(min) already)
+                Token newRight = next.right.equals(min) || current.right.compareTo(next.right) < 0 ? next.right : current.right;
+                current = current.createFrom(newRight);
+                if (current == null)
+                    // current is the full ring, can only happen for Range
+                    return Collections.<AbstractBounds>singletonList(new Range(min, min));
+            }
+            else
+            {
+                output.add(current);
+                current = next;
+            }
+        }
+        output.add(current);
         return output;
     }
 

Added: cassandra/trunk/test/unit/org/apache/cassandra/dht/AbstractBoundsTest.java
URL: http://svn.apache.org/viewvc/cassandra/trunk/test/unit/org/apache/cassandra/dht/AbstractBoundsTest.java?rev=1136008&view=auto
==============================================================================
--- cassandra/trunk/test/unit/org/apache/cassandra/dht/AbstractBoundsTest.java (added)
+++ cassandra/trunk/test/unit/org/apache/cassandra/dht/AbstractBoundsTest.java Wed Jun 15 12:01:21 2011
@@ -0,0 +1,135 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.cassandra.dht;
+
+import java.util.List;
+import static java.util.Arrays.asList;
+
+import org.junit.Test;
+
+import static org.apache.cassandra.Util.range;
+import static org.apache.cassandra.Util.bounds;
+
+public class AbstractBoundsTest
+{
+    private void assertNormalize(List<? extends AbstractBounds> input, List<? extends AbstractBounds> expected)
+    {
+        List<AbstractBounds> result = AbstractBounds.normalize(input);
+        assert result.equals(expected) : "Expecting " + expected + " but got " + result;
+    }
+
+    @Test
+    public void testNormalizeNoop()
+    {
+        List<? extends AbstractBounds> l;
+
+        l = asList(range("1", "3"), range("4", "5"));
+        assert AbstractBounds.normalize(l).equals(l);
+
+        l = asList(bounds("1", "3"), bounds("4", "5"));
+        assertNormalize(l, l);
+    }
+
+    @Test
+    public void testNormalizeSimpleOverlap()
+    {
+        List<? extends AbstractBounds> input, expected;
+
+        input = asList(range("1", "4"), range("3", "5"));
+        expected = asList(range("1", "5"));
+        assertNormalize(input, expected);
+
+        input = asList(range("1", "4"), range("1", "4"));
+        expected = asList(range("1", "4"));
+        assertNormalize(input, expected);
+
+        input = asList(bounds("1", "4"), bounds("3", "5"));
+        expected = asList(bounds("1", "5"));
+        assertNormalize(input, expected);
+
+        input = asList(bounds("1", "4"), bounds("1", "4"));
+        expected = asList(bounds("1", "4"));
+        assertNormalize(input, expected);
+
+        input = asList(bounds("1", "1"), bounds("1", "1"));
+        expected = asList(bounds("1", "1"));
+        assertNormalize(input, expected);
+    }
+
+    @Test
+    public void testNormalizeSort()
+    {
+        List<? extends AbstractBounds> input, expected;
+
+        input = asList(range("4", "5"), range("1", "3"));
+        expected = asList(range("1", "3"), range("4", "5"));
+        assertNormalize(input, expected);
+
+        input = asList(bounds("4", "5"), bounds("1", "3"));
+        expected = asList(bounds("1", "3"), bounds("4", "5"));
+        assertNormalize(input, expected);
+    }
+
+    @Test
+    public void testNormalizeUnwrap()
+    {
+        List<? extends AbstractBounds> input, expected;
+
+        input = asList(range("9", "2"));
+        expected = asList(range("", "2"), range("9", ""));
+        assertNormalize(input, expected);
+
+        // Bounds cannot wrap
+    }
+
+    @Test
+    public void testNormalizeComplex()
+    {
+        List<? extends AbstractBounds> input, expected;
+
+        input = asList(range("8", "2"), range("7", "9"), range("4", "5"));
+        expected = asList(range("", "2"), range("4", "5"), range("7", ""));
+        assertNormalize(input, expected);
+
+        input = asList(range("5", "9"), range("2", "5"));
+        expected = asList(range("2", "9"));
+        assertNormalize(input, expected);
+
+        input = asList(range ("", "1"), range("9", "2"), range("4", "5"), range("", ""));
+        expected = asList(range("", ""));
+        assertNormalize(input, expected);
+
+        input = asList(range ("", "1"), range("1", "4"), range("4", "5"), range("5", ""));
+        expected = asList(range("", ""));
+        assertNormalize(input, expected);
+
+        // bounds
+        input = asList(bounds("5", "9"), bounds("2", "5"));
+        expected = asList(bounds("2", "9"));
+        assertNormalize(input, expected);
+
+        input = asList(bounds ("", "1"), bounds("", "9"), bounds("4", "5"), bounds("", ""));
+        expected = asList(bounds("", ""));
+        assertNormalize(input, expected);
+
+        input = asList(bounds ("", "1"), bounds("1", "4"), bounds("4", "5"), bounds("5", ""));
+        expected = asList(bounds("", ""));
+        assertNormalize(input, expected);
+    }
+}