apache / datasketches-java / #64

Build # #64

Build Type

push

Committed by

Commit Message

<a href="https://github.com/apache/datasketches-java/commit/<a class=hub.com/apache/datasketches-java/commit/<a class="double-link" href="https://git"><a class=hub.com/apache/datasketches-java/commit/<a class="double-link" href="https://git"><a class=hub.com/apache/datasketches-java/commit/244fee80cc01b5f369bbae423933144114fc58e5">244fee80c<a href="https://github.com/apache/datasketches-java/commit/244fee80cc01b5f369bbae423933144114fc58e5">&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/apache/datasketches-java/commit/&lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/apache/datasketches-java/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/apache/datasketches-java/commit/244fee80cc01b5f369bbae423933144114fc58e5&quot;&gt;244fee80c&lt;/a&gt;&lt;a href=&quot;https://github.com/apache/datasketches-java/commit/244fee80cc01b5f369bbae423933144114fc58e5&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/apache/datasketches-java/commit/244fee80cc01b5f369bbae4239331441&lt;/a&gt;14fc58e5&quot;>&quot;&gt;Merge &lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/apache/datasketches-java/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/apache/datasketches-java/commit/<a class="double-link" href="https://github.com/apache/datasketches-java/commit/99d95dbe98adb4cec85c433875c9b5b957547e3a">99d95dbe9</a><a href="https://github.com/apache/datasketches-java/commit/244fee80cc01b5f369bbae423933144114fc58e5">&amp;quot;&amp;gt;99d95dbe9&amp;lt;/a&amp;gt;&amp;quot;&amp;gt;99d95dbe9&amp;lt;/a&amp;gt;&amp;lt;a href=&amp;quot;https://github.com/apache/datasketches-java/commit/244fee80cc01b5f369bbae423933144114fc5&lt;/a&gt;8e5&quot;&gt; into &lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/apache/datasketches-java/commit/<a class="double-link" href="https://github.com/apache/datasketches-java/commit/5f13ff218">5f13ff218">5f13ff218</a>

Run Details

10 of 10 new or added lines in 5 files covered. (100.0%)

17497 of 17728 relevant lines covered (98.7%)

0.99 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.95

/src/main/java/org/apache/datasketches/quantiles/Util.java

/*
 * 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.abs;
import static java.lang.Math.ceil;
import static java.lang.Math.exp;
import static java.lang.Math.log;
import static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.pow;
import static java.lang.Math.round;
import static org.apache.datasketches.Util.ceilingPowerOf2;
import static org.apache.datasketches.Util.isPowerOf2;
import static org.apache.datasketches.quantiles.DoublesSketch.MAX_K;
import static org.apache.datasketches.quantiles.DoublesSketch.MIN_K;
import static org.apache.datasketches.quantiles.PreambleUtil.COMPACT_FLAG_MASK;
import static org.apache.datasketches.quantiles.PreambleUtil.EMPTY_FLAG_MASK;
import static org.apache.datasketches.quantiles.PreambleUtil.ORDERED_FLAG_MASK;
import static org.apache.datasketches.quantiles.PreambleUtil.READ_ONLY_FLAG_MASK;
import static org.apache.datasketches.quantiles.PreambleUtil.extractFlags;

import org.apache.datasketches.Family;
import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.memory.Memory;

/**
 * Utility class for quantiles sketches.
 *
 * <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 Lee Rhodes
 */
final class Util {

  private Util() {}

  /**
   * The java line separator character as a String.
   */
  static final String LS = System.getProperty("line.separator");

  /**
   * The tab character
   */
  static final char TAB = '\t';

  /**
   * Computes the raw delta area between two quantile sketches for the
   * <i>kolmogorovSmirnovTest(DoublesSketch, DoublesSketch, double)</i>
   * method.
   * @param sketch1 Input DoubleSketch 1
   * @param sketch2 Input DoubleSketch 2
   * @return the raw delta area between two quantile sketches
   * @deprecated 2.0.0 See class <i>KolmogorovSmirnov</i>
   */
  @Deprecated
  public static double computeKSDelta(final DoublesSketch sketch1, final DoublesSketch sketch2) {
    return KolmogorovSmirnov.computeKSDelta(sketch1, sketch2);
  }

