#include <library/cpp/testing/unittest/registar.h>
#include "algorithm.h"
#include "hash.h"
#include "hash_multi_map.h"
#include "strbuf.h"
#include "string.h"
static auto isOne = [](char c) { return c == '1'; };
Y_UNIT_TEST_SUITE(TAlgorithm) {
Y_UNIT_TEST(AnyTest) {
UNIT_ASSERT(0 == AnyOf(TStringBuf("00"), isOne));
UNIT_ASSERT(1 == AnyOf(TStringBuf("01"), isOne));
UNIT_ASSERT(1 == AnyOf(TStringBuf("10"), isOne));
UNIT_ASSERT(1 == AnyOf(TStringBuf("11"), isOne));
UNIT_ASSERT(0 == AnyOf(TStringBuf(), isOne));
const char array00[]{'0', '0'};
UNIT_ASSERT(0 == AnyOf(array00, isOne));
const char array01[]{'0', '1'};
UNIT_ASSERT(1 == AnyOf(array01, isOne));
}
Y_UNIT_TEST(AllOfTest) {
UNIT_ASSERT(0 == AllOf(TStringBuf("00"), isOne));
UNIT_ASSERT(0 == AllOf(TStringBuf("01"), isOne));
UNIT_ASSERT(0 == AllOf(TStringBuf("10"), isOne));
UNIT_ASSERT(1 == AllOf(TStringBuf("11"), isOne));
UNIT_ASSERT(1 == AllOf(TStringBuf(), isOne));
const char array01[]{'0', '1'};
UNIT_ASSERT(0 == AllOf(array01, isOne));
const char array11[]{'1', '1'};
UNIT_ASSERT(1 == AllOf(array11, isOne));
}
Y_UNIT_TEST(CountIfTest) {
UNIT_ASSERT(3 == CountIf(TStringBuf("____1________1____1_______"), isOne));
UNIT_ASSERT(5 == CountIf(TStringBuf("1____1________1____1_______1"), isOne));
UNIT_ASSERT(0 == CountIf(TStringBuf("___________"), isOne));
UNIT_ASSERT(0 == CountIf(TStringBuf(), isOne));
UNIT_ASSERT(1 == CountIf(TStringBuf("1"), isOne));
const char array[] = "____1________1____1_______";
UNIT_ASSERT(3 == CountIf(array, isOne));
}
Y_UNIT_TEST(CountTest) {
UNIT_ASSERT(3 == Count("____1________1____1_______", '1'));
UNIT_ASSERT(3 == Count(TStringBuf("____1________1____1_______"), '1'));
UNIT_ASSERT(5 == Count(TStringBuf("1____1________1____1_______1"), '1'));
UNIT_ASSERT(0 == Count(TStringBuf("___________"), '1'));
UNIT_ASSERT(0 == Count(TStringBuf(), '1'));
UNIT_ASSERT(1 == Count(TStringBuf("1"), '1'));
const char array[] = "____1________1____1_______";
UNIT_ASSERT(3 == Count(array, '1'));
}
struct TStrokaNoCopy: TString {
public:
TStrokaNoCopy(const char* p)
: TString(p)
{
}
private:
TStrokaNoCopy(const TStrokaNoCopy&);
void operator=(const TStrokaNoCopy&);
};
Y_UNIT_TEST(CountOfTest) {
UNIT_ASSERT_VALUES_EQUAL(CountOf(1, 2), 0);
UNIT_ASSERT_VALUES_EQUAL(CountOf(1, 1), 1);
UNIT_ASSERT_VALUES_EQUAL(CountOf(2, 4, 5), 0);
UNIT_ASSERT_VALUES_EQUAL(CountOf(2, 4, 2), 1);
UNIT_ASSERT_VALUES_EQUAL(CountOf(3, 3, 3), 2);
// Checking comparison of different types.
UNIT_ASSERT_VALUES_EQUAL(CountOf(0x61, 'x', 'y', 'z'), 0);
UNIT_ASSERT_VALUES_EQUAL(CountOf(0x61, 'a', 'b', 'c', 0x61), 2);
UNIT_ASSERT_VALUES_EQUAL(CountOf(0x61, 'a', 'b', 'c', 0x61ll), 2);
// TString and const char *
UNIT_ASSERT_VALUES_EQUAL(CountOf(TString("xyz"), "123", "poi"), 0);
UNIT_ASSERT_VALUES_EQUAL(CountOf(TString("xyz"), "123", "poi", "xyz"), 1);
// TString and TStringBuf
UNIT_ASSERT_VALUES_EQUAL(CountOf(TString("xyz"), TStringBuf("123"), TStringBuf("poi")), 0);
UNIT_ASSERT_VALUES_EQUAL(CountOf(TString("xyz"), TStringBuf("123"), TStringBuf("poi"),
TStringBuf("xyz")),
1);
// TStringBuf and const char *
UNIT_ASSERT_VALUES_EQUAL(CountOf(TStringBuf("xyz"), "123", "poi"), 0);
UNIT_ASSERT_VALUES_EQUAL(CountOf(TStringBuf("xyz"), "123", "poi", "xyz"), 1);
// TStringBuf and TString
UNIT_ASSERT_VALUES_EQUAL(CountOf(TStringBuf("xyz"), TString("123"), TString("poi")), 0);
UNIT_ASSERT_VALUES_EQUAL(CountOf(TStringBuf("xyz"), TString("123"), TString("poi"),
TString("xyz")),
1);
}
Y_UNIT_TEST(EqualToOneOfTest) {
UNIT_ASSERT(1 == EqualToOneOf(1, 1, 2));
UNIT_ASSERT(1 == EqualToOneOf(2, 1, 2));
UNIT_ASSERT(0 == EqualToOneOf(3, 1, 2));
UNIT_ASSERT(1 == EqualToOneOf(1, 1));
UNIT_ASSERT(0 == EqualToOneOf(1, 2));
UNIT_ASSERT(0 == EqualToOneOf(3));
// test, that EqualToOneOf can compare different types, and don't copy objects:
TStrokaNoCopy x("x");
TStrokaNoCopy y("y");
TStrokaNoCopy z("z");
const char* px = "x";
const char* py = "y";
const char* pz = "z";
UNIT_ASSERT(1 == EqualToOneOf(x, px, py));
UNIT_ASSERT(1 == EqualToOneOf(y, px, py));
UNIT_ASSERT(1 == EqualToOneOf(y, px, y));
UNIT_ASSERT(1 == EqualToOneOf(y, x, py));
UNIT_ASSERT(0 == EqualToOneOf(z, px, py));
UNIT_ASSERT(1 == EqualToOneOf(px, x, y));
UNIT_ASSERT(1 == EqualToOneOf(py, x, y));
UNIT_ASSERT(0 == EqualToOneOf(pz, x, y));
}
template <class TTestConstPtr>
void TestFindPtrFoundValue(int j, TTestConstPtr root) {
if (j == 3) {
UNIT_ASSERT(root && *root == 3);
} else if (j == 4) {
UNIT_ASSERT(root == nullptr);
} else {
ythrow yexception() << "invalid param " << j;
}
}
template <class TTestConstPtr>
void TestFindIfPtrFoundValue(int j, TTestConstPtr root) {
if (j == 3) {
UNIT_ASSERT(root == nullptr);
} else if (j == 4) {
UNIT_ASSERT(root && *root == 2);
} else {
ythrow yexception() << "invalid param " << j;
}
}
struct TVectorNoCopy: std::vector<int> {
public:
TVectorNoCopy() = default;
private:
TVectorNoCopy(const TVectorNoCopy&);
void operator=(const TVectorNoCopy&);
};
Y_UNIT_TEST(FindPtrTest) {
TVectorNoCopy v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
int array[3] = {1, 2, 3};
const int array_const[3] = {1, 2, 3};
// test (const, non-const) * (iterator, vector, array) * (found, not found) variants.
// value '3' is in container, value '4' is not
for (int j = 3; j <= 4; ++j) {
TestFindPtrFoundValue<int*>(j, FindPtr(v, j));
TestFindPtrFoundValue<int*>(j, FindPtr(v.begin(), v.end(), j));
const TVectorNoCopy& q = v;
TestFindPtrFoundValue<const int*>(j, FindPtr(q, j));
TestFindPtrFoundValue<const int*>(j, FindPtr(q.begin(), q.end(), j));
TestFindPtrFoundValue<int*>(j, FindPtr(array, j));
TestFindPtrFoundValue<const int*>(j, FindPtr(array_const, j));
}
}
Y_UNIT_TEST(FindIfPtrTest) {
TVectorNoCopy v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
int array[3] = {1, 2, 3};
const int array_const[3] = {1, 2, 3};
// test (const, non-const) * (iterator, vector, array) * (found, not found) variants.
// search, that 2*2 == 4, but there is no value 'x' in array that (x*x == 3)
for (int j = 3; j <= 4; ++j) {
TestFindIfPtrFoundValue<int*>(j, FindIfPtr(v, [j](int i) { return i * i == j; }));
TestFindIfPtrFoundValue<int*>(j, FindIfPtr(v.begin(), v.end(), [j](int i) { return i * i == j; }));
const TVectorNoCopy& q = v;
TestFindIfPtrFoundValue<const int*>(j, FindIfPtr(q, [j](int i) { return i * i == j; }));
TestFindIfPtrFoundValue<const int*>(j, FindIfPtr(q.begin(), q.end(), [j](int i) { return i * i == j; }));
TestFindIfPtrFoundValue<int*>(j, FindIfPtr(array, [j](int i) { return i * i == j; }));
TestFindIfPtrFoundValue<const int*>(j, FindIfPtr(array_const, [j](int i) { return i * i == j; }));
}
}
Y_UNIT_TEST(FindIndexTest) {
TVectorNoCopy v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
UNIT_ASSERT_EQUAL(0, FindIndex(v, 1));
UNIT_ASSERT_EQUAL(1, FindIndex(v, 2));
UNIT_ASSERT_EQUAL(2, FindIndex(v, 3));
UNIT_ASSERT_EQUAL(NPOS, FindIndex(v, 42));
int array[3] = {1, 2, 3};
UNIT_ASSERT_EQUAL(0, FindIndex(array, 1));
UNIT_ASSERT_EQUAL(1, FindIndex(array, 2));
UNIT_ASSERT_EQUAL(2, FindIndex(array, 3));
UNIT_ASSERT_EQUAL(NPOS, FindIndex(array, 42));
TVector<int> empty;
UNIT_ASSERT_EQUAL(NPOS, FindIndex(empty, 0));
}
Y_UNIT_TEST(FindIndexIfTest) {
TVectorNoCopy v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
UNIT_ASSERT_EQUAL(0, FindIndexIf(v, [](int x) { return x == 1; }));
UNIT_ASSERT_EQUAL(1, FindIndexIf(v, [](int x) { return x == 2; }));
UNIT_ASSERT_EQUAL(2, FindIndexIf(v, [](int x) { return x == 3; }));
UNIT_ASSERT_EQUAL(NPOS, FindIndexIf(v, [](int x) { return x == 42; }));
int array[3] = {1, 2, 3};
UNIT_ASSERT_EQUAL(0, FindIndexIf(array, [](int x) { return x == 1; }));
UNIT_ASSERT_EQUAL(1, FindIndexIf(array, [](int x) { return x == 2; }));
UNIT_ASSERT_EQUAL(2, FindIndexIf(array, [](int x) { return x == 3; }));
UNIT_ASSERT_EQUAL(NPOS, FindIndexIf(array, [](int x) { return x == 42; }));
TVector<int> empty;
UNIT_ASSERT_EQUAL(NPOS, FindIndexIf(empty, [](int x) { return x == 3; }));
}
Y_UNIT_TEST(SortUniqueTest) {
{
TVector<TString> v;
SortUnique(v);
UNIT_ASSERT_EQUAL(v, TVector<TString>());
}
{
const char* ar[] = {"345", "3", "123", "2", "23", "3", "2"};
TVector<TString> v(ar, ar + Y_ARRAY_SIZE(ar));
SortUnique(v);
const char* suAr[] = {"123", "2", "23", "3", "345"};
TVector<TString> suV(suAr, suAr + Y_ARRAY_SIZE(suAr));
UNIT_ASSERT_EQUAL(v, suV);
}
}
Y_UNIT_TEST(EraseTest) {
TVector<int> data = {5, 4, 3, 2, 1, 0};
TVector<int> expected = {5, 4, 2, 1, 0};
Erase(data, 3);
UNIT_ASSERT_EQUAL(data, expected);
}
Y_UNIT_TEST(EraseIfTest) {
TVector<int> data = {5, 4, 3, 2, 1, 0};
TVector<int> expected = {2, 1, 0};
EraseIf(data, [](int i) { return i >= 3; });
UNIT_ASSERT_EQUAL(data, expected);
}
Y_UNIT_TEST(EraseNodesIfTest) {
TMap<int, int> map{{1, 1}, {2, 2}, {3, 5}};
TMap<int, int> expectedMap{{1, 1}};
EraseNodesIf(map, [](auto p) { return p.first >= 2; });
UNIT_ASSERT_EQUAL(map, expectedMap);
TMultiMap<int, int> multiMap{{1, 1}, {1, 3}, {2, 2}, {3, 5}};
TMultiMap<int, int> expectedMultiMap{{1, 1}, {1, 3}};
EraseNodesIf(multiMap, [](auto p) { return p.first >= 2; });
UNIT_ASSERT_EQUAL(multiMap, expectedMultiMap);
TSet<int> set{1, 2, 3, 4, 5, 6, 7};
TSet<int> expectedSet{1, 3, 5, 7};
EraseNodesIf(set, [](int i) { return i % 2 == 0; });
UNIT_ASSERT_EQUAL(set, expectedSet);
TMultiSet<int> multiSet{1, 1, 2, 3, 4, 4, 4, 5, 5, 5, 6, 7};
TMultiSet<int> expectedMultiSet{1, 1, 3, 5, 5, 5, 7};
EraseNodesIf(multiSet, [](int i) { return i % 2 == 0; });
UNIT_ASSERT_EQUAL(multiSet, expectedMultiSet);
THashMap<int, int> hashMap{{1, 0}, {3, 0}, {4, 0}, {10, 0}, {2, 0}, {5, 2}};
THashMap<int, int> expectedHashMap{{1, 0}, {3, 0}, {5, 2}};
EraseNodesIf(hashMap, [](auto p) { return p.first % 2 == 0; });
UNIT_ASSERT_EQUAL(hashMap, expectedHashMap);
THashMultiMap<int, int> hashMultiMap{{1, 0}, {3, 0}, {4, 0}, {10, 0}, {2, 0}, {5, 0}, {1, 0}, {1, 0}, {2, 0}, {2, 2}};
THashMultiMap<int, int> expectedHashMultiMap{{1, 0}, {1, 0}, {1, 0}, {3, 0}, {5, 0}};
EraseNodesIf(hashMultiMap, [](auto p) { return p.first % 2 == 0; });
UNIT_ASSERT_EQUAL(hashMultiMap, expectedHashMultiMap);
}
Y_UNIT_TEST(NthElementTest) {
{
TVector<TString> v;
NthElement(v.begin(), v.begin(), v.end());
UNIT_ASSERT_EQUAL(v, TVector<TString>());
}
{
int data[] = {3, 2, 1, 4, 6, 5, 7, 9, 8};
TVector<int> testVector(data, data + Y_ARRAY_SIZE(data));
size_t medianInd = testVector.size() / 2;
NthElement(testVector.begin(), testVector.begin() + medianInd, testVector.end());
UNIT_ASSERT_EQUAL(testVector[medianInd], 5);
NthElement(testVector.begin(), testVector.begin() + medianInd, testVector.end(), [](int lhs, int rhs) { return lhs > rhs; });
UNIT_ASSERT_EQUAL(testVector[medianInd], 5);
}
{
const char* data[] = {"3", "234", "1231", "333", "545345", "11", "111", "55", "66"};
TVector<TString> testVector(data, data + Y_ARRAY_SIZE(data));
size_t medianInd = testVector.size() / 2;
NthElement(testVector.begin(), testVector.begin() + medianInd, testVector.end());
auto median = testVector.begin() + medianInd;
for (auto it0 = testVector.begin(); it0 != median; ++it0) {
for (auto it1 = median; it1 != testVector.end(); ++it1) {
UNIT_ASSERT(*it0 <= *it1);
}
}
}
}
Y_UNIT_TEST(BinarySearchTest) {
{
TVector<TString> v;
bool test = BinarySearch(v.begin(), v.end(), "test");
UNIT_ASSERT_EQUAL(test, false);
}
{
int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
bool test = BinarySearch(data, data + Y_ARRAY_SIZE(data), 2);
UNIT_ASSERT_EQUAL(test, true);
test = BinarySearch(data, data + Y_ARRAY_SIZE(data), 10);
UNIT_ASSERT_EQUAL(test, false);
}
{
TVector<size_t> data = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
bool test = BinarySearch(data.begin(), data.end(), (size_t)9, TGreater<size_t>());
UNIT_ASSERT_EQUAL(test, true);
test = BinarySearch(data.begin(), data.end(), (size_t)11, TGreater<size_t>());
UNIT_ASSERT_EQUAL(test, false);
test = BinarySearch(data.rbegin(), data.rend(), (size_t)1);
UNIT_ASSERT_EQUAL(test, true);
}
}
Y_UNIT_TEST(EqualRangeTest) {
{
TVector<TString> v;
using PairOfVector = std::pair<TVector<TString>::iterator, TVector<TString>::iterator>;
PairOfVector tmp = EqualRange(v.begin(), v.end(), "tmp");
UNIT_ASSERT_EQUAL(tmp.first, tmp.second);
UNIT_ASSERT_EQUAL(tmp.first, v.end());
}
{
int data[] = {1, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 5};
using PairOfInt = std::pair<int*, int*>;
PairOfInt tmp = EqualRange(data, data + Y_ARRAY_SIZE(data), 3);
UNIT_ASSERT_EQUAL(tmp.second - tmp.first, 4);
UNIT_ASSERT_EQUAL(tmp.first - data, 7);
UNIT_ASSERT_EQUAL(data + Y_ARRAY_SIZE(data) - tmp.second, 2);
}
{
TVector<size_t> data = {9, 9, 8, 8, 8, 5, 4, 3, 3, 0, 0};
using PairOfVector = std::pair<TVector<size_t>::iterator, TVector<size_t>::iterator>;
PairOfVector tmp = EqualRange(data.begin(), data.end(), 8, TGreater<size_t>());
UNIT_ASSERT_EQUAL(tmp.first - data.begin(), 2);
UNIT_ASSERT_EQUAL(tmp.second - tmp.first, 3);
using PairOfVectorReverse = std::pair<TVector<size_t>::reverse_iterator, TVector<size_t>::reverse_iterator>;
PairOfVectorReverse tmpR = EqualRange(data.rbegin(), data.rend(), (size_t)0);
UNIT_ASSERT_EQUAL(tmpR.first, data.rbegin());
UNIT_ASSERT_EQUAL(tmpR.second - tmpR.first, 2);
}
}
Y_UNIT_TEST(AdjacentFindTest) {
TVector<int> v0;
UNIT_ASSERT_EQUAL(AdjacentFind(v0), v0.end());
TVector<int> v1 = {1};
UNIT_ASSERT_EQUAL(AdjacentFind(v1), v1.end());
const int v2[] = {8, 7, 6, 6, 5, 5, 5, 4, 3, 2, 1};
UNIT_ASSERT_EQUAL(AdjacentFind(v2), std::begin(v2) + 2);
TVector<TStringBuf> v3 = {"six", "five", "four", "three", "two", "one"};
UNIT_ASSERT_EQUAL(AdjacentFind(v3), v3.end());
TVector<int> v4 = {1, 1, 1, 1, 1};
for (;;) {
if (auto it = AdjacentFind(v4); it == v4.end()) {
break;
} else {
*it += 1;
}
}
UNIT_ASSERT_VALUES_EQUAL(v4, (TVector<int>{5, 4, 3, 2, 1}));
}
Y_UNIT_TEST(AdjacentFindByTest) {
TVector<int> v0;
UNIT_ASSERT_EQUAL(AdjacentFindBy(v0, std::negate<int>()), v0.end());
TVector<int> v1 = {1};
UNIT_ASSERT_EQUAL(AdjacentFindBy(v1, std::negate<int>()), v1.end());
const int v2[] = {8, 7, 6, 6, 5, 5, 5, 4, 3, 2, 1};
UNIT_ASSERT_EQUAL(AdjacentFindBy(v2, std::negate<int>()), std::begin(v2) + 2);
UNIT_ASSERT_EQUAL(AdjacentFindBy(v2, [](const auto& e) { return e / 8; }), std::begin(v2) + 1);
TVector<TStringBuf> v3 = {"six", "five", "four", "three", "two", "one"};
UNIT_ASSERT_EQUAL(AdjacentFind(v3), v3.end());
UNIT_ASSERT_EQUAL(AdjacentFindBy(v3, std::mem_fn(&TStringBuf::size)), v3.begin() + 1);
TVector<int> v4 = {101, 201, 301, 401, 501};
for (;;) {
if (auto it = AdjacentFindBy(v4, [](int a) { return a % 10; }); it == v4.end()) {
break;
} else {
*it += 1;
}
}
UNIT_ASSERT_VALUES_EQUAL(v4, (TVector<int>{105, 204, 303, 402, 501}));
}
Y_UNIT_TEST(IsSortedTest) {
TVector<int> v0;
UNIT_ASSERT_VALUES_EQUAL(IsSorted(v0.begin(), v0.end()), true);
TVector<int> v1 = {1, 2, 3, 4, 5, 5, 5, 6, 6, 7, 8};
UNIT_ASSERT_VALUES_EQUAL(IsSorted(v1.begin(), v1.end()), true);
UNIT_ASSERT_VALUES_EQUAL(IsSorted(v1.begin(), v1.end(), TLess<int>()), true);
UNIT_ASSERT_VALUES_EQUAL(IsSorted(v1.begin(), v1.end(), TGreater<int>()), false);
TVector<int> v2 = {1, 2, 1};
UNIT_ASSERT_VALUES_EQUAL(IsSorted(v2.begin(), v2.end()), false);
UNIT_ASSERT_VALUES_EQUAL(IsSorted(v2.begin(), v2.end(), TLess<int>()), false);
UNIT_ASSERT_VALUES_EQUAL(IsSorted(v2.begin(), v2.end(), TGreater<int>()), false);
}
Y_UNIT_TEST(IsSortedByTest) {
TVector<int> v0;
UNIT_ASSERT_VALUES_EQUAL(IsSortedBy(v0.begin(), v0.end(), std::negate<int>()), true);
UNIT_ASSERT_VALUES_EQUAL(IsSortedBy(v0, std::negate<int>()), true);
TVector<int> v1 = {1};
UNIT_ASSERT_VALUES_EQUAL(IsSortedBy(v1.begin(), v1.end(), std::negate<int>()), true);
UNIT_ASSERT_VALUES_EQUAL(IsSortedBy(v1, std::negate<int>()), true);
TVector<int> v2 = {8, 7, 6, 6, 5, 5, 5, 4, 3, 2, 1};
UNIT_ASSERT_VALUES_EQUAL(IsSortedBy(v2.begin(), v2.end(), std::negate<int>()), true);
UNIT_ASSERT_VALUES_EQUAL(IsSortedBy(v2, std::negate<int>()), true);
TVector<int> v3 = {1, 2, 1};
UNIT_ASSERT_VALUES_EQUAL(IsSortedBy(v3.begin(), v3.end(), std::negate<int>()), false);
UNIT_ASSERT_VALUES_EQUAL(IsSortedBy(v3, std::negate<int>()), false);
}
Y_UNIT_TEST(SortTestTwoIterators) {
TVector<int> collection = {10, 2, 7};
Sort(collection.begin(), collection.end());
TVector<int> expected = {2, 7, 10};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(SortTestTwoIteratorsAndComparator) {
TVector<int> collection = {10, 2, 7};
Sort(collection.begin(), collection.end(), [](int l, int r) { return l > r; });
TVector<int> expected = {10, 7, 2};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(SortTestContainer) {
TVector<int> collection = {10, 2, 7};
Sort(collection);
TVector<int> expected = {2, 7, 10};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(SortTestContainerAndComparator) {
TVector<int> collection = {10, 2, 7};
Sort(collection, [](int l, int r) { return l > r; });
TVector<int> expected = {10, 7, 2};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(StableSortTestTwoIterators) {
TVector<int> collection = {10, 2, 7};
StableSort(collection.begin(), collection.end());
TVector<int> expected = {2, 7, 10};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(StableSortTestTwoIteratorsAndComparator) {
TVector<int> collection = {404, 101, 106, 203, 102, 205, 401};
StableSort(collection.begin(), collection.end(), [](int l, int r) { return (l / 100) < (r / 100); });
TVector<int> expected = {101, 106, 102, 203, 205, 404, 401};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(StableSortTestContainer) {
TVector<int> collection = {10, 2, 7};
StableSort(collection);
TVector<int> expected = {2, 7, 10};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(StableSortTestContainerAndComparator) {
TVector<int> collection = {404, 101, 106, 203, 102, 205, 401};
StableSort(collection, [](int l, int r) { return (l / 100) < (r / 100); });
TVector<int> expected = {101, 106, 102, 203, 205, 404, 401};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(SortByTest) {
TVector<int> collection = {10, 2, 7};
SortBy(collection, [](int x) { return -x; });
TVector<int> expected = {10, 7, 2};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(StableSortByTest) {
TVector<int> collection = {404, 101, 106, 203, 102, 205, 401};
StableSortBy(collection, [](int x) { return x / 100; });
TVector<int> expected = {101, 106, 102, 203, 205, 404, 401};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(SortUniqueByTest) {
TVector<int> collection = {404, 101, 101, 203, 101, 203, 404};
StableSortUniqueBy(collection, [](int x) { return x / 100; });
TVector<int> expected = {101, 203, 404};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(StableSortUniqueByTest) {
TVector<int> collection = {404, 101, 106, 203, 102, 205, 401};
StableSortUniqueBy(collection, [](int x) { return x / 100; });
TVector<int> expected = {101, 203, 404};
UNIT_ASSERT_VALUES_EQUAL(collection, expected);
}
Y_UNIT_TEST(IotaTest) {
TVector<int> v(10);
Iota(v.begin(), v.end(), 0);
UNIT_ASSERT_VALUES_EQUAL(v[0], 0);
UNIT_ASSERT_VALUES_EQUAL(v[5], 5);
UNIT_ASSERT_VALUES_EQUAL(v[9], 9);
Iota(v.begin() + 2, v.begin() + 5, 162);
UNIT_ASSERT_VALUES_EQUAL(v[0], 0);
UNIT_ASSERT_VALUES_EQUAL(v[3], 163);
UNIT_ASSERT_VALUES_EQUAL(v[9], 9);
}
Y_UNIT_TEST(CopyNTest) {
int data[] = {1, 2, 3, 4, 8, 7, 6, 5};
const size_t vSize = 10;
TVector<int> result(10, 0);
size_t toCopy = 5;
TVector<int>::iterator iter = CopyN(data, toCopy, result.begin());
UNIT_ASSERT_VALUES_EQUAL(iter - result.begin(), toCopy);
UNIT_ASSERT_VALUES_EQUAL(result.size(), 10);
for (size_t idx = 0; idx < toCopy; ++idx) {
UNIT_ASSERT_VALUES_EQUAL(data[idx], result[idx]);
}
for (size_t idx = toCopy; idx < vSize; ++idx) {
UNIT_ASSERT_VALUES_EQUAL(result[idx], 0);
}
toCopy = 8;
const size_t start = 1;
result.assign(vSize, 0);
iter = CopyN(data, toCopy, result.begin() + start);
UNIT_ASSERT_VALUES_EQUAL(iter - result.begin(), start + toCopy);
for (size_t idx = 0; idx < start; ++idx) {
UNIT_ASSERT_VALUES_EQUAL(result[idx], 0);
}
for (size_t idx = 0; idx < toCopy; ++idx) {
UNIT_ASSERT_VALUES_EQUAL(result[start + idx], data[idx]);
}
for (size_t idx = start + toCopy; idx < vSize; ++idx) {
UNIT_ASSERT_VALUES_EQUAL(result[idx], 0);
}
}
Y_UNIT_TEST(CopyIfTest) {
const size_t count = 9;
int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
const size_t vSize = 10;
TVector<int> v(vSize, 0);
TVector<int>::iterator iter = CopyIf(data, data + count, v.begin(), [](int x) { return !(x % 3); });
UNIT_ASSERT_VALUES_EQUAL(v.size(), vSize);
UNIT_ASSERT_VALUES_EQUAL(iter - v.begin(), 3);
v.resize(iter - v.begin());
for (size_t idx = 0; idx < v.size(); ++idx) {
UNIT_ASSERT_VALUES_EQUAL(v[idx], 3 * (idx + 1));
}
}
Y_UNIT_TEST(MinMaxElementTest) {
TVector<int> v(10);
Iota(v.begin(), v.end(), 0);
UNIT_ASSERT_EQUAL(*MinMaxElement(v.begin(), v.end()).first, 0);
UNIT_ASSERT_EQUAL(*MinMaxElement(v.begin(), v.end()).second, 9);
v[3] = -2;
v[7] = 11;
UNIT_ASSERT_EQUAL(*MinMaxElement(v.begin(), v.end()).first, -2);
UNIT_ASSERT_EQUAL(*MinMaxElement(v.begin(), v.end()).second, 11);
}
Y_UNIT_TEST(MinMaxTest) {
std::pair<int, int> p1 = MinMax(5, 12);
UNIT_ASSERT_EQUAL(p1.first, 5);
UNIT_ASSERT_EQUAL(p1.second, 12);
std::pair<TString, TString> p2 = MinMax(TString("test"), TString("data"));
UNIT_ASSERT_EQUAL(p2.first, TString("data"));
UNIT_ASSERT_EQUAL(p2.second, TString("test"));
}
Y_UNIT_TEST(TestMaxElementBy) {
const int array[] = {1, 2, 5, 3, 4, 5};
UNIT_ASSERT_VALUES_EQUAL(*MaxElementBy(array, [](int x) {
return x * x;
}), 5);
const TVector<int> vec(array, array + Y_ARRAY_SIZE(array));
UNIT_ASSERT_VALUES_EQUAL(*MaxElementBy(vec, [](int x) {
return -1.0 * x;
}), 1);
int arrayMutable[] = {1, 2, 5, 3, 4, 5};
auto maxPtr = MaxElementBy(arrayMutable, [](int x) { return x; });
*maxPtr += 100;
UNIT_ASSERT_VALUES_EQUAL(*maxPtr, 105);
auto identity = [](char x) {
return x;
};
auto singleElementSequence = {'z'};
UNIT_ASSERT_VALUES_EQUAL(*MaxElementBy(singleElementSequence, identity), 'z');
const TString strings[] = {"one", "two", "three", "four"};
UNIT_ASSERT_STRINGS_EQUAL(*MaxElementBy(strings, [](TString s) { return s.size(); }), "three");
}
Y_UNIT_TEST(TestMinElementBy) {
const int array[] = {2, 3, 4, 1, 5};
UNIT_ASSERT_VALUES_EQUAL(*MinElementBy(array, [](int x) -> char {
return 'a' + x;
}), 1);
const TVector<int> vec(std::begin(array), std::end(array));
UNIT_ASSERT_VALUES_EQUAL(*MinElementBy(vec, [](int x) {
return -x;
}), 5);
int arrayMutable[] = {1, 2, 5, 3, 4, 5};
auto minPtr = MinElementBy(arrayMutable, [](int x) { return x; });
*minPtr += 100;
UNIT_ASSERT_VALUES_EQUAL(*minPtr, 101);
auto identity = [](char x) {
return x;
};
auto singleElementSequence = {'z'};
UNIT_ASSERT_VALUES_EQUAL(*MinElementBy(singleElementSequence, identity), 'z');
const TVector<TStringBuf> strings = {"one", "two", "three", "four"};
auto stringLength = [](TStringBuf s) {
return s.size();
};
UNIT_ASSERT_STRINGS_EQUAL(*MinElementBy(strings, stringLength), "one");
UNIT_ASSERT_STRINGS_EQUAL(*MinElementBy(strings.rbegin(), strings.rend(), stringLength), "two");
}
Y_UNIT_TEST(MaxElementByReturnsEndForEmptyRange) {
const TVector<int> empty;
UNIT_ASSERT_EQUAL(MaxElementBy(empty, [](int) { return 0; }), empty.end());
}
Y_UNIT_TEST(MaxElementByDoesntCallFunctorForEmptyRange) {
const TVector<int> empty;
auto functor = [](int) {
UNIT_ASSERT(false);
return 0;
};
MaxElementBy(empty, functor);
}
Y_UNIT_TEST(MinElementByReturnsEndForEmptyRange) {
const TVector<int> empty;
UNIT_ASSERT_EQUAL(MinElementBy(empty, [](int) { return 0; }), empty.end());
}
Y_UNIT_TEST(MinElementByDoesntCallFunctorForEmptyRange) {
const TVector<int> empty;
auto functor = [](int) {
UNIT_ASSERT(false);
return 0;
};
MinElementBy(empty, functor);
}
Y_UNIT_TEST(MinMaxElementMovableKeys) {
const TString strings[] = {"one", "two", "three", "four"};
struct TMoveOnlyKey: TString, TMoveOnly {
using TString::TString;
};
auto keyFn = [](TString s) { return TMoveOnlyKey{std::move(s)}; };
UNIT_ASSERT_STRINGS_EQUAL(*MaxElementBy(strings, keyFn), "two");
UNIT_ASSERT_STRINGS_EQUAL(*MinElementBy(strings, keyFn), "four");
}
Y_UNIT_TEST(TestApplyToMany) {
int res = 0;
ApplyToMany([&res](auto v) { res += v; }, 1, 2, 3, 4, 5);
UNIT_ASSERT_EQUAL(res, 15);
struct TVisitor {
TVisitor(int& acc)
: Acc(acc)
{
}
void operator()(const TString& s) {
Acc += s.size();
}
void operator()(int v) {
Acc += v * 2;
}
int& Acc;
};
TString s{"8-800-555-35-35"};
ApplyToMany(TVisitor{res = 0}, 1, s, 5, s);
UNIT_ASSERT_EQUAL(res, 12 + 2 * static_cast<int>(s.size()));
}
Y_UNIT_TEST(TestTupleForEach) {
ForEach(std::tuple<>{}, [&](auto) { UNIT_ASSERT(false); });
auto t = std::make_tuple(5, 6, 2, 3, 6);
ForEach(t, [](auto& v) { v *= -1; });
UNIT_ASSERT_EQUAL(t, std::make_tuple(-5, -6, -2, -3, -6));
}
Y_UNIT_TEST(TestTupleAllOf) {
UNIT_ASSERT(AllOf(std::tuple<>{}, [](auto) { return false; }));
UNIT_ASSERT(!AllOf(std::make_tuple(1, 2, 0, 4, 5), [&](auto v) { UNIT_ASSERT_LT(v, 3); return 0 != v; }));
UNIT_ASSERT(AllOf(std::make_tuple(1, 2, 3, 4, 5), [](auto v) { return 0 != v; }));
{
auto pred = std::function<bool(int)>([x = TVector<int>(1, 0)](auto v) { return x.front() != v; });
UNIT_ASSERT(AllOf(std::make_tuple(1, 2), pred));
UNIT_ASSERT(AllOf(std::make_tuple(1, 2), pred));
}
{
auto ts = std::make_tuple(TString{"foo"}, TString{"bar"});
auto pred = [](auto s) { return s.size() == 3; };
UNIT_ASSERT_VALUES_EQUAL(AllOf(ts, pred), AllOf(ts, pred));
}
}
Y_UNIT_TEST(TestTupleAnyOf) {
UNIT_ASSERT(!AnyOf(std::tuple<>{}, [](auto) { return true; }));
UNIT_ASSERT(AnyOf(std::make_tuple(0, 1, 2, 3, 4), [&](auto v) { UNIT_ASSERT_LT(v, 2); return 1 == v; }));
UNIT_ASSERT(AnyOf(std::make_tuple(1, 2, 3, 4, 5), [](auto v) { return 5 == v; }));
auto pred = std::function<bool(int)>([x = TVector<int>(1, 0)](auto v) { return x.front() == v; });
UNIT_ASSERT(!AnyOf(std::make_tuple(1, 2), pred));
UNIT_ASSERT(!AnyOf(std::make_tuple(1, 2), pred));
{
auto ts = std::make_tuple(TString{"f"}, TString{"bar"});
auto pred = [](auto s) { return s.size() == 3; };
UNIT_ASSERT_VALUES_EQUAL(AnyOf(ts, pred), AnyOf(ts, pred));
}
}
Y_UNIT_TEST(FindIfForContainer) {
using std::begin;
using std::end;
int array[] = {1, 2, 3, 4, 5};
UNIT_ASSERT_EQUAL(FindIf(array, [](int x) { return x == 1; }), begin(array));
UNIT_ASSERT_EQUAL(FindIf(array, [](int x) { return x > 5; }), end(array));
TVector<int> vector = {1, 2, 3, 4, 5};
UNIT_ASSERT_EQUAL(FindIf(vector, [](int x) { return x == 1; }), begin(vector));
UNIT_ASSERT_EQUAL(FindIf(vector, [](int x) { return x > 5; }), end(vector));
// Compilability test. Check if the returned iterator is non const
auto iter = FindIf(vector, [](int x) { return x == 1; });
*iter = 5;
// Compilability test. Check if the returned iterator is const. Should not compile
const TVector<int> constVector = {1, 2, 3, 4, 5};
auto constIter = FindIf(constVector, [](int x) { return x == 1; });
Y_UNUSED(constIter);
// *constIter = 5;
}
struct TRange {
};
const TRange* begin(const TRange& r) {
return &r;
}
const TRange* end(const TRange& r) {
return &r + 1;
}
Y_UNIT_TEST(FindIfForUserType) {
// Compileability test. Should work for user types with begin/end overloads
TRange range;
auto i = FindIf(range, [](auto) { return false; });
Y_UNUSED(i);
}
Y_UNIT_TEST(TestLowerBoundBy) {
using TIntPairs = TVector<std::pair<i32, i32>>;
auto data = TIntPairs{{1, 5}, {3, 2}, {3, 4}, {8, 0}, {5, 4}};
auto getKey = [](const auto& x) { return x.second; };
StableSortBy(data, getKey);
auto it = LowerBoundBy(data.begin(), data.end(), 4, getKey);
UNIT_ASSERT(it != data.end());
UNIT_ASSERT_EQUAL(it->second, 4);
UNIT_ASSERT_EQUAL(it->first, 3);
UNIT_ASSERT(it > data.begin());
UNIT_ASSERT_EQUAL((it - 1)->second, 2);
UNIT_ASSERT((it + 1) < data.end());
UNIT_ASSERT_EQUAL((it + 1)->second, 4);
}
Y_UNIT_TEST(TestUpperBoundBy) {
using TIntPairs = TVector<std::pair<i32, i32>>;
auto data = TIntPairs{{1, 5}, {3, 2}, {3, 4}, {8, 0}, {5, 4}};
auto getKey = [](const auto& x) { return x.second; };
StableSortBy(data, getKey);
auto it = UpperBoundBy(data.begin(), data.end(), 4, getKey);
UNIT_ASSERT(it != data.end());
UNIT_ASSERT_EQUAL(it->second, 5);
UNIT_ASSERT_EQUAL(it->first, 1);
UNIT_ASSERT(it > data.begin());
UNIT_ASSERT_EQUAL((it - 1)->second, 4);
UNIT_ASSERT((it + 1) == data.end());
}
Y_UNIT_TEST(TestFindInContainer) {
std::vector<int> v = {1, 2, 1000, 15, 100};
UNIT_ASSERT(Find(v, 5) == v.end());
UNIT_ASSERT(Find(v, 1) == v.begin());
UNIT_ASSERT(Find(v, 100) == v.end() - 1);
}
Y_UNIT_TEST(AccumulateWithBinOp) {
std::vector<int> v = {1, 2, 777};
UNIT_ASSERT_VALUES_EQUAL(TString("begin;1;2;777"), Accumulate(v, TString("begin"), [](auto&& a, auto& b) { return a + ";" + ToString(b); }));
}
} // Y_UNIT_TEST_SUITE(TAlgorithm)