intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 64 insertions, 0 deletions

diff --git a/library/cpp/hyperloglog/hyperloglog.h b/library/cpp/hyperloglog/hyperloglog.h
new file mode 100644
index 00000000000..e79ee0ed77f
--- /dev/null
+++ b/library/cpp/hyperloglog/hyperloglog.h
@@ -0,0 +1,64 @@
+#pragma once
+
+#include <util/system/types.h>
+#include <util/stream/input.h>
+#include <util/generic/array_ref.h>
+
+#include <vector>
+
+class IOutputStream;
+
+class THyperLogLogBase {
+protected:
+    explicit THyperLogLogBase(unsigned precision);
+
+public:
+    static const constexpr unsigned PRECISION_MIN = 4;
+
+    static const constexpr unsigned PRECISION_MAX = 18;
+
+    void Update(ui64 hash);
+
+    void Merge(const THyperLogLogBase& rh);
+
+    ui64 Estimate() const;
+
+    void Save(IOutputStream& out) const;
+
+protected:
+    unsigned Precision;
+
+    TArrayRef<ui8> RegistersRef;
+};
+
+template <typename Alloc>
+class THyperLogLogWithAlloc : public THyperLogLogBase {
+private:
+    explicit THyperLogLogWithAlloc(unsigned precision)
+        : THyperLogLogBase(precision) {
+        Registers.resize(1u << precision);
+        RegistersRef = MakeArrayRef(Registers);
+    }
+
+public:
+    THyperLogLogWithAlloc(THyperLogLogWithAlloc&&) = default;
+
+    THyperLogLogWithAlloc& operator=(THyperLogLogWithAlloc&&) = default;
+
+    static THyperLogLogWithAlloc Create(unsigned precision) {
+        return THyperLogLogWithAlloc(precision);
+    }
+
+    static THyperLogLogWithAlloc Load(IInputStream& in) {
+        char precision = {};
+        Y_ENSURE(in.ReadChar(precision));
+        auto res = Create(precision);
+        in.LoadOrFail(res.Registers.data(), res.Registers.size() * sizeof(res.Registers.front()));
+        return res;
+    }
+
+private:
+    std::vector<ui8, Alloc> Registers;
+};
+
+using THyperLogLog = THyperLogLogWithAlloc<std::allocator<ui8>>;