Return-Path: Delivered-To: apmail-incubator-cassandra-commits-archive@minotaur.apache.org Received: (qmail 26248 invoked from network); 23 Feb 2010 22:45:28 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (140.211.11.3) by minotaur.apache.org with SMTP; 23 Feb 2010 22:45:28 -0000 Received: (qmail 97507 invoked by uid 500); 23 Feb 2010 22:45:28 -0000 Delivered-To: apmail-incubator-cassandra-commits-archive@incubator.apache.org Received: (qmail 97473 invoked by uid 500); 23 Feb 2010 22:45:28 -0000 Mailing-List: contact cassandra-commits-help@incubator.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: cassandra-dev@incubator.apache.org Delivered-To: mailing list cassandra-commits@incubator.apache.org Received: (qmail 97463 invoked by uid 99); 23 Feb 2010 22:45:28 -0000 Received: from nike.apache.org (HELO nike.apache.org) (192.87.106.230) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 23 Feb 2010 22:45:28 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=10.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 23 Feb 2010 22:45:25 +0000 Received: by eris.apache.org (Postfix, from userid 65534) id AEDD92388901; Tue, 23 Feb 2010 22:45:03 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r915564 - in /incubator/cassandra/branches/cassandra-0.5: src/java/org/apache/cassandra/dht/ test/unit/org/apache/cassandra/dht/ Date: Tue, 23 Feb 2010 22:45:03 -0000 To: cassandra-commits@incubator.apache.org From: eevans@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20100223224503.AEDD92388901@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org Author: eevans Date: Tue Feb 23 22:45:03 2010 New Revision: 915564 URL: http://svn.apache.org/viewvc?rev=915564&view=rev Log: add missing licensing headers Modified: incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/dht/AbstractBounds.java incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/dht/Bounds.java incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/dht/BoundsTest.java incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/dht/RangeIntersectionTest.java Modified: incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/dht/AbstractBounds.java URL: http://svn.apache.org/viewvc/incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/dht/AbstractBounds.java?rev=915564&r1=915563&r2=915564&view=diff ============================================================================== --- incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/dht/AbstractBounds.java (original) +++ incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/dht/AbstractBounds.java Tue Feb 23 22:45:03 2010 @@ -1,71 +1,92 @@ -package org.apache.cassandra.dht; - -import java.io.DataInput; -import java.io.DataOutput; -import java.io.IOException; -import java.io.Serializable; -import java.util.List; -import java.util.Set; - -import org.apache.cassandra.io.ICompactSerializer2; - -public abstract class AbstractBounds implements Serializable -{ - private static AbstractBoundsSerializer serializer = new AbstractBoundsSerializer(); - - public static ICompactSerializer2 serializer() - { - return serializer; - } - - private enum Type - { - RANGE, - BOUNDS - } - - public final Token left; - public final Token right; - - protected transient final IPartitioner partitioner; - - public AbstractBounds(Token left, Token right, IPartitioner partitioner) - { - this.left = left; - this.right = right; - this.partitioner = partitioner; - } - - @Override - public int hashCode() - { - return toString().hashCode(); - } - - @Override - public abstract boolean equals(Object obj); - - public abstract boolean contains(Token start); - - public abstract Set restrictTo(Range range); - - public abstract List unwrap(); - - private static class AbstractBoundsSerializer implements ICompactSerializer2 - { - public void serialize(AbstractBounds range, DataOutput out) throws IOException - { - out.writeInt(range instanceof Range ? Type.RANGE.ordinal() : Type.BOUNDS.ordinal()); - Token.serializer().serialize(range.left, out); - Token.serializer().serialize(range.right, out); - } - - public AbstractBounds deserialize(DataInput in) throws IOException - { - if (in.readInt() == Type.RANGE.ordinal()) - return new Range(Token.serializer().deserialize(in), Token.serializer().deserialize(in)); - return new Bounds(Token.serializer().deserialize(in), Token.serializer().deserialize(in)); - } - } -} - +package org.apache.cassandra.dht; +/* + * + * 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. + * + */ + + +import java.io.DataInput; +import java.io.DataOutput; +import java.io.IOException; +import java.io.Serializable; +import java.util.List; +import java.util.Set; + +import org.apache.cassandra.io.ICompactSerializer2; + +public abstract class AbstractBounds implements Serializable +{ + private static AbstractBoundsSerializer serializer = new AbstractBoundsSerializer(); + + public static ICompactSerializer2 serializer() + { + return serializer; + } + + private enum Type + { + RANGE, + BOUNDS + } + + public final Token left; + public final Token right; + + protected transient final IPartitioner partitioner; + + public AbstractBounds(Token left, Token right, IPartitioner partitioner) + { + this.left = left; + this.right = right; + this.partitioner = partitioner; + } + + @Override + public int hashCode() + { + return toString().hashCode(); + } + + @Override + public abstract boolean equals(Object obj); + + public abstract boolean contains(Token start); + + public abstract Set restrictTo(Range range); + + public abstract List unwrap(); + + private static class AbstractBoundsSerializer implements ICompactSerializer2 + { + public void serialize(AbstractBounds range, DataOutput out) throws IOException + { + out.writeInt(range instanceof Range ? Type.RANGE.ordinal() : Type.BOUNDS.ordinal()); + Token.serializer().serialize(range.left, out); + Token.serializer().serialize(range.right, out); + } + + public AbstractBounds deserialize(DataInput in) throws IOException + { + if (in.readInt() == Type.RANGE.ordinal()) + return new Range(Token.serializer().deserialize(in), Token.serializer().deserialize(in)); + return new Bounds(Token.serializer().deserialize(in), Token.serializer().deserialize(in)); + } + } +} + Modified: incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/dht/Bounds.java URL: http://svn.apache.org/viewvc/incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/dht/Bounds.java?rev=915564&r1=915563&r2=915564&view=diff ============================================================================== --- incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/dht/Bounds.java (original) +++ incubator/cassandra/branches/cassandra-0.5/src/java/org/apache/cassandra/dht/Bounds.java Tue Feb 23 22:45:03 2010 @@ -1,73 +1,94 @@ -package org.apache.cassandra.dht; - -import java.util.*; - -import org.apache.cassandra.service.StorageService; - -public class Bounds extends AbstractBounds -{ - public Bounds(Token left, Token right) - { - this(left, right, StorageService.getPartitioner()); - } - - Bounds(Token left, Token right, IPartitioner partitioner) - { - super(left, right, partitioner); - // unlike a Range, a Bounds may not wrap - assert left.compareTo(right) <= 0 || right.equals(partitioner.getMinimumToken()) : "[" + left + "," + right + "]"; - } - - @Override - public boolean contains(Token token) - { - return Range.contains(left, right, token) || left.equals(token); - } - - public Set restrictTo(Range range) - { - Token min = partitioner.getMinimumToken(); - - // special case Bounds where left=right (single Token) - if (this.left.equals(this.right) && !this.right.equals(min)) - return range.contains(this.left) - ? Collections.unmodifiableSet(new HashSet(Arrays.asList(this))) - : Collections.emptySet(); - - // get the intersection of a Range w/ same left & right - Set ranges = range.intersectionWith(new Range(this.left, this.right)); - // if range doesn't contain left token anyway, that's the correct answer - if (!range.contains(this.left)) - return (Set) ranges; - // otherwise, add back in the left token - Set S = new HashSet(ranges.size()); - for (Range restricted : ranges) - { - if (restricted.left.equals(this.left)) - S.add(new Bounds(restricted.left, restricted.right)); - else - S.add(restricted); - } - return Collections.unmodifiableSet(S); - } - - public List unwrap() - { - // Bounds objects never wrap - return (List)Arrays.asList(this); - } - - @Override - public boolean equals(Object o) - { - if (!(o instanceof Bounds)) - return false; - Bounds rhs = (Bounds)o; - return left.equals(rhs.left) && right.equals(rhs.right); - } - - public String toString() - { - return "[" + left + "," + right + "]"; - } -} +package org.apache.cassandra.dht; +/* + * + * 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. + * + */ + + +import java.util.*; + +import org.apache.cassandra.service.StorageService; + +public class Bounds extends AbstractBounds +{ + public Bounds(Token left, Token right) + { + this(left, right, StorageService.getPartitioner()); + } + + Bounds(Token left, Token right, IPartitioner partitioner) + { + super(left, right, partitioner); + // unlike a Range, a Bounds may not wrap + assert left.compareTo(right) <= 0 || right.equals(partitioner.getMinimumToken()) : "[" + left + "," + right + "]"; + } + + @Override + public boolean contains(Token token) + { + return Range.contains(left, right, token) || left.equals(token); + } + + public Set restrictTo(Range range) + { + Token min = partitioner.getMinimumToken(); + + // special case Bounds where left=right (single Token) + if (this.left.equals(this.right) && !this.right.equals(min)) + return range.contains(this.left) + ? Collections.unmodifiableSet(new HashSet(Arrays.asList(this))) + : Collections.emptySet(); + + // get the intersection of a Range w/ same left & right + Set ranges = range.intersectionWith(new Range(this.left, this.right)); + // if range doesn't contain left token anyway, that's the correct answer + if (!range.contains(this.left)) + return (Set) ranges; + // otherwise, add back in the left token + Set S = new HashSet(ranges.size()); + for (Range restricted : ranges) + { + if (restricted.left.equals(this.left)) + S.add(new Bounds(restricted.left, restricted.right)); + else + S.add(restricted); + } + return Collections.unmodifiableSet(S); + } + + public List unwrap() + { + // Bounds objects never wrap + return (List)Arrays.asList(this); + } + + @Override + public boolean equals(Object o) + { + if (!(o instanceof Bounds)) + return false; + Bounds rhs = (Bounds)o; + return left.equals(rhs.left) && right.equals(rhs.right); + } + + public String toString() + { + return "[" + left + "," + right + "]"; + } +} Modified: incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/dht/BoundsTest.java URL: http://svn.apache.org/viewvc/incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/dht/BoundsTest.java?rev=915564&r1=915563&r2=915564&view=diff ============================================================================== --- incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/dht/BoundsTest.java (original) +++ incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/dht/BoundsTest.java Tue Feb 23 22:45:03 2010 @@ -1,73 +1,94 @@ -package org.apache.cassandra.dht; - -import java.util.*; - -import junit.framework.TestCase; -import org.apache.cassandra.utils.FBUtilities; - -public class BoundsTest extends TestCase -{ - public void testRestrictTo() throws Exception - { - IPartitioner p = new OrderPreservingPartitioner(); - Token min = p.getMinimumToken(); - Range wraps = new Range(new StringToken("m"), new StringToken("e")); - Range normal = new Range(wraps.right, wraps.left); - Bounds all = new Bounds(min, min, p); - Bounds almostAll = new Bounds(new StringToken("a"), min, p); - - Set S; - Set S2; - - S = all.restrictTo(wraps); - assert S.equals(new HashSet(Arrays.asList(wraps))); - - S = almostAll.restrictTo(wraps); - S2 = new HashSet(Arrays.asList(new Bounds(new StringToken("a"), new StringToken("e"), p), - new Range(new StringToken("m"), min))); - assert S.equals(S2); - - S = all.restrictTo(normal); - assert S.equals(new HashSet(Arrays.asList(normal))); - } - - public void testNoIntersectionWrapped() - { - IPartitioner p = new OrderPreservingPartitioner(); - Range node = new Range(new StringToken("z"), new StringToken("a")); - Bounds bounds; - - bounds = new Bounds(new StringToken("m"), new StringToken("n"), p); - assert bounds.restrictTo(node).equals(Collections.emptySet()); - - bounds = new Bounds(new StringToken("b"), node.left, p); - assert bounds.restrictTo(node).equals(Collections.emptySet()); - } - - public void testSmallBoundsFullRange() - { - IPartitioner p = new OrderPreservingPartitioner(); - Range node; - Bounds bounds = new Bounds(new StringToken("b"), new StringToken("c"), p); - - node = new Range(new StringToken("d"), new StringToken("d")); - assert bounds.restrictTo(node).equals(new HashSet(Arrays.asList(bounds))); - } - - public void testNoIntersectionUnwrapped() - { - IPartitioner p = new OrderPreservingPartitioner(); - Token min = p.getMinimumToken(); - Range node = new Range(new StringToken("m"), new StringToken("n")); - Bounds bounds; - - bounds = new Bounds(new StringToken("z"), min, p); - assert bounds.restrictTo(node).equals(Collections.emptySet()); - - bounds = new Bounds(new StringToken("a"), node.left, p); - assert bounds.restrictTo(node).equals(Collections.emptySet()); - - bounds = new Bounds(min, new StringToken("b"), p); - assert bounds.restrictTo(node).equals(Collections.emptySet()); - } -} +package org.apache.cassandra.dht; +/* + * + * 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. + * + */ + + +import java.util.*; + +import junit.framework.TestCase; +import org.apache.cassandra.utils.FBUtilities; + +public class BoundsTest extends TestCase +{ + public void testRestrictTo() throws Exception + { + IPartitioner p = new OrderPreservingPartitioner(); + Token min = p.getMinimumToken(); + Range wraps = new Range(new StringToken("m"), new StringToken("e")); + Range normal = new Range(wraps.right, wraps.left); + Bounds all = new Bounds(min, min, p); + Bounds almostAll = new Bounds(new StringToken("a"), min, p); + + Set S; + Set S2; + + S = all.restrictTo(wraps); + assert S.equals(new HashSet(Arrays.asList(wraps))); + + S = almostAll.restrictTo(wraps); + S2 = new HashSet(Arrays.asList(new Bounds(new StringToken("a"), new StringToken("e"), p), + new Range(new StringToken("m"), min))); + assert S.equals(S2); + + S = all.restrictTo(normal); + assert S.equals(new HashSet(Arrays.asList(normal))); + } + + public void testNoIntersectionWrapped() + { + IPartitioner p = new OrderPreservingPartitioner(); + Range node = new Range(new StringToken("z"), new StringToken("a")); + Bounds bounds; + + bounds = new Bounds(new StringToken("m"), new StringToken("n"), p); + assert bounds.restrictTo(node).equals(Collections.emptySet()); + + bounds = new Bounds(new StringToken("b"), node.left, p); + assert bounds.restrictTo(node).equals(Collections.emptySet()); + } + + public void testSmallBoundsFullRange() + { + IPartitioner p = new OrderPreservingPartitioner(); + Range node; + Bounds bounds = new Bounds(new StringToken("b"), new StringToken("c"), p); + + node = new Range(new StringToken("d"), new StringToken("d")); + assert bounds.restrictTo(node).equals(new HashSet(Arrays.asList(bounds))); + } + + public void testNoIntersectionUnwrapped() + { + IPartitioner p = new OrderPreservingPartitioner(); + Token min = p.getMinimumToken(); + Range node = new Range(new StringToken("m"), new StringToken("n")); + Bounds bounds; + + bounds = new Bounds(new StringToken("z"), min, p); + assert bounds.restrictTo(node).equals(Collections.emptySet()); + + bounds = new Bounds(new StringToken("a"), node.left, p); + assert bounds.restrictTo(node).equals(Collections.emptySet()); + + bounds = new Bounds(min, new StringToken("b"), p); + assert bounds.restrictTo(node).equals(Collections.emptySet()); + } +} Modified: incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/dht/RangeIntersectionTest.java URL: http://svn.apache.org/viewvc/incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/dht/RangeIntersectionTest.java?rev=915564&r1=915563&r2=915564&view=diff ============================================================================== --- incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/dht/RangeIntersectionTest.java (original) +++ incubator/cassandra/branches/cassandra-0.5/test/unit/org/apache/cassandra/dht/RangeIntersectionTest.java Tue Feb 23 22:45:03 2010 @@ -1,131 +1,152 @@ -package org.apache.cassandra.dht; - -import java.util.Arrays; -import java.util.List; -import java.util.Set; - -import org.apache.commons.lang.StringUtils; -import org.junit.Test; - -public class RangeIntersectionTest -{ - static void assertIntersection(Range one, Range two, Range ... ranges) - { - Set correct = Range.rangeSet(ranges); - Set result1 = one.intersectionWith(two); - assert result1.equals(correct) : String.format("%s != %s", - StringUtils.join(result1, ","), - StringUtils.join(correct, ",")); - Set result2 = two.intersectionWith(one); - assert result2.equals(correct) : String.format("%s != %s", - StringUtils.join(result2, ","), - StringUtils.join(correct, ",")); - } - - private void assertNoIntersection(Range wraps1, Range nowrap3) - { - assertIntersection(wraps1, nowrap3); - } - - @Test - public void testIntersectionWithAll() - { - Range all0 = new Range(new BigIntegerToken("0"), new BigIntegerToken("0")); - Range all10 = new Range(new BigIntegerToken("10"), new BigIntegerToken("10")); - Range all100 = new Range(new BigIntegerToken("100"), new BigIntegerToken("100")); - Range all1000 = new Range(new BigIntegerToken("1000"), new BigIntegerToken("1000")); - Range wraps = new Range(new BigIntegerToken("100"), new BigIntegerToken("10")); - - assertIntersection(all0, wraps, wraps); - assertIntersection(all10, wraps, wraps); - assertIntersection(all100, wraps, wraps); - assertIntersection(all1000, wraps, wraps); - } - - @Test - public void testIntersectionContains() - { - Range wraps1 = new Range(new BigIntegerToken("100"), new BigIntegerToken("10")); - Range wraps2 = new Range(new BigIntegerToken("90"), new BigIntegerToken("20")); - Range wraps3 = new Range(new BigIntegerToken("90"), new BigIntegerToken("0")); - Range nowrap1 = new Range(new BigIntegerToken("100"), new BigIntegerToken("110")); - Range nowrap2 = new Range(new BigIntegerToken("0"), new BigIntegerToken("10")); - Range nowrap3 = new Range(new BigIntegerToken("0"), new BigIntegerToken("9")); - - assertIntersection(wraps1, wraps2, wraps1); - assertIntersection(wraps3, wraps2, wraps3); - - assertIntersection(wraps1, nowrap1, nowrap1); - assertIntersection(wraps1, nowrap2, nowrap2); - assertIntersection(nowrap2, nowrap3, nowrap3); - - assertIntersection(wraps1, wraps1, wraps1); - assertIntersection(nowrap1, nowrap1, nowrap1); - assertIntersection(nowrap2, nowrap2, nowrap2); - assertIntersection(wraps3, wraps3, wraps3); - } - - @Test - public void testNoIntersection() - { - Range wraps1 = new Range(new BigIntegerToken("100"), new BigIntegerToken("10")); - Range wraps2 = new Range(new BigIntegerToken("100"), new BigIntegerToken("0")); - Range nowrap1 = new Range(new BigIntegerToken("0"), new BigIntegerToken("100")); - Range nowrap2 = new Range(new BigIntegerToken("100"), new BigIntegerToken("200")); - Range nowrap3 = new Range(new BigIntegerToken("10"), new BigIntegerToken("100")); - - assertNoIntersection(wraps1, nowrap3); - assertNoIntersection(wraps2, nowrap1); - assertNoIntersection(nowrap1, nowrap2); - } - - @Test - public void testIntersectionOneWraps() - { - Range wraps1 = new Range(new BigIntegerToken("100"), new BigIntegerToken("10")); - Range wraps2 = new Range(new BigIntegerToken("100"), new BigIntegerToken("0")); - Range nowrap1 = new Range(new BigIntegerToken("0"), new BigIntegerToken("200")); - Range nowrap2 = new Range(new BigIntegerToken("0"), new BigIntegerToken("100")); - - assertIntersection(wraps1, - nowrap1, - new Range(new BigIntegerToken("0"), new BigIntegerToken("10")), - new Range(new BigIntegerToken("100"), new BigIntegerToken("200"))); - assertIntersection(wraps2, - nowrap1, - new Range(new BigIntegerToken("100"), new BigIntegerToken("200"))); - assertIntersection(wraps1, - nowrap2, - new Range(new BigIntegerToken("0"), new BigIntegerToken("10"))); - } - - @Test - public void testIntersectionTwoWraps() - { - Range wraps1 = new Range(new BigIntegerToken("100"), new BigIntegerToken("20")); - Range wraps2 = new Range(new BigIntegerToken("120"), new BigIntegerToken("90")); - Range wraps3 = new Range(new BigIntegerToken("120"), new BigIntegerToken("110")); - Range wraps4 = new Range(new BigIntegerToken("10"), new BigIntegerToken("0")); - Range wraps5 = new Range(new BigIntegerToken("10"), new BigIntegerToken("1")); - Range wraps6 = new Range(new BigIntegerToken("30"), new BigIntegerToken("10")); - - assertIntersection(wraps1, - wraps2, - new Range(new BigIntegerToken("120"), new BigIntegerToken("20"))); - assertIntersection(wraps1, - wraps3, - new Range(new BigIntegerToken("120"), new BigIntegerToken("20")), - new Range(new BigIntegerToken("100"), new BigIntegerToken("110"))); - assertIntersection(wraps1, - wraps4, - new Range(new BigIntegerToken("10"), new BigIntegerToken("20")), - new Range(new BigIntegerToken("100"), new BigIntegerToken("0"))); - assertIntersection(wraps1, - wraps5, - new Range(new BigIntegerToken("10"), new BigIntegerToken("20")), - new Range(new BigIntegerToken("100"), new BigIntegerToken("1"))); - assertIntersection(wraps1, - wraps6, - new Range(new BigIntegerToken("100"), new BigIntegerToken("10"))); - } -} +package org.apache.cassandra.dht; +/* + * + * 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. + * + */ + + +import java.util.Arrays; +import java.util.List; +import java.util.Set; + +import org.apache.commons.lang.StringUtils; +import org.junit.Test; + +public class RangeIntersectionTest +{ + static void assertIntersection(Range one, Range two, Range ... ranges) + { + Set correct = Range.rangeSet(ranges); + Set result1 = one.intersectionWith(two); + assert result1.equals(correct) : String.format("%s != %s", + StringUtils.join(result1, ","), + StringUtils.join(correct, ",")); + Set result2 = two.intersectionWith(one); + assert result2.equals(correct) : String.format("%s != %s", + StringUtils.join(result2, ","), + StringUtils.join(correct, ",")); + } + + private void assertNoIntersection(Range wraps1, Range nowrap3) + { + assertIntersection(wraps1, nowrap3); + } + + @Test + public void testIntersectionWithAll() + { + Range all0 = new Range(new BigIntegerToken("0"), new BigIntegerToken("0")); + Range all10 = new Range(new BigIntegerToken("10"), new BigIntegerToken("10")); + Range all100 = new Range(new BigIntegerToken("100"), new BigIntegerToken("100")); + Range all1000 = new Range(new BigIntegerToken("1000"), new BigIntegerToken("1000")); + Range wraps = new Range(new BigIntegerToken("100"), new BigIntegerToken("10")); + + assertIntersection(all0, wraps, wraps); + assertIntersection(all10, wraps, wraps); + assertIntersection(all100, wraps, wraps); + assertIntersection(all1000, wraps, wraps); + } + + @Test + public void testIntersectionContains() + { + Range wraps1 = new Range(new BigIntegerToken("100"), new BigIntegerToken("10")); + Range wraps2 = new Range(new BigIntegerToken("90"), new BigIntegerToken("20")); + Range wraps3 = new Range(new BigIntegerToken("90"), new BigIntegerToken("0")); + Range nowrap1 = new Range(new BigIntegerToken("100"), new BigIntegerToken("110")); + Range nowrap2 = new Range(new BigIntegerToken("0"), new BigIntegerToken("10")); + Range nowrap3 = new Range(new BigIntegerToken("0"), new BigIntegerToken("9")); + + assertIntersection(wraps1, wraps2, wraps1); + assertIntersection(wraps3, wraps2, wraps3); + + assertIntersection(wraps1, nowrap1, nowrap1); + assertIntersection(wraps1, nowrap2, nowrap2); + assertIntersection(nowrap2, nowrap3, nowrap3); + + assertIntersection(wraps1, wraps1, wraps1); + assertIntersection(nowrap1, nowrap1, nowrap1); + assertIntersection(nowrap2, nowrap2, nowrap2); + assertIntersection(wraps3, wraps3, wraps3); + } + + @Test + public void testNoIntersection() + { + Range wraps1 = new Range(new BigIntegerToken("100"), new BigIntegerToken("10")); + Range wraps2 = new Range(new BigIntegerToken("100"), new BigIntegerToken("0")); + Range nowrap1 = new Range(new BigIntegerToken("0"), new BigIntegerToken("100")); + Range nowrap2 = new Range(new BigIntegerToken("100"), new BigIntegerToken("200")); + Range nowrap3 = new Range(new BigIntegerToken("10"), new BigIntegerToken("100")); + + assertNoIntersection(wraps1, nowrap3); + assertNoIntersection(wraps2, nowrap1); + assertNoIntersection(nowrap1, nowrap2); + } + + @Test + public void testIntersectionOneWraps() + { + Range wraps1 = new Range(new BigIntegerToken("100"), new BigIntegerToken("10")); + Range wraps2 = new Range(new BigIntegerToken("100"), new BigIntegerToken("0")); + Range nowrap1 = new Range(new BigIntegerToken("0"), new BigIntegerToken("200")); + Range nowrap2 = new Range(new BigIntegerToken("0"), new BigIntegerToken("100")); + + assertIntersection(wraps1, + nowrap1, + new Range(new BigIntegerToken("0"), new BigIntegerToken("10")), + new Range(new BigIntegerToken("100"), new BigIntegerToken("200"))); + assertIntersection(wraps2, + nowrap1, + new Range(new BigIntegerToken("100"), new BigIntegerToken("200"))); + assertIntersection(wraps1, + nowrap2, + new Range(new BigIntegerToken("0"), new BigIntegerToken("10"))); + } + + @Test + public void testIntersectionTwoWraps() + { + Range wraps1 = new Range(new BigIntegerToken("100"), new BigIntegerToken("20")); + Range wraps2 = new Range(new BigIntegerToken("120"), new BigIntegerToken("90")); + Range wraps3 = new Range(new BigIntegerToken("120"), new BigIntegerToken("110")); + Range wraps4 = new Range(new BigIntegerToken("10"), new BigIntegerToken("0")); + Range wraps5 = new Range(new BigIntegerToken("10"), new BigIntegerToken("1")); + Range wraps6 = new Range(new BigIntegerToken("30"), new BigIntegerToken("10")); + + assertIntersection(wraps1, + wraps2, + new Range(new BigIntegerToken("120"), new BigIntegerToken("20"))); + assertIntersection(wraps1, + wraps3, + new Range(new BigIntegerToken("120"), new BigIntegerToken("20")), + new Range(new BigIntegerToken("100"), new BigIntegerToken("110"))); + assertIntersection(wraps1, + wraps4, + new Range(new BigIntegerToken("10"), new BigIntegerToken("20")), + new Range(new BigIntegerToken("100"), new BigIntegerToken("0"))); + assertIntersection(wraps1, + wraps5, + new Range(new BigIntegerToken("10"), new BigIntegerToken("20")), + new Range(new BigIntegerToken("100"), new BigIntegerToken("1"))); + assertIntersection(wraps1, + wraps6, + new Range(new BigIntegerToken("100"), new BigIntegerToken("10"))); + } +}