UtilTest.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 org.apache.datasketches.quantiles.ClassicUtil.MIN_K;
import static org.apache.datasketches.quantiles.ClassicUtil.checkPreLongsFlagsCap;
import static org.apache.datasketches.quantiles.ClassicUtil.computeCombinedBufferItemCapacity;
import static org.apache.datasketches.quantiles.ClassicUtil.computeValidLevels;
import static org.apache.datasketches.quantiles.ClassicUtil.hiBitPos;
import static org.apache.datasketches.quantiles.ClassicUtil.lowestZeroBitStartingAt;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertTrue;
import java.util.Arrays;
import org.apache.datasketches.common.SketchesArgumentException;
import org.testng.annotations.Test;
public class UtilTest {
@Test
public void checkCombBufItemCapacity() {
int k = 227;
int capEl = computeCombinedBufferItemCapacity(k, 0);
assertEquals(capEl, 2 * MIN_K);
}
@Test(expectedExceptions = SketchesArgumentException.class)
public void checkThePreLongsFlagsCap() {
checkPreLongsFlagsCap(2, 0, 15L);
}
@Test
public void checkHiBitPos() {
int bitPos = hiBitPos(4096);
assertEquals(bitPos, 12);
}
@Test
public void checkNumValidLevels() {
long v = (1L << 32)-1L;
int ones = computeValidLevels(v);
assertEquals(ones, 32);
}
@Test
public void testPositionOfLowestZeroBitStartingAt() {
int [] answers = {9, 8, 7, 7, 7, 4, 4, 4, 1, 1};
long v = 109L;
//println("IN: " + Long.toBinaryString(v));
for (int i = 0, j = 9; i < 10; i++, j--) {
int result = lowestZeroBitStartingAt(v, i);
//System.out.printf ("%d %d %d%n", i, result, answers[j]);
assertTrue (answers[j] == result);
}
}
@Test
public void testPositionOfLowestZeroBitStartingAt2() {
long bits = -1L;
int startingBit = 70; //only low 6 bits are used
int result = lowestZeroBitStartingAt(bits, startingBit);
assertEquals(result, 64);
}
//The remainder of this file is a brute force test of corner cases
// for blockyTandemMergeSort.
private static void assertMergeTestPrecondition(double [] arr, long [] brr, int arrLen, int blkSize) {
int violationsCount = 0;
for (int i = 0; i < (arrLen-1); i++) {
if (((i+1) % blkSize) == 0) {
continue;
}
if (arr[i] > arr[i+1]) { violationsCount++; }
}
for (int i = 0; i < arrLen; i++) {
if (brr[i] != (long) (1e12 * (1.0 - arr[i]))) {
violationsCount++;
}
}
if (brr[arrLen] != 0) { violationsCount++; }
assertEquals(violationsCount, 0);
}
private static void assertMergeTestPostcondition(double [] arr, long [] brr, int arrLen) {
int violationsCount = 0;
for (int i = 0; i < (arrLen-1); i++) {
if (arr[i] > arr[i+1]) { violationsCount++; }
}
for (int i = 0; i < arrLen; i++) {
if (brr[i] != (long) (1e12 * (1.0 - arr[i]))) {
violationsCount++;
}
}
if (brr[arrLen] != 0) { violationsCount++; }
assertEquals(violationsCount, 0);
}
private static double[] makeMergeTestInput(int arrLen, int blkSize) {
double[] arr = new double[arrLen];
double pick = Math.random ();
for (int i = 0; i < arrLen; i++) {
if (pick < 0.01) { // every value the same
arr[i] = 0.3;
}
else if (pick < 0.02) { // ascending values
int j = i+1;
int denom = arrLen+1;
arr[i] = ((double) j) / ((double) denom);
}
else if (pick < 0.03) { // descending values
int j = i+1;
int denom = arrLen+1;
arr[i] = 1.0 - (((double) j) / ((double) denom));
}
else { // random values
arr[i] = Math.random ();
}
}
for (int start = 0; start < arrLen; start += blkSize) {
Arrays.sort (arr, start, Math.min (arrLen, start + blkSize));
}
return arr;
}
private static long [] makeTheTandemArray(double [] arr) {
long [] brr = new long [arr.length + 1]; /* make it one longer, just like in the sketches */
for (int i = 0; i < arr.length; i++) {
brr[i] = (long) (1e12 * (1.0 - arr[i])); /* it's a better test with the order reversed */
}
brr[arr.length] = 0;
return brr;
}
@Test
public void checkBlockyTandemMergeSort() {
testBlockyTandemMergeSort(10, 50);
}
/**
* @param numTries number of tries
* @param maxArrLen maximum length of array size
*/
private static void testBlockyTandemMergeSort(int numTries, int maxArrLen) {
int arrLen = 0;
double[] arr = null;
for (arrLen = 0; arrLen <= maxArrLen; arrLen++) {
for (int blkSize = 1; blkSize <= (arrLen + 100); blkSize++) {
for (int tryno = 1; tryno <= numTries; tryno++) {
arr = makeMergeTestInput(arrLen, blkSize);
long [] brr = makeTheTandemArray(arr);
assertMergeTestPrecondition(arr, brr, arrLen, blkSize);
DoublesSketch.blockyTandemMergeSort(arr, brr, arrLen, blkSize);
/* verify sorted order */
for (int i = 0; i < (arrLen-1); i++) {
assert arr[i] <= arr[i+1];
}
assertMergeTestPostcondition(arr, brr, arrLen);
}
}
}
//System.out.printf ("Passed: testBlockyTandemMergeSort%n");
}
// we are retaining this stand-alone test because it can be more exhaustive
// @SuppressWarnings("unused")
// private static void exhaustiveMain(String[] args) {
// assert (args.length == 2);
// int numTries = Integer.parseInt(args[0]);
// int maxArrLen = Integer.parseInt(args[1]);
// System.out.printf("Testing blockyTandemMergeSort%n");
// for (int arrLen = 0; arrLen < maxArrLen; arrLen++) {
// for (int blkSize = 1; blkSize <= arrLen + 100; blkSize++) {
// System.out.printf (
// "Testing %d times with arrLen = %d and blkSize = %d%n", numTries, arrLen, blkSize);
// for (int tryno = 1; tryno <= numTries; tryno++) {
// double[] arr = makeMergeTestInput(arrLen, blkSize);
// long[] brr = makeTheTandemArray(arr);
// assertMergeTestPrecondition(arr, brr, arrLen, blkSize);
// DoublesAuxiliary.blockyTandemMergeSort(arr, brr, arrLen, blkSize);
// assertMergeTestPostcondition(arr, brr, arrLen);
// }
// }
// }
// }
//
// public static void main(String[] args) {
// exhaustiveMain(new String[] {"10", "100"});
// }
@Test
public void printlnTest() {
println("PRINTING: "+this.getClass().getName());
}
/**
* @param s value to print
*/
static void println(String s) {
//System.out.println(s); //disable here
}
}