#132

Build # #132

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/52d5da8c17cb17e06571dac3bd69c7549e84b547">52d5da8c1">&lt;a href=&quot;https://github.com/apache/datasketches-java/commit/</a><a class="double-link" href="https://github.com/apache/datasketches-java/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/apache/datasketches-java/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/apache/datasketches-java/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/apache/datasketches-java/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/apache/datasketches-java/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://git">&lt;a class=</a>hub.com/apache/datasketches-java/commit/52d5da8c17cb17e06571dac3bd69c7549e84b547">52d5da8c1</a><a href="https://github.com/apache/datasketches-java/commit/52d5da8c17cb17e06571dac3bd69c7549e84b547">&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/&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/&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/&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/&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/52d5da8c17cb17e06571dac3bd69c7549e84b547&quot;&gt;... (continued)

Run Details

162 of 162 new or added lines in 7 files covered. (100.0%)

17872 of 18246 relevant lines covered (97.95%)

0.98 hits per line

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

99.49

/src/main/java/org/apache/datasketches/theta/UnionImpl.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 java.lang.Math.min;
import static org.apache.datasketches.QuickSelect.selectExcludingZeros;
import static org.apache.datasketches.Util.computeSeedHash;
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.PREAMBLE_LONGS_BYTE;
import static org.apache.datasketches.theta.PreambleUtil.UNION_THETA_LONG;
import static org.apache.datasketches.theta.PreambleUtil.clearEmpty;
import static org.apache.datasketches.theta.PreambleUtil.extractCurCount;
import static org.apache.datasketches.theta.PreambleUtil.extractFamilyID;
import static org.apache.datasketches.theta.PreambleUtil.extractFlags;
import static org.apache.datasketches.theta.PreambleUtil.extractLgArrLongs;
import static org.apache.datasketches.theta.PreambleUtil.extractPreLongs;
import static org.apache.datasketches.theta.PreambleUtil.extractSeedHash;
import static org.apache.datasketches.theta.PreambleUtil.extractSerVer;
import static org.apache.datasketches.theta.PreambleUtil.extractThetaLong;
import static org.apache.datasketches.theta.PreambleUtil.extractUnionThetaLong;
import static org.apache.datasketches.theta.PreambleUtil.insertUnionThetaLong;
import static org.apache.datasketches.theta.SingleItemSketch.otherCheckForSingleItem;

import org.apache.datasketches.Family;
import org.apache.datasketches.HashOperations;
import org.apache.datasketches.ResizeFactor;
import org.apache.datasketches.SketchesArgumentException;
import org.apache.datasketches.Util;
import org.apache.datasketches.memory.Memory;
import org.apache.datasketches.memory.MemoryRequestServer;
import org.apache.datasketches.memory.WritableMemory;

/**
 * Shared code for the HeapUnion and DirectUnion implementations.
 *
 * @author Lee Rhodes
 * @author Kevin Lang
 */
final class UnionImpl extends Union {

  /**
   * Although the gadget object is initially an UpdateSketch, in the context of a Union it is used
   * as a specialized buffer that happens to leverage much of the machinery of an UpdateSketch.
   * However, in this context some of the key invariants of the sketch algorithm are intentionally
   * violated as an optimization. As a result this object can not be considered as an UpdateSketch
   * and should never be exported as an UpdateSketch. It's internal state is not necessarily
   * finalized and may contain garbage. Also its internal concept of "nominal entries" or "k" can
   * be meaningless. It is private for very good reasons.
   */
  private final UpdateSketch gadget_;
  private final short seedHash_; //eliminates having to compute the seedHash on every union.
  private long unionThetaLong_; //when on-heap, this is the only copy
  private boolean unionEmpty_;  //when on-heap, this is the only copy

  private UnionImpl(final UpdateSketch gadget, final long seed) {
    gadget_ = gadget;
    seedHash_ = computeSeedHash(seed);
  }

  /**
   * Construct a new Union SetOperation on the java heap.
   * Called by SetOperationBuilder.
   *
   * @param lgNomLongs <a href="{@docRoot}/resources/dictionary.html#lgNomLogs">See lgNomLongs</a>
   * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
   * @param p <a href="{@docRoot}/resources/dictionary.html#p">See Sampling Probability, <i>p</i></a>
   * @param rf <a href="{@docRoot}/resources/dictionary.html#resizeFactor">See Resize Factor</a>
   * @return instance of this sketch
   */
  static UnionImpl initNewHeapInstance(
      final int lgNomLongs,
      final long seed,
      final float p,
      final ResizeFactor rf) {
    final UpdateSketch gadget = //create with UNION family
        new HeapQuickSelectSketch(lgNomLongs, seed, p, rf, true);
    final UnionImpl unionImpl = new UnionImpl(gadget, seed);
    unionImpl.unionThetaLong_ = gadget.getThetaLong();
    unionImpl.unionEmpty_ = gadget.isEmpty();
    return unionImpl;
  }

