X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/5f4fec5323389b31285cd4e19a6abda90e63a555..b7f1c354386134784f90d96dab71b2b5a3f45c23:/src/mc/explo/udpor/maximal_subsets_iterator.hpp

diff --git a/src/mc/explo/udpor/maximal_subsets_iterator.hpp b/src/mc/explo/udpor/maximal_subsets_iterator.hpp
index 79eabb7141..2be3497aea 100644
--- a/src/mc/explo/udpor/maximal_subsets_iterator.hpp
+++ b/src/mc/explo/udpor/maximal_subsets_iterator.hpp
@@ -7,8 +7,10 @@
 #define SIMGRID_MC_UDPOR_MAXIMAL_SUBSETS_ITERATOR_HPP
 
 #include "src/mc/explo/udpor/Configuration.hpp"
+#include "src/xbt/utils/iter/iterator_wrapping.hpp"
 
 #include <boost/iterator/iterator_facade.hpp>
+#include <functional>
 #include <optional>
 #include <stack>
 #include <unordered_map>
@@ -16,11 +18,12 @@
 namespace simgrid::mc::udpor {
 
 /**
- * @brief An iterator over the tree of sets of maximal events that
- * can be generated from a given configuration
+ * @brief An iterator over the tree of sets of (non-empty) maximal events that
+ * can be generated from a given set of events
  *
  * This iterator traverses all possible sets of maximal events that
- * can be formed from a configuration, each of which satisfy a predicate.
+ * can be formed from some subset of events of an unfolding,
+ * each of which satisfy a predicate.
  *
  * Iteration over the maximal events of a configuration is an important
  * step in computing the extension set of a configuration for an action
@@ -32,38 +35,29 @@ struct maximal_subsets_iterator
 public:
   // A function which answers the question "do I need to consider maximal sets
   // that contain this node?"
-  using node_filter_function = std::function<bool(const UnfoldingEvent*)>;
+  using node_filter_function       = std::function<bool(const UnfoldingEvent*)>;
+  using topological_order_position = std::vector<const UnfoldingEvent*>::const_iterator;
 
-  maximal_subsets_iterator();
-  maximal_subsets_iterator(const Configuration& config)
-      : maximal_subsets_iterator(
-            config, [](const UnfoldingEvent*) constexpr { return true; })
-  {
-  }
+  maximal_subsets_iterator() = default;
+  explicit maximal_subsets_iterator(const Configuration& config) : maximal_subsets_iterator(config.get_events()) {}
+  explicit maximal_subsets_iterator(const EventSet& events) : maximal_subsets_iterator(events, std::nullopt) {}
 
-  maximal_subsets_iterator(const Configuration& config, node_filter_function filter)
-      : config({config})
-      , topological_ordering(config.get_topologically_sorted_events_of_reverse_graph())
-      , filter(filter)
+  maximal_subsets_iterator(const Configuration& config, std::optional<node_filter_function> filter)
+      : maximal_subsets_iterator(config.get_events(), filter)
   {
-    // The idea here is that initially, no work has been done; but we want
-    // it to be the case that the iterator points at the very first
-    // element in the list. Effectively, we want to take the first step
-    if (not topological_ordering.empty()) {
-      auto earliest_element_iter = topological_ordering.begin();
-      // add_element_to_current_maximal_set(*earliest_element_iter);
-      backtrack_points.push(earliest_element_iter);
-    }
   }
+  maximal_subsets_iterator(const EventSet& events, std::optional<node_filter_function> filter);
 
 private:
-  using topological_order_position = std::vector<const UnfoldingEvent*>::const_iterator;
-  const std::optional<std::reference_wrapper<const Configuration>> config;
-  const std::vector<const UnfoldingEvent*> topological_ordering;
-  const std::optional<node_filter_function> filter;
+  std::vector<const UnfoldingEvent*> topological_ordering;
 
-  EventSet current_maximal_set = EventSet();
-  std::stack<topological_order_position> backtrack_points;
+  // The boolean is a bit of an annoyance, but it works. Effectively,
+  // there's no way to distinguish between "we're starting the search
+  // after the empty set" and "we've finished the search" since the resulting
+  // maximal set and backtracking point stack will both be empty in both cases
+  bool has_started_searching                              = false;
+  std::optional<EventSet> current_maximal_set             = std::nullopt;
+  std::stack<topological_order_position> backtrack_points = std::stack<topological_order_position>();
 
   /**
    * @brief A small class which provides functionality for managing
@@ -76,30 +70,78 @@ private:
    * its `current_maximal_set`)
    */
   struct bookkeeper {
-  private:
+  public:
     using topological_order_position = maximal_subsets_iterator::topological_order_position;
-    std::unordered_map<const UnfoldingEvent*, unsigned> event_counts;
 
-    bool is_candidate_event(const UnfoldingEvent*) const;
-
-  public:
     void mark_included_in_maximal_set(const UnfoldingEvent*);
     void mark_removed_from_maximal_set(const UnfoldingEvent*);
+    topological_order_position find_next_candidate_event(topological_order_position first,
+                                                         topological_order_position last) const;
 
-    topological_order_position find_next_event(topological_order_position first, topological_order_position last) const;
+  private:
+    std::unordered_map<const UnfoldingEvent*, unsigned> event_counts;
+
+    /// @brief Whether or not the given event, according to the
+    /// bookkeeping that has been done thus far, can be added to the
+    /// current candidate maximal set
+    bool is_candidate_event(const UnfoldingEvent*) const;
   } bookkeeper;
 
   void add_element_to_current_maximal_set(const UnfoldingEvent*);
   void remove_element_from_current_maximal_set(const UnfoldingEvent*);
 
+  /**
+   * @brief Moves to the next node in the topological ordering
+   * by continuing the search in the tree of maximal event sets
+   * from where we currently believe we are in the tree
+   *
+   * At each stage of the iteration, the iterator points to
+   * a maximal event set that can be thought of as `R` + `A`:
+   *
+   * |   R    | A
+   * +--------+
+   *
+   * where `R` is some set of events and `A` is another event.
+   *
+   * The iterator first tries expansion from `R` + `A`. If it finds
+   * node `B` to expand, this means that there is a node in the tree of
+   * maximal event sets of `C` (the configuration traversed) such that
+   * `R` + `A` + `B` needs to be checked.
+   *
+   * If no such node is found, then the iterator must check `R` +
+   * some other node AFTER `A`. The new set of possibilities potentially
+   * includes some of `A`'s dependencies, so their counts are decremented
+   * prior to searching.
+   *
+   * @note: This method is a mutating method: it manipulates the
+   * iterator such that the iterator refers to the next maximal
+   * set sans the element returned. The `increment()` function performs
+   * the rest of the work needed to actually complete the transition
+   *
+   * @returns an iterator poiting to the event that should next
+   * be added to the set of maximal events if such an event exists,
+   * or to the end of the topological ordering if no such event exists
+   */
+  topological_order_position continue_traversal_of_maximal_events_tree();
+
   // boost::iterator_facade<...> interface to implement
   void increment();
   bool equal(const maximal_subsets_iterator& other) const { return current_maximal_set == other.current_maximal_set; }
-  const EventSet& dereference() const { return current_maximal_set; }
+  const EventSet& dereference() const
+  {
+    static const EventSet empty_set = EventSet();
+    if (current_maximal_set.has_value()) {
+      return current_maximal_set.value();
+    }
+    return empty_set;
+  }
 
   // Allows boost::iterator_facade<...> to function properly
   friend class boost::iterator_core_access;
 };
 
+using maximal_subsets_iterator_wrapper =
+    simgrid::xbt::iterator_wrapping<maximal_subsets_iterator, const Configuration&>;
+
 } // namespace simgrid::mc::udpor
 #endif