1 #include "src/3rd-party/catch.hpp"
2 #include "src/xbt/utils/iter/LazyKSubsets.hpp"
3 #include "src/xbt/utils/iter/LazyPowerset.hpp"
4 #include "src/xbt/utils/iter/variable_for_loop.hpp"
6 #include <unordered_map>
7 #include <unordered_set>
10 using namespace simgrid::xbt;
12 // This is used in a number of tests below
13 // to verify that counts of elements for example.
14 static unsigned integer_power(unsigned x, unsigned p)
17 for (unsigned j = 1; j <= p; j++)
22 TEST_CASE("simgrid::xbt::subsets_iterator: Iteration General Properties")
24 std::vector<int> example_vec{0, 1, 2, 3, 4, 5, 6, 7};
26 SECTION("Each element of each subset is distinct")
28 for (unsigned k = 0; static_cast<size_t>(k) < example_vec.size(); k++) {
29 for (auto& subset : make_k_subsets_iter(k, example_vec)) {
30 // Each subset must have size `k`
31 REQUIRE(subset.size() == k);
33 // Each subset must be comprised only of distinct elements
34 std::unordered_set<int> elements_seen(k);
35 for (const auto& element_ptr : subset) {
36 const auto& element = *element_ptr;
37 REQUIRE(elements_seen.find(element) == elements_seen.end());
38 elements_seen.insert(element);
45 TEST_CASE("simgrid::xbt::powerset_iterator: Iteration General Properties")
47 std::vector<int> example_vec{0, 1, 2, 3, 4, 5, 6, 7};
49 SECTION("Each element of each subset is distinct and appears half of the time in all subsets iteration")
51 // Each element is expected to be found in half of the sets
52 const unsigned k = static_cast<unsigned>(example_vec.size());
53 const int expected_count = integer_power(2, k - 1);
55 std::unordered_map<int, int> element_counts(k);
57 for (auto& subset : make_powerset_iter(example_vec)) {
58 // Each subset must be comprised only of distinct elements
59 std::unordered_set<int> elements_seen(k);
60 for (const auto& element_ptr : subset) {
61 const auto& element = *element_ptr;
62 REQUIRE(elements_seen.find(element) == elements_seen.end());
63 elements_seen.insert(element);
64 element_counts[element]++;
68 for (const auto& iter : element_counts) {
69 REQUIRE(iter.second == expected_count);
74 TEST_CASE("simgrid::xbt::variable_for_loop: Edge Cases")
76 // Note the extra `{}` in the tests. This constructs a
77 // `std::reference_wrapper` to the specified collection
78 std::vector<int> outer_loop1{0, 1, 2, 3, 4, 5, 6, 7};
79 std::vector<int> outer_loop2{0, 1, 6, 7};
80 std::vector<int> outer_loop3{0};
81 std::vector<int> empty_set;
83 SECTION("Iterations without effect")
85 SECTION("Iteration over no collections")
87 variable_for_loop<std::vector<int>> first;
88 variable_for_loop<std::vector<int>> last;
89 REQUIRE(first == last);
92 SECTION("Iteration with an empty collection")
94 variable_for_loop<std::vector<int>> last;
95 REQUIRE(variable_for_loop<std::vector<int>>{{empty_set}} == last);
96 REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop1}, {empty_set}} == last);
97 REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop1}, {outer_loop2}, {empty_set}} == last);
98 REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop1}, {outer_loop2}, {outer_loop3}, {empty_set}} == last);
99 REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop3}, {empty_set}} == last);
102 SECTION("Iteration with multiple empty collections")
104 variable_for_loop<std::vector<int>> last;
105 REQUIRE(variable_for_loop<std::vector<int>>{{empty_set}} == last);
106 REQUIRE(variable_for_loop<std::vector<int>>{{empty_set}, {empty_set}} == last);
107 REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop1}, {outer_loop2}, {empty_set}} == last);
108 REQUIRE(variable_for_loop<std::vector<int>>{{outer_loop1}, {outer_loop2}, {empty_set}, {empty_set}} == last);
109 REQUIRE(variable_for_loop<std::vector<int>>{
110 {outer_loop1}, {outer_loop2}, {outer_loop3}, {empty_set}, {empty_set}} == last);
114 SECTION("Iteration with effects")
116 SECTION("Iteration over a single collection yields the collection")
118 variable_for_loop<std::vector<int>> first{{outer_loop1}};
119 variable_for_loop<std::vector<int>> last;
121 std::vector<int> elements_seen;
123 for (; first != last; ++first) {
124 const auto& elements = *first;
125 REQUIRE(elements.size() == 1);
126 elements_seen.push_back(*elements[0]);
129 REQUIRE(elements_seen == outer_loop1);