intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 496 insertions, 0 deletions

diff --git a/util/generic/map_ut.cpp b/util/generic/map_ut.cpp
new file mode 100644
index 0000000000..79e832b024
--- /dev/null
+++ b/util/generic/map_ut.cpp
@@ -0,0 +1,496 @@
+#include "map.h"
+
+#include <library/cpp/testing/unittest/registar.h>
+#include <util/memory/pool.h>
+#include <algorithm>
+
+Y_UNIT_TEST_SUITE(TYMapTest) {
+    template <typename TAlloc>
+    void DoTestMap1(TMap<char, int, TLess<char>, TAlloc>& m);
+
+    template <typename TAlloc>
+    void DoTestMMap1(TMultiMap<char, int, TLess<char>, TAlloc>& mm);
+
+    Y_UNIT_TEST(TestMap1) {
+        {
+            TMap<char, int, TLess<char>> m;
+            DoTestMap1(m);
+        }
+        {
+            TMemoryPool p(100);
+            TMap<char, int, TLess<char>, TPoolAllocator> m(&p);
+            DoTestMap1(m);
+        }
+    }
+
+    Y_UNIT_TEST(TestMMap1) {
+        {
+            TMultiMap<char, int, TLess<char>> mm;
+            DoTestMMap1(mm);
+        }
+        {
+            TMemoryPool p(100);
+            TMultiMap<char, int, TLess<char>, TPoolAllocator> mm(&p);
+            DoTestMMap1(mm);
+        }
+    }
+
+    template <typename TAlloc>
+    void DoTestMap1(TMap<char, int, TLess<char>, TAlloc>& m) {
+        using maptype = TMap<char, int, TLess<char>, TAlloc>;
+        // Store mappings between roman numerals and decimals.
+        m['l'] = 50;
+        m['x'] = 20; // Deliberate mistake.
+        m['v'] = 5;
+        m['i'] = 1;
+
+        UNIT_ASSERT(m['x'] == 20);
+        m['x'] = 10; // Correct mistake.
+        UNIT_ASSERT(m['x'] == 10);
+        UNIT_ASSERT(m['z'] == 0);
+
+        UNIT_ASSERT(m.count('z') == 1);
+
+        std::pair<typename maptype::iterator, bool> p = m.insert(std::pair<const char, int>('c', 100));
+
+        UNIT_ASSERT(p.second);
+        UNIT_ASSERT(p.first != m.end());
+        UNIT_ASSERT((*p.first).first == 'c');
+        UNIT_ASSERT((*p.first).second == 100);
+
+        p = m.insert(std::pair<const char, int>('c', 100));
+
+        UNIT_ASSERT(!p.second); // already existing pair
+        UNIT_ASSERT(p.first != m.end());
+        UNIT_ASSERT((*p.first).first == 'c');
+        UNIT_ASSERT((*p.first).second == 100);
+    }
+
+    template <typename TAlloc>
+    void DoTestMMap1(TMultiMap<char, int, TLess<char>, TAlloc>& m) {
+        using mmap = TMultiMap<char, int, TLess<char>, TAlloc>;
+
+        UNIT_ASSERT(m.count('X') == 0);
+
+        m.insert(std::pair<const char, int>('X', 10)); // Standard way.
+        UNIT_ASSERT(m.count('X') == 1);
+
+        m.insert(std::pair<const char, int>('X', 20)); // jbuck: standard way
+        UNIT_ASSERT(m.count('X') == 2);
+
+        m.insert(std::pair<const char, int>('Y', 32)); // jbuck: standard way
+        typename mmap::iterator i = m.find('X');       // Find first match.
+        ++i;
+        UNIT_ASSERT((*i).first == 'X');
+        UNIT_ASSERT((*i).second == 20);
+        ++i;
+        UNIT_ASSERT((*i).first == 'Y');
+        UNIT_ASSERT((*i).second == 32);
+        ++i;
+        UNIT_ASSERT(i == m.end());
+
+        size_t count = m.erase('X');
+        UNIT_ASSERT(count == 2);
+    }
+
+    Y_UNIT_TEST(TestMMap2) {
+        using pair_type = std::pair<const int, char>;
+
+        pair_type p1(3, 'c');
+        pair_type p2(6, 'f');
+        pair_type p3(1, 'a');
+        pair_type p4(2, 'b');
+        pair_type p5(3, 'x');
+        pair_type p6(6, 'f');
+
+        using mmap = TMultiMap<int, char, TLess<int>>;
+
+        pair_type array[] = {
+            p1,
+            p2,
+            p3,
+            p4,
+            p5,
+            p6};
+
+        mmap m(array + 0, array + 6);
+        mmap::iterator i;
+        i = m.lower_bound(3);
+        UNIT_ASSERT((*i).first == 3);
+        UNIT_ASSERT((*i).second == 'c');
+
+        i = m.upper_bound(3);
+        UNIT_ASSERT((*i).first == 6);
+        UNIT_ASSERT((*i).second == 'f');
+    }
+
+    Y_UNIT_TEST(TestIterators) {
+        using int_map = TMap<int, char, TLess<int>>;
+        int_map imap;
+
+        {
+            int_map::iterator ite(imap.begin());
+            int_map::const_iterator cite(imap.begin());
+
+            UNIT_ASSERT(ite == cite);
+            UNIT_ASSERT(!(ite != cite));
+            UNIT_ASSERT(cite == ite);
+            UNIT_ASSERT(!(cite != ite));
+        }
+
+        using mmap = TMultiMap<int, char, TLess<int>>;
+        using pair_type = mmap::value_type;
+
+        pair_type p1(3, 'c');
+        pair_type p2(6, 'f');
+        pair_type p3(1, 'a');
+        pair_type p4(2, 'b');
+        pair_type p5(3, 'x');
+        pair_type p6(6, 'f');
+
+        pair_type array[] = {
+            p1,
+            p2,
+            p3,
+            p4,
+            p5,
+            p6};
+
+        mmap m(array + 0, array + 6);
+
+        {
+            mmap::iterator ite(m.begin());
+            mmap::const_iterator cite(m.begin());
+            //test compare between const_iterator and iterator
+            UNIT_ASSERT(ite == cite);
+            UNIT_ASSERT(!(ite != cite));
+            UNIT_ASSERT(cite == ite);
+            UNIT_ASSERT(!(cite != ite));
+        }
+
+        mmap::reverse_iterator ri = m.rbegin();
+
+        UNIT_ASSERT(ri != m.rend());
+        UNIT_ASSERT(ri == m.rbegin());
+        UNIT_ASSERT((*ri).first == 6);
+        UNIT_ASSERT((*ri++).second == 'f');
+        UNIT_ASSERT((*ri).first == 6);
+        UNIT_ASSERT((*ri).second == 'f');
+
+        mmap const& cm = m;
+        mmap::const_reverse_iterator rci = cm.rbegin();
+
+        UNIT_ASSERT(rci != cm.rend());
+        UNIT_ASSERT((*rci).first == 6);
+        UNIT_ASSERT((*rci++).second == 'f');
+        UNIT_ASSERT((*rci).first == 6);
+        UNIT_ASSERT((*rci).second == 'f');
+    }
+
+    Y_UNIT_TEST(TestEqualRange) {
+        using maptype = TMap<char, int, TLess<char>>;
+
+        {
+            maptype m;
+            m['x'] = 10;
+
+            std::pair<maptype::iterator, maptype::iterator> ret;
+            ret = m.equal_range('x');
+            UNIT_ASSERT(ret.first != ret.second);
+            UNIT_ASSERT((*(ret.first)).first == 'x');
+            UNIT_ASSERT((*(ret.first)).second == 10);
+            UNIT_ASSERT(++(ret.first) == ret.second);
+        }
+
+        {
+            {
+                maptype m;
+
+                maptype::iterator i = m.lower_bound('x');
+                UNIT_ASSERT(i == m.end());
+
+                i = m.upper_bound('x');
+                UNIT_ASSERT(i == m.end());
+
+                std::pair<maptype::iterator, maptype::iterator> ret;
+                ret = m.equal_range('x');
+                UNIT_ASSERT(ret.first == ret.second);
+                UNIT_ASSERT(ret.first == m.end());
+            }
+
+            {
+                const maptype m;
+                std::pair<maptype::const_iterator, maptype::const_iterator> ret;
+                ret = m.equal_range('x');
+                UNIT_ASSERT(ret.first == ret.second);
+                UNIT_ASSERT(ret.first == m.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 Container = TMap<TKey, int, TKeyCmp>;
+            using value = Container::value_type;
+
+            Container cont;
+
+            cont.insert(value(TKey(1), 1));
+            cont.insert(value(TKey(2), 2));
+            cont.insert(value(TKey(3), 3));
+            cont.insert(value(TKey(4), 4));
+
+            UNIT_ASSERT(cont.count(TKey(1)) == 1);
+            UNIT_ASSERT(cont.count(1) == 1);
+            UNIT_ASSERT(cont.count(5) == 0);
+
+            UNIT_ASSERT(cont.find(2) != cont.end());
+            UNIT_ASSERT(cont.lower_bound(2) != cont.end());
+            UNIT_ASSERT(cont.upper_bound(2) != cont.end());
+            UNIT_ASSERT(cont.equal_range(2) != std::make_pair(cont.begin(), cont.end()));
+
+            Container const& ccont = cont;
+
+            UNIT_ASSERT(ccont.find(2) != ccont.end());
+            UNIT_ASSERT(ccont.lower_bound(2) != ccont.end());
+            UNIT_ASSERT(ccont.upper_bound(2) != ccont.end());
+            UNIT_ASSERT(ccont.equal_range(2) != std::make_pair(ccont.end(), ccont.end()));
+        }
+
+        {
+            using Container = TMap<TKey*, int, TKeyCmpPtr>;
+            using value = Container::value_type;
+
+            Container cont;
+
+            TKey key1(1), key2(2), key3(3), key4(4);
+
+            cont.insert(value(&key1, 1));
+            cont.insert(value(&key2, 2));
+            cont.insert(value(&key3, 3));
+            cont.insert(value(&key4, 4));
+
+            UNIT_ASSERT(cont.count(1) == 1);
+            UNIT_ASSERT(cont.count(5) == 0);
+
+            UNIT_ASSERT(cont.find(2) != cont.end());
+            UNIT_ASSERT(cont.lower_bound(2) != cont.end());
+            UNIT_ASSERT(cont.upper_bound(2) != cont.end());
+            UNIT_ASSERT(cont.equal_range(2) != std::make_pair(cont.begin(), cont.end()));
+
+            Container const& ccont = cont;
+
+            UNIT_ASSERT(ccont.find(2) != ccont.end());
+            UNIT_ASSERT(ccont.lower_bound(2) != ccont.end());
+            UNIT_ASSERT(ccont.upper_bound(2) != ccont.end());
+            UNIT_ASSERT(ccont.equal_range(2) != std::make_pair(ccont.begin(), ccont.end()));
+        }
+
+        {
+            using Container = TMultiMap<TKey, int, TKeyCmp>;
+            using value = Container::value_type;
+
+            Container cont;
+
+            cont.insert(value(TKey(1), 1));
+            cont.insert(value(TKey(2), 2));
+            cont.insert(value(TKey(3), 3));
+            cont.insert(value(TKey(4), 4));
+
+            UNIT_ASSERT(cont.count(TKey(1)) == 1);
+            UNIT_ASSERT(cont.count(1) == 1);
+            UNIT_ASSERT(cont.count(5) == 0);
+
+            UNIT_ASSERT(cont.find(2) != cont.end());
+            UNIT_ASSERT(cont.lower_bound(2) != cont.end());
+            UNIT_ASSERT(cont.upper_bound(2) != cont.end());
+            UNIT_ASSERT(cont.equal_range(2) != std::make_pair(cont.begin(), cont.end()));
+
+            Container const& ccont = cont;
+
+            UNIT_ASSERT(ccont.find(2) != ccont.end());
+            UNIT_ASSERT(ccont.lower_bound(2) != ccont.end());
+            UNIT_ASSERT(ccont.upper_bound(2) != ccont.end());
+            UNIT_ASSERT(ccont.equal_range(2) != std::make_pair(ccont.end(), ccont.end()));
+        }
+
+        {
+            using Container = TMultiMap<TKey const volatile*, int, TKeyCmpPtr>;
+            using value = Container::value_type;
+
+            Container cont;
+
+            TKey key1(1), key2(2), key3(3), key4(4);
+
+            cont.insert(value(&key1, 1));
+            cont.insert(value(&key2, 2));
+            cont.insert(value(&key3, 3));
+            cont.insert(value(&key4, 4));
+
+            UNIT_ASSERT(cont.count(1) == 1);
+            UNIT_ASSERT(cont.count(5) == 0);
+
+            UNIT_ASSERT(cont.find(2) != cont.end());
+            UNIT_ASSERT(cont.lower_bound(2) != cont.end());
+            UNIT_ASSERT(cont.upper_bound(2) != cont.end());
+            UNIT_ASSERT(cont.equal_range(2) != std::make_pair(cont.begin(), cont.end()));
+
+            Container const& ccont = cont;
+
+            UNIT_ASSERT(ccont.find(2) != ccont.end());
+            UNIT_ASSERT(ccont.lower_bound(2) != ccont.end());
+            UNIT_ASSERT(ccont.upper_bound(2) != ccont.end());
+            UNIT_ASSERT(ccont.equal_range(2) != std::make_pair(ccont.begin(), ccont.end()));
+        }
+    }
+
+    template <typename T>
+    static void EmptyAndInsertTest(typename T::value_type v) {
+        T c;
+        UNIT_ASSERT(!c);
+        c.insert(v);
+        UNIT_ASSERT(c);
+    }
+
+    Y_UNIT_TEST(TestEmpty) {
+        EmptyAndInsertTest<TMap<char, int, TLess<char>>>(std::pair<char, int>('a', 1));
+        EmptyAndInsertTest<TMultiMap<char, int, TLess<char>>>(std::pair<char, int>('a', 1));
+    }
+
+    struct TParametrizedKeyCmp {
+        bool Inverse;
+
+        TParametrizedKeyCmp(bool inverse = false)
+            : Inverse(inverse)
+        {
+        }
+
+        bool operator()(TKey lhs, TKey rhs) const {
+            if (Inverse) {
+                return lhs.m_data > rhs.m_data;
+            } else {
+                return lhs.m_data < rhs.m_data;
+            }
+        }
+    };
+
+    Y_UNIT_TEST(TestMoveComparator) {
+        using Container = TMultiMap<TKey, int, TParametrizedKeyCmp>;
+
+        TParametrizedKeyCmp direct(false);
+        TParametrizedKeyCmp inverse(true);
+
+        {
+            Container c(direct);
+            c = Container(inverse);
+
+            c.insert(std::make_pair(TKey(1), 101));
+            c.insert(std::make_pair(TKey(2), 102));
+            c.insert(std::make_pair(TKey(3), 103));
+
+            TVector<int> values;
+            for (auto& i : c) {
+                values.push_back(i.second);
+            }
+
+            UNIT_ASSERT_VALUES_EQUAL(values.size(), 3);
+            UNIT_ASSERT_VALUES_EQUAL(values[0], 103);
+            UNIT_ASSERT_VALUES_EQUAL(values[1], 102);
+            UNIT_ASSERT_VALUES_EQUAL(values[2], 101);
+        }
+    }
+
+    Y_UNIT_TEST(TestMapInitializerList) {
+        TMap<TString, int> m = {
+            {"one", 1},
+            {"two", 2},
+            {"three", 3},
+            {"four", 4},
+        };
+
+        UNIT_ASSERT_VALUES_EQUAL(m.size(), 4);
+        UNIT_ASSERT_VALUES_EQUAL(m["one"], 1);
+        UNIT_ASSERT_VALUES_EQUAL(m["two"], 2);
+        UNIT_ASSERT_VALUES_EQUAL(m["three"], 3);
+        UNIT_ASSERT_VALUES_EQUAL(m["four"], 4);
+    }
+
+    Y_UNIT_TEST(TestMMapInitializerList) {
+        TMultiMap<TString, int> mm = {
+            {"one", 1},
+            {"two", 2},
+            {"two", -2},
+            {"three", 3},
+        };
+        UNIT_ASSERT(mm.contains("two"));
+        TMultiMap<TString, int> expected;
+        expected.emplace("one", 1);
+        expected.emplace("two", 2);
+        expected.emplace("two", -2);
+        expected.emplace("three", 3);
+        UNIT_ASSERT_VALUES_EQUAL(mm, expected);
+    }
+
+    Y_UNIT_TEST(TestMovePoolAlloc) {
+        using TMapInPool = TMap<int, int, TLess<int>, TPoolAllocator>;
+
+        TMemoryPool pool(1);
+
+        TMapInPool m(&pool);
+        m.emplace(0, 1);
+
+        UNIT_ASSERT(m.contains(0));
+        UNIT_ASSERT_VALUES_EQUAL(1, m[0]);
+
+        TMapInPool movedM = std::move(m);
+
+        UNIT_ASSERT(movedM.contains(0));
+        UNIT_ASSERT_VALUES_EQUAL(1, movedM[0]);
+    }
+}