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