| /* |
| * 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.index.sasi.utils; |
| |
| import java.io.IOException; |
| import java.util.*; |
| import java.util.concurrent.ThreadLocalRandom; |
| |
| import org.apache.cassandra.index.sasi.disk.Token; |
| import org.apache.cassandra.index.sasi.utils.RangeIntersectionIterator.Strategy; |
| import org.apache.cassandra.index.sasi.utils.RangeIntersectionIterator.LookupIntersectionIterator; |
| import org.apache.cassandra.index.sasi.utils.RangeIntersectionIterator.BounceIntersectionIterator; |
| import org.apache.cassandra.io.util.FileUtils; |
| |
| import com.carrotsearch.hppc.LongOpenHashSet; |
| import com.carrotsearch.hppc.LongSet; |
| |
| import org.junit.Assert; |
| import org.junit.Test; |
| |
| import static org.apache.cassandra.index.sasi.utils.LongIterator.convert; |
| |
| public class RangeIntersectionIteratorTest |
| { |
| @Test |
| public void testNoOverlappingValues() |
| { |
| for (Strategy strategy : Strategy.values()) |
| testNoOverlappingValues(strategy); |
| } |
| |
| private void testNoOverlappingValues(Strategy strategy) |
| { |
| RangeIterator.Builder<Long, Token> builder = RangeIntersectionIterator.builder(strategy); |
| |
| builder.add(new LongIterator(new long[] { 2L, 3L, 5L, 6L })); |
| builder.add(new LongIterator(new long[] { 1L, 7L })); |
| builder.add(new LongIterator(new long[] { 4L, 8L, 9L, 10L })); |
| |
| Assert.assertEquals(convert(), convert(builder.build())); |
| |
| builder = RangeIntersectionIterator.builder(strategy); |
| // both ranges overlap by min/max but not by value |
| builder.add(new LongIterator(new long[] { 1L, 5L, 7L, 9L })); |
| builder.add(new LongIterator(new long[] { 6L })); |
| |
| RangeIterator<Long, Token> range = builder.build(); |
| |
| Assert.assertNotNull(range); |
| Assert.assertFalse(range.hasNext()); |
| |
| builder = RangeIntersectionIterator.builder(strategy); |
| // both ranges overlap by min/max but not by value |
| builder.add(new LongIterator(new long[] { 1L, 5L, 7L, 9L })); |
| builder.add(new LongIterator(new long[] { 0L, 10L, 12L })); |
| |
| range = builder.build(); |
| |
| Assert.assertNotNull(range); |
| Assert.assertFalse(range.hasNext()); |
| } |
| |
| @Test |
| public void testOverlappingValues() |
| { |
| for (Strategy strategy : Strategy.values()) |
| testOverlappingValues(strategy); |
| } |
| |
| private void testOverlappingValues(Strategy strategy) |
| { |
| RangeIterator.Builder<Long, Token> builder = RangeIntersectionIterator.builder(strategy); |
| |
| builder.add(new LongIterator(new long[] { 1L, 4L, 6L, 7L })); |
| builder.add(new LongIterator(new long[] { 2L, 4L, 5L, 6L })); |
| builder.add(new LongIterator(new long[] { 4L, 6L, 8L, 9L, 10L })); |
| |
| Assert.assertEquals(convert(4L, 6L), convert(builder.build())); |
| } |
| |
| @Test |
| public void testSingleIterator() |
| { |
| for (Strategy strategy : Strategy.values()) |
| testSingleIterator(strategy); |
| } |
| |
| private void testSingleIterator(Strategy strategy) |
| { |
| RangeIntersectionIterator.Builder<Long, Token> builder = RangeIntersectionIterator.builder(strategy); |
| |
| builder.add(new LongIterator(new long[] { 1L, 2L, 4L, 9L })); |
| |
| Assert.assertEquals(convert(1L, 2L, 4L, 9L), convert(builder.build())); |
| } |
| |
| @Test |
| public void testSkipTo() |
| { |
| for (Strategy strategy : Strategy.values()) |
| testSkipTo(strategy); |
| } |
| |
| private void testSkipTo(Strategy strategy) |
| { |
| RangeIterator.Builder<Long, Token> builder = RangeIntersectionIterator.builder(strategy); |
| |
| builder.add(new LongIterator(new long[] { 1L, 4L, 6L, 7L, 9L, 10L })); |
| builder.add(new LongIterator(new long[] { 2L, 4L, 5L, 6L, 7L, 10L, 12L })); |
| builder.add(new LongIterator(new long[] { 4L, 6L, 7L, 9L, 10L })); |
| |
| RangeIterator<Long, Token> range = builder.build(); |
| Assert.assertNotNull(range); |
| |
| // first let's skipTo something before range |
| Assert.assertEquals(4L, (long) range.skipTo(3L).get()); |
| Assert.assertEquals(4L, (long) range.getCurrent()); |
| |
| // now let's skip right to the send value |
| Assert.assertEquals(6L, (long) range.skipTo(5L).get()); |
| Assert.assertEquals(6L, (long) range.getCurrent()); |
| |
| // now right to the element |
| Assert.assertEquals(7L, (long) range.skipTo(7L).get()); |
| Assert.assertEquals(7L, (long) range.getCurrent()); |
| Assert.assertEquals(7L, (long) range.next().get()); |
| |
| Assert.assertTrue(range.hasNext()); |
| Assert.assertEquals(10L, (long) range.getCurrent()); |
| |
| // now right after the last element |
| Assert.assertNull(range.skipTo(11L)); |
| Assert.assertFalse(range.hasNext()); |
| } |
| |
| @Test |
| public void testMinMaxAndCount() |
| { |
| for (Strategy strategy : Strategy.values()) |
| testMinMaxAndCount(strategy); |
| } |
| |
| private void testMinMaxAndCount(Strategy strategy) |
| { |
| RangeIterator.Builder<Long, Token> builder = RangeIntersectionIterator.builder(strategy); |
| |
| builder.add(new LongIterator(new long[]{1L, 2L, 9L})); |
| builder.add(new LongIterator(new long[]{4L, 5L, 9L})); |
| builder.add(new LongIterator(new long[]{7L, 8L, 9L})); |
| |
| Assert.assertEquals(9L, (long) builder.getMaximum()); |
| Assert.assertEquals(9L, builder.getTokenCount()); |
| |
| RangeIterator<Long, Token> tokens = builder.build(); |
| |
| Assert.assertNotNull(tokens); |
| Assert.assertEquals(7L, (long) tokens.getMinimum()); |
| Assert.assertEquals(9L, (long) tokens.getMaximum()); |
| Assert.assertEquals(9L, tokens.getCount()); |
| |
| Assert.assertEquals(convert(9L), convert(builder.build())); |
| } |
| |
| @Test |
| public void testBuilder() |
| { |
| for (Strategy strategy : Strategy.values()) |
| testBuilder(strategy); |
| } |
| |
| private void testBuilder(Strategy strategy) |
| { |
| RangeIterator.Builder<Long, Token> builder = RangeIntersectionIterator.builder(strategy); |
| |
| Assert.assertNull(builder.getMinimum()); |
| Assert.assertNull(builder.getMaximum()); |
| Assert.assertEquals(0L, builder.getTokenCount()); |
| Assert.assertEquals(0L, builder.rangeCount()); |
| |
| builder.add(new LongIterator(new long[] { 1L, 2L, 6L })); |
| builder.add(new LongIterator(new long[] { 4L, 5L, 6L })); |
| builder.add(new LongIterator(new long[] { 6L, 8L, 9L })); |
| |
| Assert.assertEquals(6L, (long) builder.getMinimum()); |
| Assert.assertEquals(6L, (long) builder.getMaximum()); |
| Assert.assertEquals(9L, builder.getTokenCount()); |
| Assert.assertEquals(3L, builder.rangeCount()); |
| Assert.assertFalse(builder.statistics.isDisjoint()); |
| |
| Assert.assertEquals(1L, (long) builder.ranges.poll().getMinimum()); |
| Assert.assertEquals(4L, (long) builder.ranges.poll().getMinimum()); |
| Assert.assertEquals(6L, (long) builder.ranges.poll().getMinimum()); |
| |
| builder.add(new LongIterator(new long[] { 1L, 2L, 6L })); |
| builder.add(new LongIterator(new long[] { 4L, 5L, 6L })); |
| builder.add(new LongIterator(new long[] { 6L, 8L, 9L })); |
| |
| Assert.assertEquals(convert(6L), convert(builder.build())); |
| |
| builder = RangeIntersectionIterator.builder(strategy); |
| builder.add(new LongIterator(new long[]{ 1L, 5L, 6L })); |
| builder.add(new LongIterator(new long[]{ 3L, 5L, 6L })); |
| |
| RangeIterator<Long, Token> tokens = builder.build(); |
| |
| Assert.assertEquals(convert(5L, 6L), convert(tokens)); |
| |
| FileUtils.closeQuietly(tokens); |
| |
| RangeIterator emptyTokens = RangeIntersectionIterator.builder(strategy).build(); |
| Assert.assertEquals(0, emptyTokens.getCount()); |
| |
| builder = RangeIntersectionIterator.builder(strategy); |
| Assert.assertEquals(0L, builder.add((RangeIterator<Long, Token>) null).rangeCount()); |
| Assert.assertEquals(0L, builder.add((List<RangeIterator<Long, Token>>) null).getTokenCount()); |
| Assert.assertEquals(0L, builder.add(new LongIterator(new long[] {})).rangeCount()); |
| |
| RangeIterator<Long, Token> single = new LongIterator(new long[] { 1L, 2L, 3L }); |
| RangeIterator<Long, Token> range = RangeIntersectionIterator.<Long, Token>builder().add(single).build(); |
| |
| // because build should return first element if it's only one instead of building yet another iterator |
| Assert.assertEquals(range, single); |
| |
| // Make a difference between empty and null ranges. |
| builder = RangeIntersectionIterator.builder(strategy); |
| builder.add(new LongIterator(new long[] {})); |
| Assert.assertEquals(0L, builder.rangeCount()); |
| builder.add(single); |
| Assert.assertEquals(1L, builder.rangeCount()); |
| range = builder.build(); |
| Assert.assertEquals(0, range.getCount()); |
| |
| // disjoint case |
| builder = RangeIntersectionIterator.builder(); |
| builder.add(new LongIterator(new long[] { 1L, 2L, 3L })); |
| builder.add(new LongIterator(new long[] { 4L, 5L, 6L })); |
| |
| Assert.assertTrue(builder.statistics.isDisjoint()); |
| |
| RangeIterator<Long, Token> disjointIntersection = builder.build(); |
| Assert.assertNotNull(disjointIntersection); |
| Assert.assertFalse(disjointIntersection.hasNext()); |
| |
| } |
| |
| @Test |
| public void emptyRangeTest() { |
| RangeIterator.Builder<Long, Token> builder; |
| |
| // empty, then non-empty |
| builder = RangeIntersectionIterator.builder(); |
| builder.add(new LongIterator(new long[] {})); |
| builder.add(new LongIterator(new long[] {10})); |
| assertEmpty(builder.build()); |
| |
| builder = RangeIntersectionIterator.builder(); |
| builder.add(new LongIterator(new long[] {})); |
| for (int i = 0; i < 10; i++) |
| builder.add(new LongIterator(new long[] {0, i + 10})); |
| assertEmpty(builder.build()); |
| |
| // non-empty, then empty |
| builder = RangeIntersectionIterator.builder(); |
| builder.add(new LongIterator(new long[] {10})); |
| builder.add(new LongIterator(new long[] {})); |
| assertEmpty(builder.build()); |
| |
| builder = RangeIntersectionIterator.builder(); |
| for (int i = 0; i < 10; i++) |
| builder.add(new LongIterator(new long[] {0, i + 10})); |
| |
| builder.add(new LongIterator(new long[] {})); |
| assertEmpty(builder.build()); |
| |
| // empty, then non-empty then empty again |
| builder = RangeIntersectionIterator.builder(); |
| builder.add(new LongIterator(new long[] {})); |
| builder.add(new LongIterator(new long[] {0, 10})); |
| builder.add(new LongIterator(new long[] {})); |
| assertEmpty(builder.build()); |
| |
| builder = RangeIntersectionIterator.builder(); |
| builder.add(new LongIterator(new long[] {})); |
| for (int i = 0; i < 10; i++) |
| builder.add(new LongIterator(new long[] {0, i + 10})); |
| builder.add(new LongIterator(new long[] {})); |
| assertEmpty(builder.build()); |
| |
| // non-empty, empty, then non-empty again |
| builder = RangeIntersectionIterator.builder(); |
| builder.add(new LongIterator(new long[] {0, 10})); |
| builder.add(new LongIterator(new long[] {})); |
| builder.add(new LongIterator(new long[] {0, 10})); |
| assertEmpty(builder.build()); |
| |
| builder = RangeIntersectionIterator.builder(); |
| for (int i = 0; i < 5; i++) |
| builder.add(new LongIterator(new long[] {0, i + 10})); |
| builder.add(new LongIterator(new long[] {})); |
| for (int i = 5; i < 10; i++) |
| builder.add(new LongIterator(new long[] {0, i + 10})); |
| assertEmpty(builder.build()); |
| } |
| |
| public static void assertEmpty(RangeIterator<Long, Token> range) |
| { |
| Assert.assertNull(range.getMinimum()); |
| Assert.assertNull(range.getMaximum()); |
| Assert.assertFalse(range.hasNext()); |
| Assert.assertEquals(0, range.getCount()); |
| } |
| |
| @Test |
| public void testClose() throws IOException |
| { |
| for (Strategy strategy : Strategy.values()) |
| testClose(strategy); |
| } |
| |
| private void testClose(Strategy strategy) throws IOException |
| { |
| RangeIterator<Long, Token> tokens = RangeIntersectionIterator.<Long, Token>builder(strategy) |
| .add(new LongIterator(new long[] { 1L, 2L, 3L })) |
| .build(); |
| |
| Assert.assertNotNull(tokens); |
| tokens.close(); |
| } |
| |
| @Test |
| public void testIsOverlapping() |
| { |
| RangeIterator<Long, Token> rangeA, rangeB; |
| |
| rangeA = new LongIterator(new long[] { 1L, 5L }); |
| rangeB = new LongIterator(new long[] { 5L, 9L }); |
| Assert.assertTrue(RangeIterator.isOverlapping(rangeA, rangeB)); |
| |
| rangeA = new LongIterator(new long[] { 5L, 9L }); |
| rangeB = new LongIterator(new long[] { 1L, 6L }); |
| Assert.assertTrue(RangeIterator.isOverlapping(rangeA, rangeB)); |
| |
| rangeA = new LongIterator(new long[] { 5L, 9L }); |
| rangeB = new LongIterator(new long[] { 5L, 9L }); |
| Assert.assertTrue(RangeIterator.isOverlapping(rangeA, rangeB)); |
| |
| rangeA = new LongIterator(new long[] { 1L, 4L }); |
| rangeB = new LongIterator(new long[] { 5L, 9L }); |
| Assert.assertFalse(RangeIterator.isOverlapping(rangeA, rangeB)); |
| |
| rangeA = new LongIterator(new long[] { 6L, 9L }); |
| rangeB = new LongIterator(new long[] { 1L, 4L }); |
| Assert.assertFalse(RangeIterator.isOverlapping(rangeA, rangeB)); |
| } |
| |
| @Test |
| public void testIntersectionOfRandomRanges() |
| { |
| for (Strategy strategy : Strategy.values()) |
| testIntersectionOfRandomRanges(strategy); |
| } |
| |
| private void testIntersectionOfRandomRanges(Strategy strategy) |
| { |
| for (int attempt = 0; attempt < 16; attempt++) |
| { |
| final ThreadLocalRandom random = ThreadLocalRandom.current(); |
| final int maxRanges = random.nextInt(2, 16); |
| |
| // generate randomize ranges |
| long[][] ranges = new long[maxRanges][]; |
| for (int i = 0; i < ranges.length; i++) |
| { |
| int rangeSize = random.nextInt(16, 512); |
| LongSet range = new LongOpenHashSet(rangeSize); |
| |
| for (int j = 0; j < rangeSize; j++) |
| range.add(random.nextLong(0, 100)); |
| |
| ranges[i] = range.toArray(); |
| Arrays.sort(ranges[i]); |
| } |
| |
| List<Long> expected = new ArrayList<>(); |
| // determine unique tokens which intersect every range |
| for (long token : ranges[0]) |
| { |
| boolean intersectsAll = true; |
| for (int i = 1; i < ranges.length; i++) |
| { |
| if (Arrays.binarySearch(ranges[i], token) < 0) |
| { |
| intersectsAll = false; |
| break; |
| } |
| } |
| |
| if (intersectsAll) |
| expected.add(token); |
| } |
| |
| RangeIterator.Builder<Long, Token> builder = RangeIntersectionIterator.builder(strategy); |
| for (long[] range : ranges) |
| builder.add(new LongIterator(range)); |
| |
| Assert.assertEquals(expected, convert(builder.build())); |
| } |
| } |
| |
| @Test |
| public void testIteratorPeeking() |
| { |
| RangeIterator.Builder<Long, Token> builder = RangeIntersectionIterator.builder(); |
| |
| // iterator with only one element |
| builder.add(new LongIterator(new long[] { 10L })); |
| |
| // iterator with 150 elements (lookup is going to be advantageous over bound in this case) |
| long[] tokens = new long[150]; |
| for (int i = 0; i < tokens.length; i++) |
| tokens[i] = i; |
| |
| builder.add(new LongIterator(tokens)); |
| |
| RangeIterator<Long, Token> intersection = builder.build(); |
| |
| Assert.assertNotNull(intersection); |
| Assert.assertEquals(LookupIntersectionIterator.class, intersection.getClass()); |
| |
| Assert.assertTrue(intersection.hasNext()); |
| Assert.assertEquals(convert(10L), convert(intersection)); |
| |
| builder = RangeIntersectionIterator.builder(); |
| |
| builder.add(new LongIterator(new long[] { 1L, 3L, 5L, 7L, 9L })); |
| builder.add(new LongIterator(new long[] { 1L, 2L, 5L, 6L })); |
| |
| intersection = builder.build(); |
| |
| // in the situation when there is a similar number of elements inside ranges |
| // ping-pong (bounce) intersection is preferred as it covers gaps quicker then linear scan + lookup. |
| Assert.assertNotNull(intersection); |
| Assert.assertEquals(BounceIntersectionIterator.class, intersection.getClass()); |
| |
| Assert.assertTrue(intersection.hasNext()); |
| Assert.assertEquals(convert(1L, 5L), convert(intersection)); |
| } |
| } |