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
   5 #include <unordered_map>
   6 #include <unordered_set>
   7 #include <vector>
   8
   9 using namespace simgrid::xbt;
  10
  11 // This is used in a number of tests below
  12 // to verify that counts of elements for example.
  13 static unsigned integer_power(unsigned x, unsigned p)
  14 {
  15   unsigned i = 1;
  16   for (unsigned j = 1; j <= p; j++)
  17     i *= x;
  18   return i;
  19 }
  20
  21 TEST_CASE("simgrid::xbt::subsets_iterator: Iteration General Properties")
  22 {
  23   std::vector<int> example_vec{0, 1, 2, 3, 4, 5, 6, 7};
  24
  25   SECTION("Each element of each subset is distinct and appears half of the time")
  26   {
  27     for (unsigned k = 0; static_cast<size_t>(k) < example_vec.size(); k++) {
  28       for (auto& subset : make_k_subsets_iter(k, example_vec)) {
  29         // Each subset must have size `k`
  30         REQUIRE(subset.size() == k);
  31
  32         // Each subset must be comprised only of distinct elements
  33         std::unordered_set<int> elements_seen(k);
  34         for (const auto& element_ptr : subset) {
  35           const auto& element = *element_ptr;
  36           REQUIRE(elements_seen.find(element) == elements_seen.end());
  37           elements_seen.insert(element);
  38         }
  39       }
  40     }
  41   }
  42 }
  43
  44 TEST_CASE("simgrid::xbt::powerset_iterator: Iteration General Properties")
  45 {
  46   std::vector<int> example_vec{0, 1, 2, 3, 4, 5, 6, 7};
  47
  48   SECTION("Each element of each subset is distinct and appears half of the time in all subsets iteration")
  49   {
  50     // Each element is expected to be found in half of the sets
  51     const unsigned k         = static_cast<unsigned>(example_vec.size());
  52     const int expected_count = integer_power(2, k - 1);
  53
  54     std::unordered_map<int, int> element_counts(k);
  55
  56     for (auto& subset : make_powerset_iter(example_vec)) {
  57       // Each subset must be comprised only of distinct elements
  58       std::unordered_set<int> elements_seen(k);
  59       for (const auto& element_ptr : subset) {
  60         const auto& element = *element_ptr;
  61         REQUIRE(elements_seen.find(element) == elements_seen.end());
  62         elements_seen.insert(element);
  63         element_counts[element]++;
  64       }
  65     }
  66
  67     for (const auto& iter : element_counts) {
  68       REQUIRE(iter.second == expected_count);
  69     }
  70   }
  71 }