cassandra-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ifesdj...@apache.org
Subject [1/3] cassandra git commit: Improve SASI range iterator efficiency on intersection with an empty range.
Date Fri, 10 Mar 2017 12:33:41 GMT
Repository: cassandra
Updated Branches:
  refs/heads/cassandra-3.11 9efa682b3 -> 2c111d15b
  refs/heads/trunk 957ad8c0b -> 67e9a5ffd


Improve SASI range iterator efficiency on intersection with an empty range.

Patch by Corentin Chary; reviewed by Alex Petrov for CASSANDRA-12915.

Project: http://git-wip-us.apache.org/repos/asf/cassandra/repo
Commit: http://git-wip-us.apache.org/repos/asf/cassandra/commit/2c111d15
Tree: http://git-wip-us.apache.org/repos/asf/cassandra/tree/2c111d15
Diff: http://git-wip-us.apache.org/repos/asf/cassandra/diff/2c111d15

Branch: refs/heads/cassandra-3.11
Commit: 2c111d15bb080283b9b98d48fab4bcf4db515b5a
Parents: 9efa682
Author: Alex Petrov <oleksandr.petrov@gmail.com>
Authored: Fri Mar 10 13:28:16 2017 +0100
Committer: Alex Petrov <oleksandr.petrov@gmail.com>
Committed: Fri Mar 10 13:31:15 2017 +0100

----------------------------------------------------------------------
 CHANGES.txt                                     |  1 +
 .../cassandra/index/sasi/TermIterator.java      |  2 +-
 .../index/sasi/plan/QueryController.java        |  3 -
 .../sasi/utils/RangeIntersectionIterator.java   |  9 ++-
 .../index/sasi/utils/RangeIterator.java         | 79 +++++++++++++++-----
 .../index/sasi/utils/RangeUnionIterator.java    |  9 ++-
 .../cassandra/index/sasi/SASIIndexTest.java     |  6 +-
 .../index/sasi/utils/LongIteratorTest.java      | 56 ++++++++++++++
 .../utils/RangeIntersectionIteratorTest.java    | 78 ++++++++++++++++++-
 .../sasi/utils/RangeUnionIteratorTest.java      | 72 +++++++++++++++++-
 10 files changed, 283 insertions(+), 32 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/cassandra/blob/2c111d15/CHANGES.txt
----------------------------------------------------------------------
diff --git a/CHANGES.txt b/CHANGES.txt
index acef1c2..302a028 100644
--- a/CHANGES.txt
+++ b/CHANGES.txt
@@ -1,4 +1,5 @@
 3.11.0
+ * Improve SASI range iterator efficiency on intersection with an empty range (CASSANDRA-12915).
  * Fix equality comparisons of columns using the duration type (CASSANDRA-13174)
  * Obfuscate password in stress-graphs (CASSANDRA-12233)
  * Move to FastThreadLocalThread and FastThreadLocal (CASSANDRA-13034)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/2c111d15/src/java/org/apache/cassandra/index/sasi/TermIterator.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/TermIterator.java b/src/java/org/apache/cassandra/index/sasi/TermIterator.java
index 03dea18..85f81b0 100644
--- a/src/java/org/apache/cassandra/index/sasi/TermIterator.java
+++ b/src/java/org/apache/cassandra/index/sasi/TermIterator.java
@@ -157,7 +157,7 @@ public class TermIterator extends RangeIterator<Long, Token>
             e.checkpoint();
 
             RangeIterator<Long, Token> ranges = RangeUnionIterator.build(tokens);
-            return ranges == null ? null : new TermIterator(e, ranges, referencedIndexes);
+            return new TermIterator(e, ranges, referencedIndexes);
         }
         catch (Throwable ex)
         {

http://git-wip-us.apache.org/repos/asf/cassandra/blob/2c111d15/src/java/org/apache/cassandra/index/sasi/plan/QueryController.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/plan/QueryController.java b/src/java/org/apache/cassandra/index/sasi/plan/QueryController.java
index 155cd4f..22fca68 100644
--- a/src/java/org/apache/cassandra/index/sasi/plan/QueryController.java
+++ b/src/java/org/apache/cassandra/index/sasi/plan/QueryController.java
@@ -144,9 +144,6 @@ public class QueryController
             @SuppressWarnings("resource") // RangeIterators are closed by releaseIndexes
             RangeIterator<Long, Token> index = TermIterator.build(e.getKey(), e.getValue());
 
-            if (index == null)
-                continue;
-
             builder.add(index);
             perIndexUnions.add(index);
         }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/2c111d15/src/java/org/apache/cassandra/index/sasi/utils/RangeIntersectionIterator.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/utils/RangeIntersectionIterator.java
b/src/java/org/apache/cassandra/index/sasi/utils/RangeIntersectionIterator.java
index 02d9527..bd8c725 100644
--- a/src/java/org/apache/cassandra/index/sasi/utils/RangeIntersectionIterator.java
+++ b/src/java/org/apache/cassandra/index/sasi/utils/RangeIntersectionIterator.java
@@ -59,10 +59,13 @@ public class RangeIntersectionIterator
 
         protected RangeIterator<K, D> buildIterator()
         {
-            // if the range is disjoint we can simply return empty
-            // iterator of any type, because it's not going to produce any results.
+            // if the range is disjoint or we have an intersection with an empty set,
+            // we can simply return an empty iterator, because it's not going to produce
any results.
             if (statistics.isDisjoint())
-                return new BounceIntersectionIterator<>(statistics, new PriorityQueue<RangeIterator<K,
D>>(1));
+                return new EmptyRangeIterator<>();
+
+            if (rangeCount() == 1)
+                return ranges.poll();
 
             switch (strategy)
             {

http://git-wip-us.apache.org/repos/asf/cassandra/blob/2c111d15/src/java/org/apache/cassandra/index/sasi/utils/RangeIterator.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/utils/RangeIterator.java b/src/java/org/apache/cassandra/index/sasi/utils/RangeIterator.java
index 1b5aee4..06c5a6a 100644
--- a/src/java/org/apache/cassandra/index/sasi/utils/RangeIterator.java
+++ b/src/java/org/apache/cassandra/index/sasi/utils/RangeIterator.java
@@ -42,6 +42,9 @@ public abstract class RangeIterator<K extends Comparable<K>, T
extends CombinedV
 
     public RangeIterator(K min, K max, long count)
     {
+        if (min == null || max == null || count == 0)
+            assert min == null && max == null && (count == 0 || count ==
-1);
+
         this.min = min;
         this.current = min;
         this.max = max;
@@ -148,10 +151,11 @@ public abstract class RangeIterator<K extends Comparable<K>,
T extends CombinedV
 
         public Builder<K, D> add(RangeIterator<K, D> range)
         {
-            if (range == null || range.getMinimum() == null || range.getMaximum() == null)
+            if (range == null)
                 return this;
 
-            ranges.add(range);
+            if (range.getCount() > 0)
+                ranges.add(range);
             statistics.update(range);
 
             return this;
@@ -168,17 +172,18 @@ public abstract class RangeIterator<K extends Comparable<K>,
T extends CombinedV
 
         public final RangeIterator<K, D> build()
         {
-            switch (rangeCount())
-            {
-                case 0:
-                    return null;
-
-                case 1:
-                    return ranges.poll();
+            if (rangeCount() == 0)
+                return new EmptyRangeIterator<>();
+            else
+                return buildIterator();
+        }
 
-                default:
-                    return buildIterator();
-            }
+        public static class EmptyRangeIterator<K extends Comparable<K>, D extends
CombinedValue<K>> extends RangeIterator<K, D>
+        {
+            EmptyRangeIterator() { super(null, null, 0); }
+            public D computeNext() { return endOfData(); }
+            protected void performSkipTo(K nextToken) { }
+            public void close() { }
         }
 
         protected abstract RangeIterator<K, D> buildIterator();
@@ -197,7 +202,7 @@ public abstract class RangeIterator<K extends Comparable<K>,
T extends CombinedV
 
             // tracks if all of the added ranges overlap, which is useful in case of intersection,
             // as it gives direct answer as to such iterator is going to produce any results.
-            protected boolean isOverlapping = true;
+            private boolean isOverlapping = true;
 
             public Statistics(IteratorType iteratorType)
             {
@@ -217,15 +222,15 @@ public abstract class RangeIterator<K extends Comparable<K>,
T extends CombinedV
                 switch (iteratorType)
                 {
                     case UNION:
-                        min = min == null || min.compareTo(range.getMinimum()) > 0 ? range.getMinimum()
: min;
-                        max = max == null || max.compareTo(range.getMaximum()) < 0 ? range.getMaximum()
: max;
+                        min = nullSafeMin(min, range.getMinimum());
+                        max = nullSafeMax(max, range.getMaximum());
                         break;
 
                     case INTERSECTION:
                         // minimum of the intersection is the biggest minimum of individual
iterators
-                        min = min == null || min.compareTo(range.getMinimum()) < 0 ? range.getMinimum()
: min;
+                        min = nullSafeMax(min, range.getMinimum());
                         // maximum of the intersection is the smallest maximum of individual
iterators
-                        max = max == null || max.compareTo(range.getMaximum()) > 0 ? range.getMaximum()
: max;
+                        max = nullSafeMin(max, range.getMaximum());
                         break;
 
                     default:
@@ -240,7 +245,6 @@ public abstract class RangeIterator<K extends Comparable<K>,
T extends CombinedV
                 maxRange = maxRange == null ? range : max(maxRange, range);
 
                 tokenCount += range.getCount();
-
             }
 
             private RangeIterator<K, D> min(RangeIterator<K, D> a, RangeIterator<K,
D> b)
@@ -271,9 +275,46 @@ public abstract class RangeIterator<K extends Comparable<K>,
T extends CombinedV
         return isOverlapping(a.getCurrent(), a.getMaximum(), b);
     }
 
+    /**
+     * Ranges are overlapping the following cases:
+     *
+     *   * When they have a common subrange:
+     *
+     *   min       b.current      max          b.max
+     *   +---------|--------------+------------|
+     *
+     *   b.current      min       max          b.max
+     *   |--------------+---------+------------|
+     *
+     *   min        b.current     b.max        max
+     *   +----------|-------------|------------+
+     *
+     *
+     *  If either range is empty, they're disjoint.
+     */
     @VisibleForTesting
     protected static <K extends Comparable<K>, D extends CombinedValue<K>>
boolean isOverlapping(K min, K max, RangeIterator<K, D> b)
     {
-        return min.compareTo(b.getMaximum()) <= 0 && b.getCurrent().compareTo(max)
<= 0;
+        return (min != null && max != null) &&
+               b.getCount() != 0 &&
+               (min.compareTo(b.getMaximum()) <= 0 && b.getCurrent().compareTo(max)
<= 0);
+    }
+
+    @SuppressWarnings("unchecked")
+    private static <T extends Comparable> T nullSafeMin(T a, T b)
+    {
+        if (a == null) return b;
+        if (b == null) return a;
+
+        return a.compareTo(b) > 0 ? b : a;
+    }
+
+    @SuppressWarnings("unchecked")
+    private static <T extends Comparable> T nullSafeMax(T a, T b)
+    {
+        if (a == null) return b;
+        if (b == null) return a;
+
+        return a.compareTo(b) > 0 ? a : b;
     }
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/2c111d15/src/java/org/apache/cassandra/index/sasi/utils/RangeUnionIterator.java
----------------------------------------------------------------------
diff --git a/src/java/org/apache/cassandra/index/sasi/utils/RangeUnionIterator.java b/src/java/org/apache/cassandra/index/sasi/utils/RangeUnionIterator.java
index 4be460c..599de07 100644
--- a/src/java/org/apache/cassandra/index/sasi/utils/RangeUnionIterator.java
+++ b/src/java/org/apache/cassandra/index/sasi/utils/RangeUnionIterator.java
@@ -153,7 +153,14 @@ public class RangeUnionIterator<K extends Comparable<K>, D extends
CombinedValue
 
         protected RangeIterator<K, D> buildIterator()
         {
-            return new RangeUnionIterator<>(statistics, ranges);
+            switch (rangeCount())
+            {
+                case 1:
+                    return ranges.poll();
+
+                default:
+                    return new RangeUnionIterator<>(statistics, ranges);
+            }
         }
     }
 }

http://git-wip-us.apache.org/repos/asf/cassandra/blob/2c111d15/test/unit/org/apache/cassandra/index/sasi/SASIIndexTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/index/sasi/SASIIndexTest.java b/test/unit/org/apache/cassandra/index/sasi/SASIIndexTest.java
index 399aa40..3bd27e6 100644
--- a/test/unit/org/apache/cassandra/index/sasi/SASIIndexTest.java
+++ b/test/unit/org/apache/cassandra/index/sasi/SASIIndexTest.java
@@ -2253,7 +2253,7 @@ public class SASIIndexTest
         IndexMemtable afterFlushMemtable = index.getCurrentMemtable();
 
         Assert.assertNotSame(afterFlushMemtable, beforeFlushMemtable);
-        Assert.assertNull(afterFlushMemtable.search(expression));
+        Assert.assertEquals(afterFlushMemtable.search(expression).getCount(), 0);
         Assert.assertEquals(0, index.getPendingMemtables().size());
 
         loadData(new HashMap<String, Pair<String, Integer>>()
@@ -2279,7 +2279,7 @@ public class SASIIndexTest
         index.discardMemtable(store.getTracker().getView().getCurrentMemtable());
 
         Assert.assertEquals(0, index.getPendingMemtables().size());
-        Assert.assertNull(index.searchMemtable(expression));
+        Assert.assertEquals(index.searchMemtable(expression).getCount(), 0);
 
         // test discarding data from memtable
         loadData(new HashMap<String, Pair<String, Integer>>()
@@ -2293,7 +2293,7 @@ public class SASIIndexTest
         Assert.assertTrue(index.searchMemtable(expression).getCount() > 0);
 
         index.switchMemtable();
-        Assert.assertNull(index.searchMemtable(expression));
+        Assert.assertEquals(index.searchMemtable(expression).getCount(), 0);
     }
 
     private static ColumnFamilyStore loadData(Map<String, Pair<String, Integer>>
data, boolean forceFlush)

http://git-wip-us.apache.org/repos/asf/cassandra/blob/2c111d15/test/unit/org/apache/cassandra/index/sasi/utils/LongIteratorTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/index/sasi/utils/LongIteratorTest.java b/test/unit/org/apache/cassandra/index/sasi/utils/LongIteratorTest.java
new file mode 100644
index 0000000..05db33a
--- /dev/null
+++ b/test/unit/org/apache/cassandra/index/sasi/utils/LongIteratorTest.java
@@ -0,0 +1,56 @@
+/*
+ * 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 org.junit.Assert;
+import org.junit.Test;
+
+import java.io.IOException;
+
+import static org.apache.cassandra.index.sasi.utils.LongIterator.convert;
+
+public class LongIteratorTest
+{
+    @Test
+    public void testEmptyIterator() throws IOException {
+        LongIterator it = new LongIterator(new long[] { });
+
+        Assert.assertEquals(0, it.getCount());
+        Assert.assertEquals(null, it.getCurrent());
+        Assert.assertEquals(null, it.getMaximum());
+        Assert.assertEquals(null, it.getMinimum());
+        Assert.assertFalse(it.hasNext());
+
+        it.close();
+    }
+
+    @Test
+    public void testBasicITerator() throws IOException {
+        LongIterator it = new LongIterator(new long[] { 2L, 3L, 5L, 6L });
+
+        Assert.assertEquals(4L, (long) it.getCount());
+        Assert.assertEquals(2L, (long) it.getCurrent());
+        Assert.assertEquals(6L, (long) it.getMaximum());
+        Assert.assertEquals(2L, (long) it.getMinimum());
+
+        Assert.assertEquals(2L, (long) it.next().get());
+        Assert.assertEquals(3L, (long) it.next().get());
+
+        it.close();
+    }
+}
\ No newline at end of file

http://git-wip-us.apache.org/repos/asf/cassandra/blob/2c111d15/test/unit/org/apache/cassandra/index/sasi/utils/RangeIntersectionIteratorTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/index/sasi/utils/RangeIntersectionIteratorTest.java
b/test/unit/org/apache/cassandra/index/sasi/utils/RangeIntersectionIteratorTest.java
index 18b9dd7..4dc9e3f 100644
--- a/test/unit/org/apache/cassandra/index/sasi/utils/RangeIntersectionIteratorTest.java
+++ b/test/unit/org/apache/cassandra/index/sasi/utils/RangeIntersectionIteratorTest.java
@@ -223,7 +223,7 @@ public class RangeIntersectionIteratorTest
         FileUtils.closeQuietly(tokens);
 
         RangeIterator emptyTokens = RangeIntersectionIterator.builder(strategy).build();
-        Assert.assertNull(emptyTokens);
+        Assert.assertEquals(0, emptyTokens.getCount());
 
         builder = RangeIntersectionIterator.builder(strategy);
         Assert.assertEquals(0L, builder.add((RangeIterator<Long, Token>) null).rangeCount());
@@ -236,6 +236,15 @@ public class RangeIntersectionIteratorTest
         // 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 }));
@@ -250,6 +259,73 @@ public class RangeIntersectionIteratorTest
     }
 
     @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())

http://git-wip-us.apache.org/repos/asf/cassandra/blob/2c111d15/test/unit/org/apache/cassandra/index/sasi/utils/RangeUnionIteratorTest.java
----------------------------------------------------------------------
diff --git a/test/unit/org/apache/cassandra/index/sasi/utils/RangeUnionIteratorTest.java b/test/unit/org/apache/cassandra/index/sasi/utils/RangeUnionIteratorTest.java
index f69086b..162b1c6 100644
--- a/test/unit/org/apache/cassandra/index/sasi/utils/RangeUnionIteratorTest.java
+++ b/test/unit/org/apache/cassandra/index/sasi/utils/RangeUnionIteratorTest.java
@@ -214,7 +214,7 @@ public class RangeUnionIteratorTest
         FileUtils.closeQuietly(tokens);
 
         RangeIterator emptyTokens = RangeUnionIterator.builder().build();
-        Assert.assertNull(emptyTokens);
+        Assert.assertEquals(0, emptyTokens.getCount());
 
         builder = RangeUnionIterator.builder();
         Assert.assertEquals(0L, builder.add((RangeIterator<Long, Token>) null).rangeCount());
@@ -303,4 +303,74 @@ public class RangeUnionIteratorTest
         Assert.assertNull(empty.skipTo(3L));
         Assert.assertFalse(empty.hasNext());
     }
+
+    @Test
+    public void emptyRangeTest() {
+        RangeIterator.Builder<Long, Token> builder;
+        RangeIterator<Long, Token> range;
+        // empty, then non-empty
+        builder = RangeUnionIterator.builder();
+        builder.add(new LongIterator(new long[] {}));
+        for (int i = 0; i < 10; i++)
+            builder.add(new LongIterator(new long[] {i + 10}));
+        range = builder.build();
+        Assert.assertEquals(Long.valueOf(10), range.getMinimum());
+        Assert.assertEquals(Long.valueOf(19), range.getMaximum());
+        Assert.assertTrue(range.hasNext());
+        Assert.assertEquals(10, range.getCount());
+
+        builder = RangeUnionIterator.builder();
+        builder.add(new LongIterator(new long[] {}));
+        builder.add(new LongIterator(new long[] {10}));
+        range = builder.build();
+        Assert.assertEquals(Long.valueOf(10), range.getMinimum());
+        Assert.assertEquals(Long.valueOf(10), range.getMaximum());
+        Assert.assertTrue(range.hasNext());
+        Assert.assertEquals(1, range.getCount());
+
+        // non-empty, then empty
+        builder = RangeUnionIterator.builder();
+        for (int i = 0; i < 10; i++)
+            builder.add(new LongIterator(new long[] {i + 10}));
+        builder.add(new LongIterator(new long[] {}));
+        range = builder.build();
+        Assert.assertEquals(Long.valueOf(10), range.getMinimum());
+        Assert.assertEquals(Long.valueOf(19), range.getMaximum());
+        Assert.assertTrue(range.hasNext());
+        Assert.assertEquals(10, range.getCount());
+
+        builder = RangeUnionIterator.builder();
+        builder.add(new LongIterator(new long[] {10}));
+        builder.add(new LongIterator(new long[] {}));
+        range = builder.build();
+        Assert.assertEquals(Long.valueOf(10), range.getMinimum());
+        Assert.assertEquals(Long.valueOf(10), range.getMaximum());
+        Assert.assertTrue(range.hasNext());
+        Assert.assertEquals(1, range.getCount());
+
+        // empty, then non-empty then empty again
+        builder = RangeUnionIterator.builder();
+        builder.add(new LongIterator(new long[] {}));
+        for (int i = 0; i < 10; i++)
+            builder.add(new LongIterator(new long[] {i + 10}));
+        builder.add(new LongIterator(new long[] {}));
+        range = builder.build();
+        Assert.assertEquals(Long.valueOf(10), range.getMinimum());
+        Assert.assertEquals(Long.valueOf(19), range.getMaximum());
+        Assert.assertTrue(range.hasNext());
+        Assert.assertEquals(10, range.getCount());
+
+        // non-empty, empty, then non-empty again
+        builder = RangeUnionIterator.builder();
+        for (int i = 0; i < 5; i++)
+            builder.add(new LongIterator(new long[] {i + 10}));
+        builder.add(new LongIterator(new long[] {}));
+        for (int i = 5; i < 10; i++)
+            builder.add(new LongIterator(new long[] {i + 10}));
+        range = builder.build();
+        Assert.assertEquals(Long.valueOf(10), range.getMinimum());
+        Assert.assertEquals(Long.valueOf(19), range.getMaximum());
+        Assert.assertTrue(range.hasNext());
+        Assert.assertEquals(10, range.getCount());
+    }
 }
\ No newline at end of file


Mime
View raw message