  /**
   * Construct a new Direct Union in the off-heap destination Memory.
   * Called by SetOperationBuilder.
   *
   * @param lgNomLongs <a href="{@docRoot}/resources/dictionary.html#lgNomLogs">See lgNomLongs</a>.
   * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
   * @param p <a href="{@docRoot}/resources/dictionary.html#p">See Sampling Probability, <i>p</i></a>
   * @param rf <a href="{@docRoot}/resources/dictionary.html#resizeFactor">See Resize Factor</a>
   * @param memReqSvr a given instance of a MemoryRequestServer
   * @param dstMem the given Memory object destination. It will be cleared prior to use.
   * @return this class
   */
  static UnionImpl initNewDirectInstance(
      final int lgNomLongs,
      final long seed,
      final float p,
      final ResizeFactor rf,
      final MemoryRequestServer memReqSvr,
      final WritableMemory dstMem) {
    final UpdateSketch gadget = //create with UNION family
        new DirectQuickSelectSketch(lgNomLongs, seed, p, rf, memReqSvr, dstMem, true);
    final UnionImpl unionImpl = new UnionImpl(gadget, seed);
    unionImpl.unionThetaLong_ = gadget.getThetaLong();
    unionImpl.unionEmpty_ = gadget.isEmpty();
    return unionImpl;
  }

  /**
   * Heapify a Union from a Memory Union object containing data.
   * Called by SetOperation.
   * @param srcMem The source Memory Union object.
   * <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
   * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
   * @return this class
   */
  static UnionImpl heapifyInstance(final Memory srcMem, final long seed) {
    Family.UNION.checkFamilyID(extractFamilyID(srcMem));
    final UpdateSketch gadget = HeapQuickSelectSketch.heapifyInstance(srcMem, seed);
    final UnionImpl unionImpl = new UnionImpl(gadget, seed);
    unionImpl.unionThetaLong_ = extractUnionThetaLong(srcMem);
    unionImpl.unionEmpty_ = PreambleUtil.isEmptyFlag(srcMem);
    return unionImpl;
  }

  /**
   * Fast-wrap a Union object around a Union Memory object containing data.
   * This does NO validity checking of the given Memory.
   * @param srcMem The source Memory object.
   * <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
   * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
   * @return this class
   */
  static UnionImpl fastWrap(final Memory srcMem, final long seed) {
    Family.UNION.checkFamilyID(extractFamilyID(srcMem));
    final UpdateSketch gadget = DirectQuickSelectSketchR.fastReadOnlyWrap(srcMem, seed);
    final UnionImpl unionImpl = new UnionImpl(gadget, seed);
    unionImpl.unionThetaLong_ = extractUnionThetaLong(srcMem);
    unionImpl.unionEmpty_ = PreambleUtil.isEmptyFlag(srcMem);
    return unionImpl;
  }

  /**
   * Fast-wrap a Union object around a Union WritableMemory object containing data.
   * This does NO validity checking of the given Memory.
   * @param srcMem The source Memory object.
   * <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
   * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
   * @return this class
   */
  static UnionImpl fastWrap(final WritableMemory srcMem, final long seed) {
    Family.UNION.checkFamilyID(extractFamilyID(srcMem));
    final UpdateSketch gadget = DirectQuickSelectSketch.fastWritableWrap(srcMem, seed);
    final UnionImpl unionImpl = new UnionImpl(gadget, seed);
    unionImpl.unionThetaLong_ = extractUnionThetaLong(srcMem);
    unionImpl.unionEmpty_ = PreambleUtil.isEmptyFlag(srcMem);
    return unionImpl;
  }

  /**
   * Wrap a Union object around a Union Memory object containing data.
   * Called by SetOperation.
   * @param srcMem The source Memory object.
   * <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
   * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
   * @return this class
   */
  static UnionImpl wrapInstance(final Memory srcMem, final long seed) {
    Family.UNION.checkFamilyID(extractFamilyID(srcMem));
    final UpdateSketch gadget = DirectQuickSelectSketchR.readOnlyWrap(srcMem, seed);
    final UnionImpl unionImpl = new UnionImpl(gadget, seed);
    unionImpl.unionThetaLong_ = extractUnionThetaLong(srcMem);
    unionImpl.unionEmpty_ = PreambleUtil.isEmptyFlag(srcMem);
    return unionImpl;
  }

  /**
   * Wrap a Union object around a Union WritableMemory object containing data.
   * Called by SetOperation.
   * @param srcMem The source Memory object.
   * <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
   * @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
   * @return this class
   */
  static UnionImpl wrapInstance(final WritableMemory srcMem, final long seed) {
    Family.UNION.checkFamilyID(extractFamilyID(srcMem));
    final UpdateSketch gadget = DirectQuickSelectSketch.writableWrap(srcMem, seed);
    final UnionImpl unionImpl = new UnionImpl(gadget, seed);
    unionImpl.unionThetaLong_ = extractUnionThetaLong(srcMem);
    unionImpl.unionEmpty_ = PreambleUtil.isEmptyFlag(srcMem);
    return unionImpl;
  }

  @Override
  public boolean isSameResource(final Memory that) {
    return gadget_ instanceof DirectQuickSelectSketchR
        ? gadget_.getMemory().isSameResource(that) : false;
  }

  @Override
  public CompactSketch getResult() {
    return getResult(true, null);
  }

