src/test/java/org/apache/datasketches/theta/EmptyTest.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.theta;

import static org.apache.datasketches.theta.PreambleUtil.COMPACT_FLAG_MASK;
import static org.apache.datasketches.theta.PreambleUtil.ORDERED_FLAG_MASK;
import static org.apache.datasketches.theta.PreambleUtil.READ_ONLY_FLAG_MASK;
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;

import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.WritableMemory;
import org.testng.annotations.Test;


/**
 * Empty essentially means that the sketch has never seen data.
 *
 * @author Lee Rhodes
 */
@SuppressWarnings("javadoc")
public class EmptyTest {

  @Test
  public void checkEmpty() {
    final UpdateSketch sk1 = Sketches.updateSketchBuilder().build();
    final UpdateSketch sk2 = Sketches.updateSketchBuilder().build();
    final Intersection inter = Sketches.setOperationBuilder().buildIntersection();

    final int u = 100;
    for (int i = 0; i < u; i++) { //disjoint
      sk1.update(i);
      sk2.update(i + u);
    }
    inter.intersect(sk1);
    inter.intersect(sk2);

    final CompactSketch csk = inter.getResult();
    //The intersection of two disjoint, exact-mode sketches is empty, T == 1.0.
    println(csk.toString());
    assertTrue(csk.isEmpty());

    final AnotB aNotB = Sketches.setOperationBuilder().buildANotB();
    final CompactSketch csk2 = aNotB.aNotB(csk, sk1);
    //The AnotB of an empty, T == 1.0 sketch with another exact-mode sketch is empty, T == 1.0
    assertTrue(csk2.isEmpty());
  }

  @Test
  public void checkNotEmpty() {
    final UpdateSketch sk1 = Sketches.updateSketchBuilder().build();
    final UpdateSketch sk2 = Sketches.updateSketchBuilder().build();
    final Intersection inter = Sketches.setOperationBuilder().buildIntersection();

    final int u = 10000; //estimating
    for (int i = 0; i < u; i++) { //disjoint
      sk1.update(i);
      sk2.update(i + u);
    }
    inter.intersect(sk1);
    inter.intersect(sk2);

    final CompactSketch csk = inter.getResult();
    println(csk.toString());
    //The intersection of two disjoint, est-mode sketches is not-empty, T < 1.0.
    assertFalse(csk.isEmpty());

    AnotB aNotB = Sketches.setOperationBuilder().buildANotB();
    final CompactSketch csk2 = aNotB.aNotB(csk, sk1); //empty, T < 1.0; with est-mode sketch
    println(csk2.toString());
    //The AnotB of an empty, T < 1.0 sketch with another exact-mode sketch is not-empty.
    assertFalse(csk2.isEmpty());

    final UpdateSketch sk3 = Sketches.updateSketchBuilder().build();
    aNotB = Sketches.setOperationBuilder().buildANotB();
    final CompactSketch csk3 = aNotB.aNotB(sk3, sk1); //empty, T == 1.0; with est-mode sketch
    println(csk3.toString());
    //the AnotB of an empty, T == 1.0 sketch with another est-mode sketch is empty, T < 1.0
    assertTrue(csk3.isEmpty());
  }

  @Test
  public void checkPsampling() {
    final UpdateSketch sk1 = Sketches.updateSketchBuilder().setP(.5F).build();
    assertTrue(sk1.isEmpty());
    //An empty P-sampling sketch where T < 1.0 and has never seen data is also empty
    // and will have a full preamble of 24 bytes.  But when compacted, theta returns to 1.0, so
    // it will be stored as only 8 bytes.
    assertEquals(sk1.compact().toByteArray().length, 8);
  }

  //These 3 tests reproduce a failure mode where an "old" empty sketch of 8 bytes without
  // its empty-flag bit set is read.
  @Test
  public void checkBackwardCompatibility1() {
    final int k = 16;
    final int bytes = Sketches.getMaxUnionBytes(k); //288
    final Union union = SetOperation.builder().buildUnion(WritableMemory.allocate(bytes));
    final Memory mem = badEmptySk();
    final Sketch wsk = Sketches.wrapSketch(mem);
    union.union(wsk); //union has memory
  }

  @Test
  public void checkBackwardCompatibility2() {
    final Union union = SetOperation.builder().setNominalEntries(16).buildUnion();
    final Memory mem = badEmptySk();
    final Sketch wsk = Sketches.wrapSketch(mem);
    union.union(wsk); //heap union
  }

  @Test
  public void checkBackwardCompatibility3() {
    final Memory mem = badEmptySk();
    Sketches.heapifySketch(mem);
  }

  @Test
  public void checkEmptyToCompact() {
    final UpdateSketch sk1 = Sketches.updateSketchBuilder().build();
    final CompactSketch csk = sk1.compact();
    assertTrue(csk instanceof EmptyCompactSketch);
    final CompactSketch csk2 = csk.compact();
    assertTrue(csk2 instanceof EmptyCompactSketch);
    final CompactSketch csk3 = csk.compact(true, WritableMemory.allocate(8));
    assertTrue(csk3 instanceof DirectCompactSketch);
    assertEquals(csk2.getCurrentPreambleLongs(), 1);
  }


  //SerVer 2 had an empty sketch where preLongs = 1, but empty bit was not set.
  private static Memory badEmptySk() {
    final long preLongs = 1;
    final long serVer = 2;
    final long family = 3; //compact
    final long flags = ORDERED_FLAG_MASK | COMPACT_FLAG_MASK | READ_ONLY_FLAG_MASK;
    final long seedHash = 0x93CC;
    final long badEmptySk = seedHash << 48 | flags << 40
        | family << 16 | serVer << 8 | preLongs;
    final WritableMemory wmem =  WritableMemory.allocate(8);
    wmem.putLong(0, badEmptySk);
    return wmem;
  }

  /**
   * @param s value to print
   */
  static void println(final String s) {
    //System.out.println(s); //disable here
  }

}