apache / datasketches-java / #282

/*

 * 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.quantiles;

import static java.lang.Math.max;

import static java.lang.Math.min;

import static org.apache.datasketches.QuantileSearchCriteria.INCLUSIVE;

import static org.apache.datasketches.quantiles.PreambleUtil.COMPACT_FLAG_MASK;

import static org.apache.datasketches.quantiles.PreambleUtil.extractFamilyID;

import static org.apache.datasketches.quantiles.PreambleUtil.extractFlags;

import static org.apache.datasketches.quantiles.PreambleUtil.extractK;

import static org.apache.datasketches.quantiles.PreambleUtil.extractN;

import static org.apache.datasketches.quantiles.PreambleUtil.extractPreLongs;

import static org.apache.datasketches.quantiles.PreambleUtil.extractSerVer;

import static org.apache.datasketches.quantiles.Util.computeBaseBufferItems;

import static org.apache.datasketches.quantiles.Util.computeBitPattern;

import java.lang.reflect.Array;

import java.util.Arrays;

import java.util.Comparator;

import java.util.Random;

import org.apache.datasketches.QuantileSearchCriteria;

import org.apache.datasketches.QuantilesAPI;

import org.apache.datasketches.QuantilesGenericSketchIterator;

import org.apache.datasketches.ArrayOfItemsSerDe;

import org.apache.datasketches.GenericSortedView;

import org.apache.datasketches.SketchesArgumentException;

import org.apache.datasketches.memory.Memory;

import org.apache.datasketches.memory.WritableMemory;

/**

 * This is a stochastic streaming sketch that enables near-real time analysis of the

 * approximate distribution of comparable items from a very large stream in a single pass.

 * The analysis is obtained using a getQuantiles(*) function or its inverse functions the

 * Probability Mass Function from getPMF(*) and the Cumulative Distribution Function from getCDF(*).

 *

 * <p>The documentation for {@link DoublesSketch} applies here except that the size of an ItemsSketch

 * is very dependent on the Items input into the sketch, so there is no comparable size table as

 * for the DoublesSketch.

 *

 * <p>There is more documentation available on

 * <a href="https://datasketches.apache.org">datasketches.apache.org</a>.</p>

 *

 * @param <T> type of item

 *

 * @author Kevin Lang

 * @author Alexander Saydakov

 */

  private final Comparator<? super T> comparator_;

  final int k_;

  long n_;

  /**

   * The smallest quantile ever seen in the stream.

   */

  T minQuantile_;

  /**

   * The largest quantile ever seen in the stream.

   */

  T maxQuantile_;

  /**

   * In the initial on-heap version, equals combinedBuffer_.length.

   * May differ in later versions that grow space more aggressively.

   * Also, in the off-heap version, combinedBuffer_ won't even be a java array,

   * so it won't know its own length.

   */

  int combinedBufferItemCapacity_;

  /**

   * Number of samples currently in base buffer.

   *

   * <p>Count = N % (2*K)

   */

  int baseBufferCount_;

  /**

   * Active levels expressed as a bit pattern.

   *

   * <p>Pattern = N / (2 * K)

   */

  long bitPattern_;

  /**

   * This single array contains the base buffer plus all levels some of which may not be used.

   * A level is of size K and is either full and sorted, or not used. A "not used" buffer may have

   * garbage. Whether a level buffer used or not is indicated by the bitPattern_.

   * The base buffer has length 2*K but might not be full and isn't necessarily sorted.

   * The base buffer precedes the level buffers.

   *

   * <p>The levels arrays require quite a bit of explanation, which we defer until later.

   */

  Object[] combinedBuffer_;

  /**

   * Setting the seed makes the results of the sketch deterministic if the input items are

   * received in exactly the same order. This is only useful when performing test comparisons,

   * otherwise is not recommended.

   */

  /**

   * Obtains a new instance of an ItemsSketch using the DEFAULT_K.

   * @param <T> type of item

   * @param comparator to compare items

   * @return a GenericQuantileSketch

   */

  public static <T> ItemsSketch<T> getInstance(final Comparator<? super T> comparator) {

  }

  /**

   * Obtains a new instance of an ItemsSketch.

   * @param <T> type of item

   * @param k Parameter that controls space usage of sketch and accuracy of estimates.

   * Must be greater than 2 and less than 65536 and a power of 2.

   * @param comparator to compare items

   * @return a GenericQuantileSketch

   */

  public static <T> ItemsSketch<T> getInstance(final int k, final Comparator<? super T> comparator) {

  }

  /**

   * Heapifies the given srcMem, which must be a Memory image of a ItemsSketch

   * @param <T> type of item

   * @param srcMem a Memory image of a sketch.

   * <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>

   * @param comparator to compare items

   * @param serDe an instance of ArrayOfItemsSerDe

   * @return a ItemsSketch on the Java heap.

   */

  public static <T> ItemsSketch<T> getInstance(final Memory srcMem,

                                               final Comparator<? super T> comparator,

                                               final ArrayOfItemsSerDe<T> serDe) {

    }

    }

    //Not empty, must have valid preamble + min, max

    //can't check memory capacity here, not enough information

    //set class members

  }

  /**

   * Returns a copy of the given sketch

   * @param <T> the data type

   * @param sketch the given sketch

   * @return a copy of the given sketch

   */

  static <T> ItemsSketch<T> copy(final ItemsSketch<T> sketch) {

  }

  /**

   * Same as {@link #getCDF(Object[], QuantileSearchCriteria) getCDF(splitPoints, INCLUSIVE)}

   * @param splitPoints an array of <i>m</i> unique, monotonically increasing quantiles

   * @return a CDF array of m+1 double ranks (or probabilities) on the interval [0.0, 1.0).

   */

  public double[] getCDF(final T[] splitPoints) {

  }

  /**

   * Returns an approximation to the Cumulative Distribution Function (CDF) of the input stream

   * as a monotonically increasing array of double ranks (or probabilities) on the interval [0.0, 1.0],

   * given a set of splitPoints.

   * The last rank in the returned array is always 1.0.

   *

   * <p>The resulting approximations have a probabilistic guarantee that can be obtained from the

   * getNormalizedRankError(false) function.

   *

   * <p>If the sketch is empty this returns null.</p>

   *

   * @param splitPoints an array of <i>m</i> unique, monotonically increasing quantiles

   * that divide the real number line into <i>m+1</i> consecutive non-overlapping intervals.

   * It is not necessary to include either the minimum or maximum quantiles

   * of the input stream in these split points.

   *

   * <p>If searchCrit is INCLUSIVE, the definition of an "interval" is

   * exclusive of the left splitPoint and

   * inclusive of the right splitPoint.</p>

   *

   * <p>If searchCrit is EXCLUSIVE, the definition of an "interval" is

   * inclusive of the left splitPoint and

   * exclusive of the right splitPoint.</p>

   *

   *<p>The left "splitPoint" for the lowest interval is the

   * lowest quantile from the input stream retained by the sketch.

   * The right "splitPoint" for the highest interval is the

   * highest quantile from the input stream retained by the sketch.

   * </p>

   *

   * @param searchCrit if INCLUSIVE, the weight of a given splitPoint quantile,

   * if it also exists as retained quantile by the sketch,

   * is included into the interval below.

   * Otherwise, it is included into the interval above.

   *

   * @return an CDF array of m+1 double ranks (or probabilities) on the interval [0.0, 1.0).

   */

  public double[] getCDF(final T[] splitPoints, final QuantileSearchCriteria searchCrit) {

  }

  /**

   * Returns the maximum quantile of the stream. This is provided for convenience, but is distinct from the largest

   * quantile retained by the sketch algorithm.

   * If the sketch is empty this returns NaN.

   *

   * @return the maximum quantile of the stream

   */

  /**

   * Returns the minimum quantile of the stream. This is provided for convenience, but is distinct from the smallest

   * quantile retained by the sketch algorithm.

   * If the sketch is empty this returns NaN.

   *

   * @return the minimum quantile of the stream

   */

  /**

   * Same as {@link #getPMF(Object[], QuantileSearchCriteria) getPMF(splitPoints, INCLUSIVE)}

   * @param splitPoints an array of <i>m</i> unique, monotonically increasing quantiles

   * @return a PDF array of m+1 densities as double values on the interval [0.0, 1.0).

   */

  public double[] getPMF(final T[] splitPoints) {

  }

  /**

   * Returns an approximation to the Probability Mass Function (PMF) of the input stream

   * as an array of double value densities on the interval [0.0, 1.0],

   * given a set of splitPoints.

   * The sum of the densities in the returned array is always 1.0.

   *

   * <p>The resulting approximations have a probabilistic guarantee that can be obtained from the

   * getNormalizedRankError(true) function.

   *

   * <p>If the sketch is empty this returns null.</p>

   *

   * @param splitPoints an array of <i>m</i> unique, monotonically increasing quantiles

   * that divide the real number line into <i>m+1</i> consecutive non-overlapping intervals.

   * It is not necessary to include either the minimum or maximum quantiles

   * of the input stream in these split points.

   *

   * <p>If searchCrit is INCLUSIVE, the definition of an "interval" is

   * exclusive of the left splitPoint and

   * inclusive of the right splitPoint.</p>

   *

   * <p>If searchCrit is EXCLUSIVE, the definition of an "interval" is

   * inclusive of the left splitPoint and

   * exclusive of the right splitPoint.</p>

   *

   *<p>The left "splitPoint" for the lowest interval is the

   * lowest quantile from the input stream retained by the sketch.

   * The right "splitPoint" for the highest interval is the

   * highest quantile from the input stream retained by the sketch.

   * </p>

   *

   * @param searchCrit if INCLUSIVE, the weight of a given splitPoint quantile,

   * if it also exists as retained quantile by the sketch,

   * is included into the interval below.

   * Otherwise, it is included into the interval above.

   *

   * @return a PDF array of m+1 densities as double values on the interval [0.0, 1.0).

   */

  public double[] getPMF(final T[] splitPoints, final QuantileSearchCriteria searchCrit) {

  }

  /**

   * Same as {@link #getQuantile(double, QuantileSearchCriteria) getQuantile(rank, INCLUSIVE)}

   * @param rank the given normalized rank, a value in the range [0.0, 1.0].

   * @return the approximate quantile given the normalized rank.

   */

  public T getQuantile(final double rank) {

  }

  /**

   * Gets the approximate quantile of the given normalized rank and the given search criterion.

   *

   * <p>If the sketch is empty this returns NaN.</p>

   *

   * @param rank the given normalized rank, a value in the range [0.0, 1.0].

   * @param searchCrit is INCLUSIVE, the given rank includes all quantiles ≤

   * the quantile directly corresponding to the given rank.

   * @return the approximate quantile given the normalized rank.

   * @see org.apache.datasketches.QuantileSearchCriteria

   */

  public T getQuantile(final double rank, final QuantileSearchCriteria searchCrit) {

  }

  /**

   * Same as {@link #getQuantiles(double[], QuantileSearchCriteria) getQuantiles(ranks, INCLUSIVE)}

   * @param ranks the given array of normalized ranks, each of which must be

   * in the interval [0.0,1.0].

   * @return an array of quantiles corresponding to the given array of normalized ranks.

   */

  public T[] getQuantiles(final double[] ranks) {

  }

  /**

   * Gets an array of quantiles from the given array of normalized ranks.

   *

   * <p>If the sketch is empty this returns null.</p>

   *

   * @param ranks the given array of normalized ranks, each of which must be

   * in the interval [0.0,1.0].

   * @param searchCrit if INCLUSIVE, the given ranks include all quantiles ≤

   * the quantile directly corresponding to each rank.

   * @return an array of quantiles corresponding to the given array of normalized ranks.

   * @see org.apache.datasketches.QuantileSearchCriteria

   */

  @SuppressWarnings("unchecked")

  public T[] getQuantiles(final double[] ranks, final QuantileSearchCriteria searchCrit) {

    }

  }

  /**

   * Same as {@link #getQuantiles(int, QuantileSearchCriteria) getQuantiles(numEvenlySpaced, INCLUSIVE)}

   * @param numEvenlySpaced number of evenly spaced normalied ranks

   * @return an array of quantiles that are evenly spaced by their ranks.

   */

  public T[] getQuantiles(final int numEvenlySpaced) {

  }

  /**

   * This is a version of getQuantiles() where the caller only specifies the number of of desired evenly spaced,

   * normalized ranks, and returns an array of the corresponding quantiles.

   *

   * <p>If the sketch is empty this returns null.

   *

   * @param numEvenlySpaced an integer that specifies the number of evenly spaced normalized ranks.

   * This must be a positive integer greater than 0.

   * <ul><li>Let <i>Smallest</i> and <i>Largest</i> be the smallest and largest quantiles

   * retained by the sketch algorithm, respectively.

   * (This should not to be confused with {@link #getMinQuantile} and {@link #getMaxQuantile},

   * which are the smallest and largest values of the stream.)</li>

   * <li>A value of 1 will return the Smallest quantile.</li>

   * <li>A value of 2 will return the Smallest and Largest quantiles.</li>

   * <li>A value of 3 will return the Smallest, the Median, and the Largest quantiles.</li>

   * <li>Etc.</li>

   * </ul>

   *

   * @param searchCrit if INCLUSIVE, the given ranks include all quantiles ≤ the quantile directly corresponding to

   * each rank.

   * @return an array of quantiles that are evenly spaced by their ranks.

   * @see org.apache.datasketches.QuantileSearchCriteria

   */

  public T[] getQuantiles(final int numEvenlySpaced, final QuantileSearchCriteria searchCrit) {

  }

  /**

   * Gets the lower bound of the interval in which the true quantile of the given rank

   * exists with a confidence of at least 99%.

   * @param rank the given normalized rank

   * @return the lower bound of the interval in which the true quantile of the given rank

   * exists with a confidence of at least 99%. Returns NaN if the sketch is empty.

   */

  public T getQuantileLowerBound(final double rank) {

  }

  /**

   * Gets the upper bound of the interval in which the true quantile of the given rank

   * exists with a confidence of at least 99%.

   * @param rank the given normalized rank

   * @return the upper bound of the interval in which the true quantile of the given rank

   * exists with a confidence of at least 99%. Returns NaN if the sketch is empty.

   */

  public T getQuantileUpperBound(final double rank) {

  }

  /**

   * Same as {@link #getRank(Object, QuantileSearchCriteria) getRank(quantile, INCLUSIVE)}

   * @param quantile the given quantile

   * @return the normalized rank corresponding to the given quantile

   */

  public double getRank(final T quantile) {

  }

  /**

   * Gets the normalized rank corresponding to the given a quantile.

   *

   * <p>If the sketch is empty this returns NaN.</p>

   *

   * @param quantile the given quantile

   * @param searchCrit if INCLUSIVE the given quantile is included into the rank.

   * @return the normalized rank corresponding to the given quantile

   * @see org.apache.datasketches.QuantileSearchCriteria

   */

  public double getRank(final T quantile, final QuantileSearchCriteria searchCrit) {

  }

  /**

   * Same as {@link #getRanks(Object[], QuantileSearchCriteria) getRanks(quantiles, INCLUSIVE)}

   * @param quantiles the given array of quantiles

   * @return an array of normalized ranks corresponding to the given array of quantiles.

   */

  public double[] getRanks(final T[] quantiles) {

  }

  /**

   * Gets an array of normalized ranks corresponding to the given array of quantiles and the given

   * search criterion.

   *

   * <p>If the sketch is empty this returns null.</p>

   *

   * @param quantiles the given array of quantiles

   * @param searchCrit if INCLUSIVE, the given quantiles include the rank directly corresponding to each quantile.

   * @return an array of normalized ranks corresponding to the given array of quantiles.

   * @see org.apache.datasketches.QuantileSearchCriteria

   */

  public double[] getRanks(final T[] quantiles, final QuantileSearchCriteria searchCrit) {

    }

  }

  /**

   * Gets the iterator for this sketch, which is not sorted.

   * @return the iterator for this sketch

   */

  public QuantilesGenericSketchIterator<T> iterator() {

  }

  @Override

  public int getK() {

  }

  @Override

  public long getN() {

  }

  /**

   * Gets the approximate rank error of this sketch normalized as a fraction between zero and one.

   * @param pmf if true, returns the "double-sided" normalized rank error for the getPMF() function.

   * Otherwise, it is the "single-sided" normalized rank error for all the other queries.

   * @return if pmf is true, returns the normalized rank error for the getPMF() function.

   * Otherwise, it is the "single-sided" normalized rank error for all the other queries.

   */

  public double getNormalizedRankError(final boolean pmf) {

  }

  /**

   * Gets the normalized rank error given k and pmf.

   * Static method version of the {@link #getNormalizedRankError(boolean)}.

   * @param k the configuation parameter

   * @param pmf if true, returns the "double-sided" normalized rank error for the getPMF() function.

   * Otherwise, it is the "single-sided" normalized rank error for all the other queries.

   * @return if pmf is true, the normalized rank error for the getPMF() function.

   * Otherwise, it is the "single-sided" normalized rank error for all the other queries.

   */

  public static double getNormalizedRankError(final int k, final boolean pmf) {

  }

  /**

   * Gets the approximate value of <em>k</em> to use given epsilon, the normalized rank error.

   * @param epsilon the normalized rank error between zero and one.

   * @param pmf if true, this function returns the value of <em>k</em> assuming the input epsilon

   * is the desired "double-sided" epsilon for the getPMF() function. Otherwise, this function

   * returns the value of <em>k</em> assuming the input epsilon is the desired "single-sided"

   * epsilon for all the other queries.

   * @return the value of <i>k</i> given a value of epsilon.

   */

  public static int getKFromEpsilon(final double epsilon, final boolean pmf) {

  }

  @Override

  public boolean hasMemory() {

  }

  @Override

  public boolean isEmpty() {

  }

  @Override

  public boolean isDirect() {

  }

  @Override

  public boolean isEstimationMode() {

  }

  @Override

  public boolean isReadOnly() {

  }

  /**

   * {@inheritDoc}

   * <p>The parameter <i>k</i> will not change.</p>

   */

  @Override

  public void reset() {

  /**

   * Serialize this sketch to a byte array form.

   * @param serDe an instance of ArrayOfItemsSerDe

   * @return byte array of this sketch

   */

  public byte[] toByteArray(final ArrayOfItemsSerDe<T> serDe) {

  }

  /**

   * Serialize this sketch to a byte array form.

   * @param ordered if true the base buffer will be ordered (default == false).

   * @param serDe an instance of ArrayOfItemsSerDe

   * @return this sketch in a byte array form.

   */

  public byte[] toByteArray(final boolean ordered, final ArrayOfItemsSerDe<T> serDe) {

  }

  @Override

  public String toString() {

  }

  /**

   * Returns summary information about this sketch. Used for debugging.

   * @param sketchSummary if true includes sketch summary

   * @param dataDetail if true includes data detail

   * @return summary information about the sketch.

   */

  public String toString(final boolean sketchSummary, final boolean dataDetail) {

  }

  /**

   * Returns a human readable string of the preamble of a byte array image of an ItemsSketch.

   * @param byteArr the given byte array

   * @return a human readable string of the preamble of a byte array image of an ItemsSketch.

   */

  public static String toString(final byte[] byteArr) {

  }

  /**

   * Returns a human readable string of the preamble of a Memory image of an ItemsSketch.

   * @param mem the given Memory

   * @return a human readable string of the preamble of a Memory image of an ItemsSketch.

   */

  public static String toString(final Memory mem) {

  }

  /**

   * From an existing sketch, this creates a new sketch that can have a smaller value of K.

   * The original sketch is not modified.

   *

   * @param newK the new value of K that must be smaller than current value of K.

   * It is required that this.getK() = newK * 2^(nonnegative integer).

   * @return the new sketch.

   */

  public ItemsSketch<T> downSample(final int newK) {

  }

  @Override

  public int getNumRetained() {

  }

  /**

   * Puts the current sketch into the given Memory if there is sufficient space.

   * Otherwise, throws an error.

   *

   * @param dstMem the given memory.

   * @param serDe an instance of ArrayOfItemsSerDe

   */

  public void putMemory(final WritableMemory dstMem, final ArrayOfItemsSerDe<T> serDe) {

          "Destination Memory not large enough: " + memCap + " < " + byteArr.length);

    }

  /**

   * Gets the sorted view of this sketch

   * @return the sorted view of this sketch

   */

  public GenericSortedView<T> getSortedView() {

  }

  /**

   * Updates this sketch with the given quantile

   * @param quantile from a stream of quantiles. Nulls are ignored.

   */

  public void update(final T quantile) {

    // this method only uses the base buffer part of the combined buffer

    }

    }

  // Restricted

  private final void refreshSortedView() {

  /**

   * Returns the base buffer count

   * @return the base buffer count

   */

  int getBaseBufferCount() {

  }

  /**

   * Returns the allocated count for the combined base buffer

   * @return the allocated count for the combined base buffer

   */

  int getCombinedBufferAllocatedCount() {

  }

  /**

   * Returns the bit pattern for valid log levels

   * @return the bit pattern for valid log levels

   */

  long getBitPattern() {

  }

  /**

   * Returns the combined buffer reference

   * @return the combined buffer reference

   */

  Object[] getCombinedBuffer() {

  }

  Comparator<? super T> getComparator() {

  }

  /**

   * Loads the Combined Buffer, min and max from the given items array.

   * The Combined Buffer is always in non-compact form and must be pre-allocated.

   * @param itemsArray the given items array

   */

  private void itemsArrayToCombinedBuffer(final T[] itemsArray) {

    //Load min, max

    //Load base buffer

    //Load levels

        }

      }

    }

  private static <T> void growBaseBuffer(final ItemsSketch<T> sketch) {

}