intermediate changes

ref:053341dde4c25aa65918f21eb765fc97232e55cb

5 files changed, 4 insertions, 506 deletions

diff --git a/library/cpp/containers/top_keeper/README.md b/library/cpp/containers/top_keeper/README.md
index c99138e495..759096bc36 100644
--- a/library/cpp/containers/top_keeper/README.md
+++ b/library/cpp/containers/top_keeper/README.md
@@ -19,7 +19,10 @@ TopKeeper - структура данных для поддержания "top M
 Границы применимости:
 Применять стоит всегда вместо LimitedHeap (т.к. всегда не хуже, а в худшем случае - лучше)
 Ограничение - не поддерживает сценарий использования "чередующиеся добавления / извлечения элементов" (слишком часто будут происходить Partiotion Sortы)
-Для этого, когда добавление элементов закончено, должен вызываться метод Finalize(). Для упрощения использования добавлен автоматический Finalize() на GetNext() / Pop(). Тем не менее явный вызов Finalize() по-прежнему возможен - так можно контролировать момент выполнения трудоёмкой операции NthElement().  После того, как все элементы извлечены TopKeeper можно переиспользовать (для этого же служит метод Reset()).
+Для этого, когда добавление элементов закончено, должен вызываться метод Finalize().
+Для упрощения использования добавлен автоматический Finalize() на GetNext() / Pop().
+Тем не менее явный вызов Finalize() по-прежнему возможен - так можно контролировать момент выполнения трудоёмкой операции NthElement().
+После того, как все элементы извлечены TopKeeper можно переиспользовать (для этого же служит метод Reset()).
 В ситуации когда нужны чередующиеся добавления / извлечения - используйте LimitedHeap
 
 Примеры использования:
