#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())); } } }