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