You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by le...@apache.org on 2019/08/26 01:05:59 UTC
[incubator-datasketches-java] branch BkwardCompat created (now
a0888e9)
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a change to branch BkwardCompat
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git.
at a0888e9 More Unit tests. Fine tuning of union merge operations and Pairwise Set Operations.
This branch includes the following new commits:
new e163165 spelling.
new 2cee6fe Added EmptyCompactSketch.
new da6bada Fix bugs in test
new 98801f0 Update unit tests
new de94a10 Merge branch 'master' into BkwardCompat
new 48fbc16 remove comment
new a0888e9 More Unit tests. Fine tuning of union merge operations and Pairwise Set Operations.
The 7 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 05/07: Merge branch 'master' into
BkwardCompat
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch BkwardCompat
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit de94a102dad1107d422a7ce8c49feedad79dfd9a
Merge: 98801f0 0ba8f4c
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Thu Aug 22 22:12:54 2019 -0700
Merge branch 'master' into BkwardCompat
src/main/java/com/yahoo/sketches/tuple/AnotB.java | 2 +-
.../tuple/ArrayOfDoublesSetOperationBuilder.java | 4 +-
.../yahoo/sketches/tuple/ArrayOfDoublesUnion.java | 86 +++++--------------
.../sketches/tuple/DirectArrayOfDoublesUnion.java | 37 +++++++--
.../sketches/tuple/HeapArrayOfDoublesAnotB.java | 26 +++---
.../sketches/tuple/HeapArrayOfDoublesUnion.java | 22 +----
.../sketches/tuple/SerializerDeserializer.java | 31 -------
.../sketches/tuple/ArrayOfDoublesAnotBTest.java | 36 ++++++++
.../sketches/tuple/ArrayOfDoublesUnionTest.java | 96 +++++++++++++++++-----
.../yahoo/sketches/tuple/ReadOnlyMemoryTest.java | 17 ----
.../UpdatableSketchWithDoubleSummaryTest.java | 40 ++++++++-
11 files changed, 223 insertions(+), 174 deletions(-)
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 01/07: spelling.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch BkwardCompat
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit e16316542af4f318010e066a52f18c71b6393415
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Tue Aug 13 10:52:40 2019 -0700
spelling.
---
src/main/java/com/yahoo/sketches/theta/UnionImpl.java | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/main/java/com/yahoo/sketches/theta/UnionImpl.java b/src/main/java/com/yahoo/sketches/theta/UnionImpl.java
index 3b74801..9a4e6c2 100644
--- a/src/main/java/com/yahoo/sketches/theta/UnionImpl.java
+++ b/src/main/java/com/yahoo/sketches/theta/UnionImpl.java
@@ -310,7 +310,7 @@ final class UnionImpl extends Union {
final long hashIn = cacheIn[i];
if ((hashIn <= 0L) || (hashIn >= unionThetaLong_)) { continue; } //rejects dirty values
gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
- c++; //insures against invalid state inside the incoming sketch
+ c++; //ensures against invalid state inside the incoming sketch
}
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 02/07: Added EmptyCompactSketch.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch BkwardCompat
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit 2cee6feaff2964ad36aa4ce9c6c5c98da0f945b4
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Thu Aug 22 09:47:41 2019 -0700
Added EmptyCompactSketch.
Improved backward compatibility detection and handling. Refactored
testing of older serialization versions. Combined and simplified a
number of internal methods.
---
src/main/java/com/yahoo/sketches/Util.java | 3 +-
.../sketches/theta/DirectCompactOrderedSketch.java | 25 +-
.../theta/DirectCompactUnorderedSketch.java | 28 +-
.../sketches/theta/DirectQuickSelectSketchR.java | 4 +-
.../yahoo/sketches/theta/EmptyCompactSketch.java | 133 ++++++++++
.../yahoo/sketches/theta/ForwardCompatibility.java | 121 ++++++---
.../java/com/yahoo/sketches/theta/HeapAnotB.java | 22 +-
.../sketches/theta/HeapCompactOrderedSketch.java | 31 +--
.../sketches/theta/HeapCompactUnorderedSketch.java | 52 +---
.../com/yahoo/sketches/theta/Intersection.java | 6 +-
.../com/yahoo/sketches/theta/IntersectionImpl.java | 11 +-
.../sketches/theta/PairwiseSetOperations.java | 61 +++--
.../com/yahoo/sketches/theta/PreambleUtil.java | 15 +-
.../com/yahoo/sketches/theta/SetOperation.java | 44 ++--
.../com/yahoo/sketches/theta/SingleItemSketch.java | 78 +++---
src/main/java/com/yahoo/sketches/theta/Sketch.java | 106 +++++---
.../java/com/yahoo/sketches/theta/UnionImpl.java | 59 +++--
.../com/yahoo/sketches/theta/UpdateSketch.java | 94 +++++--
.../yahoo/sketches/theta/BackwardConversions.java | 232 +++++++++++++++++
.../yahoo/sketches/theta/CompactSketchTest.java | 287 ++++++++++-----------
.../ConcurrentDirectQuickSelectSketchTest.java | 4 +-
.../theta/ConcurrentHeapQuickSelectSketchTest.java | 12 +-
.../theta/DirectQuickSelectSketchTest.java | 4 +-
.../com/yahoo/sketches/theta/DirectUnionTest.java | 105 +++-----
.../java/com/yahoo/sketches/theta/EmptyTest.java | 48 +++-
.../sketches/theta/ForwardCompatibilityTest.java | 242 +++--------------
.../yahoo/sketches/theta/HeapAlphaSketchTest.java | 6 +-
.../sketches/theta/HeapQuickSelectSketchTest.java | 11 +-
.../com/yahoo/sketches/theta/HeapUnionTest.java | 148 +++++++----
.../sketches/theta/PairwiseCornerCasesTest.java | 72 +++---
.../yahoo/sketches/theta/SingleItemSketchTest.java | 31 ++-
.../java/com/yahoo/sketches/theta/SketchTest.java | 25 +-
.../com/yahoo/sketches/theta/SketchesTest.java | 35 ++-
.../com/yahoo/sketches/theta/UnionImplTest.java | 10 +-
34 files changed, 1266 insertions(+), 899 deletions(-)
diff --git a/src/main/java/com/yahoo/sketches/Util.java b/src/main/java/com/yahoo/sketches/Util.java
index bb05514..3554366 100644
--- a/src/main/java/com/yahoo/sketches/Util.java
+++ b/src/main/java/com/yahoo/sketches/Util.java
@@ -311,7 +311,8 @@ public final class Util {
public static final short checkSeedHashes(final short seedHashA, final short seedHashB) {
if (seedHashA != seedHashB) {
throw new SketchesArgumentException(
- "Incompatible Seed Hashes. " + seedHashA + ", " + seedHashB);
+ "Incompatible Seed Hashes. " + Integer.toHexString(seedHashA & 0XFFFF)
+ + ", " + Integer.toHexString(seedHashB & 0XFFFF));
}
return seedHashA;
}
diff --git a/src/main/java/com/yahoo/sketches/theta/DirectCompactOrderedSketch.java b/src/main/java/com/yahoo/sketches/theta/DirectCompactOrderedSketch.java
index 7973843..93f9e5f 100644
--- a/src/main/java/com/yahoo/sketches/theta/DirectCompactOrderedSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/DirectCompactOrderedSketch.java
@@ -42,7 +42,7 @@ import com.yahoo.memory.WritableMemory;
*/
final class DirectCompactOrderedSketch extends DirectCompactSketch {
- private DirectCompactOrderedSketch(final Memory mem) {
+ DirectCompactOrderedSketch(final Memory mem) {
super(mem);
}
@@ -61,29 +61,6 @@ final class DirectCompactOrderedSketch extends DirectCompactSketch {
}
/**
- * Converts the given UpdateSketch to this compact form.
- * @param sketch the given UpdateSketch
- * @param dstMem the given destination Memory. This clears it before use.
- * @return a DirectCompactOrderedSketch.
- */
- static DirectCompactOrderedSketch compact(final UpdateSketch sketch, final WritableMemory dstMem) {
- final int curCount = sketch.getRetainedEntries(true);
- long thetaLong = sketch.getThetaLong();
- boolean empty = sketch.isEmpty();
- thetaLong = thetaOnCompact(empty, curCount, thetaLong);
- empty = emptyOnCompact(curCount, thetaLong);
- final int preLongs = computeCompactPreLongs(thetaLong, empty, curCount);
- final short seedHash = sketch.getSeedHash();
- final long[] cache = sketch.getCache();
- final int requiredFlags = READ_ONLY_FLAG_MASK | COMPACT_FLAG_MASK | ORDERED_FLAG_MASK;
- final byte flags = (byte) (requiredFlags | (empty ? EMPTY_FLAG_MASK : 0));
- final boolean ordered = true;
- final long[] compactCache = CompactSketch.compactCache(cache, curCount, thetaLong, ordered);
- loadCompactMemory(compactCache, seedHash, curCount, thetaLong, dstMem, flags, preLongs);
- return new DirectCompactOrderedSketch(dstMem);
- }
-
- /**
* Constructs this sketch from correct, valid components.
* @param cache in compact, ordered form
* @param empty The correct <a href="{@docRoot}/resources/dictionary.html#empty">Empty</a>.
diff --git a/src/main/java/com/yahoo/sketches/theta/DirectCompactUnorderedSketch.java b/src/main/java/com/yahoo/sketches/theta/DirectCompactUnorderedSketch.java
index f05b369..c4e77a7 100644
--- a/src/main/java/com/yahoo/sketches/theta/DirectCompactUnorderedSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/DirectCompactUnorderedSketch.java
@@ -41,7 +41,7 @@ import com.yahoo.memory.WritableMemory;
*/
final class DirectCompactUnorderedSketch extends DirectCompactSketch {
- private DirectCompactUnorderedSketch(final Memory mem) {
+ DirectCompactUnorderedSketch(final Memory mem) {
super(mem);
}
@@ -60,30 +60,6 @@ final class DirectCompactUnorderedSketch extends DirectCompactSketch {
}
/**
- * Constructs given an UpdateSketch.
- * @param sketch the given UpdateSketch
- * @param dstMem the given destination Memory. This clears it before use.
- * @return a DirectCompactUnorderedSketch
- */
- static DirectCompactUnorderedSketch compact(final UpdateSketch sketch,
- final WritableMemory dstMem) {
- final int curCount = sketch.getRetainedEntries(true);
- long thetaLong = sketch.getThetaLong();
- boolean empty = sketch.isEmpty();
- thetaLong = thetaOnCompact(empty, curCount, thetaLong);
- empty = emptyOnCompact(curCount, thetaLong);
- final int preLongs = computeCompactPreLongs(thetaLong, empty, curCount);
- final short seedHash = sketch.getSeedHash();
- final long[] cache = sketch.getCache();
- final int requiredFlags = READ_ONLY_FLAG_MASK | COMPACT_FLAG_MASK;
- final byte flags = (byte) (requiredFlags | (empty ? EMPTY_FLAG_MASK : 0));
- final boolean ordered = false;
- final long[] compactCache = CompactSketch.compactCache(cache, curCount, thetaLong, ordered);
- loadCompactMemory(compactCache, seedHash, curCount, thetaLong, dstMem, flags, preLongs);
- return new DirectCompactUnorderedSketch(dstMem);
- }
-
- /**
* Constructs this sketch from correct, valid components.
* @param cache in compact, ordered form
* @param empty The correct <a href="{@docRoot}/resources/dictionary.html#empty">Empty</a>.
@@ -104,8 +80,6 @@ final class DirectCompactUnorderedSketch extends DirectCompactSketch {
return new DirectCompactUnorderedSketch(dstMem);
}
- //restricted methods
-
@Override
public boolean isOrdered() {
return false;
diff --git a/src/main/java/com/yahoo/sketches/theta/DirectQuickSelectSketchR.java b/src/main/java/com/yahoo/sketches/theta/DirectQuickSelectSketchR.java
index 93a6fd1..a3b2ac8 100644
--- a/src/main/java/com/yahoo/sketches/theta/DirectQuickSelectSketchR.java
+++ b/src/main/java/com/yahoo/sketches/theta/DirectQuickSelectSketchR.java
@@ -20,9 +20,7 @@
package com.yahoo.sketches.theta;
import static com.yahoo.sketches.Util.REBUILD_THRESHOLD;
-import static com.yahoo.sketches.theta.PreambleUtil.EMPTY_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.FAMILY_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.FLAGS_BYTE;
import static com.yahoo.sketches.theta.PreambleUtil.LG_ARR_LONGS_BYTE;
import static com.yahoo.sketches.theta.PreambleUtil.LG_NOM_LONGS_BYTE;
import static com.yahoo.sketches.theta.PreambleUtil.LG_RESIZE_FACTOR_BIT;
@@ -148,7 +146,7 @@ class DirectQuickSelectSketchR extends UpdateSketch {
@Override
public boolean isEmpty() {
- return (mem_.getByte(FLAGS_BYTE) & EMPTY_FLAG_MASK) > 0;
+ return PreambleUtil.isEmpty(mem_);
}
@Override
diff --git a/src/main/java/com/yahoo/sketches/theta/EmptyCompactSketch.java b/src/main/java/com/yahoo/sketches/theta/EmptyCompactSketch.java
new file mode 100644
index 0000000..bd4939a
--- /dev/null
+++ b/src/main/java/com/yahoo/sketches/theta/EmptyCompactSketch.java
@@ -0,0 +1,133 @@
+/*
+ * 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 com.yahoo.sketches.theta;
+
+import com.yahoo.memory.Memory;
+import com.yahoo.sketches.SketchesArgumentException;
+
+/**
+ * Singleton empty CompactSketch.
+ *
+ * @author Lee Rhodes
+ */
+final class EmptyCompactSketch extends CompactSketch {
+
+ //For backward compatibility, a candidate long must have Flags= compact, read-only,
+ // COMPACT-Family=3, SerVer=3, PreLongs=1, and be exactly 8 bytes long. The seedHash is ignored.
+ // NOTE: The empty and ordered flags may or may not be set
+ private static final long EMPTY_SKETCH_MASK = 0X00_00_EB_FF_FF_FF_FF_FFL;
+ private static final long EMPTY_SKETCH_TEST = 0X00_00_0A_00_00_03_03_01L;
+ //When returning a byte array the empty and ordered bits are also set
+ static final byte[] EMPTY_COMPACT_SKETCH_ARR = { 1, 3, 3, 0, 0, 0x1E, 0, 0 };
+ private static final EmptyCompactSketch EMPTY_COMPACT_SKETCH = new EmptyCompactSketch();
+
+ private EmptyCompactSketch() {}
+
+ static EmptyCompactSketch getInstance() {
+ return EMPTY_COMPACT_SKETCH;
+ }
+
+ static EmptyCompactSketch getInstance(final Memory srcMem) {
+ final long pre0 = srcMem.getLong(0);
+ if (testCandidatePre0(pre0)) {
+ return EMPTY_COMPACT_SKETCH;
+ }
+ final long maskedPre0 = pre0 & EMPTY_SKETCH_MASK;
+ throw new SketchesArgumentException("Input Memory does not match required Preamble. "
+ + "Memory Pre0: " + maskedPre0 + ", required Pre0: " + EMPTY_SKETCH_MASK);
+ }
+
+ //static
+
+ static boolean testCandidatePre0(final long candidate) {
+ return (candidate & EMPTY_SKETCH_MASK) == EMPTY_SKETCH_TEST;
+ }
+
+ @Override
+ public int getCurrentBytes(final boolean compact) {
+ return 8;
+ }
+
+ @Override
+ public HashIterator iterator() {
+ return new HeapHashIterator(new long[0], 0, Long.MAX_VALUE);
+ }
+
+ @Override
+ public int getRetainedEntries(final boolean valid) {
+ return 0;
+ }
+
+ @Override
+ public long getThetaLong() {
+ return Long.MAX_VALUE;
+ }
+
+ @Override
+ public boolean hasMemory() {
+ return false;
+ }
+
+ @Override
+ public boolean isDirect() {
+ return false;
+ }
+
+ @Override
+ public boolean isEmpty() {
+ return true;
+ }
+
+ @Override
+ public boolean isOrdered() {
+ return true;
+ }
+
+ /**
+ * Returns 8 bytes representing a CompactSketch that the following flags set:
+ * ordered, compact, empty, readOnly. The SerVer is 3, the Family is COMPACT(3),
+ * and the PreLongs = 1. The seedHash is zero.
+ */
+ @Override
+ public byte[] toByteArray() {
+ return EMPTY_COMPACT_SKETCH_ARR;
+ }
+
+ @Override
+ long[] getCache() {
+ return new long[0];
+ }
+
+ @Override
+ int getCurrentPreambleLongs(final boolean compact) {
+ return 1;
+ }
+
+ @Override
+ Memory getMemory() {
+ return null;
+ }
+
+ @Override
+ short getSeedHash() {
+ return 0;
+ }
+
+}
diff --git a/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java b/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
index 59237a1..73d3a5d 100644
--- a/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
+++ b/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
@@ -19,12 +19,10 @@
package com.yahoo.sketches.theta;
-import static com.yahoo.sketches.theta.PreambleUtil.EMPTY_FLAG_MASK;
-import static com.yahoo.sketches.theta.PreambleUtil.FLAGS_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.PREAMBLE_LONGS_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.RETAINED_ENTRIES_INT;
-import static com.yahoo.sketches.theta.PreambleUtil.SEED_HASH_SHORT;
-import static com.yahoo.sketches.theta.PreambleUtil.THETA_LONG;
+import static com.yahoo.sketches.theta.PreambleUtil.extractCurCount;
+import static com.yahoo.sketches.theta.PreambleUtil.extractPreLongs;
+import static com.yahoo.sketches.theta.PreambleUtil.extractSeedHash;
+import static com.yahoo.sketches.theta.PreambleUtil.extractThetaLong;
import com.yahoo.memory.Memory;
import com.yahoo.sketches.SketchesArgumentException;
@@ -40,10 +38,10 @@ import com.yahoo.sketches.Util;
final class ForwardCompatibility {
/**
- * Convert a serialization version (SerVer) 1 sketch to a SerVer 3 HeapCompactOrderedSketch.
+ * Convert a serialization version (SerVer) 1 sketch to a SerVer 3 sketch.
* Note: SerVer 1 sketches always have metadata-longs of 3 and are always stored
* in a compact ordered form, but with 3 different sketch types. All SerVer 1 sketches will
- * be converted to a SerVer 3, HeapCompactOrderedSketch.
+ * be converted to a SerVer 3 sketches.
*
* @param srcMem the image of a SerVer 1 sketch
*
@@ -51,28 +49,34 @@ final class ForwardCompatibility {
* The seed used for building the sketch image in srcMem.
* Note: SerVer 1 sketches do not have the concept of the SeedHash, so the seed provided here
* MUST be the actual seed that was used when the SerVer 1 sketches were built.
- * @return a SerVer 3 HeapCompactOrderedSketch.
+ * @return a SerVer 3 sketch.
*/
static final CompactSketch heapify1to3(final Memory srcMem, final long seed) {
final int memCap = (int) srcMem.getCapacity();
+ final int curCount = extractCurCount(srcMem);
+ final long thetaLong = extractThetaLong(srcMem);
+ final boolean empty = Sketch.emptyOnCompact(curCount, thetaLong);
- final short seedHash = Util.computeSeedHash(seed);
-
- if (memCap <= 24) { //return empty
- return HeapCompactOrderedSketch
- .compact(new long[0], true, seedHash, 0, Long.MAX_VALUE);
+ if (empty || (memCap <= 24)) { //return empty
+ return EmptyCompactSketch.getInstance();
}
- final int curCount = srcMem.getInt(RETAINED_ENTRIES_INT);
-
- final int mdLongs = 3;
- final int reqBytesIn = (curCount + mdLongs) << 3;
- validateInputSize(reqBytesIn, memCap);
+ final int preLongs = extractPreLongs(srcMem); //always 3 for serVer 1
+ if (preLongs != 3) { //TODO Test this
+ throw new SketchesArgumentException("PreLongs must be 3 for SerVer 1: " + preLongs);
+ }
- final long thetaLong = srcMem.getLong(THETA_LONG);
+ final int reqCap = (curCount + preLongs) << 3;
+ validateInputSize(reqCap, memCap);
+ if ((thetaLong == Long.MAX_VALUE) && (curCount == 1)) {
+ final long hash = srcMem.getLong(preLongs << 3);
+ return new SingleItemSketch(hash, seed);
+ }
+ //theta < 1.0 and/or curCount > 1
+ final short seedHash = Util.computeSeedHash(seed);
final long[] compactOrderedCache = new long[curCount];
- srcMem.getLongArray(24, compactOrderedCache, 0, curCount);
+ srcMem.getLongArray(preLongs << 3, compactOrderedCache, 0, curCount);
return HeapCompactOrderedSketch
.compact(compactOrderedCache, false, seedHash, curCount, thetaLong);
}
@@ -81,37 +85,70 @@ final class ForwardCompatibility {
* Convert a serialization version (SerVer) 2 sketch to a SerVer 3 HeapCompactOrderedSketch.
* Note: SerVer 2 sketches can have metadata-longs of 1,2 or 3 and are always stored
* in a compact ordered form, but with 4 different sketch types.
- * @param srcMem the image of a SerVer 1 sketch
+ * @param srcMem the image of a SerVer 2 sketch
* @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a>.
* The seed used for building the sketch image in srcMem
* @return a SerVer 3 HeapCompactOrderedSketch
*/
static final CompactSketch heapify2to3(final Memory srcMem, final long seed) {
- final int memCap = (int) srcMem.getCapacity();
-
final short seedHash = Util.computeSeedHash(seed);
- final short memSeedHash = srcMem.getShort(SEED_HASH_SHORT);
+ final short memSeedHash = (short)extractSeedHash(srcMem);
Util.checkSeedHashes(seedHash, memSeedHash);
- if (memCap == 8) { //return empty, theta = 1.0
+ final int memCap = (int) srcMem.getCapacity();
+ final int preLongs = extractPreLongs(srcMem); //1,2 or 3
+ int reqBytesIn = 8;
+ int curCount = 0;
+ long thetaLong = Long.MAX_VALUE;
+ if (preLongs == 1) {
+ reqBytesIn = 8;
+ validateInputSize(reqBytesIn, memCap);
+ return EmptyCompactSketch.getInstance();
+ }
+ if (preLongs == 2) { //includes pre0 + count, no theta
+ reqBytesIn = preLongs << 3;
+ validateInputSize(reqBytesIn, memCap);
+ curCount = extractCurCount(srcMem);
+ if (curCount == 0) {
+ return EmptyCompactSketch.getInstance();
+ }
+ if (curCount == 1) { //TODO Test this
+ reqBytesIn = (preLongs + 1) << 3;
+ validateInputSize(reqBytesIn, memCap);
+ final long hash = srcMem.getLong(preLongs << 3);
+ return new SingleItemSketch(hash, seed);
+ }
+ //curCount > 1
+ reqBytesIn = (curCount + preLongs) << 3;
+ validateInputSize(reqBytesIn, memCap);
+ final long[] compactOrderedCache = new long[curCount];
+ srcMem.getLongArray(preLongs << 3, compactOrderedCache, 0, curCount);
return HeapCompactOrderedSketch
- .compact(new long[0], true, seedHash, 0, Long.MAX_VALUE);
+ .compact(compactOrderedCache, false, seedHash, curCount, thetaLong);
}
-
- final int curCount = srcMem.getInt(RETAINED_ENTRIES_INT);
- //Note: curCount could be zero and theta < 1.0 and be empty or not-empty.
-
- final int mdLongs = srcMem.getByte(PREAMBLE_LONGS_BYTE) & 0X3F; //either 2 or 3
- final int reqBytesIn = (curCount + mdLongs) << 3;
- validateInputSize(reqBytesIn, memCap);
-
- final long thetaLong = (mdLongs < 3) ? Long.MAX_VALUE : srcMem.getLong(THETA_LONG);
- boolean empty = (srcMem.getByte(FLAGS_BYTE) & EMPTY_FLAG_MASK) != 0;
- empty = (curCount == 0) && (thetaLong == Long.MAX_VALUE); //force true
- final long[] compactOrderedCache = new long[curCount];
- srcMem.getLongArray(mdLongs << 3, compactOrderedCache, 0, curCount);
- return HeapCompactOrderedSketch
- .compact(compactOrderedCache, empty, seedHash, curCount, thetaLong);
+ if (preLongs == 3) { //pre0 + count + theta
+ reqBytesIn = (preLongs) << 3; //
+ validateInputSize(reqBytesIn, memCap);
+ curCount = extractCurCount(srcMem);
+ thetaLong = extractThetaLong(srcMem);
+ if ((curCount == 0) && (thetaLong == Long.MAX_VALUE)) {
+ return EmptyCompactSketch.getInstance();
+ }
+ if ((curCount == 1) && (thetaLong == Long.MAX_VALUE)) { //TODO Test here to end
+ reqBytesIn = (preLongs + 1) << 3;
+ validateInputSize(reqBytesIn, memCap);
+ final long hash = srcMem.getLong(preLongs << 3);
+ return new SingleItemSketch(hash, seed);
+ }
+ //curCount > 1 and/or theta < 1.0
+ reqBytesIn = (curCount + preLongs) << 3;
+ validateInputSize(reqBytesIn, memCap);
+ final long[] compactOrderedCache = new long[curCount];
+ srcMem.getLongArray(preLongs << 3, compactOrderedCache, 0, curCount);
+ return HeapCompactOrderedSketch
+ .compact(compactOrderedCache, false, seedHash, curCount, thetaLong);
+ }
+ throw new SketchesArgumentException("PreLongs must be 1,2, or 3: " + preLongs);
}
private static final void validateInputSize(final int reqBytesIn, final int memCap) {
diff --git a/src/main/java/com/yahoo/sketches/theta/HeapAnotB.java b/src/main/java/com/yahoo/sketches/theta/HeapAnotB.java
index 62ae043..9a84366 100644
--- a/src/main/java/com/yahoo/sketches/theta/HeapAnotB.java
+++ b/src/main/java/com/yahoo/sketches/theta/HeapAnotB.java
@@ -124,10 +124,24 @@ final class HeapAnotB extends AnotB {
//restricted
void compute() {
- final int swA = (a_ == null) ? 0 : (a_.isEmpty())
- ? 1 : (a_ instanceof UpdateSketch) ? 4 : (a_.isOrdered()) ? 3 : 2;
- final int swB = (b_ == null) ? 0 : (b_.isEmpty()) ? 1 : (b_ instanceof UpdateSketch)
- ? 4 : (b_.isOrdered()) ? 3 : 2;
+ final int swA = ((a_ == null) || (a_ instanceof EmptyCompactSketch))
+ ? 0
+ : (a_.isEmpty())
+ ? 1
+ : (a_ instanceof UpdateSketch)
+ ? 4
+ : (a_.isOrdered())
+ ? 3
+ : 2;
+ final int swB = ((b_ == null) || (b_ instanceof EmptyCompactSketch))
+ ? 0
+ : (b_.isEmpty())
+ ? 1
+ : (b_ instanceof UpdateSketch)
+ ? 4
+ : (b_.isOrdered())
+ ? 3
+ : 2;
final int sw = (swA * 8) | swB;
// NOTES:
diff --git a/src/main/java/com/yahoo/sketches/theta/HeapCompactOrderedSketch.java b/src/main/java/com/yahoo/sketches/theta/HeapCompactOrderedSketch.java
index a71d801..61a062c 100644
--- a/src/main/java/com/yahoo/sketches/theta/HeapCompactOrderedSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/HeapCompactOrderedSketch.java
@@ -45,7 +45,7 @@ final class HeapCompactOrderedSketch extends HeapCompactSketch {
* @param thetaLong The correct
* <a href="{@docRoot}/resources/dictionary.html#thetaLong">thetaLong</a>.
*/
- private HeapCompactOrderedSketch(final long[] cache, final boolean empty, final short seedHash,
+ HeapCompactOrderedSketch(final long[] cache, final boolean empty, final short seedHash,
final int curCount, final long thetaLong) {
super(cache, empty, seedHash, curCount, thetaLong);
}
@@ -62,7 +62,7 @@ final class HeapCompactOrderedSketch extends HeapCompactSketch {
checkSeedHashes(memSeedHash, computedSeedHash);
final int preLongs = extractPreLongs(srcMem);
- final boolean empty = PreambleUtil.isEmpty(srcMem);
+ final boolean empty = PreambleUtil.isEmpty(srcMem); //checks for cap <= 8
int curCount = 0;
long thetaLong = Long.MAX_VALUE;
long[] cache = new long[0];
@@ -86,28 +86,6 @@ final class HeapCompactOrderedSketch extends HeapCompactSketch {
}
/**
- * Converts the given UpdateSketch to this compact form.
- * @param sketch the given UpdateSketch
- * @return a CompactSketch
- */
- static CompactSketch compact(final UpdateSketch sketch) {
- final int curCount = sketch.getRetainedEntries(true);
- long thetaLong = sketch.getThetaLong();
- boolean empty = sketch.isEmpty();
- thetaLong = thetaOnCompact(empty, curCount, thetaLong);
- empty = emptyOnCompact(curCount, thetaLong);
- final short seedHash = sketch.getSeedHash();
- final long[] cache = sketch.getCache();
- final boolean ordered = true;
- final long[] cacheOut = CompactSketch.compactCache(cache, curCount, thetaLong, ordered);
- if ((curCount == 1) && (thetaLong == Long.MAX_VALUE)) {
- return new SingleItemSketch(cacheOut[0], seedHash);
- }
- return new HeapCompactOrderedSketch(cacheOut, empty, seedHash, curCount, thetaLong);
- }
-
-
- /**
* Constructs this sketch from correct, valid arguments.
* @param cache in compact, ordered form
* @param empty The correct <a href="{@docRoot}/resources/dictionary.html#empty">Empty</a>.
@@ -120,9 +98,6 @@ final class HeapCompactOrderedSketch extends HeapCompactSketch {
*/
static CompactSketch compact(final long[] cache, final boolean empty,
final short seedHash, final int curCount, final long thetaLong) {
- if ((curCount == 1) && (thetaLong == Long.MAX_VALUE)) {
- return new SingleItemSketch(cache[0], seedHash);
- }
return new HeapCompactOrderedSketch(cache, empty, seedHash, curCount, thetaLong);
}
@@ -133,8 +108,6 @@ final class HeapCompactOrderedSketch extends HeapCompactSketch {
return toByteArray(true);
}
- //restricted methods
-
@Override
public boolean isOrdered() {
return true;
diff --git a/src/main/java/com/yahoo/sketches/theta/HeapCompactUnorderedSketch.java b/src/main/java/com/yahoo/sketches/theta/HeapCompactUnorderedSketch.java
index b6e640f..c214d86 100644
--- a/src/main/java/com/yahoo/sketches/theta/HeapCompactUnorderedSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/HeapCompactUnorderedSketch.java
@@ -45,7 +45,7 @@ final class HeapCompactUnorderedSketch extends HeapCompactSketch {
* @param thetaLong The correct
* <a href="{@docRoot}/resources/dictionary.html#thetaLong">thetaLong</a>.
*/
- private HeapCompactUnorderedSketch(final long[] cache, final boolean empty, final short seedHash,
+ HeapCompactUnorderedSketch(final long[] cache, final boolean empty, final short seedHash,
final int curCount, final long thetaLong) {
super(cache, empty, seedHash, curCount, thetaLong);
}
@@ -61,52 +61,23 @@ final class HeapCompactUnorderedSketch extends HeapCompactSketch {
final short computedSeedHash = computeSeedHash(seed);
checkSeedHashes(memSeedHash, computedSeedHash);
- final int preLongs = extractPreLongs(srcMem);
- final boolean empty = PreambleUtil.isEmpty(srcMem);
+ final int preLongs = extractPreLongs(srcMem); //must be > 1
+ final boolean empty = PreambleUtil.isEmpty(srcMem); //checks for cap <= 8
int curCount = 0;
long thetaLong = Long.MAX_VALUE;
long[] cache = new long[0];
-
- if (preLongs == 1) {
- if (!empty) { //singleItem
- return new SingleItemSketch(srcMem.getLong(8), memSeedHash);
- }
- //else empty
- } else { //preLongs > 1
- curCount = extractCurCount(srcMem);
- cache = new long[curCount];
- if (preLongs == 2) {
- srcMem.getLongArray(16, cache, 0, curCount);
- } else { //preLongs == 3
- srcMem.getLongArray(24, cache, 0, curCount);
- thetaLong = extractThetaLong(srcMem);
- }
+ curCount = extractCurCount(srcMem);
+ cache = new long[curCount];
+ if (preLongs == 2) {
+ srcMem.getLongArray(16, cache, 0, curCount);
+ } else { //preLongs == 3
+ srcMem.getLongArray(24, cache, 0, curCount);
+ thetaLong = extractThetaLong(srcMem);
}
return new HeapCompactUnorderedSketch(cache, empty, memSeedHash, curCount, thetaLong);
}
/**
- * Converts the given UpdateSketch to this compact form.
- * @param sketch the given UpdateSketch
- * @return a CompactSketch
- */
- static CompactSketch compact(final UpdateSketch sketch) {
- final int curCount = sketch.getRetainedEntries(true);
- long thetaLong = sketch.getThetaLong();
- boolean empty = sketch.isEmpty();
- thetaLong = thetaOnCompact(empty, curCount, thetaLong);
- empty = emptyOnCompact(curCount, thetaLong);
- final short seedHash = sketch.getSeedHash();
- final long[] cache = sketch.getCache();
- final boolean ordered = false;
- final long[] cacheOut = CompactSketch.compactCache(cache, curCount, thetaLong, ordered);
- if ((curCount == 1) && (thetaLong == Long.MAX_VALUE)) {
- return new SingleItemSketch(cacheOut[0], seedHash);
- }
- return new HeapCompactUnorderedSketch(cacheOut, empty, seedHash, curCount, thetaLong);
- }
-
- /**
* Constructs this sketch from correct, valid arguments.
* @param cache in compact form
* @param empty The correct <a href="{@docRoot}/resources/dictionary.html#empty">Empty</a>.
@@ -119,9 +90,6 @@ final class HeapCompactUnorderedSketch extends HeapCompactSketch {
*/
static CompactSketch compact(final long[] cache, final boolean empty,
final short seedHash, final int curCount, final long thetaLong) {
- if ((curCount == 1) && (thetaLong == Long.MAX_VALUE)) {
- return new SingleItemSketch(cache[0], seedHash);
- }
return new HeapCompactUnorderedSketch(cache, empty, seedHash, curCount, thetaLong);
}
diff --git a/src/main/java/com/yahoo/sketches/theta/Intersection.java b/src/main/java/com/yahoo/sketches/theta/Intersection.java
index 2b3a12e..239fbd9 100644
--- a/src/main/java/com/yahoo/sketches/theta/Intersection.java
+++ b/src/main/java/com/yahoo/sketches/theta/Intersection.java
@@ -38,7 +38,11 @@ public abstract class Intersection extends SetOperation {
* Gets the result of this operation as a CompactSketch of the chosen form.
* The update method must have been called at least once, otherwise an exception will be
* thrown. This is because a virgin Intersection object represents the Universal Set,
- * which would have an infinite number of values.
+ * which has an infinite number of values.
+ *
+ * <p>Note that presenting an intersection with an empty or null sketch sets the internal
+ * state of the intersection to empty = true, and current count = 0. This is consistent with
+ * the mathematical definition of the intersection of any set with the null set is always null.</p>
*
* @param dstOrdered
* <a href="{@docRoot}/resources/dictionary.html#dstOrdered">See Destination Ordered</a>
diff --git a/src/main/java/com/yahoo/sketches/theta/IntersectionImpl.java b/src/main/java/com/yahoo/sketches/theta/IntersectionImpl.java
index a1de010..43e1078 100644
--- a/src/main/java/com/yahoo/sketches/theta/IntersectionImpl.java
+++ b/src/main/java/com/yahoo/sketches/theta/IntersectionImpl.java
@@ -182,12 +182,9 @@ final class IntersectionImpl extends IntersectionImplR {
@Override
public void update(final Sketch sketchIn) {
- if (sketchIn != null) {
- Util.checkSeedHashes(seedHash_, sketchIn.getSeedHash());
- }
- //Null / Empty cases.
- //Note: null == empty := Th = 1.0, count = 0, empty = true
- if ((sketchIn == null) || sketchIn.isEmpty() || empty_) { //empty rule
+ //Null/Empty cases: Note: null == empty := Th = 1.0, count = 0, empty = true
+ if (empty_ || (sketchIn == null) || sketchIn.isEmpty()
+ || (sketchIn instanceof EmptyCompactSketch)) { //empty rule
//Because of the def of null above and the Empty Rule (which is OR), empty_ must be true.
//Whatever the current internal state, we make it empty.
empty_ = true;
@@ -204,7 +201,7 @@ final class IntersectionImpl extends IntersectionImplR {
}
return;
}
-
+ Util.checkSeedHashes(seedHash_, sketchIn.getSeedHash());
thetaLong_ = min(thetaLong_, sketchIn.getThetaLong()); //Theta rule
empty_ = false;
if (mem_ != null) {
diff --git a/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java b/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
index d9d94e2..0d358ea 100644
--- a/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
+++ b/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
@@ -40,14 +40,17 @@ public class PairwiseSetOperations {
/**
* This implements a stateless, pair-wise <i>Intersect</i> operation on sketches
* that are either Heap-based or Direct.
- * If both inputs are null a null is returned.
+ * If both inputs are null an EmptyCompactSketch is returned.
*
* @param skA The first Sketch argument.
* @param skB The second Sketch argument.
* @return the result as an ordered CompactSketch on the heap.
*/
public static CompactSketch intersect(final Sketch skA, final Sketch skB) {
- if ((skA == null) && (skB == null)) { return null; }
+ if (((skA == null) || (skA instanceof EmptyCompactSketch))
+ && ((skB == null) || (skB instanceof EmptyCompactSketch))) {
+ return EmptyCompactSketch.getInstance();
+ }
final short seedHash = (skA == null) ? skB.getSeedHash() : skA.getSeedHash();
final Intersection inter = new IntersectionImpl(seedHash);
return inter.intersect(skA, skB, true, null);
@@ -56,15 +59,19 @@ public class PairwiseSetOperations {
/**
* This implements a stateless, pair-wise <i>A AND NOT B</i> operation on Sketches
* that are either Heap-based or Direct.
- * If both inputs are null a null is returned.
+ * If both inputs are null an EmptyCompactSketch is returned.
*
* @param skA The first Sketch argument.
* @param skB The second Sketch argument.
* @return the result as an ordered CompactSketch on the heap.
*/
public static CompactSketch aNotB(final Sketch skA, final Sketch skB) {
- if ((skA == null) && (skB == null)) { return null; }
- final short seedHash = (skA == null) ? skB.getSeedHash() : skA.getSeedHash();
+ if (((skA == null) || (skA instanceof EmptyCompactSketch))
+ && ((skB == null) || (skB instanceof EmptyCompactSketch))) {
+ return EmptyCompactSketch.getInstance();
+ }
+ final short seedHash = ((skA == null) || (skA instanceof EmptyCompactSketch))
+ ? skB.getSeedHash() : skA.getSeedHash();
final HeapAnotB anotb = new HeapAnotB(seedHash);
return anotb.aNotB(skA, skB, true, null);
}
@@ -72,7 +79,7 @@ public class PairwiseSetOperations {
/**
* This implements a stateless, pair-wise union operation on ordered,
* CompactSketches that are either Heap-based or Direct.
- * If both inputs are null a null is returned.
+ * If both inputs are null an EmptyCompactSketch is returned.
* If one is null the other is returned, which can be either Heap-based or Direct.
* This is equivalent to union(skA, skB, k) where k is the default of 4096.
*
@@ -103,39 +110,37 @@ public class PairwiseSetOperations {
//Handle all corner cases with null or empty arguments
//For backward compatibility, we must allow input empties with Theta < 1.0.
final int swA, swB;
- if (skA == null) { swA = 1; } else { checkOrdered(skA); swA = skA.isEmpty() ? 2 : 3; }
- if (skB == null) { swB = 1; } else { checkOrdered(skB); swB = skB.isEmpty() ? 2 : 3; }
+ if ((skA == null) || (skA instanceof EmptyCompactSketch)) {
+ swA = 1;
+ } else {
+ checkOrdered(skA);
+ swA = skA.isEmpty() ? 2 : 3;
+ }
+ if ((skB == null) || (skB instanceof EmptyCompactSketch)) {
+ swB = 1;
+ } else {
+ checkOrdered(skB);
+ swB = skB.isEmpty() ? 2 : 3;
+ }
final int sw = (swA << 2) | swB;
switch (sw) {
- case 5: { //skA == null; skB == null; return null. Cannot determine seedhash.
- return null;
- }
- case 6: { //skA == null; skB == empty; return empty
- final long thetaLong = skB.getThetaLong(); //lgtm [java/dereferenced-value-may-be-null]
- return (thetaLong == Long.MAX_VALUE) ? skB
- : HeapCompactOrderedSketch.compact(new long[0], true, skB.getSeedHash(), 0, Long.MAX_VALUE);
+ case 5: //skA == null/ECS; skB == null; return EmptyCompactSketch.
+ case 6: //skA == null/ECS; skB == empty; return EmptyCompactSketch.
+ case 9: { //skA == empty; skB == null/ECS; return EmptyCompactSketch.
+ return EmptyCompactSketch.getInstance();
}
- case 7: { //skA == null; skB == valid; return skB
+ case 7: { //skA == null/ECS; skB == valid; return skB
return maybeCutback(skB, k);
}
- case 9: { //skA == empty; skB == null; return empty
- final long thetaLong = skA.getThetaLong(); //lgtm [java/dereferenced-value-may-be-null]
- return (thetaLong == Long.MAX_VALUE) ? skA
- : HeapCompactOrderedSketch.compact(new long[0], true, skA.getSeedHash(), 0, Long.MAX_VALUE);
- }
case 10: { //skA == empty; skB == empty; return empty
- final short seedHash = seedHashesCheck(skA, skB);
- long thetaLong = skA.getThetaLong(); //lgtm [java/dereferenced-value-may-be-null]
- if (thetaLong == Long.MAX_VALUE) { return skA; }
- thetaLong = skB.getThetaLong(); //lgtm [java/dereferenced-value-may-be-null]
- if (thetaLong == Long.MAX_VALUE) { return skB; }
- return HeapCompactOrderedSketch.compact(new long[0], true, seedHash, 0, Long.MAX_VALUE);
+ seedHashesCheck(skA, skB);
+ return EmptyCompactSketch.getInstance();
}
case 11: { //skA == empty; skB == valid; return skB
seedHashesCheck(skA, skB);
return maybeCutback(skB, k);
}
- case 13: { //skA == valid; skB == null; return skA
+ case 13: { //skA == valid; skB == null/ECS; return skA
return maybeCutback(skA, k);
}
case 14: { //skA == valid; skB == empty; return skA
diff --git a/src/main/java/com/yahoo/sketches/theta/PreambleUtil.java b/src/main/java/com/yahoo/sketches/theta/PreambleUtil.java
index 07674c2..c494b76 100644
--- a/src/main/java/com/yahoo/sketches/theta/PreambleUtil.java
+++ b/src/main/java/com/yahoo/sketches/theta/PreambleUtil.java
@@ -45,7 +45,9 @@ import com.yahoo.sketches.SketchesArgumentException;
* multi-byte integers (<i>int</i> and <i>long</i>) are stored in native byte order. The
* <i>byte</i> values are treated as unsigned.</p>
*
- * <p>An empty CompactSketch only requires 8 bytes.</p>
+ * <p>An empty CompactSketch only requires 8 bytes.
+ * Flags: notSI, Ordered*, Compact, Empty*, ReadOnly, LE.
+ * (*) Earlier versions did not set these.</p>
*
* <pre>
* Long || Start Byte Adr:
@@ -55,7 +57,8 @@ import com.yahoo.sketches.SketchesArgumentException;
* </pre>
*
* <p>A SingleItemSketch (extends CompactSketch) requires an 8 byte preamble plus a single
- * hash item of 8 bytes.</p>
+ * hash item of 8 bytes. Flags: SingleItem*, Ordered, Compact, notEmpty, ReadOnly, LE.
+ * (*) Earlier versions did not set these.</p>
*
* <pre>
* Long || Start Byte Adr:
@@ -170,7 +173,8 @@ final class PreambleUtil {
static final int EMPTY_FLAG_MASK = 4; //SerVer 2, 3
static final int COMPACT_FLAG_MASK = 8; //SerVer 2 was NO_REBUILD_FLAG_MASK, 3
static final int ORDERED_FLAG_MASK = 16;//SerVer 2 was UNORDERED_FLAG_MASK, 3
- static final int SINGLEITEM_FLAG_MASK = 32;//SerVer 3. Reserved, set but not read
+ static final int SINGLEITEM_FLAG_MASK = 32;//SerVer 3
+ //The last 2 bits of the flags byte are reserved and assumed to be zero, for now.
//Backward compatibility: SerVer1 preamble always 3 longs, SerVer2 preamble: 1, 2, 3 longs
// SKETCH_TYPE_BYTE 2 //SerVer1, SerVer2
@@ -453,8 +457,9 @@ final class PreambleUtil {
}
static boolean isEmpty(final Memory mem) {
- final int flags = mem.getByte(FLAGS_BYTE) & 0xFFFF;
- return (flags & EMPTY_FLAG_MASK) > 0;
+ final boolean emptyFlag = (mem.getByte(FLAGS_BYTE) & EMPTY_FLAG_MASK) > 0;
+ final boolean emptyCap = mem.getCapacity() < 16L;
+ return emptyFlag || emptyCap;
}
/**
diff --git a/src/main/java/com/yahoo/sketches/theta/SetOperation.java b/src/main/java/com/yahoo/sketches/theta/SetOperation.java
index 5640880..387eb69 100644
--- a/src/main/java/com/yahoo/sketches/theta/SetOperation.java
+++ b/src/main/java/com/yahoo/sketches/theta/SetOperation.java
@@ -243,33 +243,37 @@ public abstract class SetOperation {
final WritableMemory dstMem) {
thetaLong = thetaOnCompact(empty, curCount, thetaLong);
empty = emptyOnCompact(curCount, thetaLong);
-
- CompactSketch sketchOut = null;
- final int sw = (dstOrdered ? 2 : 0) | ((dstMem != null) ? 1 : 0);
- switch (sw) {
- case 0: { //dst not ordered, dstMem == null
- sketchOut = HeapCompactUnorderedSketch.compact(compactCache, empty, seedHash, curCount,
- thetaLong); //converts to SingleItem if curCount == 1
- break;
+ if (empty) {
+ final EmptyCompactSketch sk = EmptyCompactSketch.getInstance();
+ if (dstMem != null) {
+ dstMem.putByteArray(0, sk.toByteArray(), 0, 8);
}
- case 1: { //dst not ordered, dstMem == valid
- sketchOut = DirectCompactUnorderedSketch.compact(compactCache, empty, seedHash, curCount,
- thetaLong, dstMem); //converts to SingleItem format if curCount == 1
- break;
+ return sk;
+ }
+ if ((thetaLong == Long.MAX_VALUE) && (curCount == 1)) {
+ final SingleItemSketch sis = new SingleItemSketch(compactCache[0], seedHash);
+ if ((dstMem != null) && (dstMem.getCapacity() >= 16)) {
+ dstMem.putByteArray(0, sis.toByteArray(), 0, 16);
}
- case 2: { //dst ordered, dstMem == null
- sketchOut = HeapCompactOrderedSketch.compact(compactCache, empty, seedHash, curCount,
+ return sis;
+ }
+ if (dstMem == null) {
+ if (dstOrdered) {
+ return HeapCompactOrderedSketch.compact(compactCache, empty, seedHash, curCount,
thetaLong); //converts to SingleItem format if curCount == 1
- break;
+ } else {
+ return HeapCompactUnorderedSketch.compact(compactCache, empty, seedHash, curCount,
+ thetaLong); //converts to SingleItem if curCount == 1
}
- case 3: { //dst ordered, dstMem == valid
- sketchOut = DirectCompactOrderedSketch.compact(compactCache, empty, seedHash, curCount,
+ } else {
+ if (dstOrdered) {
+ return DirectCompactOrderedSketch.compact(compactCache, empty, seedHash, curCount,
+ thetaLong, dstMem); //converts to SingleItem format if curCount == 1
+ } else {
+ return DirectCompactUnorderedSketch.compact(compactCache, empty, seedHash, curCount,
thetaLong, dstMem); //converts to SingleItem format if curCount == 1
- break;
}
- //default: //This cannot happen and cannot be tested
}
- return sketchOut;
}
/**
diff --git a/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java b/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java
index eeada11..536988c 100644
--- a/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java
@@ -23,10 +23,8 @@ import static com.yahoo.sketches.Util.DEFAULT_UPDATE_SEED;
import static com.yahoo.sketches.Util.checkSeedHashes;
import static com.yahoo.sketches.Util.computeSeedHash;
import static com.yahoo.sketches.hash.MurmurHash3.hash;
-import static com.yahoo.sketches.theta.PreambleUtil.COMPACT_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.MAX_THETA_LONG_AS_DOUBLE;
-import static com.yahoo.sketches.theta.PreambleUtil.ORDERED_FLAG_MASK;
-import static com.yahoo.sketches.theta.PreambleUtil.READ_ONLY_FLAG_MASK;
+import static com.yahoo.sketches.theta.PreambleUtil.SINGLEITEM_FLAG_MASK;
import static java.nio.charset.StandardCharsets.UTF_8;
import com.yahoo.memory.Memory;
@@ -36,28 +34,48 @@ import com.yahoo.sketches.SketchesArgumentException;
* @author Lee Rhodes
*/
public final class SingleItemSketch extends CompactSketch {
- private static final long FLAGS =
- (READ_ONLY_FLAG_MASK | COMPACT_FLAG_MASK | ORDERED_FLAG_MASK) & 0xFFL;
- private static final long LO6BYTES = (FLAGS << 40) | (3L << 16) | (3L << 8) | 1L;
private static final long DEFAULT_SEED_HASH = computeSeedHash(DEFAULT_UPDATE_SEED) & 0xFFFFL;
- private static final long DEFAULT_PRE0 = (DEFAULT_SEED_HASH << 48) | LO6BYTES;
+ private static final String LS = System.getProperty("line.separator");
+
+ //For backward compatibility, a candidate pre0 long must have Flags= compact, read-only, ordered,
+ // empty=0; COMPACT-Family=3, SerVer=3, PreLongs=1, plus the relevant seedHash.
+ private static final long PRE0_LO6 = 0X00_00_1A_00_00_03_03_01L; //no SI flag, requires not empty
+ private static final long PRE0_MASK = 0XFF_FF_DF_FF_FF_FF_FF_FFL; //removes SI flag
private final long[] arr = new long[2];
+ //use to test a candidate pre0 given a seed TODO need?
+ static boolean testPre0Seed(final long candidate, final long seed) {
+ final long seedHash = computeSeedHash(seed) & 0xFFFFL;
+ return testPre0SeedHash(candidate, seedHash);
+ }
+
+ //use to test a candidate pre0 given a seedHash
+ static boolean testPre0SeedHash(final long candidate, final long seedHash) {
+ final long test1 = (seedHash << 48) | PRE0_LO6; //no SI bit
+ final long test2 = test1 | ((long)SINGLEITEM_FLAG_MASK << 40);
+ final long mask = PRE0_MASK; //ignores the SI flag
+ final long masked = candidate & mask;
+ return (masked == test1) || (candidate == test2);
+ }
+
+ //Internal Constructor. All checking has been done, assumes default seed
private SingleItemSketch(final long hash) {
- arr[0] = DEFAULT_PRE0;
+ arr[0] = (DEFAULT_SEED_HASH << 48) | PRE0_LO6 | ((long)SINGLEITEM_FLAG_MASK << 40);
arr[1] = hash;
}
- private SingleItemSketch(final long hash, final long seed) {
+ //Internal Constructor.All checking has been done, give the relevant seed
+ SingleItemSketch(final long hash, final long seed) {
final long seedHash = computeSeedHash(seed) & 0xFFFFL;
- arr[0] = (seedHash << 48) | LO6BYTES;
+ arr[0] = (seedHash << 48) | PRE0_LO6 | ((long)SINGLEITEM_FLAG_MASK << 40);
arr[1] = hash;
}
+ //All checking has been done, give the relevant seed
SingleItemSketch(final long hash, final short seedHash) {
final long seedH = seedHash & 0xFFFFL;
- arr[0] = (seedH << 48) | LO6BYTES;
+ arr[0] = (seedH << 48) | PRE0_LO6 | ((long)SINGLEITEM_FLAG_MASK << 40);
arr[1] = hash;
}
@@ -68,8 +86,14 @@ public final class SingleItemSketch extends CompactSketch {
*/
public static SingleItemSketch heapify(final Memory mem) {
final long memPre0 = mem.getLong(0);
- checkDefaultBytes0to7(memPre0);
- return new SingleItemSketch(mem.getLong(8));
+ if (testPre0SeedHash(memPre0, DEFAULT_SEED_HASH)) {
+ return new SingleItemSketch(mem.getLong(8));
+ }
+ System.out.println("memPre0 : " + Long.toHexString(memPre0));
+ final long def = ((DEFAULT_SEED_HASH << 48) | PRE0_LO6);
+ throw new SketchesArgumentException("Input Memory does not match defualt Preamble. " + LS
+ + "Memory Pre0 : " + Long.toHexString(memPre0) + LS
+ + "default Pre0 : " + Long.toHexString(def));
}
/**
@@ -81,11 +105,16 @@ public final class SingleItemSketch extends CompactSketch {
*/
public static SingleItemSketch heapify(final Memory mem, final long seed) {
final long memPre0 = mem.getLong(0);
- checkDefaultBytes0to5(memPre0);
- final short seedHashIn = mem.getShort(6);
+ final short seedHashMem = mem.getShort(6);
final short seedHashCk = computeSeedHash(seed);
- checkSeedHashes(seedHashIn, seedHashCk);
- return new SingleItemSketch(mem.getLong(8), seed);
+ checkSeedHashes(seedHashMem, seedHashCk);
+ if (testPre0SeedHash(memPre0, seedHashCk)) {
+ return new SingleItemSketch(mem.getLong(8), seedHashCk);
+ }
+ final long def = (((long)seedHashCk << 48) | PRE0_LO6);
+ throw new SketchesArgumentException("Input Memory does not match required Preamble. " + LS
+ + "Memory Pre0 : " + Long.toHexString(memPre0) + LS
+ + "default Pre0 : " + Long.toHexString(def));
}
//Create methods using the default seed
@@ -385,19 +414,4 @@ public final class SingleItemSketch extends CompactSketch {
return (short) (arr[0] >>> 48);
}
- static void checkDefaultBytes0to7(final long memPre0) {
- if (memPre0 != DEFAULT_PRE0) {
- throw new SketchesArgumentException(
- "Input Memory does not match defualt Preamble bytes 0 through 7.");
- }
- }
-
- static void checkDefaultBytes0to5(final long memPre0) {
- final long mask = (1L << 48) - 1L;
- if ((memPre0 & mask) != LO6BYTES) {
- throw new SketchesArgumentException(
- "Input Memory does not match defualt Preamble bytes 0 through 5.");
- }
- }
-
}
diff --git a/src/main/java/com/yahoo/sketches/theta/Sketch.java b/src/main/java/com/yahoo/sketches/theta/Sketch.java
index 43d332f..4e32f63 100644
--- a/src/main/java/com/yahoo/sketches/theta/Sketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/Sketch.java
@@ -24,6 +24,7 @@ import static com.yahoo.sketches.HashOperations.count;
import static com.yahoo.sketches.Util.DEFAULT_UPDATE_SEED;
import static com.yahoo.sketches.Util.LS;
import static com.yahoo.sketches.Util.ceilingPowerOf2;
+import static com.yahoo.sketches.Util.computeSeedHash;
import static com.yahoo.sketches.Util.zeroPad;
import static com.yahoo.sketches.theta.PreambleUtil.COMPACT_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.FAMILY_BYTE;
@@ -31,7 +32,9 @@ import static com.yahoo.sketches.theta.PreambleUtil.FLAGS_BYTE;
import static com.yahoo.sketches.theta.PreambleUtil.MAX_THETA_LONG_AS_DOUBLE;
import static com.yahoo.sketches.theta.PreambleUtil.ORDERED_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.PREAMBLE_LONGS_BYTE;
+import static com.yahoo.sketches.theta.PreambleUtil.READ_ONLY_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.SER_VER_BYTE;
+import static com.yahoo.sketches.theta.PreambleUtil.extractSeedHash;
import com.yahoo.memory.Memory;
import com.yahoo.memory.WritableMemory;
@@ -47,9 +50,9 @@ import com.yahoo.sketches.Util;
* @author Lee Rhodes
*/
public abstract class Sketch {
-
static final int DEFAULT_LG_RESIZE_FACTOR = 3; //Unique to Heap
+
Sketch() {}
//public static factory constructor-type methods
@@ -80,9 +83,7 @@ public abstract class Sketch {
public static Sketch heapify(final Memory srcMem, final long seed) {
final int serVer = srcMem.getByte(SER_VER_BYTE);
if (serVer == 3) {
- final byte famID = srcMem.getByte(FAMILY_BYTE);
- final boolean ordered = (srcMem.getByte(FLAGS_BYTE) & ORDERED_FLAG_MASK) != 0;
- return constructHeapSketch(famID, ordered, srcMem, seed);
+ return heapifyFromMemory(srcMem, seed);
}
if (serVer == 1) {
return ForwardCompatibility.heapify1to3(srcMem, seed);
@@ -134,21 +135,38 @@ public abstract class Sketch {
}
}
case COMPACT: { //serVer 1, 2, or 3, preLongs = 1, 2, or 3
- if (serVer == 1) {
+ if (serVer == 3) {
+ final long cap = srcMem.getCapacity();
+ if (cap < 16) { //EMPTY?
+ return EmptyCompactSketch.getInstance(srcMem);
+ }
+ if (cap == 16) { //SINGLEITEM?
+ return SingleItemSketch.heapify(srcMem, seed);
+ }
+ //not empty & not singleItem, assume cap > 16
+ final int flags = srcMem.getByte(FLAGS_BYTE);
+ final boolean orderedFlag = (flags & ORDERED_FLAG_MASK) > 0;
+ final boolean compactFlag = (flags & COMPACT_FLAG_MASK) > 0;
+ if (!compactFlag) {
+ throw new SketchesArgumentException(
+ "Corrupted: COMPACT family sketch image must have compact flag set");
+ }
+ final boolean readOnly = (flags & READ_ONLY_FLAG_MASK) > 0;
+ if (!readOnly) {
+ throw new SketchesArgumentException(
+ "Corrupted: COMPACT family sketch image must have Read-Only flag set");
+ }
+ return orderedFlag ? DirectCompactOrderedSketch.wrapInstance(srcMem, seed)
+ : DirectCompactUnorderedSketch.wrapInstance(srcMem, seed);
+ } //end of serVer 3
+ else if (serVer == 1) {
return ForwardCompatibility.heapify1to3(srcMem, seed);
}
else if (serVer == 2) {
return ForwardCompatibility.heapify2to3(srcMem, seed);
}
- final int flags = srcMem.getByte(FLAGS_BYTE);
- final boolean compact = (flags & COMPACT_FLAG_MASK) > 0; //used for corruption check
- final boolean ordered = (flags & ORDERED_FLAG_MASK) > 0;
- if (compact) {
- return ordered ? DirectCompactOrderedSketch.wrapInstance(srcMem, seed)
- : DirectCompactUnorderedSketch.wrapInstance(srcMem, seed);
- }
throw new SketchesArgumentException(
- "Corrupted: " + family + " family image must have compact flag set");
+ "Corrupted: Serialization Version " + serVer + " not recognized.");
}
default: throw new SketchesArgumentException(
"Sketch cannot wrap family: " + family + " as a Sketch");
@@ -252,7 +270,9 @@ public abstract class Sketch {
* of entries.
*/
public static int getMaxCompactSketchBytes(final int numberOfEntries) {
- return (numberOfEntries << 3) + (Family.COMPACT.getMaxPreLongs() << 3);
+ if (numberOfEntries == 0) { return 8; }
+ if (numberOfEntries == 1) { return 16; }
+ return (numberOfEntries << 3) + 24;
}
/**
@@ -623,7 +643,7 @@ public abstract class Sketch {
}
/**
- * Instantiates a Heap Sketch from Memory.
+ * Instantiates a Heap Sketch from Memory. SerVer 1 & 2 already handled.
* @param famID the Family ID
* @param ordered true if the sketch is of the Compact family and ordered
* @param srcMem <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
@@ -631,15 +651,24 @@ public abstract class Sketch {
* The seed required to instantiate a non-compact sketch.
* @return a Sketch
*/
- private static final Sketch constructHeapSketch(final byte famID, final boolean ordered,
- final Memory srcMem, final long seed) {
- final boolean compact = (srcMem.getByte(FLAGS_BYTE) & COMPACT_FLAG_MASK) != 0;
- final Family family = idToFamily(famID);
+ private static final Sketch heapifyFromMemory(final Memory srcMem, final long seed) {
+ final byte familyID = srcMem.getByte(FAMILY_BYTE);
+ final int preLongs = PreambleUtil.extractPreLongs(srcMem);
+ final int flags = PreambleUtil.extractFlags(srcMem);
+ final boolean orderedFlag = (flags & ORDERED_FLAG_MASK) != 0;
+ final boolean compactFlag = (flags & COMPACT_FLAG_MASK) != 0;
+
+ final Family family = idToFamily(familyID);
+ final long cap = srcMem.getCapacity();
+ if (cap < 8) {
+ throw new SketchesArgumentException(
+ "Corrupted: valid sketch must be at least 8 bytes.");
+ }
switch (family) {
case ALPHA: {
- if (compact) {
- throw new SketchesArgumentException("Possibly Corrupted " + family
- + " image: cannot be compact");
+ if (compactFlag) {
+ throw new SketchesArgumentException(
+ "Corrupted: ALPHA family image: cannot be compact");
}
return HeapAlphaSketch.heapifyInstance(srcMem, seed);
}
@@ -647,16 +676,35 @@ public abstract class Sketch {
return HeapQuickSelectSketch.heapifyInstance(srcMem, seed);
}
case COMPACT: {
- if (!compact) {
- throw new SketchesArgumentException("Possibly Corrupted " + family
- + " image: must be compact");
+ if (!compactFlag) {
+ throw new SketchesArgumentException(
+ "Corrupted: COMPACT family sketch image must have compact flag set");
+ }
+ final boolean readOnly = (flags & READ_ONLY_FLAG_MASK) != 0;
+ if (!readOnly) {
+ throw new SketchesArgumentException(
+ "Corrupted: COMPACT family sketch image must have Read-Only flag set");
+ }
+ final boolean empty = PreambleUtil.isEmpty(srcMem); //also checks memCap < 16
+ if (empty) { //empty flag or < 16 bytes
+ return EmptyCompactSketch.getInstance(srcMem);
}
- return ordered ? HeapCompactOrderedSketch.heapifyInstance(srcMem, seed)
+ //cap >= 16 and not emptyFlag. Note older sketches may have missing empty flag.
+ if (preLongs == 1) {
+ final short memSeedHash = (short) extractSeedHash(srcMem);
+ final short computedSeedHash = computeSeedHash(seed);
+ if ((memSeedHash == computedSeedHash) && orderedFlag) { //SINGLE ITEM
+ return SingleItemSketch.heapify(srcMem, seed);
+ } else { //EMPTY
+ return EmptyCompactSketch.getInstance(srcMem);
+ }
+ }
+ return orderedFlag ? HeapCompactOrderedSketch.heapifyInstance(srcMem, seed)
: HeapCompactUnorderedSketch.heapifyInstance(srcMem, seed);
- }
+ } //end of Compact
default: {
- throw new SketchesArgumentException("Sketch cannot heapify family: " + family
- + " as a Sketch");
+ throw new SketchesArgumentException(
+ "Sketch cannot heapify family: " + family + " as a Sketch");
}
}
}
diff --git a/src/main/java/com/yahoo/sketches/theta/UnionImpl.java b/src/main/java/com/yahoo/sketches/theta/UnionImpl.java
index 9a4e6c2..0005e2a 100644
--- a/src/main/java/com/yahoo/sketches/theta/UnionImpl.java
+++ b/src/main/java/com/yahoo/sketches/theta/UnionImpl.java
@@ -27,7 +27,6 @@ import static com.yahoo.sketches.theta.PreambleUtil.FLAGS_BYTE;
import static com.yahoo.sketches.theta.PreambleUtil.LG_ARR_LONGS_BYTE;
import static com.yahoo.sketches.theta.PreambleUtil.ORDERED_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.PREAMBLE_LONGS_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.READ_ONLY_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.RETAINED_ENTRIES_INT;
import static com.yahoo.sketches.theta.PreambleUtil.SEED_HASH_SHORT;
import static com.yahoo.sketches.theta.PreambleUtil.SER_VER_BYTE;
@@ -324,40 +323,52 @@ final class UnionImpl extends Union {
@Override
public void update(final Memory skMem) {
- //UNION Empty Rule: AND the empty states
if (skMem == null) { return; }
final int cap = (int)skMem.getCapacity();
+ if (cap < 16) { return; } //empty or garbage
+ if (cap == 16) {
+ final long hash = skMem.getLong(8);
+ if (hash == 0) { return; } //hash cannot be zero, must be empty
+ }
+ if (SingleItemSketch.testPre0SeedHash(skMem.getLong(0), seedHash_)) {
+ update(skMem.getLong(8));
+ return;
+ }
+
final int fam = skMem.getByte(FAMILY_BYTE);
final int serVer = skMem.getByte(SER_VER_BYTE);
- if (serVer == 1) { //very old SetSketch, which is compact and ordered
- if (fam != 3) { //the original SetSketch
+
+ if (serVer == 3) { //The OpenSource sketches
+ if ((fam < 1) || (fam > 3)) {
throw new SketchesArgumentException(
- "Family must be old SET_SKETCH: " + Family.idToFamily(fam));
+ "Family must be Alpha, QuickSelect, or Compact: " + Family.idToFamily(fam));
}
- if (cap <= 24) { return; } //empty
- processVer1(skMem);
+ Util.checkSeedHashes(seedHash_, skMem.getShort(SEED_HASH_SHORT));
+ processVer3(skMem);
+ return;
}
- else if (serVer == 2) { //older SetSketch, which is compact and ordered
+
+ if (serVer == 2) { //older SetSketch, which is compact and ordered
if (fam != 3) { //the original SetSketch
throw new SketchesArgumentException(
"Family must be old SET_SKETCH: " + Family.idToFamily(fam));
}
- if (cap <= 8) { return; } //empty
Util.checkSeedHashes(seedHash_, skMem.getShort(SEED_HASH_SHORT));
processVer2(skMem);
+ return;
}
- else if (serVer == 3) { //The OpenSource sketches
- if ((fam < 1) || (fam > 3)) {
+
+ if (serVer == 1) { //very old SetSketch, which is compact and ordered
+ if (fam != 3) { //the original SetSketch
throw new SketchesArgumentException(
- "Family must be Alpha, QuickSelect, or Compact: " + Family.idToFamily(fam));
+ "Family must be old SET_SKETCH: " + Family.idToFamily(fam));
}
- if (cap <= 8) { return; } //empty and Theta = 1.0
- Util.checkSeedHashes(seedHash_, skMem.getShort(SEED_HASH_SHORT));
- processVer3(skMem);
- }
- else {
- throw new SketchesArgumentException("SerVer is unknown: " + serVer);
+ if (cap <= 24) { return; } //empty
+ processVer1(skMem);
+ return;
}
+
+ throw new SketchesArgumentException("SerVer is unknown: " + serVer);
}
@Override
@@ -484,15 +495,9 @@ final class UnionImpl extends Union {
final int preLongs = skMem.getByte(PREAMBLE_LONGS_BYTE) & 0X3F;
final int curCountIn;
final long thetaLongIn;
- final int flags = skMem.getByte(FLAGS_BYTE) & 0X3F;
- if (preLongs == 1) { //SingleItemSketch if not empty, Read-Only, Compact and Ordered
- if (flags == (READ_ONLY_FLAG_MASK | COMPACT_FLAG_MASK | ORDERED_FLAG_MASK)) { //nonEmpty Singleton
- curCountIn = 1;
- thetaLongIn = Long.MAX_VALUE;
- //fall through
- } else {
- return; //otherwise an empty sketch {1.0, 0, T}. Nothing changed
- }
+
+ if (preLongs == 1) { //SingleItem already handled. Treat as empty
+ return;
}
else if (preLongs == 2) {
//curCount has to be > 0 and exact mode. Cannot be from intersection. Not empty.
diff --git a/src/main/java/com/yahoo/sketches/theta/UpdateSketch.java b/src/main/java/com/yahoo/sketches/theta/UpdateSketch.java
index ff4beab..6029457 100644
--- a/src/main/java/com/yahoo/sketches/theta/UpdateSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/UpdateSketch.java
@@ -22,6 +22,8 @@ package com.yahoo.sketches.theta;
import static com.yahoo.sketches.Util.DEFAULT_UPDATE_SEED;
import static com.yahoo.sketches.Util.MIN_LG_NOM_LONGS;
import static com.yahoo.sketches.hash.MurmurHash3.hash;
+import static com.yahoo.sketches.theta.CompactSketch.compactCache;
+import static com.yahoo.sketches.theta.CompactSketch.loadCompactMemory;
import static com.yahoo.sketches.theta.PreambleUtil.BIG_ENDIAN_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.COMPACT_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.FAMILY_BYTE;
@@ -135,30 +137,84 @@ public abstract class UpdateSketch extends Sketch {
@Override
public CompactSketch compact(final boolean dstOrdered, final WritableMemory dstMem) {
- CompactSketch sketchOut = null;
- final int sw = (dstOrdered ? 2 : 0) | ((dstMem != null) ? 1 : 0);
- switch (sw) {
- case 0: { //dst not ordered, dstMem == null
- sketchOut = HeapCompactUnorderedSketch.compact(this);
- break;
+ final int curCount = this.getRetainedEntries(true);
+ long thetaLong = getThetaLong();
+ thetaLong = Sketch.thetaOnCompact(isEmpty(), curCount, thetaLong);
+ final boolean empty = Sketch.emptyOnCompact(curCount, thetaLong);
+ if (empty) {
+ final EmptyCompactSketch sk = EmptyCompactSketch.getInstance();
+ if (dstMem != null) {
+ dstMem.putByteArray(0, sk.toByteArray(), 0, 8);
}
- case 1: { //dst not ordered, dstMem == valid
- sketchOut = DirectCompactUnorderedSketch.compact(this, dstMem);
- break;
- }
- case 2: { //dst ordered, dstMem == null
- sketchOut = HeapCompactOrderedSketch.compact(this);
- break;
- }
- case 3: { //dst ordered, dstMem == valid
- sketchOut = DirectCompactOrderedSketch.compact(this, dstMem);
- break;
+ return sk;
+ }
+ //not empty
+ if ((thetaLong == Long.MAX_VALUE) && (curCount == 1)) {
+ final long[] cache = getCache();
+ final long[] cacheOut = compactCache(cache, curCount, thetaLong, dstOrdered);
+ final long hash = cacheOut[0];
+ final SingleItemSketch sis = new SingleItemSketch(hash, getSeedHash());
+ if (dstMem != null) {
+ dstMem.putByteArray(0, sis.toByteArray(), 0, 16);
}
- //default: //This cannot happen and cannot be tested
+ return new SingleItemSketch(hash, getSeedHash());
+ }
+ if (dstMem == null) {
+ return compactHeap(this, dstOrdered, curCount, thetaLong);
+ } else {
+ return compactDirect(this, dstMem, dstOrdered, curCount, thetaLong);
+ }
+ }
+
+ /**
+ * Converts the given UpdateSketch to a compact form.
+ * EmptyCompactSketch and SingleItemSketch have already been checked.
+ * @param sketch the given UpdateSketch
+ * @param ordered true if the destination is to be ordered.
+ * @param curCount the number of retained entries.
+ * @param thetaLong the value of theta.
+ * @return a CompactSketch
+ */
+ private static CompactSketch compactHeap(final UpdateSketch sketch, final boolean ordered,
+ final int curCount, final long thetaLong) {
+ final short seedHash = sketch.getSeedHash();
+ final long[] cache = sketch.getCache();
+ final long[] cacheOut = CompactSketch.compactCache(cache, curCount, thetaLong, ordered);
+ if (ordered) {
+ return new HeapCompactOrderedSketch(cacheOut, false, seedHash, curCount, thetaLong);
+ } else {
+ return new HeapCompactUnorderedSketch(cacheOut, false, seedHash, curCount, thetaLong);
}
- return sketchOut;
}
+ /**
+ * Converts the given UpdateSketch to a compact form.
+ * EmptyCompactSketch and SingleItemSketch have already been checked.
+ * @param sketch the given UpdateSketch
+ * @param dstMem the given destination Memory. This clears it before use.
+ * @param ordered true if the destination is to be ordered.
+ * @param curCount the number of retained entries.
+ * @param thetaLong the value of theta.
+ * @return a CompactSketch.
+ */
+ static CompactSketch compactDirect(final UpdateSketch sketch,
+ final WritableMemory dstMem, final boolean ordered, final int curCount, final long thetaLong) {
+ final int preLongs = computeCompactPreLongs(thetaLong, false, curCount);
+ final short seedHash = sketch.getSeedHash();
+ final long[] cache = sketch.getCache();
+ final long[] compactCache = CompactSketch.compactCache(cache, curCount, thetaLong, ordered);
+ if (ordered) {
+ final byte flags = (byte)(READ_ONLY_FLAG_MASK | COMPACT_FLAG_MASK | ORDERED_FLAG_MASK);
+ loadCompactMemory(compactCache, seedHash, curCount, thetaLong, dstMem, flags, preLongs);
+ return new DirectCompactOrderedSketch(dstMem);
+ } else {
+ final byte flags = (byte)(READ_ONLY_FLAG_MASK | COMPACT_FLAG_MASK);
+ loadCompactMemory(compactCache, seedHash, curCount, thetaLong, dstMem, flags, preLongs);
+ return new DirectCompactUnorderedSketch(dstMem);
+ }
+ }
+
+
@Override
public boolean isCompact() {
return false;
diff --git a/src/test/java/com/yahoo/sketches/theta/BackwardConversions.java b/src/test/java/com/yahoo/sketches/theta/BackwardConversions.java
new file mode 100644
index 0000000..f4a8986
--- /dev/null
+++ b/src/test/java/com/yahoo/sketches/theta/BackwardConversions.java
@@ -0,0 +1,232 @@
+/*
+ * 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 com.yahoo.sketches.theta;
+
+import com.yahoo.memory.Memory;
+import com.yahoo.memory.WritableMemory;
+import com.yahoo.sketches.SketchesArgumentException;
+import com.yahoo.sketches.Util;
+
+/**
+ * This class converts current compact sketches into prior SerVer 1 and SerVer 2 format for testing.
+ *
+ * @author Lee Rhodes
+ */
+public class BackwardConversions {
+
+ /**
+ * Converts a SerVer3 ordered, heap CompactSketch to a SerVer1 ordered, SetSketch in Memory.
+ * This is exclusively for testing purposes.
+ *
+ * <p>V1 dates from roughly Aug 2014 to about May 2015.
+ * The library at that time had an early Theta sketch with set operations based on ByteBuffer,
+ * the Alpha sketch, and an early HLL sketch. It also had an early adaptor for Pig.
+ * It also had code for the even earlier CountUniqueSketch (for backward compatibility),
+ * which was the bucket sketch based on Giroire.
+ *
+ * <p><b>Serialization:</b></p>
+ * <pre>
+ * Long || Start Byte Adr:
+ * Adr:
+ * || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+ * 0 || | Flags | LgResize | LgArr | lgNom | SkType | SerVer | MD_LONGS |
+ *
+ * || 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 |
+ * 1 || | ------------CurCount-------------- |
+ *
+ * || 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
+ * 2 || --------------------------THETA_LONG------------------------------ |
+ *
+ * || | 24 |
+ * 3 || ----------------------Start of Long Array------------------------ |
+ * </pre>
+ *
+ * <ul>
+ * <li>The serialization for V1 was always to a compact form (no hash table spaces).</li>
+ * <li><i>MD_LONGS</i> (Metadata Longs, now Preamble Longs) was always 3.</li>
+ * <li><i>SerVer</i> is always 1.</li>
+ * <li>The <i>SkType</i> had three values: 1,2,3 for Alpha, QuickSelect, and SetSketch,
+ * repectively.</li>
+ * <li>Bytes <i>lgNom</i> and <i>lgArr</i> were only used by the QS and Alpha sketches.</li>
+ * <li>V1 <i>LgResize</i> (2 bits) was only relevant to the Alpha and QS sketches.</li>
+ * <li>The flags byte is in byte 6 (moved to 5 in V2).</li>
+ * <li>The only flag bits are BE(bit0)=0, and Read-Only(bit1)=1. Read-only was only set for the
+ * SetSketch.</li>
+ * <li>There is no seedHash.</li>
+ * <li>There is no concept of p-sampling so bytes 12-15 of Pre1 are empty.</li>
+ * <li>The determination of empty is when both curCount=0 and thetaLong = Long.MAX_VALUE.</li>
+ * </ul>
+ *
+ * @param skV3 a SerVer3, ordered CompactSketch
+ * @return a SerVer1 SetSketch as Memory object.
+ */
+ public static Memory convertSerVer3toSerVer1(CompactSketch skV3) {
+ //Check input sketch
+ boolean validIn = skV3.isCompact() && skV3.isOrdered() && !skV3.hasMemory();
+ if (!validIn) {
+ throw new SketchesArgumentException("Invalid input sketch.");
+ }
+
+ //Build V1 SetSketch in memory
+ int curCount = skV3.getRetainedEntries(true);
+ WritableMemory wmem = WritableMemory.allocate((3 + curCount) << 3);
+ //Pre0
+ wmem.putByte(0, (byte) 3); //preLongs
+ wmem.putByte(1, (byte) 1); //SerVer
+ wmem.putByte(2, (byte) 3); //Compact (SetSketch)
+ wmem.putByte(6, (byte) 2); //Flags ReadOnly, LE
+ //Pre1
+ wmem.putInt(8, curCount);
+ //Pre2
+ wmem.putLong(16, skV3.getThetaLong());
+ //Data
+ if (curCount > 0) {
+ wmem.putLongArray(24, skV3.getCache(), 0, curCount);
+ }
+ return wmem;
+ }
+
+ /**
+ * Converts a SerVer3 ordered, heap CompactSketch to a SerVer2 ordered, SetSketch in Memory.
+ * This is exclusively for testing purposes.
+ *
+ * <p>V2 is short-lived and dates from roughly Mid May 2015 to about June 1st, 2015.
+ * (V3 was created about June 15th in preparation for OpenSource in July.)
+ * The Theta sketch had evolved but still based on ByteBuffer. There was an UpdateSketch,
+ * the Alpha sketch, and the early HLL sketch. It also had an early adaptor for Pig.
+ *
+ *
+ * <p><b>Serialization:</b></p>
+ * <pre>
+ * Long || Start Byte Adr:
+ * Adr:
+ * || 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
+ * 0 || Seed Hash | Flags | lgArr | lgNom | SkType | SerVer | MD_LONGS + RR |
+ *
+ * || 15 | 14 | 13 | 12 | 11 | 10 | 9 | 8 |
+ * 1 || --------------p-------------- | ---------Retained Entries Count-------- |
+ *
+ * || 23 | 22 | 21 | 20 | 19 | 18 | 17 | 16 |
+ * 2 || --------------------------THETA_LONG----------------------------------- |
+ *
+ * || | 24 |
+ * 3 || ----------Start of Long Array, could be at 2 or 3 -------------------- |
+ * </pre>
+ *
+ * <ul>
+ * <li>The serialization for V2 was always to a compact form (no hash table spaces).</li>
+ * <li><i>MD_LONGS</i> low 6 bits: 1 (Empty), 2 (Exact), 3 (Estimating).</li>
+ * <li><i>SerVer</i> is always 2.</li>
+ * <li>The <i>SkType</i> had 4 values: 1,2,3,4; see below.</li>
+ * <li>Bytes <i>lgNom</i> and <i>lgArr</i> were only used by the QS and Alpha sketches.</li>
+ * <li>V2 <i>LgResize</i> top 2 bits if byte 0. Only relevant to the Alpha and QS sketches.</li>
+ * <li>The flags byte is in byte 5.</li>
+ * <li>The flag bits are specified below.</li>
+ * <li>There is a seedHash in bytes 6-7.</li>
+ * <li>p-sampling is bytes 12-15 of Pre1.</li>
+ * <li>The determination of empty based on the sketch field empty_.</li>
+ * </ul>
+ * <pre>
+ * // Metadata byte Addresses
+ * private static final int METADATA_LONGS_BYTE = 0; //low 6 bits
+ * private static final int LG_RESIZE_RATIO_BYTE = 0; //upper 2 bits
+ * private static final int SER_VER_BYTE = 1;
+ * private static final int SKETCH_TYPE_BYTE = 2;
+ * private static final int LG_NOM_LONGS_BYTE = 3;
+ * private static final int LG_ARR_LONGS_BYTE = 4;
+ * private static final int FLAGS_BYTE = 5;
+ * private static final int SEED_HASH_SHORT = 6; //byte 6,7
+ * private static final int RETAINED_ENTRIES_COUNT_INT = 8; //4 byte aligned
+ * private static final int P_FLOAT = 12; //4 byte aligned
+ * private static final int THETA_LONG = 16; //8-byte aligned
+ * //Backward compatibility
+ * private static final int FLAGS_BYTE_V1 = 6;
+ * private static final int LG_RESIZE_RATIO_BYTE_V1 = 5;
+ *
+ * // Constant Values
+ * static final int SER_VER = 2;
+ * static final int ALPHA_SKETCH = 1; //SKETCH_TYPE_BYTE
+ * static final int QUICK_SELECT_SKETCH = 2;
+ * static final int SET_SKETCH = 3;
+ * static final int BUFFERED_QUICK_SELECT_SKETCH = 4;
+ * static final String[] SKETCH_TYPE_STR =
+ * { "None", "AlphaSketch", "QuickSelectSketch", "SetSketch", "BufferedQuickSelectSketch" };
+ *
+ * // flag bit masks
+ * static final int BIG_ENDIAN_FLAG_MASK = 1;
+ * static final int READ_ONLY_FLAG_MASK = 2;
+ * static final int EMPTY_FLAG_MASK = 4;
+ * static final int NO_REBUILD_FLAG_MASK = 8;
+ * static final int UNORDERED_FLAG_MASK = 16;
+ * </pre>
+ *
+ * @param skV3 a SerVer3, ordered CompactSketch
+ * @param seed used for checking the seed hash (if one exists).
+ * @return a SerVer2 SetSketch as Memory object.
+ */
+ public static Memory convertSerVer3toSerVer2(CompactSketch skV3, long seed) {
+ short seedHash = Util.computeSeedHash(seed);
+ WritableMemory wmem = null;
+
+ if (skV3 instanceof EmptyCompactSketch) {
+ wmem = WritableMemory.allocate(8);
+ wmem.putByte(0, (byte) 1); //preLongs
+ wmem.putByte(1, (byte) 2); //SerVer
+ wmem.putByte(2, (byte) 3); //SetSketch
+ byte flags = (byte) 0xE; //NoRebuild, Empty, ReadOnly, LE
+ wmem.putByte(5, flags);
+ wmem.putShort(6, seedHash);
+ return wmem;
+ }
+ if (skV3 instanceof SingleItemSketch) {
+ SingleItemSketch sis = (SingleItemSketch) skV3;
+ wmem = WritableMemory.allocate(16);
+ wmem.putByte(0, (byte) 1); //preLongs
+ wmem.putByte(1, (byte) 2); //SerVer
+ wmem.putByte(2, (byte) 3); //SetSketch
+ byte flags = (byte) 0xA; //NoRebuild, notEmpty, ReadOnly, LE
+ wmem.putByte(5, flags);
+ wmem.putShort(6, seedHash);
+ wmem.putInt(8, 1);
+ long[] arr = sis.getCache();
+ wmem.putLong(16, arr[0]);
+ return wmem;
+ }
+ //General CompactSketch
+ int preLongs = skV3.getCurrentPreambleLongs(true);
+ int entries = skV3.getRetainedEntries();
+ boolean unordered = !(skV3.isOrdered());
+ byte flags = (byte) (0xA | (unordered ? 16 : 0)); //Unordered, NoRebuild, notEmpty, ReadOnly, LE
+ wmem = WritableMemory.allocate((preLongs + entries) << 3);
+ wmem.putByte(0, (byte) preLongs); //preLongs
+ wmem.putByte(1, (byte) 2); //SerVer
+ wmem.putByte(2, (byte) 3); //SetSketch
+
+ wmem.putByte(5, flags);
+ wmem.putShort(6, seedHash);
+ wmem.putInt(8, entries);
+ if (preLongs == 3) {
+ wmem.putLong(16, skV3.getThetaLong());
+ }
+ long[] arr = skV3.getCache();
+ wmem.putLongArray(preLongs*8, arr, 0, entries);
+ return wmem;
+ }
+}
diff --git a/src/test/java/com/yahoo/sketches/theta/CompactSketchTest.java b/src/test/java/com/yahoo/sketches/theta/CompactSketchTest.java
index 61ca205..c7bfe19 100644
--- a/src/test/java/com/yahoo/sketches/theta/CompactSketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/CompactSketchTest.java
@@ -41,172 +41,140 @@ public class CompactSketchTest {
@Test
public void checkHeapifyWrap() {
int k = 4096;
- checkHeapifyWrap(k, 0); //empty
- checkHeapifyWrap(k, k); //exact
- checkHeapifyWrap(k, 4 * k); //estimating
+ final boolean ordered = true;
+ checkHeapifyWrap(k, 0, ordered);
+ checkHeapifyWrap(k, 1, ordered);
+ checkHeapifyWrap(k, 1, !ordered);
+ checkHeapifyWrap(k, k, ordered); //exact
+ checkHeapifyWrap(k, k, !ordered); //exact
+ checkHeapifyWrap(k, 4 * k, ordered); //estimating
+ checkHeapifyWrap(k, 4 * k, !ordered); //estimating
}
//test combinations of compact ordered/not ordered and heap/direct
- public void checkHeapifyWrap(int k, int u) {
+ public void checkHeapifyWrap(int k, int u, boolean ordered) {
UpdateSketch usk = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u; i++) {
+
+ for (int i=0; i<u; i++) { //populate update sketch
usk.update(i);
}
- assertFalse(usk.isDirect());
- assertFalse(usk.hasMemory());
- double uskEst = usk.getEstimate();
- assertEquals(uskEst, u, 0.05 * u);
- int uskCount = usk.getRetainedEntries(true);
- short uskSeedHash = usk.getSeedHash();
- long uskThetaLong = usk.getThetaLong();
-
- CompactSketch csk, csk2, csk3;
- byte[] byteArray;
- boolean ordered = true;
- boolean compact = true;
- /****/
- csk = usk.compact( !ordered, null); //NOT ORDERED
- assertEquals(csk.getClass().getSimpleName(), "HeapCompactUnorderedSketch");
- assertFalse(csk.isDirect());
- assertFalse(csk.hasMemory());
- assertTrue(csk.isCompact());
- assertFalse(csk.isOrdered());
-
- assertEquals(csk.getFamily(), Family.COMPACT);
- //println("Ord: "+(!ordered)+", Mem: "+"Null");
- //println(csk.toString(true, true, 8, true));
- //println(PreambleUtil.toString(byteArray));
-
- //put image in memory, check heapify
- Memory srcMem = Memory.wrap(csk.toByteArray());
- csk2 = (CompactSketch) Sketch.heapify(srcMem);
- //println(csk2.toString(true, true, 8, true));
- double csk2est = csk2.getEstimate();
- assertEquals(csk2est, uskEst, 0.0);
- assertEquals(csk2.getRetainedEntries(true), uskCount);
- assertEquals(csk2.getSeedHash(), uskSeedHash);
- assertEquals(csk2.getThetaLong(), uskThetaLong);
- assertNull(csk2.getMemory());
- assertFalse(csk2.isOrdered()); //CHECK NOT ORDERED
- assertNotNull(csk2.getCache());
-
- /****/
- csk = usk.compact( ordered, null); //ORDERED
- assertEquals(csk.getClass().getSimpleName(), "HeapCompactOrderedSketch");
- assertFalse(csk.isDirect());
- assertFalse(csk.hasMemory());
- assertTrue(csk.isCompact());
- assertTrue(csk.isOrdered()); //CHECK ORDERED
-
-
- Memory srcMem2 = Memory.wrap(csk.toByteArray());
- csk3 = (CompactSketch)Sketch.heapify(srcMem2);
- double csk3est = csk3.getEstimate();
- assertEquals(csk3est, uskEst, 0.0);
-
- assertEquals(csk3.getRetainedEntries(true), uskCount);
- assertEquals(csk3.getSeedHash(), uskSeedHash);
- assertEquals(csk3.getThetaLong(), uskThetaLong);
- assertNull(csk3.getMemory());
- assertFalse(csk3.isDirect());
- assertFalse(csk3.hasMemory());
- assertTrue(csk3.isOrdered());
- assertNotNull(csk3.getCache());
-
- /****/
+ /****ON HEAP MEMORY -- HEAPIFY****/
+ CompactSketch refSk = usk.compact(ordered, null);
+ byte[] barr = refSk.toByteArray();
+ Memory srcMem = Memory.wrap(barr);
+ CompactSketch testSk = (CompactSketch) Sketch.heapify(srcMem);
+
+ checkByRange(refSk, testSk, u, ordered);
+
+ /**Via byte[]**/
+ byte[] byteArray = refSk.toByteArray();
+ Memory heapROMem = Memory.wrap(byteArray);
+ testSk = (CompactSketch)Sketch.heapify(heapROMem);
+
+ checkByRange(refSk, testSk, u, ordered);
+
+ /****OFF HEAP MEMORY -- WRAP****/
//Prepare Memory for direct
- int bytes = usk.getCurrentBytes(compact);
- WritableMemory directMem;
- Memory heapROMem;
+ int bytes = usk.getCurrentBytes(true); //for Compact
try (WritableDirectHandle wdh = WritableMemory.allocateDirect(bytes)) {
- directMem = wdh.get();
- //Memory heapMem;
+ WritableMemory directMem = wdh.get();
/**Via CompactSketch.compact**/
- csk = usk.compact(!ordered, directMem); //NOT ORDERED, DIRECT
- assertEquals(csk.getClass().getSimpleName(), "DirectCompactUnorderedSketch");
- assertTrue(csk.hasMemory());
- assertTrue(csk.isDirect());
- assertTrue(csk.hasMemory());
-
- csk2 = (CompactSketch)Sketch.wrap(directMem);
- assertEquals(csk2.getEstimate(), uskEst, 0.0);
-
- assertEquals(csk2.getRetainedEntries(true), uskCount);
- assertEquals(csk2.getSeedHash(), uskSeedHash);
- assertEquals(csk2.getThetaLong(), uskThetaLong);
- assertNotNull(csk2.getMemory());
- assertTrue(csk2.isDirect());
- assertTrue(csk2.hasMemory());
- assertFalse(csk2.isOrdered());
- assertNotNull(csk2.getCache());
-
- csk = usk.compact( !ordered, directMem);
- assertEquals(csk.getClass().getSimpleName(), "DirectCompactUnorderedSketch");
- assertTrue(csk.isDirect());
- assertTrue(csk.hasMemory());
- assertTrue(csk.isCompact());
- assertFalse(csk.isOrdered());
-
- /**Via byte[]**/
- byteArray = csk.toByteArray();
- heapROMem = Memory.wrap(byteArray);
- csk2 = (CompactSketch)Sketch.wrap(heapROMem);
- assertEquals(csk2.getEstimate(), uskEst, 0.0);
-
- assertEquals(csk2.getRetainedEntries(true), uskCount);
- assertEquals(csk2.getSeedHash(), uskSeedHash);
- assertEquals(csk2.getThetaLong(), uskThetaLong);
- assertNotNull(csk2.getMemory());
- assertFalse(csk2.isOrdered());
- assertNotNull(csk2.getCache());
- assertFalse(csk2.isDirect());
- assertTrue(csk2.hasMemory());
+ refSk = usk.compact(ordered, directMem);
+ testSk = (CompactSketch)Sketch.wrap(directMem);
+
+ checkByRange(refSk, testSk, u, ordered);
/**Via CompactSketch.compact**/
- csk = usk.compact( ordered, directMem);
- assertEquals(csk.getClass().getSimpleName(), "DirectCompactOrderedSketch");
- assertTrue(csk.isDirect());
- assertTrue(csk.hasMemory());
- assertTrue(csk.isCompact());
- assertTrue(csk.isOrdered());
-
- csk2 = (CompactSketch)Sketch.wrap(directMem);
- assertEquals(csk2.getEstimate(), uskEst, 0.0);
-
- assertEquals(csk2.getRetainedEntries(true), uskCount);
- assertEquals(csk2.getSeedHash(), uskSeedHash);
- assertEquals(csk2.getThetaLong(), uskThetaLong);
- assertNotNull(csk2.getMemory());
- assertTrue(csk2.isDirect());
- assertTrue(csk2.hasMemory());
- assertTrue(csk2.isOrdered());
- assertNotNull(csk2.getCache());
-
- /**Via byte[]**/
- csk = usk.compact( ordered, directMem);
- assertEquals(csk.getClass().getSimpleName(), "DirectCompactOrderedSketch");
- assertTrue(csk2.isDirect());
- assertTrue(csk2.hasMemory());
-
- byteArray = csk.toByteArray();
- heapROMem = Memory.wrap(byteArray);
- csk2 = (CompactSketch)Sketch.wrap(heapROMem);
- assertEquals(csk2.getEstimate(), uskEst, 0.0);
-
- assertEquals(csk2.getRetainedEntries(true), uskCount);
- assertEquals(csk2.getSeedHash(), uskSeedHash);
- assertEquals(csk2.getThetaLong(), uskThetaLong);
- assertNotNull(csk2.getMemory());
- assertTrue(csk2.isOrdered());
- assertNotNull(csk2.getCache());
- assertFalse(csk2.isDirect());
- assertTrue(csk2.hasMemory());
+ testSk = (CompactSketch)Sketch.wrap(directMem);
+ checkByRange(refSk, testSk, u, ordered);
+ }
+ }
+
+ private static void checkByRange(Sketch refSk, Sketch testSk, int u, boolean ordered) {
+ if (u == 0) {
+ checkEmptySketch(testSk);
+ } else if (u == 1) {
+ checkSingleItemSketch(testSk, refSk);
+ } else {
+ checkOtherCompactSketch(testSk, refSk, ordered);
+ }
+ }
+
+ private static void checkEmptySketch(Sketch testSk) {
+ assertEquals(testSk.getFamily(), Family.COMPACT);
+ assertTrue(testSk instanceof EmptyCompactSketch);
+ assertTrue(testSk.isEmpty());
+ assertTrue(testSk.isOrdered());
+ assertNull(testSk.getMemory());
+ assertFalse(testSk.isDirect());
+ assertFalse(testSk.hasMemory());
+ assertEquals(testSk.getSeedHash(), 0);
+ assertEquals(testSk.getRetainedEntries(true), 0);
+ assertEquals(testSk.getEstimate(), 0.0, 0.0);
+ assertEquals(testSk.getCurrentBytes(true), 8);
+ assertNotNull(testSk.iterator());
+ assertEquals(testSk.toByteArray().length, 8);
+ assertEquals(testSk.getCache().length, 0);
+ assertEquals(testSk.getCurrentPreambleLongs(true), 1);
+ }
+
+ private static void checkSingleItemSketch(Sketch testSk, Sketch refSk) {
+ assertEquals(testSk.getFamily(), Family.COMPACT);
+ assertTrue(testSk instanceof SingleItemSketch);
+ assertFalse(testSk.isEmpty());
+ assertTrue(testSk.isOrdered());
+ assertNull(testSk.getMemory());
+ assertFalse(testSk.isDirect());
+ assertFalse(testSk.hasMemory());
+ assertEquals(testSk.getSeedHash(), refSk.getSeedHash());
+ assertEquals(testSk.getRetainedEntries(true), 1);
+ assertEquals(testSk.getEstimate(), 1.0, 0.0);
+ assertEquals(testSk.getCurrentBytes(true), 16);
+ assertNotNull(testSk.iterator());
+ assertEquals(testSk.toByteArray().length, 16);
+ assertEquals(testSk.getCache().length, 1);
+ assertEquals(testSk.getCurrentPreambleLongs(true), 1);
+ }
+
+ private static void checkOtherCompactSketch(Sketch testSk, Sketch refSk, boolean ordered) {
+ assertEquals(testSk.getFamily(), Family.COMPACT);
+ assertFalse(testSk.isEmpty());
+ assertNotNull(testSk.iterator());
+ assertEquals(testSk.isOrdered(), ordered);
+ if (refSk.hasMemory()) {
+ assertTrue(testSk.hasMemory());
+ assertNotNull(testSk.getMemory());
+ if (ordered) {
+ assertTrue(testSk instanceof DirectCompactOrderedSketch);
+ } else {
+ assertTrue(testSk instanceof DirectCompactUnorderedSketch);
+ }
+ if (refSk.isDirect()) {
+ assertTrue(testSk.isDirect());
+ } else {
+ assertFalse(testSk.isDirect());
+ }
+ } else {
+ assertFalse(testSk.hasMemory());
+ if (ordered) {
+ assertTrue(testSk instanceof HeapCompactOrderedSketch);
+ } else {
+ assertTrue(testSk instanceof HeapCompactUnorderedSketch);
+ }
}
+ assertEquals(testSk.getSeedHash(), refSk.getSeedHash());
+ assertEquals(testSk.getRetainedEntries(true), refSk.getRetainedEntries());
+ assertEquals(testSk.getEstimate(), refSk.getEstimate(), 0.0);
+ assertEquals(testSk.getCurrentBytes(true), refSk.getCurrentBytes(true));
+ assertEquals(testSk.toByteArray().length, refSk.toByteArray().length);
+ assertEquals(testSk.getCache().length, refSk.getCache().length);
+ assertEquals(testSk.getCurrentPreambleLongs(true), refSk.getCurrentPreambleLongs(true));
}
+
@Test(expectedExceptions = SketchesArgumentException.class)
public void checkMemTooSmall() {
int k = 512;
@@ -261,6 +229,27 @@ public class CompactSketchTest {
}
@Test
+ public void checkHeapifySingleItemSketch() {
+ UpdateSketch sk = Sketches.updateSketchBuilder().build();
+ sk.update(1);
+ int bytes = Sketches.getMaxCompactSketchBytes(2); //1 more than needed
+ WritableMemory wmem = WritableMemory.allocate(bytes);
+ sk.compact(false, wmem);
+ Sketch csk = Sketch.heapify(wmem);
+ assertTrue(csk instanceof SingleItemSketch);
+ }
+
+ @Test
+ public void checkHeapifyEmptySketch() {
+ UpdateSketch sk = Sketches.updateSketchBuilder().build();
+ WritableMemory wmem = WritableMemory.allocate(16); //extra bytes
+ sk.compact(false, wmem);
+ PreambleUtil.clearEmpty(wmem); //corrupt to simulate missing empty flag
+ Sketch csk = Sketch.heapify(wmem);
+ assertTrue(csk instanceof EmptyCompactSketch);
+ }
+
+ @Test
public void printlnTest() {
println("PRINTING: "+this.getClass().getName());
}
diff --git a/src/test/java/com/yahoo/sketches/theta/ConcurrentDirectQuickSelectSketchTest.java b/src/test/java/com/yahoo/sketches/theta/ConcurrentDirectQuickSelectSketchTest.java
index 2bb82fa..3b96d42 100644
--- a/src/test/java/com/yahoo/sketches/theta/ConcurrentDirectQuickSelectSketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/ConcurrentDirectQuickSelectSketchTest.java
@@ -438,7 +438,7 @@ public class ConcurrentDirectQuickSelectSketchTest {
assertEquals(csk2.getUpperBound(2), localUB);
assertTrue(csk2.isEmpty());
assertFalse(csk2.isEstimationMode());
- assertEquals(csk2.getClass().getSimpleName(), "DirectCompactUnorderedSketch");
+ assertTrue(csk2 instanceof EmptyCompactSketch);
CompactSketch csk3 = shared.compact(true, mem2);
csk3.toString(false, true, 0, false);
@@ -448,7 +448,7 @@ public class ConcurrentDirectQuickSelectSketchTest {
assertEquals(csk3.getUpperBound(2), localUB);
assertTrue(csk3.isEmpty());
assertFalse(csk3.isEstimationMode());
- assertEquals(csk3.getClass().getSimpleName(), "DirectCompactOrderedSketch");
+ assertTrue(csk2 instanceof EmptyCompactSketch);
}
}
diff --git a/src/test/java/com/yahoo/sketches/theta/ConcurrentHeapQuickSelectSketchTest.java b/src/test/java/com/yahoo/sketches/theta/ConcurrentHeapQuickSelectSketchTest.java
index 1e800a2..362be6e 100644
--- a/src/test/java/com/yahoo/sketches/theta/ConcurrentHeapQuickSelectSketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/ConcurrentHeapQuickSelectSketchTest.java
@@ -362,7 +362,7 @@ public class ConcurrentHeapQuickSelectSketchTest {
//empty
local.toString(false, true, 0, false);
boolean estimating = false;
- assertEquals(local.getClass().getSimpleName(), "ConcurrentHeapThetaBuffer");
+ assertTrue(local instanceof ConcurrentHeapThetaBuffer);
double localEst = local.getEstimate();
double localLB = local.getLowerBound(2);
double localUB = local.getUpperBound(2);
@@ -381,7 +381,7 @@ public class ConcurrentHeapQuickSelectSketchTest {
assertEquals(csk2.getUpperBound(2), localUB);
assertEquals(csk2.isEmpty(), true);
assertEquals(csk2.isEstimationMode(), estimating);
- assertEquals(csk2.getClass().getSimpleName(), "DirectCompactUnorderedSketch");
+ assertTrue(csk2 instanceof EmptyCompactSketch);
CompactSketch csk3 = shared.compact(true, mem2);
csk3.toString(false, true, 0, false);
@@ -391,7 +391,7 @@ public class ConcurrentHeapQuickSelectSketchTest {
assertEquals(csk3.getUpperBound(2), localUB);
assertEquals(csk3.isEmpty(), true);
assertEquals(csk3.isEstimationMode(), estimating);
- assertEquals(csk3.getClass().getSimpleName(), "DirectCompactOrderedSketch");
+ assertTrue(csk3 instanceof EmptyCompactSketch);
}
@Test
@@ -576,7 +576,7 @@ public class ConcurrentHeapQuickSelectSketchTest {
//empty
local.toString(false, true, 0, false); //exercise toString
- assertEquals(local.getClass().getSimpleName(), "ConcurrentHeapThetaBuffer");
+ assertTrue(local instanceof ConcurrentHeapThetaBuffer);
double localEst = local.getEstimate();
double localLB = local.getLowerBound(2);
double uskUB = local.getUpperBound(2);
@@ -593,7 +593,7 @@ public class ConcurrentHeapQuickSelectSketchTest {
assertEquals(csk2.getUpperBound(2), uskUB);
assertTrue(csk2.isEmpty());
assertFalse(csk2.isEstimationMode());
- assertEquals(csk2.getClass().getSimpleName(), "DirectCompactUnorderedSketch");
+ assertTrue(csk2 instanceof EmptyCompactSketch);
CompactSketch csk3 = shared.compact(true, mem2);
csk3.toString(false, true, 0, false);
@@ -603,7 +603,7 @@ public class ConcurrentHeapQuickSelectSketchTest {
assertEquals(csk3.getUpperBound(2), uskUB);
assertTrue(csk3.isEmpty());
assertFalse(csk3.isEstimationMode());
- assertEquals(csk3.getClass().getSimpleName(), "DirectCompactOrderedSketch");
+ assertTrue(csk2 instanceof EmptyCompactSketch);
}
@Test(expectedExceptions = SketchesArgumentException.class)
diff --git a/src/test/java/com/yahoo/sketches/theta/DirectQuickSelectSketchTest.java b/src/test/java/com/yahoo/sketches/theta/DirectQuickSelectSketchTest.java
index 800ea5a..9c33ef1 100644
--- a/src/test/java/com/yahoo/sketches/theta/DirectQuickSelectSketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/DirectQuickSelectSketchTest.java
@@ -388,7 +388,7 @@ public class DirectQuickSelectSketchTest {
assertEquals(csk2.getUpperBound(2), uskUB);
assertEquals(csk2.isEmpty(), true);
assertEquals(csk2.isEstimationMode(), false);
- assertEquals(csk2.getClass().getSimpleName(), "DirectCompactUnorderedSketch");
+ assertEquals(csk2.getClass().getSimpleName(), "EmptyCompactSketch");
CompactSketch csk3 = usk.compact(true, mem2);
csk3.toString(false, true, 0, false);
@@ -398,7 +398,7 @@ public class DirectQuickSelectSketchTest {
assertEquals(csk3.getUpperBound(2), uskUB);
assertEquals(csk3.isEmpty(), true);
assertEquals(csk3.isEstimationMode(), false);
- assertEquals(csk3.getClass().getSimpleName(), "DirectCompactOrderedSketch");
+ assertEquals(csk3.getClass().getSimpleName(), "EmptyCompactSketch");
}
}
diff --git a/src/test/java/com/yahoo/sketches/theta/DirectUnionTest.java b/src/test/java/com/yahoo/sketches/theta/DirectUnionTest.java
index 20001ae..27374d6 100644
--- a/src/test/java/com/yahoo/sketches/theta/DirectUnionTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/DirectUnionTest.java
@@ -19,8 +19,8 @@
package com.yahoo.sketches.theta;
-import static com.yahoo.sketches.theta.ForwardCompatibilityTest.convertSerV3toSerV1;
-import static com.yahoo.sketches.theta.ForwardCompatibilityTest.convertSerV3toSerV2;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer1;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer2;
import static com.yahoo.sketches.theta.HeapUnionTest.testAllCompactForms;
import static com.yahoo.sketches.theta.PreambleUtil.SER_VER_BYTE;
import static com.yahoo.sketches.theta.SetOperation.getMaxUnionBytes;
@@ -53,12 +53,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<(u/2); i++)
- {
+ for (int i=0; i<(u/2); i++) {
usk1.update(i); //256
}
- for (int i=u/2; i<u; i++)
- {
+ for (int i=u/2; i<u; i++) {
usk2.update(i); //256 no overlap
}
@@ -82,12 +80,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<(u/2); i++)
- {
+ for (int i=0; i<(u/2); i++) {
usk1.update(i); //2*k
}
- for (int i=u/2; i<u; i++)
- {
+ for (int i=u/2; i<u; i++) {
usk2.update(i); //2*k no overlap
}
@@ -109,12 +105,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<(u/2); i++)
- {
+ for (int i=0; i<(u/2); i++) {
usk1.update(i); //256
}
- for (int i=0; i<u ; i++)
- {
+ for (int i=0; i<u ; i++) {
usk2.update(i); //512, 256 overlapped
}
@@ -138,12 +132,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<(u/2); i++)
- {
+ for (int i=0; i<(u/2); i++) {
usk1.update(i); //256
}
- for (int i=u/2; i<u; i++)
- {
+ for (int i=u/2; i<u; i++) {
usk2.update(i); //256 no overlap
}
@@ -172,12 +164,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<(u/2); i++)
- {
+ for (int i=0; i<(u/2); i++) {
usk1.update(i); //256
}
- for (int i=u/2; i<u; i++)
- {
+ for (int i=u/2; i<u; i++) {
usk2.update(i); //256 no overlap
}
@@ -205,12 +195,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build(); //2k estimating
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(2 * k).build(); //2k exact
- for (int i=0; i<(u/2); i++)
- {
+ for (int i=0; i<(u/2); i++) {
usk1.update(i); //2k
}
- for (int i=u/2; i<u; i++)
- {
+ for (int i=u/2; i<u; i++) {
usk2.update(i); //2k no overlap, exact
}
@@ -236,12 +224,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build(); //2k estimating
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(2 * k).build(); //2k exact for early stop test
- for (int i=0; i<(u/2); i++)
- {
+ for (int i=0; i<(u/2); i++) {
usk1.update(i); //2k estimating
}
- for (int i=u/2; i<u; i++)
- {
+ for (int i=u/2; i<u; i++) {
usk2.update(i); //2k no overlap, exact, will force early stop
}
@@ -277,12 +263,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build(); //2k estimating
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(2 * k).build(); //2k exact for early stop test
- for (int i=0; i<(u/2); i++)
- {
+ for (int i=0; i<(u/2); i++) {
usk1.update(i); //2k estimating
}
- for (int i=u/2; i<u; i++)
- {
+ for (int i=u/2; i<u; i++) {
usk2.update(i); //2k no overlap, exact, will force early stop
}
@@ -319,12 +303,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build(); //2k estimating
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(2 * k).build(); //2k exact for early stop test
- for (int i=0; i<(u/2); i++)
- {
+ for (int i=0; i<(u/2); i++) {
usk1.update(i); //2k estimating
}
- for (int i=u/2; i<u; i++)
- {
+ for (int i=u/2; i<u; i++) {
usk2.update(i); //2k no overlap, exact, will force early stop
}
@@ -361,12 +343,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build(); //2k estimating
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(2 * k).build(); //2k exact for early stop test
- for (int i=0; i<(u/2); i++)
- {
+ for (int i=0; i<(u/2); i++) {
usk1.update(i); //2k estimating
}
- for (int i=u/2; i<u; i++)
- {
+ for (int i=u/2; i<u; i++) {
usk2.update(i); //2k no overlap, exact, will force early stop
}
@@ -448,12 +428,10 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u1; i++)
- {
+ for (int i=0; i<u1; i++) {
usk1.update(i); //2*k
}
- for (int i=u1; i<totU; i++)
- {
+ for (int i=u1; i<totU; i++) {
usk2.update(i); //2*k + 1024 no overlap
}
@@ -484,20 +462,15 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u1; i++)
- {
+ for (int i=0; i<u1; i++) {
usk1.update(i); //2*k
}
- for (int i=u1; i<totU; i++)
- {
+ for (int i=u1; i<totU; i++) {
usk2.update(i); //2*k + 1024 no overlap
}
- WritableMemory skMem1 = WritableMemory.wrap(usk1.compact(true, null).toByteArray());
- WritableMemory skMem2 = WritableMemory.wrap(usk2.compact(true, null).toByteArray());
-
- Memory v1mem1 = convertSerV3toSerV1(skMem1);
- Memory v1mem2 = convertSerV3toSerV1(skMem2);
+ Memory v1mem1 = convertSerVer3toSerVer1(usk1.compact(true, null));
+ Memory v1mem2 = convertSerVer3toSerVer1(usk2.compact(true, null));
WritableMemory uMem = WritableMemory.wrap(new byte[getMaxUnionBytes(k)]); //union memory
Union union = SetOperation.builder().setNominalEntries(k).buildUnion(uMem);
@@ -520,20 +493,15 @@ public class DirectUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u1; i++)
- {
+ for (int i=0; i<u1; i++) {
usk1.update(i); //2*k
}
- for (int i=u1; i<totU; i++)
- {
+ for (int i=u1; i<totU; i++) {
usk2.update(i); //2*k + 1024 no overlap
}
- WritableMemory skMem1 = WritableMemory.wrap(usk1.compact(true, null).toByteArray());
- WritableMemory skMem2 = WritableMemory.wrap(usk2.compact(true, null).toByteArray());
-
- Memory v2mem1 = convertSerV3toSerV2(skMem1);
- Memory v2mem2 = convertSerV3toSerV2(skMem2);
+ Memory v2mem1 = convertSerVer3toSerVer2(usk1.compact(true, null), Util.DEFAULT_UPDATE_SEED);
+ Memory v2mem2 = convertSerVer3toSerVer2(usk2.compact(true, null), Util.DEFAULT_UPDATE_SEED);
WritableMemory uMem = WritableMemory.wrap(new byte[getMaxUnionBytes(k)]); //union memory
Union union = SetOperation.builder().setNominalEntries(k).buildUnion(uMem);
@@ -554,7 +522,7 @@ public class DirectUnionTest {
CompactSketch usk1c = usk1.compact(true, null);
WritableMemory v3mem1 = WritableMemory.wrap(usk1c.toByteArray());
- Memory v1mem1 = convertSerV3toSerV1(v3mem1);
+ Memory v1mem1 = convertSerVer3toSerVer1(usk1c);
WritableMemory uMem = WritableMemory.wrap(new byte[getMaxUnionBytes(k)]); //union memory
Union union = SetOperation.builder().setNominalEntries(k).buildUnion(uMem);
@@ -562,7 +530,7 @@ public class DirectUnionTest {
CompactSketch cOut = union.getResult(true, null);
assertEquals(cOut.getEstimate(), 0.0, 0.0);
- Memory v2mem1 = convertSerV3toSerV2(v3mem1);
+ Memory v2mem1 = convertSerVer3toSerVer2(usk1c, Util.DEFAULT_UPDATE_SEED);
uMem = WritableMemory.wrap(new byte[getMaxUnionBytes(k)]); //union memory
union = SetOperation.builder().setNominalEntries(k).buildUnion(uMem);
@@ -609,6 +577,8 @@ public class DirectUnionTest {
int k = 1 << lgK;
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
+ usk1.update(1);
+ usk1.update(2);
CompactSketch usk1c = usk1.compact(true, null);
WritableMemory v3mem1 = WritableMemory.wrap(usk1c.toByteArray());
//corrupt SerVer
@@ -621,7 +591,6 @@ public class DirectUnionTest {
}
@Test
- //where the granted mem is larger than required
public void checkEmptySerVer2and3() {
int lgK = 12; //4096
int k = 1 << lgK;
@@ -635,7 +604,7 @@ public class DirectUnionTest {
Union union = SetOperation.builder().setNominalEntries(k).buildUnion(uMem);
union.update(v3mem1);
- Memory v2mem1 = convertSerV3toSerV2(v3mem1);
+ Memory v2mem1 = convertSerVer3toSerVer2(usk1c, Util.DEFAULT_UPDATE_SEED);
WritableMemory v2mem2 = WritableMemory.wrap(new byte[16]);
v2mem1.copyTo(0, v2mem2, 0, 8);
diff --git a/src/test/java/com/yahoo/sketches/theta/EmptyTest.java b/src/test/java/com/yahoo/sketches/theta/EmptyTest.java
index 6c229ca..8696610 100644
--- a/src/test/java/com/yahoo/sketches/theta/EmptyTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/EmptyTest.java
@@ -19,12 +19,18 @@
package com.yahoo.sketches.theta;
+import static com.yahoo.sketches.theta.PreambleUtil.COMPACT_FLAG_MASK;
+import static com.yahoo.sketches.theta.PreambleUtil.ORDERED_FLAG_MASK;
+import static com.yahoo.sketches.theta.PreambleUtil.READ_ONLY_FLAG_MASK;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
import org.testng.annotations.Test;
+import com.yahoo.memory.Memory;
+import com.yahoo.memory.WritableMemory;
+
/**
* Empty essentially means that the sketch has never seen data.
@@ -104,9 +110,47 @@ public class EmptyTest {
assertEquals(sk1.compact().toByteArray().length, 8);
}
+ //These 3 tests reproduce a failure mode where an "old" empty sketch of 8 bytes without
+ // its empty-flag bit set is read.
+ @Test
+ public void checkBackwardCompatibility1() {
+ final int k = 16;
+ final int bytes = Sketches.getMaxUnionBytes(k); //288
+ Union union = SetOperation.builder().buildUnion(WritableMemory.allocate(bytes));
+ Memory mem = badEmptySk();
+ Sketch wsk = Sketches.wrapSketch(mem);
+ union.update(wsk); //union has memory
+ }
+
+ @Test
+ public void checkBackwardCompatibility2() {
+ Union union = SetOperation.builder().setNominalEntries(16).buildUnion();
+ Memory mem = badEmptySk();
+ Sketch wsk = Sketches.wrapSketch(mem);
+ union.update(wsk); //heap union
+ }
+
+ @Test
+ public void checkBackwardCompatibility3() {
+ Memory mem = badEmptySk();
+ Sketches.heapifySketch(mem);
+ }
+
+ private static Memory badEmptySk() { //missing the empty bit
+ final long preLongs = 1;
+ final long serVer = 3;
+ final long family = 3; //compact
+ final long flags = (ORDERED_FLAG_MASK | COMPACT_FLAG_MASK | READ_ONLY_FLAG_MASK);
+ final long seedHash = 0x93CC;
+ final long badEmptySk = (seedHash << 48) | (flags << 40)
+ | (family << 16) | (serVer << 8) | preLongs;
+ WritableMemory wmem = WritableMemory.allocate(8);
+ wmem.putLong(0, badEmptySk);
+ return wmem;
+ }
+
/**
- * @param s
- * value to print
+ * @param s value to print
*/
static void println(String s) {
//System.out.println(s); //disable here
diff --git a/src/test/java/com/yahoo/sketches/theta/ForwardCompatibilityTest.java b/src/test/java/com/yahoo/sketches/theta/ForwardCompatibilityTest.java
index a52baa5..8ff5f53 100644
--- a/src/test/java/com/yahoo/sketches/theta/ForwardCompatibilityTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/ForwardCompatibilityTest.java
@@ -19,14 +19,10 @@
package com.yahoo.sketches.theta;
-import static com.yahoo.sketches.hash.MurmurHash3.hash;
-import static com.yahoo.sketches.theta.PreambleUtil.FAMILY_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.FLAGS_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.PREAMBLE_LONGS_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.RETAINED_ENTRIES_INT;
-import static com.yahoo.sketches.theta.PreambleUtil.SER_VER_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.THETA_LONG;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer1;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer2;
import static org.testng.Assert.assertEquals;
+import static org.testng.Assert.assertTrue;
import org.testng.annotations.Test;
@@ -40,24 +36,10 @@ import com.yahoo.sketches.Util;
*/
public class ForwardCompatibilityTest {
-
@Test
- public void checkSerVer1_24Bytes() {
- byte[] byteArray = new byte[24];
- WritableMemory mem = WritableMemory.wrap(byteArray);
- mem.putByte(0, (byte) 3); //mdLongs
- mem.putByte(1, (byte) 1); //SerVer
- mem.putByte(2, (byte) 3); //SketchType = SetSketch
- //byte 3 lgNomLongs not used with SetSketch
- //byte 4 lgArrLongs not used with SetSketch
- //byte 5 lgRR not used with SetSketch
- //byte 6: Flags: b0: BigEnd, b1: ReadOnly
- mem.putByte(6, (byte) 2);
- //byte 7 Not used
- mem.putInt(8, 0); //curCount = 0
- mem.putLong(16, Long.MAX_VALUE);
-
- Memory srcMem = Memory.wrap(byteArray);
+ public void checkSerVer1_Empty() {
+ CompactSketch csk = EmptyCompactSketch.getInstance();
+ Memory srcMem = convertSerVer3toSerVer1(csk);
Sketch sketch = Sketch.heapify(srcMem);
assertEquals(sketch.isEmpty(), true);
assertEquals(sketch.isEstimationMode(), false);
@@ -65,52 +47,27 @@ public class ForwardCompatibilityTest {
assertEquals(sketch.hasMemory(), false);
assertEquals(sketch.isCompact(), true);
assertEquals(sketch.isOrdered(), true);
- String name = sketch.getClass().getSimpleName();
- assertEquals(name, "HeapCompactOrderedSketch");
+ assertTrue(sketch instanceof EmptyCompactSketch);
}
@Test(expectedExceptions = SketchesArgumentException.class)
- public void checkSerVer1_32Bytes_tooSmall() {
- byte[] byteArray = new byte[32];
- WritableMemory mem = WritableMemory.wrap(byteArray);
- mem.putByte(0, (byte) 3); //mdLongs
- mem.putByte(1, (byte) 1); //SerVer
- mem.putByte(2, (byte) 3); //SketchType = SetSketch
- //byte 3 lgNomLongs not used with SetSketch
- //byte 4 lgArrLongs not used with SetSketch
- //byte 5 lgRR not used with SetSketch
- //byte 6: Flags: b0: BigEnd, b1: ReadOnly
- mem.putByte(6, (byte) 2);
- //byte 7 Not used
- mem.putInt(8, 2); //curCount = 2
- mem.putLong(16, Long.MAX_VALUE);
-
- Memory srcMem = Memory.wrap(byteArray);
- Sketch.heapify(srcMem);
+ public void checkSerVer1_tooSmall() {
+ UpdateSketch usk = Sketches.updateSketchBuilder().build();
+ usk.update(1);
+ usk.update(2);
+ CompactSketch csk = usk.compact(true, null);
+ Memory srcMem = convertSerVer3toSerVer1(csk);
+ Memory srcMem2 = srcMem.region(0, srcMem.getCapacity() - 8);
+ Sketch.heapify(srcMem2); //throws because too small
}
@Test
public void checkSerVer1_1Value() {
- byte[] byteArray = new byte[32];
- WritableMemory mem = WritableMemory.wrap(byteArray);
- mem.putByte(0, (byte) 3);
- mem.putByte(1, (byte) 1); //SerVer
- //byte 2 Sketch Type, now Family
- //byte 3 lgNomLongs not used with SetSketch
- //byte 4 lgArrLongs not used with SetSketch
- //byte 5 lgRR not used with SetSketch
- //byte 6: Flags: b0: BigEnd, b1: ReadOnly
- mem.putByte(6, (byte) 2);
- //byte 7 Not used
- mem.putInt(8, 1); //curCount = 1
- mem.putLong(16, Long.MAX_VALUE);
- long[] longArrIn = new long[2];
- longArrIn[0] = 1;
- long hash = hash(longArrIn, 0)[0] >>> 1;
- mem.putLong(24, hash);
-
- Memory srcMem = Memory.wrap(byteArray);
+ UpdateSketch usk = Sketches.updateSketchBuilder().build();
+ usk.update(1);
+ CompactSketch csk = usk.compact(true, null);
+ Memory srcMem = convertSerVer3toSerVer1(csk);
Sketch sketch = Sketch.heapify(srcMem);
assertEquals(sketch.isEmpty(), false);
assertEquals(sketch.isEstimationMode(), false);
@@ -119,27 +76,13 @@ public class ForwardCompatibilityTest {
assertEquals(sketch.isCompact(), true);
assertEquals(sketch.isOrdered(), true);
assertEquals(sketch.getEstimate(), 1.0);
- String name = sketch.getClass().getSimpleName();
- assertEquals(name, "SingleItemSketch");
+ assertTrue(sketch instanceof SingleItemSketch);
}
@Test
- public void checkSerVer2_8Bytes() {
- byte[] byteArray = new byte[8];
- WritableMemory mem = WritableMemory.wrap(byteArray);
- mem.putByte(0, (byte) 1); //mdLongs, RR = 0
- mem.putByte(1, (byte) 2); //SerVer
- mem.putByte(2, (byte) 3); //SketchType = SetSketch
- //byte 3 lgNomLongs not used w SetSketch
- //byte 4 lgArrLongs not used w SetSketch
- //byte 5 Flags: b0: BigEnd, b1: ReadOnly, b2: Empty, b3: NoRebuild, b4, Unordered
- mem.putByte(5, (byte) 2); //Flags
- short seedHash = Util.computeSeedHash(Util.DEFAULT_UPDATE_SEED);
- mem.putShort(6, seedHash);
- //mem.putInt(8, 0); //curCount = 0
- //mem.putLong(16, Long.MAX_VALUE);
-
- Memory srcMem = Memory.wrap(byteArray);
+ public void checkSerVer2_Empty() {
+ CompactSketch csk = EmptyCompactSketch.getInstance();
+ Memory srcMem = convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
Sketch sketch = Sketch.heapify(srcMem);
assertEquals(sketch.isEmpty(), true);
assertEquals(sketch.isEstimationMode(), false);
@@ -147,143 +90,34 @@ public class ForwardCompatibilityTest {
assertEquals(sketch.hasMemory(), false);
assertEquals(sketch.isCompact(), true);
assertEquals(sketch.isOrdered(), true);
- String name = sketch.getClass().getSimpleName();
- assertEquals(name, "HeapCompactOrderedSketch");
+ assertTrue(sketch instanceof EmptyCompactSketch);
}
@Test
public void checkSerVer2_24Bytes_0Values() {
- byte[] byteArray = new byte[24];
- WritableMemory mem = WritableMemory.wrap(byteArray);
- mem.putByte(0, (byte) 2); //mdLongs, RF (RR) = 0
- mem.putByte(1, (byte) 2); //SerVer
- mem.putByte(2, (byte) 3); //SketchType = SetSketch
- //byte 3 lgNomLongs not used w SetSketch
- //byte 4 lgArrLongs not used w SetSketch
- //byte 5 Flags: b0: BigEnd, b1: ReadOnly, b2: Empty, b3: NoRebuild, b4, Unordered
- mem.putByte(5, (byte) 2); //Flags = ReadOnly
- short seedHash = Util.computeSeedHash(Util.DEFAULT_UPDATE_SEED);
- mem.putShort(6, seedHash);
- mem.putInt(8, 0); //curCount = 0
- //mem.putLong(16, Long.MAX_VALUE);
-
- Memory srcMem = Memory.wrap(byteArray);
- Sketch sketch = Sketch.heapify(srcMem);
+ UpdateSketch usk = Sketches.updateSketchBuilder().setLogNominalEntries(4).build();
+ for (int i = 0; i < 32; i++) { usk.update(i); }
+ CompactSketch csk = usk.compact(true, null);
+ Memory srcMem = convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
+
+ WritableMemory srcMemW = WritableMemory.allocate(24);
+ srcMem.copyTo(0, srcMemW, 0, 24);
+ PreambleUtil.setEmpty(srcMemW); //Force
+ assertTrue(PreambleUtil.isEmpty(srcMemW));
+ srcMemW.putInt(8, 0); //corrupt curCount = 0
+ srcMemW.putLong(16, Long.MAX_VALUE); //corrupt to make it look empty
+
+ Sketch sketch = Sketch.heapify(srcMemW);
assertEquals(sketch.isEmpty(), true); //was forced true
assertEquals(sketch.isEstimationMode(), false);
assertEquals(sketch.isDirect(), false);
assertEquals(sketch.hasMemory(), false);
assertEquals(sketch.isCompact(), true);
assertEquals(sketch.isOrdered(), true);
- String name = sketch.getClass().getSimpleName();
- assertEquals(name, "HeapCompactOrderedSketch");
+ assertTrue(sketch instanceof EmptyCompactSketch);
}
@Test
- public void checkSerVer2_32Bytes_0Values() {
- byte[] byteArray = new byte[32];
- WritableMemory mem = WritableMemory.wrap(byteArray);
- mem.putByte(0, (byte) 3); //mdLongs, RF (RR) = 0
- mem.putByte(1, (byte) 2); //SerVer
- mem.putByte(2, (byte) 3); //SketchType = SetSketch
- //byte 3 lgNomLongs not used w SetSketch
- //byte 4 lgArrLongs not used w SetSketch
- //byte 5 Flags: b0: BigEnd, b1: ReadOnly, b2: Empty, b3: NoRebuild, b4, Unordered
- mem.putByte(5, (byte) 2); //Flags = ReadOnly
- short seedHash = Util.computeSeedHash(Util.DEFAULT_UPDATE_SEED);
- mem.putShort(6, seedHash);
- mem.putInt(8, 0); //curCount = 0
- mem.putLong(16, Long.MAX_VALUE);
-
- Memory srcMem = Memory.wrap(byteArray);
- Sketch sketch = Sketch.heapify(srcMem);
- assertEquals(sketch.isEmpty(), true); //forced true
- assertEquals(sketch.isEstimationMode(), false);
- assertEquals(sketch.isDirect(), false);
- assertEquals(sketch.hasMemory(), false);
- assertEquals(sketch.isCompact(), true);
- assertEquals(sketch.isOrdered(), true);
- String name = sketch.getClass().getSimpleName();
- assertEquals(name, "HeapCompactOrderedSketch");
- }
-
- /**
- * Converts a SerVer3 CompactSketch to a SerVer1 SetSketch.
- * Note: SerVer1 does not support SingleItemSketch, so entries will equal zero.
- * @param v3mem a SerVer3 CompactSketch, ordered and with 24 byte preamble.
- * @return a SerVer1 SetSketch as Memory object.
- */
- public static WritableMemory convertSerV3toSerV1(Memory v3mem) {
- //validate that v3mem is in the right form
- int serVer = v3mem.getByte(SER_VER_BYTE);
- int famId = v3mem.getByte(FAMILY_BYTE);
- int flags = v3mem.getByte(FLAGS_BYTE);
- if ((serVer != 3) || (famId != 3) || ((flags & 24) != 24)) {
- throw new SketchesArgumentException("Memory must be V3, Compact, Ordered");
- }
- //must convert v3 preamble to a v1 preamble
- int v3preLongs = v3mem.getByte(PREAMBLE_LONGS_BYTE) & 0X3F;
- int entries;
- long thetaLong;
- if (v3preLongs == 1) {
- //Note: there is no way to safely convert to a SingleItemSketch if empty is false.
- entries = 0;
- thetaLong = Long.MAX_VALUE;
- }
- else if (v3preLongs == 2) {
- entries = v3mem.getInt(RETAINED_ENTRIES_INT);
- thetaLong = Long.MAX_VALUE;
- }
- else { //preLongs == 3
- entries = v3mem.getInt(RETAINED_ENTRIES_INT);
- thetaLong = v3mem.getLong(THETA_LONG);
- }
- //compute size
- int v1preLongs = 3;
- int v1bytes = (v1preLongs+entries) << 3;
- //create new mem and place the fields for SerVer1
- WritableMemory v1mem = WritableMemory.wrap(new byte[v1bytes]);
- v1mem.putByte(0, (byte)3); //Preamble = 3
- v1mem.putByte(1, (byte)1); //SerVer
- v1mem.putByte(2, (byte)3); //SketchType SetSketch = Family CompactSketch
- v1mem.putByte(6, (byte)2); //set bit1 = ReadOnly
- v1mem.putInt(RETAINED_ENTRIES_INT, entries);
- v1mem.putLong(THETA_LONG, thetaLong);
- //copy data
- v3mem.copyTo(v3preLongs << 3, v1mem, v1preLongs << 3, entries << 3);
- return v1mem;
- }
- /**
- * Converts a SerVer3 CompactSketch to a SerVer2 SetSketch.
- * @param v3mem a SerVer3 Compact, Ordered Sketch.
- * @return a SerVer2 SetSketch as Memory object
- */
- public static WritableMemory convertSerV3toSerV2(Memory v3mem) {
- //validate that v3mem is in the right form
- int serVer = v3mem.getByte(SER_VER_BYTE);
- int famId = v3mem.getByte(FAMILY_BYTE);
- int flags = v3mem.getByte(FLAGS_BYTE);
- if ((serVer != 3) || (famId != 3) || ((flags & 24) != 24)) {
- throw new SketchesArgumentException("Memory must be V3, Compact, Ordered");
- }
- //compute size
- int preLongs = v3mem.getByte(PREAMBLE_LONGS_BYTE) & 0X3F;
- //Note: there is no way to safely convert to a SingleItemSketch if empty is false.
- int entries = (preLongs == 1)? 0 : v3mem.getInt(RETAINED_ENTRIES_INT);
- int v2bytes = (preLongs+entries) << 3;
- //create new mem and do complete copy
- WritableMemory v2mem = WritableMemory.wrap(new byte[v2bytes]);
- v3mem.copyTo(0, v2mem, 0, v2bytes);
- //set serVer2
- v2mem.putByte(SER_VER_BYTE, (byte) 2);
- //adjust the flags
- byte v2flags = (byte)(2 | ((preLongs == 1)? 4: 0));
- v2mem.putByte(FLAGS_BYTE, v2flags);
- return v2mem;
- }
-
-
- @Test
public void printlnTest() {
println("PRINTING: "+this.getClass().getName());
}
diff --git a/src/test/java/com/yahoo/sketches/theta/HeapAlphaSketchTest.java b/src/test/java/com/yahoo/sketches/theta/HeapAlphaSketchTest.java
index fe3e4cb..7833b46 100644
--- a/src/test/java/com/yahoo/sketches/theta/HeapAlphaSketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/HeapAlphaSketchTest.java
@@ -304,7 +304,7 @@ public class HeapAlphaSketchTest {
//empty
usk.toString(false, true, 0, false);
boolean estimating = false;
- assertEquals(usk.getClass().getSimpleName(), "HeapAlphaSketch");
+ assertTrue(usk instanceof HeapAlphaSketch);
double uskEst = usk.getEstimate();
double uskLB = usk.getLowerBound(2);
double uskUB = usk.getUpperBound(2);
@@ -321,7 +321,7 @@ public class HeapAlphaSketchTest {
assertEquals(csk2.getUpperBound(2), uskUB);
assertEquals(csk2.isEmpty(), true);
assertEquals(csk2.isEstimationMode(), estimating);
- assertEquals(csk2.getClass().getSimpleName(), "DirectCompactUnorderedSketch");
+ assertTrue(csk2 instanceof EmptyCompactSketch);
CompactSketch csk3 = usk.compact(true, mem2);
csk3.toString(false, true, 0, false);
@@ -331,7 +331,7 @@ public class HeapAlphaSketchTest {
assertEquals(csk3.getUpperBound(2), uskUB);
assertEquals(csk3.isEmpty(), true);
assertEquals(csk3.isEstimationMode(), estimating);
- assertEquals(csk3.getClass().getSimpleName(), "DirectCompactOrderedSketch");
+ assertTrue(csk3 instanceof EmptyCompactSketch);
}
@Test
diff --git a/src/test/java/com/yahoo/sketches/theta/HeapQuickSelectSketchTest.java b/src/test/java/com/yahoo/sketches/theta/HeapQuickSelectSketchTest.java
index d0b1e12..62dee23 100644
--- a/src/test/java/com/yahoo/sketches/theta/HeapQuickSelectSketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/HeapQuickSelectSketchTest.java
@@ -296,9 +296,8 @@ public class HeapQuickSelectSketchTest {
UpdateSketch usk = UpdateSketch.builder().setFamily(fam_).setResizeFactor(X2).setNominalEntries(k).build();
println("lgArr: "+ usk.getLgArrLongs());
-
//empty
- usk.toString(false, true, 0, false);
+ println(usk.toString(false, true, 0, false));
boolean estimating = false;
assertEquals(usk.getClass().getSimpleName(), "HeapQuickSelectSketch");
double uskEst = usk.getEstimate();
@@ -319,17 +318,17 @@ public class HeapQuickSelectSketchTest {
assertEquals(csk2.getUpperBound(2), uskUB);
assertEquals(csk2.isEmpty(), true);
assertEquals(csk2.isEstimationMode(), estimating);
- assertEquals(csk2.getClass().getSimpleName(), "DirectCompactUnorderedSketch");
+ assertEquals(csk2.getClass().getSimpleName(), "EmptyCompactSketch");
CompactSketch csk3 = usk.compact(true, mem2);
- csk3.toString(false, true, 0, false);
- csk3.toString();
+ println(csk3.toString(false, true, 0, false));
+ println(csk3.toString());
assertEquals(csk3.getEstimate(), uskEst);
assertEquals(csk3.getLowerBound(2), uskLB);
assertEquals(csk3.getUpperBound(2), uskUB);
assertEquals(csk3.isEmpty(), true);
assertEquals(csk3.isEstimationMode(), estimating);
- assertEquals(csk3.getClass().getSimpleName(), "DirectCompactOrderedSketch");
+ assertEquals(csk3.getClass().getSimpleName(), "EmptyCompactSketch");
}
@Test
diff --git a/src/test/java/com/yahoo/sketches/theta/HeapUnionTest.java b/src/test/java/com/yahoo/sketches/theta/HeapUnionTest.java
index f46767b..f7442da 100644
--- a/src/test/java/com/yahoo/sketches/theta/HeapUnionTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/HeapUnionTest.java
@@ -19,8 +19,8 @@
package com.yahoo.sketches.theta;
-import static com.yahoo.sketches.theta.ForwardCompatibilityTest.convertSerV3toSerV1;
-import static com.yahoo.sketches.theta.ForwardCompatibilityTest.convertSerV3toSerV2;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer1;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer2;
import static com.yahoo.sketches.theta.PreambleUtil.SER_VER_BYTE;
import static java.nio.charset.StandardCharsets.UTF_8;
import static org.testng.Assert.assertEquals;
@@ -34,6 +34,7 @@ import com.yahoo.memory.Memory;
import com.yahoo.memory.WritableMemory;
import com.yahoo.sketches.Family;
import com.yahoo.sketches.SketchesArgumentException;
+import com.yahoo.sketches.Util;
/**
* @author Lee Rhodes
@@ -49,8 +50,12 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u/2; i++) usk1.update(i); //256
- for (int i=u/2; i<u; i++) usk2.update(i); //256 no overlap
+ for (int i=0; i<(u/2); i++) {
+ usk1.update(i); //256
+ }
+ for (int i=u/2; i<u; i++) {
+ usk2.update(i); //256 no overlap
+ }
assertEquals(u, usk1.getEstimate() + usk2.getEstimate(), 0.0); //exact, no overlap
@@ -71,8 +76,12 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u/2; i++) usk1.update(i); //2*k
- for (int i=u/2; i<u; i++) usk2.update(i); //2*k no overlap
+ for (int i=0; i<(u/2); i++) {
+ usk1.update(i); //2*k
+ }
+ for (int i=u/2; i<u; i++) {
+ usk2.update(i); //2*k no overlap
+ }
Union union = SetOperation.builder().setNominalEntries(k).buildUnion();
@@ -91,10 +100,14 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u/2; i++) usk1.update(i); //256
- for (int i=0; i<u ; i++) usk2.update(i); //512, 256 overlapped
+ for (int i=0; i<(u/2); i++) {
+ usk1.update(i); //256
+ }
+ for (int i=0; i<u ; i++) {
+ usk2.update(i); //512, 256 overlapped
+ }
- assertEquals(u, usk1.getEstimate() + usk2.getEstimate()/2, 0.0); //exact, overlapped
+ assertEquals(u, usk1.getEstimate() + (usk2.getEstimate()/2), 0.0); //exact, overlapped
Union union = SetOperation.builder().setNominalEntries(k).buildUnion();
@@ -113,8 +126,12 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u/2; i++) usk1.update(i); //256
- for (int i=u/2; i<u; i++) usk2.update(i); //256 no overlap
+ for (int i=0; i<(u/2); i++) {
+ usk1.update(i); //256
+ }
+ for (int i=u/2; i<u; i++) {
+ usk2.update(i); //256 no overlap
+ }
assertEquals(u, usk1.getEstimate() + usk2.getEstimate(), 0.0); //exact, no overlap
@@ -139,8 +156,12 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build(); //2k estimating
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(2 * k).build(); //2k exact
- for (int i=0; i<u/2; i++) usk1.update(i); //2k
- for (int i=u/2; i<u; i++) usk2.update(i); //2k no overlap, exact
+ for (int i=0; i<(u/2); i++) {
+ usk1.update(i); //2k
+ }
+ for (int i=u/2; i<u; i++) {
+ usk2.update(i); //2k no overlap, exact
+ }
Union union = SetOperation.builder().setNominalEntries(k).buildUnion();
@@ -163,8 +184,12 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build(); //2k estimating
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(2 * k).build(); //2k exact for early stop test
- for (int i=0; i<u/2; i++) usk1.update(i); //2k
- for (int i=u/2; i<u; i++) usk2.update(i); //2k no overlap, exact, will force early stop
+ for (int i=0; i<(u/2); i++) {
+ usk1.update(i); //2k
+ }
+ for (int i=u/2; i<u; i++) {
+ usk2.update(i); //2k no overlap, exact, will force early stop
+ }
CompactSketch cosk2 = usk2.compact(true, null);
@@ -197,8 +222,12 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build(); //2k estimating
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(2 * k).build(); //2k exact for early stop test
- for (int i=0; i<u/2; i++) usk1.update(i); //2k estimating
- for (int i=u/2; i<u; i++) usk2.update(i); //2k no overlap, exact, will force early stop
+ for (int i=0; i<(u/2); i++) {
+ usk1.update(i); //2k estimating
+ }
+ for (int i=u/2; i<u; i++) {
+ usk2.update(i); //2k no overlap, exact, will force early stop
+ }
WritableMemory cskMem2 = WritableMemory.wrap(new byte[usk2.getCurrentBytes(true)]);
CompactSketch cosk2 = usk2.compact(true, cskMem2); //ordered, loads the cskMem2 as ordered
@@ -232,8 +261,12 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build(); //2k estimating
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(2 * k).build(); //2k exact for early stop test
- for (int i=0; i<u/2; i++) usk1.update(i); //2k estimating
- for (int i=u/2; i<u; i++) usk2.update(i); //2k no overlap, exact, will force early stop
+ for (int i=0; i<(u/2); i++) {
+ usk1.update(i); //2k estimating
+ }
+ for (int i=u/2; i<u; i++) {
+ usk2.update(i); //2k no overlap, exact, will force early stop
+ }
WritableMemory cskMem2 = WritableMemory.wrap(new byte[usk2.getCurrentBytes(true)]);
usk2.compact(true, cskMem2); //ordered, loads the cskMem2 as ordered
@@ -267,8 +300,12 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build(); //2k estimating
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(2 * k).build(); //2k exact for early stop test
- for (int i=0; i<u/2; i++) usk1.update(i); //2k estimating
- for (int i=u/2; i<u; i++) usk2.update(i); //2k no overlap, exact, will force early stop
+ for (int i=0; i<(u/2); i++) {
+ usk1.update(i); //2k estimating
+ }
+ for (int i=u/2; i<u; i++) {
+ usk2.update(i); //2k no overlap, exact, will force early stop
+ }
WritableMemory cskMem2 = WritableMemory.wrap(new byte[usk2.getCurrentBytes(true)]);
usk2.compact(false, cskMem2); //unordered, loads the cskMem2 as unordered
@@ -305,14 +342,22 @@ public class HeapUnionTest {
int v=0;
int u = 1000000;
- for (int i=0; i<u; i++) usk1.update(i+v);
+ for (int i=0; i<u; i++) {
+ usk1.update(i+v);
+ }
v += u;
u = 26797;
- for (int i=0; i<u; i++) usk2.update(i+v);
+ for (int i=0; i<u; i++) {
+ usk2.update(i+v);
+ }
v += u;
- for (int i=0; i<u; i++) usk3.update(i+v);
+ for (int i=0; i<u; i++) {
+ usk3.update(i+v);
+ }
v += u;
- for (int i=0; i<u; i++) usk4.update(i+v);
+ for (int i=0; i<u; i++) {
+ usk4.update(i+v);
+ }
v += u;
Union union = SetOperation.builder().setNominalEntries(k).buildUnion();
@@ -338,8 +383,12 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u1; i++) usk1.update(i); //2*k
- for (int i=u1; i<totU; i++) usk2.update(i); //2*k + 1024 no overlap
+ for (int i=0; i<u1; i++) {
+ usk1.update(i); //2*k
+ }
+ for (int i=u1; i<totU; i++) {
+ usk2.update(i); //2*k + 1024 no overlap
+ }
WritableMemory skMem1 = WritableMemory.wrap(usk1.compact(false, null).toByteArray());
WritableMemory skMem2 = WritableMemory.wrap(usk2.compact(true, null).toByteArray());
@@ -367,14 +416,15 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u1; i++) usk1.update(i); //2*k
- for (int i=u1; i<totU; i++) usk2.update(i); //2*k + 1024 no overlap
+ for (int i=0; i<u1; i++) {
+ usk1.update(i); //2*k
+ }
+ for (int i=u1; i<totU; i++) {
+ usk2.update(i); //2*k + 1024 no overlap
+ }
- WritableMemory skMem1 = WritableMemory.wrap(usk1.compact(true, null).toByteArray());
- WritableMemory skMem2 = WritableMemory.wrap(usk2.compact(true, null).toByteArray());
-
- Memory v1mem1 = convertSerV3toSerV1(skMem1);
- Memory v1mem2 = convertSerV3toSerV1(skMem2);
+ Memory v1mem1 = convertSerVer3toSerVer1(usk1.compact(true, null));
+ Memory v1mem2 = convertSerVer3toSerVer1(usk2.compact(true, null));
Union union = SetOperation.builder().setNominalEntries(k).buildUnion();
@@ -396,14 +446,15 @@ public class HeapUnionTest {
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u1; i++) usk1.update(i); //2*k
- for (int i=u1; i<totU; i++) usk2.update(i); //2*k + 1024 no overlap
+ for (int i=0; i<u1; i++) {
+ usk1.update(i); //2*k
+ }
+ for (int i=u1; i<totU; i++) {
+ usk2.update(i); //2*k + 1024 no overlap
+ }
- WritableMemory skMem1 = WritableMemory.wrap(usk1.compact(true, null).toByteArray());
- WritableMemory skMem2 = WritableMemory.wrap(usk2.compact(true, null).toByteArray());
-
- Memory v2mem1 = convertSerV3toSerV2(skMem1);
- Memory v2mem2 = convertSerV3toSerV2(skMem2);
+ Memory v2mem1 = convertSerVer3toSerVer2(usk1.compact(true, null), Util.DEFAULT_UPDATE_SEED);
+ Memory v2mem2 = convertSerVer3toSerVer2(usk2.compact(true, null), Util.DEFAULT_UPDATE_SEED);
Union union = SetOperation.builder().setNominalEntries(k).buildUnion();
@@ -423,14 +474,14 @@ public class HeapUnionTest {
CompactSketch usk1c = usk1.compact(true, null);
WritableMemory v3mem1 = WritableMemory.wrap(usk1c.toByteArray());
- Memory v1mem1 = convertSerV3toSerV1(v3mem1);
+ Memory v1mem1 = convertSerVer3toSerVer1(usk1.compact(true, null));
Union union = SetOperation.builder().setNominalEntries(k).buildUnion();
union.update(v1mem1);
CompactSketch cOut = union.getResult(true, null);
assertEquals(cOut.getEstimate(), 0.0, 0.0);
- Memory v2mem1 = convertSerV3toSerV2(v3mem1);
+ Memory v2mem1 = convertSerVer3toSerVer2(usk1.compact(true, null), Util.DEFAULT_UPDATE_SEED);
union = SetOperation.builder().setNominalEntries(k).buildUnion();
union.update(v2mem1);
@@ -456,7 +507,10 @@ public class HeapUnionTest {
int u = 2*k;
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<u; i++) usk1.update(i); //force prelongs to 3
+ for (int i=0; i<u; i++)
+ {
+ usk1.update(i); //force prelongs to 3
+ }
CompactSketch usk1c = usk1.compact(true, null);
WritableMemory v3mem1 = WritableMemory.wrap(usk1c.toByteArray());
//println(PreambleUtil.toString(v3mem1));
@@ -468,8 +522,9 @@ public class HeapUnionTest {
public void checkMemBadSerVer() {
int lgK = 12; //4096
int k = 1 << lgK;
-
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
+ usk1.update(1);
+ usk1.update(2);
CompactSketch usk1c = usk1.compact(true, null);
WritableMemory v3mem1 = WritableMemory.wrap(usk1c.toByteArray());
//corrupt SerVer
@@ -480,7 +535,6 @@ public class HeapUnionTest {
}
@Test
- //where the granted mem is larger than required
public void checkEmptySerVer2and3() {
UpdateSketch usk1 = UpdateSketch.builder().build();
CompactSketch usk1c = usk1.compact(true, null);
@@ -491,7 +545,7 @@ public class HeapUnionTest {
Union union = SetOperation.builder().buildUnion();
union.update(v3mem1);
- Memory v2mem1 = convertSerV3toSerV2(v3mem1);
+ Memory v2mem1 = convertSerVer3toSerVer2(usk1c, Util.DEFAULT_UPDATE_SEED);
WritableMemory v2mem2 = WritableMemory.wrap(new byte[16]);
v2mem1.copyTo(0, v2mem2, 0, 8);
diff --git a/src/test/java/com/yahoo/sketches/theta/PairwiseCornerCasesTest.java b/src/test/java/com/yahoo/sketches/theta/PairwiseCornerCasesTest.java
index 9eca28c..2a1d820 100644
--- a/src/test/java/com/yahoo/sketches/theta/PairwiseCornerCasesTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/PairwiseCornerCasesTest.java
@@ -22,6 +22,7 @@ package com.yahoo.sketches.theta;
import static com.yahoo.sketches.theta.PairwiseCornerCasesTest.State.EMPTY;
import static com.yahoo.sketches.theta.PairwiseCornerCasesTest.State.EST_HEAP;
import static com.yahoo.sketches.theta.PairwiseCornerCasesTest.State.EST_MEMORY_UNORDERED;
+import static com.yahoo.sketches.theta.PairwiseCornerCasesTest.State.EXACT;
import static com.yahoo.sketches.theta.PairwiseCornerCasesTest.State.NULL;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertNull;
@@ -129,13 +130,13 @@ public class PairwiseCornerCasesTest {
int stdEnt = comp.getRetainedEntries(true);
CompactSketch pwComp = PairwiseSetOperations.union(cskA, cskB, k);
- double pwEst = (pwComp != null)? pwComp.getEstimate() : -1.0;
- boolean pwEmpty = (pwComp != null)? pwComp.isEmpty() : true;
- double pwTheta = (pwComp != null)? pwComp.getTheta() : 1.0;
- int pwEnt = (pwComp != null)? pwComp.getRetainedEntries(true) : 0;
+ double pwEst = pwComp.getEstimate();
+ boolean pwEmpty = pwComp.isEmpty();
+ double pwTheta = pwComp.getTheta();
+ int pwEnt = pwComp.getRetainedEntries(true);
if ((stateA == NULL) && (stateB == NULL)) {
- Assert.assertEquals(pwEst, -1.0, 0.0);
+ Assert.assertEquals(pwEst, 0.0, 0.0);
Assert.assertEquals(stdEst, 0.0, 0.0);
} else {
Assert.assertEquals(pwEst, stdEst, 0.0);
@@ -155,13 +156,13 @@ public class PairwiseCornerCasesTest {
stdEnt = comp.getRetainedEntries(true);
pwComp = PairwiseSetOperations.intersect(cskA, cskB);
- pwEst = (pwComp != null)? pwComp.getEstimate() : -1.0;
- pwEmpty = (pwComp != null)? pwComp.isEmpty() : true;
- pwTheta = (pwComp != null)? pwComp.getTheta() : 1.0;
- pwEnt = (pwComp != null)? pwComp.getRetainedEntries(true) : 0;
+ pwEst = pwComp.getEstimate();
+ pwEmpty = pwComp.isEmpty();
+ pwTheta = pwComp.getTheta();
+ pwEnt = pwComp.getRetainedEntries(true);
if ((stateA == NULL) && (stateB == NULL)) {
- Assert.assertEquals(pwEst, -1.0, 0.0);
+ Assert.assertEquals(pwEst, 0.0, 0.0);
Assert.assertEquals(stdEst, 0.0, 0.0);
} else {
Assert.assertEquals(pwEst, stdEst, 0.0);
@@ -179,13 +180,13 @@ public class PairwiseCornerCasesTest {
stdEnt = comp.getRetainedEntries(true);
pwComp = PairwiseSetOperations.aNotB(cskA, cskB);
- pwEst = (pwComp != null)? pwComp.getEstimate() : -1.0;
- pwEmpty = (pwComp != null)? pwComp.isEmpty() : true;
- pwTheta = (pwComp != null)? pwComp.getTheta() : 1.0;
- pwEnt = (pwComp != null)? pwComp.getRetainedEntries(true) : 0;
+ pwEst = pwComp.getEstimate();
+ pwEmpty = pwComp.isEmpty();
+ pwTheta = pwComp.getTheta();
+ pwEnt = pwComp.getRetainedEntries(true);
if ((stateA == NULL) && (stateB == NULL)) {
- Assert.assertEquals(pwEst, -1.0, 0.0);
+ Assert.assertEquals(pwEst, 0.0, 0.0);
Assert.assertEquals(stdEst, 0.0, 0.0);
} else {
Assert.assertEquals(pwEst, stdEst, 0.0);
@@ -234,62 +235,65 @@ public class PairwiseCornerCasesTest {
@Test
public void checkSeedHash() {
int k = 64;
- CompactSketch skEmptyS2 =
- Sketches.updateSketchBuilder().setNominalEntries(k).setSeed(123).build().compact(true, null);
- UpdateSketch tmp = Sketches.updateSketchBuilder().setNominalEntries(k).setSeed(123).build();
- tmp.update(1);
- CompactSketch skHeapS2 = tmp.compact(true, null);
- CompactSketch skEmpty = generate(EMPTY, k);
+ UpdateSketch tmp1 = Sketches.updateSketchBuilder().setNominalEntries(k).setSeed(123).build();
+ tmp1.update(1); tmp1.update(3);
+ CompactSketch skSmallSeed2 = tmp1.compact(true, null);
+
+ UpdateSketch tmp2 = Sketches.updateSketchBuilder().setNominalEntries(k).setSeed(123).build();
+ tmp2.update(1); tmp2.update(2);
+ CompactSketch skSmallSeed2B = tmp2.compact(true, null);
+
+ CompactSketch skExact = generate(EXACT, k);
CompactSketch skHeap = generate(EST_HEAP, 2 * k);
//Intersect
try {
- PairwiseSetOperations.intersect(skEmpty, skEmptyS2);
+ PairwiseSetOperations.intersect(skExact, skSmallSeed2);
Assert.fail();
} catch (Exception e) { } //pass
try {
- PairwiseSetOperations.intersect(skEmpty, skHeapS2);
+ PairwiseSetOperations.intersect(skExact, skSmallSeed2B);
Assert.fail();
} catch (Exception e) { } //pass
try {
- PairwiseSetOperations.intersect(skHeapS2, skEmpty);
+ PairwiseSetOperations.intersect(skSmallSeed2B, skExact);
Assert.fail();
} catch (Exception e) { } //pass
try {
- PairwiseSetOperations.intersect(skHeap, skHeapS2);
+ PairwiseSetOperations.intersect(skHeap, skSmallSeed2B);
Assert.fail();
} catch (Exception e) { } //pass
//A NOT B
try {
- PairwiseSetOperations.aNotB(skEmpty, skEmptyS2);
+ PairwiseSetOperations.aNotB(skExact, skSmallSeed2);
Assert.fail();
} catch (Exception e) { } //pass
try {
- PairwiseSetOperations.aNotB(skEmpty, skHeapS2);
+ PairwiseSetOperations.aNotB(skExact, skSmallSeed2B);
Assert.fail();
} catch (Exception e) { } //pass
try {
- PairwiseSetOperations.aNotB(skHeapS2, skEmpty);
+ PairwiseSetOperations.aNotB(skSmallSeed2B, skExact);
Assert.fail();
} catch (Exception e) { } //pass
try {
- PairwiseSetOperations.aNotB(skHeap, skHeapS2);
+ PairwiseSetOperations.aNotB(skHeap, skSmallSeed2B);
Assert.fail();
} catch (Exception e) { } //pass
//Union
try {
- PairwiseSetOperations.union(skEmpty, skEmptyS2);
+ PairwiseSetOperations.union(skExact, skSmallSeed2);
Assert.fail();
} catch (Exception e) { } //pass
try {
- PairwiseSetOperations.union(skEmpty, skHeapS2);
+ PairwiseSetOperations.union(skExact, skSmallSeed2B);
Assert.fail();
} catch (Exception e) { } //pass
try {
- PairwiseSetOperations.union(skHeapS2, skEmpty);
+ PairwiseSetOperations.union(skSmallSeed2B, skExact);
Assert.fail();
} catch (Exception e) { } //pass
try {
- PairwiseSetOperations.union(skHeap, skHeapS2);
+ PairwiseSetOperations.union(skHeap, skSmallSeed2B);
Assert.fail();
} catch (Exception e) { } //pass
@@ -401,7 +405,7 @@ public class PairwiseCornerCasesTest {
//already null
break;
}
- case EMPTY : {
+ case EMPTY : { //results in EmptyCompactSketch
csk = Sketches.updateSketchBuilder().setNominalEntries(k).build().compact(true, null);
break;
}
diff --git a/src/test/java/com/yahoo/sketches/theta/SingleItemSketchTest.java b/src/test/java/com/yahoo/sketches/theta/SingleItemSketchTest.java
index 6b6575f..5bad7dc 100644
--- a/src/test/java/com/yahoo/sketches/theta/SingleItemSketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/SingleItemSketchTest.java
@@ -20,8 +20,10 @@
package com.yahoo.sketches.theta;
import static com.yahoo.sketches.Util.DEFAULT_UPDATE_SEED;
+import static com.yahoo.sketches.Util.computeSeedHash;
import static com.yahoo.sketches.hash.MurmurHash3.hash;
import static com.yahoo.sketches.theta.PreambleUtil.MAX_THETA_LONG_AS_DOUBLE;
+import static com.yahoo.sketches.theta.PreambleUtil.SINGLEITEM_FLAG_MASK;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertNull;
@@ -31,12 +33,12 @@ import org.testng.annotations.Test;
import com.yahoo.memory.Memory;
import com.yahoo.memory.WritableMemory;
-import com.yahoo.sketches.SketchesArgumentException;
/**
* @author Lee Rhodes
*/
public class SingleItemSketchTest {
+ final static short DEFAULT_SEED_HASH = (short) (computeSeedHash(DEFAULT_UPDATE_SEED) & 0XFFFFL);
@Test
public void check1() {
@@ -168,21 +170,22 @@ public class SingleItemSketchTest {
assertEquals(sis.getCurrentPreambleLongs(true), 1);
}
- @Test(expectedExceptions = SketchesArgumentException.class)
- public void checkDefaultBytes0to7() {
- SingleItemSketch.checkDefaultBytes0to7(0L);
- }
-
- @Test(expectedExceptions = SketchesArgumentException.class)
- public void checkDefaultBytes0to5() {
- SingleItemSketch.checkDefaultBytes0to5(0L);
+ @Test//(expectedExceptions = SketchesArgumentException.class)
+ public void testPre0Seed() {
+ long pre0_lo6 = 0X00_00_1A_00_00_03_03_01L; //no SI flag, requires not empty
+ long pre0 = ((long)DEFAULT_SEED_HASH << 48) | pre0_lo6;
+ assertTrue(SingleItemSketch.testPre0Seed(pre0, DEFAULT_UPDATE_SEED));
+ //add SI flag
+ pre0 |= ((long)SINGLEITEM_FLAG_MASK << 40);
+ assertTrue(SingleItemSketch.testPre0Seed(pre0, DEFAULT_UPDATE_SEED));
}
@Test
public void unionWrapped() {
Sketch sketch = SingleItemSketch.create(1);
Union union = Sketches.setOperationBuilder().buildUnion();
- union.update(Memory.wrap(sketch.toByteArray()));
+ Memory mem = Memory.wrap(sketch.toByteArray());
+ union.update(mem);
assertEquals(union.getResult().getEstimate(), 1, 0);
}
@@ -213,9 +216,9 @@ public class SingleItemSketchTest {
bytes = Sketches.getMaxCompactSketchBytes(1);
wmem = WritableMemory.wrap(new byte[bytes]);
csk = sk1.compact(true, wmem);
- assertFalse(csk instanceof SingleItemSketch);
+ assertTrue(csk instanceof SingleItemSketch);
csk = sk1.compact(false, wmem);
- assertFalse(csk instanceof SingleItemSketch);
+ assertTrue(csk instanceof SingleItemSketch);
}
@Test
@@ -301,8 +304,10 @@ public class SingleItemSketchTest {
inter.update(sk1);
inter.update(sk2);
WritableMemory wmem = WritableMemory.wrap(new byte[16]);
- inter.getResult(false, wmem);
+ CompactSketch csk = inter.getResult(false, wmem);
+ assertTrue(csk instanceof SingleItemSketch);
Sketch csk2 = Sketches.heapifySketch(wmem);
+ assertTrue(csk2 instanceof SingleItemSketch);
println(csk2.toString(true, true, 1, true));
}
diff --git a/src/test/java/com/yahoo/sketches/theta/SketchTest.java b/src/test/java/com/yahoo/sketches/theta/SketchTest.java
index b4263ff..6992086 100644
--- a/src/test/java/com/yahoo/sketches/theta/SketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/SketchTest.java
@@ -28,6 +28,8 @@ import static com.yahoo.sketches.ResizeFactor.X4;
import static com.yahoo.sketches.ResizeFactor.X8;
import static com.yahoo.sketches.Util.DEFAULT_NOMINAL_ENTRIES;
import static com.yahoo.sketches.Util.DEFAULT_UPDATE_SEED;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer1;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer2;
import static com.yahoo.sketches.theta.PreambleUtil.COMPACT_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.FLAGS_BYTE;
import static com.yahoo.sketches.theta.Sketch.getMaxCompactSketchBytes;
@@ -42,6 +44,7 @@ import com.yahoo.memory.WritableMemory;
import com.yahoo.sketches.Family;
import com.yahoo.sketches.ResizeFactor;
import com.yahoo.sketches.SketchesArgumentException;
+import com.yahoo.sketches.Util;
/**
* @author Lee Rhodes
@@ -89,8 +92,7 @@ public class SketchTest {
sketch.getRetainedEntries(true));
assertEquals(compPreLongs, 2);
- for (int i=k; i<(2*k); i++)
- {
+ for (int i = k; i < (2*k); i++) {
sketch.update(i); //go estimation mode
}
int curCount = sketch.getRetainedEntries(true);
@@ -108,7 +110,9 @@ public class SketchTest {
for (int i=0; i<3; i++) {
int maxCompBytes = Sketch.getMaxCompactSketchBytes(i);
- assertEquals(maxCompBytes, (Family.COMPACT.getMaxPreLongs() << 3) + (i*8));
+ if (i == 0) { assertEquals(maxCompBytes, 8); }
+ if (i == 1) { assertEquals(maxCompBytes, 16); }
+ if (i > 1) { assertEquals(maxCompBytes, 24 + (i * 8)); } //assumes maybe estimation mode
}
}
@@ -298,17 +302,16 @@ public class SketchTest {
sketch1.update(i);
}
double uest1 = sketch1.getEstimate();
- int bytes = sketch1.getCurrentBytes(true);
- WritableMemory v3mem = WritableMemory.wrap(new byte[bytes]);
- sketch1.compact(true, v3mem);
- Memory v1mem = ForwardCompatibilityTest.convertSerV3toSerV1(v3mem);
+ CompactSketch csk = sketch1.compact();
+
+ Memory v1mem = convertSerVer3toSerVer1(csk);
Sketch csk2 = Sketch.wrap(v1mem);
assertFalse(csk2.isDirect());
assertFalse(csk2.hasMemory());
assertEquals(uest1, csk2.getEstimate(), 0.0);
- Memory v2mem = ForwardCompatibilityTest.convertSerV3toSerV2(v3mem);
+ Memory v2mem = convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
csk2 = Sketch.wrap(v2mem);
assertFalse(csk2.isDirect());
assertFalse(csk2.hasMemory());
@@ -318,9 +321,11 @@ public class SketchTest {
@Test
public void checkIsSameResource() {
int k = 16;
- WritableMemory mem = WritableMemory.wrap(new byte[(k*16) +24]);
- WritableMemory cmem = WritableMemory.wrap(new byte[8]);
+ WritableMemory mem = WritableMemory.wrap(new byte[(k*16) + 24]);
+ WritableMemory cmem = WritableMemory.wrap(new byte[32]);
UpdateSketch sketch = Sketches.updateSketchBuilder().setNominalEntries(k).build(mem);
+ sketch.update(1);
+ sketch.update(2);
assertTrue(sketch.isSameResource(mem));
DirectCompactOrderedSketch dcos = (DirectCompactOrderedSketch) sketch.compact(true, cmem);
assertTrue(dcos.isSameResource(cmem));
diff --git a/src/test/java/com/yahoo/sketches/theta/SketchesTest.java b/src/test/java/com/yahoo/sketches/theta/SketchesTest.java
index 2e67e4d..1cbc2d7 100644
--- a/src/test/java/com/yahoo/sketches/theta/SketchesTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/SketchesTest.java
@@ -19,7 +19,7 @@
package com.yahoo.sketches.theta;
-import static com.yahoo.sketches.theta.ForwardCompatibilityTest.convertSerV3toSerV1;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer1;
import static com.yahoo.sketches.theta.Sketches.getMaxCompactSketchBytes;
import static com.yahoo.sketches.theta.Sketches.getMaxIntersectionBytes;
import static com.yahoo.sketches.theta.Sketches.getMaxUnionBytes;
@@ -47,7 +47,7 @@ import com.yahoo.sketches.Util;
*/
public class SketchesTest {
- private static Memory getCompactSketch(int k, int from, int to) {
+ private static Memory getCompactSketchMemory(int k, int from, int to) {
UpdateSketch sk1 = updateSketchBuilder().setNominalEntries(k).build();
for (int i=from; i<to; i++) {
sk1.update(i);
@@ -58,10 +58,24 @@ public class SketchesTest {
return mem;
}
+ private static Memory getMemoryFromCompactSketch(CompactSketch csk) {
+ byte[] sk1bytes = csk.toByteArray();
+ Memory mem = Memory.wrap(sk1bytes);
+ return mem;
+ }
+
+ private static CompactSketch getCompactSketch(int k, int from, int to) {
+ UpdateSketch sk1 = updateSketchBuilder().setNominalEntries(k).build();
+ for (int i=from; i<to; i++) {
+ sk1.update(i);
+ }
+ return sk1.compact(true, null);
+ }
+
@Test
public void checkSketchMethods() {
int k = 1024;
- Memory mem = getCompactSketch(k, 0, k);
+ Memory mem = getCompactSketchMemory(k, 0, k);
CompactSketch csk2 = (CompactSketch)heapifySketch(mem);
assertEquals((int)csk2.getEstimate(), k);
@@ -79,8 +93,8 @@ public class SketchesTest {
@Test
public void checkSetOpMethods() {
int k = 1024;
- Memory mem1 = getCompactSketch(k, 0, k);
- Memory mem2 = getCompactSketch(k, k/2, (3*k)/2);
+ Memory mem1 = getCompactSketchMemory(k, 0, k);
+ Memory mem2 = getCompactSketchMemory(k, k/2, (3*k)/2);
SetOperationBuilder bldr = setOperationBuilder();
Union union = bldr.setNominalEntries(2 * k).buildUnion();
@@ -136,7 +150,8 @@ public class SketchesTest {
public void checkStaticEstimators() {
int k = 4096;
int u = 4*k;
- Memory srcMem = getCompactSketch(k, 0, u);
+ CompactSketch csk = getCompactSketch(k, 0, u);
+ Memory srcMem = getMemoryFromCompactSketch(csk);
double est = Sketches.getEstimate(srcMem);
assertEquals(est, u, 0.05*u);
double rse = 1.0/Math.sqrt(k);
@@ -144,13 +159,15 @@ public class SketchesTest {
assertEquals(ub, est+rse, 0.05*u);
double lb = Sketches.getLowerBound(1, srcMem);
assertEquals(lb, est-rse, 0.05*u);
- Memory memV1 = convertSerV3toSerV1(srcMem);
+ Memory memV1 = convertSerVer3toSerVer1(csk);
boolean empty = Sketches.getEmpty(memV1);
assertFalse(empty);
- Memory emptyMemV3 = getCompactSketch(k, 0, 0);
+
+ CompactSketch csk2 = getCompactSketch(k, 0, 0);
+ Memory emptyMemV3 = getMemoryFromCompactSketch(csk2);
assertEquals(Sketches.getRetainedEntries(emptyMemV3), 0);
assertEquals(Sketches.getThetaLong(emptyMemV3), Long.MAX_VALUE);
- Memory emptyMemV1 = convertSerV3toSerV1(emptyMemV3);
+ Memory emptyMemV1 = convertSerVer3toSerVer1(csk2);
empty = Sketches.getEmpty(emptyMemV1);
assertTrue(empty);
}
diff --git a/src/test/java/com/yahoo/sketches/theta/UnionImplTest.java b/src/test/java/com/yahoo/sketches/theta/UnionImplTest.java
index 1e1cd2a..781ccc8 100644
--- a/src/test/java/com/yahoo/sketches/theta/UnionImplTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/UnionImplTest.java
@@ -20,6 +20,8 @@
package com.yahoo.sketches.theta;
import static com.yahoo.sketches.Util.DEFAULT_UPDATE_SEED;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer1;
+import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer2;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
@@ -122,8 +124,8 @@ public class UnionImplTest {
for (int i=0; i<k; i++) {
sketch.update(i);
}
- sketch.compact(true, v3mem);
- WritableMemory v1mem = ForwardCompatibilityTest.convertSerV3toSerV1(v3mem);
+ CompactSketch csk = sketch.compact(true, v3mem);
+ WritableMemory v1mem = (WritableMemory) convertSerVer3toSerVer1(csk);
v1mem.putByte(PreambleUtil.FAMILY_BYTE, (byte)2); //corrupt family
@@ -139,8 +141,8 @@ public class UnionImplTest {
for (int i=0; i<k; i++) {
sketch.update(i);
}
- sketch.compact(true, v3mem);
- WritableMemory v2mem = ForwardCompatibilityTest.convertSerV3toSerV2(v3mem);
+ CompactSketch csk = sketch.compact(true, v3mem);
+ WritableMemory v2mem = (WritableMemory) convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
v2mem.putByte(PreambleUtil.FAMILY_BYTE, (byte)2); //corrupt family
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 03/07: Fix bugs in test
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch BkwardCompat
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit da6bada9c49cfcd11fee04f00256c5d894eeef3e
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Thu Aug 22 14:16:35 2019 -0700
Fix bugs in test
---
.../yahoo/sketches/theta/ForwardCompatibility.java | 14 +--
.../sketches/theta/PairwiseSetOperations.java | 4 +-
.../yahoo/sketches/theta/BackwardConversions.java | 4 +-
.../sketches/theta/ForwardCompatibilityTest.java | 103 ++++++++++++++++++-
.../sketches/theta/PairwiseSetOperationsTest.java | 110 ++++++++++++++++-----
5 files changed, 197 insertions(+), 38 deletions(-)
diff --git a/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java b/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
index 73d3a5d..351f2a2 100644
--- a/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
+++ b/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
@@ -53,6 +53,11 @@ final class ForwardCompatibility {
*/
static final CompactSketch heapify1to3(final Memory srcMem, final long seed) {
final int memCap = (int) srcMem.getCapacity();
+ final int preLongs = extractPreLongs(srcMem); //always 3 for serVer 1
+ if (preLongs != 3) { //TODO Test this
+ throw new SketchesArgumentException("PreLongs must be 3 for SerVer 1: " + preLongs);
+ }
+
final int curCount = extractCurCount(srcMem);
final long thetaLong = extractThetaLong(srcMem);
final boolean empty = Sketch.emptyOnCompact(curCount, thetaLong);
@@ -61,11 +66,6 @@ final class ForwardCompatibility {
return EmptyCompactSketch.getInstance();
}
- final int preLongs = extractPreLongs(srcMem); //always 3 for serVer 1
- if (preLongs != 3) { //TODO Test this
- throw new SketchesArgumentException("PreLongs must be 3 for SerVer 1: " + preLongs);
- }
-
final int reqCap = (curCount + preLongs) << 3;
validateInputSize(reqCap, memCap);
@@ -112,7 +112,7 @@ final class ForwardCompatibility {
if (curCount == 0) {
return EmptyCompactSketch.getInstance();
}
- if (curCount == 1) { //TODO Test this
+ if (curCount == 1) {
reqBytesIn = (preLongs + 1) << 3;
validateInputSize(reqBytesIn, memCap);
final long hash = srcMem.getLong(preLongs << 3);
@@ -134,7 +134,7 @@ final class ForwardCompatibility {
if ((curCount == 0) && (thetaLong == Long.MAX_VALUE)) {
return EmptyCompactSketch.getInstance();
}
- if ((curCount == 1) && (thetaLong == Long.MAX_VALUE)) { //TODO Test here to end
+ if ((curCount == 1) && (thetaLong == Long.MAX_VALUE)) {
reqBytesIn = (preLongs + 1) << 3;
validateInputSize(reqBytesIn, memCap);
final long hash = srcMem.getLong(preLongs << 3);
diff --git a/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java b/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
index 0d358ea..6493693 100644
--- a/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
+++ b/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
@@ -125,8 +125,8 @@ public class PairwiseSetOperations {
final int sw = (swA << 2) | swB;
switch (sw) {
case 5: //skA == null/ECS; skB == null; return EmptyCompactSketch.
- case 6: //skA == null/ECS; skB == empty; return EmptyCompactSketch.
- case 9: { //skA == empty; skB == null/ECS; return EmptyCompactSketch.
+ case 6: //skA == null/ECS; skB == empty; return EmptyCompactSketch. *
+ case 9: { //skA == empty; skB == null/ECS; return EmptyCompactSketch. *
return EmptyCompactSketch.getInstance();
}
case 7: { //skA == null/ECS; skB == valid; return skB
diff --git a/src/test/java/com/yahoo/sketches/theta/BackwardConversions.java b/src/test/java/com/yahoo/sketches/theta/BackwardConversions.java
index f4a8986..e1ea220 100644
--- a/src/test/java/com/yahoo/sketches/theta/BackwardConversions.java
+++ b/src/test/java/com/yahoo/sketches/theta/BackwardConversions.java
@@ -197,8 +197,8 @@ public class BackwardConversions {
}
if (skV3 instanceof SingleItemSketch) {
SingleItemSketch sis = (SingleItemSketch) skV3;
- wmem = WritableMemory.allocate(16);
- wmem.putByte(0, (byte) 1); //preLongs
+ wmem = WritableMemory.allocate(24);
+ wmem.putByte(0, (byte) 2); //preLongs
wmem.putByte(1, (byte) 2); //SerVer
wmem.putByte(2, (byte) 3); //SetSketch
byte flags = (byte) 0xA; //NoRebuild, notEmpty, ReadOnly, LE
diff --git a/src/test/java/com/yahoo/sketches/theta/ForwardCompatibilityTest.java b/src/test/java/com/yahoo/sketches/theta/ForwardCompatibilityTest.java
index 8ff5f53..5c2536e 100644
--- a/src/test/java/com/yahoo/sketches/theta/ForwardCompatibilityTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/ForwardCompatibilityTest.java
@@ -51,6 +51,15 @@ public class ForwardCompatibilityTest {
}
@Test(expectedExceptions = SketchesArgumentException.class)
+ public void checkSerVer1_badPrelongs() {
+ CompactSketch csk = EmptyCompactSketch.getInstance();
+ Memory srcMem = convertSerVer3toSerVer1(csk);
+ WritableMemory srcMemW = (WritableMemory) srcMem;
+ srcMemW.putByte(0, (byte) 1);
+ Sketch.heapify(srcMemW); //throws because bad preLongs
+ }
+
+ @Test(expectedExceptions = SketchesArgumentException.class)
public void checkSerVer1_tooSmall() {
UpdateSketch usk = Sketches.updateSketchBuilder().build();
usk.update(1);
@@ -80,7 +89,7 @@ public class ForwardCompatibilityTest {
}
@Test
- public void checkSerVer2_Empty() {
+ public void checkSerVer2_1PreLong_Empty() {
CompactSketch csk = EmptyCompactSketch.getInstance();
Memory srcMem = convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
Sketch sketch = Sketch.heapify(srcMem);
@@ -94,9 +103,32 @@ public class ForwardCompatibilityTest {
}
@Test
- public void checkSerVer2_24Bytes_0Values() {
+ public void checkSerVer2_2PreLongs_Empty() {
UpdateSketch usk = Sketches.updateSketchBuilder().setLogNominalEntries(4).build();
- for (int i = 0; i < 32; i++) { usk.update(i); }
+ for (int i = 0; i < 2; i++) { usk.update(i); } //exact mode
+ CompactSketch csk = usk.compact(true, null);
+ Memory srcMem = convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
+
+ WritableMemory srcMemW = WritableMemory.allocate(16);
+ srcMem.copyTo(0, srcMemW, 0, 16);
+ PreambleUtil.setEmpty(srcMemW); //Force
+ assertTrue(PreambleUtil.isEmpty(srcMemW));
+ srcMemW.putInt(8, 0); //corrupt curCount = 0
+
+ Sketch sketch = Sketch.heapify(srcMemW);
+ assertEquals(sketch.isEmpty(), true); //was forced true
+ assertEquals(sketch.isEstimationMode(), false);
+ assertEquals(sketch.isDirect(), false);
+ assertEquals(sketch.hasMemory(), false);
+ assertEquals(sketch.isCompact(), true);
+ assertEquals(sketch.isOrdered(), true);
+ assertTrue(sketch instanceof EmptyCompactSketch);
+ }
+
+ @Test
+ public void checkSerVer2_3PreLongs_Empty() {
+ UpdateSketch usk = Sketches.updateSketchBuilder().setLogNominalEntries(4).build();
+ for (int i = 0; i < 32; i++) { usk.update(i); } //est mode
CompactSketch csk = usk.compact(true, null);
Memory srcMem = convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
@@ -118,6 +150,71 @@ public class ForwardCompatibilityTest {
}
@Test
+ public void checkSerVer2_2PreLongs_1Value() {
+ UpdateSketch usk = Sketches.updateSketchBuilder().setLogNominalEntries(4).build();
+ usk.update(1); //exact mode
+ CompactSketch csk = usk.compact(true, null);
+ Memory srcMem = convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
+
+ Sketch sketch = Sketch.heapify(srcMem);
+ assertEquals(sketch.isEmpty(), false);
+ assertEquals(sketch.isEstimationMode(), false);
+ assertEquals(sketch.isDirect(), false);
+ assertEquals(sketch.hasMemory(), false);
+ assertEquals(sketch.isCompact(), true);
+ assertEquals(sketch.isOrdered(), true);
+ assertTrue(sketch instanceof SingleItemSketch);
+ }
+
+ @Test
+ public void checkSerVer2_3PreLongs_1Value() {
+ UpdateSketch usk = Sketches.updateSketchBuilder().setLogNominalEntries(4).build();
+ for (int i = 0; i < 32; i++) { usk.update(i); } //est mode
+ CompactSketch csk = usk.compact(true, null);
+ Memory srcMem = convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
+
+ WritableMemory srcMemW = WritableMemory.allocate(32);
+ srcMem.copyTo(0, srcMemW, 0, 32);
+ srcMemW.putInt(8, 1); //corrupt curCount = 1
+ srcMemW.putLong(16, Long.MAX_VALUE); //corrupt theta to make it look exact
+ long[] cache = csk.getCache();
+ srcMemW.putLong(24, cache[0]); //corrupt cache with only one value
+
+ Sketch sketch = Sketch.heapify(srcMemW);
+ assertEquals(sketch.isEmpty(), false);
+ assertEquals(sketch.isEstimationMode(), false);
+ assertEquals(sketch.isDirect(), false);
+ assertEquals(sketch.hasMemory(), false);
+ assertEquals(sketch.isCompact(), true);
+ assertEquals(sketch.isOrdered(), true);
+ assertTrue(sketch instanceof SingleItemSketch);
+ }
+
+ @Test
+ public void checkSerVer2_3PreLongs_1Value_ThLessthan1() {
+ UpdateSketch usk = Sketches.updateSketchBuilder().setLogNominalEntries(4).build();
+ for (int i = 0; i < 32; i++) { usk.update(i); } //est mode
+ CompactSketch csk = usk.compact(true, null);
+ Memory srcMem = convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
+
+ WritableMemory srcMemW = WritableMemory.allocate(32);
+ srcMem.copyTo(0, srcMemW, 0, 32);
+ srcMemW.putInt(8, 1); //corrupt curCount = 1
+ //srcMemW.putLong(16, Long.MAX_VALUE);
+ long[] cache = csk.getCache();
+ srcMemW.putLong(24, cache[0]); //corrupt cache with only one value
+
+ Sketch sketch = Sketch.heapify(srcMemW);
+ assertEquals(sketch.isEmpty(), false);
+ assertEquals(sketch.isEstimationMode(), true);
+ assertEquals(sketch.isDirect(), false);
+ assertEquals(sketch.hasMemory(), false);
+ assertEquals(sketch.isCompact(), true);
+ assertEquals(sketch.isOrdered(), true);
+ assertTrue(sketch instanceof HeapCompactOrderedSketch);
+ }
+
+ @Test
public void printlnTest() {
println("PRINTING: "+this.getClass().getName());
}
diff --git a/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java b/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java
index bda7bcd..7e3c77b 100644
--- a/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java
@@ -271,63 +271,125 @@ public class PairwiseSetOperationsTest {
}
@Test
- public void checkEmptyRules() {
+ public void checkEmptyNullRules() {
int k = 16;
UpdateSketch uskA = UpdateSketch.builder().setNominalEntries(k).build();
UpdateSketch uskB = UpdateSketch.builder().setNominalEntries(k).build();
- CompactSketch cskA = uskA.compact();
- CompactSketch cskB = uskB.compact();
+ CompactSketch cskAempty = uskA.compact();
+ CompactSketch cskBempty = uskB.compact();
+ CompactSketch cskAnull = null;
+ CompactSketch cskBnull = null;
Union union = SetOperation.builder().setNominalEntries(k).buildUnion();
AnotB aNotB = SetOperation.builder().buildANotB();
Intersection inter = SetOperation.builder().buildIntersection();
CompactSketch cskC, cskR;
+ //Null, Null
+ union.update(cskAnull);
+ union.update(cskBnull);
+ cskC = union.getResult();
+ cskR = PairwiseSetOperations.union(cskAnull, cskBnull, k);
+ assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ union.reset();
+
+ inter.update(cskAnull);
+ inter.update(cskBnull);
+ cskC = inter.getResult();
+ cskR = PairwiseSetOperations.intersect(cskAnull, cskBnull);
+ assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ inter.reset();
+
+ aNotB.update(cskAnull, cskBnull);
+ cskC = aNotB.getResult();
+ cskR = PairwiseSetOperations.aNotB(cskAnull, cskBnull);
+ assertEquals(cskC.isEmpty(), cskR.isEmpty());
+
+ //Null, Empty
+ union.update(cskAnull);
+ union.update(cskBempty);
+ cskC = union.getResult();
+ cskR = PairwiseSetOperations.union(cskAnull, cskBempty, k);
+ assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ union.reset();
+
+ inter.update(cskAnull);
+ inter.update(cskBempty);
+ cskC = inter.getResult();
+ cskR = PairwiseSetOperations.intersect(cskAnull, cskBempty);
+ assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ inter.reset();
+
+ aNotB.update(cskAnull, cskBempty);
+ cskC = aNotB.getResult();
+ cskR = PairwiseSetOperations.aNotB(cskAnull, cskBempty);
+ assertEquals(cskC.isEmpty(), cskR.isEmpty());
+
+ //Empty, Null
+ union.update(cskAempty);
+ union.update(cskBnull);
+ cskC = union.getResult();
+ cskR = PairwiseSetOperations.union(cskAempty, cskBnull, k);
+ assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ union.reset();
+
+ inter.update(cskAempty);
+ inter.update(cskBnull);
+ cskC = inter.getResult();
+ cskR = PairwiseSetOperations.intersect(cskAempty, cskBnull);
+ assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ inter.reset();
+
+ aNotB.update(cskAempty, cskBnull);
+ cskC = aNotB.getResult();
+ cskR = PairwiseSetOperations.aNotB(cskAempty, cskBnull);
+ assertEquals(cskC.isEmpty(), cskR.isEmpty());
+
//Empty, Empty
- union.update(cskA);
- union.update(cskB);
+ union.update(cskAempty);
+ union.update(cskBempty);
cskC = union.getResult();
- cskR = PairwiseSetOperations.union(cskA, cskB, k);
+ cskR = PairwiseSetOperations.union(cskAempty, cskBempty, k);
assertEquals(cskC.isEmpty(), cskR.isEmpty());
union.reset();
- inter.update(cskA);
- inter.update(cskB);
+ inter.update(cskAempty);
+ inter.update(cskBempty);
cskC = inter.getResult();
- cskR = PairwiseSetOperations.intersect(cskA, cskB);
+ cskR = PairwiseSetOperations.intersect(cskAempty, cskBempty);
assertEquals(cskC.isEmpty(), cskR.isEmpty());
inter.reset();
- aNotB.update(cskA, cskB);
+ aNotB.update(cskAempty, cskBempty);
cskC = aNotB.getResult();
- cskR = PairwiseSetOperations.aNotB(cskA, cskB);
+ cskR = PairwiseSetOperations.aNotB(cskAempty, cskBempty);
assertEquals(cskC.isEmpty(), cskR.isEmpty());
//NotEmpty, Empty
uskA.update(1);
- cskA = uskA.compact();
+ CompactSketch cskA1 = uskA.compact();
- union.update(cskA);
- union.update(cskB);
+ union.update(cskA1);
+ union.update(cskBempty);
cskC = union.getResult();
- cskR = PairwiseSetOperations.union(cskA, cskB, k);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ cskR = PairwiseSetOperations.union(cskA1, cskBempty, k);
+ assertEquals(!cskC.isEmpty(), !cskR.isEmpty());
union.reset();
- inter.update(cskA);
- inter.update(cskB);
+ inter.update(cskA1);
+ inter.update(cskBempty);
cskC = inter.getResult();
- cskR = PairwiseSetOperations.intersect(cskA, cskB);
+ cskR = PairwiseSetOperations.intersect(cskA1, cskBempty);
assertEquals(cskC.isEmpty(), cskR.isEmpty());
inter.reset();
- aNotB.update(cskA, cskB);
+ aNotB.update(cskA1, cskBempty);
cskC = aNotB.getResult();
- cskR = PairwiseSetOperations.aNotB(cskA, cskB);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ cskR = PairwiseSetOperations.aNotB(cskA1, cskBempty);
+ assertEquals(!cskC.isEmpty(), !cskR.isEmpty());
- aNotB.update(cskB, cskA); //check the reverse
+ aNotB.update(cskBempty, cskA1); //check the reverse
cskC = aNotB.getResult();
- cskR = PairwiseSetOperations.aNotB(cskB, cskA);
+ cskR = PairwiseSetOperations.aNotB(cskBempty, cskA1);
assertEquals(cskC.isEmpty(), cskR.isEmpty());
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 04/07: Update unit tests
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch BkwardCompat
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit 98801f01283d6d2ea8a44e387bc84bdcee2c3aa1
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Thu Aug 22 20:15:44 2019 -0700
Update unit tests
---
.../yahoo/sketches/theta/DirectCompactSketch.java | 15 +--
.../sketches/theta/HeapCompactOrderedSketch.java | 25 ++--
.../sketches/theta/PairwiseSetOperations.java | 42 ++-----
.../com/yahoo/sketches/theta/SingleItemSketch.java | 1 -
.../yahoo/sketches/theta/CompactSketchTest.java | 26 +++-
.../sketches/theta/PairwiseSetOperationsTest.java | 136 ++++++---------------
6 files changed, 81 insertions(+), 164 deletions(-)
diff --git a/src/main/java/com/yahoo/sketches/theta/DirectCompactSketch.java b/src/main/java/com/yahoo/sketches/theta/DirectCompactSketch.java
index 24df841..f07dacb 100644
--- a/src/main/java/com/yahoo/sketches/theta/DirectCompactSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/DirectCompactSketch.java
@@ -39,14 +39,10 @@ abstract class DirectCompactSketch extends CompactSketch {
}
//Sketch
-
+ //overidden by EmptyCompactSketch and SingleItemSketch
@Override
public int getCurrentBytes(final boolean compact) { //compact is ignored here
final int preLongs = getCurrentPreambleLongs(true);
- final boolean empty = PreambleUtil.isEmpty(mem_);
- if (preLongs == 1) {
- return (empty) ? 8 : 16; //empty or singleItem
- }
//preLongs > 1
final int curCount = extractCurCount(mem_);
return (preLongs + curCount) << 3;
@@ -57,16 +53,11 @@ abstract class DirectCompactSketch extends CompactSketch {
return new MemoryHashIterator(mem_, getRetainedEntries(), getThetaLong());
}
+ //overidden by EmptyCompactSketch and SingleItemSketch
@Override
public int getRetainedEntries(final boolean valid) { //compact is always valid
- final int preLongs = getCurrentPreambleLongs(true);
- final boolean empty = PreambleUtil.isEmpty(mem_);
- if (preLongs == 1) {
- return (empty) ? 0 : 1;
- }
//preLongs > 1
- final int curCount = extractCurCount(mem_);
- return curCount;
+ return extractCurCount(mem_);
}
@Override
diff --git a/src/main/java/com/yahoo/sketches/theta/HeapCompactOrderedSketch.java b/src/main/java/com/yahoo/sketches/theta/HeapCompactOrderedSketch.java
index 61a062c..59521c0 100644
--- a/src/main/java/com/yahoo/sketches/theta/HeapCompactOrderedSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/HeapCompactOrderedSketch.java
@@ -63,24 +63,15 @@ final class HeapCompactOrderedSketch extends HeapCompactSketch {
final int preLongs = extractPreLongs(srcMem);
final boolean empty = PreambleUtil.isEmpty(srcMem); //checks for cap <= 8
- int curCount = 0;
long thetaLong = Long.MAX_VALUE;
- long[] cache = new long[0];
-
- if (preLongs == 1) {
- if (!empty) { //singleItem
- return new SingleItemSketch(srcMem.getLong(8), memSeedHash);
- }
- //else empty
- } else { //preLongs > 1
- curCount = extractCurCount(srcMem);
- cache = new long[curCount];
- if (preLongs == 2) {
- srcMem.getLongArray(16, cache, 0, curCount);
- } else { //preLongs == 3
- srcMem.getLongArray(24, cache, 0, curCount);
- thetaLong = extractThetaLong(srcMem);
- }
+ //preLongs == 1 handled before this method, so preLongs > 1
+ final int curCount = extractCurCount(srcMem);
+ final long[] cache = new long[curCount];
+ if (preLongs == 2) {
+ srcMem.getLongArray(16, cache, 0, curCount);
+ } else { //preLongs == 3
+ srcMem.getLongArray(24, cache, 0, curCount);
+ thetaLong = extractThetaLong(srcMem);
}
return new HeapCompactOrderedSketch(cache, empty, memSeedHash, curCount, thetaLong);
}
diff --git a/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java b/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
index 6493693..245346a 100644
--- a/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
+++ b/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
@@ -110,44 +110,24 @@ public class PairwiseSetOperations {
//Handle all corner cases with null or empty arguments
//For backward compatibility, we must allow input empties with Theta < 1.0.
final int swA, swB;
- if ((skA == null) || (skA instanceof EmptyCompactSketch)) {
- swA = 1;
- } else {
- checkOrdered(skA);
- swA = skA.isEmpty() ? 2 : 3;
- }
- if ((skB == null) || (skB instanceof EmptyCompactSketch)) {
- swB = 1;
- } else {
- checkOrdered(skB);
- swB = skB.isEmpty() ? 2 : 3;
- }
- final int sw = (swA << 2) | swB;
+ swA = ((skA == null) || (skA instanceof EmptyCompactSketch)) ? 0 : 2;
+ swB = ((skB == null) || (skB instanceof EmptyCompactSketch)) ? 0 : 1;
+ final int sw = swA | swB;
switch (sw) {
- case 5: //skA == null/ECS; skB == null; return EmptyCompactSketch.
- case 6: //skA == null/ECS; skB == empty; return EmptyCompactSketch. *
- case 9: { //skA == empty; skB == null/ECS; return EmptyCompactSketch. *
+ case 0: { //skA == null/ECS; skB == null/ECS; return EmptyCompactSketch.
return EmptyCompactSketch.getInstance();
}
- case 7: { //skA == null/ECS; skB == valid; return skB
+ case 1: { //skA == null/ECS; skB == valid; return skB
+ checkOrdered(skB);
return maybeCutback(skB, k);
}
- case 10: { //skA == empty; skB == empty; return empty
- seedHashesCheck(skA, skB);
- return EmptyCompactSketch.getInstance();
- }
- case 11: { //skA == empty; skB == valid; return skB
- seedHashesCheck(skA, skB);
- return maybeCutback(skB, k);
- }
- case 13: { //skA == valid; skB == null/ECS; return skA
- return maybeCutback(skA, k);
- }
- case 14: { //skA == valid; skB == empty; return skA
- seedHashesCheck(skA, skB);
+ case 2: { //skA == valid; skB == null/ECS; return skA
+ checkOrdered(skA);
return maybeCutback(skA, k);
}
- case 15: { //skA == valid; skB == valid; perform full union
+ case 3: { //skA == valid; skB == valid; perform full union
+ checkOrdered(skA);
+ checkOrdered(skB);
seedHashesCheck(skA, skB);
break;
}
diff --git a/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java b/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java
index 536988c..f09239a 100644
--- a/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java
@@ -89,7 +89,6 @@ public final class SingleItemSketch extends CompactSketch {
if (testPre0SeedHash(memPre0, DEFAULT_SEED_HASH)) {
return new SingleItemSketch(mem.getLong(8));
}
- System.out.println("memPre0 : " + Long.toHexString(memPre0));
final long def = ((DEFAULT_SEED_HASH << 48) | PRE0_LO6);
throw new SketchesArgumentException("Input Memory does not match defualt Preamble. " + LS
+ "Memory Pre0 : " + Long.toHexString(memPre0) + LS
diff --git a/src/test/java/com/yahoo/sketches/theta/CompactSketchTest.java b/src/test/java/com/yahoo/sketches/theta/CompactSketchTest.java
index c7bfe19..ff9fe0f 100644
--- a/src/test/java/com/yahoo/sketches/theta/CompactSketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/CompactSketchTest.java
@@ -174,6 +174,16 @@ public class CompactSketchTest {
assertEquals(testSk.getCurrentPreambleLongs(true), refSk.getCurrentPreambleLongs(true));
}
+ @Test
+ public void checkDirectSingleItemSketch() {
+ UpdateSketch sk = Sketches.updateSketchBuilder().build();
+ sk.update(1);
+ int bytes = sk.getCurrentBytes(true);
+ WritableMemory wmem = WritableMemory.allocate(bytes);
+ sk.compact(true, wmem);
+ Sketch csk2 = Sketch.heapify(wmem);
+ assertTrue(csk2 instanceof SingleItemSketch);
+ }
@Test(expectedExceptions = SketchesArgumentException.class)
public void checkMemTooSmall() {
@@ -220,10 +230,12 @@ public class CompactSketchTest {
public void checkDirectCompactSingleItemSketch() {
UpdateSketch sk = Sketches.updateSketchBuilder().build();
CompactSketch csk = sk.compact(true, WritableMemory.allocate(16));
- assertEquals(csk.getCurrentBytes(true), 8);
+ int bytes = csk.getCurrentBytes(true);
+ assertEquals(bytes, 8);
sk.update(1);
csk = sk.compact(true, WritableMemory.allocate(16));
- assertEquals(csk.getCurrentBytes(true), 16);
+ bytes = csk.getCurrentBytes(true);
+ assertEquals(bytes, 16);
assertTrue(csk == csk.compact());
assertTrue(csk == csk.compact(true, null));
}
@@ -250,6 +262,16 @@ public class CompactSketchTest {
}
@Test
+ public void checkGetCache() {
+ UpdateSketch sk = Sketches.updateSketchBuilder().setP((float).5).build();
+ sk.update(7);
+ int bytes = sk.getCurrentBytes(true);
+ CompactSketch csk = sk.compact(true, WritableMemory.allocate(bytes));
+ long[] cache = csk.getCache();
+ assertTrue(cache.length == 0);
+ }
+
+ @Test
public void printlnTest() {
println("PRINTING: "+this.getClass().getName());
}
diff --git a/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java b/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java
index 7e3c77b..c30eaa6 100644
--- a/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java
@@ -279,118 +279,52 @@ public class PairwiseSetOperationsTest {
CompactSketch cskBempty = uskB.compact();
CompactSketch cskAnull = null;
CompactSketch cskBnull = null;
+ uskA.update(1);
+ CompactSketch cskA1 = uskA.compact();
+
Union union = SetOperation.builder().setNominalEntries(k).buildUnion();
AnotB aNotB = SetOperation.builder().buildANotB();
Intersection inter = SetOperation.builder().buildIntersection();
- CompactSketch cskC, cskR;
-
- //Null, Null
- union.update(cskAnull);
- union.update(cskBnull);
- cskC = union.getResult();
- cskR = PairwiseSetOperations.union(cskAnull, cskBnull, k);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
- union.reset();
-
- inter.update(cskAnull);
- inter.update(cskBnull);
- cskC = inter.getResult();
- cskR = PairwiseSetOperations.intersect(cskAnull, cskBnull);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
- inter.reset();
-
- aNotB.update(cskAnull, cskBnull);
- cskC = aNotB.getResult();
- cskR = PairwiseSetOperations.aNotB(cskAnull, cskBnull);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
-
- //Null, Empty
- union.update(cskAnull);
- union.update(cskBempty);
- cskC = union.getResult();
- cskR = PairwiseSetOperations.union(cskAnull, cskBempty, k);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
- union.reset();
-
- inter.update(cskAnull);
- inter.update(cskBempty);
- cskC = inter.getResult();
- cskR = PairwiseSetOperations.intersect(cskAnull, cskBempty);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
- inter.reset();
-
- aNotB.update(cskAnull, cskBempty);
- cskC = aNotB.getResult();
- cskR = PairwiseSetOperations.aNotB(cskAnull, cskBempty);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
-
- //Empty, Null
- union.update(cskAempty);
- union.update(cskBnull);
- cskC = union.getResult();
- cskR = PairwiseSetOperations.union(cskAempty, cskBnull, k);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
- union.reset();
- inter.update(cskAempty);
- inter.update(cskBnull);
- cskC = inter.getResult();
- cskR = PairwiseSetOperations.intersect(cskAempty, cskBnull);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
- inter.reset();
-
- aNotB.update(cskAempty, cskBnull);
- cskC = aNotB.getResult();
- cskR = PairwiseSetOperations.aNotB(cskAempty, cskBnull);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
-
- //Empty, Empty
- union.update(cskAempty);
- union.update(cskBempty);
- cskC = union.getResult();
- cskR = PairwiseSetOperations.union(cskAempty, cskBempty, k);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
- union.reset();
-
- inter.update(cskAempty);
- inter.update(cskBempty);
- cskC = inter.getResult();
- cskR = PairwiseSetOperations.intersect(cskAempty, cskBempty);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
- inter.reset();
+ checkSetOps(union, inter, aNotB, k, cskAnull, cskBnull); //Null, Null
+ checkSetOps(union, inter, aNotB, k, cskAnull, cskBempty); //Null, Empty
+ checkSetOps(union, inter, aNotB, k, cskAempty, cskBnull); //Empty, Null
+ checkSetOps(union, inter, aNotB, k, cskAempty, cskBempty); //Empty, Empty
+ checkSetOps(union, inter, aNotB, k, cskA1, cskBempty); //NotEmpty, Empty
+ checkSetOps(union, inter, aNotB, k, cskAempty, cskA1); //Empty, NotEmpty
+ }
- aNotB.update(cskAempty, cskBempty);
- cskC = aNotB.getResult();
- cskR = PairwiseSetOperations.aNotB(cskAempty, cskBempty);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ private static void checkSetOps(Union union, Intersection inter, AnotB aNotB, int k,
+ CompactSketch cskA, CompactSketch cskB) {
+ checkUnion(union, cskA, cskB, k);
+ checkIntersection(inter, cskA, cskB);
+ checkAnotB(aNotB, cskA, cskB);
- //NotEmpty, Empty
- uskA.update(1);
- CompactSketch cskA1 = uskA.compact();
+ }
- union.update(cskA1);
- union.update(cskBempty);
- cskC = union.getResult();
- cskR = PairwiseSetOperations.union(cskA1, cskBempty, k);
- assertEquals(!cskC.isEmpty(), !cskR.isEmpty());
+ private static void checkUnion(Union union, CompactSketch cskA, CompactSketch cskB, int k) {
+ union.update(cskA);
+ union.update(cskB);
+ CompactSketch cskU = union.getResult();
+ CompactSketch cskP = PairwiseSetOperations.union(cskA, cskB, k);
+ assertEquals(cskU.isEmpty(), cskP.isEmpty());
union.reset();
+ }
- inter.update(cskA1);
- inter.update(cskBempty);
- cskC = inter.getResult();
- cskR = PairwiseSetOperations.intersect(cskA1, cskBempty);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ private static void checkIntersection(Intersection inter, CompactSketch cskA, CompactSketch cskB) {
+ inter.update(cskA);
+ inter.update(cskB);
+ CompactSketch cskI = inter.getResult();
+ CompactSketch cskP = PairwiseSetOperations.intersect(cskA, cskB);
+ assertEquals(cskI.isEmpty(), cskP.isEmpty());
inter.reset();
+ }
- aNotB.update(cskA1, cskBempty);
- cskC = aNotB.getResult();
- cskR = PairwiseSetOperations.aNotB(cskA1, cskBempty);
- assertEquals(!cskC.isEmpty(), !cskR.isEmpty());
-
- aNotB.update(cskBempty, cskA1); //check the reverse
- cskC = aNotB.getResult();
- cskR = PairwiseSetOperations.aNotB(cskBempty, cskA1);
- assertEquals(cskC.isEmpty(), cskR.isEmpty());
+ private static void checkAnotB(AnotB aNotB, CompactSketch cskA, CompactSketch cskB) {
+ aNotB.update(cskA, cskB);
+ CompactSketch cskD = aNotB.getResult();
+ CompactSketch cskP = PairwiseSetOperations.aNotB(cskA, cskB);
+ assertEquals(cskD.isEmpty(), cskP.isEmpty());
}
@Test
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 06/07: remove comment
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch BkwardCompat
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit 48fbc162465443eec864ed552606a20c15485834
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Fri Aug 23 11:46:54 2019 -0700
remove comment
---
src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java b/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
index 351f2a2..bd14f20 100644
--- a/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
+++ b/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
@@ -54,7 +54,7 @@ final class ForwardCompatibility {
static final CompactSketch heapify1to3(final Memory srcMem, final long seed) {
final int memCap = (int) srcMem.getCapacity();
final int preLongs = extractPreLongs(srcMem); //always 3 for serVer 1
- if (preLongs != 3) { //TODO Test this
+ if (preLongs != 3) {
throw new SketchesArgumentException("PreLongs must be 3 for SerVer 1: " + preLongs);
}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org
[incubator-datasketches-java] 07/07: More Unit tests. Fine tuning
of union merge operations and Pairwise Set Operations.
Posted by le...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch BkwardCompat
in repository https://gitbox.apache.org/repos/asf/incubator-datasketches-java.git
commit a0888e9f86b57d1289a2098cc497b3fcc54c3367
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Sun Aug 25 17:57:52 2019 -0700
More Unit tests. Fine tuning of union merge operations and Pairwise Set
Operations.
---
.../yahoo/sketches/theta/ForwardCompatibility.java | 8 +-
.../sketches/theta/PairwiseSetOperations.java | 4 +-
.../com/yahoo/sketches/theta/SetOperation.java | 4 +-
.../com/yahoo/sketches/theta/SingleItemSketch.java | 37 ++-
src/main/java/com/yahoo/sketches/theta/Sketch.java | 20 +-
.../java/com/yahoo/sketches/theta/UnionImpl.java | 299 +++++++++++----------
.../com/yahoo/sketches/theta/UpdateSketch.java | 2 +-
.../sketches/theta/PairwiseSetOperationsTest.java | 34 +++
.../com/yahoo/sketches/theta/SetOperationTest.java | 42 ++-
.../yahoo/sketches/theta/SingleItemSketchTest.java | 15 ++
.../java/com/yahoo/sketches/theta/SketchTest.java | 63 +++++
.../com/yahoo/sketches/theta/UnionImplTest.java | 17 +-
12 files changed, 350 insertions(+), 195 deletions(-)
diff --git a/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java b/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
index bd14f20..cdbdeb9 100644
--- a/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
+++ b/src/main/java/com/yahoo/sketches/theta/ForwardCompatibility.java
@@ -41,7 +41,7 @@ final class ForwardCompatibility {
* Convert a serialization version (SerVer) 1 sketch to a SerVer 3 sketch.
* Note: SerVer 1 sketches always have metadata-longs of 3 and are always stored
* in a compact ordered form, but with 3 different sketch types. All SerVer 1 sketches will
- * be converted to a SerVer 3 sketches.
+ * be converted to a SerVer 3 sketches. There is no concept of p-sampling, no empty bit.
*
* @param srcMem the image of a SerVer 1 sketch
*
@@ -60,7 +60,7 @@ final class ForwardCompatibility {
final int curCount = extractCurCount(srcMem);
final long thetaLong = extractThetaLong(srcMem);
- final boolean empty = Sketch.emptyOnCompact(curCount, thetaLong);
+ final boolean empty = Sketch.emptyFromCountAndTheta(curCount, thetaLong);
if (empty || (memCap <= 24)) { //return empty
return EmptyCompactSketch.getInstance();
@@ -84,7 +84,7 @@ final class ForwardCompatibility {
/**
* Convert a serialization version (SerVer) 2 sketch to a SerVer 3 HeapCompactOrderedSketch.
* Note: SerVer 2 sketches can have metadata-longs of 1,2 or 3 and are always stored
- * in a compact ordered form, but with 4 different sketch types.
+ * in a compact ordered form (not as a hash table), but with 4 different sketch types.
* @param srcMem the image of a SerVer 2 sketch
* @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See Update Hash Seed</a>.
* The seed used for building the sketch image in srcMem
@@ -105,7 +105,7 @@ final class ForwardCompatibility {
validateInputSize(reqBytesIn, memCap);
return EmptyCompactSketch.getInstance();
}
- if (preLongs == 2) { //includes pre0 + count, no theta
+ if (preLongs == 2) { //includes pre0 + count, no theta (== 1.0)
reqBytesIn = preLongs << 3;
validateInputSize(reqBytesIn, memCap);
curCount = extractCurCount(srcMem);
diff --git a/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java b/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
index 245346a..7480ece 100644
--- a/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
+++ b/src/main/java/com/yahoo/sketches/theta/PairwiseSetOperations.java
@@ -194,8 +194,8 @@ public class PairwiseSetOperations {
int curCount = indexOut;
final long[] outArr;
- if (indexOut > k) {
- outArr = Arrays.copyOf(outCache, k); //cutback to k
+ if (indexOut > k) { //unlikely
+ outArr = Arrays.copyOf(outCache, k); //cutback to k, just in case
curCount = k;
} else {
outArr = Arrays.copyOf(outCache, curCount); //copy only valid items
diff --git a/src/main/java/com/yahoo/sketches/theta/SetOperation.java b/src/main/java/com/yahoo/sketches/theta/SetOperation.java
index 387eb69..feef95a 100644
--- a/src/main/java/com/yahoo/sketches/theta/SetOperation.java
+++ b/src/main/java/com/yahoo/sketches/theta/SetOperation.java
@@ -26,7 +26,7 @@ import static com.yahoo.sketches.Util.REBUILD_THRESHOLD;
import static com.yahoo.sketches.Util.ceilingPowerOf2;
import static com.yahoo.sketches.theta.PreambleUtil.FAMILY_BYTE;
import static com.yahoo.sketches.theta.PreambleUtil.SER_VER_BYTE;
-import static com.yahoo.sketches.theta.Sketch.emptyOnCompact;
+import static com.yahoo.sketches.theta.Sketch.emptyFromCountAndTheta;
import static com.yahoo.sketches.theta.Sketch.thetaOnCompact;
import static java.lang.Math.max;
@@ -242,7 +242,7 @@ public abstract class SetOperation {
final short seedHash, final int curCount, long thetaLong, final boolean dstOrdered,
final WritableMemory dstMem) {
thetaLong = thetaOnCompact(empty, curCount, thetaLong);
- empty = emptyOnCompact(curCount, thetaLong);
+ empty = emptyFromCountAndTheta(curCount, thetaLong);
if (empty) {
final EmptyCompactSketch sk = EmptyCompactSketch.getInstance();
if (dstMem != null) {
diff --git a/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java b/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java
index f09239a..50f3665 100644
--- a/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/SingleItemSketch.java
@@ -29,6 +29,7 @@ import static java.nio.charset.StandardCharsets.UTF_8;
import com.yahoo.memory.Memory;
import com.yahoo.sketches.SketchesArgumentException;
+import com.yahoo.sketches.Util;
/**
* @author Lee Rhodes
@@ -44,7 +45,7 @@ public final class SingleItemSketch extends CompactSketch {
private final long[] arr = new long[2];
- //use to test a candidate pre0 given a seed TODO need?
+ //use to test a candidate pre0 given a seed
static boolean testPre0Seed(final long candidate, final long seed) {
final long seedHash = computeSeedHash(seed) & 0xFFFFL;
return testPre0SeedHash(candidate, seedHash);
@@ -53,7 +54,7 @@ public final class SingleItemSketch extends CompactSketch {
//use to test a candidate pre0 given a seedHash
static boolean testPre0SeedHash(final long candidate, final long seedHash) {
final long test1 = (seedHash << 48) | PRE0_LO6; //no SI bit
- final long test2 = test1 | ((long)SINGLEITEM_FLAG_MASK << 40);
+ final long test2 = test1 | ((long)SINGLEITEM_FLAG_MASK << 40); //adds the SI bit
final long mask = PRE0_MASK; //ignores the SI flag
final long masked = candidate & mask;
return (masked == test1) || (candidate == test2);
@@ -80,40 +81,34 @@ public final class SingleItemSketch extends CompactSketch {
}
/**
- * Creates a SingleItemSketch on the heap given a Memory and assumes the DEFAULT_UPDATE_SEED.
- * @param mem the Memory to be heapified. It must be a least 16 bytes.
+ * Creates a SingleItemSketch on the heap given a SingleItemSketch Memory image and assumes the
+ * DEFAULT_UPDATE_SEED.
+ * @param srcMem the Memory to be heapified. It must be a least 16 bytes.
* @return a SingleItemSketch
*/
- public static SingleItemSketch heapify(final Memory mem) {
- final long memPre0 = mem.getLong(0);
- if (testPre0SeedHash(memPre0, DEFAULT_SEED_HASH)) {
- return new SingleItemSketch(mem.getLong(8));
- }
- final long def = ((DEFAULT_SEED_HASH << 48) | PRE0_LO6);
- throw new SketchesArgumentException("Input Memory does not match defualt Preamble. " + LS
- + "Memory Pre0 : " + Long.toHexString(memPre0) + LS
- + "default Pre0 : " + Long.toHexString(def));
+ public static SingleItemSketch heapify(final Memory srcMem) {
+ return heapify(srcMem, Util.DEFAULT_UPDATE_SEED);
}
/**
- * Creates a SingleItemSketch on the heap given a Memory.
+ * Creates a SingleItemSketch on the heap given a SingleItemSketch Memory image and a seed.
* Checks the seed hash of the given Memory against a hash of the given seed.
- * @param mem the Memory to be heapified
+ * @param srcMem the Memory to be heapified
* @param seed a given hash seed
* @return a SingleItemSketch
*/
- public static SingleItemSketch heapify(final Memory mem, final long seed) {
- final long memPre0 = mem.getLong(0);
- final short seedHashMem = mem.getShort(6);
+ public static SingleItemSketch heapify(final Memory srcMem, final long seed) {
+ final long memPre0 = srcMem.getLong(0);
+ final short seedHashMem = srcMem.getShort(6);
final short seedHashCk = computeSeedHash(seed);
checkSeedHashes(seedHashMem, seedHashCk);
if (testPre0SeedHash(memPre0, seedHashCk)) {
- return new SingleItemSketch(mem.getLong(8), seedHashCk);
+ return new SingleItemSketch(srcMem.getLong(8), seedHashCk);
}
final long def = (((long)seedHashCk << 48) | PRE0_LO6);
throw new SketchesArgumentException("Input Memory does not match required Preamble. " + LS
- + "Memory Pre0 : " + Long.toHexString(memPre0) + LS
- + "default Pre0 : " + Long.toHexString(def));
+ + "Memory Pre0 : " + Long.toHexString(memPre0) + LS
+ + "Should be Pre0 : " + Long.toHexString(def));
}
//Create methods using the default seed
diff --git a/src/main/java/com/yahoo/sketches/theta/Sketch.java b/src/main/java/com/yahoo/sketches/theta/Sketch.java
index 4e32f63..7b78b0a 100644
--- a/src/main/java/com/yahoo/sketches/theta/Sketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/Sketch.java
@@ -593,7 +593,7 @@ public abstract class Sketch {
}
/*
- * The truth table for empty, curCount and theta on compact is as follows:
+ * The truth table for empty, curCount and theta when compacting is as follows:
* <pre>
* Num Theta CurCount Empty State Comments
* 0 1.0 0 T OK The Normal Empty State
@@ -607,14 +607,14 @@ public abstract class Sketch {
* 7 <1.0 !0 F OK This corresponds to a sketch in estimation mode
* </pre>
* <p>thetaOnCompact() checks for only #4 and corrects theta.
- * <p>emptyOnCompact() corrects for #1, 2, 6 if they occur
- * <p>First apply thetaOnCompact() then emptyOnCompact().
+ * <p>emptyFromCountAndTheta() corrects for #1, 2, 6 if they occur
+ * <p>First apply thetaOnCompact() then emptyFromCountAndTheta().
*/
static final long thetaOnCompact(final boolean empty, final int curCount, final long thetaLong) {
return (empty && (curCount == 0) && (thetaLong < Long.MAX_VALUE)) ? Long.MAX_VALUE : thetaLong;
}
- static final boolean emptyOnCompact(final int curCount, final long thetaLong) {
+ static final boolean emptyFromCountAndTheta(final int curCount, final long thetaLong) {
return ((curCount == 0) && (thetaLong == Long.MAX_VALUE));
}
@@ -652,18 +652,18 @@ public abstract class Sketch {
* @return a Sketch
*/
private static final Sketch heapifyFromMemory(final Memory srcMem, final long seed) {
+ final long cap = srcMem.getCapacity();
+ if (cap < 8) {
+ throw new SketchesArgumentException(
+ "Corrupted: valid sketch must be at least 8 bytes.");
+ }
final byte familyID = srcMem.getByte(FAMILY_BYTE);
+ final Family family = idToFamily(familyID);
final int preLongs = PreambleUtil.extractPreLongs(srcMem);
final int flags = PreambleUtil.extractFlags(srcMem);
final boolean orderedFlag = (flags & ORDERED_FLAG_MASK) != 0;
final boolean compactFlag = (flags & COMPACT_FLAG_MASK) != 0;
- final Family family = idToFamily(familyID);
- final long cap = srcMem.getCapacity();
- if (cap < 8) {
- throw new SketchesArgumentException(
- "Corrupted: valid sketch must be at least 8 bytes.");
- }
switch (family) {
case ALPHA: {
if (compactFlag) {
diff --git a/src/main/java/com/yahoo/sketches/theta/UnionImpl.java b/src/main/java/com/yahoo/sketches/theta/UnionImpl.java
index 0005e2a..8b5dfcb 100644
--- a/src/main/java/com/yahoo/sketches/theta/UnionImpl.java
+++ b/src/main/java/com/yahoo/sketches/theta/UnionImpl.java
@@ -22,18 +22,19 @@ package com.yahoo.sketches.theta;
import static com.yahoo.sketches.QuickSelect.selectExcludingZeros;
import static com.yahoo.sketches.theta.CompactSketch.compactCache;
import static com.yahoo.sketches.theta.PreambleUtil.COMPACT_FLAG_MASK;
-import static com.yahoo.sketches.theta.PreambleUtil.FAMILY_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.FLAGS_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.LG_ARR_LONGS_BYTE;
import static com.yahoo.sketches.theta.PreambleUtil.ORDERED_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.PREAMBLE_LONGS_BYTE;
-import static com.yahoo.sketches.theta.PreambleUtil.RETAINED_ENTRIES_INT;
-import static com.yahoo.sketches.theta.PreambleUtil.SEED_HASH_SHORT;
-import static com.yahoo.sketches.theta.PreambleUtil.SER_VER_BYTE;
import static com.yahoo.sketches.theta.PreambleUtil.THETA_LONG;
import static com.yahoo.sketches.theta.PreambleUtil.UNION_THETA_LONG;
import static com.yahoo.sketches.theta.PreambleUtil.clearEmpty;
+import static com.yahoo.sketches.theta.PreambleUtil.extractCurCount;
import static com.yahoo.sketches.theta.PreambleUtil.extractFamilyID;
+import static com.yahoo.sketches.theta.PreambleUtil.extractFlags;
+import static com.yahoo.sketches.theta.PreambleUtil.extractLgArrLongs;
+import static com.yahoo.sketches.theta.PreambleUtil.extractPreLongs;
+import static com.yahoo.sketches.theta.PreambleUtil.extractSeedHash;
+import static com.yahoo.sketches.theta.PreambleUtil.extractSerVer;
+import static com.yahoo.sketches.theta.PreambleUtil.extractThetaLong;
import static com.yahoo.sketches.theta.PreambleUtil.extractUnionThetaLong;
import static com.yahoo.sketches.theta.PreambleUtil.insertUnionThetaLong;
import static java.lang.Math.min;
@@ -324,53 +325,180 @@ final class UnionImpl extends Union {
@Override
public void update(final Memory skMem) {
if (skMem == null) { return; }
- final int cap = (int)skMem.getCapacity();
+ final int cap = (int) skMem.getCapacity();
if (cap < 16) { return; } //empty or garbage
- if (cap == 16) {
- final long hash = skMem.getLong(8);
- if (hash == 0) { return; } //hash cannot be zero, must be empty
- }
- if (SingleItemSketch.testPre0SeedHash(skMem.getLong(0), seedHash_)) {
- update(skMem.getLong(8));
- return;
- }
+ final int serVer = extractSerVer(skMem);
+ final int fam = extractFamilyID(skMem);
- final int fam = skMem.getByte(FAMILY_BYTE);
- final int serVer = skMem.getByte(SER_VER_BYTE);
-
- if (serVer == 3) { //The OpenSource sketches
+ if (serVer == 3) { //The OpenSource sketches (Aug 4, 2015)
if ((fam < 1) || (fam > 3)) {
throw new SketchesArgumentException(
"Family must be Alpha, QuickSelect, or Compact: " + Family.idToFamily(fam));
}
- Util.checkSeedHashes(seedHash_, skMem.getShort(SEED_HASH_SHORT));
processVer3(skMem);
return;
}
- if (serVer == 2) { //older SetSketch, which is compact and ordered
- if (fam != 3) { //the original SetSketch
- throw new SketchesArgumentException(
- "Family must be old SET_SKETCH: " + Family.idToFamily(fam));
- }
- Util.checkSeedHashes(seedHash_, skMem.getShort(SEED_HASH_SHORT));
+ if (fam != 3) { //In older sketches this family was called the SetSketch
+ throw new SketchesArgumentException(
+ "Family must be old SET_SKETCH (now COMPACT) = 3: " + Family.idToFamily(fam));
+ }
+
+ if (serVer == 2) { //older Sketch, which is compact and ordered
+ Util.checkSeedHashes(seedHash_, (short)extractSeedHash(skMem));
processVer2(skMem);
return;
}
- if (serVer == 1) { //very old SetSketch, which is compact and ordered
- if (fam != 3) { //the original SetSketch
- throw new SketchesArgumentException(
- "Family must be old SET_SKETCH: " + Family.idToFamily(fam));
- }
- if (cap <= 24) { return; } //empty
- processVer1(skMem);
+ if (serVer == 1) { //much older Sketch, which is compact and ordered
+ processVer1(skMem, cap);
return;
}
throw new SketchesArgumentException("SerVer is unknown: " + serVer);
}
+ //Has seedHash, p, could have 0 entries & theta < 1.0,
+ //could be unordered, ordered, compact, or not compact, size >= 16,
+ //could be Alpha, QuickSelect, or Compact.
+ private void processVer3(final Memory skMem) {
+ final int preLongs = extractPreLongs(skMem);
+
+ if (preLongs == 1) { //we know cap >= 16
+ //This test requires compact, ordered, notEmpty, ReadOnly, LE, seedHash is OK;
+ // OR the above and the SI bit is set
+ if (SingleItemSketch.testPre0SeedHash(skMem.getLong(0), seedHash_)) {
+ final long hash = skMem.getLong(8);
+ update(hash); //a hash < 1 will be rejected later
+ return;
+ }
+ return; //empty
+ }
+
+ Util.checkSeedHashes(seedHash_, (short)extractSeedHash(skMem));
+
+ final int curCountIn;
+ final long thetaLongIn;
+
+ if (preLongs == 2) { //exact mode
+ curCountIn = extractCurCount(skMem);
+ if (curCountIn == 0) { return; } //should be > 0, but if it is return empty anyway.
+ thetaLongIn = Long.MAX_VALUE;
+ }
+
+ else { //prelongs == 3
+ //curCount may be 0 (e.g., from intersection); but sketch cannot be empty.
+ curCountIn = extractCurCount(skMem);
+ thetaLongIn = extractThetaLong(skMem);
+ }
+
+ unionThetaLong_ = min(min(unionThetaLong_, thetaLongIn), gadget_.getThetaLong()); //theta rule
+ unionEmpty_ = false;
+ final int flags = extractFlags(skMem);
+ final boolean ordered = (flags & ORDERED_FLAG_MASK) != 0;
+ if (ordered) { //must be compact
+
+ for (int i = 0; i < curCountIn; i++ ) {
+ final int offsetBytes = (preLongs + i) << 3;
+ final long hashIn = skMem.getLong(offsetBytes);
+ if (hashIn >= unionThetaLong_) { break; } // "early stop"
+ gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
+ }
+ }
+
+ else { //not-ordered, could be compact or hash-table form
+ final boolean compact = (flags & COMPACT_FLAG_MASK) != 0;
+ final int size = (compact) ? curCountIn : 1 << extractLgArrLongs(skMem);
+
+ for (int i = 0; i < size; i++ ) {
+ final int offsetBytes = (preLongs + i) << 3;
+ final long hashIn = skMem.getLong(offsetBytes);
+ if ((hashIn <= 0L) || (hashIn >= unionThetaLong_)) { continue; }
+ gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
+ }
+ }
+
+ unionThetaLong_ = min(unionThetaLong_, gadget_.getThetaLong()); //sync thetaLongs
+
+ if (gadget_.hasMemory()) {
+ final WritableMemory wmem = (WritableMemory)gadget_.getMemory();
+ PreambleUtil.insertUnionThetaLong(wmem, unionThetaLong_);
+ PreambleUtil.clearEmpty(wmem);
+ }
+ }
+
+ //has seedHash and p, could have 0 entries & theta,
+ // can only be compact, ordered, size >= 8
+ private void processVer2(final Memory skMem) {
+ final int preLongs = extractPreLongs(skMem);
+
+ if (preLongs == 1) { //does not change anything, return empty
+ return;
+ }
+
+ Util.checkSeedHashes(seedHash_, (short)extractSeedHash(skMem));
+
+ final int curCountIn;
+ final long thetaLongIn;
+
+ if (preLongs == 2) { //exact mode, not empty, cannot be a set operation
+ curCountIn = extractCurCount(skMem);
+ if (curCountIn == 0) { return; } //should be > 0, but if it is return empty anyway.
+ thetaLongIn = Long.MAX_VALUE;
+ }
+
+ else { //prelongs == 3
+ //curCount may be 0 (e.g., from intersection); but sketch cannot be empty.
+ curCountIn = extractCurCount(skMem);
+ thetaLongIn = extractThetaLong(skMem);
+ }
+
+ unionThetaLong_ = min(min(unionThetaLong_, thetaLongIn), gadget_.getThetaLong()); //Theta rule
+ unionEmpty_ = false;
+
+ for (int i = 0; i < curCountIn; i++ ) {
+ final int offsetBytes = (preLongs + i) << 3;
+ final long hashIn = skMem.getLong(offsetBytes);
+ if (hashIn >= unionThetaLong_) { break; } // "early stop"
+ gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
+ }
+
+ unionThetaLong_ = min(unionThetaLong_, gadget_.getThetaLong());
+
+ if (gadget_.hasMemory()) {
+ final WritableMemory wmem = (WritableMemory)gadget_.getMemory();
+ PreambleUtil.insertUnionThetaLong(wmem, unionThetaLong_);
+ PreambleUtil.clearEmpty(wmem);
+ }
+ }
+
+ //no seedHash, assumes given seed is correct. No p, no empty flag, no concept of direct
+ // can only be compact, ordered, size > 24
+ private void processVer1(final Memory skMem, final int cap) {
+ final long thetaLongIn = skMem.getLong(THETA_LONG);
+ final int curCountIn = extractCurCount(skMem);
+ if ((cap <= 24) || ((curCountIn == 0) && (unionThetaLong_ == Long.MAX_VALUE))) {
+ return; //empty
+ }
+
+ unionThetaLong_ = min(min(unionThetaLong_, thetaLongIn), gadget_.getThetaLong()); //Theta rule
+ unionEmpty_ = false;
+
+ final int preLongs = 3;
+ for (int i = 0; i < curCountIn; i++ ) {
+ final int offsetBytes = (preLongs + i) << 3;
+ final long hashIn = skMem.getLong(offsetBytes);
+ if (hashIn >= unionThetaLong_) { break; } // "early stop"
+ gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
+ }
+ unionThetaLong_ = min(unionThetaLong_, gadget_.getThetaLong()); //Theta rule
+ if (gadget_.hasMemory()) {
+ final WritableMemory wmem = (WritableMemory)gadget_.getMemory();
+ PreambleUtil.insertUnionThetaLong(wmem, unionThetaLong_);
+ PreambleUtil.clearEmpty(wmem);
+ }
+ }
+
@Override
public void update(final long datum) {
gadget_.update(datum);
@@ -433,109 +561,4 @@ final class UnionImpl extends Union {
return gadget_.isEmpty() && unionEmpty_;
}
- //no seedHash, assumes given seed is correct. No p, no empty flag, no concept of direct
- // can only be compact, ordered, size > 24
- private void processVer1(final Memory skMem) {
- final long thetaLongIn = skMem.getLong(THETA_LONG);
- final int curCountIn = skMem.getInt(RETAINED_ENTRIES_INT);
- unionThetaLong_ = min(min(unionThetaLong_, thetaLongIn), gadget_.getThetaLong()); //Theta rule
- final boolean emptyIn = (curCountIn == 0) && (unionThetaLong_ == Long.MAX_VALUE);
- if (emptyIn) { return; }
- unionEmpty_ = false;
-
- final int preLongs = 3;
- for (int i = 0; i < curCountIn; i++ ) {
- final int offsetBytes = (preLongs + i) << 3;
- final long hashIn = skMem.getLong(offsetBytes);
- if (hashIn >= unionThetaLong_) { break; } // "early stop"
- gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
- }
- unionThetaLong_ = min(unionThetaLong_, gadget_.getThetaLong()); //Theta rule
- if (gadget_.hasMemory()) {
- final WritableMemory wmem = (WritableMemory)gadget_.getMemory();
- PreambleUtil.insertUnionThetaLong(wmem, unionThetaLong_);
- PreambleUtil.clearEmpty(wmem);
- }
- }
-
- //has seedHash and p, could have 0 entries & theta,
- // can only be compact, ordered, size >= 8
- private void processVer2(final Memory skMem) {
- final int preLongs = skMem.getByte(PREAMBLE_LONGS_BYTE) & 0X3F;
- final int curCount = skMem.getInt(RETAINED_ENTRIES_INT);
- final long thetaLongIn;
- if (preLongs == 1) { //does not change anything {1.0, 0, T}
- return;
- }
- if (preLongs == 2) { //exact mode, not empty
- assert curCount > 0;
- thetaLongIn = Long.MAX_VALUE;
- } else { //prelongs == 3, curCount may be 0 (e.g., from intersection), not empty
- thetaLongIn = skMem.getLong(THETA_LONG);
- }
- unionThetaLong_ = min(min(unionThetaLong_, thetaLongIn), gadget_.getThetaLong()); //Theta rule
- unionEmpty_ = false;
- for (int i = 0; i < curCount; i++ ) {
- final int offsetBytes = (preLongs + i) << 3;
- final long hashIn = skMem.getLong(offsetBytes);
- if (hashIn >= unionThetaLong_) { break; } // "early stop"
- gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
- }
- unionThetaLong_ = min(unionThetaLong_, gadget_.getThetaLong());
- if (gadget_.hasMemory()) {
- final WritableMemory wmem = (WritableMemory)gadget_.getMemory();
- PreambleUtil.insertUnionThetaLong(wmem, unionThetaLong_);
- PreambleUtil.clearEmpty(wmem);
- }
- }
-
- //has seedHash, p, could have 0 entries & theta,
- // could be unordered, ordered, compact, or not, size >= 8
- private void processVer3(final Memory skMem) {
- final int preLongs = skMem.getByte(PREAMBLE_LONGS_BYTE) & 0X3F;
- final int curCountIn;
- final long thetaLongIn;
-
- if (preLongs == 1) { //SingleItem already handled. Treat as empty
- return;
- }
- else if (preLongs == 2) {
- //curCount has to be > 0 and exact mode. Cannot be from intersection. Not empty.
- curCountIn = skMem.getInt(RETAINED_ENTRIES_INT);
- assert curCountIn > 0;
- thetaLongIn = Long.MAX_VALUE;
- }
- else { //prelongs == 3, curCount may be 0 (e.g., from intersection), but not empty.
- curCountIn = skMem.getInt(RETAINED_ENTRIES_INT);
- thetaLongIn = skMem.getLong(THETA_LONG);
- }
- unionThetaLong_ = min(min(unionThetaLong_, thetaLongIn), gadget_.getThetaLong()); //theta rule
- unionEmpty_ = false;
- final boolean ordered = (skMem.getByte(FLAGS_BYTE) & ORDERED_FLAG_MASK) != 0;
- if (ordered) { //must be compact
- for (int i = 0; i < curCountIn; i++ ) {
- final int offsetBytes = (preLongs + i) << 3;
- final long hashIn = skMem.getLong(offsetBytes);
- if (hashIn >= unionThetaLong_) { break; } // "early stop"
- gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
- }
- }
- else { //not-ordered, could be compact or hash-table form
- final boolean compact = (skMem.getByte(FLAGS_BYTE) & COMPACT_FLAG_MASK) != 0;
- final int size = (compact) ? curCountIn : 1 << skMem.getByte(LG_ARR_LONGS_BYTE);
- for (int i = 0; i < size; i++ ) {
- final int offsetBytes = (preLongs + i) << 3;
- final long hashIn = skMem.getLong(offsetBytes);
- if ((hashIn <= 0L) || (hashIn >= unionThetaLong_)) { continue; }
- gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
- }
- }
- unionThetaLong_ = min(unionThetaLong_, gadget_.getThetaLong()); //sync thetaLongs
- if (gadget_.hasMemory()) {
- final WritableMemory wmem = (WritableMemory)gadget_.getMemory();
- PreambleUtil.insertUnionThetaLong(wmem, unionThetaLong_);
- PreambleUtil.clearEmpty(wmem);
- }
- }
-
}
diff --git a/src/main/java/com/yahoo/sketches/theta/UpdateSketch.java b/src/main/java/com/yahoo/sketches/theta/UpdateSketch.java
index 6029457..23c93be 100644
--- a/src/main/java/com/yahoo/sketches/theta/UpdateSketch.java
+++ b/src/main/java/com/yahoo/sketches/theta/UpdateSketch.java
@@ -140,7 +140,7 @@ public abstract class UpdateSketch extends Sketch {
final int curCount = this.getRetainedEntries(true);
long thetaLong = getThetaLong();
thetaLong = Sketch.thetaOnCompact(isEmpty(), curCount, thetaLong);
- final boolean empty = Sketch.emptyOnCompact(curCount, thetaLong);
+ final boolean empty = Sketch.emptyFromCountAndTheta(curCount, thetaLong);
if (empty) {
final EmptyCompactSketch sk = EmptyCompactSketch.getInstance();
if (dstMem != null) {
diff --git a/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java b/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java
index c30eaa6..059c28c 100644
--- a/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/PairwiseSetOperationsTest.java
@@ -271,6 +271,40 @@ public class PairwiseSetOperationsTest {
}
@Test
+ public void checkUnionCutbackToK() {
+ int lgK = 10;
+ int k = 1<<lgK;
+ int u = (3 * k);
+
+ UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
+ UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
+ Union union = SetOperation.builder().setNominalEntries(k).buildUnion();
+
+ for (int i=0; i < u; i++) {
+ usk1.update(i);
+ usk2.update(i + (2 * u));
+ }
+
+ CompactSketch csk1 = usk1.compact(true, null);
+ CompactSketch csk2 = usk2.compact(true, null);
+
+ Sketch pwSk = PairwiseSetOperations.union(csk1, csk2, k);
+ double pwEst = pwSk.getEstimate();
+
+ union.update(csk1);
+ union.update(csk2);
+ CompactSketch stdSk = union.getResult(true, null);
+ double stdEst = stdSk.getEstimate();
+
+ assertEquals(pwEst, stdEst, stdEst * .06);
+
+ usk1.reset();
+ usk2.reset();
+ union.reset();
+
+ }
+
+ @Test
public void checkEmptyNullRules() {
int k = 16;
UpdateSketch uskA = UpdateSketch.builder().setNominalEntries(k).build();
diff --git a/src/test/java/com/yahoo/sketches/theta/SetOperationTest.java b/src/test/java/com/yahoo/sketches/theta/SetOperationTest.java
index ba1ada9..266ff95 100644
--- a/src/test/java/com/yahoo/sketches/theta/SetOperationTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/SetOperationTest.java
@@ -56,12 +56,10 @@ public class SetOperationTest {
UpdateSketch usk1 = UpdateSketch.builder().setSeed(seed).setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setSeed(seed).setNominalEntries(k).build();
- for (int i=0; i<(k/2); i++)
- {
+ for (int i=0; i<(k/2); i++) {
usk1.update(i); //256
}
- for (int i=k/2; i<k; i++)
- {
+ for (int i=k/2; i<k; i++) {
usk2.update(i); //256 no overlap
}
@@ -149,12 +147,10 @@ public class SetOperationTest {
UpdateSketch usk1 = UpdateSketch.builder().setSeed(seed).setNominalEntries(k).build();
UpdateSketch usk2 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<(k/2); i++)
- {
+ for (int i=0; i<(k/2); i++) {
usk1.update(i); //256
}
- for (int i=k/2; i<k; i++)
- {
+ for (int i=k/2; i<k; i++) {
usk2.update(i); //256 no overlap
}
@@ -177,8 +173,7 @@ public class SetOperationTest {
public void checkIllegalSetOpHeapify() {
int k = 64;
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<k; i++)
- {
+ for (int i=0; i<k; i++) {
usk1.update(i); //64
}
byte[] byteArray = usk1.toByteArray();
@@ -190,8 +185,7 @@ public class SetOperationTest {
public void checkIllegalSetOpWrap() {
int k = 64;
UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
- for (int i=0; i<k; i++)
- {
+ for (int i=0; i<k; i++) {
usk1.update(i); //64
}
byte[] byteArray = usk1.toByteArray();
@@ -199,6 +193,30 @@ public class SetOperationTest {
Sketches.wrapIntersection(mem);
}
+ @Test(expectedExceptions = SketchesArgumentException.class)
+ public void checkIllegalSetOpWrap2() {
+ int k = 64;
+ UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
+ for (int i=0; i<k; i++) {
+ usk1.update(i); //64
+ }
+ WritableMemory wmem = WritableMemory.wrap(usk1.toByteArray());
+ PreambleUtil.insertSerVer(wmem, 2); //corrupt
+ Memory mem = wmem;
+ SetOperation.wrap(mem);
+ }
+
+ @Test(expectedExceptions = SketchesArgumentException.class)
+ public void checkIllegalSetOpWrap3() {
+ int k = 64;
+ UpdateSketch usk1 = UpdateSketch.builder().setNominalEntries(k).build();
+ for (int i=0; i<k; i++) {
+ usk1.update(i); //64
+ }
+ WritableMemory wmem = WritableMemory.wrap(usk1.toByteArray());
+ SetOperation.wrap(wmem);
+ }
+
@Test
public void checkBuildSetOps() {
SetOperationBuilder bldr = Sketches.setOperationBuilder();
diff --git a/src/test/java/com/yahoo/sketches/theta/SingleItemSketchTest.java b/src/test/java/com/yahoo/sketches/theta/SingleItemSketchTest.java
index 5bad7dc..722eb04 100644
--- a/src/test/java/com/yahoo/sketches/theta/SingleItemSketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/SingleItemSketchTest.java
@@ -28,11 +28,13 @@ import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertNull;
import static org.testng.Assert.assertTrue;
+import static org.testng.Assert.fail;
import org.testng.annotations.Test;
import com.yahoo.memory.Memory;
import com.yahoo.memory.WritableMemory;
+import com.yahoo.sketches.SketchesArgumentException;
/**
* @author Lee Rhodes
@@ -312,6 +314,19 @@ public class SingleItemSketchTest {
}
@Test
+ public void checkSingleItemBadFlags() {
+ UpdateSketch sk1 = new UpdateSketchBuilder().build();
+ sk1.update(1);
+ WritableMemory wmem = WritableMemory.allocate(16);
+ sk1.compact(true, wmem);
+ wmem.putByte(5, (byte) 0); //corrupt flags
+ try {
+ SingleItemSketch.heapify(wmem);
+ fail();
+ } catch (SketchesArgumentException e) { }
+ }
+
+ @Test
public void printlnTest() {
println("PRINTING: "+this.getClass().getName());
}
diff --git a/src/test/java/com/yahoo/sketches/theta/SketchTest.java b/src/test/java/com/yahoo/sketches/theta/SketchTest.java
index 6992086..852d335 100644
--- a/src/test/java/com/yahoo/sketches/theta/SketchTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/SketchTest.java
@@ -32,10 +32,12 @@ import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVe
import static com.yahoo.sketches.theta.BackwardConversions.convertSerVer3toSerVer2;
import static com.yahoo.sketches.theta.PreambleUtil.COMPACT_FLAG_MASK;
import static com.yahoo.sketches.theta.PreambleUtil.FLAGS_BYTE;
+import static com.yahoo.sketches.theta.PreambleUtil.READ_ONLY_FLAG_MASK;
import static com.yahoo.sketches.theta.Sketch.getMaxCompactSketchBytes;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
+import static org.testng.Assert.fail;
import org.testng.annotations.Test;
@@ -348,6 +350,67 @@ public class SketchTest {
assertEquals(count, k);
}
+ private static WritableMemory createCompactSketchMemory(int k, int u) {
+ UpdateSketch usk = Sketches.updateSketchBuilder().setNominalEntries(k).build();
+ for (int i = 0; i < u; i++) { usk.update(i); }
+ int bytes = Sketch.getMaxCompactSketchBytes(usk.getRetainedEntries(true));
+ WritableMemory wmem = WritableMemory.allocate(bytes);
+ usk.compact(true, wmem);
+ return wmem;
+ }
+
+ @Test
+ public void checkCompactFlagsOnWrap() {
+ WritableMemory wmem = createCompactSketchMemory(16, 32);
+ Sketch sk = Sketch.wrap(wmem);
+ assertTrue(sk instanceof CompactSketch);
+ int flags = PreambleUtil.extractFlags(wmem);
+
+ int flagsNoCompact = flags & ~COMPACT_FLAG_MASK;
+ PreambleUtil.insertFlags(wmem, flagsNoCompact);
+ try {
+ sk = Sketch.wrap(wmem);
+ fail();
+ } catch (SketchesArgumentException e) { }
+
+ int flagsNoReadOnly = flags & ~READ_ONLY_FLAG_MASK;
+ PreambleUtil.insertFlags(wmem, flagsNoReadOnly);
+ try {
+ sk = Sketch.wrap(wmem);
+ fail();
+ } catch (SketchesArgumentException e) { }
+ PreambleUtil.insertFlags(wmem, flags); //repair to original
+ PreambleUtil.insertSerVer(wmem, 5);
+ try {
+ sk = Sketch.wrap(wmem);
+ fail();
+ } catch (SketchesArgumentException e) { }
+ }
+
+ @Test
+ public void checkCompactSizeAndFlagsOnHeapify() {
+ WritableMemory wmem = createCompactSketchMemory(16, 32);
+ Sketch sk = Sketch.heapify(wmem);
+ assertTrue(sk instanceof CompactSketch);
+ int flags = PreambleUtil.extractFlags(wmem);
+
+ int flagsNoCompact = flags & ~READ_ONLY_FLAG_MASK;
+ PreambleUtil.insertFlags(wmem, flagsNoCompact);
+ try {
+ sk = Sketch.heapify(wmem);
+ fail();
+ } catch (SketchesArgumentException e) { }
+
+ wmem = WritableMemory.allocate(7);
+ PreambleUtil.insertSerVer(wmem, 3);
+ //PreambleUtil.insertFamilyID(wmem, 3);
+ try {
+ sk = Sketch.heapify(wmem);
+ fail();
+ } catch (SketchesArgumentException e) { }
+
+ }
+
@Test
public void printlnTest() {
println("PRINTING: "+this.getClass().getName());
diff --git a/src/test/java/com/yahoo/sketches/theta/UnionImplTest.java b/src/test/java/com/yahoo/sketches/theta/UnionImplTest.java
index 781ccc8..96a0bfa 100644
--- a/src/test/java/com/yahoo/sketches/theta/UnionImplTest.java
+++ b/src/test/java/com/yahoo/sketches/theta/UnionImplTest.java
@@ -119,15 +119,14 @@ public class UnionImplTest {
@Test(expectedExceptions = SketchesArgumentException.class)
public void checkVer1FamilyException() {
int k = 16;
- WritableMemory v3mem = WritableMemory.wrap(new byte[(k*8) + 24]);
UpdateSketch sketch = Sketches.updateSketchBuilder().setNominalEntries(k).build();
for (int i=0; i<k; i++) {
sketch.update(i);
}
- CompactSketch csk = sketch.compact(true, v3mem);
+ CompactSketch csk = sketch.compact(true, null);
WritableMemory v1mem = (WritableMemory) convertSerVer3toSerVer1(csk);
- v1mem.putByte(PreambleUtil.FAMILY_BYTE, (byte)2); //corrupt family
+ v1mem.putByte(PreambleUtil.FAMILY_BYTE, (byte) 2); //corrupt family
Union union = Sketches.setOperationBuilder().setNominalEntries(k).buildUnion();
union.update(v1mem);
@@ -136,12 +135,11 @@ public class UnionImplTest {
@Test(expectedExceptions = SketchesArgumentException.class)
public void checkVer2FamilyException() {
int k = 16;
- WritableMemory v3mem = WritableMemory.wrap(new byte[(k*8) + 24]);
UpdateSketch sketch = Sketches.updateSketchBuilder().setNominalEntries(k).build();
for (int i=0; i<k; i++) {
sketch.update(i);
}
- CompactSketch csk = sketch.compact(true, v3mem);
+ CompactSketch csk = sketch.compact(true, null);
WritableMemory v2mem = (WritableMemory) convertSerVer3toSerVer2(csk, Util.DEFAULT_UPDATE_SEED);
v2mem.putByte(PreambleUtil.FAMILY_BYTE, (byte)2); //corrupt family
@@ -151,6 +149,15 @@ public class UnionImplTest {
}
@Test
+ public void checkVer2EmptyHandling() {
+ int k = 16;
+ UpdateSketch sketch = Sketches.updateSketchBuilder().setNominalEntries(k).build();
+ Memory mem = convertSerVer3toSerVer2(sketch.compact(), Util.DEFAULT_UPDATE_SEED);
+ Union union = Sketches.setOperationBuilder().setNominalEntries(k).buildUnion();
+ union.update(mem);
+ }
+
+ @Test
public void checkMoveAndResize() {
int k = 1 << 12;
int u = 2 * k;
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org