  @Override
  public CompactSketch getResult(final boolean dstOrdered, final WritableMemory dstMem) {
    final int gadgetCurCount = gadget_.getRetainedEntries(true);
    final int k = 1 << gadget_.getLgNomLongs();
    final long[] gadgetCacheCopy =
        gadget_.hasMemory() ? gadget_.getCache() : gadget_.getCache().clone();

    //Pull back to k
    final long curGadgetThetaLong = gadget_.getThetaLong();
    final long adjGadgetThetaLong = gadgetCurCount > k
        ? selectExcludingZeros(gadgetCacheCopy, gadgetCurCount, k + 1) : curGadgetThetaLong;

    //Finalize Theta and curCount
    final long unionThetaLong = gadget_.hasMemory()
        ? gadget_.getMemory().getLong(UNION_THETA_LONG) : unionThetaLong_;

    final long minThetaLong = min(min(curGadgetThetaLong, adjGadgetThetaLong), unionThetaLong);
    final int curCountOut = minThetaLong < curGadgetThetaLong
        ? HashOperations.count(gadgetCacheCopy, minThetaLong)
        : gadgetCurCount;

    //Compact the cache
    final long[] compactCacheOut =
        CompactOperations.compactCache(gadgetCacheCopy, curCountOut, minThetaLong, dstOrdered);
    final boolean empty = gadget_.isEmpty() && unionEmpty_;
    final short seedHash = gadget_.getSeedHash();
    return CompactOperations.componentsToCompact(
        minThetaLong, curCountOut, seedHash, empty, true, dstOrdered, dstOrdered, dstMem, compactCacheOut);
  }

  @Override
  public void reset() {
    gadget_.reset();
    unionThetaLong_ = gadget_.getThetaLong();
    unionEmpty_ = gadget_.isEmpty();
  }

  @Override
  public byte[] toByteArray() {
    final byte[] gadgetByteArr = gadget_.toByteArray();
    final WritableMemory mem = WritableMemory.writableWrap(gadgetByteArr);
    insertUnionThetaLong(mem, unionThetaLong_);
    if (gadget_.isEmpty() != unionEmpty_) {
      clearEmpty(mem);
      unionEmpty_ = false;
    }
    return gadgetByteArr;
  }

  @Override //Stateless Union
  public CompactSketch union(final Sketch sketchA, final Sketch sketchB, final boolean dstOrdered,
      final WritableMemory dstMem) {
    reset();
    union(sketchA);
    union(sketchB);
    final CompactSketch csk = getResult(dstOrdered, dstMem);
    reset();
    return csk;
  }

  @Override
  public void union(final Sketch sketchIn) { //Only valid for theta Sketches using SerVer = 3
    //UNION Empty Rule: AND the empty states.

    if (sketchIn == null || sketchIn.isEmpty()) {
      //null and empty is interpreted as (Theta = 1.0, count = 0, empty = T).  Nothing changes
      return;
    }
    //sketchIn is valid and not empty
    Util.checkSeedHashes(seedHash_, sketchIn.getSeedHash());
    if (sketchIn instanceof SingleItemSketch) {
      gadget_.hashUpdate(sketchIn.getCache()[0]);
      return;
    }
    Sketch.checkSketchAndMemoryFlags(sketchIn);

    unionThetaLong_ = min(min(unionThetaLong_, sketchIn.getThetaLong()), gadget_.getThetaLong()); //Theta rule
    unionEmpty_ = false;
    final int curCountIn = sketchIn.getRetainedEntries(true);
    if (curCountIn > 0) {
      if (sketchIn.isOrdered()) { //Only true if Compact. Use early stop
        //Ordered, thus compact
        if (sketchIn.hasMemory()) {
          final Memory skMem = ((CompactSketch) sketchIn).getMemory();
          final int preambleLongs = skMem.getByte(PREAMBLE_LONGS_BYTE) & 0X3F;
          for (int i = 0; i < curCountIn; i++ ) {
            final int offsetBytes = preambleLongs + i << 3;
            final long hashIn = skMem.getLong(offsetBytes);
            if (hashIn >= unionThetaLong_) { break; } // "early stop"
            gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
          }
        }
        else { //sketchIn is on the Java Heap or has array
          final long[] cacheIn = sketchIn.getCache(); //not a copy!
          for (int i = 0; i < curCountIn; i++ ) {
            final long hashIn = cacheIn[i];
            if (hashIn >= unionThetaLong_) { break; } // "early stop"
            gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
          }
        }
      } //End ordered, compact
      else { //either not-ordered compact or Hash Table form. A HT may have dirty values.
        final long[] cacheIn = sketchIn.getCache(); //if off-heap this will be a copy
        final int arrLongs = cacheIn.length;
        for (int i = 0, c = 0; i < arrLongs && c < curCountIn; i++ ) {
          final long hashIn = cacheIn[i];
          if (hashIn <= 0L || hashIn >= unionThetaLong_) { continue; } //rejects dirty values
          gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
          c++; //ensures against invalid state inside the incoming sketch
        }
      }
    }
    unionThetaLong_ = min(unionThetaLong_, gadget_.getThetaLong()); //Theta rule with gadget
    if (gadget_.hasMemory()) {
      final WritableMemory wmem = (WritableMemory)gadget_.getMemory();
      PreambleUtil.insertUnionThetaLong(wmem, unionThetaLong_);
      PreambleUtil.clearEmpty(wmem);
    }
  }

  @Override
  public void union(final Memory skMem) {
    if (skMem == null) { return; }
    final int cap = (int) skMem.getCapacity();
    if (cap < 16) { return; } //empty or garbage
    final int serVer = extractSerVer(skMem);
    final int fam = extractFamilyID(skMem);

    if (serVer == 3) { //The OpenSource sketches (Aug 4, 2015) starts with serVer = 3
      if (fam < 1 || fam > 3) {
        throw new SketchesArgumentException(
            "Family must be Alpha, QuickSelect, or Compact: " + Family.idToFamily(fam));
      }
      processVer3(skMem);
      return;
    }

    if (serVer == 2) { //older Sketch, which is compact and ordered
      Util.checkSeedHashes(seedHash_, (short)extractSeedHash(skMem));
      final CompactSketch csk = ForwardCompatibility.heapify2to3(skMem,seedHash_);
      union(csk);
      return;
    }

    if (serVer == 1) { //much older Sketch, which is compact and ordered, no seedHash
      final CompactSketch csk = ForwardCompatibility.heapify1to3(skMem, seedHash_);
      union(csk);
      return;
    }

    throw new SketchesArgumentException("SerVer is unknown: " + serVer);
  }

