src/xbt/utils/iter/subsets_tests.cpp

   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"
   5
   6 #include <unordered_map>
   7 #include <unordered_set>
   8 #include <vector>
   9
  10 using namespace simgrid::xbt;
  11
  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)
  15 {
  16   unsigned i = 1;
  17   for (unsigned j = 1; j <= p; j++)
  18     i *= x;
  19   return i;
  20 }
  21
  22 TEST_CASE("simgrid::xbt::subsets_iterator: Iteration General Properties")
  23 {
  24   std::vector<int> example_vec{0, 1, 2, 3, 4, 5, 6, 7};
  25
  26   SECTION("Each element of each subset is distinct")
  27   {
  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);
  32
  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);
  39         }
  40       }
  41     }
  42   }
  43 }
  44
  45 TEST_CASE("simgrid::xbt::powerset_iterator: Iteration General Properties")
  46 {
  47   std::vector<int> example_vec{0, 1, 2, 3, 4, 5, 6, 7};
  48
  49   SECTION("Each element of each subset is distinct and appears half of the time in all subsets iteration")
  50   {
  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);
  54
  55     std::unordered_map<int, int> element_counts(k);
  56
  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]++;
  65       }
  66     }
  67
  68     for (const auto& [_, count] : element_counts) {
  69       REQUIRE(count == expected_count);
  70     }
  71   }
  72 }
  73
  74 TEST_CASE("simgrid::xbt::variable_for_loop: Edge Cases")
  75 {
  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};
  79   std::vector<int> outer_loop2{0, 1, 6, 7};
  80   std::vector<int> outer_loop3{1, 2};
  81   std::vector<int> empty_set;
  82
  83   SECTION("Iterations without effect")
  84   {
  85     SECTION("Iteration over no collections")
  86     {
  87       variable_for_loop<std::vector<int>> first;
  88       variable_for_loop<std::vector<int>> last;
  89       REQUIRE(first == last);
  90     }
  91
  92     SECTION("Iteration with an empty collection")
  93     {
  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);
 100     }
 101
 102     SECTION("Iteration with multiple empty collections")
 103     {
 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);
 111     }
 112   }
 113
 114   SECTION("Iteration with effects")
 115   {
 116     SECTION("Iteration over a single collection yields the collection")
 117     {
 118       variable_for_loop<std::vector<int>> first{{outer_loop1}};
 119       variable_for_loop<std::vector<int>> last;
 120
 121       std::vector<int> elements_seen;
 122
 123       for (; first != last; ++first) {
 124         const auto& elements = *first;
 125         REQUIRE(elements.size() == 1);
 126         elements_seen.push_back(*elements[0]);
 127       }
 128
 129       REQUIRE(elements_seen == outer_loop1);
 130     }
 131
 132     SECTION("Iteration over two collections yields all pairs")
 133     {
 134       variable_for_loop<std::vector<int>> first{{outer_loop1, outer_loop2}};
 135       variable_for_loop<std::vector<int>> last;
 136
 137       std::vector<std::pair<int, int>> pairs_seen;
 138       for (; first != last; ++first) {
 139         const auto& elements = *first;
 140         REQUIRE(elements.size() == 2);
 141         pairs_seen.push_back(std::make_pair(*elements[0], *elements[1]));
 142       }
 143
 144       std::vector<std::pair<int, int>> expected_pairs{{0, 0}, {0, 1}, {0, 6}, {0, 7}, {1, 0}, {1, 1}, {1, 6},
 145                                                       {1, 7}, {2, 0}, {2, 1}, {2, 6}, {2, 7}, {3, 0}, {3, 1},
 146                                                       {3, 6}, {3, 7}, {4, 0}, {4, 1}, {4, 6}, {4, 7}};
 147       REQUIRE(pairs_seen == expected_pairs);
 148     }
 149
 150     SECTION("Iteration over three collections yields all triples")
 151     {
 152       variable_for_loop<std::vector<int>> first{{outer_loop3, outer_loop1, outer_loop2}};
 153       variable_for_loop<std::vector<int>> last;
 154
 155       std::vector<std::tuple<int, int, int>> triples_seen;
 156       for (; first != last; ++first) {
 157         const auto& elements = *first;
 158         REQUIRE(elements.size() == 3);
 159         triples_seen.push_back(std::make_tuple(*elements[0], *elements[1], *elements[2]));
 160       }
 161
 162       std::vector<std::tuple<int, int, int>> expected_triples{
 163           {1, 0, 0}, {1, 0, 1}, {1, 0, 6}, {1, 0, 7}, {1, 1, 0}, {1, 1, 1}, {1, 1, 6}, {1, 1, 7}, {1, 2, 0}, {1, 2, 1},
 164           {1, 2, 6}, {1, 2, 7}, {1, 3, 0}, {1, 3, 1}, {1, 3, 6}, {1, 3, 7}, {1, 4, 0}, {1, 4, 1}, {1, 4, 6}, {1, 4, 7},
 165
 166           {2, 0, 0}, {2, 0, 1}, {2, 0, 6}, {2, 0, 7}, {2, 1, 0}, {2, 1, 1}, {2, 1, 6}, {2, 1, 7}, {2, 2, 0}, {2, 2, 1},
 167           {2, 2, 6}, {2, 2, 7}, {2, 3, 0}, {2, 3, 1}, {2, 3, 6}, {2, 3, 7}, {2, 4, 0}, {2, 4, 1}, {2, 4, 6}, {2, 4, 7}};
 168
 169       REQUIRE(triples_seen == expected_triples);
 170     }
 171
 172     SECTION("Iteration over all collections yields all combinations")
 173     {
 174       std::vector<int> outer_loop4{1, 5};
 175       std::vector<int> outer_loop5{1, 8};
 176
 177       variable_for_loop<std::vector<int>> first{
 178           {outer_loop1}, {outer_loop2}, {outer_loop3}, {outer_loop4}, {outer_loop5}};
 179       variable_for_loop<std::vector<int>> last;
 180
 181       size_t total_iterations = 0;
 182       for (; first != last; ++first, ++total_iterations) {
 183         const auto& elements = *first;
 184         REQUIRE(elements.size() == 5);
 185       }
 186       REQUIRE(total_iterations ==
 187               (outer_loop1.size() * outer_loop2.size() * outer_loop3.size() * outer_loop4.size() * outer_loop5.size()));
 188     }
 189   }
 190 }