Add first "implementation" of k-subsets iterator

The higher-order iterator `subsets_iterator`
iterates over all subsets of a given iterator.
Eventually, we'll create the LazyPowerSet and
LazyKSubsets classes which will act as convenience
wrappers around the creation of a k-subset iterator

diff --git a/MANIFEST.in b/MANIFEST.in
index 4b50687..ccae978 100644 (file)
--- a/MANIFEST.in
+++ b/MANIFEST.in
@@ -2519,6 +2519,8 @@ include src/xbt/random_test.cpp
 include src/xbt/snprintf.c
 include src/xbt/string.cpp
 include src/xbt/unit-tests_main.cpp
+include src/xbt/utils/iter/subsets.cpp
+include src/xbt/utils/iter/subsets.hpp
 include src/xbt/xbt_log_appender_file.cpp
 include src/xbt/xbt_log_layout_format.cpp
 include src/xbt/xbt_log_layout_simple.cpp

diff --git a/src/xbt/utils/iter/subsets.cpp b/src/xbt/utils/iter/subsets.cpp
index e69de29..fec2f3f 100644 (file)
--- a/src/xbt/utils/iter/subsets.cpp
+++ b/src/xbt/utils/iter/subsets.cpp
@@ -0,0 +1,8 @@
+#include "src/xbt/utils/iter/subsets.hpp"
+
+#include <algorithm>
+#include <numeric>
+
+namespace simgrid::xbt {
+
+} // namespace simgrid::xbt
\ No newline at end of file

diff --git a/src/xbt/utils/iter/subsets.hpp b/src/xbt/utils/iter/subsets.hpp
index 1e107be..eb8c8ff 100644 (file)
--- a/src/xbt/utils/iter/subsets.hpp
+++ b/src/xbt/utils/iter/subsets.hpp
@@ -5,15 +5,128 @@
 /* This program is free software; you can redistribute it and/or modify it
  * under the terms of the license (GNU LGPL) which comes with this package. */
 
-#ifndef XBT_SUBSETS_HPP
-#define XBT_SUBSETS_HPP
+#ifndef XBT_UTILS_ITER_SUBSETS_HPP
+#define XBT_UTILS_ITER_SUBSETS_HPP
 
 #include <functional>
-#include <unordered_set>
+#include <numeric>
+#include <optional>
 #include <vector>
 
 namespace simgrid::xbt {
 
+// template <class Iterable> struct LazyPowerSet {
+// };
+
+// template <class Iterable> struct LazyKSubsets {
+// private:
+//   const Iterable& universe;
+
+// public:
+//   LazyKSubsets(const Iterable& universe) : universe(universe) {}
+// };
+
+template <class Iterator> struct subsets_iterator {
+
+  subsets_iterator(unsigned k);
+  subsets_iterator(unsigned k, Iterator begin, Iterator end = Iterator());
+
+  subsets_iterator& operator++();
+  auto operator->() const { return &current_subset; }
+  auto& operator*() const { return current_subset; }
+
+  bool operator==(const subsets_iterator<Iterator>& other) const
+  {
+    if (this->k != other.k) {
+      return false;
+    }
+    if (this->k == 0) {
+      return true;
+    }
+    return this->P[0] == other.P[0];
+  }
+  bool operator!=(const subsets_iterator<Iterator>& other) const { return not(this->operator==(other)); }
+
+  using iterator_category = std::forward_iterator_tag;
+  using difference_type   = int; // # of steps between
+  using value_type        = std::vector<Iterator>;
+  using pointer           = value_type*;
+  using reference         = value_type&;
+
+private:
+  unsigned k;
+  std::optional<Iterator> end = std::nullopt;
+  std::vector<Iterator> current_subset;
+  std::vector<unsigned> P;
+};
+
+template <typename Iterator>
+subsets_iterator<Iterator>::subsets_iterator(unsigned k)
+    : k(k), current_subset(std::vector<Iterator>(k)), P(std::vector<unsigned>(k))
+{
+  std::iota(P.begin(), P.end(), k);
+}
+
+template <typename Iterator>
+subsets_iterator<Iterator>::subsets_iterator(unsigned k, Iterator begin, Iterator end)
+    : k(k), end(std::optional<Iterator>{end}), current_subset(std::vector<Iterator>(k)), P(std::vector<unsigned>(k))
+{
+  for (unsigned i = 0; i < k; i++) {
+    // Less than `k` elements to choose
+    if (begin == end) {
+      // We want to initialize the object then to be equivalent
+      // to the end iterator so that there are no items to iterate
+      // over
+      this->end = std::nullopt;
+      std::iota(P.begin(), P.end(), k);
+      return;
+    }
+    current_subset[i] = begin++;
+  }
+  std::iota(P.begin(), P.end(), 0);
+}
+
+template <typename Iterator> subsets_iterator<Iterator>& subsets_iterator<Iterator>::operator++()
+{
+  if (end == std::nullopt || k == 0) {
+    return *this;
+  }
+
+  // Move the last element over each time
+  ++current_subset[k - 1];
+  ++P[k - 1];
+
+  const auto end                  = this->end.value();
+  const bool shift_other_elements = current_subset[k - 1] == end;
+
+  if (shift_other_elements) {
+    // The number of elements is now equal to the "index"
+    // of the last element (it is at the end, which means we added
+    // for the finalth time)
+    const unsigned n = P[k - 1];
+
+    auto l = 0;
+    for (int j = static_cast<int>(k - 2); j >= 0; j--) {
+      if (P[j] != (n - (k - j))) {
+        l = j;
+        break;
+      }
+    }
+
+    P[l] += 1;
+
+    if (l == 0 and P[0] > (n - k)) {
+      return *this;
+    }
+
+    for (auto i = l + 1; i <= (k - 1); i++) {
+      P[i] = P[l] + (i - l);
+    }
+  }
+
+  return *this;
+}
+
 } // namespace simgrid::xbt
 
 #endif

diff --git a/tools/cmake/DefinePackages.cmake b/tools/cmake/DefinePackages.cmake
index 6fb642c..0c00fee 100644 (file)
--- a/tools/cmake/DefinePackages.cmake
+++ b/tools/cmake/DefinePackages.cmake
@@ -274,6 +274,7 @@ set(XBT_SRC
   src/xbt/random.cpp
   src/xbt/snprintf.c
   src/xbt/string.cpp
+  src/xbt/utils/iter/subsets.cpp
   src/xbt/xbt_log_appender_file.cpp
   src/xbt/xbt_log_layout_format.cpp
   src/xbt/xbt_log_layout_simple.cpp