diff --git a/library/cpp/containers/top_keeper/top_keeper/README.md b/library/cpp/containers/top_keeper/top_keeper/README.md
deleted file mode 100644
index f160fb1c01..0000000000
--- a/library/cpp/containers/top_keeper/top_keeper/README.md
+++ /dev/null
@@ -1,26 +0,0 @@
-TopKeeper - структура данных для поддержания "top M from stream"
-Используется для выборки наибольших / наименьших элементов за один проход (полезно при фильтрации)
-
-Пусть входной поток состоит из N элементов, из которых нужно отфильтровать M с наибольшим значением.
-Алгоритм (для случая top max M):
-1) Выделим вектор размера 2 * M
-2а) Если вектор заполнен меньше, чем наполовину - добавляем очередной элемент, обновляем минимум
-2б) Иначе - сравниваем с текущим минимумом, в случае, если новый больше, добавляем его в вектор, минимум не обновляем, иначе - отбрасываем
-3) Если заполнен - делаем Partition Sort с M-ым элементом в качестве сепаратора
-4) Таким образом в левой половине все значения больше оных в правой, в позиции M стоит ровно M-ый элемент сортированной последовательности
-5) Удаляем элементы из правой половины
-
-Трудоёмкость:
-На M добавлений происходит 1 PartitionSort (усреднённая оценка трудоёмкости - О(M)) и удаление M элементов. Таким образом достигается О(1) операций в среднем на 1 добавление. Для алгоритма TLimitedHeap (library/cpp/containers/limited_heap) - эта оценка О(log (M))
-
-Тесты:
-На случайных потоках данных количество сравнений у TopKeeper и LimitedHeap одинаково (происходит потому что минимум у первого обновляется раз в M добавлений, а у второго - при каждом добавлении). Худший случай LimitedHeap - сортированная последовательность (добавляем каждый элемент), на таком потоке для 2 000 000 000 int TopKeeper выигрывает во много раз.
-
-Границы применимости:
-Применять стоит всегда вместо LimitedHeap (т.к. всегда не хуже, а в худшем случае - лучше)
-Ограничение - не поддерживает сценарий использования "чередующиеся добавления / извлечения элементов" (слишком часто будут происходить Partiotion Sortы)
-Для этого, когда добавление элементов закончено, должен вызываться метод Finalize(). Для упрощения использования добавлен автоматический Finalize() на GetNext() / Pop(). Тем не менее явный вызов Finalize() по-прежнему возможен - так можно контроллировать момент выполнения трудоёмкой операции NthElement().  После того, как все элементы извлечены TopKeeper можно переиспользовать (для этого же служит метод Reset()).
-В ситуации когда нужны чередующиеся добавления / извлечения - используйте LimitedHeap
-
-Примеры использования:
-library/cpp/containers/top_keeper/ut
diff --git a/library/cpp/containers/top_keeper/top_keeper/top_keeper.cpp b/library/cpp/containers/top_keeper/top_keeper/top_keeper.cpp
deleted file mode 100644
index 29544bf227..0000000000
--- a/library/cpp/containers/top_keeper/top_keeper/top_keeper.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "top_keeper.h"
diff --git a/library/cpp/containers/top_keeper/top_keeper/top_keeper.h b/library/cpp/containers/top_keeper/top_keeper/top_keeper.h
deleted file mode 100644
index 2f282b5a9e..0000000000
--- a/library/cpp/containers/top_keeper/top_keeper/top_keeper.h
+++ /dev/null
@@ -1,256 +0,0 @@
-#pragma once
-
-#include <util/generic/vector.h>
-#include <util/generic/algorithm.h>
-#include <util/generic/maybe.h>
-#include <util/str_stl.h>
-
-template <class T, class TComparator = TGreater<T>, bool sort = true, class Alloc = std::allocator<T>>
-class TTopKeeper {
-private:
-    class TVectorWithMin {
-    private:
-        TVector<T, Alloc> Internal;
-        size_t HalfMaxSize;
-        TComparator Comparer;
-        size_t MinElementIndex;
-
-    private:
-        void Reserve() {
-            Internal.reserve(2 * HalfMaxSize);
-        }
-
-        template <class UT>
-        bool Insert(UT&& value) noexcept {
-            if (Y_UNLIKELY(0 == HalfMaxSize)) {
-                return false;
-            }
-
-            if (Internal.size() < HalfMaxSize) {
-                if (Internal.empty() || Comparer(Internal[MinElementIndex], value)) {
-                    MinElementIndex = Internal.size();
-                    Internal.push_back(std::forward<UT>(value));
-                    return true;
-                }
-            } else if (!Comparer(value, Internal[MinElementIndex])) {
-                return false;
-            }
-
-            Internal.push_back(std::forward<UT>(value));
-
-            if (Internal.size() == (HalfMaxSize << 1)) {
-                Partition();
-            }
-
-            return true;
-        }
-
-    public:
-        using value_type = T;
-
-        TVectorWithMin(const size_t halfMaxSize, const TComparator& comp)
-            : HalfMaxSize(halfMaxSize)
-            , Comparer(comp)
-        {
-            Reserve();
-        }
-
-        template <class TAllocParam>
-        TVectorWithMin(const size_t halfMaxSize, const TComparator& comp, TAllocParam&& param)
-            : Internal(std::forward<TAllocParam>(param))
-            , HalfMaxSize(halfMaxSize)
-            , Comparer(comp)
-        {
-            Reserve();
-        }
-
-        void SortAccending() {
-            Sort(Internal.begin(), Internal.end(), Comparer);
-        }
-
-        void Partition() {
-            if (Y_UNLIKELY(HalfMaxSize == 0)) {
-                return;
-            }
-            if (Y_LIKELY(Internal.size() >= HalfMaxSize)) {
-                NthElement(Internal.begin(), Internal.begin() + HalfMaxSize - 1, Internal.end(), Comparer);
-                Internal.erase(Internal.begin() + HalfMaxSize, Internal.end());
-
-                //we should update MinElementIndex cause we just altered Internal
-                MinElementIndex = HalfMaxSize - 1;
-            }
-        }
-
-        bool Push(const T& value) {
-            return Insert(value);
-        }
-
-        bool Push(T&& value) {
-            return Insert(std::move(value));
-        }
-
-        template <class... TArgs>
-        bool Emplace(TArgs&&... args) {
-            return Insert(T(std::forward<TArgs>(args)...)); // TODO: make it "real" emplace, not that fake one
-        }
-
-        void SetMaxSize(size_t newHalfMaxSize) {
-            HalfMaxSize = newHalfMaxSize;
-            Reserve();
-            Partition();
-        }
-
-        size_t GetSize() const {
-            return Internal.size();
-        }
-
-        const auto& GetInternal() const {
-            return Internal;
-        }
-
-        auto Extract() {
-            using std::swap;
-
-            decltype(Internal) values;
-            swap(Internal, values);
-            Reset();
-            return values;
-        }
-
-        const T& Back() const {
-            return Internal.back();
-        }
-
-        void Pop() {
-            Internal.pop_back();
-        }
-
-        void Reset() {
-            Internal.clear();
-            //MinElementIndex will reset itself when we start adding new values
-        }
-    };
-
-    void CheckNotFinalized() {
-        Y_ENSURE(!Finalized, "Cannot insert after finalizing (Pop() / GetNext() / Finalize())! "
-                             "Use TLimitedHeap for this scenario");
-    }
-
-    size_t MaxSize;
-    const TComparator Comparer;
-    TVectorWithMin Internal;
-    bool Finalized;
-
-public:
-    TTopKeeper()
-        : MaxSize(0)
-        , Comparer()
-        , Internal(0, Comparer)
-        , Finalized(false)
-    {
-    }
-
-    TTopKeeper(size_t maxSize, const TComparator& comp = TComparator())
-        : MaxSize(maxSize)
-        , Comparer(comp)
-        , Internal(maxSize, comp)
-        , Finalized(false)
-    {
-    }
-
-    template <class TAllocParam>
-    TTopKeeper(size_t maxSize, const TComparator& comp, TAllocParam&& param)
-        : MaxSize(maxSize)
-        , Comparer(comp)
-        , Internal(maxSize, comp, std::forward<TAllocParam>(param))
-        , Finalized(false)
-    {
-    }
-
-    void Finalize() {
-        if (Y_LIKELY(Finalized)) {
-            return;
-        }
-        Internal.Partition();
-        if (sort) {
-            Internal.SortAccending();
-        }
-        Finalized = true;
-    }
-
-    const T& GetNext() {
-        Y_ENSURE(!IsEmpty(), "Trying GetNext from empty heap!");
-        Finalize();
-        return Internal.Back();
-    }
-
-    void Pop() {
-        Y_ENSURE(!IsEmpty(), "Trying Pop from empty heap!");
-        Finalize();
-        Internal.Pop();
-        if (IsEmpty()) {
-            Reset();
-        }
-    }
-
-    T ExtractOne() {
-        Y_ENSURE(!IsEmpty(), "Trying ExtractOne from empty heap!");
-        Finalize();
-        auto value = std::move(Internal.Back());
-        Internal.Pop();
-        if (IsEmpty()) {
-            Reset();
-        }
-        return value;
-    }
-
-    auto Extract() {
-        Finalize();
-        return Internal.Extract();
-    }
-
-    bool Insert(const T& value) {
-        CheckNotFinalized();
-        return Internal.Push(value);
-    }
-
-    bool Insert(T&& value) {
-        CheckNotFinalized();
-        return Internal.Push(std::move(value));
-    }
-
-    template <class... TArgs>
-    bool Emplace(TArgs&&... args) {
-        CheckNotFinalized();
-        return Internal.Emplace(std::forward<TArgs>(args)...);
-    }
-
-    const auto& GetInternal() {
-        Finalize();
-        return Internal.GetInternal();
-    }
-
-    bool IsEmpty() const {
-        return Internal.GetSize() == 0;
-    }
-
-    size_t GetSize() const {
-        return Min(Internal.GetSize(), MaxSize);
-    }
-
-    size_t GetMaxSize() const {
-        return MaxSize;
-    }
-
-    void SetMaxSize(size_t newMaxSize) {
-        Y_ENSURE(!Finalized, "Cannot resize after finalizing (Pop() / GetNext() / Finalize())! "
-                             "Use TLimitedHeap for this scenario");
-        MaxSize = newMaxSize;
-        Internal.SetMaxSize(newMaxSize);
-    }
-
-    void Reset() {
-        Internal.Reset();
-        Finalized = false;
-    }
-};
diff --git a/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp b/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp
deleted file mode 100644
index a938279025..0000000000
--- a/library/cpp/containers/top_keeper/top_keeper/ut/top_keeper_ut.cpp
+++ /dev/null
@@ -1,222 +0,0 @@
-#include <library/cpp/containers/limited_heap/limited_heap.h>
-#include <library/cpp/containers/top_keeper/top_keeper.h>
-#include <library/cpp/testing/unittest/registar.h>
-#include <util/random/random.h>
-
-static ui32 seed = 3;
-ui32 Rnd() {
-    seed = seed * 5 + 1;
-    return seed;
-}
-
-/*
- * Tests for TTopKeeper
- */
-Y_UNIT_TEST_SUITE(TTopKeeperTest) {
-    // Tests correctness on usual examples
-    Y_UNIT_TEST(CorrectnessTest) {
-        int m = 20000;
-
-        TLimitedHeap<std::pair<int, int>> h1(m);
-        TTopKeeper<std::pair<int, int>> h2(m);
-
-        int n = 20000000;
-        while (n--) {
-            int r = int(Rnd());
-
-            h1.Insert({r, -r});
-            h2.Emplace(r, -r);
-        }
-
-        h2.Finalize();
-
-        UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize());
-
-        while (!h1.IsEmpty()) {
-            UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext());
-            h1.PopMin();
-            h2.Pop();
-        }
-    }
-
-    // Tests on zero-size correctness
-    Y_UNIT_TEST(ZeroSizeCorrectnes) {
-        TTopKeeper<int> h(0);
-        for (int i = 0; i < 100; ++i) {
-            h.Insert(i % 10 + i / 10);
-        }
-        h.Finalize();
-        UNIT_ASSERT(h.IsEmpty());
-    }
-
-    // Tests SetMaxSize behaviour
-    Y_UNIT_TEST(SetMaxSizeTest) {
-        int m = 20000;
-        TLimitedHeap<int> h1(m);
-        TTopKeeper<int> h2(m);
-
-        int n = 20000000;
-        while (n--) {
-            int r = int(Rnd());
-
-            h1.Insert(r);
-            h2.Insert(r);
-        }
-
-        h1.SetMaxSize(m / 3);
-        h2.SetMaxSize(m / 3);
-        h2.Finalize();
-
-        UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize());
-
-        while (!h1.IsEmpty()) {
-            UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext());
-            h1.PopMin();
-            h2.Pop();
-        }
-    }
-
-    // Tests reuse behavior
-    Y_UNIT_TEST(ReuseTest) {
-        int m = 20000;
-        TLimitedHeap<int> h1(m);
-        TTopKeeper<int> h2(m);
-
-        int n = 20000000;
-        while (n--) {
-            int r = int(Rnd());
-
-            h1.Insert(r);
-            h2.Insert(r);
-        }
-
-        UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize());
-
-        while (!h1.IsEmpty()) {
-            UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext());
-            h1.PopMin();
-            h2.Pop();
-        }
-
-        n = 20000000;
-        while (n--) {
-            int r = int(Rnd());
-
-            h1.Insert(r);
-            h2.Insert(r);
-        }
-
-        UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize());
-
-        while (!h1.IsEmpty()) {
-            UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext());
-            h1.PopMin();
-            h2.Pop();
-        }
-    }
-
-    // Tests reset behavior
-    Y_UNIT_TEST(ResetTest) {
-        int m = 20000;
-        TLimitedHeap<int> h1(m);
-        TTopKeeper<int> h2(m);
-
-        int n = 20000000;
-        while (n--) {
-            int r = int(Rnd());
-
-            h1.Insert(r);
-            h2.Insert(r);
-        }
-
-        UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize());
-
-        for (int i = 0; i < m / 2; ++i) {
-            UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext());
-            h1.PopMin();
-            h2.Pop();
-        }
-
-        h2.Reset();
-        while (!h1.IsEmpty()) {
-            h1.PopMin();
-        }
-
-        n = 20000000;
-        while (n--) {
-            int r = int(Rnd());
-
-            h1.Insert(r);
-            h2.Insert(r);
-        }
-
-        UNIT_ASSERT_EQUAL(h1.GetSize(), h2.GetSize());
-
-        while (!h1.IsEmpty()) {
-            UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext());
-            h1.PopMin();
-            h2.Pop();
-        }
-    }
-
-    Y_UNIT_TEST(PreRegressionTest) {
-        typedef std::pair<float, unsigned int> TElementType;
-
-        const size_t randomTriesCount = 128;
-        for (size_t i1 = 0; i1 < randomTriesCount; ++i1) {
-            const size_t desiredElementsCount = RandomNumber<size_t>(5) + 1;
-            TLimitedHeap<TElementType> h1(desiredElementsCount);
-            TTopKeeper<TElementType> h2(desiredElementsCount);
-
-            const size_t elementsToInsert = RandomNumber<size_t>(10) + desiredElementsCount;
-            UNIT_ASSERT_C(desiredElementsCount <= elementsToInsert, "Test internal invariant is broken");
-            for (size_t i2 = 0; i2 < elementsToInsert; ++i2) {
-                const auto f = RandomNumber<float>();
-                const auto id = RandomNumber<unsigned int>();
-
-                h1.Insert(TElementType(f, id));
-                h2.Insert(TElementType(f, id));
-            }
-
-            h2.Finalize();
-
-            //we inserted enough elements to guarantee this outcome
-            UNIT_ASSERT_EQUAL(h1.GetSize(), desiredElementsCount);
-            UNIT_ASSERT_EQUAL(h2.GetSize(), desiredElementsCount);
-
-            const auto n = h2.GetSize();
-            for (size_t i3 = 0; i3 < n; ++i3) {
-                UNIT_ASSERT_EQUAL(h1.GetMin(), h2.GetNext());
-                h1.PopMin();
-                h2.Pop();
-            }
-        }
-    }
-
-    Y_UNIT_TEST(CopyKeeperRegressionCase) {
-        using TKeeper = TTopKeeper<float>;
-        TVector<TKeeper> v(2, TKeeper(200));
-        auto& k = v[1];
-        for (size_t i = 0; i < 100; ++i) {
-            k.Insert(RandomNumber<float>());
-        }
-        k.Finalize();
-    }
-
-    Y_UNIT_TEST(ExtractTest) {
-        TTopKeeper<size_t> keeper(100);
-        for (size_t i = 0; i < 100; ++i) {
-            keeper.Insert(i);
-        }
-
-        auto values = keeper.Extract();
-        UNIT_ASSERT_EQUAL(values.size(), 100);
-        Sort(values);
-
-        for (size_t i = 0; i < 100; ++i) {
-            UNIT_ASSERT_EQUAL(values[i], i);
-        }
-
-        UNIT_ASSERT(keeper.IsEmpty());
-    }
-}