ydb/library/cpp/histogram/adaptive/adaptive_histogram.h

#pragma once

#include "histogram.h"
#include "common.h"

#include <library/cpp/histogram/adaptive/protos/histo.pb.h>

#include <util/generic/ptr.h>
#include <util/generic/set.h>
#include <util/generic/vector.h>

namespace NKiwiAggr {
    class TAdaptiveHistogram: private TNonCopyable, public IHistogram {
    protected:
        static const size_t DEFAULT_INTERVALS = 100;

    private:
        using TPairSet = TSet<TWeightedValue>;

        struct TFastBin {
            // these names are for compatibility with TWeightedValue
            double first;
            double second;
            // both sums do not include current bin
            double SumBelow;
            double SumAbove;

            TFastBin(double first_, double second_, double sumBelow = 0, double sumAbove = 0)
                : first(first_)
                , second(second_)
                , SumBelow(sumBelow)
                , SumAbove(sumAbove)
            {
            }

            bool operator<(const TFastBin& rhs) const {
                return first < rhs.first;
            }
        };

        ui64 Id;
        double MinValue;
        double MaxValue;
        double Sum;
        size_t Intervals;
        TPairSet Bins;
        TPairSet BinsByQuality;
        TQualityFunction CalcQuality;

        TVector<TFastBin> PrecomputedBins;

    public:
        TAdaptiveHistogram(size_t intervals, ui64 id = 0, TQualityFunction qualityFunc = CalcWeightQuality);
        TAdaptiveHistogram(const THistogram& histo, size_t defaultIntervals = DEFAULT_INTERVALS, ui64 defaultId = 0, TQualityFunction qualityFunc = nullptr);
        TAdaptiveHistogram(IHistogram* histo, size_t defaultIntervals = DEFAULT_INTERVALS, ui64 defaultId = 0, TQualityFunction qualityFunc = CalcWeightQuality);

        ~TAdaptiveHistogram() override {
        }

        TQualityFunction GetQualityFunc();

        void Clear() override;

        void Add(double value, double weight) override;
        void Add(const THistoRec& histoRec) override;

        void Merge(const THistogram& histo, double multiplier) final;
        void Merge(const TVector<THistogram>& histogramsToMerge) final;
        void Merge(TVector<IHistogramPtr> histogramsToMerge) final;

        void Multiply(double factor) final;

        void FromProto(const THistogram& histo) final;
        void ToProto(THistogram& histo) final;

        void SetId(ui64 id) final;
        ui64 GetId() final;
        bool Empty() final;
        double GetMinValue() final;
        double GetMaxValue() final;
        double GetSum() final;
        double GetSumInRange(double leftBound, double rightBound) final;
        double GetSumAboveBound(double bound) final;
        double GetSumBelowBound(double bound) final;
        double CalcUpperBound(double sum) final;
        double CalcLowerBound(double sum) final;
        double CalcUpperBoundSafe(double sum) final;
        double CalcLowerBoundSafe(double sum) final;

        void PrecomputePartialSums() final;

    private:
        void FromIHistogram(IHistogram* histo);
        void Add(const TWeightedValue& weightedValue, bool initial);
        void Erase(double value);
        void Shrink();

        template <typename TBins, typename TGetSumAbove>
        double GetSumAboveBoundImpl(double bound, const TBins& bins, typename TBins::const_iterator rightBin, const TGetSumAbove& getSumAbove) const;

        template <typename TBins, typename TGetSumBelow>
        double GetSumBelowBoundImpl(double bound, const TBins& bins, typename TBins::const_iterator rightBin, const TGetSumBelow& getSumBelow) const;
    };

    template <TQualityFunction QualityFunction>
    class TDefinedAdaptiveHistogram: public TAdaptiveHistogram {
    public:
        TDefinedAdaptiveHistogram(size_t intervals, ui64 id = 0)
            : TAdaptiveHistogram(intervals, id, QualityFunction)
        {
        }

        TDefinedAdaptiveHistogram(const THistogram& histo, size_t defaultIntervals = DEFAULT_INTERVALS, ui64 defaultId = 0)
            : TAdaptiveHistogram(histo, defaultIntervals, defaultId, QualityFunction)
        {
        }

        TDefinedAdaptiveHistogram(IHistogram* histo, size_t defaultIntervals = DEFAULT_INTERVALS, ui64 defaultId = 0)
            : TAdaptiveHistogram(histo, defaultIntervals, defaultId, QualityFunction)
        {
        }

        ~TDefinedAdaptiveHistogram() override {
        }
    };

    typedef TDefinedAdaptiveHistogram<CalcDistanceQuality> TAdaptiveDistanceHistogram;
    typedef TDefinedAdaptiveHistogram<CalcWeightQuality> TAdaptiveWeightHistogram;
    typedef TDefinedAdaptiveHistogram<CalcWardQuality> TAdaptiveWardHistogram;

}