  /**
   * Computes the adjusted delta area threshold for the
   * <i>kolmogorovSmirnovTest(DoublesSketch, DoublesSketch, double)</i>
   * method.
   * This adjusts the computed threshold by the error epsilons of the two given sketches.
   * See <a href="https://en.wikipedia.org/wiki/Kolmogorov-Smirnov_test">Kolmogorov–Smirnov Test</a>
   * @param sketch1 Input DoubleSketch 1
   * @param sketch2 Input DoubleSketch 2
   * @param tgtPvalue Target p-value. Typically .001 to .1, e.g., .05.
   * @return the adjusted threshold to be compared with the raw delta area.
   * @deprecated 2.0.0 See class <i>KolmogorovSmirnov</i>
   */
  @Deprecated
  public static double computeKSThreshold(final DoublesSketch sketch1,
                                           final DoublesSketch sketch2,
                                           final double tgtPvalue) {
    return KolmogorovSmirnov.computeKSThreshold(sketch1, sketch2, tgtPvalue);
  }

  /**
   * Performs the Kolmogorov-Smirnov Test between two quantiles sketches.
   * Note: if the given sketches have insufficient data or if the sketch sizes are too small,
   * this will return false.
   * @param sketch1 Input DoubleSketch 1
   * @param sketch2 Input DoubleSketch 2
   * @param tgtPvalue Target p-value. Typically .001 to .1, e.g., .05.
   * @return Boolean indicating whether we can reject the null hypothesis (that the sketches
   * reflect the same underlying distribution) using the provided tgtPValue.
   * @deprecated 2.0.0 See class <i>KolmogorovSmirnov</i>
   */
  @Deprecated
  public static boolean kolmogorovSmirnovTest(final DoublesSketch sketch1,
      final DoublesSketch sketch2, final double tgtPvalue) {
    return KolmogorovSmirnov.kolmogorovSmirnovTest(sketch1, sketch2, tgtPvalue);
  }

  /**
   * Gets the normalized rank error given k and pmf for the Quantiles DoubleSketch and ItemsSketch.
   * @param k the configuration 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.
   */
  // constants were derived as the best fit to 99 percentile empirically measured max error in
  // thousands of trials
  public static double getNormalizedRankError(final int k, final boolean pmf) {
    return pmf
        ? 1.854 / pow(k, 0.9657)
        : 1.576 / pow(k, 0.9726);
  }

  /**
   * Gets the approximate value of <em>k</em> to use given epsilon, the normalized rank error
   * for the Quantiles DoubleSketch and ItemsSketch.
   * @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.
   */
  // constants were derived as the best fit to 99 percentile empirically measured max error in
  // thousands of trials
  public static int getKFromEpsilon(final double epsilon, final boolean pmf) {
    //Ensure that eps is >= than the lowest possible eps given MAX_K and pmf=false.
    final double eps = max(epsilon, 6.395E-5);
    final double kdbl = pmf
        ? exp(log(1.854 / eps) / 0.9657)
        : exp(log(1.576 / eps) / 0.9726);
    final double krnd = round(kdbl);
    final double del = abs(krnd - kdbl);
    //round to closest int if within 1 ppm of the int, otherwise use the ceiling.
    final int k = (int) ((del < 1E-6) ? krnd : ceil(kdbl));
    return max(MIN_K, min(MAX_K, k));
  }

  /**
   * Checks the validity of the given value k
   * @param k must be greater than 1 and less than 65536 and a power of 2.
   */
  static void checkK(final int k) {
    if ((k < MIN_K) || (k > MAX_K) || !isPowerOf2(k)) {
      throw new SketchesArgumentException(
          "K must be >= " + MIN_K + " and <= " + MAX_K + " and a power of 2: " + k);
    }
  }

  /**
   * Checks the validity of the given family ID
   * @param familyID the given family ID
   */
  static void checkFamilyID(final int familyID) {
    final Family family = Family.idToFamily(familyID);
    if (!family.equals(Family.QUANTILES)) {
      throw new SketchesArgumentException(
          "Possible corruption: Invalid Family: " + family.toString());
    }
  }

