intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 637 insertions, 0 deletions

diff --git a/library/cpp/histogram/adaptive/adaptive_histogram.cpp b/library/cpp/histogram/adaptive/adaptive_histogram.cpp
new file mode 100644
index 0000000000..cbfc494021
--- /dev/null
+++ b/library/cpp/histogram/adaptive/adaptive_histogram.cpp
@@ -0,0 +1,637 @@
+#include "adaptive_histogram.h"
+
+#include <util/generic/algorithm.h>
+#include <util/generic/yexception.h>
+#include <util/generic/ymath.h>
+#include <util/string/printf.h>
+
+#include <util/system/backtrace.h>
+
+namespace NKiwiAggr {
+    TAdaptiveHistogram::TAdaptiveHistogram(size_t intervals, ui64 id, TQualityFunction qualityFunc)
+        : Id(id)
+        , Sum(0.0)
+        , Intervals(intervals)
+        , CalcQuality(qualityFunc)
+    {
+    }
+
+    TAdaptiveHistogram::TAdaptiveHistogram(const THistogram& histo, size_t defaultIntervals, ui64 defaultId, TQualityFunction qualityFunc)
+        : TAdaptiveHistogram(defaultIntervals, defaultId, qualityFunc)
+    {
+        FromProto(histo);
+    }
+
+    TAdaptiveHistogram::TAdaptiveHistogram(IHistogram* histo, size_t defaultIntervals, ui64 defaultId, TQualityFunction qualityFunc)
+        : TAdaptiveHistogram(defaultIntervals, defaultId, qualityFunc)
+    {
+        TAdaptiveHistogram* adaptiveHisto = dynamic_cast<TAdaptiveHistogram*>(histo);
+        if (!adaptiveHisto) {
+            FromIHistogram(histo);
+            return;
+        }
+        Id = adaptiveHisto->Id;
+        MinValue = adaptiveHisto->MinValue;
+        MaxValue = adaptiveHisto->MaxValue;
+        Sum = adaptiveHisto->Sum;
+        Intervals = adaptiveHisto->Intervals;
+        Bins = adaptiveHisto->Bins;
+        BinsByQuality = adaptiveHisto->BinsByQuality;
+        if (CalcQuality == nullptr) {
+            CalcQuality = adaptiveHisto->CalcQuality;
+        }
+    }
+
+    TQualityFunction TAdaptiveHistogram::GetQualityFunc() {
+        return CalcQuality;
+    }
+
+    void TAdaptiveHistogram::Clear() {
+        Sum = 0.0;
+        Bins.clear();
+        BinsByQuality.clear();
+    }
+
+    void TAdaptiveHistogram::Add(const THistoRec& histoRec) {
+        if (!histoRec.HasId() || histoRec.GetId() == Id) {
+            Add(histoRec.GetValue(), histoRec.GetWeight());
+        }
+    }
+
+    void TAdaptiveHistogram::Add(double value, double weight) {
+        if (!IsValidFloat(value) || !IsValidFloat(weight)) {
+            ythrow yexception() << Sprintf("Histogram id %lu: bad value %f weight %f", Id, value, weight);
+        }
+        TWeightedValue weightedValue(value, weight);
+        Add(weightedValue, true);
+        PrecomputedBins.clear();
+    }
+
+    void TAdaptiveHistogram::Merge(const THistogram& histo, double multiplier) {
+        if (!IsValidFloat(histo.GetMinValue()) || !IsValidFloat(histo.GetMaxValue())) {
+            fprintf(stderr, "Merging in histogram id %lu: skip bad histo with minvalue %f maxvalue %f\n", Id, histo.GetMinValue(), histo.GetMaxValue());
+            return;
+        }
+        if (histo.FreqSize() == 0) {
+            return; // skip empty histos
+        }
+        if (histo.GetType() == HT_ADAPTIVE_DISTANCE_HISTOGRAM ||
+            histo.GetType() == HT_ADAPTIVE_WEIGHT_HISTOGRAM ||
+            histo.GetType() == HT_ADAPTIVE_WARD_HISTOGRAM ||
+            histo.GetType() == HT_ADAPTIVE_HISTOGRAM)
+        {
+            Y_VERIFY(histo.FreqSize() == histo.PositionSize(), "Corrupted histo");
+            for (size_t j = 0; j < histo.FreqSize(); ++j) {
+                double value = histo.GetPosition(j);
+                double weight = histo.GetFreq(j);
+                if (!IsValidFloat(value) || !IsValidFloat(weight)) {
+                    fprintf(stderr, "Merging in histogram id %lu: skip bad value %f weight %f\n", Id, value, weight);
+                    continue;
+                }
+                Add(value, weight * multiplier);
+            }
+
+            MinValue = Min(MinValue, histo.GetMinValue());
+            MaxValue = Max(MaxValue, histo.GetMaxValue());
+        } else if (histo.GetType() == HT_FIXED_BIN_HISTOGRAM) {
+            double pos = histo.GetMinValue() + histo.GetBinRange() / 2.0;
+            for (size_t j = 0; j < histo.FreqSize(); ++j) {
+                double weight = histo.GetFreq(j);
+                if (!IsValidFloat(pos) || !IsValidFloat(weight)) {
+                    fprintf(stderr, "Merging in histogram id %lu: skip bad value %f weight %f\n", Id, pos, weight);
+                    pos += histo.GetBinRange();
+                    continue;
+                }
+                Add(pos, weight * multiplier);
+                pos += histo.GetBinRange();
+            }
+
+            MinValue = Min(MinValue, histo.GetMinValue());
+            MaxValue = Max(MaxValue, histo.GetMaxValue());
+        } else {
+            ythrow yexception() << "Unknown THistogram type";
+        }
+    }
+
+    void TAdaptiveHistogram::Merge(const TVector<THistogram>& histogramsToMerge) {
+        for (size_t i = 0; i < histogramsToMerge.size(); ++i) {
+            Merge(histogramsToMerge[i], 1.0);
+        }
+    }
+
+    void TAdaptiveHistogram::Merge(TVector<IHistogramPtr> histogramsToMerge) {
+        TVector<IHistogramPtr> histogramsToMergeRepacked(0);
+        TVector<TAdaptiveHistogram*> histograms(0);
+        for (size_t i = 0; i < histogramsToMerge.size(); ++i) {
+            if (!histogramsToMerge[i] || histogramsToMerge[i]->Empty()) {
+                continue;
+            }
+            TAdaptiveHistogram* adaptiveHisto = dynamic_cast<TAdaptiveHistogram*>(histogramsToMerge[i].Get());
+            if (adaptiveHisto) {
+                histogramsToMergeRepacked.push_back(histogramsToMerge[i]);
+            } else {
+                histogramsToMergeRepacked.push_back(IHistogramPtr(new TAdaptiveHistogram(histogramsToMerge[i].Get(), Intervals, Id, CalcQuality))); // Convert histograms that are not of TFixedBinHistogram type
+            }
+            if (histogramsToMergeRepacked.back()->Empty()) {
+                continue;
+            }
+            histograms.push_back(dynamic_cast<TAdaptiveHistogram*>(histogramsToMergeRepacked.back().Get()));
+        }
+
+        if (histograms.size() == 0) {
+            return;
+        }
+
+        for (size_t histoIndex = 0; histoIndex < histograms.size(); ++histoIndex) {
+            TAdaptiveHistogram* histo = histograms[histoIndex];
+            for (TPairSet::const_iterator it = histo->Bins.begin(); it != histo->Bins.end(); ++it) {
+                Add(*it, true);
+            }
+        }
+
+        for (size_t i = 0; i < histograms.size(); ++i) {
+            MinValue = Min(MinValue, histograms[i]->MinValue);
+            MaxValue = Max(MaxValue, histograms[i]->MaxValue);
+        }
+    }
+
+    void TAdaptiveHistogram::Multiply(double factor) {
+        if (!IsValidFloat(factor) || factor <= 0) {
+            ythrow yexception() << "Not valid factor in IHistogram::Multiply(): " << factor;
+        }
+        Sum *= factor;
+
+        TPairSet newBins;
+        for (TPairSet::iterator it = Bins.begin(); it != Bins.end(); ++it) {
+            newBins.insert(TWeightedValue(it->first, it->second * factor));
+        }
+        Bins = newBins;
+
+        TPairSet newBinsByQuality;
+        for (TPairSet::iterator it = Bins.begin(); it != Bins.end(); ++it) {
+            TPairSet::iterator rightBin = it;
+            ++rightBin;
+            if (rightBin == Bins.end()) {
+                break;
+            }
+            newBinsByQuality.insert(CalcQuality(*it, *rightBin));
+        }
+        BinsByQuality = newBinsByQuality;
+    }
+
+    void TAdaptiveHistogram::FromProto(const THistogram& histo) {
+        Y_VERIFY(histo.HasType(), "Attempt to parse TAdaptiveHistogram from THistogram protobuf with no Type field set");
+        ;
+        switch (histo.GetType()) { // check that histogram type could be deduced
+            case HT_ADAPTIVE_DISTANCE_HISTOGRAM:
+            case HT_ADAPTIVE_WEIGHT_HISTOGRAM:
+            case HT_ADAPTIVE_WARD_HISTOGRAM:
+                break; // ok
+            case HT_ADAPTIVE_HISTOGRAM:
+                if (CalcQuality != nullptr)
+                    break; // ok
+                [[fallthrough]];
+            default:       // not ok
+                ythrow yexception() << "Attempt to parse TAdaptiveHistogram from THistogram protobuf record of type = " << (ui32)histo.GetType();
+        }
+
+        if (histo.FreqSize() != histo.PositionSize()) {
+            ythrow yexception() << "Attempt to parse TAdaptiveHistogram from THistogram protobuf record where FreqSize != PositionSize. FreqSize == " << (ui32)histo.FreqSize() << ", PositionSize == " << (ui32)histo.PositionSize();
+        }
+        if (CalcQuality == nullptr) {
+            if (histo.GetType() == HT_ADAPTIVE_DISTANCE_HISTOGRAM) {
+                CalcQuality = CalcDistanceQuality;
+            } else if (histo.GetType() == HT_ADAPTIVE_WEIGHT_HISTOGRAM) {
+                CalcQuality = CalcWeightQuality;
+            } else if (histo.GetType() == HT_ADAPTIVE_WARD_HISTOGRAM) {
+                CalcQuality = CalcWardQuality;
+            } else {
+                ythrow yexception() << "Attempt to parse an HT_ADAPTIVE_HISTOGRAM without default quality function";
+            }
+        }
+        Id = histo.GetId();
+        Sum = 0.0;
+        Intervals = Max(Intervals, histo.FreqSize());
+        for (size_t i = 0; i < histo.FreqSize(); ++i) {
+            double value = histo.GetPosition(i);
+            double weight = histo.GetFreq(i);
+            if (!IsValidFloat(value) || !IsValidFloat(weight)) {
+                fprintf(stderr, "FromProto in histogram id %lu: skip bad value %f weight %f\n", Id, value, weight);
+                continue;
+            }
+            Add(value, weight);
+        }
+
+        if (!IsValidFloat(histo.GetMinValue()) || !IsValidFloat(histo.GetMaxValue())) {
+            ythrow yexception() << Sprintf("FromProto in histogram id %lu: skip bad histo with minvalue %f maxvalue %f", Id, histo.GetMinValue(), histo.GetMaxValue());
+        }
+
+        MinValue = histo.GetMinValue();
+        MaxValue = histo.GetMaxValue();
+    }
+
+    void TAdaptiveHistogram::ToProto(THistogram& histo) {
+        histo.Clear();
+        if (CalcQuality == CalcDistanceQuality) {
+            histo.SetType(HT_ADAPTIVE_DISTANCE_HISTOGRAM);
+        } else if (CalcQuality == CalcWeightQuality) {
+            histo.SetType(HT_ADAPTIVE_WEIGHT_HISTOGRAM);
+        } else if (CalcQuality == CalcWardQuality) {
+            histo.SetType(HT_ADAPTIVE_WARD_HISTOGRAM);
+        } else {
+            histo.SetType(HT_ADAPTIVE_HISTOGRAM);
+        }
+        histo.SetId(Id);
+        if (Empty()) {
+            return;
+        }
+        histo.SetMinValue(MinValue);
+        histo.SetMaxValue(MaxValue);
+        for (TPairSet::const_iterator it = Bins.begin(); it != Bins.end(); ++it) {
+            histo.AddFreq(it->second);
+            histo.AddPosition(it->first);
+        }
+    }
+
+    void TAdaptiveHistogram::SetId(ui64 id) {
+        Id = id;
+    }
+
+    ui64 TAdaptiveHistogram::GetId() {
+        return Id;
+    }
+
+    bool TAdaptiveHistogram::Empty() {
+        return Bins.size() == 0;
+    }
+
+    double TAdaptiveHistogram::GetMinValue() {
+        return MinValue;
+    }
+
+    double TAdaptiveHistogram::GetMaxValue() {
+        return MaxValue;
+    }
+
+    double TAdaptiveHistogram::GetSum() {
+        return Sum;
+    }
+
+    double TAdaptiveHistogram::GetSumInRange(double leftBound, double rightBound) {
+        if (leftBound > rightBound) {
+            return 0.0;
+        }
+        return GetSumAboveBound(leftBound) + GetSumBelowBound(rightBound) - Sum;
+    }
+
+    double TAdaptiveHistogram::GetSumAboveBound(double bound) {
+        if (Empty()) {
+            return 0.0;
+        }
+        if (bound < MinValue) {
+            return Sum;
+        }
+        if (bound > MaxValue) {
+            return 0.0;
+        }
+
+        if (!PrecomputedBins.empty()) {
+            return GetSumAboveBoundImpl(
+                bound,
+                PrecomputedBins,
+                LowerBound(PrecomputedBins.begin(), PrecomputedBins.end(), TFastBin{bound, -1.0, 0, 0}),
+                [](const auto& it) { return it->SumAbove; });
+        } else {
+            return GetSumAboveBoundImpl(
+                bound,
+                Bins,
+                Bins.lower_bound(TWeightedValue(bound, -1.0)),
+                [this](TPairSet::const_iterator rightBin) {
+                    ++rightBin;
+                    double sum = 0;
+                    for (TPairSet::const_iterator it = rightBin; it != Bins.end(); ++it) {
+                        sum += it->second;
+                    }
+                    return sum;
+                });
+        }
+    }
+
+    double TAdaptiveHistogram::GetSumBelowBound(double bound) {
+        if (Empty()) {
+            return 0.0;
+        }
+        if (bound < MinValue) {
+            return 0.0;
+        }
+        if (bound > MaxValue) {
+            return Sum;
+        }
+
+        if (!PrecomputedBins.empty()) {
+            return GetSumBelowBoundImpl(
+                bound,
+                PrecomputedBins,
+                LowerBound(PrecomputedBins.begin(), PrecomputedBins.end(), TFastBin{bound, -1.0, 0, 0}),
+                [](const auto& it) { return it->SumBelow; });
+        } else {
+            return GetSumBelowBoundImpl(
+                bound,
+                Bins,
+                Bins.lower_bound(TWeightedValue(bound, -1.0)),
+                [this](TPairSet::const_iterator rightBin) {
+                    double sum = 0;
+                    for (TPairSet::iterator it = Bins.begin(); it != rightBin; ++it) {
+                        sum += it->second;
+                    }
+                    return sum;
+                });
+        }
+    }
+
+    double TAdaptiveHistogram::CalcUpperBound(double sum) {
+        Y_VERIFY(sum >= 0, "Sum must be >= 0");
+        if (sum == 0.0) {
+            return MinValue;
+        }
+        if (Empty()) {
+            return MaxValue;
+        }
+        TPairSet::iterator current = Bins.begin();
+        double gatheredSum = 0.0;
+        while (current != Bins.end() && gatheredSum < sum) {
+            gatheredSum += current->second;
+            ++current;
+        }
+        --current;
+        if (gatheredSum < sum) {
+            return MaxValue;
+        }
+        TWeightedValue left(MinValue, 0.0);
+        TWeightedValue right(MaxValue, 0.0);
+        if (current != Bins.begin()) {
+            TPairSet::iterator leftBin = current;
+            --leftBin;
+            left = *leftBin;
+        }
+        {
+            TPairSet::iterator rightBin = current;
+            ++rightBin;
+            if (rightBin != Bins.end()) {
+                right = *rightBin;
+            }
+        }
+        double sumToAdd = sum - (gatheredSum - current->second - left.second / 2);
+        if (sumToAdd <= ((current->second + left.second) / 2)) {
+            return left.first + 2 * sumToAdd * (current->first - left.first) / (current->second + left.second);
+        } else {
+            sumToAdd -= (current->second + left.second) / 2;
+            return current->first + 2 * sumToAdd * (right.first - current->first) / (right.second + current->second);
+        }
+    }
+
+    double TAdaptiveHistogram::CalcLowerBound(double sum) {
+        Y_VERIFY(sum >= 0, "Sum must be >= 0");
+        if (sum == 0.0) {
+            return MaxValue;
+        }
+        if (Empty()) {
+            return MinValue;
+        }
+        TPairSet::iterator current = Bins.end();
+        double gatheredSum = 0.0;
+        while (current != Bins.begin() && gatheredSum < sum) {
+            --current;
+            gatheredSum += current->second;
+        }
+        if (gatheredSum < sum) {
+            return MinValue;
+        }
+        TWeightedValue left(MinValue, 0.0);
+        TWeightedValue right(MaxValue, 0.0);
+        if (current != Bins.begin()) {
+            TPairSet::iterator leftBin = current;
+            --leftBin;
+            left = *leftBin;
+        }
+        {
+            TPairSet::iterator rightBin = current;
+            ++rightBin;
+            if (rightBin != Bins.end()) {
+                right = *rightBin;
+            }
+        }
+        double sumToAdd = sum - (gatheredSum - current->second - right.second / 2);
+        if (sumToAdd <= ((current->second + right.second) / 2)) {
+            return right.first - 2 * sumToAdd * (right.first - current->first) / (current->second + right.second);
+        } else {
+            sumToAdd -= (current->second + right.second) / 2;
+            return current->first - 2 * sumToAdd * (current->first - left.first) / (left.second + current->second);
+        }
+    }
+
+    double TAdaptiveHistogram::CalcUpperBoundSafe(double sum) {
+        if (!Empty()) {
+            sum = Max(Bins.begin()->second, sum);
+        }
+        return CalcUpperBound(sum);
+    }
+
+    double TAdaptiveHistogram::CalcLowerBoundSafe(double sum) {
+        if (!Empty()) {
+            sum = Max(Bins.rbegin()->second, sum);
+        }
+        return CalcLowerBound(sum);
+    }
+
+    void TAdaptiveHistogram::FromIHistogram(IHistogram* histo) {
+        if (!histo) {
+            ythrow yexception() << "Attempt to create TAdaptiveHistogram from a NULL pointer";
+        }
+        if (CalcQuality == CalcWardQuality) {
+            ythrow yexception() << "Not implemented";
+        } else if (CalcQuality != CalcDistanceQuality && CalcQuality != CalcWeightQuality) {
+            ythrow yexception() << "Attempt to create TAdaptiveHistogram from a pointer without default CalcQuality";
+        }
+        Id = histo->GetId();
+        if (histo->Empty()) {
+            return;
+        }
+        double sum = histo->GetSum();
+        double minValue = histo->GetMinValue();
+        double maxValue = histo->GetMaxValue();
+        if (minValue == maxValue) {
+            Add(minValue, sum);
+            return;
+        }
+        if (CalcQuality == CalcDistanceQuality) {
+            double binRange = (maxValue - minValue) / (Intervals);
+            for (size_t i = 0; i < Intervals; ++i) {
+                Add(minValue + binRange * (i + 0.5), histo->GetSumInRange(minValue + binRange * i, minValue + binRange * (i + 1)));
+            }
+        } else if (CalcQuality == CalcWeightQuality && sum != 0.0) {
+            double slab = sum / Intervals;
+            double prevBound = minValue;
+            for (size_t i = 0; i < Intervals; ++i) {
+                double bound = histo->CalcUpperBound(slab * (i + 1));
+                Add((bound + prevBound) / 2, slab);
+                prevBound = bound;
+            }
+        }
+        MinValue = minValue;
+        MaxValue = maxValue;
+    }
+
+    void TAdaptiveHistogram::Add(const TWeightedValue& weightedValue, bool initial) {
+        const double& value = weightedValue.first;
+        const double& weight = weightedValue.second;
+        if (weight <= 0.0) {
+            return; // all zero-weighted values should be skipped because they don't affect the distribution, negative weights are forbidden
+        }
+        if (initial) {
+            Sum += weight;
+        }
+        if (Bins.size() == 0) {
+            MinValue = value;
+            MaxValue = value;
+            Bins.insert(weightedValue);
+            return;
+        }
+        if (value < MinValue) {
+            MinValue = value;
+        }
+        if (value > MaxValue) {
+            MaxValue = value;
+        }
+        TPairSet::iterator rightBin = Bins.lower_bound(TWeightedValue(value, -1.0));
+        if (rightBin != Bins.end() && rightBin->first == value) {
+            TPairSet::iterator currentBin = rightBin;
+            ++rightBin;
+            TWeightedValue newBin(value, weight + currentBin->second);
+            if (rightBin != Bins.end()) {
+                Y_VERIFY(BinsByQuality.erase(CalcQuality(*currentBin, *rightBin)) == 1, "Erase failed");
+                BinsByQuality.insert(CalcQuality(newBin, *rightBin));
+            }
+            if (currentBin != Bins.begin()) {
+                TPairSet::iterator leftBin = currentBin;
+                --leftBin;
+                Y_VERIFY(BinsByQuality.erase(CalcQuality(*leftBin, *currentBin)) == 1, "Erase failed");
+                BinsByQuality.insert(CalcQuality(*leftBin, newBin));
+            }
+            Bins.erase(currentBin);
+            Bins.insert(newBin);
+            return;
+        }
+        if (rightBin == Bins.begin()) {
+            BinsByQuality.insert(CalcQuality(weightedValue, *rightBin));
+        } else {
+            TPairSet::iterator leftBin = rightBin;
+            --leftBin;
+            if (rightBin == Bins.end()) {
+                BinsByQuality.insert(CalcQuality(*leftBin, weightedValue));
+            } else {
+                Y_VERIFY(BinsByQuality.erase(CalcQuality(*leftBin, *rightBin)) == 1, "Erase failed");
+                BinsByQuality.insert(CalcQuality(*leftBin, weightedValue));
+                BinsByQuality.insert(CalcQuality(weightedValue, *rightBin));
+            }
+        }
+        Bins.insert(weightedValue);
+        if (Bins.size() > Intervals) {
+            Shrink();
+        }
+    }
+
+    void TAdaptiveHistogram::Erase(double value) {
+        TPairSet::iterator currentBin = Bins.lower_bound(TWeightedValue(value, -1.0));
+        Y_VERIFY(currentBin != Bins.end() && currentBin->first == value, "Can't find bin that should be erased");
+        TPairSet::iterator rightBin = currentBin;
+        ++rightBin;
+        if (currentBin == Bins.begin()) {
+            Y_VERIFY(rightBin != Bins.end(), "No right bin for the first bin");
+            Y_VERIFY(BinsByQuality.erase(CalcQuality(*currentBin, *rightBin)) != 0, "Erase failed");
+        } else {
+            TPairSet::iterator leftBin = currentBin;
+            --leftBin;
+            if (rightBin == Bins.end()) {
+                Y_VERIFY(BinsByQuality.erase(CalcQuality(*leftBin, *currentBin)) != 0, "Erase failed");
+            } else {
+                Y_VERIFY(BinsByQuality.erase(CalcQuality(*leftBin, *currentBin)) != 0, "Erase failed");
+                Y_VERIFY(BinsByQuality.erase(CalcQuality(*currentBin, *rightBin)) != 0, "Erase failed");
+                BinsByQuality.insert(CalcQuality(*leftBin, *rightBin));
+            }
+        }
+        Bins.erase(currentBin);
+    }
+
+    void TAdaptiveHistogram::Shrink() {
+        TPairSet::iterator worstBin = BinsByQuality.begin();
+        Y_VERIFY(worstBin != BinsByQuality.end(), "No right bin for the first bin");
+        TPairSet::iterator leftBin = Bins.lower_bound(TWeightedValue(worstBin->second, -1.0));
+        Y_VERIFY(leftBin != Bins.end() && leftBin->first == worstBin->second, "Can't find worst bin");
+        TPairSet::iterator rightBin = leftBin;
+        ++rightBin;
+        Y_VERIFY(rightBin != Bins.end(), "Can't find right bin");
+
+        TWeightedValue newBin((leftBin->first * leftBin->second + rightBin->first * rightBin->second) / (leftBin->second + rightBin->second), leftBin->second + rightBin->second);
+        if (Bins.size() > 2) {
+            Erase(leftBin->first);
+            Erase(rightBin->first);
+        } else {
+            Bins.clear();
+            BinsByQuality.clear();
+        }
+        Add(newBin, false);
+    }
+
+    void TAdaptiveHistogram::PrecomputePartialSums() {
+        PrecomputedBins.clear();
+        PrecomputedBins.reserve(Bins.size());
+        double currentSum = 0;
+        for (const auto& bin : Bins) {
+            PrecomputedBins.emplace_back(bin.first, bin.second, currentSum, Sum - currentSum - bin.second);
+            currentSum += bin.second;
+        }
+    }
+
+    template <typename TBins, typename TGetSumAbove>
+    double TAdaptiveHistogram::GetSumAboveBoundImpl(double bound, const TBins& bins, typename TBins::const_iterator rightBin, const TGetSumAbove& getSumAbove) const {
+        typename TBins::value_type left(MinValue, 0.0);
+        typename TBins::value_type right(MaxValue, 0.0);
+        if (rightBin != bins.end()) {
+            right = *rightBin;
+        }
+        if (rightBin != bins.begin()) {
+            typename TBins::const_iterator leftBin = rightBin;
+            --leftBin;
+            left = *leftBin;
+        }
+        double sum = (right.second / 2) + ((right.first == left.first) ? ((left.second + right.second) / 2) : (((left.second + right.second) / 2) * (right.first - bound) / (right.first - left.first)));
+        if (rightBin == bins.end()) {
+            return sum;
+        }
+        sum += getSumAbove(rightBin);
+        return sum;
+    }
+
+    template <typename TBins, typename TGetSumBelow>
+    double TAdaptiveHistogram::GetSumBelowBoundImpl(double bound, const TBins& bins, typename TBins::const_iterator rightBin, const TGetSumBelow& getSumBelow) const {
+        typename TBins::value_type left(MinValue, 0.0);
+        typename TBins::value_type right(MaxValue, 0.0);
+        if (rightBin != bins.end()) {
+            right = *rightBin;
+        }
+        if (rightBin != bins.begin()) {
+            typename TBins::const_iterator leftBin = rightBin;
+            --leftBin;
+            left = *leftBin;
+        }
+        double sum = (left.second / 2) + ((right.first == left.first) ? ((left.second + right.second) / 2) : (((left.second + right.second) / 2) * (bound - left.first) / (right.first - left.first)));
+        if (rightBin == bins.begin()) {
+            return sum;
+        }
+        --rightBin;
+        sum += getSumBelow(rightBin);
+        return sum;
+    }
+
+}