  //Has seedHash, p, could have 0 entries & theta < 1.0,
  //could be unordered, ordered, compact, or not compact,
  //could be Alpha, QuickSelect, or Compact.
  private void processVer3(final Memory skMem) {
    final int preLongs = extractPreLongs(skMem);

    if (preLongs == 1) {
      if (otherCheckForSingleItem(skMem)) {
        final long hash = skMem.getLong(8);
        gadget_.hashUpdate(hash);
        return;
      }
      return; //empty
    }
    Util.checkSeedHashes(seedHash_, (short)extractSeedHash(skMem));
    final int curCountIn;
    final long thetaLongIn;

    if (preLongs == 2) { //exact mode
      curCountIn = extractCurCount(skMem);
      if (curCountIn == 0) { return; } //should be > 0, but if it is 0 return empty anyway.
      thetaLongIn = Long.MAX_VALUE;
    }

    else { //prelongs == 3
      //curCount may be 0 (e.g., from intersection); but sketch cannot be empty.
      curCountIn = extractCurCount(skMem);
      thetaLongIn = extractThetaLong(skMem);
    }

    unionThetaLong_ = min(min(unionThetaLong_, thetaLongIn), gadget_.getThetaLong()); //theta rule
    unionEmpty_ = false;
    final int flags = extractFlags(skMem);
    final boolean ordered = (flags & ORDERED_FLAG_MASK) != 0;
    if (ordered) { //must be compact

      for (int i = 0; i < curCountIn; i++ ) {
        final int offsetBytes = preLongs + i << 3;
        final long hashIn = skMem.getLong(offsetBytes);
        if (hashIn >= unionThetaLong_) { break; } // "early stop"
        gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
      }
    }

    else { //not-ordered, could be compact or hash-table form
      final boolean compact = (flags & COMPACT_FLAG_MASK) != 0;
      final int size = compact ? curCountIn : 1 << extractLgArrLongs(skMem);

      for (int i = 0; i < size; i++ ) {
        final int offsetBytes = preLongs + i << 3;
        final long hashIn = skMem.getLong(offsetBytes);
        if (hashIn <= 0L || hashIn >= unionThetaLong_) { continue; }
        gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed
      }
    }

    unionThetaLong_ = min(unionThetaLong_, gadget_.getThetaLong()); //sync thetaLongs

    if (gadget_.hasMemory()) {
      final WritableMemory wmem = (WritableMemory)gadget_.getMemory();
      PreambleUtil.insertUnionThetaLong(wmem, unionThetaLong_);
      PreambleUtil.clearEmpty(wmem);
    }
  }

  @Override
  public void update(final long datum) {
    gadget_.update(datum);
  }

  @Override
  public void update(final double datum) {
    gadget_.update(datum);
  }

  @Override
  public void update(final String datum) {
    gadget_.update(datum);
  }

  @Override
  public void update(final byte[] data) {
    gadget_.update(data);
  }

  @Override
  public void update(final char[] data) {
    gadget_.update(data);
  }

  @Override
  public void update(final int[] data) {
    gadget_.update(data);
  }

  @Override
  public void update(final long[] data) {
    gadget_.update(data);
  }

  //Restricted

  @Override
  long[] getCache() {
    return gadget_.getCache();
  }

  @Override
  int getRetainedEntries() {
    return gadget_.getRetainedEntries(true);
  }

  @Override
  short getSeedHash() {
    return gadget_.getSeedHash();
  }

  @Override
  long getThetaLong() {
    return min(unionThetaLong_, gadget_.getThetaLong());
  }