  /**
   * Checks the consistency of the flag bits and the state of preambleLong and the memory
   * capacity and returns the empty state.
   * @param preambleLongs the size of preamble in longs
   * @param flags the flags field
   * @param memCapBytes the memory capacity
   * @return the value of the empty state
   */
  static boolean checkPreLongsFlagsCap(final int preambleLongs, final int flags, final long memCapBytes) {
    final boolean empty = (flags & EMPTY_FLAG_MASK) > 0; //Preamble flags empty state
    final int minPre = Family.QUANTILES.getMinPreLongs(); //1
    final int maxPre = Family.QUANTILES.getMaxPreLongs(); //2
    final boolean valid = ((preambleLongs == minPre) && empty) || ((preambleLongs == maxPre) && !empty);
    if (!valid) {
      throw new SketchesArgumentException(
          "Possible corruption: PreambleLongs inconsistent with empty state: " + preambleLongs);
    }
    checkHeapFlags(flags);
    if (memCapBytes < (preambleLongs << 3)) {
      throw new SketchesArgumentException(
          "Possible corruption: Insufficient capacity for preamble: " + memCapBytes);
    }
    return empty;
  }

  /**
   * Checks just the flags field of the preamble. Allowed flags are Read Only, Empty, Compact, and
   * ordered.
   * @param flags the flags field
   */
  static void checkHeapFlags(final int flags) {  //only used by checkPreLongsFlagsCap and test
    final int allowedFlags =
        READ_ONLY_FLAG_MASK | EMPTY_FLAG_MASK | COMPACT_FLAG_MASK | ORDERED_FLAG_MASK;
    final int flagsMask = ~allowedFlags;
    if ((flags & flagsMask) > 0) {
      throw new SketchesArgumentException(
         "Possible corruption: Invalid flags field: " + Integer.toBinaryString(flags));
    }
  }

  /**
   * Checks just the flags field of an input Memory object. Returns true for a compact
   * sketch, false for an update sketch. Does not perform additional checks, including sketch
   * family.
   * @param srcMem the source Memory containing a sketch
   * @return true if flags indicate a compact sketch, otherwise false
   */
  static boolean checkIsCompactMemory(final Memory srcMem) {
    // only reading so downcast is ok
    final int flags = extractFlags(srcMem);
    final int compactFlags = READ_ONLY_FLAG_MASK | COMPACT_FLAG_MASK;
    return (flags & compactFlags) > 0;
  }

  /**
   * Checks the sequential validity of the given array of double values.
   * They must be unique, monotonically increasing and not NaN.
   * @param values the given array of double values
   */
  static final void checkSplitPointsOrder(final double[] values) {
    if (values == null) {
      throw new SketchesArgumentException("Values cannot be null.");
    }
    final int lenM1 = values.length - 1;
    for (int j = 0; j < lenM1; j++) {
      if (values[j] < values[j + 1]) { continue; }
      throw new SketchesArgumentException(
          "Values must be unique, monotonically increasing and not NaN.");
    }
  }

  /**
   * Checks that the given fractional rank: <i>0 &le; frank &le; 1.0</i>.
   * @param frank the given fractional rank.
   */
  static final void checkFractionalRankBounds(final double frank) {
    if ((frank < 0.0) || (frank > 1.0)) {
      throw new SketchesArgumentException(
        "Fractional rank must be >= 0 and <= 1.0: " + frank);
    }
  }

  /**
   * Returns the number of retained valid items in the sketch given k and n.
   * @param k the given configured k of the sketch
   * @param n the current number of items seen by the sketch
   * @return the number of retained items in the sketch given k and n.
   */
  static int computeRetainedItems(final int k, final long n) {
    final int bbCnt = computeBaseBufferItems(k, n);
    final long bitPattern = computeBitPattern(k, n);
    final int validLevels = computeValidLevels(bitPattern);
    return bbCnt + (validLevels * k);
  }

