This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch new_kll_items_sketch in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 035ba13a4e83738feef2d0cc843161da1834127b Author: Lee Rhodes <[email protected]> AuthorDate: Tue May 30 15:05:43 2023 -0700 Interim 1 towards KllItemsSketch - works --- .../datasketches/kll/KllDirectDoublesSketch.java | 4 - .../datasketches/kll/KllDirectFloatsSketch.java | 4 - .../apache/datasketches/kll/KllDoublesHelper.java | 90 ++--- .../apache/datasketches/kll/KllDoublesProxy.java | 83 +++++ .../apache/datasketches/kll/KllDoublesSketch.java | 28 +- .../apache/datasketches/kll/KllFloatsHelper.java | 47 +-- .../apache/datasketches/kll/KllFloatsProxy.java | 82 +++++ .../apache/datasketches/kll/KllFloatsSketch.java | 48 +-- .../apache/datasketches/kll/KllGenericProxy.java | 79 +++++ .../datasketches/kll/KllHeapDoublesSketch.java | 4 - .../datasketches/kll/KllHeapFloatsSketch.java | 10 +- .../org/apache/datasketches/kll/KllHelper.java | 373 ++++++++++++++------- .../apache/datasketches/kll/KllItemsSketch.java | 320 ++++++++++++++++++ .../apache/datasketches/kll/KllMemoryValidate.java | 2 +- .../apache/datasketches/kll/KllPreambleUtil.java | 1 + .../org/apache/datasketches/kll/KllSketch.java | 72 +--- .../apache/datasketches/quantiles/ItemsUnion.java | 2 +- .../apache/datasketches/quantiles/ItemsUtil.java | 4 - .../kll/KllDirectDoublesSketchTest.java | 3 +- .../kll/KllDirectFloatsSketchTest.java | 2 +- .../datasketches/kll/KllDoublesSketchTest.java | 17 +- .../datasketches/kll/KllFloatsSketchTest.java | 15 - .../datasketches/kll/KllMiscDirectFloatsTest.java | 2 +- .../datasketches/kll/KllMiscDoublesTest.java | 12 - .../apache/datasketches/kll/KllMiscFloatsTest.java | 12 - 25 files changed, 913 insertions(+), 403 deletions(-) diff --git a/src/main/java/org/apache/datasketches/kll/KllDirectDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDirectDoublesSketch.java index d9d89257..ba0baa4c 100644 --- a/src/main/java/org/apache/datasketches/kll/KllDirectDoublesSketch.java +++ b/src/main/java/org/apache/datasketches/kll/KllDirectDoublesSketch.java @@ -40,7 +40,6 @@ import static org.apache.datasketches.kll.KllPreambleUtil.setMemoryN; import static org.apache.datasketches.kll.KllPreambleUtil.setMemoryNumLevels; import static org.apache.datasketches.kll.KllPreambleUtil.setMemoryPreInts; import static org.apache.datasketches.kll.KllPreambleUtil.setMemorySerVer; -import static org.apache.datasketches.kll.KllSketch.Error.MUST_NOT_CALL; import static org.apache.datasketches.kll.KllSketch.Error.NOT_SINGLE_ITEM; import static org.apache.datasketches.kll.KllSketch.Error.TGT_IS_READ_ONLY; import static org.apache.datasketches.kll.KllSketch.Error.kllSketchThrow; @@ -128,9 +127,6 @@ class KllDirectDoublesSketch extends KllDoublesSketch { return wmem.getDouble(offset); } - @Override - float getFloatSingleItem() { kllSketchThrow(MUST_NOT_CALL); return Float.NaN; } - @Override int getM() { return getMemoryM(wmem); diff --git a/src/main/java/org/apache/datasketches/kll/KllDirectFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllDirectFloatsSketch.java index cbb6347b..c46d0b58 100644 --- a/src/main/java/org/apache/datasketches/kll/KllDirectFloatsSketch.java +++ b/src/main/java/org/apache/datasketches/kll/KllDirectFloatsSketch.java @@ -39,7 +39,6 @@ import static org.apache.datasketches.kll.KllPreambleUtil.setMemoryN; import static org.apache.datasketches.kll.KllPreambleUtil.setMemoryNumLevels; import static org.apache.datasketches.kll.KllPreambleUtil.setMemoryPreInts; import static org.apache.datasketches.kll.KllPreambleUtil.setMemorySerVer; -import static org.apache.datasketches.kll.KllSketch.Error.MUST_NOT_CALL; import static org.apache.datasketches.kll.KllSketch.Error.NOT_SINGLE_ITEM; import static org.apache.datasketches.kll.KllSketch.Error.TGT_IS_READ_ONLY; import static org.apache.datasketches.kll.KllSketch.Error.kllSketchThrow; @@ -110,9 +109,6 @@ class KllDirectFloatsSketch extends KllFloatsSketch { return getMemoryN(wmem); } - @Override - double getDoubleSingleItem() { kllSketchThrow(MUST_NOT_CALL); return Double.NaN; } - @Override //returns entire array including empty space at bottom float[] getFloatItemsArray() { final int capacityItems = levelsArr[getNumLevels()]; diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java index 236b4c44..c4b25fd2 100644 --- a/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java +++ b/src/main/java/org/apache/datasketches/kll/KllDoublesHelper.java @@ -35,39 +35,41 @@ import java.util.Random; final class KllDoublesHelper { //Called from KllSketch - static void mergeDoubleImpl(final KllDoublesSketch sketch, final KllSketch other) { - if (other.isEmpty()) { return; } - sketch.nullSortedView(); - final long finalN = sketch.getN() + other.getN(); - final int otherNumLevels = other.getNumLevels(); - final int[] otherLevelsArr = other.getLevelsArray(); + static void mergeDoubleImpl(final KllDoublesSketch mySketch, final KllSketch other) { + final KllDoublesSketch otherDblSk = (KllDoublesSketch) other; + if (otherDblSk.isEmpty()) { return; } + mySketch.nullSortedView(); + final long finalN = mySketch.getN() + otherDblSk.getN(); + final int otherNumLevels = otherDblSk.getNumLevels(); + final int[] otherLevelsArr = otherDblSk.getLevelsArray(); final double[] otherDoubleItemsArr; //capture my min & max, minK - final double myMin = sketch.isEmpty() ? Double.NaN : sketch.getMinDoubleItem(); - final double myMax = sketch.isEmpty() ? Double.NaN : sketch.getMaxDoubleItem(); - final int myMinK = sketch.getMinK(); + final double myMin = mySketch.isEmpty() ? Double.NaN : mySketch.getMinDoubleItem(); + final double myMax = mySketch.isEmpty() ? Double.NaN : mySketch.getMaxDoubleItem(); + final int myMinK = mySketch.getMinK(); //update this sketch with level0 items from the other sketch - if (other.isCompactSingleItem()) { - updateDouble(sketch, other.getDoubleSingleItem()); + + if (otherDblSk.isCompactSingleItem()) { + updateDouble(mySketch, otherDblSk.getDoubleSingleItem()); otherDoubleItemsArr = new double[0]; } else { - otherDoubleItemsArr = other.getDoubleItemsArray(); + otherDoubleItemsArr = otherDblSk.getDoubleItemsArray(); for (int i = otherLevelsArr[0]; i < otherLevelsArr[1]; i++) { - KllDoublesHelper.updateDouble(sketch, otherDoubleItemsArr[i]); + KllDoublesHelper.updateDouble(mySketch, otherDoubleItemsArr[i]); } } // after the level 0 update, we capture the state of levels and items arrays - final int myCurNumLevels = sketch.getNumLevels(); - final int[] myCurLevelsArr = sketch.getLevelsArray(); - final double[] myCurDoubleItemsArr = sketch.getDoubleItemsArray(); + final int myCurNumLevels = mySketch.getNumLevels(); + final int[] myCurLevelsArr = mySketch.getLevelsArray(); + final double[] myCurDoubleItemsArr = mySketch.getDoubleItemsArray(); int myNewNumLevels = myCurNumLevels; int[] myNewLevelsArr = myCurLevelsArr; double[] myNewDoubleItemsArr = myCurDoubleItemsArr; - if (otherNumLevels > 1 && !other.isCompactSingleItem()) { //now merge other levels if they exist - final int tmpSpaceNeeded = sketch.getNumRetained() + if (otherNumLevels > 1 && !otherDblSk.isCompactSingleItem()) { //now merge other levels if they exist + final int tmpSpaceNeeded = mySketch.getNumRetained() + KllHelper.getNumRetainedAboveLevelZero(otherNumLevels, otherLevelsArr); final double[] workbuf = new double[tmpSpaceNeeded]; final int ub = KllHelper.ubOnNumLevels(finalN); @@ -81,8 +83,8 @@ final class KllDoublesHelper { otherNumLevels, otherLevelsArr, otherDoubleItemsArr); // notice that workbuf is being used as both the input and output - final int[] result = generalDoublesCompress(sketch.getK(), sketch.getM(), provisionalNumLevels, - workbuf, worklevels, workbuf, outlevels, sketch.isLevelZeroSorted(), KllSketch.random); + final int[] result = generalDoublesCompress(mySketch.getK(), mySketch.getM(), provisionalNumLevels, + workbuf, worklevels, workbuf, outlevels, mySketch.isLevelZeroSorted(), KllSketch.random); final int targetItemCount = result[1]; //was finalCapacity. Max size given k, m, numLevels final int curItemCount = result[2]; //was finalPop @@ -113,28 +115,28 @@ final class KllDoublesHelper { } //MEMORY SPACE MANAGEMENT - if (sketch.updatableMemFormat) { - sketch.wmem = KllHelper.memorySpaceMgmt(sketch, myNewLevelsArr.length, myNewDoubleItemsArr.length); + if (mySketch.updatableMemFormat) { + mySketch.wmem = KllHelper.memorySpaceMgmt(mySketch, myNewLevelsArr.length, myNewDoubleItemsArr.length); } } //Update Preamble: - sketch.setN(finalN); - if (other.isEstimationMode()) { //otherwise the merge brings over exact items. - sketch.setMinK(min(myMinK, other.getMinK())); + mySketch.setN(finalN); + if (otherDblSk.isEstimationMode()) { //otherwise the merge brings over exact items. + mySketch.setMinK(min(myMinK, otherDblSk.getMinK())); } //Update numLevels, levelsArray, items - sketch.setNumLevels(myNewNumLevels); - sketch.setLevelsArray(myNewLevelsArr); - sketch.setDoubleItemsArray(myNewDoubleItemsArr); + mySketch.setNumLevels(myNewNumLevels); + mySketch.setLevelsArray(myNewLevelsArr); + mySketch.setDoubleItemsArray(myNewDoubleItemsArr); //Update min, max items - final double otherMin = other.getMinDoubleItem(); - final double otherMax = other.getMaxDoubleItem(); - sketch.setMinDoubleItem(resolveDoubleMinItem(myMin, otherMin)); - sketch.setMaxDoubleItem(resolveDoubleMaxItem(myMax, otherMax)); - assert KllHelper.sumTheSampleWeights(sketch.getNumLevels(), sketch.getLevelsArray()) == sketch.getN(); + final double otherMin = otherDblSk.getMinDoubleItem(); + final double otherMax = otherDblSk.getMaxDoubleItem(); + mySketch.setMinDoubleItem(resolveDoubleMinItem(myMin, otherMin)); + mySketch.setMaxDoubleItem(resolveDoubleMaxItem(myMax, otherMax)); + assert KllHelper.sumTheSampleWeights(mySketch.getNumLevels(), mySketch.getLevelsArray()) == mySketch.getN(); } //Called from KllHelper and this.generalDoublesCompress(...), this.populateDoubleWorkArrays(...) @@ -212,20 +214,20 @@ final class KllDoublesHelper { } //Called from KllDoublesSketch, this.mergeDoubleImpl(...) - static void updateDouble(final KllSketch sketch, final double item) { + static void updateDouble(final KllDoublesSketch dblSk, final double item) { if (Double.isNaN(item)) { return; } - final double prevMin = sketch.getMinDoubleItem(); - final double prevMax = sketch.getMaxDoubleItem(); - sketch.setMinDoubleItem(resolveDoubleMinItem(prevMin, item)); - sketch.setMaxDoubleItem(resolveDoubleMaxItem(prevMax, item)); - if (sketch.getLevelsArray()[0] == 0) { KllHelper.compressWhileUpdatingSketch(sketch); } - final int myLevelsArrAtZero = sketch.getLevelsArray()[0]; //LevelsArr could be expanded - sketch.incN(); - sketch.setLevelZeroSorted(false); + final double prevMin = dblSk.getMinDoubleItem(); + final double prevMax = dblSk.getMaxDoubleItem(); + dblSk.setMinDoubleItem(resolveDoubleMinItem(prevMin, item)); + dblSk.setMaxDoubleItem(resolveDoubleMaxItem(prevMax, item)); + if (dblSk.getLevelsArray()[0] == 0) { KllHelper.compressWhileUpdatingSketch(dblSk); } + final int myLevelsArrAtZero = dblSk.getLevelsArray()[0]; //LevelsArr could be expanded + dblSk.incN(); + dblSk.setLevelZeroSorted(false); final int nextPos = myLevelsArrAtZero - 1; assert myLevelsArrAtZero >= 0; - sketch.setLevelsArrayAt(0, nextPos); - sketch.setDoubleItemsArrayAt(nextPos, item); + dblSk.setLevelsArrayAt(0, nextPos); + dblSk.setDoubleItemsArrayAt(nextPos, item); } /** diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesProxy.java b/src/main/java/org/apache/datasketches/kll/KllDoublesProxy.java new file mode 100644 index 00000000..c74482d2 --- /dev/null +++ b/src/main/java/org/apache/datasketches/kll/KllDoublesProxy.java @@ -0,0 +1,83 @@ +/* + * 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.kll; + +import static org.apache.datasketches.kll.KllSketch.Error.TGT_IS_READ_ONLY; +import static org.apache.datasketches.kll.KllSketch.Error.kllSketchThrow; + +import org.apache.datasketches.memory.MemoryRequestServer; +import org.apache.datasketches.memory.WritableMemory; + +abstract class KllDoublesProxy extends KllSketch { + + KllDoublesProxy(final WritableMemory wmem, final MemoryRequestServer memReqSvr) { + super(SketchType.DOUBLES_SKETCH, wmem, memReqSvr); + } + + /** + * @return full size of internal items array including garbage. + */ + abstract double[] getDoubleItemsArray(); + + abstract double getDoubleSingleItem(); + + abstract double getMaxDoubleItem(); + + abstract double getMinDoubleItem(); + + abstract void setDoubleItemsArray(double[] doubleItems); + + abstract void setDoubleItemsArrayAt(int index, double item); + + abstract void setMaxDoubleItem(double item); + + abstract void setMinDoubleItem(double item); + + /** + * Merges another sketch into this one. + * Attempting to merge a KllDoublesSketch with a KllFloatsSketch will + * throw an exception. + * @param other sketch to merge into this one + */ + public final void merge(final KllDoublesSketch other) { + if (readOnly) { kllSketchThrow(TGT_IS_READ_ONLY); } + KllDoublesHelper.mergeDoubleImpl((KllDoublesSketch)this, other); + } + + + /** + * {@inheritDoc} + * <p>The parameter <i>k</i> will not change.</p> + */ + @Override + public final void reset() { + if (readOnly) { kllSketchThrow(TGT_IS_READ_ONLY); } + final int k = getK(); + setN(0); + setMinK(k); + setNumLevels(1); + setLevelZeroSorted(false); + setLevelsArray(new int[] {k, k}); + setMinDoubleItem(Double.NaN); + setMaxDoubleItem(Double.NaN); + setDoubleItemsArray(new double[k]); + } + +} diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java index dbba6d1d..c21a374c 100644 --- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java +++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java @@ -23,7 +23,6 @@ import static java.lang.Math.max; import static java.lang.Math.min; import static org.apache.datasketches.kll.KllPreambleUtil.getMemoryUpdatableFormatFlag; import static org.apache.datasketches.kll.KllSketch.Error.MUST_NOT_BE_UPDATABLE_FORMAT; -import static org.apache.datasketches.kll.KllSketch.Error.MUST_NOT_CALL; import static org.apache.datasketches.kll.KllSketch.Error.TGT_IS_READ_ONLY; import static org.apache.datasketches.kll.KllSketch.Error.kllSketchThrow; import static org.apache.datasketches.quantilescommon.QuantilesUtil.THROWS_EMPTY; @@ -45,11 +44,11 @@ import org.apache.datasketches.quantilescommon.QuantilesDoublesSketchIterator; * * @see org.apache.datasketches.kll.KllSketch */ -public abstract class KllDoublesSketch extends KllSketch implements QuantilesDoublesAPI { +public abstract class KllDoublesSketch extends KllDoublesProxy implements QuantilesDoublesAPI { private KllDoublesSketchSortedView kllDoublesSV = null; KllDoublesSketch(final WritableMemory wmem, final MemoryRequestServer memReqSvr) { - super(SketchType.DOUBLES_SKETCH, wmem, memReqSvr); + super(wmem, memReqSvr); } /** @@ -83,7 +82,7 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou * @param memReqSvr the given MemoryRequestServer to request a larger WritableMemory * @return a new direct instance of this sketch */ - public static KllDoublesSketch newDirectInstance( + public static KllDirectDoublesSketch newDirectInstance( final int k, final WritableMemory dstMem, final MemoryRequestServer memReqSvr) { @@ -314,27 +313,6 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou void nullSortedView() { kllDoublesSV = null; } - @Override //Artifact of inheritance - float[] getFloatItemsArray() { kllSketchThrow(MUST_NOT_CALL); return null; } - - @Override //Artifact of inheritance - float getMaxFloatItem() { kllSketchThrow(MUST_NOT_CALL); return Float.NaN; } - - @Override //Artifact of inheritance - float getMinFloatItem() { kllSketchThrow(MUST_NOT_CALL); return Float.NaN; } - - @Override //Artifact of inheritance - void setFloatItemsArray(final float[] floatItems) { kllSketchThrow(MUST_NOT_CALL); } - - @Override //Artifact of inheritance - void setFloatItemsArrayAt(final int index, final float item) { kllSketchThrow(MUST_NOT_CALL); } - - @Override //Artifact of inheritance - void setMaxFloatItem(final float item) { kllSketchThrow(MUST_NOT_CALL); } - - @Override //Artifact of inheritance - void setMinFloatItem(final float item) { kllSketchThrow(MUST_NOT_CALL); } - private final void refreshSortedView() { kllDoublesSV = (kllDoublesSV == null) ? new KllDoublesSketchSortedView(this) : kllDoublesSV; } diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java index 321e1527..42a08e8c 100644 --- a/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java +++ b/src/main/java/org/apache/datasketches/kll/KllFloatsHelper.java @@ -36,11 +36,12 @@ final class KllFloatsHelper { //Called from KllSketch static void mergeFloatImpl(final KllFloatsSketch sketch, final KllSketch other) { - if (other.isEmpty()) { return; } + final KllFloatsSketch otherFltSk = (KllFloatsSketch) other; + if (otherFltSk.isEmpty()) { return; } sketch.nullSortedView(); - final long finalN = sketch.getN() + other.getN(); - final int otherNumLevels = other.getNumLevels(); - final int[] otherLevelsArr = other.getLevelsArray(); + final long finalN = sketch.getN() + otherFltSk.getN(); + final int otherNumLevels = otherFltSk.getNumLevels(); + final int[] otherLevelsArr = otherFltSk.getLevelsArray(); final float[] otherFloatItemsArr; //capture my min & max, minK final float myMin = sketch.isEmpty() ? Float.NaN : sketch.getMinFloatItem(); @@ -48,11 +49,11 @@ final class KllFloatsHelper { final int myMinK = sketch.getMinK(); //update this sketch with level0 items from the other sketch - if (other.isCompactSingleItem()) { - updateFloat(sketch, other.getFloatSingleItem()); + if (otherFltSk.isCompactSingleItem()) { + updateFloat(sketch, otherFltSk.getFloatSingleItem()); otherFloatItemsArr = new float[0]; } else { - otherFloatItemsArr = other.getFloatItemsArray(); + otherFloatItemsArr = otherFltSk.getFloatItemsArray(); for (int i = otherLevelsArr[0]; i < otherLevelsArr[1]; i++) { updateFloat(sketch, otherFloatItemsArr[i]); } @@ -66,7 +67,7 @@ final class KllFloatsHelper { int[] myNewLevelsArr = myCurLevelsArr; float[] myNewFloatItemsArr = myCurFloatItemsArr; - if (otherNumLevels > 1 && !other.isCompactSingleItem()) { //now merge higher levels if they exist + if (otherNumLevels > 1 && !otherFltSk.isCompactSingleItem()) { //now merge higher levels if they exist final int tmpSpaceNeeded = sketch.getNumRetained() + KllHelper.getNumRetainedAboveLevelZero(otherNumLevels, otherLevelsArr); final float[] workbuf = new float[tmpSpaceNeeded]; @@ -120,8 +121,8 @@ final class KllFloatsHelper { //Update Preamble: sketch.setN(finalN); - if (other.isEstimationMode()) { //otherwise the merge brings over exact items. - sketch.setMinK(min(myMinK, other.getMinK())); + if (otherFltSk.isEstimationMode()) { //otherwise the merge brings over exact items. + sketch.setMinK(min(myMinK, otherFltSk.getMinK())); } //Update numLevels, levelsArray, items @@ -130,8 +131,8 @@ final class KllFloatsHelper { sketch.setFloatItemsArray(myNewFloatItemsArr); //Update min, max items - final float otherMin = other.getMinFloatItem(); - final float otherMax = other.getMaxFloatItem(); + final float otherMin = otherFltSk.getMinFloatItem(); + final float otherMax = otherFltSk.getMaxFloatItem(); sketch.setMinFloatItem(resolveFloatMinItem(myMin, otherMin)); sketch.setMaxFloatItem(resolveFloatMaxItem(myMax, otherMax)); assert KllHelper.sumTheSampleWeights(sketch.getNumLevels(), sketch.getLevelsArray()) == sketch.getN(); @@ -212,20 +213,20 @@ final class KllFloatsHelper { } //Called from KllFloatsSketch, this.mergeFloatImpl(...) - static void updateFloat(final KllSketch sketch, final float item) { + static void updateFloat(final KllFloatsSketch fltSk, final float item) { if (Float.isNaN(item)) { return; } - final float prevMin = sketch.getMinFloatItem(); - final float prevMax = sketch.getMaxFloatItem(); - sketch.setMinFloatItem(resolveFloatMinItem(prevMin, item)); - sketch.setMaxFloatItem(resolveFloatMaxItem(prevMax, item)); - if (sketch.getLevelsArray()[0] == 0) { KllHelper.compressWhileUpdatingSketch(sketch); } - final int myLevelsArrAtZero = sketch.getLevelsArray()[0]; //LevelsArr could be expanded - sketch.incN(); - sketch.setLevelZeroSorted(false); + final float prevMin = fltSk.getMinFloatItem(); + final float prevMax = fltSk.getMaxFloatItem(); + fltSk.setMinFloatItem(resolveFloatMinItem(prevMin, item)); + fltSk.setMaxFloatItem(resolveFloatMaxItem(prevMax, item)); + if (fltSk.getLevelsArray()[0] == 0) { KllHelper.compressWhileUpdatingSketch(fltSk); } + final int myLevelsArrAtZero = fltSk.getLevelsArray()[0]; //LevelsArr could be expanded + fltSk.incN(); + fltSk.setLevelZeroSorted(false); final int nextPos = myLevelsArrAtZero - 1; assert myLevelsArrAtZero >= 0; - sketch.setLevelsArrayAt(0, nextPos); - sketch.setFloatItemsArrayAt(nextPos, item); + fltSk.setLevelsArrayAt(0, nextPos); + fltSk.setFloatItemsArrayAt(nextPos, item); } /** diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsProxy.java b/src/main/java/org/apache/datasketches/kll/KllFloatsProxy.java new file mode 100644 index 00000000..41eba830 --- /dev/null +++ b/src/main/java/org/apache/datasketches/kll/KllFloatsProxy.java @@ -0,0 +1,82 @@ +/* + * 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.kll; + +import static org.apache.datasketches.kll.KllSketch.Error.TGT_IS_READ_ONLY; +import static org.apache.datasketches.kll.KllSketch.Error.kllSketchThrow; + +import org.apache.datasketches.memory.MemoryRequestServer; +import org.apache.datasketches.memory.WritableMemory; + +abstract class KllFloatsProxy extends KllSketch { + + KllFloatsProxy(final WritableMemory wmem, final MemoryRequestServer memReqSvr) { + super(SketchType.FLOATS_SKETCH, wmem, memReqSvr); + } + + /** + * @return full size of internal items array including garbage. + */ + abstract float[] getFloatItemsArray(); + + abstract float getFloatSingleItem(); + + abstract float getMaxFloatItem(); + + abstract float getMinFloatItem(); + + abstract void setFloatItemsArray(float[] floatItems); + + abstract void setFloatItemsArrayAt(int index, float item); + + abstract void setMaxFloatItem(float item); + + abstract void setMinFloatItem(float item); + + /** + * Merges another sketch into this one. + * Attempting to merge a KllDoublesSketch with a KllFloatsSketch will + * throw an exception. + * @param other sketch to merge into this one + */ + public final void merge(final KllFloatsSketch other) { + if (readOnly) { kllSketchThrow(TGT_IS_READ_ONLY); } + KllFloatsHelper.mergeFloatImpl((KllFloatsSketch)this, other); + } + + /** + * {@inheritDoc} + * <p>The parameter <i>k</i> will not change.</p> + */ + @Override + public final void reset() { + if (readOnly) { kllSketchThrow(TGT_IS_READ_ONLY); } + final int k = getK(); + setN(0); + setMinK(k); + setNumLevels(1); + setLevelZeroSorted(false); + setLevelsArray(new int[] {k, k}); + setMinFloatItem(Float.NaN); + setMaxFloatItem(Float.NaN); + setFloatItemsArray(new float[k]); + } + +} diff --git a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java index eed0e4fe..e72a7f79 100644 --- a/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java +++ b/src/main/java/org/apache/datasketches/kll/KllFloatsSketch.java @@ -23,7 +23,6 @@ import static java.lang.Math.max; import static java.lang.Math.min; import static org.apache.datasketches.kll.KllPreambleUtil.getMemoryUpdatableFormatFlag; import static org.apache.datasketches.kll.KllSketch.Error.MUST_NOT_BE_UPDATABLE_FORMAT; -import static org.apache.datasketches.kll.KllSketch.Error.MUST_NOT_CALL; import static org.apache.datasketches.kll.KllSketch.Error.TGT_IS_READ_ONLY; import static org.apache.datasketches.kll.KllSketch.Error.kllSketchThrow; import static org.apache.datasketches.quantilescommon.QuantilesUtil.THROWS_EMPTY; @@ -45,22 +44,11 @@ import org.apache.datasketches.quantilescommon.QuantilesFloatsSketchIterator; * * @see org.apache.datasketches.kll.KllSketch */ -public abstract class KllFloatsSketch extends KllSketch implements QuantilesFloatsAPI { +public abstract class KllFloatsSketch extends KllFloatsProxy implements QuantilesFloatsAPI { private KllFloatsSketchSortedView kllFloatsSV = null; KllFloatsSketch(final WritableMemory wmem, final MemoryRequestServer memReqSvr) { - super(SketchType.FLOATS_SKETCH, wmem, memReqSvr); - } - - /** - * Returns upper bound on the serialized size of a KllFloatsSketch given the following parameters. - * @param k parameter that controls size of the sketch and accuracy of estimates - * @param n stream length - * @param updatableMemoryFormat true if updatable Memory format, otherwise the standard compact format. - * @return upper bound on the serialized size of a KllSketch. - */ - public static int getMaxSerializedSizeBytes(final int k, final long n, final boolean updatableMemoryFormat) { - return getMaxSerializedSizeBytes(k, n, SketchType.FLOATS_SKETCH, updatableMemoryFormat); + super(wmem, memReqSvr); } /** @@ -169,6 +157,17 @@ public abstract class KllFloatsSketch extends KllSketch implements QuantilesFloa } } + /** + * Returns upper bound on the serialized size of a KllFloatsSketch given the following parameters. + * @param k parameter that controls size of the sketch and accuracy of estimates + * @param n stream length + * @param updatableMemoryFormat true if updatable Memory format, otherwise the standard compact format. + * @return upper bound on the serialized size of a KllSketch. + */ + public static int getMaxSerializedSizeBytes(final int k, final long n, final boolean updatableMemoryFormat) { + return getMaxSerializedSizeBytes(k, n, SketchType.FLOATS_SKETCH, updatableMemoryFormat); + } + @Override public double[] getCDF(final float[] splitPoints, final QuantileSearchCriteria searchCrit) { if (isEmpty()) { throw new IllegalArgumentException(THROWS_EMPTY); } @@ -314,27 +313,6 @@ public abstract class KllFloatsSketch extends KllSketch implements QuantilesFloa void nullSortedView() { kllFloatsSV = null; } - @Override //Artifact of inheritance - double[] getDoubleItemsArray() { kllSketchThrow(MUST_NOT_CALL); return null; } - - @Override //Artifact of inheritance - double getMaxDoubleItem() { kllSketchThrow(MUST_NOT_CALL); return Double.NaN; } - - @Override //Artifact of inheritance - double getMinDoubleItem() { kllSketchThrow(MUST_NOT_CALL); return Double.NaN; } - - @Override //Artifact of inheritance - void setDoubleItemsArray(final double[] doubleItems) { kllSketchThrow(MUST_NOT_CALL); } - - @Override //Artifact of inheritance - void setDoubleItemsArrayAt(final int index, final double item) { kllSketchThrow(MUST_NOT_CALL); } - - @Override //Artifact of inheritance - void setMaxDoubleItem(final double item) { kllSketchThrow(MUST_NOT_CALL); } - - @Override //Artifact of inheritance - void setMinDoubleItem(final double item) { kllSketchThrow(MUST_NOT_CALL); } - private final void refreshSortedView() { kllFloatsSV = (kllFloatsSV == null) ? new KllFloatsSketchSortedView(this) : kllFloatsSV; } diff --git a/src/main/java/org/apache/datasketches/kll/KllGenericProxy.java b/src/main/java/org/apache/datasketches/kll/KllGenericProxy.java new file mode 100644 index 00000000..d424e2c8 --- /dev/null +++ b/src/main/java/org/apache/datasketches/kll/KllGenericProxy.java @@ -0,0 +1,79 @@ +/* + * 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.kll; + +import static org.apache.datasketches.kll.KllSketch.Error.TGT_IS_READ_ONLY; +import static org.apache.datasketches.kll.KllSketch.Error.kllSketchThrow; + +abstract class KllGenericProxy<T> extends KllSketch { + + KllGenericProxy() { + super(SketchType.ITEMS_SKETCH, null, null); + } + + /** + * @return full size of internal items array including garbage. + */ + abstract T[] getItemsArray(); + + abstract T getSingleItem(); + + abstract T getMaxItem(); + + abstract T getMinItem(); + + abstract void setItemsArray(T[] Items); + + abstract void setItemsArrayAt(int index, T item); + + abstract void setMaxItem(T item); + + abstract void setMinItem(T item); + + /** + * Merges another sketch into this one. + * Attempting to merge a KllDoublesSketch with a KllFloatsSketch will + * throw an exception. + * @param other sketch to merge into this one + */ + public final void merge(final KllItemsSketch<T> other) { + if (readOnly) { kllSketchThrow(TGT_IS_READ_ONLY); } + //KllItemsHelper.mergeItemImpl((KllItemsSketch)this, other); //TODO + } + + /** + * {@inheritDoc} + * <p>The parameter <i>k</i> will not change.</p> + */ + @SuppressWarnings("unchecked") + @Override + public final void reset() { + if (readOnly) { kllSketchThrow(TGT_IS_READ_ONLY); } + final int k = getK(); + setN(0); + setMinK(k); + setNumLevels(1); + setLevelZeroSorted(false); + setLevelsArray(new int[] {k, k}); + setMinItem(null); + setMaxItem(null); + setItemsArray((T[])(new Object[k])); + } +} diff --git a/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java index 1882b0e1..5fa1d18a 100644 --- a/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java +++ b/src/main/java/org/apache/datasketches/kll/KllHeapDoublesSketch.java @@ -21,7 +21,6 @@ package org.apache.datasketches.kll; import static org.apache.datasketches.kll.KllPreambleUtil.DATA_START_ADR; import static org.apache.datasketches.kll.KllPreambleUtil.DATA_START_ADR_SINGLE_ITEM; -import static org.apache.datasketches.kll.KllSketch.Error.MUST_NOT_CALL; import static org.apache.datasketches.kll.KllSketch.Error.NOT_SINGLE_ITEM; import static org.apache.datasketches.kll.KllSketch.Error.SRC_MUST_BE_DOUBLE; import static org.apache.datasketches.kll.KllSketch.Error.kllSketchThrow; @@ -142,9 +141,6 @@ final class KllHeapDoublesSketch extends KllDoublesSketch { return quantiles_[k_ - 1]; } - @Override - float getFloatSingleItem() { kllSketchThrow(MUST_NOT_CALL); return Float.NaN; } - @Override int getM() { return m_; } diff --git a/src/main/java/org/apache/datasketches/kll/KllHeapFloatsSketch.java b/src/main/java/org/apache/datasketches/kll/KllHeapFloatsSketch.java index f1ebb91f..4bc383bb 100644 --- a/src/main/java/org/apache/datasketches/kll/KllHeapFloatsSketch.java +++ b/src/main/java/org/apache/datasketches/kll/KllHeapFloatsSketch.java @@ -21,7 +21,6 @@ package org.apache.datasketches.kll; import static org.apache.datasketches.kll.KllPreambleUtil.DATA_START_ADR; import static org.apache.datasketches.kll.KllPreambleUtil.DATA_START_ADR_SINGLE_ITEM; -import static org.apache.datasketches.kll.KllSketch.Error.MUST_NOT_CALL; import static org.apache.datasketches.kll.KllSketch.Error.NOT_SINGLE_ITEM; import static org.apache.datasketches.kll.KllSketch.Error.SRC_MUST_BE_FLOAT; import static org.apache.datasketches.kll.KllSketch.Error.kllSketchThrow; @@ -39,9 +38,9 @@ import org.apache.datasketches.memory.Memory; * @author Lee Rhodes, Kevin Lang */ final class KllHeapFloatsSketch extends KllFloatsSketch { - private final int k_; // configured size of K. - private final int m_; // configured size of M. - private long n_; // number of items input into this sketch. + private final int k_; // configured size of K. + private final int m_; // configured size of M. + private long n_; // number of items input into this sketch. private int minK_; // dynamic minK for error estimation after merging with different k. private boolean isLevelZeroSorted_; private float minFloatItem_; @@ -133,9 +132,6 @@ final class KllHeapFloatsSketch extends KllFloatsSketch { @Override public long getN() { return n_; } - @Override - double getDoubleSingleItem() { kllSketchThrow(MUST_NOT_CALL); return Double.NaN; } - @Override float[] getFloatItemsArray() { return floatItems_; } diff --git a/src/main/java/org/apache/datasketches/kll/KllHelper.java b/src/main/java/org/apache/datasketches/kll/KllHelper.java index d27760f5..506836ca 100644 --- a/src/main/java/org/apache/datasketches/kll/KllHelper.java +++ b/src/main/java/org/apache/datasketches/kll/KllHelper.java @@ -33,14 +33,19 @@ import static org.apache.datasketches.kll.KllPreambleUtil.DATA_START_ADR; import static org.apache.datasketches.kll.KllPreambleUtil.DATA_START_ADR_SINGLE_ITEM; import static org.apache.datasketches.kll.KllPreambleUtil.DOUBLES_SKETCH_BIT_MASK; import static org.apache.datasketches.kll.KllPreambleUtil.EMPTY_BIT_MASK; +import static org.apache.datasketches.kll.KllPreambleUtil.FAMILY_BYTE_ADR; import static org.apache.datasketches.kll.KllPreambleUtil.FLAGS_BYTE_ADR; +import static org.apache.datasketches.kll.KllPreambleUtil.ITEMS_SKETCH_BIT_MASK; import static org.apache.datasketches.kll.KllPreambleUtil.KLL_FAMILY; import static org.apache.datasketches.kll.KllPreambleUtil.K_SHORT_ADR; +import static org.apache.datasketches.kll.KllPreambleUtil.M_BYTE_ADR; +import static org.apache.datasketches.kll.KllPreambleUtil.PREAMBLE_INTS_BYTE_ADR; import static org.apache.datasketches.kll.KllPreambleUtil.PREAMBLE_INTS_EMPTY_SINGLE; import static org.apache.datasketches.kll.KllPreambleUtil.PREAMBLE_INTS_FULL; import static org.apache.datasketches.kll.KllPreambleUtil.SERIAL_VERSION_EMPTY_FULL; import static org.apache.datasketches.kll.KllPreambleUtil.SERIAL_VERSION_SINGLE; import static org.apache.datasketches.kll.KllPreambleUtil.SERIAL_VERSION_UPDATABLE; +import static org.apache.datasketches.kll.KllPreambleUtil.SER_VER_BYTE_ADR; import static org.apache.datasketches.kll.KllPreambleUtil.SINGLE_ITEM_BIT_MASK; import static org.apache.datasketches.kll.KllPreambleUtil.UPDATABLE_BIT_MASK; import static org.apache.datasketches.kll.KllPreambleUtil.setMemoryDoubleSketchFlag; @@ -57,6 +62,8 @@ import static org.apache.datasketches.kll.KllPreambleUtil.setMemorySerVer; import static org.apache.datasketches.kll.KllPreambleUtil.setMemorySingleItemFlag; import static org.apache.datasketches.kll.KllPreambleUtil.setMemoryUpdatableFlag; import static org.apache.datasketches.kll.KllSketch.SketchType.DOUBLES_SKETCH; +import static org.apache.datasketches.kll.KllSketch.SketchType.FLOATS_SKETCH; +import static org.apache.datasketches.kll.KllSketch.SketchType.ITEMS_SKETCH; import java.util.Arrays; @@ -140,6 +147,7 @@ final class KllHelper { * @param sketch the current sketch */ static void compressWhileUpdatingSketch(final KllSketch sketch) { + final SketchType sketchType = sketch.sketchType; final int level = findLevelToCompact(sketch.getK(), sketch.getM(), sketch.getNumLevels(), sketch.getLevelsArray()); if (level == sketch.getNumLevels() - 1) { @@ -161,8 +169,9 @@ final class KllHelper { final int adjPop = oddPop ? rawPop - 1 : rawPop; final int halfAdjPop = adjPop / 2; - if (sketch.sketchType == DOUBLES_SKETCH) { - final double[] myDoubleItemsArr = sketch.getDoubleItemsArray(); + if (sketchType == DOUBLES_SKETCH) { + final KllDoublesSketch dblSk = (KllDoublesSketch) sketch; + final double[] myDoubleItemsArr = dblSk.getDoubleItemsArray(); if (level == 0) { // level zero might not be sorted, so we must sort it if we wish to compact it Arrays.sort(myDoubleItemsArr, adjBeg, adjBeg + adjPop); } @@ -177,13 +186,13 @@ final class KllHelper { } int newIndex = myLevelsArr[level + 1] - halfAdjPop; // adjust boundaries of the level above - sketch.setLevelsArrayAt(level + 1, newIndex); + dblSk.setLevelsArrayAt(level + 1, newIndex); if (oddPop) { - sketch.setLevelsArrayAt(level, myLevelsArr[level + 1] - 1); // the current level now contains one item + dblSk.setLevelsArrayAt(level, myLevelsArr[level + 1] - 1); // the current level now contains one item myDoubleItemsArr[myLevelsArr[level]] = myDoubleItemsArr[rawBeg]; // namely this leftover guy } else { - sketch.setLevelsArrayAt(level, myLevelsArr[level + 1]); // the current level is now empty + dblSk.setLevelsArrayAt(level, myLevelsArr[level + 1]); // the current level is now empty } // verify that we freed up halfAdjPop array slots just below the current level @@ -197,12 +206,13 @@ final class KllHelper { } for (int lvl = 0; lvl < level; lvl++) { newIndex = myLevelsArr[lvl] + halfAdjPop; //adjust boundary - sketch.setLevelsArrayAt(lvl, newIndex); + dblSk.setLevelsArrayAt(lvl, newIndex); } - sketch.setDoubleItemsArray(myDoubleItemsArr); + dblSk.setDoubleItemsArray(myDoubleItemsArr); } - else { //Float sketch - final float[] myFloatItemsArr = sketch.getFloatItemsArray(); + else if (sketchType == FLOATS_SKETCH) { + final KllFloatsSketch fltSk = (KllFloatsSketch) sketch; + final float[] myFloatItemsArr = fltSk.getFloatItemsArray(); if (level == 0) { // level zero might not be sorted, so we must sort it if we wish to compact it Arrays.sort(myFloatItemsArr, adjBeg, adjBeg + adjPop); } @@ -217,13 +227,13 @@ final class KllHelper { } int newIndex = myLevelsArr[level + 1] - halfAdjPop; // adjust boundaries of the level above - sketch.setLevelsArrayAt(level + 1, newIndex); + fltSk.setLevelsArrayAt(level + 1, newIndex); if (oddPop) { - sketch.setLevelsArrayAt(level, myLevelsArr[level + 1] - 1); // the current level now contains one item + fltSk.setLevelsArrayAt(level, myLevelsArr[level + 1] - 1); // the current level now contains one item myFloatItemsArr[myLevelsArr[level]] = myFloatItemsArr[rawBeg]; // namely this leftover guy } else { - sketch.setLevelsArrayAt(level, myLevelsArr[level + 1]); // the current level is now empty + fltSk.setLevelsArrayAt(level, myLevelsArr[level + 1]); // the current level is now empty } // verify that we freed up halfAdjPop array slots just below the current level @@ -237,9 +247,11 @@ final class KllHelper { } for (int lvl = 0; lvl < level; lvl++) { newIndex = myLevelsArr[lvl] + halfAdjPop; //adjust boundary - sketch.setLevelsArrayAt(lvl, newIndex); + fltSk.setLevelsArrayAt(lvl, newIndex); } - sketch.setFloatItemsArray(myFloatItemsArr); + fltSk.setFloatItemsArray(myFloatItemsArr); + } else { + //ITEMS_SKETCH //TODO } } @@ -347,7 +359,8 @@ final class KllHelper { println("Given N : " + gStats.givenN); printf("%10s %10s %20s %13s %15s\n", "NumLevels", "MaxItems", "MaxN", "CompactBytes", "UpdatableBytes"); } - final int typeBytes = (sketchType == DOUBLES_SKETCH) ? Double.BYTES : Float.BYTES; + final int typeBytes = sketchType == DOUBLES_SKETCH ? Double.BYTES + : sketchType == FLOATS_SKETCH ? Float.BYTES : 0; //TODO do { gStats.numLevels++; // lvlStats = getFinalSketchStatsAtNumLevels(gStats.k, gStats.m, gStats.numLevels, false); @@ -460,8 +473,8 @@ final class KllHelper { final int newItemsArrLen) { final KllSketch.SketchType sketchType = sketch.sketchType; final WritableMemory oldWmem = sketch.wmem; - final int typeBytes = (sketchType == DOUBLES_SKETCH) ? Double.BYTES : Float.BYTES; - + final int typeBytes = sketchType == DOUBLES_SKETCH ? Double.BYTES + : sketchType == FLOATS_SKETCH ? Float.BYTES : 0; //TODO final int requiredSketchBytes = DATA_START_ADR + newLevelsArrLen * Integer.BYTES + 2 * typeBytes @@ -479,57 +492,90 @@ final class KllHelper { return newWmem; } - static String outputData(final boolean doubleType, final int numLevels, final int[] levelsArr, - final float[] floatItemsArr, final double[] doubleItemsArr) { + private static String outputDoublesData(final int numLevels, final int[] levelsArr, final double[] doubleItemsArr) { final StringBuilder sb = new StringBuilder(); sb.append("### KLL items data {index, item}:").append(Util.LS); if (levelsArr[0] > 0) { sb.append(" Garbage:" + Util.LS); - if (doubleType) { - for (int i = 0; i < levelsArr[0]; i++) { - sb.append(" ").append(i + ", ").append(doubleItemsArr[i]).append(Util.LS); - } - } else { - for (int i = 0; i < levelsArr[0]; i++) { - sb.append(" ").append(i + ", ").append(floatItemsArr[i]).append(Util.LS); - } + for (int i = 0; i < levelsArr[0]; i++) { + sb.append(" ").append(i + ", ").append(doubleItemsArr[i]).append(Util.LS); } } int level = 0; - if (doubleType) { - while (level < numLevels) { - final int fromIndex = levelsArr[level]; - final int toIndex = levelsArr[level + 1]; // exclusive - if (fromIndex < toIndex) { - sb.append(" level[").append(level).append("]: offset: " + levelsArr[level] + " wt: " + (1 << level)); - sb.append(Util.LS); - } + while (level < numLevels) { + final int fromIndex = levelsArr[level]; + final int toIndex = levelsArr[level + 1]; // exclusive + if (fromIndex < toIndex) { + sb.append(" level[").append(level).append("]: offset: " + levelsArr[level] + " wt: " + (1 << level)); + sb.append(Util.LS); + } - for (int i = fromIndex; i < toIndex; i++) { - sb.append(" ").append(i + ", ").append(doubleItemsArr[i]).append(Util.LS); - } - level++; + for (int i = fromIndex; i < toIndex; i++) { + sb.append(" ").append(i + ", ").append(doubleItemsArr[i]).append(Util.LS); } + level++; } - else { - while (level < numLevels) { - final int fromIndex = levelsArr[level]; - final int toIndex = levelsArr[level + 1]; // exclusive - if (fromIndex <= toIndex) { - sb.append(" level[").append(level).append("]: offset: " + levelsArr[level] + " wt: " + (1 << level)); - sb.append(Util.LS); - } + sb.append(" level[" + level + "]: offset: " + levelsArr[level] + " (Exclusive)"); + sb.append(Util.LS); + sb.append("### End items data").append(Util.LS); + return sb.toString(); + } - for (int i = fromIndex; i < toIndex; i++) { - sb.append(" ").append(i + ", ").append(floatItemsArr[i]).append(Util.LS); - } - level++; + private static String outputFloatsData(final int numLevels, final int[] levelsArr, final float[] floatsItemsArr) { + final StringBuilder sb = new StringBuilder(); + sb.append("### KLL items data {index, item}:").append(Util.LS); + if (levelsArr[0] > 0) { + sb.append(" Garbage:" + Util.LS); + for (int i = 0; i < levelsArr[0]; i++) { + sb.append(" ").append(i + ", ").append(floatsItemsArr[i]).append(Util.LS); } } + int level = 0; + while (level < numLevels) { + final int fromIndex = levelsArr[level]; + final int toIndex = levelsArr[level + 1]; // exclusive + if (fromIndex < toIndex) { + sb.append(" level[").append(level).append("]: offset: " + levelsArr[level] + " wt: " + (1 << level)); + sb.append(Util.LS); + } + + for (int i = fromIndex; i < toIndex; i++) { + sb.append(" ").append(i + ", ").append(floatsItemsArr[i]).append(Util.LS); + } + level++; + } sb.append(" level[" + level + "]: offset: " + levelsArr[level] + " (Exclusive)"); sb.append(Util.LS); sb.append("### End items data").append(Util.LS); + return sb.toString(); + } + private static String outputGenericItemsData(final int numLevels, final int[] levelsArr, final Object[] itemsArr) { + final StringBuilder sb = new StringBuilder(); + sb.append("### KLL items data {index, item}:").append(Util.LS); + if (levelsArr[0] > 0) { + sb.append(" Garbage:" + Util.LS); + for (int i = 0; i < levelsArr[0]; i++) { + sb.append(" ").append(i + ", ").append(itemsArr[i].toString()).append(Util.LS); + } + } + int level = 0; + while (level < numLevels) { + final int fromIndex = levelsArr[level]; + final int toIndex = levelsArr[level + 1]; // exclusive + if (fromIndex < toIndex) { + sb.append(" level[").append(level).append("]: offset: " + levelsArr[level] + " wt: " + (1 << level)); + sb.append(Util.LS); + } + + for (int i = fromIndex; i < toIndex; i++) { + sb.append(" ").append(i + ", ").append(itemsArr[i].toString()).append(Util.LS); + } + level++; + } + sb.append(" level[" + level + "]: offset: " + levelsArr[level] + " (Exclusive)"); + sb.append(Util.LS); + sb.append("### End items data").append(Util.LS); return sb.toString(); } @@ -562,20 +608,24 @@ final class KllHelper { static byte[] toCompactByteArrayImpl(final KllSketch sketch) { if (sketch.isEmpty()) { return fastEmptyCompactByteArray(sketch); } if (sketch.isSingleItem()) { return fastSingleItemCompactByteArray(sketch); } + final byte[] byteArr = new byte[sketch.getCurrentCompactSerializedSizeBytes()]; final WritableMemory wmem = WritableMemory.writableWrap(byteArr); loadFirst8Bytes(sketch, wmem, false); if (sketch.getN() == 0) { return byteArr; } //empty - final boolean doubleType = (sketch.sketchType == DOUBLES_SKETCH); + final KllDoublesSketch dblSk = (sketch.sketchType == DOUBLES_SKETCH) ? (KllDoublesSketch)sketch : null; + final KllFloatsSketch fltSk = (sketch.sketchType == FLOATS_SKETCH) ? (KllFloatsSketch)sketch : null; + //final KllItemsSketch itmSk = (sketch.sketchType == ITEMS_SKETCH) ? (KllItemsSketch)sketch : null; //TODO //load data int offset = DATA_START_ADR_SINGLE_ITEM; final int[] myLevelsArr = sketch.getLevelsArray(); if (sketch.getN() == 1) { //single item - if (doubleType) { - wmem.putDouble(offset, sketch.getDoubleItemsArray()[myLevelsArr[0]]); - } else { - wmem.putFloat(offset, sketch.getFloatItemsArray()[myLevelsArr[0]]); + switch (sketch.sketchType) { + case DOUBLES_SKETCH : wmem.putDouble(offset, dblSk.getDoubleItemsArray()[myLevelsArr[0]]); break; + case FLOATS_SKETCH : wmem.putFloat(offset, fltSk.getFloatItemsArray()[myLevelsArr[0]]); break; + case ITEMS_SKETCH : break; //TODO + default: throw new IllegalStateException("Unknown Sketch Type"); } } else { // n > 1 //remainder of preamble after first 8 bytes @@ -590,55 +640,84 @@ final class KllHelper { offset += len * Integer.BYTES; //LOAD MIN, MAX Items FOLLOWED BY ITEMS ARRAY - if (doubleType) { - wmem.putDouble(offset,sketch.getMinDoubleItem()); - offset += Double.BYTES; - wmem.putDouble(offset, sketch.getMaxDoubleItem()); - offset += Double.BYTES; - wmem.putDoubleArray(offset, sketch.getDoubleItemsArray(), myLevelsArr[0], sketch.getNumRetained()); - } else { - wmem.putFloat(offset, sketch.getMinFloatItem()); - offset += Float.BYTES; - wmem.putFloat(offset, sketch.getMaxFloatItem()); - offset += Float.BYTES; - wmem.putFloatArray(offset, sketch.getFloatItemsArray(), myLevelsArr[0], sketch.getNumRetained()); + switch (sketch.sketchType) { + case DOUBLES_SKETCH : { + wmem.putDouble(offset,dblSk.getMinDoubleItem()); + offset += Double.BYTES; + wmem.putDouble(offset, dblSk.getMaxDoubleItem()); + offset += Double.BYTES; + wmem.putDoubleArray(offset, dblSk.getDoubleItemsArray(), myLevelsArr[0], sketch.getNumRetained()); + break; + } + case FLOATS_SKETCH : { + wmem.putFloat(offset, fltSk.getMinFloatItem()); + offset += Float.BYTES; + wmem.putFloat(offset, fltSk.getMaxFloatItem()); + offset += Float.BYTES; + wmem.putFloatArray(offset, fltSk.getFloatItemsArray(), myLevelsArr[0], sketch.getNumRetained()); + break; + } + case ITEMS_SKETCH : break; //TODO + default: throw new IllegalStateException("Unknown Sketch Type"); } + } return byteArr; } static byte[] fastEmptyCompactByteArray(final KllSketch sketch) { - final int doubleFlagBit = (sketch.sketchType == DOUBLES_SKETCH) ? DOUBLES_SKETCH_BIT_MASK : 0; + final SketchType sketchType = sketch.sketchType; + final int typeFlagBit = sketchType == DOUBLES_SKETCH ? DOUBLES_SKETCH_BIT_MASK + : sketchType == ITEMS_SKETCH ? ITEMS_SKETCH_BIT_MASK : 0; final byte[] byteArr = new byte[8]; byteArr[0] = PREAMBLE_INTS_EMPTY_SINGLE; //2 byteArr[1] = SERIAL_VERSION_EMPTY_FULL; //1 byteArr[2] = KLL_FAMILY; //15 - byteArr[3] = (byte) (EMPTY_BIT_MASK | doubleFlagBit); + byteArr[3] = (byte) (EMPTY_BIT_MASK | typeFlagBit); ByteArrayUtil.putShortLE(byteArr, K_SHORT_ADR, (short)sketch.getK()); byteArr[6] = (byte)sketch.getM(); return byteArr; } static byte[] fastSingleItemCompactByteArray(final KllSketch sketch) { - final boolean doubleSketch = sketch.sketchType == DOUBLES_SKETCH; - final int doubleFlagBit = doubleSketch ? DOUBLES_SKETCH_BIT_MASK : 0; - final byte[] byteArr = new byte[8 + (doubleSketch ? Double.BYTES : Float.BYTES)]; - byteArr[0] = PREAMBLE_INTS_EMPTY_SINGLE; //2 - byteArr[1] = SERIAL_VERSION_SINGLE; //2 - byteArr[2] = KLL_FAMILY; //15 - byteArr[3] = (byte) (SINGLE_ITEM_BIT_MASK | doubleFlagBit); - ByteArrayUtil.putShortLE(byteArr, K_SHORT_ADR, (short)sketch.getK()); - byteArr[6] = (byte)sketch.getM(); - if (doubleSketch) { - ByteArrayUtil.putDoubleLE(byteArr, DATA_START_ADR_SINGLE_ITEM, sketch.getDoubleSingleItem()); - } else { - ByteArrayUtil.putFloatLE(byteArr, DATA_START_ADR_SINGLE_ITEM, sketch.getFloatSingleItem()); + final SketchType sketchType = sketch.sketchType; + final byte[] byteArr; + switch (sketchType) { + case FLOATS_SKETCH: { + final KllFloatsSketch fltSk = (KllFloatsSketch) sketch; + byteArr = new byte[8 + Float.BYTES]; + byteArr[PREAMBLE_INTS_BYTE_ADR] = PREAMBLE_INTS_EMPTY_SINGLE; //2 + byteArr[SER_VER_BYTE_ADR] = SERIAL_VERSION_SINGLE; //2 + byteArr[FAMILY_BYTE_ADR] = KLL_FAMILY; //15 + byteArr[FLAGS_BYTE_ADR] = (byte) SINGLE_ITEM_BIT_MASK; //4 + ByteArrayUtil.putShortLE(byteArr, K_SHORT_ADR, (short)sketch.getK()); + byteArr[M_BYTE_ADR] = (byte)sketch.getM(); + ByteArrayUtil.putFloatLE(byteArr, DATA_START_ADR_SINGLE_ITEM, fltSk.getFloatSingleItem()); + break; + } + case DOUBLES_SKETCH: { + final KllDoublesSketch dblSk = (KllDoublesSketch) sketch; + byteArr = new byte[8 + Double.BYTES]; + byteArr[PREAMBLE_INTS_BYTE_ADR] = PREAMBLE_INTS_EMPTY_SINGLE; //2 + byteArr[SER_VER_BYTE_ADR] = SERIAL_VERSION_SINGLE; //2 + byteArr[FAMILY_BYTE_ADR] = KLL_FAMILY; //15 + byteArr[FLAGS_BYTE_ADR] = (byte) (SINGLE_ITEM_BIT_MASK | DOUBLES_SKETCH_BIT_MASK); //12 + ByteArrayUtil.putShortLE(byteArr, K_SHORT_ADR, (short)sketch.getK()); + byteArr[M_BYTE_ADR] = (byte)sketch.getM(); + ByteArrayUtil.putDoubleLE(byteArr, DATA_START_ADR_SINGLE_ITEM, dblSk.getDoubleSingleItem()); + break; + } + case ITEMS_SKETCH: { + byteArr = null; //TODO + break; + } + default: return null; //can't happen } return byteArr; } static String toStringImpl(final KllSketch sketch, final boolean withLevels, final boolean withData) { - final boolean doubleType = (sketch.sketchType == DOUBLES_SKETCH); + final SketchType sketchType = sketch.sketchType; final int k = sketch.getK(); final int m = sketch.getM(); final int numLevels = sketch.getNumLevels(); @@ -646,7 +725,9 @@ final class KllHelper { final String epsPct = String.format("%.3f%%", sketch.getNormalizedRankError(false) * 100); final String epsPMFPct = String.format("%.3f%%", sketch.getNormalizedRankError(true) * 100); final StringBuilder sb = new StringBuilder(); - final String skType = (sketch.updatableMemFormat ? "Direct" : "") + (doubleType ? "Doubles" : "Floats"); + final String directStr = sketch.updatableMemFormat ? "Direct" : ""; + final String skType = sketchType == DOUBLES_SKETCH ? directStr + "Doubles" : + sketchType == FLOATS_SKETCH ? directStr + "Floats" : directStr + "Items"; sb.append(Util.LS).append("### Kll").append(skType).append("Sketch Summary:").append(Util.LS); sb.append(" K : ").append(k).append(Util.LS); sb.append(" Dynamic min K : ").append(sketch.getMinK()).append(Util.LS); @@ -665,28 +746,44 @@ final class KllHelper { } else { sb.append(" Compact Storage Bytes : ").append(sketch.getCurrentCompactSerializedSizeBytes()).append(Util.LS); } - - if (doubleType) { - sb.append(" Min Item : ").append(sketch.getMinDoubleItem()).append(Util.LS); - sb.append(" Max Item : ").append(sketch.getMaxDoubleItem()).append(Util.LS); - } else { - sb.append(" Min Item : ").append(sketch.getMinFloatItem()).append(Util.LS); - sb.append(" Max Item : ").append(sketch.getMaxFloatItem()).append(Util.LS); + KllDoublesSketch dblSk = null; + KllFloatsSketch fltSk = null; + //final KllItemsSketch itmSk = null; + + if (sketchType == DOUBLES_SKETCH) { + dblSk = (KllDoublesSketch) sketch; + sb.append(" Min Item : ").append(dblSk.getMinDoubleItem()).append(Util.LS); + sb.append(" Max Item : ").append(dblSk.getMaxDoubleItem()).append(Util.LS); + } else if (sketchType == FLOATS_SKETCH) { + fltSk = (KllFloatsSketch) sketch; + sb.append(" Min Item : ").append(fltSk.getMinFloatItem()).append(Util.LS); + sb.append(" Max Item : ").append(fltSk.getMaxFloatItem()).append(Util.LS); } +// else { +// itmSk = (KllItemsSketch) sketch; +// sb.append(" Min Item : ").append(itmSk.getMinItem()).append(Util.LS); +// sb.append(" Max Item : ").append(itmSk.getMaxItem()).append(Util.LS); +// } sb.append("### End sketch summary").append(Util.LS); double[] myDoubleItemsArr = null; float[] myFloatItemsArr = null; - if (doubleType) { - myDoubleItemsArr = sketch.getDoubleItemsArray(); - } else { - myFloatItemsArr = sketch.getFloatItemsArray(); - } + Object[] myItemsArr = null; + if (withLevels) { sb.append(outputLevels(k, m, numLevels, levelsArr)); } if (withData) { - sb.append(outputData(doubleType, numLevels, levelsArr, myFloatItemsArr, myDoubleItemsArr)); + if (sketchType == DOUBLES_SKETCH) { + myDoubleItemsArr = dblSk.getDoubleItemsArray(); + sb.append(outputDoublesData(numLevels, levelsArr, myDoubleItemsArr)); + } else if (sketchType == FLOATS_SKETCH) { + myFloatItemsArr = fltSk.getFloatItemsArray(); + sb.append(outputFloatsData(numLevels, levelsArr, myFloatItemsArr)); + } else { //Items Sketch + myItemsArr = null; + sb.append(outputGenericItemsData(numLevels, levelsArr, myItemsArr)); + } } return sb.toString(); } @@ -699,13 +796,16 @@ final class KllHelper { * @return a byte array in an updatable form. */ private static byte[] toUpdatableByteArrayFromUpdatableMemory(final KllSketch sketch) { - final boolean doubleType = (sketch.sketchType == SketchType.DOUBLES_SKETCH); + final SketchType sketchType = sketch.sketchType; + final int typeFlagBit = sketchType == DOUBLES_SKETCH ? DOUBLES_SKETCH_BIT_MASK + : sketchType == ITEMS_SKETCH ? ITEMS_SKETCH_BIT_MASK : 0; + final int curBytes = sketch.getCurrentUpdatableSerializedSizeBytes(); final long n = sketch.getN(); final byte flags = (byte) (UPDATABLE_BIT_MASK | ((n == 0) ? EMPTY_BIT_MASK : 0) | ((n == 1) ? SINGLE_ITEM_BIT_MASK : 0) - | (doubleType ? DOUBLES_SKETCH_BIT_MASK : 0)); + | typeFlagBit); final byte[] byteArr = new byte[curBytes]; sketch.wmem.getByteArray(0, byteArr, 0, curBytes); byteArr[FLAGS_BYTE_ADR] = flags; @@ -732,7 +832,7 @@ final class KllHelper { setMemoryNumLevels(wmem, sketch.getNumLevels()); //load data - final boolean doubleType = (sketch.sketchType == DOUBLES_SKETCH); + final SketchType sketchType = sketch.sketchType; int offset = DATA_START_ADR; //LOAD LEVELS ARRAY the last integer in levels_ IS serialized @@ -742,21 +842,26 @@ final class KllHelper { offset += len * Integer.BYTES; //LOAD MIN, MAX Items FOLLOWED BY ITEMS ARRAY - if (doubleType) { - wmem.putDouble(offset, sketch.getMinDoubleItem()); + if (sketchType == DOUBLES_SKETCH) { + final KllDoublesSketch dblSk = (KllDoublesSketch) sketch; + wmem.putDouble(offset, dblSk.getMinDoubleItem()); offset += Double.BYTES; - wmem.putDouble(offset, sketch.getMaxDoubleItem()); + wmem.putDouble(offset, dblSk.getMaxDoubleItem()); offset += Double.BYTES; - final double[] doubleItemsArr = sketch.getDoubleItemsArray(); + final double[] doubleItemsArr = dblSk.getDoubleItemsArray(); wmem.putDoubleArray(offset, doubleItemsArr, 0, doubleItemsArr.length); - } else { - wmem.putFloat(offset, sketch.getMinFloatItem()); + } else if (sketchType == FLOATS_SKETCH) { + final KllFloatsSketch fltSk = (KllFloatsSketch) sketch; + wmem.putFloat(offset, fltSk.getMinFloatItem()); offset += Float.BYTES; - wmem.putFloat(offset,sketch.getMaxFloatItem()); + wmem.putFloat(offset,fltSk.getMaxFloatItem()); offset += Float.BYTES; - final float[] floatItemsArr = sketch.getFloatItemsArray(); + final float[] floatItemsArr = fltSk.getFloatItemsArray(); wmem.putFloatArray(offset, floatItemsArr, 0, floatItemsArr.length); } + else { + //ITEMS_SKETCH //TODO + } return byteArr; } @@ -775,6 +880,18 @@ final class KllHelper { * @param sketch the current sketch */ private static void addEmptyTopLevelToCompletelyFullSketch(final KllSketch sketch) { + final SketchType sketchType = sketch.sketchType; + KllDoublesSketch dblSk = null; + KllFloatsSketch fltSk = null; + //KllItemsSketch itmSk = null; //TODO + + if (sketchType == DOUBLES_SKETCH) { + dblSk = (KllDoublesSketch) sketch; + } else if (sketchType == FLOATS_SKETCH) { + fltSk = (KllFloatsSketch) sketch; + } else { + //itmSk = (KllItemsSketch) sketch; //TODO + } final int[] myCurLevelsArr = sketch.getLevelsArray(); final int myCurNumLevels = sketch.getNumLevels(); final int myCurTotalItemsCapacity = myCurLevelsArr[myCurNumLevels]; @@ -793,17 +910,19 @@ final class KllHelper { float[] myNewFloatItemsArr = null; double[] myNewDoubleItemsArr = null; - if (sketch.sketchType == DOUBLES_SKETCH) { - minDouble = sketch.getMinDoubleItem(); - maxDouble = sketch.getMaxDoubleItem(); - myCurDoubleItemsArr = sketch.getDoubleItemsArray(); + if (sketchType == DOUBLES_SKETCH) { + minDouble = dblSk.getMinDoubleItem(); + maxDouble = dblSk.getMaxDoubleItem(); + myCurDoubleItemsArr = dblSk.getDoubleItemsArray(); //assert we are following a certain growth scheme assert myCurDoubleItemsArr.length == myCurTotalItemsCapacity; - } else { //FLOATS_SKETCH - minFloat = sketch.getMinFloatItem(); - maxFloat = sketch.getMaxFloatItem(); - myCurFloatItemsArr = sketch.getFloatItemsArray(); + } else if (sketchType == FLOATS_SKETCH) { + minFloat = fltSk.getMinFloatItem(); + maxFloat = fltSk.getMaxFloatItem(); + myCurFloatItemsArr = fltSk.getFloatItemsArray(); assert myCurFloatItemsArr.length == myCurTotalItemsCapacity; + } else { + //ITEMS_SKETCH //TODO } assert myCurLevelsArr[0] == 0; //definition of full is part of the growth scheme @@ -832,14 +951,16 @@ final class KllHelper { myNewLevelsArr[myNewNumLevels] = myNewTotalItemsCapacity; // initialize the new "extra" index at the top // GROW ITEMS ARRAY - if (sketch.sketchType == DOUBLES_SKETCH) { + if (sketchType == DOUBLES_SKETCH) { myNewDoubleItemsArr = new double[myNewTotalItemsCapacity]; // copy and shift the current data into the new array System.arraycopy(myCurDoubleItemsArr, 0, myNewDoubleItemsArr, deltaItemsCap, myCurTotalItemsCapacity); - } else { + } else if (sketchType == FLOATS_SKETCH) { myNewFloatItemsArr = new float[myNewTotalItemsCapacity]; // copy and shift the current items data into the new array System.arraycopy(myCurFloatItemsArr, 0, myNewFloatItemsArr, deltaItemsCap, myCurTotalItemsCapacity); + } else { + //ITEMS_SKETCH // TODO } //MEMORY SPACE MANAGEMENT @@ -849,14 +970,14 @@ final class KllHelper { //update our sketch with new expanded spaces sketch.setNumLevels(myNewNumLevels); sketch.setLevelsArray(myNewLevelsArr); - if (sketch.sketchType == DOUBLES_SKETCH) { - sketch.setMinDoubleItem(minDouble); - sketch.setMaxDoubleItem(maxDouble); - sketch.setDoubleItemsArray(myNewDoubleItemsArr); + if (sketchType == DOUBLES_SKETCH) { + dblSk.setMinDoubleItem(minDouble); + dblSk.setMaxDoubleItem(maxDouble); + dblSk.setDoubleItemsArray(myNewDoubleItemsArr); } else { //Float sketch - sketch.setMinFloatItem(minFloat); - sketch.setMaxFloatItem(maxFloat); - sketch.setFloatItemsArray(myNewFloatItemsArr); + fltSk.setMinFloatItem(minFloat); + fltSk.setMaxFloatItem(maxFloat); + fltSk.setFloatItemsArray(myNewFloatItemsArr); } } diff --git a/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java b/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java new file mode 100644 index 00000000..00d44dea --- /dev/null +++ b/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java @@ -0,0 +1,320 @@ +/* + * 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.kll; + +import static java.lang.Math.max; +import static java.lang.Math.min; + +import java.util.Comparator; +import java.util.Objects; + +import org.apache.datasketches.common.ArrayOfItemsSerDe; +import org.apache.datasketches.quantilescommon.GenericSortedView; +import org.apache.datasketches.quantilescommon.QuantileSearchCriteria; +import org.apache.datasketches.quantilescommon.QuantilesGenericAPI; +import org.apache.datasketches.quantilescommon.QuantilesGenericSketchIterator; + +public class KllItemsSketch<T> extends KllGenericProxy<T> implements QuantilesGenericAPI<T> { + private final int k_; // configured size of K. + private final int m_; // configured size of M. + private long n_; // number of items input into this sketch. + private int minK_; // dynamic minK for error estimation after merging with different k. + private boolean isLevelZeroSorted_; + private T maxItem_; + private T minItem_; + Object[] items_; + final Class<T> clazz_; + private final Comparator<? super T> comparator_; + private final ArrayOfItemsSerDe<T> serDe_; + + KllItemsSketch( + final int k, + final int m, + final Class<T> clazz, + final Comparator<? super T> comparator, + final ArrayOfItemsSerDe<T> serDe) { + super(); + Objects.requireNonNull(clazz, "Class<T> must not be null."); + Objects.requireNonNull(comparator, "Comparator must not be null."); + Objects.requireNonNull(serDe, "Serializer/Deserializer must not be null."); + KllHelper.checkM(m); + KllHelper.checkK(k, m); + k_ = k; + m_ = DEFAULT_M; + n_ = 0; + minK_ = k; + isLevelZeroSorted_ = false; + maxItem_ = null; + minItem_ = null; + items_ = new Object[k]; + levelsArr = new int[] {k, k}; + clazz_ = clazz; + comparator_ = comparator; + serDe_ = serDe; + } + + /** + * Create a new heap instance of this sketch with the default <em>k = 200</em>. + * The default <em>k</em> = 200 results in a normalized rank error of about + * 1.65%. Larger K will have smaller error but the sketch will be larger (and slower). + * This will have a rank error of about 1.65%. + * @param <T> The sketch data type + * @param clazz the given class of T + * @param comparator to compare items + * @param serDe Serializer / deserializer for an array of items, <i>T[]</i>. + * @return new KllItemsSketch on the heap. + */ + public static <T> KllItemsSketch<T> newHeapInstance( + final Class<T> clazz, + final Comparator<? super T> comparator, + final ArrayOfItemsSerDe<T> serDe) { + final KllItemsSketch<T> itmSk = new KllItemsSketch<T>(DEFAULT_K, DEFAULT_M, clazz, comparator, serDe); + return itmSk; + } + + /** + * Create a new heap instance of this sketch with a given parameter <em>k</em>. + * <em>k</em> can be between DEFAULT_M and 65535, inclusive. + * The default <em>k</em> = 200 results in a normalized rank error of about + * 1.65%. Larger K will have smaller error but the sketch will be larger (and slower). + * @param k parameter that controls size of the sketch and accuracy of estimates. + * @param <T> The sketch data type + * @param clazz the given class of T + * @param comparator to compare items + * @param serDe Serializer / deserializer for an array of items, <i>T[]</i>. + * @return new KllItemsSketch on the heap. + */ + public static <T> KllItemsSketch<T> newHeapInstance( + final int k, + final Class<T> clazz, + final Comparator<? super T> comparator, + final ArrayOfItemsSerDe<T> serDe) { + final KllItemsSketch<T> itmSk = new KllItemsSketch<T>(k, DEFAULT_M, clazz, comparator, serDe); + return itmSk; + } + + /** + * {@inheritDoc} + * The approximate probability that the true rank is within the confidence interval + * specified by the upper and lower rank bounds for this sketch is 0.99. + */ + @Override + public double getRankLowerBound(final double rank) { + return max(0.0, rank - KllHelper.getNormalizedRankError(getMinK(), false)); + } + + /** + * {@inheritDoc} + * The approximate probability that the true rank is within the confidence interval + * specified by the upper and lower rank bounds for this sketch is 0.99. + */ + @Override + public double getRankUpperBound(final double rank) { + return min(1.0, rank + KllHelper.getNormalizedRankError(getMinK(), false)); + } + + @Override + public double[] getCDF(final T[] splitPoints, final QuantileSearchCriteria searchCrit) { + // TODO Auto-generated method stub + return null; + } + + @Override + public T getMaxItem() { + // TODO Auto-generated method stub + return null; + } + + @Override + public T getMinItem() { + // TODO Auto-generated method stub + return null; + } + + @Override + public GenericPartitionBoundaries<T> getPartitionBoundaries(final int numEquallyWeighted, + final QuantileSearchCriteria searchCrit) { + // TODO Auto-generated method stub + return null; + } + + @Override + public double[] getPMF(final T[] splitPoints, final QuantileSearchCriteria searchCrit) { + // TODO Auto-generated method stub + return null; + } + + @Override + public T getQuantile(final double rank, final QuantileSearchCriteria searchCrit) { + // TODO Auto-generated method stub + return null; + } + + @Override + public T getQuantileLowerBound(final double rank) { + // TODO Auto-generated method stub + return null; + } + + @Override + public T getQuantileUpperBound(final double rank) { + // TODO Auto-generated method stub + return null; + } + + @Override + public T[] getQuantiles(final double[] ranks, final QuantileSearchCriteria searchCrit) { + // TODO Auto-generated method stub + return null; + } + + @Override + public double getRank(final T quantile, final QuantileSearchCriteria searchCrit) { + // TODO Auto-generated method stub + return 0; + } + + @Override + public double[] getRanks(final T[] quantiles, final QuantileSearchCriteria searchCrit) { + // TODO Auto-generated method stub + return null; + } + + @Override + public GenericSortedView<T> getSortedView() { + // TODO Auto-generated method stub + return null; + } + + @Override + public QuantilesGenericSketchIterator<T> iterator() { + // TODO Auto-generated method stub + return null; + } + + @Override + public void update(final T item) { + // TODO Auto-generated method stub + + } + + @Override + public int getK() { + // TODO Auto-generated method stub + return 0; + } + + @Override + public long getN() { + // TODO Auto-generated method stub + return 0; + } + + @Override + int getM() { + // TODO Auto-generated method stub + return 0; + } + + @Override + int getMinK() { + // TODO Auto-generated method stub + return 0; + } + + @Override + void incN() { + // TODO Auto-generated method stub + + } + + @Override + void incNumLevels() { + // TODO Auto-generated method stub + + } + + @Override + boolean isLevelZeroSorted() { + // TODO Auto-generated method stub + return false; + } + + @Override + void setLevelZeroSorted(final boolean sorted) { + // TODO Auto-generated method stub + + } + + @Override + void setMinK(final int minK) { + // TODO Auto-generated method stub + + } + + @Override + void setN(final long n) { + // TODO Auto-generated method stub + + } + + @Override + void setNumLevels(final int numLevels) { + // TODO Auto-generated method stub + + } + + @Override + T[] getItemsArray() { + // TODO Auto-generated method stub + return null; + } + + @Override + T getSingleItem() { + // TODO Auto-generated method stub + return null; + } + + @Override + void setItemsArray(final T[] Items) { + // TODO Auto-generated method stub + + } + + @Override + void setItemsArrayAt(final int index, final T item) { + // TODO Auto-generated method stub + + } + + @Override + void setMaxItem(final T item) { + // TODO Auto-generated method stub + + } + + @Override + void setMinItem(final T item) { + // TODO Auto-generated method stub + + } + +} diff --git a/src/main/java/org/apache/datasketches/kll/KllMemoryValidate.java b/src/main/java/org/apache/datasketches/kll/KllMemoryValidate.java index cd571ae8..651e4066 100644 --- a/src/main/java/org/apache/datasketches/kll/KllMemoryValidate.java +++ b/src/main/java/org/apache/datasketches/kll/KllMemoryValidate.java @@ -58,7 +58,7 @@ import org.apache.datasketches.memory.WritableMemory; /** * This class performs all the error checking of an incoming Memory object and extracts the key fields in the process. - * This is used by all sketches that read or import Memory objects. + * This is used by all KLL sketches that read or import Memory objects. * * @author lrhodes * diff --git a/src/main/java/org/apache/datasketches/kll/KllPreambleUtil.java b/src/main/java/org/apache/datasketches/kll/KllPreambleUtil.java index 6bfe4d90..24ea33f6 100644 --- a/src/main/java/org/apache/datasketches/kll/KllPreambleUtil.java +++ b/src/main/java/org/apache/datasketches/kll/KllPreambleUtil.java @@ -159,6 +159,7 @@ final class KllPreambleUtil { static final int SINGLE_ITEM_BIT_MASK = 4; static final int DOUBLES_SKETCH_BIT_MASK = 8; static final int UPDATABLE_BIT_MASK = 16; + static final int ITEMS_SKETCH_BIT_MASK = 32; /** * Returns a human readable string summary of the internal state of the given sketch byte array. diff --git a/src/main/java/org/apache/datasketches/kll/KllSketch.java b/src/main/java/org/apache/datasketches/kll/KllSketch.java index 32e17a6b..ed00321f 100644 --- a/src/main/java/org/apache/datasketches/kll/KllSketch.java +++ b/src/main/java/org/apache/datasketches/kll/KllSketch.java @@ -82,7 +82,7 @@ public abstract class KllSketch implements QuantilesAPI { /** * Used to define the variable type of the current instance of this class. */ - public enum SketchType { FLOATS_SKETCH, DOUBLES_SKETCH } + public enum SketchType { FLOATS_SKETCH, DOUBLES_SKETCH, ITEMS_SKETCH } enum Error { TGT_IS_READ_ONLY("Given sketch Memory is immutable, cannot write."), @@ -145,7 +145,7 @@ public abstract class KllSketch implements QuantilesAPI { * @param wmem the current WritableMemory or null * @param memReqSvr the given MemoryRequestServer or null */ - KllSketch(final SketchType sketchType, final WritableMemory wmem, final MemoryRequestServer memReqSvr) { + public KllSketch(final SketchType sketchType, final WritableMemory wmem, final MemoryRequestServer memReqSvr) { this.sketchType = sketchType; this.wmem = wmem; if (wmem != null) { @@ -227,7 +227,7 @@ public abstract class KllSketch implements QuantilesAPI { * @return the current number of bytes this sketch would require to store in the compact Memory Format. * @deprecated version 4.0.0 use {@link #getSerializedSizeBytes}. */ - @Deprecated + @Deprecated //just make this package private public final int getCurrentCompactSerializedSizeBytes() { return getCurrentSerializedSizeBytes(getNumLevels(), getNumRetained(), sketchType, false); } @@ -237,7 +237,7 @@ public abstract class KllSketch implements QuantilesAPI { * @return the current number of bytes this sketch would require to store in the updatable Memory Format. * @deprecated version 4.0.0 use {@link #getSerializedSizeBytes}. */ - @Deprecated + @Deprecated //just make this package private public final int getCurrentUpdatableSerializedSizeBytes() { final int quantilesCap = KllHelper.computeTotalItemCapacity(getK(), getM(), getNumLevels()); return getCurrentSerializedSizeBytes(getNumLevels(), quantilesCap, sketchType, true); @@ -342,33 +342,11 @@ public abstract class KllSketch implements QuantilesAPI { if (sketchType == DOUBLES_SKETCH) { if (!other.isDoublesSketch()) { kllSketchThrow(SRC_MUST_BE_DOUBLE); } KllDoublesHelper.mergeDoubleImpl((KllDoublesSketch)this, other); - } else { + } else if (sketchType == FLOATS_SKETCH) { if (!other.isFloatsSketch()) { kllSketchThrow(SRC_MUST_BE_FLOAT); } KllFloatsHelper.mergeFloatImpl((KllFloatsSketch)this, other); - } - } - - /** - * {@inheritDoc} - * <p>The parameter <i>k</i> will not change.</p> - */ - @Override - public final void reset() { - if (readOnly) { kllSketchThrow(TGT_IS_READ_ONLY); } - final int k = getK(); - setN(0); - setMinK(k); - setNumLevels(1); - setLevelZeroSorted(false); - setLevelsArray(new int[] {k, k}); - if (sketchType == DOUBLES_SKETCH) { - setMinDoubleItem(Double.NaN); - setMaxDoubleItem(Double.NaN); - setDoubleItemsArray(new double[k]); } else { - setMinFloatItem(Float.NaN); - setMaxFloatItem(Float.NaN); - setFloatItemsArray(new float[k]); + //ITEMS_SKETCH //TODO } } @@ -387,20 +365,6 @@ public abstract class KllSketch implements QuantilesAPI { return KllHelper.toStringImpl(this, withLevels, withData); } - /** - * @return full size of internal items array including garbage. - */ - abstract double[] getDoubleItemsArray(); - - abstract double getDoubleSingleItem(); - - /** - * @return full size of internal items array including garbage. - */ - abstract float[] getFloatItemsArray(); - - abstract float getFloatSingleItem(); - final int[] getLevelsArray() { return levelsArr; } @@ -414,14 +378,6 @@ public abstract class KllSketch implements QuantilesAPI { */ abstract int getM(); - abstract double getMaxDoubleItem(); - - abstract float getMaxFloatItem(); - - abstract double getMinDoubleItem(); - - abstract float getMinFloatItem(); - /** * MinK is the K that results from a merge with a sketch configured with a K lower than * the K of this sketch. This is then used in computing the estimated upper and lower bounds of error. @@ -453,14 +409,6 @@ public abstract class KllSketch implements QuantilesAPI { */ boolean isSingleItem() { return getN() == 1; } - abstract void setDoubleItemsArray(double[] doubleItems); - - abstract void setDoubleItemsArrayAt(int index, double item); - - abstract void setFloatItemsArray(float[] floatItems); - - abstract void setFloatItemsArrayAt(int index, float item); - final void setLevelsArray(final int[] levelsArr) { if (readOnly) { kllSketchThrow(TGT_IS_READ_ONLY); } this.levelsArr = levelsArr; @@ -480,14 +428,6 @@ public abstract class KllSketch implements QuantilesAPI { abstract void setLevelZeroSorted(boolean sorted); - abstract void setMaxDoubleItem(double item); - - abstract void setMaxFloatItem(float item); - - abstract void setMinDoubleItem(double item); - - abstract void setMinFloatItem(float item); - abstract void setMinK(int minK); abstract void setN(long n); diff --git a/src/main/java/org/apache/datasketches/quantiles/ItemsUnion.java b/src/main/java/org/apache/datasketches/quantiles/ItemsUnion.java index d90ba235..ed0a006c 100644 --- a/src/main/java/org/apache/datasketches/quantiles/ItemsUnion.java +++ b/src/main/java/org/apache/datasketches/quantiles/ItemsUnion.java @@ -137,7 +137,7 @@ public final class ItemsUnion<T> { * @param srcMem Memory image of sketch to be merged * @param serDe an instance of ArrayOfItemsSerDe */ - public void union(final Memory srcMem, final ArrayOfItemsSerDe<T> serDe) { //TODO rename merge + public void union(final Memory srcMem, final ArrayOfItemsSerDe<T> serDe) { final ItemsSketch<T> that = ItemsSketch.getInstance(this.clazz_, srcMem, comparator_, serDe); gadget_ = updateLogic(maxK_, comparator_, gadget_, that); } diff --git a/src/main/java/org/apache/datasketches/quantiles/ItemsUtil.java b/src/main/java/org/apache/datasketches/quantiles/ItemsUtil.java index 1e1f6703..782c467d 100644 --- a/src/main/java/org/apache/datasketches/quantiles/ItemsUtil.java +++ b/src/main/java/org/apache/datasketches/quantiles/ItemsUtil.java @@ -29,10 +29,6 @@ import org.apache.datasketches.common.SketchesArgumentException; /** * Utility class for generic quantiles sketch. * - * <p>This class contains a highly specialized sort called blockyTandemMergeSort(). - * It also contains methods that are used while building histograms and other common - * functions.</p> - * * @author Kevin Lang * @author Alexander Saydakov */ diff --git a/src/test/java/org/apache/datasketches/kll/KllDirectDoublesSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllDirectDoublesSketchTest.java index c2c7b14c..2db05ea9 100644 --- a/src/test/java/org/apache/datasketches/kll/KllDirectDoublesSketchTest.java +++ b/src/test/java/org/apache/datasketches/kll/KllDirectDoublesSketchTest.java @@ -565,7 +565,7 @@ public class KllDirectDoublesSketchTest { @Test public void checkReset() { WritableMemory dstMem = WritableMemory.allocate(6000); - KllDoublesSketch sk = KllDoublesSketch.newDirectInstance(20, dstMem, memReqSvr); + KllDirectDoublesSketch sk = KllDoublesSketch.newDirectInstance(20, dstMem, memReqSvr); for (int i = 1; i <= 100; i++) { sk.update(i); } long n1 = sk.getN(); double min1 = sk.getMinItem(); @@ -643,7 +643,6 @@ public class KllDirectDoublesSketchTest { try { sk2.setMinK(idx); fail(); } catch (SketchesArgumentException e) { } try { sk2.setN(idx); fail(); } catch (SketchesArgumentException e) { } try { sk2.setNumLevels(idx); fail(); } catch (SketchesArgumentException e) { } - try { sk2.getFloatSingleItem(); fail(); } catch (SketchesArgumentException e) { } } @Test(expectedExceptions = SketchesArgumentException.class) diff --git a/src/test/java/org/apache/datasketches/kll/KllDirectFloatsSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllDirectFloatsSketchTest.java index 875595d9..4cf1b60b 100644 --- a/src/test/java/org/apache/datasketches/kll/KllDirectFloatsSketchTest.java +++ b/src/test/java/org/apache/datasketches/kll/KllDirectFloatsSketchTest.java @@ -644,7 +644,6 @@ public class KllDirectFloatsSketchTest { try { sk2.setMinK(idx); fail(); } catch (SketchesArgumentException e) { } try { sk2.setN(idx); fail(); } catch (SketchesArgumentException e) { } try { sk2.setNumLevels(idx); fail(); } catch (SketchesArgumentException e) { } - try { sk2.getDoubleSingleItem(); fail(); } catch (SketchesArgumentException e) { } } @Test(expectedExceptions = SketchesArgumentException.class) @@ -663,6 +662,7 @@ public class KllDirectFloatsSketchTest { try { sk2.merge(sk1); fail(); } catch (SketchesArgumentException e) { } } + // get Direct Floats Sketch private static KllFloatsSketch getDFSketch(final int k, final int n) { KllFloatsSketch sk = KllFloatsSketch.newHeapInstance(k); for (int i = 1; i <= n; i++) { sk.update(i); } diff --git a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java index 6777b931..e6d1edc1 100644 --- a/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java +++ b/src/test/java/org/apache/datasketches/kll/KllDoublesSketchTest.java @@ -415,7 +415,7 @@ public class KllDoublesSketchTest { sketch1.update(1); final byte[] bytes = sketch1.toByteArray(); final KllDoublesSketch sketch2 = KllDoublesSketch.heapify(Memory.wrap(bytes)); - assertEquals(bytes.length, sketch1.getCurrentCompactSerializedSizeBytes()); + assertEquals(bytes.length, sketch1.getSerializedSizeBytes()); assertFalse(sketch2.isEmpty()); assertEquals(sketch2.getNumRetained(), 1); assertEquals(sketch2.getN(), 1); @@ -500,21 +500,6 @@ public class KllDoublesSketchTest { assertEquals(max2, max1); } - @Test - public void coverInheritanceArtifacts() { - float[] fltArr = new float[0]; - float fltV = 1.0f; - int idx = 1; - KllDoublesSketch sk = KllDoublesSketch.newHeapInstance(20); - try { sk.getFloatItemsArray(); fail(); } catch (SketchesArgumentException e) { } - try { sk.getMaxFloatItem(); fail(); } catch (SketchesArgumentException e) { } - try { sk.getMinFloatItem(); fail(); } catch (SketchesArgumentException e) { } - try { sk.setFloatItemsArray(fltArr); fail(); } catch (SketchesArgumentException e) { } - try { sk.setFloatItemsArrayAt(idx,fltV); fail(); } catch (SketchesArgumentException e) { } - try { sk.setMaxFloatItem(fltV); fail(); } catch (SketchesArgumentException e) { } - try { sk.setMinFloatItem(fltV); fail(); } catch (SketchesArgumentException e) { } - } - @Test public void checkReadOnlyUpdate() { KllDoublesSketch sk1 = KllDoublesSketch.newHeapInstance(20); diff --git a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java index 51cbcf17..c6ef9466 100644 --- a/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java +++ b/src/test/java/org/apache/datasketches/kll/KllFloatsSketchTest.java @@ -501,21 +501,6 @@ public class KllFloatsSketchTest { assertEquals(max2, max1); } - @Test - public void coverInheritanceArtifacts() { - double[] dblArr = new double[0]; - double dblV = 1.0; - int idx = 1; - KllFloatsSketch sk = KllFloatsSketch.newHeapInstance(20); - try { sk.getDoubleItemsArray(); fail(); } catch (SketchesArgumentException e) { } - try { sk.getMaxDoubleItem(); fail(); } catch (SketchesArgumentException e) { } - try { sk.getMinDoubleItem(); fail(); } catch (SketchesArgumentException e) { } - try { sk.setDoubleItemsArray(dblArr); fail(); } catch (SketchesArgumentException e) { } - try { sk.setDoubleItemsArrayAt(idx,dblV); fail(); } catch (SketchesArgumentException e) { } - try { sk.setMaxDoubleItem(dblV); fail(); } catch (SketchesArgumentException e) { } - try { sk.setMinDoubleItem(dblV); fail(); } catch (SketchesArgumentException e) { } - } - @Test public void checkReadOnlyUpdate() { KllFloatsSketch sk1 = KllFloatsSketch.newHeapInstance(20); diff --git a/src/test/java/org/apache/datasketches/kll/KllMiscDirectFloatsTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscDirectFloatsTest.java index 4755a4ab..ed141e7b 100644 --- a/src/test/java/org/apache/datasketches/kll/KllMiscDirectFloatsTest.java +++ b/src/test/java/org/apache/datasketches/kll/KllMiscDirectFloatsTest.java @@ -391,7 +391,7 @@ public class KllMiscDirectFloatsTest { public void checkSizes() { KllFloatsSketch sk = getDFSketch(20, 0); for (int i = 1; i <= 21; i++) { sk.update(i); } - //println(sk.toString(true, true)); + println(sk.toString(true, true)); //TODO byte[] byteArr1 = KllHelper.toUpdatableByteArrayImpl(sk); int size1 = sk.getCurrentUpdatableSerializedSizeBytes(); assertEquals(size1, byteArr1.length); diff --git a/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java index fd6f52c3..b623ba26 100644 --- a/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java +++ b/src/test/java/org/apache/datasketches/kll/KllMiscDoublesTest.java @@ -541,18 +541,6 @@ public class KllMiscDoublesTest { assertEquals(skCompact.getDoubleSingleItem(), 1.0); } - @Test - public void checkInheritanceArtifacts() { - KllDoublesSketch sk = KllDoublesSketch.newHeapInstance(20); - try { sk.getFloatItemsArray(); fail();} catch (SketchesArgumentException e) {} - try { sk.getMaxFloatItem(); fail();} catch (SketchesArgumentException e) {} - try { sk.getMinFloatItem(); fail();} catch (SketchesArgumentException e) {} - try { sk.setFloatItemsArray(null); fail();} catch (SketchesArgumentException e) {} - try { sk.setFloatItemsArrayAt(0, 0f); fail();} catch (SketchesArgumentException e) {} - try { sk.setMaxFloatItem(0); fail();} catch (SketchesArgumentException e) {} - try { sk.setMinFloatItem(0); fail();} catch (SketchesArgumentException e) {} - } - @Test public void printlnTest() { String s = "PRINTING: printf in " + this.getClass().getName(); diff --git a/src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java b/src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java index 0642da61..ed2e4b05 100644 --- a/src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java +++ b/src/test/java/org/apache/datasketches/kll/KllMiscFloatsTest.java @@ -562,18 +562,6 @@ public class KllMiscFloatsTest { assertEquals(skCompact.getFloatSingleItem(), 1.0F); } - //@Test - public void checkInheritanceArtifacts() { - KllFloatsSketch sk = KllFloatsSketch.newHeapInstance(20); - try { sk.getDoubleItemsArray(); fail();} catch (SketchesArgumentException e) {} - try { sk.getMaxDoubleItem(); fail();} catch (SketchesArgumentException e) {} - try { sk.getMinDoubleItem(); fail();} catch (SketchesArgumentException e) {} - try { sk.setDoubleItemsArray(null); fail();} catch (SketchesArgumentException e) {} - try { sk.setDoubleItemsArrayAt(0, 0f); fail();} catch (SketchesArgumentException e) {} - try { sk.setMaxDoubleItem(0); fail();} catch (SketchesArgumentException e) {} - try { sk.setMinDoubleItem(0); fail();} catch (SketchesArgumentException e) {} - } - @Test public void printlnTest() { String s = "PRINTING: printf in " + this.getClass().getName(); --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