  @Override
  boolean isEmpty() {
    return gadget_.isEmpty() && unionEmpty_;
  }

}

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.theta;
21
22	import static java.lang.Math.min;
23	import static org.apache.datasketches.QuickSelect.selectExcludingZeros;
24	import static org.apache.datasketches.Util.computeSeedHash;
25	import static org.apache.datasketches.theta.PreambleUtil.COMPACT_FLAG_MASK;
26	import static org.apache.datasketches.theta.PreambleUtil.ORDERED_FLAG_MASK;
27	import static org.apache.datasketches.theta.PreambleUtil.PREAMBLE_LONGS_BYTE;
28	import static org.apache.datasketches.theta.PreambleUtil.UNION_THETA_LONG;
29	import static org.apache.datasketches.theta.PreambleUtil.clearEmpty;
30	import static org.apache.datasketches.theta.PreambleUtil.extractCurCount;
31	import static org.apache.datasketches.theta.PreambleUtil.extractFamilyID;
32	import static org.apache.datasketches.theta.PreambleUtil.extractFlags;
33	import static org.apache.datasketches.theta.PreambleUtil.extractLgArrLongs;
34	import static org.apache.datasketches.theta.PreambleUtil.extractPreLongs;
35	import static org.apache.datasketches.theta.PreambleUtil.extractSeedHash;
36	import static org.apache.datasketches.theta.PreambleUtil.extractSerVer;
37	import static org.apache.datasketches.theta.PreambleUtil.extractThetaLong;
38	import static org.apache.datasketches.theta.PreambleUtil.extractUnionThetaLong;
39	import static org.apache.datasketches.theta.PreambleUtil.insertUnionThetaLong;
40	import static org.apache.datasketches.theta.SingleItemSketch.otherCheckForSingleItem;
41
42	import org.apache.datasketches.Family;
43	import org.apache.datasketches.HashOperations;
44	import org.apache.datasketches.ResizeFactor;
45	import org.apache.datasketches.SketchesArgumentException;
46	import org.apache.datasketches.Util;
47	import org.apache.datasketches.memory.Memory;
48	import org.apache.datasketches.memory.MemoryRequestServer;
49	import org.apache.datasketches.memory.WritableMemory;
50
51	/**
52	* Shared code for the HeapUnion and DirectUnion implementations.
53	*
54	* @author Lee Rhodes
55	* @author Kevin Lang
56	*/
57	final class UnionImpl extends Union {
58
59	/**
60	* Although the gadget object is initially an UpdateSketch, in the context of a Union it is used
61	* as a specialized buffer that happens to leverage much of the machinery of an UpdateSketch.
62	* However, in this context some of the key invariants of the sketch algorithm are intentionally
63	* violated as an optimization. As a result this object can not be considered as an UpdateSketch
64	* and should never be exported as an UpdateSketch. It's internal state is not necessarily
65	* finalized and may contain garbage. Also its internal concept of "nominal entries" or "k" can
66	* be meaningless. It is private for very good reasons.
67	*/
68	private final UpdateSketch gadget_;
69	private final short seedHash_; //eliminates having to compute the seedHash on every union.
70	private long unionThetaLong_; //when on-heap, this is the only copy
71	private boolean unionEmpty_; //when on-heap, this is the only copy
72
73	private UnionImpl(final UpdateSketch gadget, final long seed) {	1✔
74	gadget_ = gadget;	1✔
75	seedHash_ = computeSeedHash(seed);	1✔
76	}	1✔
77
78	/**
79	* Construct a new Union SetOperation on the java heap.
80	* Called by SetOperationBuilder.
81	*
82	* @param lgNomLongs <a href="{@docRoot}/resources/dictionary.html#lgNomLogs">See lgNomLongs</a>
83	* @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
84	* @param p <a href="{@docRoot}/resources/dictionary.html#p">See Sampling Probability, <i>p</i></a>
85	* @param rf <a href="{@docRoot}/resources/dictionary.html#resizeFactor">See Resize Factor</a>
86	* @return instance of this sketch
87	*/
88	static UnionImpl initNewHeapInstance(
89	final int lgNomLongs,
90	final long seed,
91	final float p,
92	final ResizeFactor rf) {
93	final UpdateSketch gadget = //create with UNION family	1✔
94	new HeapQuickSelectSketch(lgNomLongs, seed, p, rf, true);
95	final UnionImpl unionImpl = new UnionImpl(gadget, seed);	1✔
96	unionImpl.unionThetaLong_ = gadget.getThetaLong();	1✔
97	unionImpl.unionEmpty_ = gadget.isEmpty();	1✔
98	return unionImpl;	1✔
99	}
100
101	/**
102	* Construct a new Direct Union in the off-heap destination Memory.
103	* Called by SetOperationBuilder.
104	*
105	* @param lgNomLongs <a href="{@docRoot}/resources/dictionary.html#lgNomLogs">See lgNomLongs</a>.
106	* @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
107	* @param p <a href="{@docRoot}/resources/dictionary.html#p">See Sampling Probability, <i>p</i></a>
108	* @param rf <a href="{@docRoot}/resources/dictionary.html#resizeFactor">See Resize Factor</a>
109	* @param memReqSvr a given instance of a MemoryRequestServer
110	* @param dstMem the given Memory object destination. It will be cleared prior to use.
111	* @return this class
112	*/
113	static UnionImpl initNewDirectInstance(
114	final int lgNomLongs,
115	final long seed,
116	final float p,
117	final ResizeFactor rf,
118	final MemoryRequestServer memReqSvr,
119	final WritableMemory dstMem) {
120	final UpdateSketch gadget = //create with UNION family	1✔
121	new DirectQuickSelectSketch(lgNomLongs, seed, p, rf, memReqSvr, dstMem, true);
122	final UnionImpl unionImpl = new UnionImpl(gadget, seed);	1✔
123	unionImpl.unionThetaLong_ = gadget.getThetaLong();	1✔
124	unionImpl.unionEmpty_ = gadget.isEmpty();	1✔
125	return unionImpl;	1✔
126	}
127
128	/**
129	* Heapify a Union from a Memory Union object containing data.
130	* Called by SetOperation.
131	* @param srcMem The source Memory Union object.
132	* <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
133	* @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
134	* @return this class
135	*/
136	static UnionImpl heapifyInstance(final Memory srcMem, final long seed) {
137	Family.UNION.checkFamilyID(extractFamilyID(srcMem));	1✔
138	final UpdateSketch gadget = HeapQuickSelectSketch.heapifyInstance(srcMem, seed);	1✔
139	final UnionImpl unionImpl = new UnionImpl(gadget, seed);	1✔
140	unionImpl.unionThetaLong_ = extractUnionThetaLong(srcMem);	1✔
141	unionImpl.unionEmpty_ = PreambleUtil.isEmptyFlag(srcMem);	1✔
142	return unionImpl;	1✔
143	}
144
145	/**
146	* Fast-wrap a Union object around a Union Memory object containing data.
147	* This does NO validity checking of the given Memory.
148	* @param srcMem The source Memory object.
149	* <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
150	* @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
151	* @return this class
152	*/
153	static UnionImpl fastWrap(final Memory srcMem, final long seed) {
154	Family.UNION.checkFamilyID(extractFamilyID(srcMem));	1✔
155	final UpdateSketch gadget = DirectQuickSelectSketchR.fastReadOnlyWrap(srcMem, seed);	1✔
156	final UnionImpl unionImpl = new UnionImpl(gadget, seed);	1✔
157	unionImpl.unionThetaLong_ = extractUnionThetaLong(srcMem);	1✔
158	unionImpl.unionEmpty_ = PreambleUtil.isEmptyFlag(srcMem);	1✔
159	return unionImpl;	1✔
160	}
161
162	/**
163	* Fast-wrap a Union object around a Union WritableMemory object containing data.
164	* This does NO validity checking of the given Memory.
165	* @param srcMem The source Memory object.
166	* <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
167	* @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
168	* @return this class
169	*/
170	static UnionImpl fastWrap(final WritableMemory srcMem, final long seed) {
171	Family.UNION.checkFamilyID(extractFamilyID(srcMem));	1✔
172	final UpdateSketch gadget = DirectQuickSelectSketch.fastWritableWrap(srcMem, seed);	1✔
173	final UnionImpl unionImpl = new UnionImpl(gadget, seed);	1✔
174	unionImpl.unionThetaLong_ = extractUnionThetaLong(srcMem);	1✔
175	unionImpl.unionEmpty_ = PreambleUtil.isEmptyFlag(srcMem);	1✔
176	return unionImpl;	1✔
177	}
178
179	/**
180	* Wrap a Union object around a Union Memory object containing data.
181	* Called by SetOperation.
182	* @param srcMem The source Memory object.
183	* <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
184	* @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
185	* @return this class
186	*/
187	static UnionImpl wrapInstance(final Memory srcMem, final long seed) {
188	Family.UNION.checkFamilyID(extractFamilyID(srcMem));	1✔
189	final UpdateSketch gadget = DirectQuickSelectSketchR.readOnlyWrap(srcMem, seed);	1✔
190	final UnionImpl unionImpl = new UnionImpl(gadget, seed);	1✔
191	unionImpl.unionThetaLong_ = extractUnionThetaLong(srcMem);	1✔
192	unionImpl.unionEmpty_ = PreambleUtil.isEmptyFlag(srcMem);	1✔
193	return unionImpl;	1✔
194	}
195
196	/**
197	* Wrap a Union object around a Union WritableMemory object containing data.
198	* Called by SetOperation.
199	* @param srcMem The source Memory object.
200	* <a href="{@docRoot}/resources/dictionary.html#mem">See Memory</a>
201	* @param seed <a href="{@docRoot}/resources/dictionary.html#seed">See seed</a>
202	* @return this class
203	*/
204	static UnionImpl wrapInstance(final WritableMemory srcMem, final long seed) {
205	Family.UNION.checkFamilyID(extractFamilyID(srcMem));	1✔
206	final UpdateSketch gadget = DirectQuickSelectSketch.writableWrap(srcMem, seed);	1✔
207	final UnionImpl unionImpl = new UnionImpl(gadget, seed);	1✔
208	unionImpl.unionThetaLong_ = extractUnionThetaLong(srcMem);	1✔
209	unionImpl.unionEmpty_ = PreambleUtil.isEmptyFlag(srcMem);	1✔
210	return unionImpl;	1✔
211	}
212
213	@Override
214	public boolean isSameResource(final Memory that) {
215	return gadget_ instanceof DirectQuickSelectSketchR	1✔
216	? gadget_.getMemory().isSameResource(that) : false;	1✔
217	}
218
219	@Override
220	public CompactSketch getResult() {
221	return getResult(true, null);	1✔
222	}
223
224	@Override
225	public CompactSketch getResult(final boolean dstOrdered, final WritableMemory dstMem) {
226	final int gadgetCurCount = gadget_.getRetainedEntries(true);	1✔
227	final int k = 1 << gadget_.getLgNomLongs();	1✔
228	final long[] gadgetCacheCopy =	1✔
229	gadget_.hasMemory() ? gadget_.getCache() : gadget_.getCache().clone();	1✔
230
231	//Pull back to k
232	final long curGadgetThetaLong = gadget_.getThetaLong();	1✔
233	final long adjGadgetThetaLong = gadgetCurCount > k	1✔
234	? selectExcludingZeros(gadgetCacheCopy, gadgetCurCount, k + 1) : curGadgetThetaLong;	1✔
235
236	//Finalize Theta and curCount
237	final long unionThetaLong = gadget_.hasMemory()	1✔
238	? gadget_.getMemory().getLong(UNION_THETA_LONG) : unionThetaLong_;	1✔
239
240	final long minThetaLong = min(min(curGadgetThetaLong, adjGadgetThetaLong), unionThetaLong);	1✔
241	final int curCountOut = minThetaLong < curGadgetThetaLong	1✔
242	? HashOperations.count(gadgetCacheCopy, minThetaLong)	1✔
243	: gadgetCurCount;
244
245	//Compact the cache
246	final long[] compactCacheOut =	1✔
247	CompactOperations.compactCache(gadgetCacheCopy, curCountOut, minThetaLong, dstOrdered);	1✔
248	final boolean empty = gadget_.isEmpty() && unionEmpty_;	1✔
249	final short seedHash = gadget_.getSeedHash();	1✔
250	return CompactOperations.componentsToCompact(	1✔
251	minThetaLong, curCountOut, seedHash, empty, true, dstOrdered, dstOrdered, dstMem, compactCacheOut);
252	}
253
254	@Override
255	public void reset() {
256	gadget_.reset();	1✔
257	unionThetaLong_ = gadget_.getThetaLong();	1✔
258	unionEmpty_ = gadget_.isEmpty();	1✔
259	}	1✔
260
261	@Override
262	public byte[] toByteArray() {
263	final byte[] gadgetByteArr = gadget_.toByteArray();	1✔
264	final WritableMemory mem = WritableMemory.writableWrap(gadgetByteArr);	1✔
265	insertUnionThetaLong(mem, unionThetaLong_);	1✔
266	if (gadget_.isEmpty() != unionEmpty_) {	1✔
267	clearEmpty(mem);	1✔
268	unionEmpty_ = false;	1✔
269	}
270	return gadgetByteArr;	1✔
271	}
272
273	@Override //Stateless Union
274	public CompactSketch union(final Sketch sketchA, final Sketch sketchB, final boolean dstOrdered,
275	final WritableMemory dstMem) {
276	reset();	1✔
277	union(sketchA);	1✔
278	union(sketchB);	1✔
279	final CompactSketch csk = getResult(dstOrdered, dstMem);	1✔
280	reset();	1✔
281	return csk;	1✔
282	}
283
284	@Override
285	public void union(final Sketch sketchIn) { //Only valid for theta Sketches using SerVer = 3
286	//UNION Empty Rule: AND the empty states.
287
288	if (sketchIn == null \|\| sketchIn.isEmpty()) {	1✔
289	//null and empty is interpreted as (Theta = 1.0, count = 0, empty = T). Nothing changes
290	return;	1✔
291	}
292	//sketchIn is valid and not empty
293	Util.checkSeedHashes(seedHash_, sketchIn.getSeedHash());	1✔
294	if (sketchIn instanceof SingleItemSketch) {	1✔
295	gadget_.hashUpdate(sketchIn.getCache()[0]);	1✔
296	return;	1✔
297	}
298	Sketch.checkSketchAndMemoryFlags(sketchIn);	1✔
299
300	unionThetaLong_ = min(min(unionThetaLong_, sketchIn.getThetaLong()), gadget_.getThetaLong()); //Theta rule	1✔
301	unionEmpty_ = false;	1✔
302	final int curCountIn = sketchIn.getRetainedEntries(true);	1✔
303	if (curCountIn > 0) {	1✔
304	if (sketchIn.isOrdered()) { //Only true if Compact. Use early stop	1✔
305	//Ordered, thus compact
306	if (sketchIn.hasMemory()) {	1✔
307	final Memory skMem = ((CompactSketch) sketchIn).getMemory();	1✔
308	final int preambleLongs = skMem.getByte(PREAMBLE_LONGS_BYTE) & 0X3F;	1✔
309	for (int i = 0; i < curCountIn; i++ ) {	1✔
310	final int offsetBytes = preambleLongs + i << 3;	1✔
311	final long hashIn = skMem.getLong(offsetBytes);	1✔
312	if (hashIn >= unionThetaLong_) { break; } // "early stop"	1✔
313	gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed	1✔
314	}
315	}	1✔
316	else { //sketchIn is on the Java Heap or has array
317	final long[] cacheIn = sketchIn.getCache(); //not a copy!	1✔
318	for (int i = 0; i < curCountIn; i++ ) {	1✔
319	final long hashIn = cacheIn[i];	1✔
320	if (hashIn >= unionThetaLong_) { break; } // "early stop"	1✔
321	gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed	1✔
322	}
323	}	1✔
324	} //End ordered, compact
325	else { //either not-ordered compact or Hash Table form. A HT may have dirty values.
326	final long[] cacheIn = sketchIn.getCache(); //if off-heap this will be a copy	1✔
327	final int arrLongs = cacheIn.length;	1✔
328	for (int i = 0, c = 0; i < arrLongs && c < curCountIn; i++ ) {	1✔
329	final long hashIn = cacheIn[i];	1✔
330	if (hashIn <= 0L \|\| hashIn >= unionThetaLong_) { continue; } //rejects dirty values	1✔
331	gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed	1✔
332	c++; //ensures against invalid state inside the incoming sketch	1✔
333	}
334	}
335	}
336	unionThetaLong_ = min(unionThetaLong_, gadget_.getThetaLong()); //Theta rule with gadget	1✔
337	if (gadget_.hasMemory()) {	1✔
338	final WritableMemory wmem = (WritableMemory)gadget_.getMemory();	1✔
339	PreambleUtil.insertUnionThetaLong(wmem, unionThetaLong_);	1✔
340	PreambleUtil.clearEmpty(wmem);	1✔
341	}
342	}	1✔
343
344	@Override
345	public void union(final Memory skMem) {
346	if (skMem == null) { return; }	1✔
347	final int cap = (int) skMem.getCapacity();	1✔
348	if (cap < 16) { return; } //empty or garbage	1✔
349	final int serVer = extractSerVer(skMem);	1✔
350	final int fam = extractFamilyID(skMem);	1✔
351
352	if (serVer == 3) { //The OpenSource sketches (Aug 4, 2015) starts with serVer = 3	1✔
353	if (fam < 1 \|\| fam > 3) {	1✔
354	throw new SketchesArgumentException(	1✔
355	"Family must be Alpha, QuickSelect, or Compact: " + Family.idToFamily(fam));	×
356	}
357	processVer3(skMem);	1✔
358	return;	1✔
359	}
360
361	if (serVer == 2) { //older Sketch, which is compact and ordered	1✔
362	Util.checkSeedHashes(seedHash_, (short)extractSeedHash(skMem));	1✔
363	final CompactSketch csk = ForwardCompatibility.heapify2to3(skMem,seedHash_);	1✔
364	union(csk);	1✔
365	return;	1✔
366	}
367
368	if (serVer == 1) { //much older Sketch, which is compact and ordered, no seedHash	1✔
369	final CompactSketch csk = ForwardCompatibility.heapify1to3(skMem, seedHash_);	1✔
370	union(csk);	1✔
371	return;	1✔
372	}
373
374	throw new SketchesArgumentException("SerVer is unknown: " + serVer);	1✔
375	}
376
377	//Has seedHash, p, could have 0 entries & theta < 1.0,
378	//could be unordered, ordered, compact, or not compact,
379	//could be Alpha, QuickSelect, or Compact.
380	private void processVer3(final Memory skMem) {
381	final int preLongs = extractPreLongs(skMem);	1✔
382
383	if (preLongs == 1) {	1✔
384	if (otherCheckForSingleItem(skMem)) {	1✔
385	final long hash = skMem.getLong(8);	1✔
386	gadget_.hashUpdate(hash);	1✔
387	return;	1✔
388	}
389	return; //empty	1✔
390	}
391	Util.checkSeedHashes(seedHash_, (short)extractSeedHash(skMem));	1✔
392	final int curCountIn;
393	final long thetaLongIn;
394
395	if (preLongs == 2) { //exact mode	1✔
396	curCountIn = extractCurCount(skMem);	1✔
397	if (curCountIn == 0) { return; } //should be > 0, but if it is 0 return empty anyway.	1✔
398	thetaLongIn = Long.MAX_VALUE;	1✔
399	}
400
401	else { //prelongs == 3
402	//curCount may be 0 (e.g., from intersection); but sketch cannot be empty.
403	curCountIn = extractCurCount(skMem);	1✔
404	thetaLongIn = extractThetaLong(skMem);	1✔
405	}
406
407	unionThetaLong_ = min(min(unionThetaLong_, thetaLongIn), gadget_.getThetaLong()); //theta rule	1✔
408	unionEmpty_ = false;	1✔
409	final int flags = extractFlags(skMem);	1✔
410	final boolean ordered = (flags & ORDERED_FLAG_MASK) != 0;	1✔
411	if (ordered) { //must be compact	1✔
412
413	for (int i = 0; i < curCountIn; i++ ) {	1✔
414	final int offsetBytes = preLongs + i << 3;	1✔
415	final long hashIn = skMem.getLong(offsetBytes);	1✔
416	if (hashIn >= unionThetaLong_) { break; } // "early stop"	1✔
417	gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed	1✔
418	}
419	}
420
421	else { //not-ordered, could be compact or hash-table form
422	final boolean compact = (flags & COMPACT_FLAG_MASK) != 0;	1✔
423	final int size = compact ? curCountIn : 1 << extractLgArrLongs(skMem);	1✔
424
425	for (int i = 0; i < size; i++ ) {	1✔
426	final int offsetBytes = preLongs + i << 3;	1✔
427	final long hashIn = skMem.getLong(offsetBytes);	1✔
428	if (hashIn <= 0L \|\| hashIn >= unionThetaLong_) { continue; }	1✔
429	gadget_.hashUpdate(hashIn); //backdoor update, hash function is bypassed	1✔
430	}
431	}
432
433	unionThetaLong_ = min(unionThetaLong_, gadget_.getThetaLong()); //sync thetaLongs	1✔
434
435	if (gadget_.hasMemory()) {	1✔
436	final WritableMemory wmem = (WritableMemory)gadget_.getMemory();	1✔
437	PreambleUtil.insertUnionThetaLong(wmem, unionThetaLong_);	1✔
438	PreambleUtil.clearEmpty(wmem);	1✔
439	}
440	}	1✔
441
442	@Override
443	public void update(final long datum) {
444	gadget_.update(datum);	1✔
445	}	1✔
446
447	@Override
448	public void update(final double datum) {
449	gadget_.update(datum);	1✔
450	}	1✔
451
452	@Override
453	public void update(final String datum) {
454	gadget_.update(datum);	1✔
455	}	1✔
456
457	@Override
458	public void update(final byte[] data) {
459	gadget_.update(data);	1✔
460	}	1✔
461
462	@Override
463	public void update(final char[] data) {
464	gadget_.update(data);	1✔
465	}	1✔
466
467	@Override
468	public void update(final int[] data) {
469	gadget_.update(data);	1✔
470	}	1✔
471
472	@Override
473	public void update(final long[] data) {
474	gadget_.update(data);	1✔
475	}	1✔
476
477	//Restricted
478
479	@Override
480	long[] getCache() {
481	return gadget_.getCache();	1✔
482	}
483
484	@Override
485	int getRetainedEntries() {
486	return gadget_.getRetainedEntries(true);	1✔
487	}
488
489	@Override
490	short getSeedHash() {
491	return gadget_.getSeedHash();	1✔
492	}
493
494	@Override
495	long getThetaLong() {
496	return min(unionThetaLong_, gadget_.getThetaLong());	1✔
497	}
498
499	@Override
500	boolean isEmpty() {
501	return gadget_.isEmpty() && unionEmpty_;	1✔
502	}
503
504	}

apache / datasketches-java / #132

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