intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 408 insertions, 0 deletions

diff --git a/util/generic/set_ut.cpp b/util/generic/set_ut.cpp
new file mode 100644
index 00000000000..d2769d327f7
--- /dev/null
+++ b/util/generic/set_ut.cpp
@@ -0,0 +1,408 @@
+#include "set.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+
+#include <utility>
+
+#include <algorithm>
+
+Y_UNIT_TEST_SUITE(YSetTest) {
+    Y_UNIT_TEST(TestSet1) {
+        TSet<int, TLess<int>> s;
+        UNIT_ASSERT(!s);
+        UNIT_ASSERT(s.count(42) == 0);
+        s.insert(42);
+        UNIT_ASSERT(s);
+        UNIT_ASSERT(s.count(42) == 1);
+        s.insert(42);
+        UNIT_ASSERT(s.count(42) == 1);
+        size_t count = s.erase(42);
+        UNIT_ASSERT(count == 1);
+    }
+
+    Y_UNIT_TEST(TestSet2) {
+        using int_set = TSet<int, TLess<int>>;
+        int_set s;
+        std::pair<int_set::iterator, bool> p = s.insert(42);
+        UNIT_ASSERT(p.second == true);
+        p = s.insert(42);
+        UNIT_ASSERT(p.second == false);
+
+        int array1[] = {1, 3, 6, 7};
+        s.insert(array1, array1 + 4);
+        UNIT_ASSERT(distance(s.begin(), s.end()) == 5);
+
+        int_set s2;
+        s2.swap(s);
+        UNIT_ASSERT(distance(s2.begin(), s2.end()) == 5);
+        UNIT_ASSERT(distance(s.begin(), s.end()) == 0);
+
+        int_set s3;
+        s3.swap(s);
+        s3.swap(s2);
+        UNIT_ASSERT(distance(s.begin(), s.end()) == 0);
+        UNIT_ASSERT(distance(s2.begin(), s2.end()) == 0);
+        UNIT_ASSERT(distance(s3.begin(), s3.end()) == 5);
+    }
+
+    Y_UNIT_TEST(TestErase) {
+        TSet<int, TLess<int>> s;
+        s.insert(1);
+        s.erase(s.begin());
+        UNIT_ASSERT(s.empty());
+
+        size_t nb = s.erase(1);
+        UNIT_ASSERT(nb == 0);
+    }
+
+    Y_UNIT_TEST(TestInsert) {
+        TSet<int> s;
+        TSet<int>::iterator i = s.insert(s.end(), 0);
+        UNIT_ASSERT(*i == 0);
+    }
+
+    Y_UNIT_TEST(TestFind) {
+        TSet<int> s;
+
+        UNIT_ASSERT(s.find(0) == s.end());
+
+        TSet<int> const& crs = s;
+
+        UNIT_ASSERT(crs.find(0) == crs.end());
+    }
+
+    Y_UNIT_TEST(TestHas) {
+        TSet<int> s;
+        UNIT_ASSERT(!s.contains(0));
+
+        TSet<int> const& crs = s;
+        UNIT_ASSERT(!crs.contains(0));
+
+        s.insert(1);
+        s.insert(42);
+        s.insert(100);
+        s.insert(2);
+
+        UNIT_ASSERT(s.contains(1));
+        UNIT_ASSERT(s.contains(2));
+        UNIT_ASSERT(s.contains(42));
+        UNIT_ASSERT(s.contains(100));
+    }
+
+    Y_UNIT_TEST(TestBounds) {
+        int array1[] = {1, 3, 6, 7};
+        TSet<int> s(array1, array1 + sizeof(array1) / sizeof(array1[0]));
+        TSet<int> const& crs = s;
+
+        TSet<int>::iterator sit;
+        TSet<int>::const_iterator scit;
+        std::pair<TSet<int>::iterator, TSet<int>::iterator> pit;
+        std::pair<TSet<int>::const_iterator, TSet<int>::const_iterator> pcit;
+
+        //Check iterator on mutable set
+        sit = s.lower_bound(2);
+        UNIT_ASSERT(sit != s.end());
+        UNIT_ASSERT(*sit == 3);
+
+        sit = s.upper_bound(5);
+        UNIT_ASSERT(sit != s.end());
+        UNIT_ASSERT(*sit == 6);
+
+        pit = s.equal_range(6);
+        UNIT_ASSERT(pit.first != pit.second);
+        UNIT_ASSERT(pit.first != s.end());
+        UNIT_ASSERT(*pit.first == 6);
+        UNIT_ASSERT(pit.second != s.end());
+        UNIT_ASSERT(*pit.second == 7);
+
+        pit = s.equal_range(4);
+        UNIT_ASSERT(pit.first == pit.second);
+        UNIT_ASSERT(pit.first != s.end());
+        UNIT_ASSERT(*pit.first == 6);
+        UNIT_ASSERT(pit.second != s.end());
+        UNIT_ASSERT(*pit.second == 6);
+
+        //Check const_iterator on mutable set
+        scit = s.lower_bound(2);
+        UNIT_ASSERT(scit != s.end());
+        UNIT_ASSERT(*scit == 3);
+
+        scit = s.upper_bound(5);
+        UNIT_ASSERT(scit != s.end());
+        UNIT_ASSERT(*scit == 6);
+
+        pcit = s.equal_range(6);
+        UNIT_ASSERT(pcit.first != pcit.second);
+        UNIT_ASSERT(pcit.first != s.end());
+        UNIT_ASSERT(*pcit.first == 6);
+        UNIT_ASSERT(pcit.second != s.end());
+        UNIT_ASSERT(*pcit.second == 7);
+
+        //Check const_iterator on const set
+        scit = crs.lower_bound(2);
+        UNIT_ASSERT(scit != crs.end());
+        UNIT_ASSERT(*scit == 3);
+
+        scit = crs.upper_bound(5);
+        UNIT_ASSERT(scit != crs.end());
+        UNIT_ASSERT(*scit == 6);
+
+        pcit = crs.equal_range(6);
+        UNIT_ASSERT(pcit.first != pcit.second);
+        UNIT_ASSERT(pcit.first != crs.end());
+        UNIT_ASSERT(*pcit.first == 6);
+        UNIT_ASSERT(pcit.second != crs.end());
+        UNIT_ASSERT(*pcit.second == 7);
+    }
+
+    Y_UNIT_TEST(TestImplementationCheck) {
+        TSet<int> tree;
+        tree.insert(1);
+        TSet<int>::iterator it = tree.begin();
+        int const& int_ref = *it++;
+        UNIT_ASSERT(int_ref == 1);
+
+        UNIT_ASSERT(it == tree.end());
+        UNIT_ASSERT(it != tree.begin());
+
+        TSet<int>::const_iterator cit = tree.begin();
+        int const& int_cref = *cit++;
+        UNIT_ASSERT(int_cref == 1);
+    }
+
+    Y_UNIT_TEST(TestReverseIteratorTest) {
+        TSet<int> tree;
+        tree.insert(1);
+        tree.insert(2);
+
+        {
+            TSet<int>::reverse_iterator rit(tree.rbegin());
+            UNIT_ASSERT(*(rit++) == 2);
+            UNIT_ASSERT(*(rit++) == 1);
+            UNIT_ASSERT(rit == tree.rend());
+        }
+
+        {
+            TSet<int> const& ctree = tree;
+            TSet<int>::const_reverse_iterator rit(ctree.rbegin());
+            UNIT_ASSERT(*(rit++) == 2);
+            UNIT_ASSERT(*(rit++) == 1);
+            UNIT_ASSERT(rit == ctree.rend());
+        }
+    }
+
+    Y_UNIT_TEST(TestConstructorsAndAssignments) {
+        {
+            using container = TSet<int>;
+
+            container c1;
+            c1.insert(100);
+            c1.insert(200);
+
+            container c2(c1);
+
+            UNIT_ASSERT_VALUES_EQUAL(2, c1.size());
+            UNIT_ASSERT_VALUES_EQUAL(2, c2.size());
+            UNIT_ASSERT(c1.contains(100));
+            UNIT_ASSERT(c2.contains(200));
+
+            container c3(std::move(c1));
+
+            UNIT_ASSERT_VALUES_EQUAL(0, c1.size());
+            UNIT_ASSERT_VALUES_EQUAL(2, c3.size());
+            UNIT_ASSERT(c3.contains(100));
+
+            c2.insert(300);
+            c3 = c2;
+
+            UNIT_ASSERT_VALUES_EQUAL(3, c2.size());
+            UNIT_ASSERT_VALUES_EQUAL(3, c3.size());
+            UNIT_ASSERT(c3.contains(300));
+
+            c2.insert(400);
+            c3 = std::move(c2);
+
+            UNIT_ASSERT_VALUES_EQUAL(0, c2.size());
+            UNIT_ASSERT_VALUES_EQUAL(4, c3.size());
+            UNIT_ASSERT(c3.contains(400));
+        }
+
+        {
+            using container = TMultiSet<int>;
+
+            container c1;
+            c1.insert(100);
+            c1.insert(200);
+
+            container c2(c1);
+
+            UNIT_ASSERT_VALUES_EQUAL(2, c1.size());
+            UNIT_ASSERT_VALUES_EQUAL(2, c2.size());
+            UNIT_ASSERT(c1.find(100) != c1.end());
+            UNIT_ASSERT(c2.find(200) != c2.end());
+
+            container c3(std::move(c1));
+
+            UNIT_ASSERT_VALUES_EQUAL(0, c1.size());
+            UNIT_ASSERT_VALUES_EQUAL(2, c3.size());
+            UNIT_ASSERT(c3.find(100) != c3.end());
+
+            c2.insert(300);
+            c3 = c2;
+
+            UNIT_ASSERT_VALUES_EQUAL(3, c2.size());
+            UNIT_ASSERT_VALUES_EQUAL(3, c3.size());
+            UNIT_ASSERT(c3.find(300) != c3.end());
+
+            c2.insert(400);
+            c3 = std::move(c2);
+
+            UNIT_ASSERT_VALUES_EQUAL(0, c2.size());
+            UNIT_ASSERT_VALUES_EQUAL(4, c3.size());
+            UNIT_ASSERT(c3.find(400) != c3.end());
+        }
+    }
+
+    struct TKey {
+        TKey()
+            : m_data(0)
+        {
+        }
+
+        explicit TKey(int data)
+            : m_data(data)
+        {
+        }
+
+        int m_data;
+    };
+
+    struct TKeyCmp {
+        bool operator()(TKey lhs, TKey rhs) const {
+            return lhs.m_data < rhs.m_data;
+        }
+
+        bool operator()(TKey lhs, int rhs) const {
+            return lhs.m_data < rhs;
+        }
+
+        bool operator()(int lhs, TKey rhs) const {
+            return lhs < rhs.m_data;
+        }
+
+        using is_transparent = void;
+    };
+
+    struct TKeyCmpPtr {
+        bool operator()(TKey const volatile* lhs, TKey const volatile* rhs) const {
+            return (*lhs).m_data < (*rhs).m_data;
+        }
+
+        bool operator()(TKey const volatile* lhs, int rhs) const {
+            return (*lhs).m_data < rhs;
+        }
+
+        bool operator()(int lhs, TKey const volatile* rhs) const {
+            return lhs < (*rhs).m_data;
+        }
+
+        using is_transparent = void;
+    };
+
+    Y_UNIT_TEST(TestTemplateMethods) {
+        {
+            using KeySet = TSet<TKey, TKeyCmp>;
+            KeySet keySet;
+            keySet.insert(TKey(1));
+            keySet.insert(TKey(2));
+            keySet.insert(TKey(3));
+            keySet.insert(TKey(4));
+
+            UNIT_ASSERT(keySet.count(TKey(1)) == 1);
+            UNIT_ASSERT(keySet.count(1) == 1);
+            UNIT_ASSERT(keySet.count(5) == 0);
+
+            UNIT_ASSERT(keySet.find(2) != keySet.end());
+            UNIT_ASSERT(keySet.lower_bound(2) != keySet.end());
+            UNIT_ASSERT(keySet.upper_bound(2) != keySet.end());
+            UNIT_ASSERT(keySet.equal_range(2) != std::make_pair(keySet.begin(), keySet.end()));
+
+            KeySet const& ckeySet = keySet;
+            UNIT_ASSERT(ckeySet.find(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.lower_bound(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.upper_bound(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.equal_range(2) != std::make_pair(ckeySet.begin(), ckeySet.end()));
+        }
+
+        {
+            using KeySet = TSet<TKey*, TKeyCmpPtr>;
+            KeySet keySet;
+            TKey key1(1), key2(2), key3(3), key4(4);
+            keySet.insert(&key1);
+            keySet.insert(&key2);
+            keySet.insert(&key3);
+            keySet.insert(&key4);
+
+            UNIT_ASSERT(keySet.count(1) == 1);
+            UNIT_ASSERT(keySet.count(5) == 0);
+
+            UNIT_ASSERT(keySet.find(2) != keySet.end());
+            UNIT_ASSERT(keySet.lower_bound(2) != keySet.end());
+            UNIT_ASSERT(keySet.upper_bound(2) != keySet.end());
+            UNIT_ASSERT(keySet.equal_range(2) != std::make_pair(keySet.begin(), keySet.end()));
+
+            KeySet const& ckeySet = keySet;
+            UNIT_ASSERT(ckeySet.find(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.lower_bound(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.upper_bound(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.equal_range(2) != std::make_pair(ckeySet.begin(), ckeySet.end()));
+        }
+        {
+            using KeySet = TMultiSet<TKey, TKeyCmp>;
+            KeySet keySet;
+            keySet.insert(TKey(1));
+            keySet.insert(TKey(2));
+            keySet.insert(TKey(3));
+            keySet.insert(TKey(4));
+
+            UNIT_ASSERT(keySet.count(TKey(1)) == 1);
+            UNIT_ASSERT(keySet.count(1) == 1);
+            UNIT_ASSERT(keySet.count(5) == 0);
+
+            UNIT_ASSERT(keySet.find(2) != keySet.end());
+            UNIT_ASSERT(keySet.lower_bound(2) != keySet.end());
+            UNIT_ASSERT(keySet.upper_bound(2) != keySet.end());
+            UNIT_ASSERT(keySet.equal_range(2) != std::make_pair(keySet.begin(), keySet.end()));
+
+            KeySet const& ckeySet = keySet;
+            UNIT_ASSERT(ckeySet.find(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.lower_bound(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.upper_bound(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.equal_range(2) != std::make_pair(ckeySet.begin(), ckeySet.end()));
+        }
+
+        {
+            using KeySet = TMultiSet<TKey const volatile*, TKeyCmpPtr>;
+            KeySet keySet;
+            TKey key1(1), key2(2), key3(3), key4(4);
+            keySet.insert(&key1);
+            keySet.insert(&key2);
+            keySet.insert(&key3);
+            keySet.insert(&key4);
+
+            UNIT_ASSERT(keySet.count(1) == 1);
+            UNIT_ASSERT(keySet.count(5) == 0);
+
+            UNIT_ASSERT(keySet.find(2) != keySet.end());
+            UNIT_ASSERT(keySet.lower_bound(2) != keySet.end());
+            UNIT_ASSERT(keySet.upper_bound(2) != keySet.end());
+            UNIT_ASSERT(keySet.equal_range(2) != std::make_pair(keySet.begin(), keySet.end()));
+
+            KeySet const& ckeySet = keySet;
+            UNIT_ASSERT(ckeySet.find(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.lower_bound(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.upper_bound(2) != ckeySet.end());
+            UNIT_ASSERT(ckeySet.equal_range(2) != std::make_pair(ckeySet.begin(), ckeySet.end()));
+        }
+    }
+}