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 2024/04/16 05:39:26 UTC
(datasketches-java) 01/01: Implemented fix for min/max for Floats, Doubles and Items Sorted Views.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch fix_min_max
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 54396e0ea79bea29e76c781cb6f07ecd7a7dd4e6
Author: Lee Rhodes <le...@gmail.com>
AuthorDate: Mon Apr 15 22:39:14 2024 -0700
Implemented fix for min/max for Floats, Doubles and Items Sorted Views.
Also fixed a problem I discovered in the deserialization for Boolean
quantiles, but it would also have shown up with other types. The data
was ok, but the max value would have been incorrect.
Also fixed some problems with some of the tests.
Along the way I also replaced "back-slash-n" with platform independent
"LS" in the sketches I touched.
Also moved some functions like getCDF(..) and getPMF(...) into parent
interfaces as default functions. Now the three parent interfaces for
Doubles SV, Floats SV and Items SV are all code-parallel.
---
.../kll/KllDirectCompactItemsSketch.java | 6 +-
.../apache/datasketches/kll/KllDoublesSketch.java | 2 +-
.../apache/datasketches/kll/KllFloatsSketch.java | 3 +-
.../datasketches/kll/KllHeapDoublesSketch.java | 2 +-
.../apache/datasketches/kll/KllItemsSketch.java | 33 ++--
.../apache/datasketches/kll/KllMemoryValidate.java | 2 +-
.../datasketches/quantiles/DoublesSketch.java | 2 +-
.../apache/datasketches/quantiles/ItemsUtil.java | 1 -
.../quantilescommon/DoublesSketchSortedView.java | 40 +++--
.../quantilescommon/FloatsSketchSortedView.java | 42 +++--
.../quantilescommon/GenericSortedView.java | 32 +++-
.../quantilescommon/IncludeMinMax.java | 179 ++++++++++++++++++
.../quantilescommon/ItemsSketchSortedView.java | 108 ++---------
.../org/apache/datasketches/req/ReqSketch.java | 3 +-
.../KllDirectCompactItemsSketchIteratorTest.java | 26 ++-
.../datasketches/kll/KllMiscDoublesTest.java | 40 ++---
.../apache/datasketches/kll/KllMiscFloatsTest.java | 40 ++---
.../apache/datasketches/kll/KllMiscItemsTest.java | 43 +++--
.../quantilescommon/IncludeMinMaxTest.java | 199 +++++++++++++++++++++
19 files changed, 592 insertions(+), 211 deletions(-)
diff --git a/src/main/java/org/apache/datasketches/kll/KllDirectCompactItemsSketch.java b/src/main/java/org/apache/datasketches/kll/KllDirectCompactItemsSketch.java
index 3e493a7f..05324d28 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDirectCompactItemsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDirectCompactItemsSketch.java
@@ -90,8 +90,10 @@ final class KllDirectCompactItemsSketch<T> extends KllItemsSketch<T> {
return serDe.deserializeFromMemory(mem, DATA_START_ADR_SINGLE_ITEM, 1)[0];
}
//sketchStructure == COMPACT_FULL
- final int offset = DATA_START_ADR + getNumLevels() * Integer.BYTES;
- return serDe.deserializeFromMemory(mem, offset, 2)[1];
+ final int baseOffset = DATA_START_ADR + getNumLevels() * Integer.BYTES;
+ final int offset = baseOffset + serDe.sizeOf(mem, baseOffset, 1); //size of minItem
+
+ return serDe.deserializeFromMemory(mem, offset, 1)[0];
}
@Override
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
index 8c60e42e..59cda435 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java
@@ -561,7 +561,7 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou
cumWeights = new long[numQuantiles];
populateFromSketch(srcQuantiles, srcLevels, srcNumLevels, numQuantiles);
return new DoublesSketchSortedView(
- quantiles, cumWeights, getN(), getMaxItemInternal(), getMinItemInternal());
+ quantiles, cumWeights, KllDoublesSketch.this);
}
private void populateFromSketch(final double[] srcQuantiles, final int[] srcLevels,
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
index 4fcee5ee..48781631 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java
@@ -560,8 +560,7 @@ public abstract class KllFloatsSketch extends KllSketch implements QuantilesFloa
quantiles = new float[numQuantiles];
cumWeights = new long[numQuantiles];
populateFromSketch(srcQuantiles, srcLevels, srcNumLevels, numQuantiles);
- return new FloatsSketchSortedView(
- quantiles, cumWeights, getN(), getMaxItemInternal(), getMinItemInternal());
+ return new FloatsSketchSortedView(quantiles, cumWeights, KllFloatsSketch.this);
}
private void populateFromSketch(final float[] srcQuantiles, final int[] srcLevels,
diff --git a/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java
index 3682c8ed..dfb8219f 100644
--- a/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java
@@ -286,7 +286,7 @@ final class KllHeapDoublesSketch extends KllDoublesSketch {
void setDoubleItemsArrayAt(final int index, final double item) { this.doubleItems[index] = item; }
@Override
- void setDoubleItemsArrayAt(final int dstIndex, final double[] srcItems, final int srcOffset, final int length) { //TODO
+ void setDoubleItemsArrayAt(final int dstIndex, final double[] srcItems, final int srcOffset, final int length) {
System.arraycopy(srcItems, srcOffset, doubleItems, dstIndex, length);
}
diff --git a/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java b/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java
index 6ad57cf6..392da067 100644
--- a/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java
+++ b/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java
@@ -297,7 +297,7 @@ public abstract class KllItemsSketch<T> extends KllSketch implements QuantilesGe
@Override
public String toString(final boolean withLevels, final boolean withLevelsAndItems) {
KllSketch sketch = this;
- if (withLevelsAndItems && sketchStructure != UPDATABLE) {
+ if (hasMemory()) {
final Memory mem = getWritableMemory();
assert mem != null;
sketch = KllItemsSketch.heapify((Memory)getWritableMemory(), comparator, serDe);
@@ -422,49 +422,50 @@ public abstract class KllItemsSketch<T> extends KllSketch implements QuantilesGe
@SuppressWarnings({"rawtypes"})
private final class CreateSortedView {
T[] quantiles;
- long[] cumWeights;
+ long[] cumWeights; //The new cumWeights array
ItemsSketchSortedView<T> getSV() {
- if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
- if (getN() == 0) { throw new SketchesArgumentException(EMPTY_MSG); }
+ if (isEmpty() || getN() == 0) { throw new SketchesArgumentException(EMPTY_MSG); }
final T[] srcQuantiles = getTotalItemsArray();
- final int[] srcLevels = levelsArr;
+ final int[] srcLevelsArr = levelsArr;
final int srcNumLevels = getNumLevels();
if (!isLevelZeroSorted()) {
- Arrays.sort(srcQuantiles, srcLevels[0], srcLevels[1], comparator);
+ Arrays.sort(srcQuantiles, srcLevelsArr[0], srcLevelsArr[1], comparator);
if (!hasMemory()) { setLevelZeroSorted(true); }
}
final int numQuantiles = getNumRetained();
quantiles = (T[]) Array.newInstance(serDe.getClassOfT(), numQuantiles);
cumWeights = new long[numQuantiles];
- populateFromSketch(srcQuantiles, srcLevels, srcNumLevels, numQuantiles);
+ populateFromSketch(srcQuantiles, srcLevelsArr, srcNumLevels, numQuantiles);
final QuantilesGenericAPI<T> sk = KllItemsSketch.this;
return new ItemsSketchSortedView(quantiles, cumWeights, sk);
}
- private void populateFromSketch(final Object[] srcQuantiles, final int[] srcLevels,
+ private void populateFromSketch(final Object[] srcQuantiles, final int[] srcLevelsArr,
final int srcNumLevels, final int numItems) {
- final int[] myLevels = new int[srcNumLevels + 1];
- final int offset = srcLevels[0];
- System.arraycopy(srcQuantiles, offset, quantiles, 0, numItems);
+ //Remove free space from both itemsArray and levels array
+ final int[] myLevelsArr = new int[srcLevelsArr.length];
+ final int offset = srcLevelsArr[0];
+ System.arraycopy(srcQuantiles, offset, quantiles, 0, numItems); //remove free space from quantiles arr
+ //fill the new cumWeights array with the correct weights and adjust the levels array to match.
int srcLevel = 0;
int dstLevel = 0;
long weight = 1;
while (srcLevel < srcNumLevels) {
- final int fromIndex = srcLevels[srcLevel] - offset;
- final int toIndex = srcLevels[srcLevel + 1] - offset; // exclusive
+ final int fromIndex = srcLevelsArr[srcLevel] - offset;
+ final int toIndex = srcLevelsArr[srcLevel + 1] - offset; // exclusive
if (fromIndex < toIndex) { // if equal, skip empty level
Arrays.fill(cumWeights, fromIndex, toIndex, weight);
- myLevels[dstLevel] = fromIndex;
- myLevels[dstLevel + 1] = toIndex;
+ myLevelsArr[dstLevel] = fromIndex;
+ myLevelsArr[dstLevel + 1] = toIndex;
dstLevel++;
}
srcLevel++;
weight *= 2;
}
final int numLevels = dstLevel;
- blockyTandemMergeSort(quantiles, cumWeights, myLevels, numLevels, comparator); //create unit weights
+ blockyTandemMergeSort(quantiles, cumWeights, myLevelsArr, numLevels, comparator); //create unit weights
KllHelper.convertToCumulative(cumWeights);
}
} //End of class CreateSortedView
diff --git a/src/main/java/org/apache/datasketches/kll/KllMemoryValidate.java b/src/main/java/org/apache/datasketches/kll/KllMemoryValidate.java
index ae4e3f23..67ac09ef 100644
--- a/src/main/java/org/apache/datasketches/kll/KllMemoryValidate.java
+++ b/src/main/java/org/apache/datasketches/kll/KllMemoryValidate.java
@@ -174,7 +174,7 @@ final class KllMemoryValidate {
final int levelsLen = updatable ? levelsArr.length : levelsArr.length - 1;
final int numItems = updatable ? capacityItems : retainedItems;
- int offsetBytes = DATA_START_ADR + levelsLen * Integer.BYTES;
+ int offsetBytes = DATA_START_ADR + levelsLen * Integer.BYTES; //levels array
if (sketchType == ITEMS_SKETCH) {
if (serDe instanceof ArrayOfBooleansSerDe) {
offsetBytes += serDe.sizeOf(srcMem, offsetBytes, numItems) + 2; //2 for min & max
diff --git a/src/main/java/org/apache/datasketches/quantiles/DoublesSketch.java b/src/main/java/org/apache/datasketches/quantiles/DoublesSketch.java
index 1d148268..03f84116 100644
--- a/src/main/java/org/apache/datasketches/quantiles/DoublesSketch.java
+++ b/src/main/java/org/apache/datasketches/quantiles/DoublesSketch.java
@@ -597,7 +597,7 @@ public abstract class DoublesSketch implements QuantilesDoublesAPI {
if (convertToCumulative(svCumWeights) != totalN) {
throw new SketchesStateException("Sorted View is misconfigured. TotalN does not match cumWeights.");
}
- return new DoublesSketchSortedView(svQuantiles, svCumWeights, totalN, getMaxItem(), getMinItem());
+ return new DoublesSketchSortedView(svQuantiles, svCumWeights, this);
}
private final static void populateFromDoublesSketch(
diff --git a/src/main/java/org/apache/datasketches/quantiles/ItemsUtil.java b/src/main/java/org/apache/datasketches/quantiles/ItemsUtil.java
index 63e40ce7..81a0654f 100644
--- a/src/main/java/org/apache/datasketches/quantiles/ItemsUtil.java
+++ b/src/main/java/org/apache/datasketches/quantiles/ItemsUtil.java
@@ -80,7 +80,6 @@ final class ItemsUtil {
assert (n / (2L * sketch.getK())) == sketch.getBitPattern(); // internal consistency check
}
- //TODO change booleans to "withLevels", "withLevelsAndItems"
static <T> String toString(final boolean withLevels, final boolean withLevelsAndItems,
final ItemsSketch<T> sk) {
final StringBuilder sb = new StringBuilder();
diff --git a/src/main/java/org/apache/datasketches/quantilescommon/DoublesSketchSortedView.java b/src/main/java/org/apache/datasketches/quantilescommon/DoublesSketchSortedView.java
index 564f8aa1..b5a8b8a4 100644
--- a/src/main/java/org/apache/datasketches/quantilescommon/DoublesSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/quantilescommon/DoublesSketchSortedView.java
@@ -19,6 +19,7 @@
package org.apache.datasketches.quantilescommon;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.DoublesPair;
import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INCLUSIVE;
import static org.apache.datasketches.quantilescommon.QuantilesAPI.EMPTY_MSG;
import static org.apache.datasketches.quantilescommon.QuantilesUtil.getNaturalRank;
@@ -34,24 +35,36 @@ public final class DoublesSketchSortedView implements DoublesSortedView {
private final double[] quantiles;
private final long[] cumWeights; //cumulative natural weights
private final long totalN;
- private final double maxItem;
- private final double minItem;
/**
* Construct from elements, also used in testing.
* @param quantiles sorted array of quantiles
* @param cumWeights sorted, monotonically increasing cumulative weights.
- * @param totalN the total number of items presented to the sketch.
- * @param maxItem of type double
- * @param minItem of type double
+ * @param sk the underlying quantile sketch.
*/
- public DoublesSketchSortedView(final double[] quantiles, final long[] cumWeights, final long totalN,
- final double maxItem, final double minItem) {
- this.quantiles = quantiles;
- this.cumWeights = cumWeights;
+ public DoublesSketchSortedView(
+ final double[] quantiles,
+ final long[] cumWeights,
+ final QuantilesDoublesAPI sk) {
+ final DoublesPair dPair =
+ IncludeMinMax.includeDoublesMinMax(quantiles, cumWeights, sk.getMaxItem(), sk.getMinItem());
+ this.quantiles = dPair.quantiles;
+ this.cumWeights = dPair.cumWeights;
+ this.totalN = sk.getN();
+ }
+
+ //Used for testing
+ DoublesSketchSortedView(
+ final double[] quantiles,
+ final long[] cumWeights,
+ final long totalN,
+ final double maxItem,
+ final double minItem) {
+ final DoublesPair dPair =
+ IncludeMinMax.includeDoublesMinMax(quantiles, cumWeights, maxItem, minItem);
+ this.quantiles = dPair.quantiles;
+ this.cumWeights = dPair.cumWeights;
this.totalN = totalN;
- this.maxItem = maxItem;
- this.minItem = minItem;
}
@Override
@@ -61,12 +74,13 @@ public final class DoublesSketchSortedView implements DoublesSortedView {
@Override
public double getMaxItem() {
- return maxItem;
+ final int top = quantiles.length - 1;
+ return quantiles[top];
}
@Override
public double getMinItem() {
- return minItem;
+ return quantiles[0];
}
@Override
diff --git a/src/main/java/org/apache/datasketches/quantilescommon/FloatsSketchSortedView.java b/src/main/java/org/apache/datasketches/quantilescommon/FloatsSketchSortedView.java
index 7dfb4053..4c2276f0 100644
--- a/src/main/java/org/apache/datasketches/quantilescommon/FloatsSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/quantilescommon/FloatsSketchSortedView.java
@@ -19,6 +19,7 @@
package org.apache.datasketches.quantilescommon;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.FloatsPair;
import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INCLUSIVE;
import static org.apache.datasketches.quantilescommon.QuantilesAPI.EMPTY_MSG;
import static org.apache.datasketches.quantilescommon.QuantilesUtil.getNaturalRank;
@@ -34,24 +35,36 @@ public class FloatsSketchSortedView implements FloatsSortedView {
private final float[] quantiles;
private final long[] cumWeights; //cumulative natural weights
private final long totalN;
- private final float maxItem;
- private final float minItem;
/**
- * Construct from elements, also used in testing.
+ * Construct Sorted View.
* @param quantiles sorted array of quantiles
* @param cumWeights sorted, monotonically increasing cumulative weights.
- * @param totalN the total number of items presented to the sketch.
- * @param maxItem of type double
- * @param minItem of type double
+ * @param sk the underlying quantile sketch.
*/
- public FloatsSketchSortedView(final float[] quantiles, final long[] cumWeights, final long totalN,
- final float maxItem, final float minItem) {
- this.quantiles = quantiles;
- this.cumWeights = cumWeights;
+ public FloatsSketchSortedView(
+ final float[] quantiles,
+ final long[] cumWeights,
+ final QuantilesFloatsAPI sk) {
+ final FloatsPair fPair =
+ IncludeMinMax.includeFloatsMinMax(quantiles, cumWeights, sk.getMaxItem(), sk.getMinItem());
+ this.quantiles = fPair.quantiles;
+ this.cumWeights = fPair.cumWeights;
+ this.totalN = sk.getN();
+ }
+
+ //Used for testing
+ FloatsSketchSortedView(
+ final float[] quantiles,
+ final long[] cumWeights,
+ final long totalN,
+ final float maxItem,
+ final float minItem) {
+ final FloatsPair fPair =
+ IncludeMinMax.includeFloatsMinMax(quantiles, cumWeights, maxItem, minItem);
+ this.quantiles = fPair.quantiles;
+ this.cumWeights = fPair.cumWeights;
this.totalN = totalN;
- this.maxItem = maxItem;
- this.minItem = minItem;
}
@Override
@@ -61,12 +74,13 @@ public class FloatsSketchSortedView implements FloatsSortedView {
@Override
public float getMaxItem() {
- return maxItem;
+ final int top = quantiles.length - 1;
+ return quantiles[top];
}
@Override
public float getMinItem() {
- return minItem;
+ return quantiles[0];
}
@Override
diff --git a/src/main/java/org/apache/datasketches/quantilescommon/GenericSortedView.java b/src/main/java/org/apache/datasketches/quantilescommon/GenericSortedView.java
index 4f9da76a..74a7a4b8 100644
--- a/src/main/java/org/apache/datasketches/quantilescommon/GenericSortedView.java
+++ b/src/main/java/org/apache/datasketches/quantilescommon/GenericSortedView.java
@@ -19,6 +19,8 @@
package org.apache.datasketches.quantilescommon;
+import static org.apache.datasketches.quantilescommon.QuantilesAPI.EMPTY_MSG;
+
import java.util.Comparator;
import org.apache.datasketches.common.SketchesArgumentException;
@@ -67,7 +69,23 @@ public interface GenericSortedView<T> extends PartitioningFeature<T>, SketchPar
* @return a discrete CDF array of m+1 double ranks (or cumulative probabilities) on the interval [0.0, 1.0].
* @throws IllegalArgumentException if sketch is empty.
*/
- double[] getCDF(T[] splitPoints, QuantileSearchCriteria searchCrit);
+ default double[] getCDF(final T[] splitPoints, final QuantileSearchCriteria searchCrit) {
+ if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
+ GenericSortedView.validateItems(splitPoints, getComparator());
+ final int len = splitPoints.length + 1;
+ final double[] buckets = new double[len];
+ for (int i = 0; i < len - 1; i++) {
+ buckets[i] = getRank(splitPoints[i], searchCrit);
+ }
+ buckets[len - 1] = 1.0;
+ return buckets;
+ }
+
+ /**
+ * Gets the Comparator for this generic type.
+ * @return the Comparator for this generic type.
+ */
+ Comparator<? super T> getComparator();
/**
* Returns the maximum item of the stream. This may be distinct from the largest item retained by the
@@ -127,7 +145,17 @@ public interface GenericSortedView<T> extends PartitioningFeature<T>, SketchPar
* @return a PMF array of m+1 probability masses as doubles on the interval [0.0, 1.0].
* @throws IllegalArgumentException if sketch is empty.
*/
- double[] getPMF(T[] splitPoints, QuantileSearchCriteria searchCrit);
+ //double[] getPMF(T[] splitPoints, QuantileSearchCriteria searchCrit);
+ default double[] getPMF(final T[] splitPoints, final QuantileSearchCriteria searchCrit) {
+ if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
+ GenericSortedView.validateItems(splitPoints, getComparator());
+ final double[] buckets = getCDF(splitPoints, searchCrit);
+ final int len = buckets.length;
+ for (int i = len; i-- > 1; ) {
+ buckets[i] -= buckets[i - 1];
+ }
+ return buckets;
+ }
/**
* Gets the approximate quantile of the given normalized rank and the given search criterion.
diff --git a/src/main/java/org/apache/datasketches/quantilescommon/IncludeMinMax.java b/src/main/java/org/apache/datasketches/quantilescommon/IncludeMinMax.java
new file mode 100644
index 00000000..9397fcd0
--- /dev/null
+++ b/src/main/java/org/apache/datasketches/quantilescommon/IncludeMinMax.java
@@ -0,0 +1,179 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.datasketches.quantilescommon;
+
+import java.lang.reflect.Array;
+import java.util.Comparator;
+
+/**
+ * This class reinserts the min and max values into the sorted view arrays as required.
+ */
+public class IncludeMinMax {
+
+ public static class DoublesPair {
+ public double[] quantiles;
+ public long[] cumWeights;
+
+ public DoublesPair(final double[] quantiles, final long[] cumWeights) {
+ this.quantiles = quantiles;
+ this.cumWeights = cumWeights;
+ }
+ }
+
+ public static class FloatsPair {
+ public float[] quantiles;
+ public long[] cumWeights;
+
+ public FloatsPair(final float[] quantiles, final long[] cumWeights) {
+ this.quantiles = quantiles;
+ this.cumWeights = cumWeights;
+ }
+ }
+
+ public static class ItemsPair<T> {
+ public T[] quantiles;
+ public long[] cumWeights;
+
+ public ItemsPair(final T[] quantiles, final long[] cumWeights) {
+ this.quantiles = quantiles;
+ this.cumWeights = cumWeights;
+ }
+ }
+
+ public static DoublesPair includeDoublesMinMax(
+ final double[] quantilesIn,
+ final long[] cumWeightsIn,
+ final double maxItem,
+ final double minItem) {
+ final int lenIn = cumWeightsIn.length;
+ final boolean adjLow = quantilesIn[0] != minItem; //if true, adjust the low end
+ final boolean adjHigh = quantilesIn[lenIn - 1] != maxItem; //if true, adjust the high end
+ int adjLen = lenIn; //this will be the length of the local copies of quantiles and cumWeights
+ adjLen += adjLow ? 1 : 0;
+ adjLen += adjHigh ? 1 : 0;
+ final double[] adjQuantiles;
+ final long[] adjCumWeights;
+ if (adjLen > lenIn) { //is any adjustment required at all?
+ adjQuantiles = new double[adjLen];
+ adjCumWeights = new long[adjLen];
+ final int offset = adjLow ? 1 : 0;
+ System.arraycopy(quantilesIn, 0, adjQuantiles, offset, lenIn);
+ System.arraycopy(cumWeightsIn,0, adjCumWeights, offset, lenIn);
+
+ //Adjust the low end if required.
+ if (adjLow) {
+ adjQuantiles[0] = minItem;
+ adjCumWeights[0] = 1;
+ }
+
+ if (adjHigh) {
+ adjQuantiles[adjLen - 1] = maxItem;
+ adjCumWeights[adjLen - 1] = cumWeightsIn[lenIn - 1];
+ adjCumWeights[adjLen - 2] = cumWeightsIn[lenIn - 1] - 1;
+ }
+ } else { //both min and max are already in place, no adjustments are required.
+ adjQuantiles = quantilesIn;
+ adjCumWeights = cumWeightsIn;
+
+ } //END of Adjust End Points
+ return new DoublesPair(adjQuantiles, adjCumWeights);
+ }
+
+ public static FloatsPair includeFloatsMinMax(
+ final float[] quantilesIn,
+ final long[] cumWeightsIn,
+ final float maxItem,
+ final float minItem) {
+ final int lenIn = cumWeightsIn.length;
+ final boolean adjLow = quantilesIn[0] != minItem; //if true, adjust the low end
+ final boolean adjHigh = quantilesIn[lenIn - 1] != maxItem; //if true, adjust the high end
+ int adjLen = lenIn; //this will be the length of the local copies of quantiles and cumWeights
+ adjLen += adjLow ? 1 : 0;
+ adjLen += adjHigh ? 1 : 0;
+ final float[] adjQuantiles;
+ final long[] adjCumWeights;
+ if (adjLen > lenIn) { //is any adjustment required at all?
+ adjQuantiles = new float[adjLen];
+ adjCumWeights = new long[adjLen];
+ final int offset = adjLow ? 1 : 0;
+ System.arraycopy(quantilesIn, 0, adjQuantiles, offset, lenIn);
+ System.arraycopy(cumWeightsIn,0, adjCumWeights, offset, lenIn);
+
+ //Adjust the low end if required.
+ if (adjLow) {
+ adjQuantiles[0] = minItem;
+ adjCumWeights[0] = 1;
+ }
+
+ if (adjHigh) {
+ adjQuantiles[adjLen - 1] = maxItem;
+ adjCumWeights[adjLen - 1] = cumWeightsIn[lenIn - 1];
+ adjCumWeights[adjLen - 2] = cumWeightsIn[lenIn - 1] - 1;
+ }
+ } else { //both min and max are already in place, no adjustments are required.
+ adjQuantiles = quantilesIn;
+ adjCumWeights = cumWeightsIn;
+
+ } //END of Adjust End Points
+ return new FloatsPair(adjQuantiles, adjCumWeights);
+ }
+
+ @SuppressWarnings("unchecked")
+ public static <T> ItemsPair<T> includeItemsMinMax(
+ final T[] quantilesIn,
+ final long[] cumWeightsIn,
+ final T maxItem,
+ final T minItem,
+ final Comparator<? super T> comparator) {
+ final int lenIn = cumWeightsIn.length;
+ final boolean adjLow = comparator.compare(quantilesIn[0], minItem) != 0; //if true, adjust the low end
+ final boolean adjHigh = comparator.compare(quantilesIn[lenIn - 1], maxItem) != 0; //if true, adjust the high end
+ int adjLen = lenIn; //this will be the length of the local copies of quantiles and cumWeights
+ adjLen += adjLow ? 1 : 0;
+ adjLen += adjHigh ? 1 : 0;
+ final T[] adjQuantiles;
+ final long[] adjCumWeights;
+ if (adjLen > lenIn) { //is any adjustment required at all?
+ adjQuantiles = (T[]) Array.newInstance(minItem.getClass(), adjLen);
+ adjCumWeights = new long[adjLen];
+ final int offset = adjLow ? 1 : 0;
+ System.arraycopy(quantilesIn, 0, adjQuantiles, offset, lenIn);
+ System.arraycopy(cumWeightsIn,0, adjCumWeights, offset, lenIn);
+
+ //Adjust the low end if required.
+ if (adjLow) {
+ adjQuantiles[0] = minItem;
+ adjCumWeights[0] = 1;
+ }
+
+ if (adjHigh) {
+ adjQuantiles[adjLen - 1] = maxItem;
+ adjCumWeights[adjLen - 1] = cumWeightsIn[lenIn - 1];
+ adjCumWeights[adjLen - 2] = cumWeightsIn[lenIn - 1] - 1;
+ }
+ } else { //both min and max are already in place, no adjustments are required.
+ adjQuantiles = quantilesIn;
+ adjCumWeights = cumWeightsIn;
+
+ } //END of Adjust End Points
+ return new ItemsPair<>(adjQuantiles, adjCumWeights);
+ }
+
+}
diff --git a/src/main/java/org/apache/datasketches/quantilescommon/ItemsSketchSortedView.java b/src/main/java/org/apache/datasketches/quantilescommon/ItemsSketchSortedView.java
index 67e92ad2..4af4acd5 100644
--- a/src/main/java/org/apache/datasketches/quantilescommon/ItemsSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/quantilescommon/ItemsSketchSortedView.java
@@ -21,6 +21,7 @@ package org.apache.datasketches.quantilescommon;
import static java.lang.Math.min;
import static org.apache.datasketches.quantilescommon.GenericInequalitySearch.find;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.ItemsPair;
import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INCLUSIVE;
import static org.apache.datasketches.quantilescommon.QuantilesAPI.EMPTY_MSG;
import static org.apache.datasketches.quantilescommon.QuantilesUtil.evenlySpacedDoubles;
@@ -43,14 +44,12 @@ public class ItemsSketchSortedView<T> implements GenericSortedView<T> {
private final long[] cumWeights; //cumulative natural weights
private final long totalN;
private final Comparator<? super T> comparator;
- private final T maxItem;
- private final T minItem;
private final Class<T> clazz;
private final double normRankError;
private final int numRetItems;
/**
- * Construct from elements, also used in testing.
+ * Construct Sorted View.
* @param quantiles sorted array of quantiles
* @param cumWeights sorted, monotonically increasing cumulative weights.
* @param sk the underlying quantile sketch.
@@ -59,12 +58,12 @@ public class ItemsSketchSortedView<T> implements GenericSortedView<T> {
final T[] quantiles,
final long[] cumWeights, //or Natural Ranks
final QuantilesGenericAPI<T> sk) {
- this.quantiles = quantiles;
- this.cumWeights = cumWeights;
- this.totalN = sk.getN();
this.comparator = sk.getComparator();
- this.maxItem = sk.getMaxItem();
- this.minItem = sk.getMinItem();
+ final ItemsPair<T> iPair =
+ IncludeMinMax.includeItemsMinMax(quantiles, cumWeights, sk.getMaxItem(), sk.getMinItem(), comparator);
+ this.quantiles = iPair.quantiles;
+ this.cumWeights = iPair.cumWeights;
+ this.totalN = sk.getN();
this.clazz = sk.getClassOfT();
this.normRankError = sk.getNormalizedRankError(true);
this.numRetItems = sk.getNumRetained();
@@ -81,12 +80,12 @@ public class ItemsSketchSortedView<T> implements GenericSortedView<T> {
final Class<T> clazz,
final double normRankError,
final int numRetItems) {
- this.quantiles = quantiles;
- this.cumWeights = cumWeights;
- this.totalN = totalN;
this.comparator = comparator;
- this.maxItem = maxItem;
- this.minItem = minItem;
+ final ItemsPair<T> iPair =
+ IncludeMinMax.includeItemsMinMax(quantiles, cumWeights, maxItem, minItem, comparator);
+ this.quantiles = iPair.quantiles;
+ this.cumWeights = iPair.cumWeights;
+ this.totalN = totalN;
this.clazz = clazz;
this.normRankError = normRankError;
this.numRetItems = numRetItems;
@@ -95,17 +94,7 @@ public class ItemsSketchSortedView<T> implements GenericSortedView<T> {
//end of constructors
@Override
- public double[] getCDF(final T[] splitPoints, final QuantileSearchCriteria searchCrit) {
- if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
- GenericSortedView.validateItems(splitPoints, comparator);
- final int len = splitPoints.length + 1;
- final double[] buckets = new double[len];
- for (int i = 0; i < len - 1; i++) {
- buckets[i] = getRank(splitPoints[i], searchCrit);
- }
- buckets[len - 1] = 1.0;
- return buckets;
- }
+ public Comparator<? super T> getComparator() { return comparator; }
@Override
public long[] getCumulativeWeights() {
@@ -114,12 +103,13 @@ public class ItemsSketchSortedView<T> implements GenericSortedView<T> {
@Override
public T getMaxItem() {
- return maxItem;
+ final int top = quantiles.length - 1;
+ return quantiles[top];
}
@Override
public T getMinItem() {
- return minItem;
+ return quantiles[0];
}
@Override
@@ -170,59 +160,11 @@ public class ItemsSketchSortedView<T> implements GenericSortedView<T> {
final long[] partNatRanks = new long[partArrLen];
final double[] partNormRanks = new double[partArrLen];
- //Adjust End Points: The ends of the Sorted View arrays may be missing the actual MinItem and MaxItem bounds,
- // which are absolutely required when partitioning, especially inner partitions.
-
- //Are the minItem and maxItem already in place?
- final int svLen = cumWeights.length;
- int adjLen = svLen; //this will be the length of the local copies of quantiles and cumWeights
- final boolean adjLow = quantiles[0] != minItem; //if true, adjust the low end
- final boolean adjHigh = quantiles[svLen - 1] != maxItem; //if true, adjust the high end
- adjLen += adjLow ? 1 : 0;
- adjLen += adjHigh ? 1 : 0;
-
- //These are local copies of the quantiles and cumWeights arrays just for partitioning.
- //The rest of the SV remains unchanged.
- final T[] adjQuantiles;
- final long[] adjCumWeights;
- if (adjLen > svLen) { //is any adjustment required at all?
- adjQuantiles = (T[]) new Object[adjLen];
- adjCumWeights = new long[adjLen];
- final int offset = adjLow ? 1 : 0;
- System.arraycopy(quantiles, 0, adjQuantiles, offset, svLen);
- System.arraycopy(cumWeights,0, adjCumWeights, offset, svLen);
-
- //Adjust the low end if required.
- if (adjLow) {
- adjQuantiles[0] = minItem;
- adjCumWeights[0] = 1;
- }
- /* When inserting a MaxItem, if required, we can't just add it at the top of the quantiles array,
- * we have to adjust the cumulative weight of the item just before it as well so that the maximum cumulative
- * weight at the top still equals totalN.
- *
- * Quiz #1: Adjusting the adjacent weight is not required at the bottom. Why?
- *
- * Quiz #2: If the maxItem is missing, the quantile that is currently in the top
- * position must have a weight >= 2. Why?
- *
- * Thus, it is safe to subtract 1.
- */
- if (adjHigh) {
- adjQuantiles[adjLen - 1] = maxItem;
- adjCumWeights[adjLen - 1] = cumWeights[svLen - 1];
- adjCumWeights[adjLen - 2] = cumWeights[svLen - 1] - 1;
- }
- } else { //both min and max are already in place, no adjustments are required.
- adjQuantiles = quantiles;
- adjCumWeights = cumWeights;
- } //END of Adjust End Points
-
//compute the quantiles and natural and normalized ranks for the partition boundaries.
for (int i = 0; i < partArrLen; i++) {
- final int index = getQuantileIndex(searchNormRanks[i], adjCumWeights, searchCrit);
- partQuantiles[i] = adjQuantiles[index];
- final long cumWt = adjCumWeights[index];
+ final int index = getQuantileIndex(searchNormRanks[i], cumWeights, searchCrit);
+ partQuantiles[i] = quantiles[index];
+ final long cumWt = cumWeights[index];
partNatRanks[i] = cumWt;
partNormRanks[i] = (double)cumWt / totalN;
}
@@ -238,18 +180,6 @@ public class ItemsSketchSortedView<T> implements GenericSortedView<T> {
return gpb;
} //End of getPartitionBoundaries
- @Override
- public double[] getPMF(final T[] splitPoints, final QuantileSearchCriteria searchCrit) {
- if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
- GenericSortedView.validateItems(splitPoints, comparator);
- final double[] buckets = getCDF(splitPoints, searchCrit);
- final int len = buckets.length;
- for (int i = len; i-- > 1; ) {
- buckets[i] -= buckets[i - 1];
- }
- return buckets;
- }
-
@Override
public T getQuantile(final double rank, final QuantileSearchCriteria searchCrit) {
if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); }
diff --git a/src/main/java/org/apache/datasketches/req/ReqSketch.java b/src/main/java/org/apache/datasketches/req/ReqSketch.java
index fbe5a5ba..bda7d4b9 100644
--- a/src/main/java/org/apache/datasketches/req/ReqSketch.java
+++ b/src/main/java/org/apache/datasketches/req/ReqSketch.java
@@ -594,8 +594,7 @@ public final class ReqSketch extends BaseReqSketch {
count += bufInLen;
}
createCumulativeNativeRanks();
- return new FloatsSketchSortedView(
- quantiles, cumWeights, getN(), getMaxItem(), getMinItem());
+ return new FloatsSketchSortedView(quantiles, cumWeights, ReqSketch.this);
}
/**
diff --git a/src/test/java/org/apache/datasketches/kll/KllDirectCompactItemsSketchIteratorTest.java b/src/test/java/org/apache/datasketches/kll/KllDirectCompactItemsSketchIteratorTest.java
index a359996c..01e76e82 100644
--- a/src/test/java/org/apache/datasketches/kll/KllDirectCompactItemsSketchIteratorTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllDirectCompactItemsSketchIteratorTest.java
@@ -31,10 +31,12 @@ import org.apache.datasketches.common.ArrayOfStringsSerDe;
import org.apache.datasketches.common.Util;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.quantilescommon.GenericSortedViewIterator;
+import org.apache.datasketches.quantilescommon.ItemsSketchSortedView;
import org.apache.datasketches.quantilescommon.QuantilesGenericSketchIterator;
import org.testng.Assert;
import org.testng.annotations.Test;
+@SuppressWarnings("unused")
public class KllDirectCompactItemsSketchIteratorTest {
private ArrayOfStringsSerDe serDe = new ArrayOfStringsSerDe();
@@ -84,13 +86,15 @@ public class KllDirectCompactItemsSketchIteratorTest {
@Test
public void twoItemSketchForSortedViewIterator() {
- KllItemsSketch<String> sk = KllItemsSketch.newHeapInstance(Comparator.naturalOrder(), serDe);
+ KllItemsSketch<String> sk = KllItemsSketch.newHeapInstance(20, Comparator.naturalOrder(), serDe);
sk.update("1");
sk.update("2");
+ println(sk.toString(true, true));
byte[] byteArr = sk.toByteArray();
KllItemsSketch<String> sk2 = KllItemsSketch.wrap(Memory.wrap(byteArr), Comparator.naturalOrder(), serDe);
assertTrue(sk2 instanceof KllDirectCompactItemsSketch);
- GenericSortedViewIterator<String> itr = sk2.getSortedView().iterator();
+ ItemsSketchSortedView<String> sv = sk2.getSortedView();
+ GenericSortedViewIterator<String> itr = sv.iterator();
assertTrue(itr.next());
@@ -133,4 +137,22 @@ public class KllDirectCompactItemsSketchIteratorTest {
Assert.assertEquals(weight, n);
}
}
+
+ private final static boolean enablePrinting = false;
+
+ /**
+ * @param format the format
+ * @param args the args
+ */
+ private static final void printf(final String format, final Object ...args) {
+ if (enablePrinting) { System.out.printf(format, args); }
+ }
+
+ /**
+ * @param o the Object to println
+ */
+ private static final void println(final Object o) {
+ if (enablePrinting) { System.out.println(o.toString()); }
+ }
+
}
diff --git a/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java
index 41f19325..e58c2741 100644
--- a/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java
@@ -19,8 +19,8 @@
package org.apache.datasketches.kll;
+import static org.apache.datasketches.common.Util.LS;
import static org.apache.datasketches.common.Util.bitAt;
-import static org.apache.datasketches.kll.KllHelper.getGrowthSchemeForGivenN;
import static org.apache.datasketches.kll.KllSketch.SketchType.DOUBLES_SKETCH;
import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INCLUSIVE;
import static org.testng.Assert.assertEquals;
@@ -30,7 +30,6 @@ import static org.testng.Assert.fail;
import org.apache.datasketches.common.SketchesArgumentException;
import org.apache.datasketches.kll.KllDirectDoublesSketch.KllDirectCompactDoublesSketch;
-import org.apache.datasketches.kll.KllSketch.SketchType;
import org.apache.datasketches.memory.DefaultMemoryRequestServer;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.MemoryRequestServer;
@@ -42,9 +41,7 @@ import org.testng.annotations.Test;
/**
* @author Lee Rhodes
*/
-@SuppressWarnings("unused")
public class KllMiscDoublesTest {
- static final String LS = System.getProperty("line.separator");
private final MemoryRequestServer memReqSvr = new DefaultMemoryRequestServer();
@Test
@@ -155,7 +152,7 @@ public class KllMiscDoublesTest {
final KllDoublesSketch sk2 = KllDoublesSketch.newHeapInstance(20);
n = 400;
for (int i = 101; i <= n + 100; i++) { sk2.update(i); }
- println("\n" + sk2.toString(true, true));
+ println(LS + sk2.toString(true, true));
assertEquals(sk2.getNumLevels(), 5);
assertEquals(sk2.getMinItem(), 101);
assertEquals(sk2.getMaxItem(), 500);
@@ -228,15 +225,16 @@ public class KllMiscDoublesTest {
DoublesSortedView sv = sk.getSortedView();
DoublesSortedViewIterator itr = sv.iterator();
println("### SORTED VIEW");
- printf("%12s%12s\n", "Value", "Weight");
- long[] correct = {2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
+ printf("%6s %12s %12s" + LS, "Idx", "Value", "CumWeight");
int i = 0;
while (itr.next()) {
double v = itr.getQuantile();
long wt = itr.getWeight();
- printf("%12.1f%12d\n", v, wt);
- assertEquals(wt, correct[i++]);
+ printf("%6d %12.1f %12d" + LS, i, v, wt);
+ i++;
}
+ assertEquals(sv.getMinItem(), 1.0);
+ assertEquals(sv.getMaxItem(), n * 1.0);
}
@Test //set static enablePrinting = true for visual checking
@@ -272,7 +270,7 @@ public class KllMiscDoublesTest {
DoublesSortedViewIterator itr = sk.getSortedView().iterator();
println("### SORTED VIEW");
- printf("%12s %12s %12s\n", "Value", "Weight", "NaturalRank");
+ printf("%12s %12s %12s" + LS, "Value", "Weight", "NaturalRank");
long cumWt = 0;
while (itr.next()) {
double v = itr.getQuantile();
@@ -280,7 +278,7 @@ public class KllMiscDoublesTest {
long natRank = itr.getNaturalRank(INCLUSIVE);
cumWt += wt;
assertEquals(cumWt, natRank);
- printf("%12.1f %12d %12d\n", v, wt, natRank);
+ printf("%12.1f %12d %12d" + LS, v, wt, natRank);
}
assertEquals(cumWt, sk.getN());
}
@@ -297,8 +295,8 @@ public class KllMiscDoublesTest {
private static void outputItems(double[] itemsArr) {
String[] hdr2 = {"Index", "Value"};
- String hdr2fmt = "%6s %15s\n";
- String d2fmt = "%6d %15f\n";
+ String hdr2fmt = "%6s %15s" + LS;
+ String d2fmt = "%6d %15f" + LS;
println("ItemsArr");
printf(hdr2fmt, (Object[]) hdr2);
for (int i = 0; i < itemsArr.length; i++) {
@@ -321,9 +319,9 @@ public class KllMiscDoublesTest {
private static void outputLevels(int weight, int[] levelsArr) {
String[] hdr = {"Lvl", "StartAdr", "BitPattern", "Weight"};
- String hdrfmt = "%3s %9s %10s %s\n";
- String dfmt = "%3d %9d %10d %d\n";
- String dfmt_2 = "%3d %9d %s\n";
+ String hdrfmt = "%3s %9s %10s %s" + LS;
+ String dfmt = "%3d %9d %10d %d" + LS;
+ String dfmt_2 = "%3d %9d %s" + LS;
println("Count = " + weight + " => " + (Integer.toBinaryString(weight)));
println("LevelsArr");
printf(hdrfmt, (Object[]) hdr);
@@ -355,8 +353,8 @@ public class KllMiscDoublesTest {
@Test //set static enablePrinting = true for visual checking
public void checkIntCapAux() {
String[] hdr = {"level", "depth", "wt", "cap", "(end)", "MaxN"};
- String hdrFmt = "%6s %6s %28s %10s %10s %34s\n";
- String dataFmt = "%6d %6d %,28d %,10d %,10d %,34.0f\n";
+ String hdrFmt = "%6s %6s %28s %10s %10s %34s" + LS;
+ String dataFmt = "%6d %6d %,28d %,10d %,10d %,34.0f" + LS;
int k = 1000;
int m = 8;
int numLevels = 20;
@@ -378,8 +376,8 @@ public class KllMiscDoublesTest {
@Test //set static enablePrinting = true for visual checking
public void checkIntCapAuxAux() {
String[] hdr = {"d","twoK","2k*2^d","3^d","tmp=2k*2^d/3^d","(tmp + 1)/2", "(end)"};
- String hdrFmt = "%6s %10s %20s %20s %15s %12s %10s\n";
- String dataFmt = "%6d %10d %,20d %,20d %15d %12d %10d\n";
+ String hdrFmt = "%6s %10s %20s %20s %15s %12s %10s" + LS;
+ String dataFmt = "%6d %10d %,20d %,20d %15d %12d %10d" + LS;
long k = (1L << 16) - 1L;
long m = 8;
println("k = " + k + ", m = " + m);
@@ -770,7 +768,7 @@ public class KllMiscDoublesTest {
public void printlnTest() {
String s = "PRINTING: printf in " + this.getClass().getName();
println(s);
- printf("%s\n", s);
+ printf("%s" + LS, s);
}
private final static boolean enablePrinting = false;
diff --git a/src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java
index e7ba7d19..820f9ff7 100644
--- a/src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java
@@ -19,8 +19,8 @@
package org.apache.datasketches.kll;
+import static org.apache.datasketches.common.Util.LS;
import static org.apache.datasketches.common.Util.bitAt;
-import static org.apache.datasketches.kll.KllHelper.getGrowthSchemeForGivenN;
import static org.apache.datasketches.kll.KllSketch.SketchType.FLOATS_SKETCH;
import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INCLUSIVE;
import static org.testng.Assert.assertEquals;
@@ -30,7 +30,6 @@ import static org.testng.Assert.fail;
import org.apache.datasketches.common.SketchesArgumentException;
import org.apache.datasketches.kll.KllDirectFloatsSketch.KllDirectCompactFloatsSketch;
-import org.apache.datasketches.kll.KllSketch.SketchType;
import org.apache.datasketches.memory.DefaultMemoryRequestServer;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.MemoryRequestServer;
@@ -42,9 +41,7 @@ import org.testng.annotations.Test;
/**
* @author Lee Rhodes
*/
-@SuppressWarnings("unused")
public class KllMiscFloatsTest {
- static final String LS = System.getProperty("line.separator");
private final MemoryRequestServer memReqSvr = new DefaultMemoryRequestServer();
@Test
@@ -155,7 +152,7 @@ public class KllMiscFloatsTest {
final KllFloatsSketch sk2 = KllFloatsSketch.newHeapInstance(20);
n = 400;
for (int i = 101; i <= n + 100; i++) { sk2.update(i); }
- println("\n" + sk2.toString(true, true));
+ println(LS + sk2.toString(true, true));
assertEquals(sk2.getNumLevels(), 5);
assertEquals(sk2.getMinItem(), 101);
assertEquals(sk2.getMaxItem(), 500);
@@ -228,15 +225,16 @@ public class KllMiscFloatsTest {
FloatsSortedView sv = sk.getSortedView();
FloatsSortedViewIterator itr = sv.iterator();
println("### SORTED VIEW");
- printf("%12s%12s\n", "Value", "Weight");
- long[] correct = {2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
+ printf("%6s %12s %12s" + LS, "Idx", "Value", "Weight");
int i = 0;
while (itr.next()) {
float v = itr.getQuantile();
long wt = itr.getWeight();
- printf("%12.1f%12d\n", v, wt);
- assertEquals(wt, correct[i++]);
+ printf("%6d %12.1f %12d" + LS, i, v, wt);
+ i++;
}
+ assertEquals(sv.getMinItem(), 1.0F);
+ assertEquals(sv.getMaxItem(), n * 1.0F);
}
@Test //set static enablePrinting = true for visual checking
@@ -272,7 +270,7 @@ public class KllMiscFloatsTest {
FloatsSortedViewIterator itr = sk.getSortedView().iterator();
println("### SORTED VIEW");
- printf("%12s %12s %12s\n", "Value", "Weight", "NaturalRank");
+ printf("%12s %12s %12s" + LS, "Value", "Weight", "NaturalRank");
long cumWt = 0;
while (itr.next()) {
double v = itr.getQuantile();
@@ -280,7 +278,7 @@ public class KllMiscFloatsTest {
long natRank = itr.getNaturalRank(INCLUSIVE);
cumWt += wt;
assertEquals(cumWt, natRank);
- printf("%12.1f %12d %12d\n", v, wt, natRank);
+ printf("%12.1f %12d %12d" + LS, v, wt, natRank);
}
assertEquals(cumWt, sk.getN());
}
@@ -297,8 +295,8 @@ public class KllMiscFloatsTest {
private static void outputItems(float[] itemsArr) {
String[] hdr2 = {"Index", "Value"};
- String hdr2fmt = "%6s %15s\n";
- String d2fmt = "%6d %15f\n";
+ String hdr2fmt = "%6s %15s" + LS;
+ String d2fmt = "%6d %15f" + LS;
println("ItemsArr");
printf(hdr2fmt, (Object[]) hdr2);
for (int i = 0; i < itemsArr.length; i++) {
@@ -321,9 +319,9 @@ public class KllMiscFloatsTest {
private static void outputLevels(int weight, int[] levelsArr) {
String[] hdr = {"Lvl", "StartAdr", "BitPattern", "Weight"};
- String hdrfmt = "%3s %9s %10s %s\n";
- String dfmt = "%3d %9d %10d %d\n";
- String dfmt_2 = "%3d %9d %s\n";
+ String hdrfmt = "%3s %9s %10s %s" + LS;
+ String dfmt = "%3d %9d %10d %d" + LS;
+ String dfmt_2 = "%3d %9d %s" + LS;
println("Count = " + weight + " => " + (Integer.toBinaryString(weight)));
println("LevelsArr");
printf(hdrfmt, (Object[]) hdr);
@@ -355,8 +353,8 @@ public class KllMiscFloatsTest {
@Test //set static enablePrinting = true for visual checking
public void checkIntCapAux() {
String[] hdr = {"level", "depth", "wt", "cap", "(end)", "MaxN"};
- String hdrFmt = "%6s %6s %28s %10s %10s %34s\n";
- String dataFmt = "%6d %6d %,28d %,10d %,10d %,34.0f\n";
+ String hdrFmt = "%6s %6s %28s %10s %10s %34s" + LS;
+ String dataFmt = "%6d %6d %,28d %,10d %,10d %,34.0f" + LS;
int k = 1000;
int m = 8;
int numLevels = 20;
@@ -378,8 +376,8 @@ public class KllMiscFloatsTest {
@Test //set static enablePrinting = true for visual checking
public void checkIntCapAuxAux() {
String[] hdr = {"d","twoK","2k*2^d","3^d","tmp=2k*2^d/3^d","(tmp + 1)/2", "(end)"};
- String hdrFmt = "%6s %10s %20s %20s %15s %12s %10s\n";
- String dataFmt = "%6d %10d %,20d %,20d %15d %12d %10d\n";
+ String hdrFmt = "%6s %10s %20s %20s %15s %12s %10s" + LS;
+ String dataFmt = "%6d %10d %,20d %,20d %15d %12d %10d" + LS;
long k = (1L << 16) - 1L;
long m = 8;
println("k = " + k + ", m = " + m);
@@ -770,7 +768,7 @@ public class KllMiscFloatsTest {
public void printlnTest() {
String s = "PRINTING: printf in " + this.getClass().getName();
println(s);
- printf("%s\n", s);
+ printf("%s" + LS, s);
}
private final static boolean enablePrinting = false;
diff --git a/src/test/java/org/apache/datasketches/kll/KllMiscItemsTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscItemsTest.java
index cfb17e48..f211abb3 100644
--- a/src/test/java/org/apache/datasketches/kll/KllMiscItemsTest.java
+++ b/src/test/java/org/apache/datasketches/kll/KllMiscItemsTest.java
@@ -19,8 +19,8 @@
package org.apache.datasketches.kll;
+import static org.apache.datasketches.common.Util.LS;
import static org.apache.datasketches.common.Util.bitAt;
-import static org.apache.datasketches.kll.KllHelper.getGrowthSchemeForGivenN;
import static org.apache.datasketches.kll.KllSketch.SketchType.ITEMS_SKETCH;
import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INCLUSIVE;
import static org.testng.Assert.assertEquals;
@@ -34,22 +34,17 @@ import org.apache.datasketches.common.ArrayOfBooleansSerDe;
import org.apache.datasketches.common.ArrayOfStringsSerDe;
import org.apache.datasketches.common.SketchesArgumentException;
import org.apache.datasketches.common.Util;
-import org.apache.datasketches.kll.KllSketch.SketchType;
-import org.apache.datasketches.quantilescommon.GenericSortedViewIterator;
-import org.apache.datasketches.quantilescommon.ItemsSketchSortedView;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
-import org.apache.datasketches.quantilescommon.DoublesSortedViewIterator;
-import org.apache.datasketches.quantilescommon.GenericSortedView;
import org.apache.datasketches.quantilescommon.GenericSortedViewIterator;
+import org.apache.datasketches.quantilescommon.ItemsSketchSortedView;
import org.testng.annotations.Test;
/**
* @author Lee Rhodes
*/
-@SuppressWarnings("unused")
+//@SuppressWarnings("unused")
public class KllMiscItemsTest {
- static final String LS = System.getProperty("line.separator");
public ArrayOfStringsSerDe serDe = new ArrayOfStringsSerDe();
@Test
@@ -221,15 +216,16 @@ public class KllMiscItemsTest {
ItemsSketchSortedView<String> sv = sk.getSortedView();
GenericSortedViewIterator<String> itr = sv.iterator();
println("### SORTED VIEW");
- printf("%12s%12s\n", "Value", "CumWeight");
- long[] correct = {2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1};
+ printf("%6s %12s %12s" + LS, "Idx", "Value", "CumWeight");
int i = 0;
while (itr.next()) {
String v = itr.getQuantile();
long wt = itr.getWeight();
- printf("%12s%12d\n", v, wt);
- assertEquals(wt, correct[i++]);
+ printf("%6d %12s %12d" + LS,i, v, wt);
+ i++;
}
+ assertEquals(sv.getMinItem(), " 1");
+ assertEquals(sv.getMaxItem(), Integer.toString(n));
}
@Test //set static enablePrinting = true for visual checking
@@ -266,7 +262,7 @@ public class KllMiscItemsTest {
GenericSortedViewIterator<String> itr = sk.getSortedView().iterator();
println("### SORTED VIEW");
- printf("%12s %12s %12s\n", "Value", "Weight", "NaturalRank");
+ printf("%12s %12s %12s" + LS, "Value", "Weight", "NaturalRank");
long cumWt = 0;
while (itr.next()) {
String v = itr.getQuantile();
@@ -274,7 +270,7 @@ public class KllMiscItemsTest {
long natRank = itr.getNaturalRank(INCLUSIVE);
cumWt += wt;
assertEquals(cumWt, natRank);
- printf("%12s %12d %12d\n", v, wt, natRank);
+ printf("%12s %12d %12d" + LS, v, wt, natRank);
}
assertEquals(cumWt, sk.getN());
}
@@ -496,8 +492,8 @@ public class KllMiscItemsTest {
private static void outputItems(String[] itemsArr) {
String[] hdr2 = {"Index", "Value"};
- String hdr2fmt = "%6s %15s\n";
- String d2fmt = "%6d %15s\n";
+ String hdr2fmt = "%6s %15s" + LS;
+ String d2fmt = "%6d %15s" + LS;
println("ItemsArr");
printf(hdr2fmt, (Object[]) hdr2);
for (int i = 0; i < itemsArr.length; i++) {
@@ -520,9 +516,9 @@ public class KllMiscItemsTest {
private static void outputLevels(int weight, int[] levelsArr) {
String[] hdr = {"Lvl", "StartAdr", "BitPattern", "Weight"};
- String hdrfmt = "%3s %9s %10s %s\n";
- String dfmt = "%3d %9d %10d %d\n";
- String dfmt_2 = "%3d %9d %s\n";
+ String hdrfmt = "%3s %9s %10s %s" + LS;
+ String dfmt = "%3d %9d %10d %d" + LS;
+ String dfmt_2 = "%3d %9d %s" + LS;
println("Count = " + weight + " => " + (Integer.toBinaryString(weight)));
println("LevelsArr");
printf(hdrfmt, (Object[]) hdr);
@@ -557,8 +553,9 @@ public class KllMiscItemsTest {
@Test
public void checkIssue484() {
+ final int k = 20;
Boolean[] items = { true,false,true,false,true,false,true,false,true,false };
- KllItemsSketch<Boolean> sketch = KllItemsSketch.newHeapInstance(Boolean::compareTo, new ArrayOfBooleansSerDe());
+ KllItemsSketch<Boolean> sketch = KllItemsSketch.newHeapInstance(k, Boolean::compareTo, new ArrayOfBooleansSerDe());
for (int i = 0; i < items.length; i++) { sketch.update(items[i]); }
byte[] serialized = sketch.toByteArray();
KllItemsSketch<Boolean> deserialized =
@@ -574,12 +571,14 @@ public class KllMiscItemsTest {
Boolean[] expItemsArr = (Boolean[])expSV.getQuantiles();
long[] actCumWts = actSV.getCumulativeWeights();
Boolean[] actItemsArr = (Boolean[])actSV.getQuantiles();
- printf("%3s %8s %8s\n", "i","Actual", "Expected");
+ printf("%3s %8s %8s" + LS, "i","Actual", "Expected");
for (int i = 0; i < N; i++) {
- printf("%3d %8s %8s\n", i, actItemsArr[i].toString(), expItemsArr[i].toString());
+ printf("%3d %8s %8s" + LS, i, actItemsArr[i].toString(), expItemsArr[i].toString());
}
assertEquals(actCumWts, expCumWts);
assertEquals(actItemsArr, expItemsArr);
+ assertEquals(actual.getMinItem(), expected.getMinItem());
+ assertEquals(actual.getMaxItem(), expected.getMaxItem());
}
private final static boolean enablePrinting = false;
diff --git a/src/test/java/org/apache/datasketches/quantilescommon/IncludeMinMaxTest.java b/src/test/java/org/apache/datasketches/quantilescommon/IncludeMinMaxTest.java
new file mode 100644
index 00000000..50957fd6
--- /dev/null
+++ b/src/test/java/org/apache/datasketches/quantilescommon/IncludeMinMaxTest.java
@@ -0,0 +1,199 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+package org.apache.datasketches.quantilescommon;
+
+import static org.apache.datasketches.common.Util.LS;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.DoublesPair;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.FloatsPair;
+import static org.apache.datasketches.quantilescommon.IncludeMinMax.ItemsPair;
+import static org.testng.Assert.assertEquals;
+
+import java.util.Comparator;
+
+import org.testng.annotations.Test;
+
+/**
+ * Checks the IncludeMinMax process
+ */
+public final class IncludeMinMaxTest {
+
+ @Test
+ public static void checkDoublesEndsAdjustment() {
+ final double[] quantiles = {2, 4, 6, 7};
+ final long[] cumWeights = {2, 4, 6, 8};
+
+ final double maxItem = 8;
+ final double minItem = 1;
+ final DoublesPair dPair = IncludeMinMax.includeDoublesMinMax(quantiles, cumWeights, maxItem, minItem);
+ final double[] adjQuantiles = dPair.quantiles;
+ final long[] adjCumWeights = dPair.cumWeights;
+ int len = adjCumWeights.length;
+ printf("%10s %10s" + LS, "Quantiles", "CumWeights");
+ for (int i = 0; i < len; i++) {
+ printf("%10.1f %10d" + LS, adjQuantiles[i], adjCumWeights[i]);
+ }
+ final int topIn = quantiles.length - 1;
+ final int topAdj = adjQuantiles.length - 1;
+ assertEquals(adjQuantiles[topAdj], maxItem);
+ assertEquals(adjQuantiles[0], minItem);
+ assertEquals(adjCumWeights[topAdj], cumWeights[topIn]);
+ assertEquals(adjCumWeights[0], 1);
+ }
+
+ @Test
+ public static void checkDoublesEndsAdjustment2() {
+ final double[] quantiles = {2, 4, 6, 7};
+ final long[] cumWeights = {2, 4, 6, 8};
+
+ final double maxItem = 7;
+ final double minItem = 2;
+ final DoublesPair dPair = IncludeMinMax.includeDoublesMinMax(quantiles, cumWeights, maxItem, minItem);
+ final double[] adjQuantiles = dPair.quantiles;
+ final long[] adjCumWeights = dPair.cumWeights;
+ int len = adjCumWeights.length;
+ printf("%10s %10s" + LS, "Quantiles", "CumWeights");
+ for (int i = 0; i < len; i++) {
+ printf("%10.1f %10d" + LS, adjQuantiles[i], adjCumWeights[i]);
+ }
+ final int topIn = quantiles.length - 1;
+ final int topAdj = adjQuantiles.length - 1;
+ assertEquals(adjQuantiles[topAdj], maxItem);
+ assertEquals(adjQuantiles[0], minItem);
+ assertEquals(adjCumWeights[topAdj], cumWeights[topIn]);
+ assertEquals(adjCumWeights[0], cumWeights[0]);
+ }
+
+ @Test
+ public static void checkFloatsEndsAdjustment() {
+ final float[] quantiles = {2, 4, 6, 7};
+ final long[] cumWeights = {2, 4, 6, 8};
+
+ final float maxItem = 8;
+ final float minItem = 1;
+ final FloatsPair dPair = IncludeMinMax.includeFloatsMinMax(quantiles, cumWeights, maxItem, minItem);
+ final float[] adjQuantiles = dPair.quantiles;
+ final long[] adjCumWeights = dPair.cumWeights;
+ int len = adjCumWeights.length;
+ printf("%10s %10s" + LS, "Quantiles", "CumWeights");
+ for (int i = 0; i < len; i++) {
+ printf("%10.1f %10d" + LS, adjQuantiles[i], adjCumWeights[i]);
+ }
+ final int topIn = quantiles.length - 1;
+ final int topAdj = adjQuantiles.length - 1;
+ assertEquals(adjQuantiles[topAdj], maxItem);
+ assertEquals(adjQuantiles[0], minItem);
+ assertEquals(adjCumWeights[topAdj], cumWeights[topIn]);
+ assertEquals(adjCumWeights[0], 1);
+ }
+
+ @Test
+ public static void checkFloatsEndsAdjustment2() {
+ final float[] quantiles = {2, 4, 6, 7};
+ final long[] cumWeights = {2, 4, 6, 8};
+
+ final float maxItem = 7;
+ final float minItem = 2;
+ final FloatsPair dPair = IncludeMinMax.includeFloatsMinMax(quantiles, cumWeights, maxItem, minItem);
+ final float[] adjQuantiles = dPair.quantiles;
+ final long[] adjCumWeights = dPair.cumWeights;
+ int len = adjCumWeights.length;
+ printf("%10s %10s" + LS, "Quantiles", "CumWeights");
+ for (int i = 0; i < len; i++) {
+ printf("%10.1f %10d" + LS, adjQuantiles[i], adjCumWeights[i]);
+ }
+ final int topIn = quantiles.length - 1;
+ final int topAdj = adjQuantiles.length - 1;
+ assertEquals(adjQuantiles[topAdj], maxItem);
+ assertEquals(adjQuantiles[0], minItem);
+ assertEquals(adjCumWeights[topAdj], cumWeights[topIn]);
+ assertEquals(adjCumWeights[0], cumWeights[0]);
+ }
+
+ @Test
+ public static void checkItemsEndsAdjustment() {
+ final String[] quantiles = {"2", "4", "6", "7"};
+ final long[] cumWeights = {2, 4, 6, 8};
+
+ final String maxItem = "8";
+ final String minItem = "1";
+ final ItemsPair<String> dPair =
+ IncludeMinMax.includeItemsMinMax(quantiles, cumWeights, maxItem, minItem, Comparator.naturalOrder());
+ final String[] adjQuantiles = dPair.quantiles;
+ final long[] adjCumWeights = dPair.cumWeights;
+ int len = adjCumWeights.length;
+ printf("%10s %10s" + LS, "Quantiles", "CumWeights");
+ for (int i = 0; i < len; i++) {
+ printf("%10s %10d" + LS, adjQuantiles[i], adjCumWeights[i]);
+ }
+ final int topIn = quantiles.length - 1;
+ final int topAdj = adjQuantiles.length - 1;
+ assertEquals(adjQuantiles[topAdj], maxItem);
+ assertEquals(adjQuantiles[0], minItem);
+ assertEquals(adjCumWeights[topAdj], cumWeights[topIn]);
+ assertEquals(adjCumWeights[0], 1);
+ }
+
+ @Test
+ public static void checkItemsEndsAdjustment2() {
+ final String[] quantiles = {"2", "4", "6", "7"};
+ final long[] cumWeights = {2, 4, 6, 8};
+
+ final String maxItem = "7";
+ final String minItem = "2";
+ final ItemsPair<String> dPair =
+ IncludeMinMax.includeItemsMinMax(quantiles, cumWeights, maxItem, minItem, Comparator.naturalOrder());
+ final String[] adjQuantiles = dPair.quantiles;
+ final long[] adjCumWeights = dPair.cumWeights;
+ int len = adjCumWeights.length;
+ printf("%10s %10s" + LS, "Quantiles", "CumWeights");
+ for (int i = 0; i < len; i++) {
+ printf("%10s %10d" + LS, adjQuantiles[i], adjCumWeights[i]);
+ }
+ final int topIn = quantiles.length - 1;
+ final int topAdj = adjQuantiles.length - 1;
+ assertEquals(adjQuantiles[topAdj], maxItem);
+ assertEquals(adjQuantiles[0], minItem);
+ assertEquals(adjCumWeights[topAdj], cumWeights[topIn]);
+ assertEquals(adjCumWeights[0], cumWeights[0]);
+ }
+
+ @Test
+ public void printlnTest() {
+ println("PRINTING: " + this.getClass().getName());
+ }
+
+ private final static boolean enablePrinting = false;
+
+ /**
+ * @param format the format
+ * @param args the args
+ */
+ static final void printf(final String format, final Object ...args) {
+ if (enablePrinting) { System.out.printf(format, args); }
+ }
+
+ /**
+ * @param o the Object to println
+ */
+ static final void println(final Object o) {
+ if (enablePrinting) { System.out.println(o.toString()); }
+ }
+
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org