Merge pull request #407 from apache/minor_changes_to_REQ
Added SortedView to REQ, Renamed variables for clarity. JavaDoc updates.
diff --git a/README.md b/README.md
index 10630e9..1fc3e72 100644
--- a/README.md
+++ b/README.md
@@ -149,6 +149,5 @@
* Select button: *opens*
* Hit *OK*
-
**NOTE:** If you execute *Maven/Update Project...* from Eclipse with the option *Update project configuration from pom.xml* checked, all of the above will be erased, and you will have to redo it.
diff --git a/pom.xml b/pom.xml
index 909d4af..c626f47 100644
--- a/pom.xml
+++ b/pom.xml
@@ -397,9 +397,9 @@
</plugins>
</build>
<profiles>
- <!-- Ignore nuisance warning from Apache parent plugin:
+ <!-- Ignore nuisance warning from Apache parent plugin:
"maven-remote-resources-plugin (goal "process") is ignored by m2e".
- This profile is only active when the property "m2e.version" is set,
+ This profile is only active when the property "m2e.version" is set,
which is the case when building in Eclipse with m2e.
-->
<profile>
@@ -467,8 +467,8 @@
</build>
</profile>
- <!-- This profile is used to release signed jars to the Apache Nexus repository.
- This must be executed from a git repository set at the proper Release branch (e.g., 1.1.X)
+ <!-- This profile is used to release signed jars to the Apache Nexus repository.
+ This must be executed from a git repository set at the proper Release branch (e.g., 1.1.X)
and at a Release Candidate tag (e.g., 1.1.0-RC1).
The pom version in the release branch must be properly set to something like: "1.1.0".
The pom version in the master would be set to something like: "1.2.0-SNAPSHOT".
@@ -611,7 +611,7 @@
</plugins>
</build>
</profile>
- <!-- Disable source release assembly for 'apache-release' profile.
+ <!-- Disable source release assembly for 'apache-release' profile.
This is performed from a script outside Maven
-->
<profile>
@@ -662,6 +662,9 @@
<activation>
<jdk>[11,14)</jdk>
</activation>
+ <properties>
+ <maven.compiler.release>8</maven.compiler.release>
+ </properties>
<build>
<pluginManagement>
<plugins>
diff --git a/src/main/java/org/apache/datasketches/InequalitySearch.java b/src/main/java/org/apache/datasketches/InequalitySearch.java
index bb2c3c2..278a338 100644
--- a/src/main/java/org/apache/datasketches/InequalitySearch.java
+++ b/src/main/java/org/apache/datasketches/InequalitySearch.java
@@ -85,12 +85,11 @@
@Override
int resolve(final int lo, final int hi, final int low, final int high) {
- if (lo >= high) { return high; }
- return -1;
+ return (lo >= high) ? high : -1;
}
@Override
- String desc(final double[] arr, final int low, final int high, final double v, final int idx) {
+ public String desc(final double[] arr, final int low, final int high, final double v, final int idx) {
if (idx == -1) {
return "LT: " + v + " <= arr[" + low + "]=" + arr[low] + "; return -1";
}
@@ -104,7 +103,7 @@
}
@Override
- String desc(final float[] arr, final int low, final int high, final float v, final int idx) {
+ public String desc(final float[] arr, final int low, final int high, final float v, final int idx) {
if (idx == -1) {
return "LT: " + v + " <= arr[" + low + "]=" + arr[low] + "; return -1";
}
@@ -118,7 +117,7 @@
}
@Override
- String desc(final long[] arr, final int low, final int high, final long v, final int idx) {
+ public String desc(final long[] arr, final int low, final int high, final long v, final int idx) {
if (idx == -1) {
return "LT: " + v + " <= arr[" + low + "]=" + arr[low] + "; return -1";
}
@@ -176,12 +175,11 @@
@Override
int resolve(final int lo, final int hi, final int low, final int high) {
- if (lo >= high) { return high; }
- return -1;
+ return (lo >= high) ? high : -1;
}
@Override
- String desc(final double[] arr, final int low, final int high, final double v, final int idx) {
+ public String desc(final double[] arr, final int low, final int high, final double v, final int idx) {
if (idx == -1) {
return "LE: " + v + " < arr[" + low + "]=" + arr[low] + "; return -1";
}
@@ -195,7 +193,7 @@
}
@Override
- String desc(final float[] arr, final int low, final int high, final float v, final int idx) {
+ public String desc(final float[] arr, final int low, final int high, final float v, final int idx) {
if (idx == -1) {
return "LE: " + v + " < arr[" + low + "]=" + arr[low] + "; return -1";
}
@@ -209,7 +207,7 @@
}
@Override
- String desc(final long[] arr, final int low, final int high, final long v, final int idx) {
+ public String desc(final long[] arr, final int low, final int high, final long v, final int idx) {
if (idx == -1) {
return "LE: " + v + " < arr[" + low + "]=" + arr[low] + "; return -1";
}
@@ -267,7 +265,7 @@
}
@Override
- String desc(final double[] arr, final int low, final int high, final double v, final int idx) {
+ public String desc(final double[] arr, final int low, final int high, final double v, final int idx) {
if (idx == -1) {
if (v > arr[high]) {
return "EQ: " + v + " > arr[" + high + "]; return -1";
@@ -281,7 +279,7 @@
}
@Override
- String desc(final float[] arr, final int low, final int high, final float v, final int idx) {
+ public String desc(final float[] arr, final int low, final int high, final float v, final int idx) {
if (idx == -1) {
if (v > arr[high]) {
return "EQ: " + v + " > arr[" + high + "]; return -1";
@@ -295,7 +293,7 @@
}
@Override
- String desc(final long[] arr, final int low, final int high, final long v, final int idx) {
+ public String desc(final long[] arr, final int low, final int high, final long v, final int idx) {
if (idx == -1) {
if (v > arr[high]) {
return "EQ: " + v + " > arr[" + high + "]; return -1";
@@ -353,12 +351,11 @@
@Override
int resolve(final int lo, final int hi, final int low, final int high) {
- if (hi <= low) { return low; }
- return -1;
+ return (hi <= low) ? low : -1;
}
@Override
- String desc(final double[] arr, final int low, final int high, final double v, final int idx) {
+ public String desc(final double[] arr, final int low, final int high, final double v, final int idx) {
if (idx == -1) {
return "GE: " + v + " > arr[" + high + "]=" + arr[high] + "; return -1";
}
@@ -372,7 +369,7 @@
}
@Override
- String desc(final float[] arr, final int low, final int high, final float v, final int idx) {
+ public String desc(final float[] arr, final int low, final int high, final float v, final int idx) {
if (idx == -1) {
return "GE: " + v + " > arr[" + high + "]=" + arr[high] + "; return -1";
}
@@ -386,7 +383,7 @@
}
@Override
- String desc(final long[] arr, final int low, final int high, final long v, final int idx) {
+ public String desc(final long[] arr, final int low, final int high, final long v, final int idx) {
if (idx == -1) {
return "GE: " + v + " > arr[" + high + "]=" + arr[high] + "; return -1";
}
@@ -444,12 +441,11 @@
@Override
int resolve(final int lo, final int hi, final int low, final int high) {
- if (hi <= low) { return low; }
- return -1;
+ return (hi <= low) ? low : -1;
}
@Override
- String desc(final double[] arr, final int low, final int high, final double v, final int idx) {
+ public String desc(final double[] arr, final int low, final int high, final double v, final int idx) {
if (idx == -1) {
return "GT: " + v + " >= arr[" + high + "]=" + arr[high] + "; return -1";
}
@@ -463,7 +459,7 @@
}
@Override
- String desc(final float[] arr, final int low, final int high, final float v, final int idx) {
+ public String desc(final float[] arr, final int low, final int high, final float v, final int idx) {
if (idx == -1) {
return "GT: " + v + " >= arr[" + high + "]=" + arr[high] + "; return -1";
}
@@ -477,7 +473,7 @@
}
@Override
- String desc(final long[] arr, final int low, final int high, final long v, final int idx) {
+ public String desc(final long[] arr, final int low, final int high, final long v, final int idx) {
if (idx == -1) {
return "GT: " + v + " >= arr[" + high + "]=" + arr[high] + "; return -1";
}
@@ -580,7 +576,7 @@
* @param idx the resolved index from the search
* @return the descriptive string.
*/
- abstract String desc(double[] arr, int low, int high, double v, int idx);
+ public abstract String desc(double[] arr, int low, int high, double v, int idx);
/**
* Optional call that describes the details of the results of the search.
@@ -592,7 +588,7 @@
* @param idx the resolved index from the search
* @return the descriptive string.
*/
- abstract String desc(float[] arr, int low, int high, float v, int idx);
+ public abstract String desc(float[] arr, int low, int high, float v, int idx);
/**
* Optional call that describes the details of the results of the search.
@@ -604,7 +600,7 @@
* @param idx the resolved index from the search
* @return the descriptive string.
*/
- abstract String desc(long[] arr, int low, int high, long v, int idx);
+ public abstract String desc(long[] arr, int low, int high, long v, int idx);
/**
* Binary Search for the index of the double value in the given search range that satisfies
diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java
index 6577447..e1ca4a2 100644
--- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java
@@ -21,11 +21,25 @@
import java.util.Arrays;
-import org.apache.datasketches.QuantilesHelper;
import org.apache.datasketches.SketchesStateException;
/**
- * Data structure for answering quantile queries based on the samples from KllSketch
+ * The Sorted View provides a view of the data retained by the sketch that would be cumbersome to get any other way.
+ * One can iterate of the contents of the sketch, but the result is not sorted.
+ * Trying to use getQuantiles would be very cumbersome since one doesn't know what ranks to use to supply the
+ * getQuantiles method. Even worse, suppose it is a large sketch that has retained 1000 values from a stream of
+ * millions (or billions). One would have to execute the getQuantiles method many thousands of times, and using
+ * trial & error, try to figure out what the sketch actually has retained.
+ *
+ * <p>The data from a Sorted view is an unbiased sample of the input stream that can be used for other kinds of
+ * analysis not directly provided by the sketch. A good example comparing two sketches using the Kolmogorov-Smirnov
+ * test. One needs this sorted view for the test.</p>
+ *
+ * <p>This sorted view can also be used for multiple getRank and getQuantile queries once it has been created.
+ * Because it takes some computational work to create this sorted view, it doesn't make sense to create this sorted view
+ * just for single getRank queries. For the first getQuantile queries, it must be created. But for all queries
+ * after the first, assuming the sketch has not been updated, the getQuantile and getRank queries are very fast.</p>
+ *
* @author Kevin Lang
* @author Alexander Saydakov
*/
@@ -38,6 +52,7 @@
private int numLevels_;
// assumes that all levels are sorted including level 0
+ @SuppressWarnings("deprecation")
KllDoublesSketchSortedView(final double[] items, final int[] levels, final int numLevels,
final long n, final boolean cumulative, final boolean inclusive) {
n_ = n;
@@ -48,7 +63,7 @@
populateFromSketch(items, levels, numLevels, numItems);
blockyTandemMergeSort(items_, weights_, levels_, numLevels_);
if (cumulative) {
- QuantilesHelper.convertToPrecedingCumulative(weights_, inclusive);
+ KllQuantilesHelper.convertToPrecedingCumulative(weights_, inclusive);
}
}
@@ -61,11 +76,12 @@
numLevels_ = 0; //not used by test
}
+ @SuppressWarnings("deprecation")
public double getQuantile(final double rank) {
if (weights_[weights_.length - 1] < n_) {
throw new SketchesStateException("getQuantile must be used with cumulative view only");
}
- final long pos = QuantilesHelper.posOfRank(rank, n_);
+ final long pos = KllQuantilesHelper.posOfRank(rank, n_);
return approximatelyAnswerPositonalQuery(pos);
}
@@ -147,10 +163,11 @@
}
}
+ @SuppressWarnings("deprecation")
private double approximatelyAnswerPositonalQuery(final long pos) {
assert pos >= 0;
assert pos < n_;
- final int index = QuantilesHelper.chunkContainingPos(weights_, pos);
+ final int index = KllQuantilesHelper.chunkContainingPos(weights_, pos);
return items_[index];
}
diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
index 8627fcf..e6c2e97 100644
--- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketchSortedView.java
@@ -21,11 +21,25 @@
import java.util.Arrays;
-import org.apache.datasketches.QuantilesHelper;
import org.apache.datasketches.SketchesStateException;
/**
- * Data structure for answering quantile queries based on the samples from KllSketch
+ * The Sorted View provides a view of the data retained by the sketch that would be cumbersome to get any other way.
+ * One can iterate of the contents of the sketch, but the result is not sorted.
+ * Trying to use getQuantiles would be very cumbersome since one doesn't know what ranks to use to supply the
+ * getQuantiles method. Even worse, suppose it is a large sketch that has retained 1000 values from a stream of
+ * millions (or billions). One would have to execute the getQuantiles method many thousands of times, and using
+ * trial & error, try to figure out what the sketch actually has retained.
+ *
+ * <p>The data from a Sorted view is an unbiased sample of the input stream that can be used for other kinds of
+ * analysis not directly provided by the sketch. A good example comparing two sketches using the Kolmogorov-Smirnov
+ * test. One needs this sorted view for the test.</p>
+ *
+ * <p>This sorted view can also be used for multiple getRank and getQuantile queries once it has been created.
+ * Because it takes some computational work to create this sorted view, it doesn't make sense to create this sorted view
+ * just for single getRank queries. For the first getQuantile queries, it must be created. But for all queries
+ * after the first, assuming the sketch has not been updated, the getQuantile and getRank queries are very fast.</p>
+ *
* @author Kevin Lang
* @author Alexander Saydakov
*/
@@ -38,6 +52,7 @@
private int numLevels_;
// assumes that all levels are sorted including level 0
+ @SuppressWarnings("deprecation")
KllFloatsSketchSortedView(final float[] items, final int[] levels, final int numLevels,
final long n, final boolean cumulative, final boolean inclusive) {
n_ = n;
@@ -48,7 +63,7 @@
populateFromSketch(items, levels, numLevels, numItems);
blockyTandemMergeSort(items_, weights_, levels_, numLevels_);
if (cumulative) {
- QuantilesHelper.convertToPrecedingCumulative(weights_, inclusive);
+ KllQuantilesHelper.convertToPrecedingCumulative(weights_, inclusive);
}
}
@@ -61,11 +76,12 @@
numLevels_ = 0; //not used by test
}
+ @SuppressWarnings("deprecation")
public float getQuantile(final double rank) {
if (weights_[weights_.length - 1] < n_) {
throw new SketchesStateException("getQuantile must be used with cumulative view only");
}
- final long pos = QuantilesHelper.posOfRank(rank, n_);
+ final long pos = KllQuantilesHelper.posOfRank(rank, n_);
return approximatelyAnswerPositonalQuery(pos);
}
@@ -147,10 +163,11 @@
}
}
+ @SuppressWarnings("deprecation")
private float approximatelyAnswerPositonalQuery(final long pos) {
assert pos >= 0;
assert pos < n_;
- final int index = QuantilesHelper.chunkContainingPos(weights_, pos);
+ final int index = KllQuantilesHelper.chunkContainingPos(weights_, pos);
return items_[index];
}
diff --git a/src/main/java/org/apache/datasketches/QuantilesHelper.java b/src/main/java/org/apache/datasketches/kll/KllQuantilesHelper.java
similarity index 92%
rename from src/main/java/org/apache/datasketches/QuantilesHelper.java
rename to src/main/java/org/apache/datasketches/kll/KllQuantilesHelper.java
index bbb7c48..d07355b 100644
--- a/src/main/java/org/apache/datasketches/QuantilesHelper.java
+++ b/src/main/java/org/apache/datasketches/kll/KllQuantilesHelper.java
@@ -17,13 +17,15 @@
* under the License.
*/
-package org.apache.datasketches;
+package org.apache.datasketches.kll;
/**
- * Common static methods for classic quantiles and KLL sketches
+ * Common static methods for KLL sketches.
+ * @author lrhodes
+ * @deprecated to be removed before next release.
*/
-public class QuantilesHelper {
-
+@Deprecated
+public class KllQuantilesHelper {
/**
* Convert the weights into totals of the weights preceding each item.
* An array of {1,1,1,0} becomes {0,1,2,3}
@@ -83,7 +85,7 @@
// the following three asserts should probably be retained since they ensure
// that the necessary invariants hold at the beginning of the search
assert l < r;
- assert wtArr[l] <= pos;
+ //assert wtArr[l] <= pos; //TODO inclusive fails with Kevins code
assert pos < wtArr[r];
return searchForChunkContainingPos(wtArr, pos, l, r);
}
@@ -104,7 +106,7 @@
// the following three asserts can probably go away eventually, since it is fairly clear
// that if these invariants hold at the beginning of the search, they will be maintained
assert l < r;
- assert arr[l] <= pos;
+ //assert arr[l] <= pos; //TODO inclusive fails with Kevins code
assert pos < arr[r];
if (l + 1 == r) {
return l;
@@ -117,3 +119,4 @@
}
}
+
diff --git a/src/main/java/org/apache/datasketches/QuantilesHelper.java b/src/main/java/org/apache/datasketches/quantiles/ClassicQuantilesHelper.java
similarity index 92%
copy from src/main/java/org/apache/datasketches/QuantilesHelper.java
copy to src/main/java/org/apache/datasketches/quantiles/ClassicQuantilesHelper.java
index bbb7c48..243a035 100644
--- a/src/main/java/org/apache/datasketches/QuantilesHelper.java
+++ b/src/main/java/org/apache/datasketches/quantiles/ClassicQuantilesHelper.java
@@ -17,12 +17,15 @@
* under the License.
*/
-package org.apache.datasketches;
+package org.apache.datasketches.quantiles;
/**
- * Common static methods for classic quantiles and KLL sketches
+ * Common static methods for Classic Quantiles sketches.
+ * @author lrhodes
+ * @deprecated to be removed before next release.
*/
-public class QuantilesHelper {
+@Deprecated
+public class ClassicQuantilesHelper {
/**
* Convert the weights into totals of the weights preceding each item.
@@ -83,7 +86,7 @@
// the following three asserts should probably be retained since they ensure
// that the necessary invariants hold at the beginning of the search
assert l < r;
- assert wtArr[l] <= pos;
+ //assert wtArr[l] <= pos; //TODO inclusive fails with Kevins code
assert pos < wtArr[r];
return searchForChunkContainingPos(wtArr, pos, l, r);
}
@@ -104,7 +107,7 @@
// the following three asserts can probably go away eventually, since it is fairly clear
// that if these invariants hold at the beginning of the search, they will be maintained
assert l < r;
- assert arr[l] <= pos;
+ //assert arr[l] <= pos; //TODO inclusive fails with Kevins code
assert pos < arr[r];
if (l + 1 == r) {
return l;
@@ -117,3 +120,4 @@
}
}
+
diff --git a/src/main/java/org/apache/datasketches/quantiles/DoublesSketchSortedView.java b/src/main/java/org/apache/datasketches/quantiles/DoublesSketchSortedView.java
index 121b8eb..a8b77ff 100644
--- a/src/main/java/org/apache/datasketches/quantiles/DoublesSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/quantiles/DoublesSketchSortedView.java
@@ -25,10 +25,22 @@
import java.util.Arrays;
-import org.apache.datasketches.QuantilesHelper;
-
/**
- * Auxiliary data structure for answering quantile queries
+ * The Sorted View provides a view of the data retained by the sketch that would be cumbersome to get any other way.
+ * One can iterate of the contents of the sketch, but the result is not sorted.
+ * Trying to use getQuantiles would be very cumbersome since one doesn't know what ranks to use to supply the
+ * getQuantiles method. Even worse, suppose it is a large sketch that has retained 1000 values from a stream of
+ * millions (or billions). One would have to execute the getQuantiles method many thousands of times, and using
+ * trial & error, try to figure out what the sketch actually has retained.
+ *
+ * <p>The data from a Sorted view is an unbiased sample of the input stream that can be used for other kinds of
+ * analysis not directly provided by the sketch. A good example comparing two sketches using the Kolmogorov-Smirnov
+ * test. One needs this sorted view for the test.</p>
+ *
+ * <p>This sorted view can also be used for multiple getRank and getQuantile queries once it has been created.
+ * Because it takes some computational work to create this sorted view, it doesn't make sense to create this sorted view
+ * just for single getRank queries. For the first getQuantile queries, it must be created. But for all queries
+ * after the first, assuming the sketch has not been updated, the getQuantile and getRank queries are very fast.</p>
*
* @author Kevin Lang
* @author Lee Rhodes
@@ -43,6 +55,7 @@
* @param qs a DoublesSketch
* @param inclusive if true, fractional ranks are considered inclusive
*/
+ @SuppressWarnings("deprecation")
DoublesSketchSortedView(final DoublesSketch qs, final boolean cumulative, final boolean inclusive) {
final int k = qs.getK();
final long n = qs.getN();
@@ -62,7 +75,7 @@
blockyTandemMergeSort(itemsArr, cumWtsArr, numSamples, k);
if (cumulative) {
- final long total = QuantilesHelper.convertToPrecedingCumulative(cumWtsArr, inclusive);
+ final long total = ClassicQuantilesHelper.convertToPrecedingCumulative(cumWtsArr, inclusive);
assert total == n;
}
@@ -76,9 +89,10 @@
* @param rank the normalized rank where: 0 ≤ rank ≤ 1.0.
* @return the estimated quantile
*/
+ @SuppressWarnings("deprecation")
public double getQuantile(final double rank) {
checkFractionalRankBounds(rank);
- final long pos = QuantilesHelper.posOfRank(rank, auxN_);
+ final long pos = ClassicQuantilesHelper.posOfRank(rank, auxN_);
return approximatelyAnswerPositionalQuery(pos);
}
@@ -98,10 +112,11 @@
* @param pos position
* @return approximate answer
*/
+ @SuppressWarnings("deprecation")
private double approximatelyAnswerPositionalQuery(final long pos) {
assert 0 <= pos;
assert pos < auxN_;
- final int index = QuantilesHelper.chunkContainingPos(auxCumWtsArr_, pos);
+ final int index = ClassicQuantilesHelper.chunkContainingPos(auxCumWtsArr_, pos);
return auxSamplesArr_[index];
}
diff --git a/src/main/java/org/apache/datasketches/quantiles/ItemsSketchSortedView.java b/src/main/java/org/apache/datasketches/quantiles/ItemsSketchSortedView.java
index 415ee30..701045d 100644
--- a/src/main/java/org/apache/datasketches/quantiles/ItemsSketchSortedView.java
+++ b/src/main/java/org/apache/datasketches/quantiles/ItemsSketchSortedView.java
@@ -24,11 +24,25 @@
import java.util.Arrays;
import java.util.Comparator;
-import org.apache.datasketches.QuantilesHelper;
import org.apache.datasketches.SketchesStateException;
/**
- * Auxiliary data structure for answering generic quantile queries
+ * The Sorted View provides a view of the data retained by the sketch that would be cumbersome to get any other way.
+ * One can iterate of the contents of the sketch, but the result is not sorted.
+ * Trying to use getQuantiles would be very cumbersome since one doesn't know what ranks to use to supply the
+ * getQuantiles method. Even worse, suppose it is a large sketch that has retained 1000 values from a stream of
+ * millions (or billions). One would have to execute the getQuantiles method many thousands of times, and using
+ * trial & error, try to figure out what the sketch actually has retained.
+ *
+ * <p>The data from a Sorted view is an unbiased sample of the input stream that can be used for other kinds of
+ * analysis not directly provided by the sketch. A good example comparing two sketches using the Kolmogorov-Smirnov
+ * test. One needs this sorted view for the test.</p>
+ *
+ * <p>This sorted view can also be used for multiple getRank and getQuantile queries once it has been created.
+ * Because it takes some computational work to create this sorted view, it doesn't make sense to create this sorted view
+ * just for single getRank queries. For the first getQuantile queries, it must be created. But for all queries
+ * after the first, assuming the sketch has not been updated, the getQuantile and getRank queries are very fast.</p>
+ *
* @param <T> type of item
*
* @author Kevin Lang
@@ -72,7 +86,7 @@
cumWtsArr[i] = inclusive ? newSubtot : subtot;
subtot = newSubtot;
}
-
+
assert subtot == n;
}
@@ -86,13 +100,14 @@
* @param rank the normalized rank where: 0 ≤ rank ≤ 1.0.
* @return the estimated quantile
*/
+ @SuppressWarnings("deprecation")
public T getQuantile(final double rank) {
checkFractionalRankBounds(rank);
if (auxN_ <= 0) { return null; }
if (auxCumWtsArr_[auxCumWtsArr_.length - 1] < auxN_) {
throw new SketchesStateException("getQuantile must be used with cumulative view only");
}
- final long pos = QuantilesHelper.posOfRank(rank, auxN_);
+ final long pos = ClassicQuantilesHelper.posOfRank(rank, auxN_);
return approximatelyAnswerPositionalQuery(pos);
}
@@ -108,11 +123,11 @@
* @param pos position
* @return approximate answer
*/
- @SuppressWarnings("unchecked")
+ @SuppressWarnings({ "unchecked", "deprecation" })
private T approximatelyAnswerPositionalQuery(final long pos) {
assert 0 <= pos;
assert pos < auxN_;
- final int index = QuantilesHelper.chunkContainingPos(auxCumWtsArr_, pos);
+ final int index = ClassicQuantilesHelper.chunkContainingPos(auxCumWtsArr_, pos);
return (T) this.auxSamplesArr_[index];
}
diff --git a/src/main/java/org/apache/datasketches/req/BaseReqSketch.java b/src/main/java/org/apache/datasketches/req/BaseReqSketch.java
index db4c2b1..10b5142 100644
--- a/src/main/java/org/apache/datasketches/req/BaseReqSketch.java
+++ b/src/main/java/org/apache/datasketches/req/BaseReqSketch.java
@@ -224,6 +224,12 @@
public abstract int getSerializationBytes();
/**
+ * Gets the sorted view of the current state of this sketch
+ * @return the sorted view of the current state of this sketch
+ */
+ public abstract ReqSketchSortedView getSortedView();
+
+ /**
* Returns true if this sketch is empty.
* @return empty flag
*/
@@ -239,8 +245,10 @@
* Returns the current comparison criterion. If true the value comparison criterion is
* ≤, otherwise it will be the default, which is <.
* @return the current comparison criterion
- * @deprecated
+ * @deprecated in the future the ltEq comparison parameter will not be saved at the class level in preference to
+ * the comparison parameter being specified for each API call. This method will be removed.
*/
+ @Deprecated
public abstract boolean isLessThanOrEqual();
/**
@@ -266,14 +274,15 @@
/**
* Sets the chosen criterion for value comparison
- * @deprecated
- *
* @param ltEq (Less-than-or Equals) If true, the sketch will use the ≤ criterion for comparing
* values. Otherwise, the criterion is strictly <, the default.
* This can be set anytime prior to a <i>getRank(float)</i> or <i>getQuantile(double)</i> or
* equivalent query.
* @return this
+ * @deprecated 4.0.0. In the future the ltEq comparison parameter will not be saved at the class level in preference to
+ * the comparison parameter being specified for each API call. This method will be removed.
*/
+ @Deprecated
public abstract ReqSketch setLessThanOrEqual(final boolean ltEq);
/**
@@ -301,7 +310,7 @@
* items of the compactor and the current nominal capacity of the compactor.
* @param fmt the format string for the data items; example: "%4.0f".
* @param allData all the retained items for the sketch will be output by
- * compactory level. Otherwise, just a summary will be output.
+ * compactor level. Otherwise, just a summary will be output.
* @return a detailed view of the compactors and their data
*/
public abstract String viewCompactorDetail(String fmt, boolean allData);
diff --git a/src/main/java/org/apache/datasketches/req/ReqAuxiliary.java b/src/main/java/org/apache/datasketches/req/ReqAuxiliary.java
deleted file mode 100644
index c329ba4..0000000
--- a/src/main/java/org/apache/datasketches/req/ReqAuxiliary.java
+++ /dev/null
@@ -1,193 +0,0 @@
-/*
- * 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.req;
-
-import java.util.Arrays;
-import java.util.List;
-
-import org.apache.datasketches.InequalitySearch;
-
-/**
- * Supports searches for quantiles
- * @author Lee Rhodes
- */
-class ReqAuxiliary {
- private static final String LS = System.getProperty("line.separator");
- private float[] items;
- private long[] weights;
- private final boolean hra; //used in merge
- private final long N;
-
- ReqAuxiliary(final ReqSketch sk) {
- hra = sk.getHighRankAccuracy();
- N = sk.getN();
- buildAuxTable(sk);
- }
-
- //Testing only! Allows testing of support methods without a sketch.
- ReqAuxiliary(final float[] items, final long[] weights, final boolean hra, final long N) {
- this.hra = hra;
- this.N = N;
- this.items = items;
- this.weights = weights;
- }
-
- private void buildAuxTable(final ReqSketch sk) {
- final List<ReqCompactor> compactors = sk.getCompactors();
- final int numComp = compactors.size();
- final int totalItems = sk.getRetainedItems();
- items = new float[totalItems];
- weights = new long[totalItems];
- int auxCount = 0;
- for (int i = 0; i < numComp; i++) {
- final ReqCompactor c = compactors.get(i);
- final FloatBuffer bufIn = c.getBuffer();
- final long weight = 1 << c.getLgWeight();
- final int bufInLen = bufIn.getCount();
- mergeSortIn(bufIn, weight, auxCount);
- auxCount += bufInLen;
- }
- createCumulativeWeights();
- dedup();
- }
-
- private void createCumulativeWeights() {
- final int len = items.length;
- for (int i = 1; i < len; i++) {
- weights[i] += weights[i - 1];
- }
- assert weights[len - 1] == N;
- }
-
- void dedup() {
- final int itemsLen = items.length;
- final float[] itemsB = new float[itemsLen];
- final long[] wtsB = new long[itemsLen];
- int bidx = 0;
- int i = 0;
- while (i < itemsLen) {
- int j = i + 1;
- int hidup = j;
- while (j < itemsLen && items[i] == items[j]) {
- hidup = j++;
- }
- if (j - i == 1) { //no dups
- itemsB[bidx] = items[i];
- wtsB[bidx++] = weights[i];
- i++;
- continue;
- } else {
- itemsB[bidx] = items[hidup]; //lgtm [java/index-out-of-bounds]
- wtsB[bidx++] = weights[hidup];
- i = j;
- continue;
- }
- }
- items = Arrays.copyOf(itemsB, bidx);
- weights = Arrays.copyOf(wtsB, bidx);
- }
-
- //Specially modified version of FloatBuffer.mergeSortIn(). Here spaceAtBottom is always false and
- // the ultimate array size has already been set. However, this must simultaneously deal with
- // sorting the weights as well. Also used in test.
- void mergeSortIn(final FloatBuffer bufIn, final long weight, final int auxCount) {
- if (!bufIn.isSorted()) { bufIn.sort(); }
- final float[] arrIn = bufIn.getArray(); //may be larger than its item count.
- final int bufInLen = bufIn.getCount();
- final int totLen = auxCount + bufInLen;
- int i = auxCount - 1;
- int j = bufInLen - 1;
- int h = hra ? bufIn.getCapacity() - 1 : bufInLen - 1;
- for (int k = totLen; k-- > 0; ) {
- if (i >= 0 && j >= 0) { //both valid
- if (items[i] >= arrIn[h]) {
- items[k] = items[i];
- weights[k] = weights[i--];
- } else {
- items[k] = arrIn[h--]; j--;
- weights[k] = weight;
- }
- } else if (i >= 0) { //i is valid
- items[k] = items[i];
- weights[k] = weights[i--];
- } else if (j >= 0) { //j is valid
- items[k] = arrIn[h--]; j--;
- weights[k] = weight;
- } else {
- break;
- }
- }
- }
-
- /**
- * Gets the quantile based on the given normalized rank,
- * which must be in the range [0.0, 1.0], inclusive.
- * @param normRank the given normalized rank
- * @param ltEq determines the search method used.
- * @return the quantile based on given normalized rank and ltEq.
- */
- float getQuantile(final double normRank, final boolean ltEq) {
- final int len = weights.length;
- final long rank = (int)(normRank * N);
- //Note that when ltEq=false, GT matches KLL & Quantiles behavior.
- final InequalitySearch crit = ltEq ? InequalitySearch.GE : InequalitySearch.GT;
- final int index = InequalitySearch.find(weights, 0, len - 1, rank, crit);
- if (index == -1) {
- return items[len - 1]; //resolves high end (GE & GT) -1 only!
- }
- return items[index];
- }
-
- //used for testing
-
- Row getRow(final int index) {
- return new Row(items[index], weights[index]);
- }
-
- static class Row {
- float item;
- long weight;
-
- Row(final float item, final long weight) {
- this.item = item;
- this.weight = weight;
- }
- }
-
- String toString(final int precision, final int fieldSize) {
- final StringBuilder sb = new StringBuilder();
- final int p = precision;
- final int z = fieldSize;
- final String ff = "%" + z + "." + p + "f";
- final String sf = "%" + z + "s";
- final String df = "%" + z + "d";
- final String dfmt = ff + df + LS;
- final String sfmt = sf + sf + LS;
- sb.append("Aux Detail").append(LS);
- sb.append(String.format(sfmt, "Item", "Weight"));
- final int totalCount = items.length;
- for (int i = 0; i < totalCount; i++) {
- final Row row = getRow(i);
- sb.append(String.format(dfmt, row.item, row.weight));
- }
- return sb.toString();
- }
-
-}
diff --git a/src/main/java/org/apache/datasketches/req/ReqSketch.java b/src/main/java/org/apache/datasketches/req/ReqSketch.java
index e84ebaf..2232809 100644
--- a/src/main/java/org/apache/datasketches/req/ReqSketch.java
+++ b/src/main/java/org/apache/datasketches/req/ReqSketch.java
@@ -69,6 +69,10 @@
* @author Lee Rhodes
*/
public class ReqSketch extends BaseReqSketch {
+ static class CompactorReturn {
+ int deltaRetItems;
+ int deltaNomSize;
+ }
//static finals
private static final String LS = System.getProperty("line.separator");
static final byte INIT_NUMBER_OF_SECTIONS = 3;
@@ -89,12 +93,28 @@
private int retItems = 0; //number of retained items in the sketch
private int maxNomSize = 0; //sum of nominal capacities of all compactors
//Objects
- private ReqAuxiliary aux = null;
+ private ReqSketchSortedView reqSV = null;
private List<ReqCompactor> compactors = new ArrayList<>();
private ReqDebug reqDebug = null; //user config, default: null, can be set after construction.
+
private final CompactorReturn cReturn = new CompactorReturn(); //used in compress()
/**
+ * Construct from elements. After sketch is constructed, retItems and maxNomSize must be computed.
+ * Used by ReqSerDe.
+ */
+ ReqSketch(final int k, final boolean hra, final long totalN, final float minValue,
+ final float maxValue, final List<ReqCompactor> compactors) {
+ checkK(k);
+ this.k = k;
+ this.hra = hra;
+ this.totalN = totalN;
+ this.minValue = minValue;
+ this.maxValue = maxValue;
+ this.compactors = compactors;
+ }
+
+ /**
* Normal Constructor used by ReqSketchBuilder.
* @param k Controls the size and error of the sketch. It must be even and in the range
* [4, 1024], inclusive.
@@ -129,27 +149,20 @@
maxValue = other.maxValue;
ltEq = other.ltEq;
reqDebug = other.reqDebug;
- //aux does not need to be copied
+ //rssv does not need to be copied
for (int i = 0; i < other.getNumLevels(); i++) {
compactors.add(new ReqCompactor(other.compactors.get(i)));
}
- aux = null;
+ reqSV = null;
}
/**
- * Construct from elements. After sketch is constructed, retItems and maxNomSize must be computed.
- * Used by ReqSerDe.
+ * Returns a new ReqSketchBuilder
+ * @return a new ReqSketchBuilder
*/
- ReqSketch(final int k, final boolean hra, final long totalN, final float minValue,
- final float maxValue, final List<ReqCompactor> compactors) {
- checkK(k);
- this.k = k;
- this.hra = hra;
- this.totalN = totalN;
- this.minValue = minValue;
- this.maxValue = maxValue;
- this.compactors = compactors;
+ public static final ReqSketchBuilder builder() {
+ return new ReqSketchBuilder();
}
/**
@@ -161,39 +174,63 @@
return ReqSerDe.heapify(mem);
}
- /**
- * Returns a new ReqSketchBuilder
- * @return a new ReqSketchBuilder
- */
- public static final ReqSketchBuilder builder() {
- return new ReqSketchBuilder();
+ private static void checkK(final int k) {
+ if ((k & 1) > 0 || k < 4 || k > 1024) {
+ throw new SketchesArgumentException(
+ "<i>K</i> must be even and in the range [4, 1024], inclusive: " + k );
+ }
}
- private void compress() {
- if (reqDebug != null) { reqDebug.emitStartCompress(); }
- for (int h = 0; h < compactors.size(); h++) {
- final ReqCompactor c = compactors.get(h);
- final int compRetItems = c.getBuffer().getCount();
- final int compNomCap = c.getNomCapacity();
-
- if (compRetItems >= compNomCap) {
- if (h + 1 >= getNumLevels()) { //at the top?
- if (reqDebug != null) { reqDebug.emitMustAddCompactor(); }
- grow(); //add a level, increases maxNomSize
- }
- final FloatBuffer promoted = c.compact(cReturn);
- compactors.get(h + 1).getBuffer().mergeSortIn(promoted);
- retItems += cReturn.deltaRetItems;
- maxNomSize += cReturn.deltaNomSize;
- //we specifically decided not to do lazy compression.
+ /**
+ * This checks the given float array to make sure that it contains only finite values
+ * and is monotonically increasing in value.
+ * @param splits the given array
+ */
+ static void validateSplits(final float[] splits) {
+ final int len = splits.length;
+ for (int i = 0; i < len; i++) {
+ final float v = splits[i];
+ if (!Float.isFinite(v)) {
+ throw new SketchesArgumentException("Values must be finite");
+ }
+ if (i < len - 1 && v >= splits[i + 1]) {
+ throw new SketchesArgumentException(
+ "Values must be unique and monotonically increasing");
}
}
- aux = null;
- if (reqDebug != null) { reqDebug.emitCompressDone(); }
}
- ReqAuxiliary getAux() {
- return aux;
+ private static boolean exactRank(final int k, final int levels, final double rank,
+ final boolean hra, final long totalN) {
+ final int baseCap = k * INIT_NUMBER_OF_SECTIONS;
+ if (levels == 1 || totalN <= baseCap) { return true; }
+ final double exactRankThresh = (double)baseCap / totalN;
+ return hra && rank >= 1.0 - exactRankThresh || !hra && rank <= exactRankThresh;
+ }
+
+ private static double getRankLB(final int k, final int levels, final double rank,
+ final int numStdDev, final boolean hra, final long totalN) {
+ if (exactRank(k, levels, rank, hra, totalN)) { return rank; }
+ final double relative = relRseFactor / k * (hra ? 1.0 - rank : rank);
+ final double fixed = fixRseFactor / k;
+ final double lbRel = rank - numStdDev * relative;
+ final double lbFix = rank - numStdDev * fixed;
+ return Math.max(lbRel, lbFix);
+ }
+
+ private static double getRankUB(final int k, final int levels, final double rank,
+ final int numStdDev, final boolean hra, final long totalN) {
+ if (exactRank(k, levels, rank, hra, totalN)) { return rank; }
+ final double relative = relRseFactor / k * (hra ? 1.0 - rank : rank);
+ final double fixed = fixRseFactor / k;
+ final double ubRel = rank + numStdDev * relative;
+ final double ubFix = rank + numStdDev * fixed;
+ return Math.min(ubRel, ubFix);
+ }
+
+ @Override
+ public double[] getCDF(final float[] splitPoints) {
+ return getCDF(splitPoints, ltEq);
}
@Override
@@ -209,64 +246,10 @@
}
@Override
- public double[] getCDF(final float[] splitPoints) {
- return getCDF(splitPoints, ltEq);
- }
-
- List<ReqCompactor> getCompactors() {
- return compactors;
- }
-
- private long getCount(final float value, final boolean inclusive) {
- if (isEmpty()) { return 0; }
- final int numComp = compactors.size();
- long cumNnr = 0;
- for (int i = 0; i < numComp; i++) { //cycle through compactors
- final ReqCompactor c = compactors.get(i);
- final long wt = 1L << c.getLgWeight();
- final FloatBuffer buf = c.getBuffer();
- cumNnr += buf.getCountWithCriterion(value, inclusive) * wt;
- }
- return cumNnr;
- }
-
- private long[] getCounts(final float[] values, final boolean inclusive) {
- final int numValues = values.length;
- final int numComp = compactors.size();
- final long[] cumNnrArr = new long[numValues];
- if (isEmpty()) { return cumNnrArr; }
- for (int i = 0; i < numComp; i++) { //cycle through compactors
- final ReqCompactor c = compactors.get(i);
- final long wt = 1L << c.getLgWeight();
- final FloatBuffer buf = c.getBuffer();
- for (int j = 0; j < numValues; j++) {
- cumNnrArr[j] += buf.getCountWithCriterion(values[j], inclusive) * wt;
- }
- }
- return cumNnrArr;
- }
-
- /**
- * @deprecated
- * @return ltEq flag
- */
- boolean getLtEq() {
- return ltEq;
- }
-
- @Override
public boolean getHighRankAccuracy() {
return hra;
}
- int getK() {
- return k;
- }
-
- int getMaxNomSize() {
- return maxNomSize;
- }
-
@Override
public float getMaxValue() {
return maxValue;
@@ -282,12 +265,9 @@
return totalN;
}
- /**
- * Gets the number of levels of compactors in the sketch.
- * @return the number of levels of compactors in the sketch.
- */
- int getNumLevels() {
- return compactors.size();
+ @Override
+ public double[] getPMF(final float[] splitPoints) {
+ return getPMF(splitPoints, ltEq);
}
@Override
@@ -304,24 +284,8 @@
}
@Override
- public double[] getPMF(final float[] splitPoints) {
- return getPMF(splitPoints, ltEq);
- }
-
- /**
- * Gets a CDF in raw counts, which can be easily converted into a CDF or PMF.
- * @param splits the splitPoints array
- * @param inclusive if true the weight of a given value is included into its rank
- * @return a CDF in raw counts
- */
- private long[] getPMForCDF(final float[] splits, final boolean inclusive) {
- validateSplits(splits);
- final int numSplits = splits.length;
- final long[] splitCounts = getCounts(splits, inclusive);
- final int numBkts = numSplits + 1;
- final long[] bkts = Arrays.copyOf(splitCounts, numBkts);
- bkts[numBkts - 1] = getN();
- return bkts;
+ public float getQuantile(final double normRank) {
+ return getQuantile(normRank, ltEq);
}
@Override
@@ -331,15 +295,15 @@
throw new SketchesArgumentException(
"Normalized rank must be in the range [0.0, 1.0]: " + normRank);
}
- if (aux == null) {
- aux = new ReqAuxiliary(this);
+ if (reqSV == null) {
+ reqSV = new ReqSketchSortedView(this);
}
- return aux.getQuantile(normRank, inclusive);
+ return reqSV.getQuantile(normRank, inclusive);
}
@Override
- public float getQuantile(final double normRank) {
- return getQuantile(normRank, ltEq);
+ public float[] getQuantiles(final double[] normRanks) {
+ return getQuantiles(normRanks, ltEq);
}
@Override
@@ -354,8 +318,8 @@
}
@Override
- public float[] getQuantiles(final double[] normRanks) {
- return getQuantiles(normRanks, ltEq);
+ public double getRank(final float value) {
+ return getRank(value, ltEq);
}
@Override
@@ -366,20 +330,8 @@
}
@Override
- public double getRank(final float value) {
- return getRank(value, ltEq);
- }
-
- @Override
- public double[] getRanks(final float[] values, final boolean inclusive) {
- if (isEmpty()) { return null; }
- final long[] cumNnrArr = getCounts(values, inclusive);
- final int numValues = values.length;
- final double[] rArr = new double[numValues];
- for (int i = 0; i < numValues; i++) {
- rArr[i] = (double)cumNnrArr[i] / totalN;
- }
- return rArr;
+ public double getRankLowerBound(final double rank, final int numStdDev) {
+ return getRankLB(k, getNumLevels(), rank, numStdDev, hra, getN());
}
@Override
@@ -387,37 +339,22 @@
return getRanks(values, ltEq);
}
- private static double getRankLB(final int k, final int levels, final double rank,
- final int numStdDev, final boolean hra, final long totalN) {
- if (exactRank(k, levels, rank, hra, totalN)) { return rank; }
- final double relative = relRseFactor / k * (hra ? 1.0 - rank : rank);
- final double fixed = fixRseFactor / k;
- final double lbRel = rank - numStdDev * relative;
- final double lbFix = rank - numStdDev * fixed;
- return Math.max(lbRel, lbFix);
- }
-
@Override
- public double getRankLowerBound(final double rank, final int numStdDev) {
- return getRankLB(k, getNumLevels(), rank, numStdDev, hra, getN());
- }
-
- private static double getRankUB(final int k, final int levels, final double rank,
- final int numStdDev, final boolean hra, final long totalN) {
- if (exactRank(k, levels, rank, hra, totalN)) { return rank; }
- final double relative = relRseFactor / k * (hra ? 1.0 - rank : rank);
- final double fixed = fixRseFactor / k;
- final double ubRel = rank + numStdDev * relative;
- final double ubFix = rank + numStdDev * fixed;
- return Math.min(ubRel, ubFix);
- }
-
- private static boolean exactRank(final int k, final int levels, final double rank,
- final boolean hra, final long totalN) {
- final int baseCap = k * INIT_NUMBER_OF_SECTIONS;
- if (levels == 1 || totalN <= baseCap) { return true; }
- final double exactRankThresh = (double)baseCap / totalN;
- return hra && rank >= 1.0 - exactRankThresh || !hra && rank <= exactRankThresh;
+ public double[] getRanks(final float[] values, final boolean inclusive) {
+ if (isEmpty()) { return null; }
+ final int numValues = values.length;
+ final double[] retArr = new double[numValues];
+ if (reqSV != null) {
+ for (int i = 0; i < numValues; i++) {
+ retArr[i] = reqSV.getRank(values[i], inclusive); //already normalized
+ }
+ return retArr;
+ }
+ final long[] cumNnrArr = getCounts(values, inclusive);
+ for (int i = 0; i < numValues; i++) {
+ retArr[i] = (double)cumNnrArr[i] / totalN;
+ }
+ return retArr;
}
@Override
@@ -439,12 +376,9 @@
return ReqSerDe.getSerBytes(this, serDeFormat);
}
- private void grow() {
- final byte lgWeight = (byte)getNumLevels();
- if (lgWeight == 0 && reqDebug != null) { reqDebug.emitStart(this); }
- compactors.add(new ReqCompactor(lgWeight, hra, k, reqDebug));
- maxNomSize = computeMaxNomSize();
- if (reqDebug != null) { reqDebug.emitNewCompactor(lgWeight); }
+ @Override
+ public ReqSketchSortedView getSortedView() {
+ return (reqSV != null) ? reqSV : new ReqSketchSortedView(this);
}
@Override
@@ -490,7 +424,7 @@
compress();
}
assert retItems < maxNomSize;
- aux = null;
+ reqSV = null;
return this;
}
@@ -501,7 +435,7 @@
maxNomSize = 0;
minValue = Float.NaN;
maxValue = Float.NaN;
- aux = null;
+ reqSV = null;
compactors = new ArrayList<>();
grow();
return this;
@@ -536,71 +470,24 @@
}
@Override
- public void update(final float item) {
- if (Float.isNaN(item)) { return; }
+ public void update(final float value) {
+ if (Float.isNaN(value)) { return; }
if (isEmpty()) {
- minValue = item;
- maxValue = item;
+ minValue = value;
+ maxValue = value;
} else {
- if (item < minValue) { minValue = item; }
- if (item > maxValue) { maxValue = item; }
+ if (value < minValue) { minValue = value; }
+ if (value > maxValue) { maxValue = value; }
}
final FloatBuffer buf = compactors.get(0).getBuffer();
- buf.append(item);
+ buf.append(value);
retItems++;
totalN++;
if (retItems >= maxNomSize) {
buf.sort();
compress();
}
- aux = null;
- }
-
- /**
- * Computes a new bound for determining when to compress the sketch.
- */
- int computeMaxNomSize() {
- int cap = 0;
- for (final ReqCompactor c : compactors) { cap += c.getNomCapacity(); }
- return cap;
- }
-
- void setMaxNomSize(final int maxNomSize) {
- this.maxNomSize = maxNomSize;
- }
-
- /**
- * Computes the retItems for the sketch.
- */
- int computeTotalRetainedItems() {
- int count = 0;
- for (final ReqCompactor c : compactors) {
- count += c.getBuffer().getCount();
- }
- return count;
- }
-
- void setRetainedItems(final int retItems) {
- this.retItems = retItems;
- }
-
- /**
- * This checks the given float array to make sure that it contains only finite values
- * and is monotonically increasing in value.
- * @param splits the given array
- */
- static void validateSplits(final float[] splits) {
- final int len = splits.length;
- for (int i = 0; i < len; i++) {
- final float v = splits[i];
- if (!Float.isFinite(v)) {
- throw new SketchesArgumentException("Values must be finite");
- }
- if (i < len - 1 && v >= splits[i + 1]) {
- throw new SketchesArgumentException(
- "Values must be unique and monotonically increasing");
- }
- }
+ reqSV = null;
}
@Override
@@ -619,16 +506,137 @@
return sb.toString();
}
- static void checkK(final int k) {
- if ((k & 1) > 0 || k < 4 || k > 1024) {
- throw new SketchesArgumentException(
- "<i>K</i> must be even and in the range [4, 1024], inclusive: " + k );
- }
+ /**
+ * Computes a new bound for determining when to compress the sketch.
+ */
+ int computeMaxNomSize() {
+ int cap = 0;
+ for (final ReqCompactor c : compactors) { cap += c.getNomCapacity(); }
+ return cap;
}
- static class CompactorReturn {
- int deltaRetItems;
- int deltaNomSize;
+ /**
+ * Computes the retItems for the sketch.
+ */
+ int computeTotalRetainedItems() {
+ int count = 0;
+ for (final ReqCompactor c : compactors) {
+ count += c.getBuffer().getCount();
+ }
+ return count;
+ }
+
+ List<ReqCompactor> getCompactors() {
+ return compactors;
+ }
+
+ int getK() {
+ return k;
+ }
+
+ /**
+ * @return ltEq flag
+ * @deprecated
+ */
+ @Deprecated
+ boolean getLtEq() {
+ return ltEq;
+ }
+
+ int getMaxNomSize() {
+ return maxNomSize;
+ }
+
+ /**
+ * Gets the number of levels of compactors in the sketch.
+ * @return the number of levels of compactors in the sketch.
+ */
+ int getNumLevels() {
+ return compactors.size();
+ }
+
+ void setMaxNomSize(final int maxNomSize) {
+ this.maxNomSize = maxNomSize;
+ }
+
+ void setRetainedItems(final int retItems) {
+ this.retItems = retItems;
+ }
+
+ private void compress() {
+ if (reqDebug != null) { reqDebug.emitStartCompress(); }
+ for (int h = 0; h < compactors.size(); h++) {
+ final ReqCompactor c = compactors.get(h);
+ final int compRetItems = c.getBuffer().getCount();
+ final int compNomCap = c.getNomCapacity();
+
+ if (compRetItems >= compNomCap) {
+ if (h + 1 >= getNumLevels()) { //at the top?
+ if (reqDebug != null) { reqDebug.emitMustAddCompactor(); }
+ grow(); //add a level, increases maxNomSize
+ }
+ final FloatBuffer promoted = c.compact(cReturn);
+ compactors.get(h + 1).getBuffer().mergeSortIn(promoted);
+ retItems += cReturn.deltaRetItems;
+ maxNomSize += cReturn.deltaNomSize;
+ //we specifically decided not to do lazy compression.
+ }
+ }
+ reqSV = null;
+ if (reqDebug != null) { reqDebug.emitCompressDone(); }
+ }
+
+ private long getCount(final float value, final boolean inclusive) {
+ if (isEmpty()) { return 0; }
+ final int numComp = compactors.size();
+ long cumNnr = 0;
+ for (int i = 0; i < numComp; i++) { //cycle through compactors
+ final ReqCompactor c = compactors.get(i);
+ final long wt = 1L << c.getLgWeight();
+ final FloatBuffer buf = c.getBuffer();
+ cumNnr += buf.getCountWithCriterion(value, inclusive) * wt;
+ }
+ return cumNnr;
+ }
+
+ private long[] getCounts(final float[] values, final boolean inclusive) {
+ final int numValues = values.length;
+ final int numComp = compactors.size();
+ final long[] cumNnrArr = new long[numValues];
+ if (isEmpty()) { return cumNnrArr; }
+ for (int i = 0; i < numComp; i++) { //cycle through compactors
+ final ReqCompactor c = compactors.get(i);
+ final long wt = 1L << c.getLgWeight();
+ final FloatBuffer buf = c.getBuffer();
+ for (int j = 0; j < numValues; j++) {
+ cumNnrArr[j] += buf.getCountWithCriterion(values[j], inclusive) * wt;
+ }
+ }
+ return cumNnrArr;
+ }
+
+ /**
+ * Gets a CDF in raw counts, which can be easily converted into a CDF or PMF.
+ * @param splits the splitPoints array
+ * @param inclusive if true the weight of a given value is included into its rank
+ * @return a CDF in raw counts
+ */
+ private long[] getPMForCDF(final float[] splits, final boolean inclusive) {
+ validateSplits(splits);
+ final int numSplits = splits.length;
+ final long[] splitCounts = getCounts(splits, inclusive);
+ final int numBkts = numSplits + 1;
+ final long[] bkts = Arrays.copyOf(splitCounts, numBkts);
+ bkts[numBkts - 1] = getN();
+ return bkts;
+ }
+
+ private void grow() {
+ final byte lgWeight = (byte)getNumLevels();
+ if (lgWeight == 0 && reqDebug != null) { reqDebug.emitStart(this); }
+ compactors.add(new ReqCompactor(lgWeight, hra, k, reqDebug));
+ maxNomSize = computeMaxNomSize();
+ if (reqDebug != null) { reqDebug.emitNewCompactor(lgWeight); }
}
}
diff --git a/src/main/java/org/apache/datasketches/req/ReqSketchSortedView.java b/src/main/java/org/apache/datasketches/req/ReqSketchSortedView.java
new file mode 100644
index 0000000..35f913a
--- /dev/null
+++ b/src/main/java/org/apache/datasketches/req/ReqSketchSortedView.java
@@ -0,0 +1,247 @@
+/*
+ * 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.req;
+
+import java.util.Arrays;
+import java.util.List;
+
+import org.apache.datasketches.InequalitySearch;
+
+/**
+ * The Sorted View provides a view of the data retained by the sketch that would be cumbersome to get any other way.
+ * One can iterate of the contents of the sketch, but the result is not sorted.
+ * Trying to use getQuantiles would be very cumbersome since one doesn't know what ranks to use to supply the
+ * getQuantiles method. Even worse, suppose it is a large sketch that has retained 1000 values from a stream of
+ * millions (or billions). One would have to execute the getQuantiles method many thousands of times, and using
+ * trial & error, try to figure out what the sketch actually has retained.
+ *
+ * <p>The data from a Sorted view is an unbiased sample of the input stream that can be used for other kinds of
+ * analysis not directly provided by the sketch. A good example comparing two sketches using the Kolmogorov-Smirnov
+ * test. One needs this sorted view for the test.</p>
+ *
+ * <p>This sorted view can also be used for multiple getRank and getQuantile queries once it has been created.
+ * Because it takes some computational work to create this sorted view, it doesn't make sense to create this sorted view
+ * just for single getRank queries. For the first getQuantile queries, it must be created. But for all queries
+ * after the first, assuming the sketch has not been updated, the getQuantile and getRank queries are very fast.<p>
+ * @author Lee Rhodes
+ */
+public class ReqSketchSortedView {
+ private static final String LS = System.getProperty("line.separator");
+ private float[] values;
+ private long[] cumWeights;
+ private final boolean hra; //used in merge
+ private final long N;
+ private final boolean dedup;
+
+ /**
+ *
+ * Construct this sorted view with the given sketch.
+ * The number of values in this sorted view will be the same as the number of retained values in the sketch.
+ * @param sk the given sketch
+ */
+ public ReqSketchSortedView(final ReqSketch sk) {
+ this(sk, false);
+ }
+
+ /**
+ * Construct this sorted view with the given sketch and option to deduplicate the values.
+ * The weights will be combined for the duplicate values.
+ * The getQuantile() and getRank() methods will work correctly.
+ * @param sk the given sketch
+ * @param dedup if true, duplicate values will be combined into a single value with the combined weights.
+ */
+ public ReqSketchSortedView(final ReqSketch sk, final boolean dedup) {
+ hra = sk.getHighRankAccuracy();
+ N = sk.getN();
+ this.dedup = dedup;
+ buildAuxTable(sk);
+ }
+
+ /**
+ * Gets the quantile based on the given normalized rank,
+ * which must be in the range [0.0, 1.0], inclusive.
+ * @param normRank the given normalized rank
+ * @param inclusive determines the search criterion used.
+ * @return the quantile
+ */
+ public float getQuantile(final double normRank, final boolean inclusive) {
+ final int len = cumWeights.length;
+ final long rank = (int)(normRank * N);
+ final InequalitySearch crit = inclusive ? InequalitySearch.GE : InequalitySearch.GT;
+ final int index = InequalitySearch.find(cumWeights, 0, len - 1, rank, crit);
+ if (index == -1) {
+ return values[len - 1]; //GT: normRank >= 1.0; GE: normRank > 1.0
+ }
+ return values[index];
+ }
+
+ /**
+ * Gets the normalized rank based on the given value.
+ * @param value the given value
+ * @param inclusive determines the search criterion used.
+ * @return the normalized rank
+ */
+ public double getRank(final float value, final boolean inclusive) {
+ final int len = values.length;
+ final InequalitySearch crit = inclusive ? InequalitySearch.LE : InequalitySearch.LT;
+ final int index = InequalitySearch.find(values, 0, len - 1, value, crit);
+ if (index == -1) {
+ return 0; //LT: value <= minValue; LE: value < minValue
+ }
+ return (double)cumWeights[index] / N;
+ }
+
+ public ReqSketchSortedViewIterator iterator() {
+ return new ReqSketchSortedViewIterator(values, cumWeights);
+ }
+
+ public String toString(final int precision, final int fieldSize) {
+ final StringBuilder sb = new StringBuilder();
+ final int p = precision;
+ final int z = Math.max(fieldSize, 6);
+ final String ff = "%" + z + "." + p + "f";
+ final String sf = "%" + z + "s";
+ final String df = "%" + z + "d";
+ final String dfmt = ff + df + LS;
+ final String sfmt = sf + sf + LS;
+ sb.append("REQ toString(): Sorted View Data:").append(LS + LS);
+ sb.append(String.format(sfmt, "Value", "CumWeight"));
+ final int totalCount = values.length;
+ for (int i = 0; i < totalCount; i++) {
+ final Row row = getRow(i);
+ sb.append(String.format(dfmt, row.value, row.cumWeight));
+ }
+ return sb.toString();
+ }
+
+ //restricted methods
+
+ private void buildAuxTable(final ReqSketch sk) {
+ final List<ReqCompactor> compactors = sk.getCompactors();
+ final int numComp = compactors.size();
+ final int totalValues = sk.getRetainedItems();
+ values = new float[totalValues];
+ cumWeights = new long[totalValues];
+ int count = 0;
+ for (int i = 0; i < numComp; i++) {
+ final ReqCompactor c = compactors.get(i);
+ final FloatBuffer bufIn = c.getBuffer();
+ final long bufWeight = 1 << c.getLgWeight();
+ final int bufInLen = bufIn.getCount();
+ mergeSortIn(bufIn, bufWeight, count);
+ count += bufInLen;
+ }
+ createCumulativeNativeRanks();
+ if (dedup) { dedup(); }
+ }
+
+ /**
+ * Specially modified version of FloatBuffer.mergeSortIn(). Here spaceAtBottom is always false and
+ * the ultimate array size has already been set. However, this must simultaneously deal with
+ * sorting the base FloatBuffer as well.
+ *
+ * @param bufIn given FloatBuffer. If not sorted it will be sorted here.
+ * @param bufWeight associated weight of input FloatBuffer
+ * @param count tracks number of values inserted into the class arrays
+ */
+ private void mergeSortIn(final FloatBuffer bufIn, final long bufWeight, final int count) {
+ if (!bufIn.isSorted()) { bufIn.sort(); }
+ final float[] arrIn = bufIn.getArray(); //may be larger than its value count.
+ final int bufInLen = bufIn.getCount();
+ final int totLen = count + bufInLen;
+ int i = count - 1;
+ int j = bufInLen - 1;
+ int h = hra ? bufIn.getCapacity() - 1 : bufInLen - 1;
+ for (int k = totLen; k-- > 0; ) {
+ if (i >= 0 && j >= 0) { //both valid
+ if (values[i] >= arrIn[h]) {
+ values[k] = values[i];
+ cumWeights[k] = cumWeights[i--]; //not yet natRanks, just individual wts
+ } else {
+ values[k] = arrIn[h--]; j--;
+ cumWeights[k] = bufWeight;
+ }
+ } else if (i >= 0) { //i is valid
+ values[k] = values[i];
+ cumWeights[k] = cumWeights[i--];
+ } else if (j >= 0) { //j is valid
+ values[k] = arrIn[h--]; j--;
+ cumWeights[k] = bufWeight;
+ } else {
+ break;
+ }
+ }
+ }
+
+ private void createCumulativeNativeRanks() {
+ final int len = values.length;
+ for (int i = 1; i < len; i++) {
+ cumWeights[i] += cumWeights[i - 1];
+ }
+ assert cumWeights[len - 1] == N;
+ }
+
+ private void dedup() {
+ final int valuesLen = values.length;
+ final float[] valuesB = new float[valuesLen];
+ final long[] natRanksB = new long[valuesLen];
+ int bidx = 0;
+ int i = 0;
+ while (i < valuesLen) {
+ int j = i + 1;
+ int hidup = j;
+ while (j < valuesLen && values[i] == values[j]) {
+ hidup = j++;
+ }
+ if (j - i == 1) { //no dups
+ valuesB[bidx] = values[i];
+ natRanksB[bidx++] = cumWeights[i];
+ i++;
+ continue;
+ } else {
+ valuesB[bidx] = values[hidup];
+ natRanksB[bidx++] = cumWeights[hidup];
+ i = j;
+ continue;
+ }
+ }
+ values = Arrays.copyOf(valuesB, bidx);
+ cumWeights = Arrays.copyOf(natRanksB, bidx);
+ }
+
+
+
+ //used for testing and for public SortedView toString
+
+ Row getRow(final int index) {
+ return new Row(values[index], cumWeights[index]);
+ }
+
+ static class Row {
+ float value;
+ long cumWeight;
+
+ Row(final float value, final long cumWeight) {
+ this.value = value;
+ this.cumWeight = cumWeight;
+ }
+ }
+
+}
diff --git a/src/main/java/org/apache/datasketches/req/ReqSketchSortedViewIterator.java b/src/main/java/org/apache/datasketches/req/ReqSketchSortedViewIterator.java
new file mode 100644
index 0000000..8bc1a65
--- /dev/null
+++ b/src/main/java/org/apache/datasketches/req/ReqSketchSortedViewIterator.java
@@ -0,0 +1,111 @@
+/*
+
+ * 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.req;
+
+/**
+ * Iterator over ReqSketchSortedView.
+ *
+ * <p>The recommended iteration loop:</p>
+ * <pre>{@code
+ * ReqSketchSortedViewIterator itr = sketch.getSortedView().iterator();
+ * while (itr.next()) {
+ * float v = itr.getValue();
+ * ...
+ * }
+ * }</pre>
+ */
+public class ReqSketchSortedViewIterator {
+
+ private final float[] values;
+ private final long[] cumWeights;
+ private final long totalN;
+ private int index;
+
+ ReqSketchSortedViewIterator(final float[] values, final long[] cumWeights) {
+ this.values = values;
+ this.cumWeights = cumWeights;
+ this.totalN = cumWeights[cumWeights.length - 1];
+ index = -1;
+ }
+
+ /**
+ * Gets the current value.
+ *
+ * <p>Don't call this before calling next() for the first time
+ * or after getting false from next(). </p>
+ * @return the current value
+ */
+ public float getValue() {
+ return values[index];
+ }
+
+ /**
+ * Gets the cumulative weight for the current value.
+ *
+ * <p>Don't call this before calling next() for the first time
+ * or after getting false from next().</p>
+ * @param inclusive If true, includes the weight of the current value.
+ * Otherwise, returns the cumulative weightof the previous value.
+ * @return cumulative weight for the current value.
+ */
+ public long getCumulativeWeight(final boolean inclusive) {
+ return inclusive ? cumWeights[index]
+ : (index == 0) ? 0 : cumWeights[index - 1];
+ }
+
+ /**
+ * Gets the normalized rank for the current value or previous value.
+ *
+ * <p>Don't call this before calling next() for the first time
+ * or after getting false from next().</p>
+ * @param inclusive if true, returns the normalized rank of the current value.
+ * Otherwise, returns the normalized rank of the previous value.
+ * @return normalized rank for the current value or previous value.
+ */
+ public double getNormalizedRank(final boolean inclusive) {
+ return (double) getCumulativeWeight(inclusive) / totalN;
+ }
+
+ /**
+ * Gets the weight of the current value.
+ *
+ * <p>Don't call this before calling next() for the first time
+ * or after getting false from next().</p>
+ * @return item weight of the current value.
+ */
+ public long getWeight() {
+ if (index == 0) { return cumWeights[0]; }
+ return cumWeights[index] - cumWeights[index - 1];
+ }
+
+ /**
+ * Advancing the iterator and checking existence of the next element
+ * is combined here for efficiency. This results in an undefined
+ * state of the iterator before the first call of this method.
+ * @return true if the next element exists
+ */
+ public boolean next() {
+ index++;
+ return index < values.length;
+ }
+
+}
+
diff --git a/src/test/java/org/apache/datasketches/CrossCheckQuantilesTest.java b/src/test/java/org/apache/datasketches/CrossCheckQuantilesTest.java
new file mode 100644
index 0000000..945e9f9
--- /dev/null
+++ b/src/test/java/org/apache/datasketches/CrossCheckQuantilesTest.java
@@ -0,0 +1,356 @@
+/*
+ * 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;
+
+import static org.apache.datasketches.CrossCheckQuantilesTest.PrimType.DOUBLE;
+import static org.apache.datasketches.CrossCheckQuantilesTest.PrimType.FLOAT;
+import static org.apache.datasketches.CrossCheckQuantilesTest.SkType.CLASSIC;
+import static org.apache.datasketches.CrossCheckQuantilesTest.SkType.KLL;
+import static org.apache.datasketches.CrossCheckQuantilesTest.SkType.REQ;
+import static org.apache.datasketches.CrossCheckQuantilesTest.SkType.REQ_NO_DEDUP;
+import static org.apache.datasketches.CrossCheckQuantilesTest.SkType.REQ_SV;
+import static org.testng.Assert.assertEquals;
+
+import org.apache.datasketches.kll.KllFloatsSketch;
+import org.apache.datasketches.quantiles.DoublesSketch;
+import org.apache.datasketches.quantiles.UpdateDoublesSketch;
+import org.apache.datasketches.req.ReqSketch;
+import org.apache.datasketches.req.ReqSketchBuilder;
+import org.apache.datasketches.req.ReqSketchSortedView;
+import org.testng.annotations.Test;
+
+public class CrossCheckQuantilesTest {
+
+ enum SkType { REQ, REQ_SV, REQ_NO_DEDUP, KLL, CLASSIC }
+
+ enum PrimType { DOUBLE, FLOAT }
+
+ final int k = 32; //all sketches are in exact mode
+ final boolean hra = false; //for the REQ sketch
+ final boolean INCLUSIVE = true;
+ final boolean NON_INCLUSIVE = false;
+
+ @Test
+ public void checkQuantileSketches() {
+ checkQAndR(REQ, FLOAT, NON_INCLUSIVE); //must do REQ first to compute expected results!
+ checkQAndR(REQ, FLOAT, INCLUSIVE);
+
+ checkQAndR(REQ_SV, FLOAT, NON_INCLUSIVE);
+ checkQAndR(REQ_SV, FLOAT, INCLUSIVE);
+
+ checkQAndR(REQ_NO_DEDUP, FLOAT, NON_INCLUSIVE);
+ checkQAndR(REQ_NO_DEDUP, FLOAT, INCLUSIVE);
+
+ checkQAndR(KLL, FLOAT, NON_INCLUSIVE);
+ checkQAndR(KLL, FLOAT, INCLUSIVE);
+
+ checkQAndR(CLASSIC, DOUBLE, NON_INCLUSIVE);
+ checkQAndR(CLASSIC, DOUBLE, INCLUSIVE);
+ println("");
+ }
+
+ double[] testRankResults_NI = null;
+ double[] testRankResults_I = null;
+ float[] testQuantileFResults_NI = null;
+ float[] testQuantileFResults_I = null;
+ double[] testQuantileDResults_NI = null;
+ double[] testQuantileDResults_I = null;
+
+ private void checkQAndR(final SkType skType, final PrimType type, final boolean inclusive) {
+ String head = "CHECK " + skType.toString();
+ if (inclusive) { println("\n---------- " + head + " INCLUSIVE ----------\n"); }
+ else { println("\n########## " + head + " NON-INCLUSIVE ##########\n"); }
+
+ //CREATE EMPTY SKETCHES
+ ReqSketchBuilder reqBldr = ReqSketch.builder();
+ reqBldr.setK(k).setHighRankAccuracy(hra).setLessThanOrEqual(inclusive);
+ ReqSketch reqSk = reqBldr.build();
+
+ KllFloatsSketch kllSk = KllFloatsSketch.newHeapInstance(k);
+
+ UpdateDoublesSketch udSk = DoublesSketch.builder().setK(k).build();
+
+ //SKETCH INPUT.
+ float[] baseFVals = {10,20,30,40,50};
+ double[] baseDVals = {10,20,30,40,50};
+ int[] baseDups = { 1, 4, 6, 2, 1}; //number of duplicates per base value
+
+ //RAW TEST INPUT. This simulates what the Sorted View might see.
+ //This checks the search algos without the sketch and created by hand
+ float[] rawFVals = {10,20,20,30,30, 30, 40, 50}; //note grouping by twos
+ long[] rawCumWts = { 1, 3, 5, 7, 9, 11, 13, 14};
+
+ //COMPUTE N
+ int N = 0;
+ for (int i : baseDups) { N += i; }
+ int numV = baseFVals.length; //num of distinct input values
+
+ //CREATE SKETCH INPUT ARRAYS
+ float[] skFValues = new float[N];
+ double[] skDValues = new double[N];
+ int n = 0;
+ for (int bv = 0; bv < baseFVals.length; bv++) {
+ float bvF = baseFVals[bv];
+ double bvD = baseDVals[bv];
+ for (int i = 0; i < baseDups[bv]; i++) {
+ skFValues[n] = bvF;
+ skDValues[n] = bvD;
+ n++;
+ }
+ }
+
+ //CREATE getRank TEST VALUES
+ int numTV = 2 * numV + 1;
+ float[] testFValues = new float[numTV];
+ double[] testDValues = new double[numTV];
+ for (int i = 0; i < numTV; i++) {
+ testFValues[i] = 5F * (i + 1);
+ testDValues[i] = 5.0 * (i + 1);
+ }
+
+ //CREATE getQuantile() TEST NORMALIZED RANKS
+ //One for each value in the stream + one inbetween and zero
+ int numTR = 2 * N + 1;
+ double[] testRanks = new double[numTR];
+ testRanks[0] = 0;
+ for (int i = 1; i < numTR; i++) {
+ testRanks[i] = (double) i / (numTR - 1);
+ }
+
+ //TEST RESULT ARRAYS, NI = non inclusive, I = inclusive
+ if (testRankResults_NI == null) {
+ testRankResults_NI = new double[numTV];
+ testRankResults_I = new double[numTV];
+ testQuantileFResults_NI = new float[numTR];
+ testQuantileFResults_I = new float[numTR];
+ testQuantileDResults_NI = new double[numTR];
+ testQuantileDResults_I = new double[numTR];
+ }
+
+ println("Sketch Input with exact weights and ranks:");
+ println(" Sketch only keeps individual value weights per level.");
+ println(" Cumulative Weights are computed in Sorted View.");
+ println(" Normalized Ranks are computed on the fly.");
+ println("");
+ printf("%16s%16s%16s\n", "Value", "CumWeight", "NormalizedRank");
+
+ //LOAD THE SKETCHES and PRINT
+ for (int i = 0; i < N; i++) {
+ printf("%16.1f%16d%16.3f\n", skFValues[i], i + 1, (i + 1.0)/N);
+ reqSk.update(skFValues[i]);
+ kllSk.update(skFValues[i]);
+ udSk.update((skDValues[i]));
+ }
+ println("");
+
+ //REQ SORTED VIEW DATA:
+ ReqSketchSortedView rssv = null;
+ if (skType.toString().startsWith("REQ")) {
+ rssv = new ReqSketchSortedView(reqSk);
+ println(rssv.toString(1, 16));
+ }
+
+ /**************************************/
+
+ println(skType.toString() + " GetQuantile(NormalizedRank), INCLUSIVE = " + inclusive);
+ println(" CumWeight is for illustration");
+ println(" Convert NormalizedRank to CumWeight (CW).");
+ println(" Search RSSV CumWeights[] array:");
+ println(" Non Inclusive (uses GT): arr[A] <= CW < arr[B], return B");
+ println(" Inclusive (uses GE): arr[A] < CW <= arr[B], return B");
+ println(" Return Values[B]");
+ println("");
+ printf("%16s%16s%16s%16s\n", "NormalizedRank", "CumWeight", "Quantile", "True_Quantile");
+ for (int i = 0; i < numTR; i++) {
+ double testRank = testRanks[i];
+ float qF; //float result
+ double qD;//double result
+ switch (skType) {
+ case REQ: { //this case creates the expected values for all the others
+ qF = reqSk.getQuantile(testRank, inclusive);
+ qD = qF;
+ if (inclusive) {
+ testQuantileFResults_I[i] = qF;
+ testQuantileDResults_I[i] = qD;
+ }
+ else {
+ testQuantileFResults_NI[i] = qF;
+ testQuantileDResults_NI[i] = qD;
+ }
+ break;
+ }
+ case REQ_SV: {
+ qF = rssv.getQuantile(testRank, inclusive);
+ qD = 0;
+ if (inclusive) { assertEquals(qF, testQuantileFResults_I[i]); }
+ else { assertEquals(qF, testQuantileFResults_NI[i]); };
+ break;
+ }
+ case REQ_NO_DEDUP: {
+ qF = this.getQuantile(rawCumWts, rawFVals, testRank, inclusive);
+ qD = 0;
+ if (inclusive) { assertEquals(qF, testQuantileFResults_I[i]); }
+ else { assertEquals(qF, testQuantileFResults_NI[i]); };
+ break;
+ }
+ case KLL: {
+ qF = kllSk.getQuantile(testRank, inclusive);
+ qD = 0;
+ if (inclusive) { assertEquals(qF, testQuantileFResults_I[i]); }
+ else { assertEquals(qF, testQuantileFResults_NI[i]); };
+ break;
+ }
+ case CLASSIC: {
+ qF = 0;
+ qD = kllSk.getQuantile(testRank, inclusive);
+ if (inclusive) { assertEquals(qD, testQuantileDResults_I[i]); }
+ else { assertEquals(qD, testQuantileDResults_NI[i]); };
+ break;
+ }
+ default: qD = qF = 0; break;
+ }
+ if (inclusive) {
+ if (type == PrimType.DOUBLE) {
+ printf("%16.3f%16.3f%16.1f%16.1f\n", testRank, testRank * N, qD, testQuantileDResults_I[i]);
+ } else { //float
+ printf("%16.3f%16.3f%16.1f%16.1f\n", testRank, testRank * N, qF, testQuantileFResults_I[i]);
+ }
+ } else { //else NI
+ if (type == PrimType.DOUBLE) {
+ printf("%16.3f%16.3f%16.1f%16.1f\n", testRank, testRank * N, qD, testQuantileDResults_NI[i]);
+ } else { //float
+ printf("%16.3f%16.3f%16.1f%16.1f\n", testRank, testRank * N, qF, testQuantileFResults_NI[i]);
+ }
+ }
+ }
+
+ //GET RANK
+ println("");
+ println(skType.toString() + " GetRank(Value), INCLUSIVE = " + inclusive);
+ println(" Search RSSV Values[] array:");
+ println(" Non Inclusive (uses LT): arr[A] < V <= arr[B], return A");
+ println(" Inclusive (uses LE): arr[A] <= V < arr[B], return A");
+ println(" Convert CumWeights[A] to NormRank,");
+ println(" Return NormRank");
+ printf("%16s%16s%16s\n", "ValueIn", "NormalizedRank", "True-NormRank");
+
+ double r; //result
+ for (int i = 0; i < numTV; i++) {
+ float testValue = testFValues[i];
+ switch (skType) {
+ case REQ: {
+ r = reqSk.getRank(testValue, inclusive);
+ if (inclusive) { testRankResults_I[i] = r; }
+ else { testRankResults_NI[i] = r; }
+ break;
+ }
+ case REQ_SV: {
+ r = rssv.getRank(testValue, inclusive);
+ if (inclusive) { assertEquals(r, testRankResults_I[i]); }
+ else { assertEquals(r, testRankResults_NI[i]); };
+ break;
+ }
+ case REQ_NO_DEDUP: {
+ r = getRank(rawCumWts, rawFVals, testValue, inclusive);
+ if (inclusive) { assertEquals(r, testRankResults_I[i]); }
+ else { assertEquals(r, testRankResults_NI[i]); };
+ break;
+ }
+ case KLL: {
+ r = kllSk.getRank(testValue, inclusive);
+ if (inclusive) { assertEquals(r, testRankResults_I[i]); }
+ else { assertEquals(r, testRankResults_NI[i]); };
+ break;
+ }
+ case CLASSIC: {
+ r = udSk.getRank(testValue, inclusive);
+ if (inclusive) { assertEquals(r, testRankResults_I[i]); }
+ else { assertEquals(r, testRankResults_NI[i]); };
+ break;
+ }
+ default: r = 0; break;
+ }
+ if (inclusive) {
+ printf("%16.1f%16.3f%16.3f\n", testValue, r, testRankResults_I[i]);
+ } else {
+ printf("%16.1f%16.3f%16.3f\n", testValue, r, testRankResults_NI[i]);
+ }
+ }
+ }
+
+ /**
+ * Gets the quantile based on the given normalized rank,
+ * which must be in the range [0.0, 1.0], inclusive.
+ * @param cumWeights the given cumulative weights
+ * @param values the given values
+ * @param normRank the given normalized rank
+ * @param inclusive determines the search criterion used.
+ * @return the quantile
+ */
+ public float getQuantile(final long[] cumWeights, final float[] values, final double normRank,
+ final boolean inclusive) {
+ final int len = cumWeights.length;
+ final long N = cumWeights[len -1];
+ final long rank = (int)(normRank * N);
+ final InequalitySearch crit = inclusive ? InequalitySearch.GE : InequalitySearch.GT;
+ final int index = InequalitySearch.find(cumWeights, 0, len - 1, rank, crit);
+ if (index == -1) {
+ return values[len - 1]; //GT: normRank >= 1.0; GE: normRank > 1.0
+ }
+ return values[index];
+ }
+
+ /**
+ * Gets the normalized rank based on the given value.
+ * @param cumWeights the given cumulative weights
+ * @param values the given values
+ * @param value the given value
+ * @param ltEq determines the search criterion used.
+ * @return the normalized rank
+ */
+ public double getRank(final long[] cumWeights, final float[] values, final float value, final boolean ltEq) {
+ final int len = values.length;
+ final long N = cumWeights[len -1];
+ final InequalitySearch crit = ltEq ? InequalitySearch.LE : InequalitySearch.LT;
+ final int index = InequalitySearch.find(values, 0, len - 1, value, crit);
+ if (index == -1) {
+ return 0; //LT: value <= minValue; LE: value < minValue
+ }
+ return (double)cumWeights[index] / 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/GenericInequalitySearchTest.java b/src/test/java/org/apache/datasketches/GenericInequalitySearchTest.java
index fa2e638..2d6729f 100644
--- a/src/test/java/org/apache/datasketches/GenericInequalitySearchTest.java
+++ b/src/test/java/org/apache/datasketches/GenericInequalitySearchTest.java
@@ -67,17 +67,6 @@
}
}
- private static String listFltArray(final Float[] arr, final int low, final int high) {
- final StringBuilder sb = new StringBuilder();
- sb.append(LS);
- sb.append("arr: ");
- for (int i = 0; i < arr.length; i++) {
- if (i == low || i == high) { sb.append(String.format("(%.0f) ", arr[i])); }
- else { sb.append(String.format("%.0f ", arr[i])); }
- }
- return sb.toString();
- }
-
@Test
public void checkBinSearchFltLimits() {
for (int len = 10; len <= 13; len++) {
@@ -89,6 +78,19 @@
}
}
+ private static String listFltArray(final Float[] arr, final int low, final int high) {
+ final StringBuilder sb = new StringBuilder();
+ sb.append(LS);
+ sb.append("The values in parentheses are the low and high values of the sub-array to search");
+ sb.append(LS);
+ sb.append("arr: ");
+ for (int i = 0; i < arr.length; i++) {
+ if (i == low || i == high) { sb.append(String.format("(%.0f) ", arr[i])); }
+ else { sb.append(String.format("%.0f ", arr[i])); }
+ }
+ return sb.toString();
+ }
+
private void checkBinarySearchFloatLimits(final Float[] arr, final int low, final int high) {
final Float lowV = arr[low];
final Float highV = arr[high];
@@ -287,27 +289,28 @@
return "";
}
+ private final static boolean enablePrinting = false;
/**
* @param format the format
* @param args the args
*/
static final void printf(final String format, final Object ...args) {
- //System.out.printf(format, args);
+ if (enablePrinting) { System.out.printf(format, args); }
}
/**
* @param o the Object to println
*/
static final void println(final Object o) {
- //System.out.println(o.toString());
+ if (enablePrinting) { System.out.println(o.toString()); }
}
/**
* @param o the Object to print
*/
static final void print(final Object o) {
- //System.out.print(o.toString());
+ if (enablePrinting) { System.out.print(o.toString()); }
}
}
diff --git a/src/test/java/org/apache/datasketches/quantiles/HeapUpdateDoublesSketchTest.java b/src/test/java/org/apache/datasketches/quantiles/HeapUpdateDoublesSketchTest.java
index 1a4a6a3..e4be39c 100644
--- a/src/test/java/org/apache/datasketches/quantiles/HeapUpdateDoublesSketchTest.java
+++ b/src/test/java/org/apache/datasketches/quantiles/HeapUpdateDoublesSketchTest.java
@@ -35,7 +35,6 @@
import java.nio.ByteOrder;
-import org.apache.datasketches.QuantilesHelper;
import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
@@ -853,10 +852,11 @@
qs1.putMemory(dstMem);
}
+ @SuppressWarnings("deprecation")
@Test
public void checkAuxPosOfRank() throws Exception {
long n = 10;
- long returnValue = QuantilesHelper.posOfRank(1.0, 10);
+ long returnValue = ClassicQuantilesHelper.posOfRank(1.0, 10);
//println("" + returnValue);
assertEquals(returnValue, n-1);
}
diff --git a/src/test/java/org/apache/datasketches/req/ReqAuxiliaryTest.java b/src/test/java/org/apache/datasketches/req/ReqAuxiliaryTest.java
deleted file mode 100644
index 66e90eb..0000000
--- a/src/test/java/org/apache/datasketches/req/ReqAuxiliaryTest.java
+++ /dev/null
@@ -1,68 +0,0 @@
-/*
- * 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.req;
-
-import static org.testng.Assert.assertTrue;
-
-import org.apache.datasketches.req.ReqAuxiliary.Row;
-import org.testng.annotations.Test;
-
-/**
- * @author Lee Rhodes
- */
-
-public class ReqAuxiliaryTest {
-
- @Test
- public void checkMergeSortIn() {
- checkMergeSortInImpl(true);
- checkMergeSortInImpl(false);
- }
-
- private static void checkMergeSortInImpl(final boolean hra) {
- final FloatBuffer buf1 = new FloatBuffer(25, 0, hra);
- for (int i = 1; i < 12; i += 2) { buf1.append(i); } //6 items
- final FloatBuffer buf2 = new FloatBuffer(25, 0, hra);
- for (int i = 2; i <= 12; i += 2) { buf2.append(i); } //6 items
- final long N = 12;
-
- final float[] items = new float[25];
- final long[] weights = new long[25];
-
- final ReqAuxiliary aux = new ReqAuxiliary(items, weights, hra, N);
- aux.mergeSortIn(buf1, 1, 0);
- aux.mergeSortIn(buf2, 2, 6);
- println(aux.toString(3, 12));
- Row row = aux.getRow(0);
- for (int i = 1; i < 12; i++) {
- final Row rowi = aux.getRow(i);
- assertTrue(rowi.item >= row.item);
- row = rowi;
- }
- }
-
- /**
- * output
- * @param o object
- */
- static final void println(final Object o) {
- //System.out.println(o.toString());
- }
-}
diff --git a/src/test/java/org/apache/datasketches/req/ReqSketchOtherTest.java b/src/test/java/org/apache/datasketches/req/ReqSketchOtherTest.java
index f4313d0..3f9499a 100644
--- a/src/test/java/org/apache/datasketches/req/ReqSketchOtherTest.java
+++ b/src/test/java/org/apache/datasketches/req/ReqSketchOtherTest.java
@@ -104,7 +104,7 @@
assertEquals(maxNomSize, 240);
final float v = sk.getQuantile(1.0);
assertEquals(v, 120.0f);
- final ReqAuxiliary aux = sk.getAux();
+ final ReqSketchSortedView aux = sk.getSortedView();
assertNotNull(aux);
assertTrue(sk.getRSE(sk.getK(), .5, false, 120) > 0);
assertTrue(sk.getSerializationBytes() > 0);
diff --git a/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java b/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java
new file mode 100644
index 0000000..8281126
--- /dev/null
+++ b/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java
@@ -0,0 +1,107 @@
+/*
+ * 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.req;
+
+import org.testng.annotations.Test;
+
+/**
+ * @author Lee Rhodes
+ */
+
+public class ReqSketchSortedViewTest {
+ private final int k = 32;
+ private final boolean hra = false;
+ private final int numV = 3;
+ private final int dup = 2;
+ private final int n = numV * dup;
+
+ @Test
+ public void checkIterator() {
+ println("");
+ println("CHECK ReqSketchSortedViewIterator");
+ println(" k: " + k + ", hra: " + hra);
+ println(" numV: " + numV + ", dup: " + dup + ", Total n = " + n);
+ ReqSketch sketch = buildDataLoadSketch();
+ checkNotDedup(sketch);
+ checkDedup(sketch);
+ }
+
+ private ReqSketch buildDataLoadSketch() {
+ float[] fArr = new float[n];
+ int h = 0;
+ for (int i = 0; i < numV; i++) {
+ float flt = (i + 1) * 10;
+ for (int j = 1; j <= dup; j++) { fArr[h++] = flt; }
+ }
+ ReqSketchBuilder bldr = ReqSketch.builder();
+ ReqSketch sketch = bldr.build();
+ for (int i = 0; i < n; i++) { sketch.update(fArr[i]); }
+ return sketch;
+ }
+
+ private void checkNotDedup(final ReqSketch sketch) {
+ println("\nNot Deduped:");
+ ReqSketchSortedView sv = sketch.getSortedView();
+ ReqSketchSortedViewIterator itr = sv.iterator();
+ printIterator(itr);
+ }
+
+ private void checkDedup(final ReqSketch sketch) {
+ println("\nDeduped:");
+ ReqSketchSortedView sv = new ReqSketchSortedView(sketch, true);
+ ReqSketchSortedViewIterator itr = sv.iterator();
+ printIterator(itr);
+ }
+
+ private void printIterator(final ReqSketchSortedViewIterator itr) {
+ println("");
+ String[] header = {"Value", "Wt", "CumWtNotInc", "NormRankNotInc", "CumWtInc", "NormRankInc"};
+ String hfmt = "%8s%6s%16s%16s%16s%16s\n";
+ String fmt = "%8.1f%6d%16d%16.3f%16d%16.3f\n";
+ printf(hfmt, (Object[]) header);
+ while (itr.next()) {
+ float v = itr.getValue();
+ long wt = itr.getWeight();
+ long cumWtNotInc = itr.getCumulativeWeight(false);
+ double nRankNotInc = itr.getNormalizedRank(false);
+ long cumWtInc = itr.getCumulativeWeight(true);
+ double nRankInc = itr.getNormalizedRank(true);
+ printf(fmt, v, wt, cumWtNotInc, nRankNotInc, cumWtInc, nRankInc);
+ }
+ }
+
+ 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/req/ReqSketchTest.java b/src/test/java/org/apache/datasketches/req/ReqSketchTest.java
index 6436292..cdd3a8d 100644
--- a/src/test/java/org/apache/datasketches/req/ReqSketchTest.java
+++ b/src/test/java/org/apache/datasketches/req/ReqSketchTest.java
@@ -27,8 +27,7 @@
import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.memory.Memory;
-//import static org.apache.datasketches.req.FloatBuffer.TAB;
-import org.apache.datasketches.req.ReqAuxiliary.Row;
+import org.apache.datasketches.req.ReqSketchSortedView.Row;
import org.testng.annotations.Test;
/**
@@ -60,7 +59,7 @@
}
final ReqSketch sk = loadSketch(k, min, max, up, hra, ltEq, skDebug);
checkToString(sk, iDebug);
- checkAux(sk, iDebug);
+ checkSortedView(sk, iDebug);
checkGetRank(sk, min, max, iDebug);
checkGetRanks(sk, max, iDebug);
checkGetQuantiles(sk, iDebug);
@@ -153,23 +152,23 @@
if (iDebug > 0) { println(""); }
}
- private static void checkAux(final ReqSketch sk, final int iDebug) {
- final ReqAuxiliary aux = new ReqAuxiliary(sk);
- if (iDebug > 0) { println(aux.toString(3,12)); }
+ private static void checkSortedView(final ReqSketch sk, final int iDebug) {
+ final ReqSketchSortedView sv = new ReqSketchSortedView(sk);
+ if (iDebug > 0) { println(sv.toString(3,12)); }
final int totalCount = sk.getRetainedItems();
- float item = 0;
+ float value = 0;
long wt = 0;
for (int i = 0; i < totalCount; i++) {
- final Row row = aux.getRow(i);
+ final Row row = sv.getRow(i);
if (i == 0) {
- item = row.item;
- wt = row.weight;
+ value = row.value;
+ wt = row.cumWeight;
} else {
- assertTrue(row.item >= item);
- assertTrue(row.weight >= wt);
- item = row.item;
- wt = row.weight;
+ assertTrue(row.value >= value);
+ assertTrue(row.cumWeight >= wt);
+ value = row.value;
+ wt = row.cumWeight;
}
}
}
@@ -214,7 +213,7 @@
}
private static void checkIterator(final ReqSketch sk, final int iDebug) {
- if (iDebug > 0) { println("iterator() Test"); }
+ if (iDebug > 0) { println("Sketch iterator() Test"); }
final ReqIterator itr = sk.iterator();
while (itr.next()) {
final float v = itr.getValue();
@@ -288,6 +287,7 @@
checkSerDeImpl(12, true, 2 * exact);
}
+ @SuppressWarnings("deprecation")
private static void checkSerDeImpl(final int k, final boolean hra, final int count) {
final ReqSketch sk1 = ReqSketch.builder().setK(k).setHighRankAccuracy(hra).build();
for (int i = 1; i <= count; i++) {
@@ -332,7 +332,7 @@
}
@Test
- public void tenItems() {
+ public void tenValues() {
final ReqSketch sketch = ReqSketch.builder().build();
for (int i = 1; i <= 10; i++) { sketch.update(i); }
assertFalse(sketch.isEmpty());
@@ -387,7 +387,8 @@
}
}
- private static void outputCompactorDetail(final ReqSketch sk, final String fmt, final boolean allData, final String text) {
+ private static void outputCompactorDetail(final ReqSketch sk, final String fmt, final boolean allData,
+ final String text) {
println(text);
println(sk.viewCompactorDetail(fmt, allData));
}
