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& iter : element_counts) {
  69       REQUIRE(iter.second == expected_count);
  70     }
  71   }
  72 }
  73
  74 TEST_CASE("simgrid::xbt::variable_for_loop: Edge Cases")
  75 {
  76
  77   SECTION("Iterations without effect")
  78   {
  79     SECTION("Iteration over no collections") {}
  80
  81     SECTION("Iteration with an empty collection") {}
  82   }
  83 }