src/main/java/org/apache/datasketches/hll/Conversions.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.hll;

import static org.apache.datasketches.hll.HllUtil.AUX_TOKEN;
import static org.apache.datasketches.hll.HllUtil.EMPTY;
import static org.apache.datasketches.hll.HllUtil.LG_AUX_ARR_INTS;

/**
 * Converters for one TgtHllType to another.  The source can be heap or direct, but the result is
 * always on heap. These conversions only apply to sketches in HLL (dense) mode.
 *
 * @author Lee Rhodes
 */
class Conversions {

  static final Hll4Array convertToHll4(final AbstractHllArray srcAbsHllArr) {
    final int lgConfigK = srcAbsHllArr.getLgConfigK();
    final Hll4Array hll4Array = new Hll4Array(lgConfigK);
    hll4Array.putOutOfOrder(srcAbsHllArr.isOutOfOrder());

    //1st pass: compute starting curMin and numAtCurMin:
    final int pair = curMinAndNum(srcAbsHllArr);
    final int curMin = HllUtil.getPairValue(pair);
    final int numAtCurMin = HllUtil.getPairLow26(pair);

    //2nd pass: Must know curMin to create AuxHashMap.
    //Populate KxQ registers, build AuxHashMap if needed
    final PairIterator itr = srcAbsHllArr.iterator();
    AuxHashMap auxHashMap = hll4Array.getAuxHashMap(); //may be null
    while (itr.nextValid()) {
      final int slotNo = itr.getIndex();
      final int actualValue = itr.getValue();
      AbstractHllArray.hipAndKxQIncrementalUpdate(hll4Array, 0, actualValue);
      if (actualValue >= (curMin + 15)) {
        hll4Array.putNibble(slotNo, AUX_TOKEN);
        if (auxHashMap == null) {
          auxHashMap = new HeapAuxHashMap(LG_AUX_ARR_INTS[lgConfigK], lgConfigK);
          hll4Array.putAuxHashMap(auxHashMap, false);
        }
        auxHashMap.mustAdd(slotNo, actualValue);
      } else {
        hll4Array.putNibble(slotNo, actualValue - curMin);
      }
    }

    hll4Array.putCurMin(curMin);
    hll4Array.putNumAtCurMin(numAtCurMin);
    hll4Array.putHipAccum(srcAbsHllArr.getHipAccum()); //intentional overwrite
    hll4Array.putRebuildCurMinNumKxQFlag(false);
    return hll4Array;
  }

  /**
   * This returns curMin and numAtCurMin as a pair and will be correct independent of the TgtHllType
   * of the input AbstractHllArray.
   *
   * <p>In general, it is always true that for HLL_6 and HLL_8, curMin is always 0, and numAtCurMin
   * is the number of zero slots. For these two types there is no need to track curMin nor to track
   * numAtCurMin once all the slots are filled.
   *
   * @param absHllArr an instance of AbstractHllArray
   * @return pair values representing numAtCurMin and curMin
   */
  static final int curMinAndNum(final AbstractHllArray absHllArr) {
    int curMin = 64;
    int numAtCurMin = 0;
    final PairIterator itr = absHllArr.iterator();
    while (itr.nextAll()) {
      final int v = itr.getValue();
      if (v > curMin) { continue; }
      if (v < curMin) {
        curMin = v;
        numAtCurMin = 1;
      } else {
        numAtCurMin++;
      }
    }
    return HllUtil.pair(numAtCurMin, curMin);
  }

  static final Hll6Array convertToHll6(final AbstractHllArray srcAbsHllArr) {
    final int lgConfigK = srcAbsHllArr.lgConfigK;
    final Hll6Array hll6Array = new Hll6Array(lgConfigK);
    hll6Array.putOutOfOrder(srcAbsHllArr.isOutOfOrder());
    int numZeros = 1 << lgConfigK;
    final PairIterator itr = srcAbsHllArr.iterator();
    while (itr.nextAll()) {
      if (itr.getValue() != EMPTY) {
        numZeros--;
        hll6Array.couponUpdate(itr.getPair()); //couponUpdate creates KxQ registers
      }
    }
    hll6Array.putNumAtCurMin(numZeros);
    hll6Array.putHipAccum(srcAbsHllArr.getHipAccum()); //intentional overwrite
    hll6Array.putRebuildCurMinNumKxQFlag(false);
    return hll6Array;
  }

  static final Hll8Array convertToHll8(final AbstractHllArray srcAbsHllArr) {
    final int lgConfigK = srcAbsHllArr.lgConfigK;
    final Hll8Array hll8Array = new Hll8Array(lgConfigK);
    hll8Array.putOutOfOrder(srcAbsHllArr.isOutOfOrder());
    int numZeros = 1 << lgConfigK;
    final PairIterator itr = srcAbsHllArr.iterator();
    while (itr.nextAll()) {
      if (itr.getValue() != EMPTY) {
        numZeros--;
        hll8Array.couponUpdate(itr.getPair()); //creates KxQ registers
      }
    }
    hll8Array.putNumAtCurMin(numZeros);
    hll8Array.putHipAccum(srcAbsHllArr.getHipAccum()); //intentional overwrite
    hll8Array.putRebuildCurMinNumKxQFlag(false);
    return hll8Array;
  }

}