intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 131 insertions, 0 deletions

diff --git a/library/cpp/histogram/adaptive/adaptive_histogram.h b/library/cpp/histogram/adaptive/adaptive_histogram.h
new file mode 100644
index 0000000000..fa8f48433f
--- /dev/null
+++ b/library/cpp/histogram/adaptive/adaptive_histogram.h
@@ -0,0 +1,131 @@
+#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;
+
+}