diff options
author | mikari <mikari@yandex-team.ru> | 2022-02-10 16:48:47 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:48:47 +0300 |
commit | 2e0ed5ad2d70bf924ccd3cbbfab508784ab36325 (patch) | |
tree | c407f44de8fd4579bf0ceffc822d243ff76cfd26 /library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp | |
parent | ab32245a89d56835833808c7e644b3da277d7085 (diff) | |
download | ydb-2e0ed5ad2d70bf924ccd3cbbfab508784ab36325.tar.gz |
Restoring authorship annotation for <mikari@yandex-team.ru>. Commit 1 of 2.
Diffstat (limited to 'library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp')
-rw-r--r-- | library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp | 142 |
1 files changed, 71 insertions, 71 deletions
diff --git a/library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp b/library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp index c34ed1fd9b..095cf76b47 100644 --- a/library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp +++ b/library/cpp/containers/intrusive_rb_tree/rb_tree_ut.cpp @@ -43,8 +43,8 @@ class TRedBlackTreeTest: public TTestBase { UNIT_TEST(TestFind) UNIT_TEST(TestStress) UNIT_TEST(TestGettingIndexWithDifferentValues) - UNIT_TEST(TestCheckChildrenAfterErase) - UNIT_TEST(TestGettingIndexWithDifferentValuesAfterErase) + UNIT_TEST(TestCheckChildrenAfterErase) + UNIT_TEST(TestGettingIndexWithDifferentValuesAfterErase) UNIT_TEST(TestGettingIndexWithEqualValues) UNIT_TEST(TestLessCountOnEmptyTree) UNIT_TEST_SUITE_END(); @@ -104,77 +104,77 @@ private: } } - inline void TestCheckChildrenAfterErase() { + inline void TestCheckChildrenAfterErase() { TVector<TSimpleSharedPtr<TNode>> nodes; - size_t N = 1000; - - for (size_t i = 0; i < N; ++i) { - nodes.push_back(new TNode(int(i))); - } - - TTree tree; - Shuffle(nodes.begin(), nodes.end()); - - for (size_t i = 0; i < N; ++i) { - tree.Insert(nodes[i].Get()); - } - auto checker = [](const TTree& tree) { - for (auto node = tree.Begin(); node != tree.End(); ++node) { - size_t childrens = 1; - if (node->Left_) { - childrens += node->Left_->Children_; - } - if (node->Right_) { - childrens += node->Right_->Children_; - } - UNIT_ASSERT_VALUES_EQUAL(childrens, node->Children_); - } - }; - - for (auto node : nodes) { - tree.Erase(node.Get()); - checker(tree); - } - } - - inline void TestGettingIndexWithDifferentValuesAfterErase() { + size_t N = 1000; + + for (size_t i = 0; i < N; ++i) { + nodes.push_back(new TNode(int(i))); + } + + TTree tree; + Shuffle(nodes.begin(), nodes.end()); + + for (size_t i = 0; i < N; ++i) { + tree.Insert(nodes[i].Get()); + } + auto checker = [](const TTree& tree) { + for (auto node = tree.Begin(); node != tree.End(); ++node) { + size_t childrens = 1; + if (node->Left_) { + childrens += node->Left_->Children_; + } + if (node->Right_) { + childrens += node->Right_->Children_; + } + UNIT_ASSERT_VALUES_EQUAL(childrens, node->Children_); + } + }; + + for (auto node : nodes) { + tree.Erase(node.Get()); + checker(tree); + } + } + + inline void TestGettingIndexWithDifferentValuesAfterErase() { TVector<TSimpleSharedPtr<TNode>> nodes; - size_t N = 1000; - - for (size_t i = 0; i < N; ++i) { - nodes.push_back(new TNode(int(i))); - } - - TTree tree; - Shuffle(nodes.begin(), nodes.end()); - - for (size_t i = 0; i < N; ++i) { - tree.Insert(nodes[i].Get()); - } - { - size_t index = 0; - for (auto node = tree.Begin(); node != tree.End(); ++node, ++index) { - UNIT_ASSERT_VALUES_EQUAL(tree.GetIndex(&*node), index); - UNIT_ASSERT_VALUES_EQUAL(tree.ByIndex(index)->N, node->N); - UNIT_ASSERT_VALUES_EQUAL(node->N, index); - } - } - - for (size_t i = 1; i < N; i += 2) { - auto* node = tree.Find(i); - UNIT_ASSERT_VALUES_EQUAL(node->N, i); - tree.Erase(node); - } - { - size_t index = 0; - for (auto node = tree.Begin(); node != tree.End(); ++node, ++index) { - UNIT_ASSERT_VALUES_EQUAL(tree.GetIndex(&*node), index); - UNIT_ASSERT_VALUES_EQUAL(tree.ByIndex(index)->N, node->N); - UNIT_ASSERT_VALUES_EQUAL(node->N, 2 * index); - } - } - } - + size_t N = 1000; + + for (size_t i = 0; i < N; ++i) { + nodes.push_back(new TNode(int(i))); + } + + TTree tree; + Shuffle(nodes.begin(), nodes.end()); + + for (size_t i = 0; i < N; ++i) { + tree.Insert(nodes[i].Get()); + } + { + size_t index = 0; + for (auto node = tree.Begin(); node != tree.End(); ++node, ++index) { + UNIT_ASSERT_VALUES_EQUAL(tree.GetIndex(&*node), index); + UNIT_ASSERT_VALUES_EQUAL(tree.ByIndex(index)->N, node->N); + UNIT_ASSERT_VALUES_EQUAL(node->N, index); + } + } + + for (size_t i = 1; i < N; i += 2) { + auto* node = tree.Find(i); + UNIT_ASSERT_VALUES_EQUAL(node->N, i); + tree.Erase(node); + } + { + size_t index = 0; + for (auto node = tree.Begin(); node != tree.End(); ++node, ++index) { + UNIT_ASSERT_VALUES_EQUAL(tree.GetIndex(&*node), index); + UNIT_ASSERT_VALUES_EQUAL(tree.ByIndex(index)->N, node->N); + UNIT_ASSERT_VALUES_EQUAL(node->N, 2 * index); + } + } + } + inline void TestGettingIndexWithEqualValues() { TVector<TSimpleSharedPtr<TNode>> nodes; size_t N = 1000; |