static void compressWhileUpdatingSketch()

in src/main/java/org/apache/datasketches/kll/KllHelper.java [143:249]
85 lines of code
16 McCabe index (conditional complexity)

  static void compressWhileUpdatingSketch(final KllSketch sketch) {
    final SketchType sketchType = sketch.sketchType;
    final int level =
        findLevelToCompact(sketch.getK(), sketch.getM(), sketch.getNumLevels(), sketch.getLevelsArray());
    if (level == sketch.getNumLevels() - 1) {
      //The level to compact is the top level, thus we need to add a level.
      //Be aware that this operation grows the items array,
      //shifts the items data and the level boundaries of the data,
      //and grows the levels array and increments numLevels_.
      KllHelper.addEmptyTopLevelToCompletelyFullSketch(sketch);
    }
    //after this point, the levelsArray will not be expanded, only modified.
    final int[] myLevelsArr = sketch.getLevelsArray();
    final int rawBeg = myLevelsArr[level];
    final int rawEnd = myLevelsArr[level + 1];
    // +2 is OK because we already added a new top level if necessary
    final int popAbove = myLevelsArr[level + 2] - rawEnd;
    final int rawPop = rawEnd - rawBeg;
    final boolean oddPop = isOdd(rawPop);
    final int adjBeg = oddPop ? rawBeg + 1 : rawBeg;
    final int adjPop = oddPop ? rawPop - 1 : rawPop;
    final int halfAdjPop = adjPop / 2;

    if (sketchType == DOUBLES_SKETCH) {
      final KllDoublesSketch dblSk = (KllDoublesSketch) sketch;
      final double[] myDoubleItemsArr = dblSk.getDoubleItemsArray();
      if (level == 0) { // level zero might not be sorted, so we must sort it if we wish to compact it
        Arrays.sort(myDoubleItemsArr, adjBeg, adjBeg + adjPop);
      }
      if (popAbove == 0) {
        KllDoublesHelper.randomlyHalveUpDoubles(myDoubleItemsArr, adjBeg, adjPop, KllSketch.random);
      } else {
        KllDoublesHelper.randomlyHalveDownDoubles(myDoubleItemsArr, adjBeg, adjPop, KllSketch.random);
        KllDoublesHelper.mergeSortedDoubleArrays(
            myDoubleItemsArr, adjBeg, halfAdjPop,
            myDoubleItemsArr, rawEnd, popAbove,
            myDoubleItemsArr, adjBeg + halfAdjPop);
      }

      int newIndex = myLevelsArr[level + 1] - halfAdjPop;  // adjust boundaries of the level above
      dblSk.setLevelsArrayAt(level + 1, newIndex);

      if (oddPop) {
        dblSk.setLevelsArrayAt(level, myLevelsArr[level + 1] - 1); // the current level now contains one item
        myDoubleItemsArr[myLevelsArr[level]] = myDoubleItemsArr[rawBeg];  // namely this leftover guy
      } else {
        dblSk.setLevelsArrayAt(level, myLevelsArr[level + 1]); // the current level is now empty
      }

      // verify that we freed up halfAdjPop array slots just below the current level
      assert myLevelsArr[level] == rawBeg + halfAdjPop;

   // finally, we need to shift up the data in the levels below
      // so that the freed-up space can be used by level zero
      if (level > 0) {
        final int amount = rawBeg - myLevelsArr[0];
        System.arraycopy(myDoubleItemsArr, myLevelsArr[0], myDoubleItemsArr, myLevelsArr[0] + halfAdjPop, amount);
      }
      for (int lvl = 0; lvl < level; lvl++) {
        newIndex = myLevelsArr[lvl] + halfAdjPop; //adjust boundary
        dblSk.setLevelsArrayAt(lvl, newIndex);
      }
      dblSk.setDoubleItemsArray(myDoubleItemsArr);
    }
    else if (sketchType == FLOATS_SKETCH) {
      final KllFloatsSketch fltSk = (KllFloatsSketch) sketch;
      final float[] myFloatItemsArr = fltSk.getFloatItemsArray();
      if (level == 0) { // level zero might not be sorted, so we must sort it if we wish to compact it
        Arrays.sort(myFloatItemsArr, adjBeg, adjBeg + adjPop);
      }
      if (popAbove == 0) {
        KllFloatsHelper.randomlyHalveUpFloats(myFloatItemsArr, adjBeg, adjPop, KllSketch.random);
      } else {
        KllFloatsHelper.randomlyHalveDownFloats(myFloatItemsArr, adjBeg, adjPop, KllSketch.random);
        KllFloatsHelper.mergeSortedFloatArrays(
            myFloatItemsArr, adjBeg, halfAdjPop,
            myFloatItemsArr, rawEnd, popAbove,
            myFloatItemsArr, adjBeg + halfAdjPop);
      }

      int newIndex = myLevelsArr[level + 1] - halfAdjPop;  // adjust boundaries of the level above
      fltSk.setLevelsArrayAt(level + 1, newIndex);

      if (oddPop) {
        fltSk.setLevelsArrayAt(level, myLevelsArr[level + 1] - 1); // the current level now contains one item
        myFloatItemsArr[myLevelsArr[level]] = myFloatItemsArr[rawBeg];  // namely this leftover guy
      } else {
        fltSk.setLevelsArrayAt(level, myLevelsArr[level + 1]); // the current level is now empty
      }

      // verify that we freed up halfAdjPop array slots just below the current level
      assert myLevelsArr[level] == rawBeg + halfAdjPop;

      // finally, we need to shift up the data in the levels below
      // so that the freed-up space can be used by level zero
      if (level > 0) {
        final int amount = rawBeg - myLevelsArr[0];
        System.arraycopy(myFloatItemsArr, myLevelsArr[0], myFloatItemsArr, myLevelsArr[0] + halfAdjPop, amount);
      }
      for (int lvl = 0; lvl < level; lvl++) {
        newIndex = myLevelsArr[lvl] + halfAdjPop; //adjust boundary
        fltSk.setLevelsArrayAt(lvl, newIndex);
      }
      fltSk.setFloatItemsArray(myFloatItemsArr);
    }
    //TODO add items
  }