  /**
   * Returns the total item capacity of an updatable, non-compact combined buffer
   * given <i>k</i> and <i>n</i>.  If total levels = 0, this returns the ceiling power of 2
   * size for the base buffer or the MIN_BASE_BUF_SIZE, whichever is larger.
   *
   * @param k sketch parameter. This determines the accuracy of the sketch and the
   * size of the updatable data structure, which is a function of <i>k</i> and <i>n</i>.
   *
   * @param n The number of items in the input stream
   * @return the current item capacity of the combined buffer
   */
  static int computeCombinedBufferItemCapacity(final int k, final long n) {
    final int totLevels = computeNumLevelsNeeded(k, n);
    if (totLevels == 0) {
      final int bbItems = computeBaseBufferItems(k, n);
      return Math.max(2 * DoublesSketch.MIN_K, ceilingPowerOf2(bbItems));
    }
    return (2 + totLevels) * k;
  }

  /**
   * Computes the number of valid levels above the base buffer
   * @param bitPattern the bit pattern
   * @return the number of valid levels above the base buffer
   */
  static int computeValidLevels(final long bitPattern) {
    return Long.bitCount(bitPattern);
  }

  /**
   * Computes the total number of logarithmic levels above the base buffer given the bitPattern.
   * @param bitPattern the given bit pattern
   * @return the total number of logarithmic levels above the base buffer
   */
  static int computeTotalLevels(final long bitPattern) {
    return hiBitPos(bitPattern) + 1;
  }

  /**
   * Computes the total number of logarithmic levels above the base buffer given k and n.
   * This is equivalent to max(floor(lg(n/k), 0).
   * Returns zero if n is less than 2 * k.
   * @param k the configured size of the sketch
   * @param n the total values presented to the sketch.
   * @return the total number of levels needed.
   */
  static int computeNumLevelsNeeded(final int k, final long n) {
    return 1 + hiBitPos(n / (2L * k));
  }

  /**
   * Computes the number of base buffer items given k, n
   * @param k the configured size of the sketch
   * @param n the total values presented to the sketch
   * @return the number of base buffer items
   */
  static int computeBaseBufferItems(final int k, final long n) {
    return (int) (n % (2L * k));
  }

  /**
   * Computes the levels bit pattern given k, n.
   * This is computed as <i>n / (2*k)</i>.
   * @param k the configured size of the sketch
   * @param n the total values presented to the sketch.
   * @return the levels bit pattern
   */
  static long computeBitPattern(final int k, final long n) {
    return n / (2L * k);
  }

  /**
   * Returns the log_base2 of x
   * @param x the given x
   * @return the log_base2 of x
   */
  static double lg(final double x) {
    return ( Math.log(x) / Math.log(2.0) );
  }

  /**
   * Zero-based position of the highest one-bit of the given long.
   * Returns minus one if num is zero.
   * @param num the given long
   * @return Zero-based position of the highest one-bit of the given long
   */
  static int hiBitPos(final long num) {
    return 63 - Long.numberOfLeadingZeros(num);
  }

  /**
   * Returns the zero-based bit position of the lowest zero bit of <i>bits</i> starting at
   * <i>startingBit</i>. If input is all ones, this returns 64.
   * @param bits the input bits as a long
   * @param startingBit the zero-based starting bit position. Only the low 6 bits are used.
   * @return the zero-based bit position of the lowest zero bit starting at <i>startingBit</i>.
   */
  static int lowestZeroBitStartingAt(final long bits, final int startingBit) {
    int pos = startingBit & 0X3F;
    long myBits = bits >>> pos;

    while ((myBits & 1L) != 0) {
      myBits = myBits >>> 1;
      pos++;
    }
    return pos;
  }

}

