Index: uspace/lib/cpp/Makefile =================================================================== --- uspace/lib/cpp/Makefile (revision 21d97e85380f9ea131a025873e8863f6b9d26060) +++ uspace/lib/cpp/Makefile (revision 0fe0f32dfb8722a4a927b01b9204f35063ec3d4c) @@ -59,4 +59,5 @@ src/internal/test/deque.cpp \ src/internal/test/map.cpp \ + src/internal/test/set.cpp \ src/internal/test/string.cpp \ src/internal/test/test.cpp \ Index: uspace/lib/cpp/include/internal/test/tests.hpp =================================================================== --- uspace/lib/cpp/include/internal/test/tests.hpp (revision 21d97e85380f9ea131a025873e8863f6b9d26060) +++ uspace/lib/cpp/include/internal/test/tests.hpp (revision 0fe0f32dfb8722a4a927b01b9204f35063ec3d4c) @@ -180,4 +180,19 @@ void test_multi_bounds_and_ranges(); }; + + class set_test: public test_suite + { + public: + bool run(bool) override; + const char* name() override; + + private: + void test_constructors_and_assignment(); + void test_emplace_insert(); + void test_bounds_and_ranges(); + void test_multi(); + void test_reverse_iterators(); + void test_multi_bounds_and_ranges(); + }; } Index: uspace/lib/cpp/src/internal/test/set.cpp =================================================================== --- uspace/lib/cpp/src/internal/test/set.cpp (revision 0fe0f32dfb8722a4a927b01b9204f35063ec3d4c) +++ uspace/lib/cpp/src/internal/test/set.cpp (revision 0fe0f32dfb8722a4a927b01b9204f35063ec3d4c) @@ -0,0 +1,301 @@ +/* + * Copyright (c) 2018 Jaroslav Jindrak + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include +#include +#include +#include +#include + +namespace std::test +{ + bool set_test::run(bool report) + { + report_ = report; + start(); + + test_constructors_and_assignment(); + test_emplace_insert(); + test_bounds_and_ranges(); + test_multi(); + test_reverse_iterators(); + test_multi_bounds_and_ranges(); + + return end(); + } + + const char* set_test::name() + { + return "set"; + } + + void set_test::test_constructors_and_assignment() + { + auto check1 = {1, 2, 3, 4, 5, 6, 7}; + auto src1 = {3, 1, 5, 2, 7, 6, 4}; + + std::set s1{src1}; + test_eq( + "initializer list initialization", + check1.begin(), check1.end(), + s1.begin(), s1.end() + ); + test_eq("size", s1.size(), 7U); + + std::set s2{src1.begin(), src1.end()}; + test_eq( + "iterator range initialization", + check1.begin(), check1.end(), + s2.begin(), s2.end() + ); + + std::set s3{s1}; + test_eq( + "copy initialization", + check1.begin(), check1.end(), + s3.begin(), s3.end() + ); + + std::set s4{std::move(s1)}; + test_eq( + "move initialization", + check1.begin(), check1.end(), + s4.begin(), s4.end() + ); + test_eq("move initialization - origin empty", s1.size(), 0U); + test_eq("empty", s1.empty(), true); + + s1 = s4; + test_eq( + "copy assignment", + check1.begin(), check1.end(), + s1.begin(), s1.end() + ); + + s4 = std::move(s1); + test_eq( + "move assignment", + check1.begin(), check1.end(), + s4.begin(), s4.end() + ); + test_eq("move assignment - origin empty", s1.size(), 0U); + + s1 = src1; + test_eq( + "initializer list assignment", + check1.begin(), check1.end(), + s1.begin(), s1.end() + ); + } + + void set_test::test_emplace_insert() + { + std::set set1{}; + + auto res1 = set1.emplace(1); + test_eq("first emplace succession", res1.second, true); + test_eq("first emplace equivalence", *res1.first, 1); + + auto res2 = set1.emplace(1); + test_eq("second emplace failure", res2.second, false); + test_eq("second emplace equivalence", *res2.first, 1); + + auto res3 = set1.emplace_hint(set1.begin(), 2); + test_eq("first emplace_hint succession", (res3 != set1.end()), true); + test_eq("first emplace_hint equivalence", *res3, 2); + + auto res4 = set1.emplace_hint(set1.begin(), 2); + test_eq("second emplace_hint failure", (res4 != set1.end()), true); + test_eq("second emplace_hint equivalence", *res4, 2); + + std::set set2{}; + auto res5 = set2.insert("A"); + test_eq("conversion insert succession", res5.second, true); + test_eq("conversion insert equivalence", *res5.first, std::string{"A"}); + + auto res6 = set2.insert(std::string{"B"}); + test_eq("first insert succession", res6.second, true); + test_eq("first insert equivalence", *res6.first, std::string{"B"}); + + auto res7 = set2.insert(std::string{"B"}); + test_eq("second insert failure", res7.second, false); + test_eq("second insert equivalence", *res7.first, std::string{"B"}); + + auto res10 = set1.erase(set1.find(2)); + test_eq("erase", set1.find(2), set1.end()); + test_eq("highest erased", res10, set1.end()); + + set2.insert(std::string{"G"}); + set2.insert(std::string{"H"}); + set2.insert(std::string{"K"}); + auto res11 = set2.erase(std::string{"G"}); + test_eq("erase by key pt1", res11, 1U); + auto res12 = set2.erase(std::string{"M"}); + test_eq("erase by key pt2", res12, 0U); + + std::set set3{}; + set3.insert(1); + auto res13 = set3.erase(1); + test_eq("erase root by key pt1", res13, 1U); + test_eq("erase root by key pt2", set3.empty(), true); + + set3.insert(3); + auto res14 = set3.erase(set3.begin()); + test_eq("erase root by iterator pt1", res14, set3.end()); + test_eq("erase root by iterator pt2", set3.empty(), true); + + set2.clear(); + test_eq("clear", set2.empty(), true); + + set3.insert(1); + auto res15 = set3.count(1); + test_eq("count", res15, 1U); + } + + void set_test::test_bounds_and_ranges() + { + std::set set{}; + for (int i = 0; i < 10; ++i) + set.insert(i); + for (int i = 15; i < 20; ++i) + set.insert(i); + + auto res1 = set.lower_bound(5); + test_eq("lower_bound of present key", *res1, 5); + + auto res2 = set.lower_bound(13); + test_eq("lower_bound of absent key", *res2, 9); + + auto res3 = set.upper_bound(7); + test_eq("upper_bound of present key", *res3, 8); + + auto res4 = set.upper_bound(12); + test_eq("upper_bound of absent key", *res4, 15); + + auto res5 = set.equal_range(4); + test_eq("equal_range of present key pt1", *res5.first, 4); + test_eq("equal_range of present key pt2", *res5.second, 5); + + auto res6 = set.equal_range(14); + test_eq("equal_range of absent key pt1", *res6.first, 9); + test_eq("equal_range of absent key pt2", *res6.second, 15); + } + + void set_test::test_multi() + { + auto check1 = {1, 2, 3, 3, 4, 5, 6, 6, 6, 7}; + auto src1 = {3, 6, 1, 5, 6, 3, 2, 7, 6, 4}; + + std::multiset mset{src1}; + test_eq( + "multi construction", + check1.begin(), check1.end(), + mset.begin(), mset.end() + ); + + auto res1 = mset.count(6); + test_eq("multi count", res1, 3U); + + auto res2 = mset.emplace(7); + test_eq("multi duplicit emplace pt1", *res2, 7); + test_eq("multi duplicit emplace pt2", mset.count(7), 2U); + + auto res3 = mset.emplace(8); + test_eq("multi unique emplace pt1", *res3, 8); + test_eq("multi unique emplace pt2", mset.count(8), 1U); + + auto res4 = mset.insert(8); + test_eq("multi duplicit insert pt1", *res4, 8); + test_eq("multi duplicit insert pt2", mset.count(8), 2U); + + auto res5 = mset.insert(9); + test_eq("multi unique insert pt1", *res5, 9); + test_eq("multi unique insert pt2", mset.count(9), 1U); + + auto res6 = mset.erase(8); + test_eq("multi erase by key pt1", res6, 2U); + test_eq("multi erase by key pt2", mset.count(8), 0U); + + auto res7 = mset.erase(mset.find(7)); + test_eq("multi erase by iterator pt1", *res7, 7); + test_eq("multi erase by iterator pt2", mset.count(7), 1U); + } + + void set_test::test_reverse_iterators() + { + auto check1 = {7, 6, 6, 6, 5, 4, 3, 3, 2, 1}; + auto src1 = {3, 6, 1, 5, 6, 3, 2, 7, 6, 4}; + + std::multiset mset{src1}; + test_eq( + "multi reverse iterators", + check1.begin(), check1.end(), + mset.rbegin(), mset.rend() + ); + + auto check2 = {7, 6, 5, 4, 3, 2, 1}; + auto src2 = {3, 1, 5, 2, 7, 6, 4}; + + std::set set{src2}; + test_eq( + "reverse iterators", + check2.begin(), check2.end(), + set.rbegin(), set.rend() + ); + } + + void set_test::test_multi_bounds_and_ranges() + { + auto check1 = {1, 1}; + auto check2 = {5, 5, 5}; + auto check3 = {6}; + auto src = {1, 1, 2, 3, 5, 5, 5, 6}; + + std::multiset mset{src}; + auto res1 = mset.equal_range(1); + test_eq( + "multi equal_range at the start", + check1.begin(), check1.end(), + res1.first, res1.second + ); + + auto res2 = mset.equal_range(5); + test_eq( + "multi equal_range in the middle", + check2.begin(), check2.end(), + res2.first, res2.second + ); + + auto res3 = mset.equal_range(6); + test_eq( + "multi equal_range at the end + single element range", + check3.begin(), check3.end(), + res3.first, res3.second + ); + } +}