This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch FixMikhailsBug in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit c89e0711418666801f4dcc5c39924ad656d97e5f Author: Lee Rhodes <[email protected]> AuthorDate: Mon Oct 18 15:59:04 2021 -0400 This fixes Mikhail's Bug: datasketches-java Issue #368. In addition to the issue that Mikhail found, I found a number of other discrepancies in the treatment of various corner cases in the Set Operations. Those were also fixed. --- .../org/apache/datasketches/theta/AnotBimpl.java | 13 +- .../java/org/apache/datasketches/tuple/AnotB.java | 107 +++- .../apache/datasketches/tuple/Intersection.java | 22 +- .../datasketches/tuple/QuickSelectSketch.java | 3 +- .../theta/CornerCaseThetaSetOperationsTest.java | 679 +++++++++++++++++++++ .../CornerCaseTupleSetOperationsTest.java | 659 ++++++++++++++++++++ 6 files changed, 1449 insertions(+), 34 deletions(-) diff --git a/src/main/java/org/apache/datasketches/theta/AnotBimpl.java b/src/main/java/org/apache/datasketches/theta/AnotBimpl.java index 35e3241..6f8828e 100644 --- a/src/main/java/org/apache/datasketches/theta/AnotBimpl.java +++ b/src/main/java/org/apache/datasketches/theta/AnotBimpl.java @@ -78,6 +78,7 @@ final class AnotBimpl extends AnotB { //process A hashArr_ = getHashArrA(skA); + hashArr_ = (hashArr_ == null) ? new long[0] : hashArr_; empty_ = false; thetaLong_ = skA.getThetaLong(); curCount_ = hashArr_.length; @@ -93,6 +94,7 @@ final class AnotBimpl extends AnotB { //process B hashArr_ = getResultHashArr(thetaLong_, curCount_, hashArr_, skB); + hashArr_ = (hashArr_ == null) ? new long[0] : hashArr_; curCount_ = hashArr_.length; empty_ = curCount_ == 0 && thetaLong_ == Long.MAX_VALUE; } @@ -119,17 +121,22 @@ final class AnotBimpl extends AnotB { } //Both skA & skB are not null + final long minThetaLong = Math.min(skA.getThetaLong(), skB.getThetaLong()); + if (skA.isEmpty()) { return skA.compact(dstOrdered, dstMem); } + //A is not Empty checkSeedHashes(skA.getSeedHash(), seedHash_); - if (skB.isEmpty()) { return skA.compact(dstOrdered, dstMem); } + if (skB.isEmpty() && skB.getRetainedEntries() == 0) { + return skA.compact(dstOrdered, dstMem); + } checkSeedHashes(skB.getSeedHash(), seedHash_); //Both skA & skB are not empty //process A final long[] hashArrA = getHashArrA(skA); - final int countA = hashArrA.length; - final long minThetaLong = Math.min(skA.getThetaLong(), skB.getThetaLong()); + final int countA = (hashArrA == null) ? 0 : hashArrA.length; + //process B final long[] hashArrOut = getResultHashArr(minThetaLong, countA, hashArrA, skB); //out is clone diff --git a/src/main/java/org/apache/datasketches/tuple/AnotB.java b/src/main/java/org/apache/datasketches/tuple/AnotB.java index 5dadfdf..2b5de6c 100644 --- a/src/main/java/org/apache/datasketches/tuple/AnotB.java +++ b/src/main/java/org/apache/datasketches/tuple/AnotB.java @@ -37,7 +37,7 @@ import org.apache.datasketches.SketchesStateException; * * <p>The stateful operation is as follows:</p> * <pre><code> - * AnotB anotb = SetOperationBuilder.buildAnotB(); + * AnotB anotb = new AnotB(); * * anotb.setA(Sketch skA); //The first argument. * anotb.notB(Sketch skB); //The second (subtraction) argument. @@ -49,7 +49,7 @@ import org.apache.datasketches.SketchesStateException; * * <p>The stateless operation is as follows:</p> * <pre><code> - * AnotB anotb = SetOperationBuilder.buildAnotB(); + * AnotB anotb = new AnotB(); * * CompactSketch csk = anotb.aNotB(Sketch skA, Sketch skB); * </code></pre> @@ -95,10 +95,10 @@ public final class AnotB<S extends Summary> { * With a null as the first argument, we cannot know what the user's intent is. * Since it is very likely that a <i>null</i> is a programming error, we throw a an exception.</p> * - * <p>An enpty input argument will set the internal state to empty.</p> + * <p>An empty input argument will set the internal state to empty.</p> * * <p>Rationale: An empty set is a mathematically legal concept. Although it makes any subsequent, - * valid argument for B irrelvant, we must allow this and assume the user knows what they are + * valid argument for B irrelevant, we must allow this and assume the user knows what they are * doing.</p> * * <p>Performing {@link #getResult(boolean)} just after this step will return a compact form of @@ -106,6 +106,7 @@ public final class AnotB<S extends Summary> { * * @param skA The incoming sketch for the first argument, <i>A</i>. */ + @SuppressWarnings("unchecked") public void setA(final Sketch<S> skA) { if (skA == null) { reset(); @@ -116,14 +117,23 @@ public final class AnotB<S extends Summary> { return; } //skA is not empty - empty_ = false; - thetaLong_ = skA.getThetaLong(); //process A + empty_ = false; + thetaLong_ = skA.getThetaLong(); final DataArrays<S> da = getDataArraysA(skA); + hashArr_ = da.hashArr; - summaryArr_ = da.summaryArr; + hashArr_ = (hashArr_ == null) ? new long[0] : hashArr_; curCount_ = hashArr_.length; + + summaryArr_ = da.summaryArr; + if (summaryArr_ == null) { + final SummaryFactory<S> sumFact = ((QuickSelectSketch<S>)skA).getSummaryFactory(); + final S summary = sumFact.newSummary(); + final Class<S> summaryType = (Class<S>)summary.getClass(); + summaryArr_ = (S[]) Array.newInstance(summaryType, 0); + } } /** @@ -133,7 +143,7 @@ public final class AnotB<S extends Summary> { * * <p>An input argument of null or empty is ignored.</p> * - * <p>Rationale: A <i>null</i> for the second or following arguments is more tollerable because + * <p>Rationale: A <i>null</i> for the second or following arguments is more tolerable because * <i>A NOT null</i> is still <i>A</i> even if we don't know exactly what the null represents. It * clearly does not have any content that overlaps with <i>A</i>. Also, because this can be part of * a multistep operation with multiple <i>notB</i> steps. Other following steps can still produce @@ -143,18 +153,28 @@ public final class AnotB<S extends Summary> { * * @param skB The incoming Tuple sketch for the second (or following) argument <i>B</i>. */ + @SuppressWarnings("unchecked") public void notB(final Sketch<S> skB) { - if (empty_ || skB == null || skB.isEmpty() || hashArr_ == null) { return; } + if (empty_ || skB == null || skB.isEmpty()) { return; } //skB is not empty final long thetaLongB = skB.getThetaLong(); thetaLong_ = Math.min(thetaLong_, thetaLongB); //process B final DataArrays<S> daB = getResultArraysTuple(thetaLong_, curCount_, hashArr_, summaryArr_, skB); + hashArr_ = daB.hashArr; + hashArr_ = (hashArr_ == null) ? new long[0] : hashArr_; + curCount_ = hashArr_.length; + summaryArr_ = daB.summaryArr; + if (summaryArr_ == null) { + final SummaryFactory<S> sumFact = ((QuickSelectSketch<S>)skB).getSummaryFactory(); + final S summary = sumFact.newSummary(); + final Class<S> summaryType = (Class<S>)summary.getClass(); + summaryArr_ = (S[]) Array.newInstance(summaryType, 0); + } - curCount_ = hashArr_.length; empty_ = curCount_ == 0 && thetaLong_ == Long.MAX_VALUE; } @@ -167,7 +187,7 @@ public final class AnotB<S extends Summary> { * * <p>An input argument of null or empty is ignored.</p> * - * <p>Rationale: A <i>null</i> for the second or following arguments is more tollerable because + * <p>Rationale: A <i>null</i> for the second or following arguments is more tolerable because * <i>A NOT null</i> is still <i>A</i> even if we don't know exactly what the null represents. It * clearly does not have any content that overlaps with <i>A</i>. Also, because this can be part of * a multistep operation with multiple <i>notB</i> steps. Other following steps can still produce @@ -185,15 +205,18 @@ public final class AnotB<S extends Summary> { //process B final DataArrays<S> daB = getResultArraysTheta(thetaLong_, curCount_, hashArr_, summaryArr_, skB); + hashArr_ = daB.hashArr; - summaryArr_ = daB.summaryArr; + hashArr_ = (hashArr_ == null) ? new long[0] : hashArr_; + curCount_ = hashArr_.length; + summaryArr_ = daB.summaryArr; curCount_ = hashArr_.length; empty_ = curCount_ == 0 && thetaLong_ == Long.MAX_VALUE; } /** - * Gets the result of the mutistep, stateful operation AnotB that have been executed with calls + * Gets the result of the multistep, stateful operation AnotB that have been executed with calls * to {@link #setA(Sketch)} and ({@link #notB(Sketch)} or * {@link #notB(org.apache.datasketches.theta.Sketch)}). * @@ -235,25 +258,40 @@ public final class AnotB<S extends Summary> { * @param <S> Type of Summary * @return the result as an unordered {@link CompactSketch} */ + @SuppressWarnings("unchecked") public static <S extends Summary> CompactSketch<S> aNotB(final Sketch<S> skA, final Sketch<S> skB) { if (skA == null || skB == null) { throw new SketchesArgumentException("Neither argument may be null"); } - if (skA.getRetainedEntries() == 0) { return skA.compact(); } - if (skB.getRetainedEntries() == 0) { return skA.compact(); } - //Both skA & skB are not empty + //Both skA & skB are not null + + final long minThetaLong = Math.min(skA.getThetaLong(), skB.getThetaLong()); + + if (skA.isEmpty()) { return skA.compact(); } + if (skB.isEmpty() && skB.getRetainedEntries() == 0) { return skA.compact(); } + //Both skA & skB are not empty, and skB has valid entries //Process A final DataArrays<S> da = getDataArraysA(skA); - final long[] hashArrA = da.hashArr; - final S[] summaryArrA = da.summaryArr; + long[] hashArrA = da.hashArr; + hashArrA = (hashArrA == null) ? new long[0] : hashArrA; final int countA = hashArrA.length; + S[] summaryArrA = da.summaryArr; + if (summaryArrA == null) { + final SummaryFactory<S> sumFact = ((QuickSelectSketch<S>)skA).getSummaryFactory(); + final S summary = sumFact.newSummary(); + final Class<S> summaryType = (Class<S>)summary.getClass(); + summaryArrA = (S[]) Array.newInstance(summaryType, 0); + } + + if (countA == 0) { + return new CompactSketch<S>(new long[0], summaryArrA, minThetaLong, false); + } + //Process B - final long minThetaLong = Math.min(skA.getThetaLong(), skB.getThetaLong()); final DataArrays<S> daB = getResultArraysTuple(minThetaLong, countA, hashArrA, summaryArrA, skB); - final long[] hashArr = daB.hashArr; final S[] summaryArr = daB.summaryArr; final int curCountOut = hashArr.length; @@ -287,6 +325,7 @@ public final class AnotB<S extends Summary> { * @param <S> Type of Summary * @return the result as an unordered {@link CompactSketch} */ + @SuppressWarnings("unchecked") public static <S extends Summary> CompactSketch<S> aNotB(final Sketch<S> skA, final org.apache.datasketches.theta.Sketch skB) { if (skA == null || skB == null) { @@ -294,19 +333,33 @@ public final class AnotB<S extends Summary> { } //Both skA & skB are not null - if (skA.getRetainedEntries() == 0) { return skA.compact(); } - if (skB.getRetainedEntries() == 0) { return skA.compact(); } - //Both skA & skB have valid retained entries, and are not empty + final long minThetaLong = Math.min(skA.getThetaLong(), skB.getThetaLong()); + + if (skA.isEmpty()) { return skA.compact(); } + if (skB.isEmpty() && skB.getRetainedEntries() == 0) { return skA.compact(); } + //Both skA & skB are not empty, and skB has valid entries + //Process A final DataArrays<S> da = getDataArraysA(skA); - final long[] hashArrA = da.hashArr; - final S[] summaryArrA = da.summaryArr; + long[] hashArrA = da.hashArr; + hashArrA = (hashArrA == null) ? new long[0] : hashArrA; final int countA = hashArrA.length; + S[] summaryArrA = da.summaryArr; + if (summaryArrA == null) { + final SummaryFactory<S> sumFact = ((QuickSelectSketch<S>)skA).getSummaryFactory(); + final S summary = sumFact.newSummary(); + final Class<S> summaryType = (Class<S>)summary.getClass(); + summaryArrA = (S[]) Array.newInstance(summaryType, 0); + } + + if (countA == 0) { + return new CompactSketch<S>(new long[0], summaryArrA, minThetaLong, false); + } + //Process B - final long minThetaLong = Math.min(skA.getThetaLong(), skB.getThetaLong()); - final DataArrays<S> daB = getResultArraysTheta(minThetaLong, countA, hashArrA, summaryArrA, skB); + final DataArrays<S> daB = getResultArraysTheta(minThetaLong, countA, hashArrA, summaryArrA, skB); final long[] hashArr = daB.hashArr; final S[] summaryArr = daB.summaryArr; final int countOut = hashArr.length; diff --git a/src/main/java/org/apache/datasketches/tuple/Intersection.java b/src/main/java/org/apache/datasketches/tuple/Intersection.java index 9494580..8c047a9 100644 --- a/src/main/java/org/apache/datasketches/tuple/Intersection.java +++ b/src/main/java/org/apache/datasketches/tuple/Intersection.java @@ -107,14 +107,19 @@ public class Intersection<S extends Summary> { if (tupleSketch == null) { throw new SketchesArgumentException("Sketch must not be null"); } final boolean firstCall = firstCall_; firstCall_ = false; + final boolean emptyIn = tupleSketch.isEmpty(); + if (empty_ || emptyIn) { //empty rule + //Because of the definition of null above and the Empty Rule (which is OR), empty_ must be true. + //Whatever the current internal state, we make our local empty. + resetToEmpty(); + return; + } // input sketch could be first or next call final long thetaLongIn = tupleSketch.getThetaLong(); final int countIn = tupleSketch.getRetainedEntries(); thetaLong_ = min(thetaLong_, thetaLongIn); //Theta rule - // Empty rule extended in case incoming sketch does not have empty bit properly set - final boolean emptyIn = countIn == 0 && thetaLongIn == Long.MAX_VALUE; - empty_ |= emptyIn; //empty rule + if (countIn == 0) { hashTables_.clear(); return; @@ -274,12 +279,23 @@ public class Intersection<S extends Summary> { * Resets the internal set to the initial state, which represents the Universal Set */ public void reset() { + hardReset(); + } + + private void hardReset() { empty_ = false; thetaLong_ = Long.MAX_VALUE; hashTables_.clear(); firstCall_ = true; } + private void resetToEmpty() { + empty_ = true; + thetaLong_ = Long.MAX_VALUE; + hashTables_.clear(); + firstCall_ = false; + } + static int getLgTableSize(final int count) { final int tableSize = max(ceilingPowerOf2((int) ceil(count / 0.75)), 1 << MIN_LG_NOM_LONGS); return Integer.numberOfTrailingZeros(tableSize); diff --git a/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java b/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java index fd56b06..f80d6e9 100644 --- a/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java +++ b/src/main/java/org/apache/datasketches/tuple/QuickSelectSketch.java @@ -292,7 +292,8 @@ class QuickSelectSketch<S extends Summary> extends Sketch<S> { @SuppressWarnings("unchecked") public CompactSketch<S> compact() { if (getRetainedEntries() == 0) { - return new CompactSketch<>(null, null, thetaLong_, empty_); + if (empty_) { return new CompactSketch<>(null, null, Long.MAX_VALUE, true); } + return new CompactSketch<>(null, null, thetaLong_, false); } final long[] hashArr = new long[getRetainedEntries()]; final S[] summaryArr = (S[]) diff --git a/src/test/java/org/apache/datasketches/theta/CornerCaseThetaSetOperationsTest.java b/src/test/java/org/apache/datasketches/theta/CornerCaseThetaSetOperationsTest.java new file mode 100644 index 0000000..6a09c88 --- /dev/null +++ b/src/test/java/org/apache/datasketches/theta/CornerCaseThetaSetOperationsTest.java @@ -0,0 +1,679 @@ +/* + * 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.datasketches.theta; + +import static org.apache.datasketches.Util.DEFAULT_UPDATE_SEED; +import static org.apache.datasketches.hash.MurmurHash3.hash; + +import org.testng.annotations.Test; + +public class CornerCaseThetaSetOperationsTest { + + /* Hash Values + * 9223372036854775807 Theta = 1.0 + * + * 6730918654704304314 hash(3L)[0] >>> 1 GT_MIDP + * 4611686018427387904 Theta for p = 0.5f = MIDP + * 2206043092153046979 hash(2L)[0] >>> 1 LT_MIDP_V + * 1498732507761423037 hash(5L)[0] >>> 1 LTLT_MIDP_V + * + * 1206007004353599230 hash(6L)[0] >>> 1 GT_LOWP_V + * 922337217429372928 Theta for p = 0.1f = LOWP + * 593872385995628096 hash(4L)[0] >>> 1 LT_LOWP_V + * 405753591161026837 hash(1L)[0] >>> 1 LTLT_LOWP_V + + */ + //private static final long + + private static final long GT_MIDP_V = 3L; + private static final float MIDP = 0.5f; + private static final long LT_MIDP_V = 2L; + //private static final long LTLT_MIDP_V = 5L; + + private static final long GT_LOWP_V = 6L; + private static final float LOWP = 0.1f; + private static final long LT_LOWP_V = 4L; + //private static final long VALUE_1 = 1L; + + + private static final double MIDP_THETA = MIDP; + private static final double LOWP_THETA = LOWP; + + + enum SkType { + NEW, //{ 1.0, 0, T} Bin: 101 Oct: 05 + EXACT, //{ 1.0, >0, F} Bin: 111 Oct: 07, specify only value + ESTIMATION, //{<1.0, >0, F} Bin: 010 Oct: 02, specify only value + NEW_DEGEN, //{<1.0, 0, T} Bin: 001 Oct: 01, specify only p + RESULT_DEGEN //{<1.0, 0, F} Bin: 000 Oct: 0, specify p, value + } + + //NOTE: 0 values in getSketch are not used. + + @Test + public void newNew() { + UpdateSketch ska = getSketch(SkType.NEW, 0, 0); + UpdateSketch skb = getSketch(SkType.NEW, 0, 0); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + + } + + @Test + public void newExact() { + UpdateSketch ska = getSketch(SkType.NEW, 0, 0); + UpdateSketch skb = getSketch(SkType.EXACT, 0, GT_MIDP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + } + + @Test + public void newNewDegen() { + UpdateSketch ska = getSketch(SkType.NEW, 0, 0); + UpdateSketch skb = getSketch(SkType.NEW_DEGEN, LOWP, 0); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + } + + @Test + public void newResultDegen() { + UpdateSketch ska = getSketch(SkType.NEW, 0, 0); + UpdateSketch skb = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + } + + @Test + public void newNewEstimation() { + UpdateSketch ska = getSketch(SkType.NEW, 0, 0); + UpdateSketch skb = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + } + + /*********************/ + + @Test + public void exactNew() { + UpdateSketch ska = getSketch(SkType.EXACT, 0, GT_MIDP_V); + UpdateSketch skb = getSketch(SkType.NEW, 0, 0); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 1, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 1, false); + } + + @Test + public void exactExact() { + UpdateSketch ska = getSketch(SkType.EXACT, 0, GT_MIDP_V); + UpdateSketch skb = getSketch(SkType.EXACT, 0, GT_MIDP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 1, false); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + } + + @Test + public void exactNewDegen() { + UpdateSketch ska = getSketch(SkType.EXACT, 0, LT_LOWP_V); + UpdateSketch skb = getSketch(SkType.NEW_DEGEN, LOWP, 0); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 1, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 1, false); + } + + @Test + public void exactResultDegen() { + UpdateSketch ska = getSketch(SkType.EXACT, 0, LT_LOWP_V); + UpdateSketch skb = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); //entries = 0 + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 0, false); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, LOWP_THETA, 1, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, LOWP_THETA, 1, false); + } + + @Test + public void exactEstimation() { + UpdateSketch ska = getSketch(SkType.EXACT, 0, LT_LOWP_V); + UpdateSketch skb = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 1, false); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, LOWP_THETA, 0, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, LOWP_THETA, 0, false); + } + + /*********************/ + + @Test + public void estimationNew() { + UpdateSketch ska = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + UpdateSketch skb = getSketch(SkType.NEW, 0, 0); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, LOWP_THETA, 1, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, LOWP_THETA, 1, false); + } + + @Test + public void estimationExact() { + UpdateSketch ska = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + UpdateSketch skb = getSketch(SkType.EXACT, 0, LT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 1, false); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, LOWP_THETA, 0, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, LOWP_THETA, 0, false); + } + + @Test + public void estimationNewDegen() { + UpdateSketch ska = getSketch(SkType.ESTIMATION, MIDP, LT_MIDP_V); + UpdateSketch skb = getSketch(SkType.NEW_DEGEN, LOWP, 0); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, MIDP_THETA, 1, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, MIDP_THETA, 1, false); + } + + @Test + public void estimationResultDegen() { + UpdateSketch ska = getSketch(SkType.ESTIMATION, MIDP, LT_LOWP_V); + UpdateSketch skb = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 0, false); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, LOWP_THETA, 1, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, LOWP_THETA, 1, false); + } + + @Test + public void estimationEstimation() { + UpdateSketch ska = getSketch(SkType.ESTIMATION, MIDP, LT_LOWP_V); + UpdateSketch skb = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 1, false); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, LOWP_THETA, 0, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, LOWP_THETA, 0, false); + } + + /*********************/ + + @Test + public void newDegenNew() { + UpdateSketch ska = getSketch(SkType.NEW_DEGEN, LOWP, 0); + UpdateSketch skb = getSketch(SkType.NEW, 0, 0); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + } + + @Test + public void newDegenExact() { + UpdateSketch ska = getSketch(SkType.NEW_DEGEN, LOWP,0); + UpdateSketch skb = getSketch(SkType.EXACT, 0, LT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + } + + @Test + public void newDegenNewDegen() { + UpdateSketch ska = getSketch(SkType.NEW_DEGEN, MIDP, 0); + UpdateSketch skb = getSketch(SkType.NEW_DEGEN, LOWP, 0); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + } + + @Test + public void newDegenResultDegen() { + UpdateSketch ska = getSketch(SkType.NEW_DEGEN, MIDP, 0); + UpdateSketch skb = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + } + + @Test + public void newDegenEstimation() { + UpdateSketch ska = getSketch(SkType.NEW_DEGEN, MIDP, 0); + UpdateSketch skb = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, 1.0, 0, true); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, 1.0, 0, true); + } + + /*********************/ + + @Test + public void resultDegenNew() { + UpdateSketch ska = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); //entries = 0 + UpdateSketch skb = getSketch(SkType.NEW, 0, 0); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, LOWP_THETA, 0, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, LOWP_THETA, 0, false); + } + + @Test + public void resultDegenExact() { + UpdateSketch ska = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); //entries = 0 + UpdateSketch skb = getSketch(SkType.EXACT, 0, LT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 0, false); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, LOWP_THETA, 0, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, LOWP_THETA, 0, false); + } + + @Test + public void resultDegenNewDegen() { + UpdateSketch ska = getSketch(SkType.RESULT_DEGEN, MIDP, GT_MIDP_V); //entries = 0 + UpdateSketch skb = getSketch(SkType.NEW_DEGEN, LOWP, 0); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, MIDP_THETA, 0, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, MIDP_THETA, 0, false); + } + + @Test + public void resultDegenResultDegen() { + UpdateSketch ska = getSketch(SkType.RESULT_DEGEN, MIDP, GT_MIDP_V); //entries = 0 + UpdateSketch skb = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 0, false); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, LOWP_THETA, 0, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, LOWP_THETA, 0, false); + } + + @Test + public void resultDegenEstimation() { + UpdateSketch ska = getSketch(SkType.RESULT_DEGEN, MIDP, GT_MIDP_V); //entries = 0 + UpdateSketch skb = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + + //Stateless + Intersection inter = SetOperation.builder().buildIntersection(); + CompactSketch csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 0, false); + + AnotB anotb = SetOperation.builder().buildANotB(); + csk = anotb.aNotB(ska, skb); + checkResult("AnotB Stateless", csk, LOWP_THETA, 0, false); + + //Stateful AnotB + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful", csk, LOWP_THETA, 0, false); + } + + //================================= + + private static void checkResult(String comment, CompactSketch sk, double theta, int entries, boolean empty) { + double skTheta = sk.getTheta(); + int skEntries = sk.getRetainedEntries(); + boolean skEmpty = sk.isEmpty(); + + boolean thetaOk = skTheta == theta; + boolean entriesOk = skEntries == entries; + boolean emptyOk = skEmpty == empty; + if (!thetaOk || !entriesOk || !emptyOk) { + StringBuilder sb = new StringBuilder(); + sb.append(comment + ": "); + if (!thetaOk) { sb.append("Got: " + skTheta + ", Expected: " + theta + "; "); } + if (!entriesOk) { sb.append("Got: " + skEntries + ", Expected: " + entries + "; "); } + if (!emptyOk) { sb.append("Got: " + skEmpty + ", Expected: " + empty + "."); } + throw new IllegalArgumentException(sb.toString()); + } + } + + private static UpdateSketch getSketch(SkType skType, float p, long value) { + UpdateSketchBuilder bldr = UpdateSketch.builder(); + bldr.setLogNominalEntries(4); + UpdateSketch sk; + switch(skType) { + case NEW: { //{ 1.0, 0, T} Bin: 101 Oct: 05 + sk = bldr.build(); + break; + } + case EXACT: { //{ 1.0, >0, F} Bin: 111 Oct: 07 + sk = bldr.build(); + sk.update(value); + break; + } + case ESTIMATION: { //{<1.0, >0, F} Bin: 010 Oct: 02 + bldr.setP(p); + sk = bldr.build(); + sk.update(value); + break; + } + case NEW_DEGEN: { //{<1.0, 0, T} Bin: 001 Oct: 01 + bldr.setP(p); + sk = bldr.build(); + break; + } + case RESULT_DEGEN: { //{<1.0, 0, F} Bin: 000 Oct: 0 + bldr.setP(p); + sk = bldr.build(); + sk.update(value); + break; + } + + default: { return null; } //should not happen + } + return sk; + } + + private static void println(Object o) { + System.out.println(o.toString()); + } + + //@Test + public void printHash() { + long seed = DEFAULT_UPDATE_SEED; + long v = 6; + long hash = (hash(v, seed)[0]) >>> 1; + println(v + ", " + hash); + } + + //@Test + public void printPAsLong() { + float p = 0.5f; + println("p = " + p + ", " + (long)(Long.MAX_VALUE * p)); + } + +} diff --git a/src/test/java/org/apache/datasketches/tuple/aninteger/CornerCaseTupleSetOperationsTest.java b/src/test/java/org/apache/datasketches/tuple/aninteger/CornerCaseTupleSetOperationsTest.java new file mode 100644 index 0000000..4cfd2b6 --- /dev/null +++ b/src/test/java/org/apache/datasketches/tuple/aninteger/CornerCaseTupleSetOperationsTest.java @@ -0,0 +1,659 @@ +/* + * 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.datasketches.tuple.aninteger; + +import org.apache.datasketches.tuple.AnotB; +import org.apache.datasketches.tuple.CompactSketch; +import org.apache.datasketches.tuple.Intersection; +import org.testng.annotations.Test; + +public class CornerCaseTupleSetOperationsTest { + + /* Hash Values + * 9223372036854775807 Theta = 1.0 + * + * 6730918654704304314 hash(3L)[0] >>> 1 GT_MIDP + * 4611686018427387904 Theta for p = 0.5f = MIDP + * 2206043092153046979 hash(2L)[0] >>> 1 LT_MIDP_V + * 1498732507761423037 hash(5L)[0] >>> 1 LTLT_MIDP_V + * + * 1206007004353599230 hash(6L)[0] >>> 1 GT_LOWP_V + * 922337217429372928 Theta for p = 0.1f = LOWP + * 593872385995628096 hash(4L)[0] >>> 1 LT_LOWP_V + * 405753591161026837 hash(1L)[0] >>> 1 LTLT_LOWP_V + + */ + //private static final long + + private static final long GT_MIDP_V = 3L; + private static final float MIDP = 0.5f; + private static final long LT_MIDP_V = 2L; + //private static final long LTLT_MIDP_V = 5L; + + private static final long GT_LOWP_V = 6L; + private static final float LOWP = 0.1f; + private static final long LT_LOWP_V = 4L; + //private static final long VALUE_1 = 1L; + + + private static final double MIDP_THETA = MIDP; + private static final double LOWP_THETA = LOWP; + + IntegerSummarySetOperations setOperations = + new IntegerSummarySetOperations(IntegerSummary.Mode.Min, IntegerSummary.Mode.Min); + Intersection<IntegerSummary> intersection = new Intersection<>(setOperations); + + enum SkType { + NEW, //{ 1.0, 0, T} Bin: 101 Oct: 05 + EXACT, //{ 1.0, >0, F} Bin: 111 Oct: 07, specify only value + ESTIMATION, //{<1.0, >0, F} Bin: 010 Oct: 02, specify only value + NEW_DEGEN, //{<1.0, 0, T} Bin: 001 Oct: 01, specify only p + RESULT_DEGEN //{<1.0, 0, F} Bin: 000 Oct: 0, specify p, value + } + + //NOTE: 0 values in getSketch are not used. + + @Test + public void newNew() { + IntegerSketch ska = getSketch(SkType.NEW, 0, 0); + IntegerSketch skb = getSketch(SkType.NEW, 0, 0); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + @Test + public void newExact() { + IntegerSketch ska = getSketch(SkType.NEW, 0, 0); + IntegerSketch skb = getSketch(SkType.EXACT, 0, GT_MIDP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + @Test + public void newNewDegen() { + IntegerSketch ska = getSketch(SkType.NEW, 0, 0); + IntegerSketch skb = getSketch(SkType.NEW_DEGEN, LOWP, 0); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + @Test + public void newResultDegen() { + IntegerSketch ska = getSketch(SkType.NEW, 0, 0); + IntegerSketch skb = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + @Test + public void newNewEstimation() { + IntegerSketch ska = getSketch(SkType.NEW, 0, 0); + IntegerSketch skb = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + /*********************/ + + @Test + public void exactNew() { + IntegerSketch ska = getSketch(SkType.EXACT, 0, GT_MIDP_V); + IntegerSketch skb = getSketch(SkType.NEW, 0, 0); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 1, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 1, false); + } + + @Test + public void exactExact() { + IntegerSketch ska = getSketch(SkType.EXACT, 0, GT_MIDP_V); + IntegerSketch skb = getSketch(SkType.EXACT, 0, GT_MIDP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 1, false); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + @Test + public void exactNewDegen() { + IntegerSketch ska = getSketch(SkType.EXACT, 0, LT_LOWP_V); + IntegerSketch skb = getSketch(SkType.NEW_DEGEN, LOWP, 0); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 1, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 1, false); + } + + @Test + public void exactResultDegen() { //AnotB: 1.0 != 0.10000000149011612; + IntegerSketch ska = getSketch(SkType.EXACT, 0, LT_LOWP_V); + IntegerSketch skb = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); //entries = 0 + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 0, false); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 1, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 1, false); + } + + @Test + public void exactEstimation() { + IntegerSketch ska = getSketch(SkType.EXACT, 0, LT_LOWP_V); + IntegerSketch skb = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 1, false); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + } + + /*********************/ + + @Test + public void estimationNew() { + IntegerSketch ska = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + IntegerSketch skb = getSketch(SkType.NEW, 0, 0); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 1, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 1, false); + } + + @Test + public void estimationExact() { + IntegerSketch ska = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + IntegerSketch skb = getSketch(SkType.EXACT, 0, LT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 1, false); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + } + + @Test + public void estimationNewDegen() { + IntegerSketch ska = getSketch(SkType.ESTIMATION, MIDP, LT_MIDP_V); + IntegerSketch skb = getSketch(SkType.NEW_DEGEN, LOWP, 0); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, MIDP_THETA, 1, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, MIDP_THETA, 1, false); + } + + @Test + public void estimationResultDegen() { + IntegerSketch ska = getSketch(SkType.ESTIMATION, MIDP, LT_LOWP_V); + IntegerSketch skb = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 0, false); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 1, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 1, false); + } + + @Test + public void estimationEstimation() { + IntegerSketch ska = getSketch(SkType.ESTIMATION, MIDP, LT_LOWP_V); + IntegerSketch skb = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 1, false); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + } + + /*********************/ + + @Test + public void newDegenNew() {//AnotB: 0.10000000149011612 != 1.0; + IntegerSketch ska = getSketch(SkType.NEW_DEGEN, LOWP, 0); + IntegerSketch skb = getSketch(SkType.NEW, 0, 0); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + @Test + public void newDegenExact() { //AnotB: 0.10000000149011612 != 1.0; + IntegerSketch ska = getSketch(SkType.NEW_DEGEN, LOWP,0); + IntegerSketch skb = getSketch(SkType.EXACT, 0, LT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + @Test + public void newDegenNewDegen() { //AnotB: 0.10000000149011612 != 1.0; + IntegerSketch ska = getSketch(SkType.NEW_DEGEN, MIDP, 0); + IntegerSketch skb = getSketch(SkType.NEW_DEGEN, LOWP, 0); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + @Test + public void newDegenResultDegen() { //AnotB: 0.10000000149011612 != 1.0; + IntegerSketch ska = getSketch(SkType.NEW_DEGEN, MIDP, 0); + IntegerSketch skb = getSketch(SkType.RESULT_DEGEN, LOWP,GT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + @Test + public void newDegenEstimation() { //AnotB: 0.10000000149011612 != 1.0; + IntegerSketch ska = getSketch(SkType.NEW_DEGEN, MIDP, 0); + IntegerSketch skb =getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, 1.0, 0, true); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateful Tuple, Tuple", csk, 1.0, 0, true); + } + + /*********************/ + + @Test + public void resultDegenNew() { + IntegerSketch ska = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); //entries = 0 + IntegerSketch skb = getSketch(SkType.NEW, 0, 0); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + } + + @Test + public void resultDegenExact() { + IntegerSketch ska = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); //entries = 0 + IntegerSketch skb = getSketch(SkType.EXACT, 0, LT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 0, false); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + } + + @Test + public void resultDegenNewDegen() { + IntegerSketch ska = getSketch(SkType.RESULT_DEGEN, MIDP, GT_MIDP_V); //entries = 0 + IntegerSketch skb = getSketch(SkType.NEW_DEGEN, LOWP, 0); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, 1.0, 0, true); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, MIDP_THETA, 0, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, MIDP_THETA, 0, false); + } + + @Test + public void resultDegenResultDegen() { //AnotB NullPointerException + IntegerSketch ska = getSketch(SkType.RESULT_DEGEN, MIDP, GT_MIDP_V); //entries = 0 + IntegerSketch skb = getSketch(SkType.RESULT_DEGEN, LOWP, GT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 0, false); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + } + + @Test + public void resultDegenEstimation() { + IntegerSketch ska = getSketch(SkType.RESULT_DEGEN, MIDP, GT_MIDP_V); //entries = 0 + IntegerSketch skb = getSketch(SkType.ESTIMATION, LOWP, LT_LOWP_V); + + //Stateless Tuple, Tuple + Intersection<IntegerSummary> inter = new Intersection<>(setOperations); + CompactSketch<IntegerSummary> csk = inter.intersect(ska, skb); + checkResult("Intersect", csk, LOWP_THETA, 0, false); + + csk = AnotB.aNotB(ska, skb); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + + //Stateful Tuple, Tuple + AnotB<IntegerSummary> anotb = new AnotB<>(); + anotb.setA(ska); + anotb.notB(skb); + csk = anotb.getResult(true); + checkResult("AnotB Stateless Tuple, Tuple", csk, LOWP_THETA, 0, false); + } + + //================================= + + private static void checkResult(String comment, CompactSketch<IntegerSummary> sk, double theta, int entries, boolean empty) { + double skTheta = sk.getTheta(); + int skEntries = sk.getRetainedEntries(); + boolean skEmpty = sk.isEmpty(); + + boolean thetaOk = skTheta == theta; + boolean entriesOk = skEntries == entries; + boolean emptyOk = skEmpty == empty; + if (!thetaOk || !entriesOk || !emptyOk) { + StringBuilder sb = new StringBuilder(); + sb.append(comment + ": "); + if (!thetaOk) { sb.append("Got: " + skTheta + ", Expected: " + theta + "; "); } + if (!entriesOk) { sb.append("Got: " + skEntries + ", Expected: " + entries + "; "); } + if (!emptyOk) { sb.append("Got: " + skEmpty + ", Expected: " + empty + "."); } + throw new IllegalArgumentException(sb.toString()); + } + } + + private static IntegerSketch getSketch(SkType skType, float p, long value) { + + IntegerSketch sk; + switch(skType) { + case NEW: { //{ 1.0, 0, T} Bin: 101 Oct: 05 + sk = new IntegerSketch(4, 2, 1.0f, IntegerSummary.Mode.Min); + break; + } + case EXACT: { //{ 1.0, >0, F} Bin: 111 Oct: 07 + sk = new IntegerSketch(4, 2, 1.0f, IntegerSummary.Mode.Min); + sk.update(value, 1); + break; + } + case ESTIMATION: { //{<1.0, >0, F} Bin: 010 Oct: 02 + sk = new IntegerSketch(4, 2, p, IntegerSummary.Mode.Min); + sk.update(value, 1); + break; + } + case NEW_DEGEN: { //{<1.0, 0, T} Bin: 001 Oct: 01 + sk = new IntegerSketch(4, 2, p, IntegerSummary.Mode.Min); + break; + } + case RESULT_DEGEN: { //{<1.0, 0, F} Bin: 000 Oct: 0 + sk = new IntegerSketch(4, 2, p, IntegerSummary.Mode.Min); + sk.update(value, 1); // > theta + break; + } + + default: { return null; } //should not happen + } + return sk; + } + +} --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