1	/*
2	* Licensed to the Apache Software Foundation (ASF) under one
3	* or more contributor license agreements. See the NOTICE file
4	* distributed with this work for additional information
5	* regarding copyright ownership. The ASF licenses this file
6	* to you under the Apache License, Version 2.0 (the
7	* "License"); you may not use this file except in compliance
8	* with the License. You may obtain a copy of the License at
9	*
10	* http://www.apache.org/licenses/LICENSE-2.0
11	*
12	* Unless required by applicable law or agreed to in writing,
13	* software distributed under the License is distributed on an
14	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15	* KIND, either express or implied. See the License for the
16	* specific language governing permissions and limitations
17	* under the License.
18	*/
19
20	package org.apache.datasketches.quantiles;
21
22	import static java.lang.Math.abs;
23	import static java.lang.Math.ceil;
24	import static java.lang.Math.exp;
25	import static java.lang.Math.log;
26	import static java.lang.Math.max;
27	import static java.lang.Math.min;
28	import static java.lang.Math.pow;
29	import static java.lang.Math.round;
30	import static org.apache.datasketches.Util.ceilingPowerOf2;
31	import static org.apache.datasketches.Util.isPowerOf2;
32	import static org.apache.datasketches.quantiles.DoublesSketch.MAX_K;
33	import static org.apache.datasketches.quantiles.DoublesSketch.MIN_K;
34	import static org.apache.datasketches.quantiles.PreambleUtil.COMPACT_FLAG_MASK;
35	import static org.apache.datasketches.quantiles.PreambleUtil.EMPTY_FLAG_MASK;
36	import static org.apache.datasketches.quantiles.PreambleUtil.ORDERED_FLAG_MASK;
37	import static org.apache.datasketches.quantiles.PreambleUtil.READ_ONLY_FLAG_MASK;
38	import static org.apache.datasketches.quantiles.PreambleUtil.extractFlags;
39
40	import org.apache.datasketches.Family;
41	import org.apache.datasketches.SketchesArgumentException;
42	import org.apache.datasketches.memory.Memory;
43
44	/**
45	* Utility class for quantiles sketches.
46	*
47	* <p>This class contains a highly specialized sort called blockyTandemMergeSort().
48	* It also contains methods that are used while building histograms and other common
49	* functions.</p>
50	*
51	* @author Lee Rhodes
52	*/
53	final class Util {
54
55	private Util() {}
56
57	/**
58	* The java line separator character as a String.
59	*/
60	static final String LS = System.getProperty("line.separator");	1✔
61
62	/**
63	* The tab character
64	*/
65	static final char TAB = '\t';
66
67	/**
68	* Computes the raw delta area between two quantile sketches for the
69	* <i>kolmogorovSmirnovTest(DoublesSketch, DoublesSketch, double)</i>
70	* method.
71	* @param sketch1 Input DoubleSketch 1
72	* @param sketch2 Input DoubleSketch 2
73	* @return the raw delta area between two quantile sketches
74	* @deprecated 2.0.0 See class <i>KolmogorovSmirnov</i>
75	*/
76	@Deprecated
77	public static double computeKSDelta(final DoublesSketch sketch1, final DoublesSketch sketch2) {
78	return KolmogorovSmirnov.computeKSDelta(sketch1, sketch2);	×
79	}
80
81	/**
82	* Computes the adjusted delta area threshold for the
83	* <i>kolmogorovSmirnovTest(DoublesSketch, DoublesSketch, double)</i>
84	* method.
85	* This adjusts the computed threshold by the error epsilons of the two given sketches.
86	* See <a href="https://en.wikipedia.org/wiki/Kolmogorov-Smirnov_test">Kolmogorov–Smirnov Test</a>
87	* @param sketch1 Input DoubleSketch 1
88	* @param sketch2 Input DoubleSketch 2
89	* @param tgtPvalue Target p-value. Typically .001 to .1, e.g., .05.
90	* @return the adjusted threshold to be compared with the raw delta area.
91	* @deprecated 2.0.0 See class <i>KolmogorovSmirnov</i>
92	*/
93	@Deprecated
94	public static double computeKSThreshold(final DoublesSketch sketch1,
95	final DoublesSketch sketch2,
96	final double tgtPvalue) {
97	return KolmogorovSmirnov.computeKSThreshold(sketch1, sketch2, tgtPvalue);	×
98	}
99
100	/**
101	* Performs the Kolmogorov-Smirnov Test between two quantiles sketches.
102	* Note: if the given sketches have insufficient data or if the sketch sizes are too small,
103	* this will return false.
104	* @param sketch1 Input DoubleSketch 1
105	* @param sketch2 Input DoubleSketch 2
106	* @param tgtPvalue Target p-value. Typically .001 to .1, e.g., .05.
107	* @return Boolean indicating whether we can reject the null hypothesis (that the sketches
108	* reflect the same underlying distribution) using the provided tgtPValue.
109	* @deprecated 2.0.0 See class <i>KolmogorovSmirnov</i>
110	*/
111	@Deprecated
112	public static boolean kolmogorovSmirnovTest(final DoublesSketch sketch1,
113	final DoublesSketch sketch2, final double tgtPvalue) {
114	return KolmogorovSmirnov.kolmogorovSmirnovTest(sketch1, sketch2, tgtPvalue);	×
115	}
116
117	/**
118	* Gets the normalized rank error given k and pmf for the Quantiles DoubleSketch and ItemsSketch.
119	* @param k the configuration parameter
120	* @param pmf if true, returns the "double-sided" normalized rank error for the getPMF() function.
121	* Otherwise, it is the "single-sided" normalized rank error for all the other queries.
122	* @return if pmf is true, the normalized rank error for the getPMF() function.
123	* Otherwise, it is the "single-sided" normalized rank error for all the other queries.
124	*/
125	// constants were derived as the best fit to 99 percentile empirically measured max error in
126	// thousands of trials
127	public static double getNormalizedRankError(final int k, final boolean pmf) {
128	return pmf	1✔
129	? 1.854 / pow(k, 0.9657)	1✔
130	: 1.576 / pow(k, 0.9726);	1✔
131	}
132
133	/**
134	* Gets the approximate value of <em>k</em> to use given epsilon, the normalized rank error
135	* for the Quantiles DoubleSketch and ItemsSketch.
136	* @param epsilon the normalized rank error between zero and one.
137	* @param pmf if true, this function returns the value of <em>k</em> assuming the input epsilon
138	* is the desired "double-sided" epsilon for the getPMF() function. Otherwise, this function
139	* returns the value of <em>k</em> assuming the input epsilon is the desired "single-sided"
140	* epsilon for all the other queries.
141	* @return the value of <i>k</i> given a value of epsilon.
142	*/
143	// constants were derived as the best fit to 99 percentile empirically measured max error in
144	// thousands of trials
145	public static int getKFromEpsilon(final double epsilon, final boolean pmf) {
146	//Ensure that eps is >= than the lowest possible eps given MAX_K and pmf=false.
147	final double eps = max(epsilon, 6.395E-5);	1✔
148	final double kdbl = pmf	1✔
149	? exp(log(1.854 / eps) / 0.9657)	1✔
150	: exp(log(1.576 / eps) / 0.9726);	1✔
151	final double krnd = round(kdbl);	1✔
152	final double del = abs(krnd - kdbl);	1✔
153	//round to closest int if within 1 ppm of the int, otherwise use the ceiling.
154	final int k = (int) ((del < 1E-6) ? krnd : ceil(kdbl));	1✔
155	return max(MIN_K, min(MAX_K, k));	1✔
156	}
157
158	/**
159	* Checks the validity of the given value k
160	* @param k must be greater than 1 and less than 65536 and a power of 2.
161	*/
162	static void checkK(final int k) {
163	if ((k < MIN_K) \|\| (k > MAX_K) \|\| !isPowerOf2(k)) {	1✔
164	throw new SketchesArgumentException(	1✔
165	"K must be >= " + MIN_K + " and <= " + MAX_K + " and a power of 2: " + k);
166	}
167	}	1✔
168
169	/**
170	* Checks the validity of the given family ID
171	* @param familyID the given family ID
172	*/
173	static void checkFamilyID(final int familyID) {
174	final Family family = Family.idToFamily(familyID);	1✔
175	if (!family.equals(Family.QUANTILES)) {	1✔
176	throw new SketchesArgumentException(	1✔
177	"Possible corruption: Invalid Family: " + family.toString());	1✔
178	}
179	}	1✔
180
181	/**
182	* Checks the consistency of the flag bits and the state of preambleLong and the memory
183	* capacity and returns the empty state.
184	* @param preambleLongs the size of preamble in longs
185	* @param flags the flags field
186	* @param memCapBytes the memory capacity
187	* @return the value of the empty state
188	*/
189	static boolean checkPreLongsFlagsCap(final int preambleLongs, final int flags, final long memCapBytes) {
190	final boolean empty = (flags & EMPTY_FLAG_MASK) > 0; //Preamble flags empty state	1✔
191	final int minPre = Family.QUANTILES.getMinPreLongs(); //1	1✔
192	final int maxPre = Family.QUANTILES.getMaxPreLongs(); //2	1✔
193	final boolean valid = ((preambleLongs == minPre) && empty) \|\| ((preambleLongs == maxPre) && !empty);	1✔
194	if (!valid) {	1✔
195	throw new SketchesArgumentException(	1✔
196	"Possible corruption: PreambleLongs inconsistent with empty state: " + preambleLongs);
197	}
198	checkHeapFlags(flags);	1✔
199	if (memCapBytes < (preambleLongs << 3)) {	1✔
200	throw new SketchesArgumentException(	1✔
201	"Possible corruption: Insufficient capacity for preamble: " + memCapBytes);
202	}
203	return empty;	1✔
204	}
205
206	/**
207	* Checks just the flags field of the preamble. Allowed flags are Read Only, Empty, Compact, and
208	* ordered.
209	* @param flags the flags field
210	*/
211	static void checkHeapFlags(final int flags) { //only used by checkPreLongsFlagsCap and test
212	final int allowedFlags =	1✔
213	READ_ONLY_FLAG_MASK \| EMPTY_FLAG_MASK \| COMPACT_FLAG_MASK \| ORDERED_FLAG_MASK;
214	final int flagsMask = ~allowedFlags;	1✔
215	if ((flags & flagsMask) > 0) {	1✔
216	throw new SketchesArgumentException(	1✔
217	"Possible corruption: Invalid flags field: " + Integer.toBinaryString(flags));	1✔
218	}
219	}	1✔
220
221	/**
222	* Checks just the flags field of an input Memory object. Returns true for a compact
223	* sketch, false for an update sketch. Does not perform additional checks, including sketch
224	* family.
225	* @param srcMem the source Memory containing a sketch
226	* @return true if flags indicate a compact sketch, otherwise false
227	*/
228	static boolean checkIsCompactMemory(final Memory srcMem) {
229	// only reading so downcast is ok
230	final int flags = extractFlags(srcMem);	1✔
231	final int compactFlags = READ_ONLY_FLAG_MASK \| COMPACT_FLAG_MASK;	1✔
232	return (flags & compactFlags) > 0;	1✔
233	}
234
235	/**
236	* Checks the sequential validity of the given array of double values.
237	* They must be unique, monotonically increasing and not NaN.
238	* @param values the given array of double values
239	*/
240	static final void checkSplitPointsOrder(final double[] values) {
241	if (values == null) {	1✔
242	throw new SketchesArgumentException("Values cannot be null.");	1✔
243	}
244	final int lenM1 = values.length - 1;	1✔
245	for (int j = 0; j < lenM1; j++) {	1✔
246	if (values[j] < values[j + 1]) { continue; }	1✔
247	throw new SketchesArgumentException(	1✔
248	"Values must be unique, monotonically increasing and not NaN.");
249	}
250	}	1✔
251
252	/**
253	* Checks that the given fractional rank: <i>0 ≤ frank ≤ 1.0</i>.
254	* @param frank the given fractional rank.
255	*/
256	static final void checkFractionalRankBounds(final double frank) {
257	if ((frank < 0.0) \|\| (frank > 1.0)) {	1✔
258	throw new SketchesArgumentException(	1✔
259	"Fractional rank must be >= 0 and <= 1.0: " + frank);
260	}
261	}	1✔
262
263	/**
264	* Returns the number of retained valid items in the sketch given k and n.
265	* @param k the given configured k of the sketch
266	* @param n the current number of items seen by the sketch
267	* @return the number of retained items in the sketch given k and n.
268	*/
269	static int computeRetainedItems(final int k, final long n) {
270	final int bbCnt = computeBaseBufferItems(k, n);	1✔
271	final long bitPattern = computeBitPattern(k, n);	1✔
272	final int validLevels = computeValidLevels(bitPattern);	1✔
273	return bbCnt + (validLevels * k);	1✔
274	}
275
276	/**
277	* Returns the total item capacity of an updatable, non-compact combined buffer
278	* given <i>k</i> and <i>n</i>. If total levels = 0, this returns the ceiling power of 2
279	* size for the base buffer or the MIN_BASE_BUF_SIZE, whichever is larger.
280	*
281	* @param k sketch parameter. This determines the accuracy of the sketch and the
282	* size of the updatable data structure, which is a function of <i>k</i> and <i>n</i>.
283	*
284	* @param n The number of items in the input stream
285	* @return the current item capacity of the combined buffer
286	*/
287	static int computeCombinedBufferItemCapacity(final int k, final long n) {
288	final int totLevels = computeNumLevelsNeeded(k, n);	1✔
289	if (totLevels == 0) {	1✔
290	final int bbItems = computeBaseBufferItems(k, n);	1✔
291	return Math.max(2 * DoublesSketch.MIN_K, ceilingPowerOf2(bbItems));	1✔
292	}
293	return (2 + totLevels) * k;	1✔
294	}
295
296	/**
297	* Computes the number of valid levels above the base buffer
298	* @param bitPattern the bit pattern
299	* @return the number of valid levels above the base buffer
300	*/
301	static int computeValidLevels(final long bitPattern) {
302	return Long.bitCount(bitPattern);	1✔
303	}
304
305	/**
306	* Computes the total number of logarithmic levels above the base buffer given the bitPattern.
307	* @param bitPattern the given bit pattern
308	* @return the total number of logarithmic levels above the base buffer
309	*/
310	static int computeTotalLevels(final long bitPattern) {
311	return hiBitPos(bitPattern) + 1;	1✔
312	}
313
314	/**
315	* Computes the total number of logarithmic levels above the base buffer given k and n.
316	* This is equivalent to max(floor(lg(n/k), 0).
317	* Returns zero if n is less than 2 * k.
318	* @param k the configured size of the sketch
319	* @param n the total values presented to the sketch.
320	* @return the total number of levels needed.
321	*/
322	static int computeNumLevelsNeeded(final int k, final long n) {
323	return 1 + hiBitPos(n / (2L * k));	1✔
324	}
325
326	/**
327	* Computes the number of base buffer items given k, n
328	* @param k the configured size of the sketch
329	* @param n the total values presented to the sketch
330	* @return the number of base buffer items
331	*/
332	static int computeBaseBufferItems(final int k, final long n) {
333	return (int) (n % (2L * k));	1✔
334	}
335
336	/**
337	* Computes the levels bit pattern given k, n.
338	* This is computed as <i>n / (2*k)</i>.
339	* @param k the configured size of the sketch
340	* @param n the total values presented to the sketch.
341	* @return the levels bit pattern
342	*/
343	static long computeBitPattern(final int k, final long n) {
344	return n / (2L * k);	1✔
345	}
346
347	/**
348	* Returns the log_base2 of x
349	* @param x the given x
350	* @return the log_base2 of x
351	*/
352	static double lg(final double x) {
353	return ( Math.log(x) / Math.log(2.0) );	1✔
354	}
355
356	/**
357	* Zero-based position of the highest one-bit of the given long.
358	* Returns minus one if num is zero.
359	* @param num the given long
360	* @return Zero-based position of the highest one-bit of the given long
361	*/
362	static int hiBitPos(final long num) {
363	return 63 - Long.numberOfLeadingZeros(num);	1✔
364	}
365
366	/**
367	* Returns the zero-based bit position of the lowest zero bit of <i>bits</i> starting at
368	* <i>startingBit</i>. If input is all ones, this returns 64.
369	* @param bits the input bits as a long
370	* @param startingBit the zero-based starting bit position. Only the low 6 bits are used.
371	* @return the zero-based bit position of the lowest zero bit starting at <i>startingBit</i>.
372	*/
373	static int lowestZeroBitStartingAt(final long bits, final int startingBit) {
374	int pos = startingBit & 0X3F;	1✔
375	long myBits = bits >>> pos;	1✔
376
377	while ((myBits & 1L) != 0) {	1✔
378	myBits = myBits >>> 1;	1✔
379	pos++;	1✔
380	}
381	return pos;	1✔
382	}
383
384	}

apache / datasketches-java / #64

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous