@Test public void testSplitBar() { EquiDepthStreamHistogram histo = new EquiDepthStreamHistogram(10); Bar targetBar = new Bar(bytesA, bytesC); targetBar.incrementCount(31); histo.bars.add(targetBar); histo.splitBar(targetBar); assertEquals(2, histo.bars.size()); Bar newLeft = histo.bars.get(0); assertArrayEquals(bytesA, newLeft.getLeftBoundInclusive()); assertArrayEquals(bytesB, newLeft.getRightBoundExclusive()); assertEquals(15, newLeft.getSize()); Bar newRight = histo.bars.get(1); assertArrayEquals(bytesB, newRight.getLeftBoundInclusive()); assertArrayEquals(bytesC, newRight.getRightBoundExclusive()); assertEquals(16, newRight.getSize()); histo.bars.clear(); targetBar = new Bar(bytesA, bytesE); targetBar.incrementCount(10); a_b.incrementCount(3); targetBar.addBlockedBar(a_b); b_c.incrementCount(4); targetBar.addBlockedBar(b_c); c_d.incrementCount(2); targetBar.addBlockedBar(c_d); d_e.incrementCount(1); targetBar.addBlockedBar(d_e); histo.bars.add(targetBar); histo.splitBar(targetBar); newLeft = histo.bars.get(0); newRight = histo.bars.get(1); assertEquals(10, newLeft.getSize()); assertEquals(a_b, newLeft.getBlockedBars().get(0)); assertEquals(d_e, newLeft.getBlockedBars().get(1)); assertEquals(10, newRight.getSize()); assertEquals(b_c, newRight.getBlockedBars().get(0)); assertEquals(c_d, newRight.getBlockedBars().get(1)); }
@VisibleForTesting void splitBar(Bar origBar) { if (Bytes.compareTo(origBar.leftBoundInclusive, origBar.rightBoundExclusive) == 0) { return; } if (bars.size() == maxBars) { boolean mergeSuccessful = mergeBars(); if (!mergeSuccessful) return; } byte[] mid = Bytes.split(origBar.getLeftBoundInclusive(), origBar.getRightBoundExclusive(), 1)[1]; Bar newLeft = new Bar(origBar.getLeftBoundInclusive(), mid); Bar newRight = new Bar(mid, origBar.getRightBoundExclusive()); long leftSize = 0; long bbAggCount = origBar.getBlockedBarsSize(); for (Bar bb : origBar.getBlockedBars()) { long bbSize = bb.getSize(); if (leftSize + bbSize < bbAggCount/2) { leftSize += bbSize; newLeft.addBlockedBar(bb); } else { newRight.addBlockedBar(bb); } } long countToDistribute = origBar.getSize() - bbAggCount; long rightSize = newRight.getSize(); long sizeDiff = Math.abs(leftSize - rightSize); Bar smallerBar = leftSize <= rightSize ? newLeft : newRight; if (sizeDiff <= countToDistribute) { smallerBar.incrementCount(sizeDiff); countToDistribute -= sizeDiff; long halfDistrib = countToDistribute / 2; newLeft.incrementCount(halfDistrib); newRight.incrementCount(countToDistribute - halfDistrib); } else { smallerBar.incrementCount(countToDistribute); } if (LOG.isTraceEnabled()) { LOG.trace(String.format("Split orig=%s , newLeft=%s , newRight=%s", origBar, newLeft, newRight)); } bars.remove(origBar); bars.add(newLeft); bars.add(newRight); Collections.sort(bars); }
EquiDepthStreamHistogram { @VisibleForTesting void splitBar(Bar origBar) { if (Bytes.compareTo(origBar.leftBoundInclusive, origBar.rightBoundExclusive) == 0) { return; } if (bars.size() == maxBars) { boolean mergeSuccessful = mergeBars(); if (!mergeSuccessful) return; } byte[] mid = Bytes.split(origBar.getLeftBoundInclusive(), origBar.getRightBoundExclusive(), 1)[1]; Bar newLeft = new Bar(origBar.getLeftBoundInclusive(), mid); Bar newRight = new Bar(mid, origBar.getRightBoundExclusive()); long leftSize = 0; long bbAggCount = origBar.getBlockedBarsSize(); for (Bar bb : origBar.getBlockedBars()) { long bbSize = bb.getSize(); if (leftSize + bbSize < bbAggCount/2) { leftSize += bbSize; newLeft.addBlockedBar(bb); } else { newRight.addBlockedBar(bb); } } long countToDistribute = origBar.getSize() - bbAggCount; long rightSize = newRight.getSize(); long sizeDiff = Math.abs(leftSize - rightSize); Bar smallerBar = leftSize <= rightSize ? newLeft : newRight; if (sizeDiff <= countToDistribute) { smallerBar.incrementCount(sizeDiff); countToDistribute -= sizeDiff; long halfDistrib = countToDistribute / 2; newLeft.incrementCount(halfDistrib); newRight.incrementCount(countToDistribute - halfDistrib); } else { smallerBar.incrementCount(countToDistribute); } if (LOG.isTraceEnabled()) { LOG.trace(String.format("Split orig=%s , newLeft=%s , newRight=%s", origBar, newLeft, newRight)); } bars.remove(origBar); bars.add(newLeft); bars.add(newRight); Collections.sort(bars); } }
EquiDepthStreamHistogram { @VisibleForTesting void splitBar(Bar origBar) { if (Bytes.compareTo(origBar.leftBoundInclusive, origBar.rightBoundExclusive) == 0) { return; } if (bars.size() == maxBars) { boolean mergeSuccessful = mergeBars(); if (!mergeSuccessful) return; } byte[] mid = Bytes.split(origBar.getLeftBoundInclusive(), origBar.getRightBoundExclusive(), 1)[1]; Bar newLeft = new Bar(origBar.getLeftBoundInclusive(), mid); Bar newRight = new Bar(mid, origBar.getRightBoundExclusive()); long leftSize = 0; long bbAggCount = origBar.getBlockedBarsSize(); for (Bar bb : origBar.getBlockedBars()) { long bbSize = bb.getSize(); if (leftSize + bbSize < bbAggCount/2) { leftSize += bbSize; newLeft.addBlockedBar(bb); } else { newRight.addBlockedBar(bb); } } long countToDistribute = origBar.getSize() - bbAggCount; long rightSize = newRight.getSize(); long sizeDiff = Math.abs(leftSize - rightSize); Bar smallerBar = leftSize <= rightSize ? newLeft : newRight; if (sizeDiff <= countToDistribute) { smallerBar.incrementCount(sizeDiff); countToDistribute -= sizeDiff; long halfDistrib = countToDistribute / 2; newLeft.incrementCount(halfDistrib); newRight.incrementCount(countToDistribute - halfDistrib); } else { smallerBar.incrementCount(countToDistribute); } if (LOG.isTraceEnabled()) { LOG.trace(String.format("Split orig=%s , newLeft=%s , newRight=%s", origBar, newLeft, newRight)); } bars.remove(origBar); bars.add(newLeft); bars.add(newRight); Collections.sort(bars); } EquiDepthStreamHistogram(int numBuckets);  EquiDepthStreamHistogram(int numBuckets, int expansionFactor); }
EquiDepthStreamHistogram { @VisibleForTesting void splitBar(Bar origBar) { if (Bytes.compareTo(origBar.leftBoundInclusive, origBar.rightBoundExclusive) == 0) { return; } if (bars.size() == maxBars) { boolean mergeSuccessful = mergeBars(); if (!mergeSuccessful) return; } byte[] mid = Bytes.split(origBar.getLeftBoundInclusive(), origBar.getRightBoundExclusive(), 1)[1]; Bar newLeft = new Bar(origBar.getLeftBoundInclusive(), mid); Bar newRight = new Bar(mid, origBar.getRightBoundExclusive()); long leftSize = 0; long bbAggCount = origBar.getBlockedBarsSize(); for (Bar bb : origBar.getBlockedBars()) { long bbSize = bb.getSize(); if (leftSize + bbSize < bbAggCount/2) { leftSize += bbSize; newLeft.addBlockedBar(bb); } else { newRight.addBlockedBar(bb); } } long countToDistribute = origBar.getSize() - bbAggCount; long rightSize = newRight.getSize(); long sizeDiff = Math.abs(leftSize - rightSize); Bar smallerBar = leftSize <= rightSize ? newLeft : newRight; if (sizeDiff <= countToDistribute) { smallerBar.incrementCount(sizeDiff); countToDistribute -= sizeDiff; long halfDistrib = countToDistribute / 2; newLeft.incrementCount(halfDistrib); newRight.incrementCount(countToDistribute - halfDistrib); } else { smallerBar.incrementCount(countToDistribute); } if (LOG.isTraceEnabled()) { LOG.trace(String.format("Split orig=%s , newLeft=%s , newRight=%s", origBar, newLeft, newRight)); } bars.remove(origBar); bars.add(newLeft); bars.add(newRight); Collections.sort(bars); } EquiDepthStreamHistogram(int numBuckets);  EquiDepthStreamHistogram(int numBuckets, int expansionFactor); void addValue(byte[] value); List<Bucket> computeBuckets(); long getTotalCount(); }
EquiDepthStreamHistogram { @VisibleForTesting void splitBar(Bar origBar) { if (Bytes.compareTo(origBar.leftBoundInclusive, origBar.rightBoundExclusive) == 0) { return; } if (bars.size() == maxBars) { boolean mergeSuccessful = mergeBars(); if (!mergeSuccessful) return; } byte[] mid = Bytes.split(origBar.getLeftBoundInclusive(), origBar.getRightBoundExclusive(), 1)[1]; Bar newLeft = new Bar(origBar.getLeftBoundInclusive(), mid); Bar newRight = new Bar(mid, origBar.getRightBoundExclusive()); long leftSize = 0; long bbAggCount = origBar.getBlockedBarsSize(); for (Bar bb : origBar.getBlockedBars()) { long bbSize = bb.getSize(); if (leftSize + bbSize < bbAggCount/2) { leftSize += bbSize; newLeft.addBlockedBar(bb); } else { newRight.addBlockedBar(bb); } } long countToDistribute = origBar.getSize() - bbAggCount; long rightSize = newRight.getSize(); long sizeDiff = Math.abs(leftSize - rightSize); Bar smallerBar = leftSize <= rightSize ? newLeft : newRight; if (sizeDiff <= countToDistribute) { smallerBar.incrementCount(sizeDiff); countToDistribute -= sizeDiff; long halfDistrib = countToDistribute / 2; newLeft.incrementCount(halfDistrib); newRight.incrementCount(countToDistribute - halfDistrib); } else { smallerBar.incrementCount(countToDistribute); } if (LOG.isTraceEnabled()) { LOG.trace(String.format("Split orig=%s , newLeft=%s , newRight=%s", origBar, newLeft, newRight)); } bars.remove(origBar); bars.add(newLeft); bars.add(newRight); Collections.sort(bars); } EquiDepthStreamHistogram(int numBuckets);  EquiDepthStreamHistogram(int numBuckets, int expansionFactor); void addValue(byte[] value); List<Bucket> computeBuckets(); long getTotalCount();  }