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