Add tests for LazyKSubsets and LazyPowerset

The LazyKSubsets and LazyPowerset are simply
wrappers around an iterator type which can
enumerate all subsets of a given iteration.

While this won't be used anymore to enumerate
all possible sets of events of the configuration
in the compatibility graph, which will soon be
removed, it will still be used (or a variant
thereof) when computing K-partial alternatives
later on

diff --git a/src/xbt/utils/iter/LazyKSubsets.hpp b/src/xbt/utils/iter/LazyKSubsets.hpp
index 0164e0d..e9773d1 100644 (file)
--- a/src/xbt/utils/iter/LazyKSubsets.hpp
+++ b/src/xbt/utils/iter/LazyKSubsets.hpp
@@ -10,7 +10,7 @@
 
 namespace simgrid::xbt {
 
-template <class Iterable> class LazyKSubsets<Iterable>;
+template <class Iterable> class LazyKSubsets;
 template <class Iterable> LazyKSubsets<Iterable> make_k_subsets_iter(unsigned k, const Iterable& container);
 
 /**
@@ -27,14 +27,19 @@ template <class Iterable> LazyKSubsets<Iterable> make_k_subsets_iter(unsigned k,
  */
 template <class Iterable> class LazyKSubsets final {
 public:
-  auto begin() const { return subsets_iterator<Iterable::iterator>(k, iterable.begin(), iterable.end()); }
-  auto end() const { return subsets_iterator<Iterable::iterator>(k); }
+  auto begin() const
+  {
+    return subsets_iterator<typename Iterable::const_iterator>(k, iterable.begin(), iterable.end());
+  }
+  auto end() const { return subsets_iterator<typename Iterable::const_iterator>(k); }
 
 private:
   const unsigned k;
   const Iterable& iterable;
   LazyKSubsets(unsigned k, const Iterable& iterable) : k(k), iterable(iterable) {}
-  friend LazyKSubsets<Iterable> make_k_subsets_iter(unsigned k, const Iterable& iterable);
+
+  template <class IterableType>
+  friend LazyKSubsets<IterableType> make_k_subsets_iter(unsigned k, const IterableType& iterable);
 };
 
 template <class Iterable> LazyKSubsets<Iterable> make_k_subsets_iter(unsigned k, const Iterable& container)

diff --git a/src/xbt/utils/iter/LazyPowerset.hpp b/src/xbt/utils/iter/LazyPowerset.hpp
index cb74844..76d3483 100644 (file)
--- a/src/xbt/utils/iter/LazyPowerset.hpp
+++ b/src/xbt/utils/iter/LazyPowerset.hpp
@@ -10,7 +10,7 @@
 
 namespace simgrid::xbt {
 
-template <class Iterable> class LazyPowerset<Iterable>;
+template <class Iterable> class LazyPowerset;
 template <class Iterable> LazyPowerset<Iterable> make_powerset_iter(const Iterable& container);
 
 /**
@@ -27,13 +27,13 @@ template <class Iterable> LazyPowerset<Iterable> make_powerset_iter(const Iterab
  */
 template <class Iterable> class LazyPowerset final {
 public:
-  auto begin() const { return powerset_iterator<Iterable::iterator>(iterable.begin(), iterable.end()); }
-  auto end() const { return powerset_iterator<Iterable::iterator>(); }
+  auto begin() const { return powerset_iterator<typename Iterable::const_iterator>(iterable.begin(), iterable.end()); }
+  auto end() const { return powerset_iterator<typename Iterable::const_iterator>(); }
 
 private:
   const Iterable& iterable;
   LazyPowerset(const Iterable& iterable) : iterable(iterable) {}
-  friend LazyPowerset<Iterable> make_powerset_iter(const Iterable& iterable);
+  template <class IterableType> friend LazyPowerset<IterableType> make_powerset_iter(const IterableType& iterable);
 };
 
 template <class Iterable> LazyPowerset<Iterable> make_powerset_iter(const Iterable& container)

diff --git a/src/xbt/utils/iter/subsets_tests.cpp b/src/xbt/utils/iter/subsets_tests.cpp
new file mode 100644 (file)
index 0000000..2db7f18
--- /dev/null
+++ b/src/xbt/utils/iter/subsets_tests.cpp
@@ -0,0 +1,71 @@
+#include "src/3rd-party/catch.hpp"
+#include "src/xbt/utils/iter/LazyKSubsets.hpp"
+#include "src/xbt/utils/iter/LazyPowerset.hpp"
+
+#include <unordered_map>
+#include <unordered_set>
+#include <vector>
+
+using namespace simgrid::xbt;
+
+// This is used in a number of tests below
+// to verify that counts of elements for example.
+static unsigned integer_power(unsigned x, unsigned p)
+{
+  unsigned i = 1;
+  for (unsigned j = 1; j <= p; j++)
+    i *= x;
+  return i;
+}
+
+TEST_CASE("simgrid::xbt::subsets_iterator: Iteration General Properties")
+{
+  std::vector<int> example_vec{0, 1, 2, 3, 4, 5, 6, 7};
+
+  SECTION("Each element of each subset is distinct and appears half of the time")
+  {
+    for (unsigned k = 0; static_cast<size_t>(k) < example_vec.size(); k++) {
+      for (auto& subset : make_k_subsets_iter(k, example_vec)) {
+        // Each subset must have size `k`
+        REQUIRE(subset.size() == k);
+
+        // Each subset must be comprised only of distinct elements
+        std::unordered_set<int> elements_seen(k);
+        for (const auto& element_ptr : subset) {
+          const auto& element = *element_ptr;
+          REQUIRE(elements_seen.find(element) == elements_seen.end());
+          elements_seen.insert(element);
+        }
+      }
+    }
+  }
+}
+
+TEST_CASE("simgrid::xbt::powerset_iterator: Iteration General Properties")
+{
+  std::vector<int> example_vec{0, 1, 2, 3, 4, 5, 6, 7};
+
+  SECTION("Each element of each subset is distinct and appears half of the time in all subsets iteration")
+  {
+    // Each element is expected to be found in half of the sets
+    const unsigned k         = static_cast<unsigned>(example_vec.size());
+    const int expected_count = integer_power(2, k - 1);
+
+    std::unordered_map<int, int> element_counts(k);
+
+    for (auto& subset : make_powerset_iter(example_vec)) {
+      // Each subset must be comprised only of distinct elements
+      std::unordered_set<int> elements_seen(k);
+      for (const auto& element_ptr : subset) {
+        const auto& element = *element_ptr;
+        REQUIRE(elements_seen.find(element) == elements_seen.end());
+        elements_seen.insert(element);
+        element_counts[element]++;
+      }
+    }
+
+    for (const auto& iter : element_counts) {
+      REQUIRE(iter.second == expected_count);
+    }
+  }
+}
\ No newline at end of file

diff --git a/tools/cmake/Tests.cmake b/tools/cmake/Tests.cmake
index ba1e45f..ce7d830 100644 (file)
--- a/tools/cmake/Tests.cmake
+++ b/tools/cmake/Tests.cmake
@@ -126,6 +126,7 @@ set(UNIT_TESTS  src/xbt/unit-tests_main.cpp
                 src/xbt/dynar_test.cpp
                 src/xbt/random_test.cpp
                 src/xbt/xbt_str_test.cpp
+                src/xbt/utils/iter/subsets_tests.cpp
                 src/kernel/lmm/maxmin_test.cpp)
 
 set(MC_UNIT_TESTS src/mc/sosp/Snapshot_test.cpp