X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/d1b1a66acfcfa7948b3eaca81154e438f93c5578..6bc04475b4308e91e18d869a5fb665bc35b48508:/src/mc/explo/udpor/History.hpp

diff --git a/src/mc/explo/udpor/History.hpp b/src/mc/explo/udpor/History.hpp
index df5cb32b17..dc17c27e58 100644
--- a/src/mc/explo/udpor/History.hpp
+++ b/src/mc/explo/udpor/History.hpp
@@ -6,9 +6,15 @@
 #ifndef SIMGRID_MC_UDPOR_HISTORY_HPP
 #define SIMGRID_MC_UDPOR_HISTORY_HPP
 
+#include "src/mc/explo/udpor/Configuration.hpp"
 #include "src/mc/explo/udpor/EventSet.hpp"
 #include "src/mc/explo/udpor/udpor_forward.hpp"
 
+#include <boost/iterator/iterator_facade.hpp>
+#include <functional>
+#include <initializer_list>
+#include <optional>
+
 namespace simgrid::mc::udpor {
 
 /**
@@ -45,13 +51,16 @@ private:
   EventSet events_;
 
 public:
-  History()                          = default;
   History(const History&)            = default;
   History& operator=(History const&) = default;
   History(History&&)                 = default;
 
-  explicit History(UnfoldingEvent* e) : events_({e}) {}
-  explicit History(EventSet event_set) : events_(std::move(event_set)) {}
+  explicit History(const UnfoldingEvent* e) : events_({e}) {}
+  explicit History(EventSet event_set = EventSet()) : events_(std::move(event_set)) {}
+  explicit History(std::initializer_list<const UnfoldingEvent*> list) : events_(std::move(list)) {}
+
+  auto begin() const { return Iterator(events_); }
+  auto end() const { return Iterator(EventSet()); }
 
   /**
    * @brief Whether or not the given event is contained in the history
@@ -65,7 +74,7 @@ public:
    * @param e the event to check
    * @returns whether or not `e` is contained in the collection
    */
-  bool contains(UnfoldingEvent* e) const;
+  bool contains(const UnfoldingEvent* e) const;
 
   /**
    * @brief Computes all events in the history described by this instance
@@ -80,8 +89,61 @@ public:
    */
   EventSet get_all_events() const;
 
-  EventSet get_event_diff_with(const EventSet& event_set) const;
+  /**
+   * @brief Computes all events in the history described by this instance
+   * which are maximal (intuitively, those events which cause no others
+   * or are the "most recent")
+   */
+  EventSet get_all_maximal_events() const;
+
+  /**
+   * @brief Computes the set of events that are not contained
+   * in the given configuration
+   *
+   * A configuration is a causally-closed, conflict-free set
+   * of events. Thus, you can determine which events lie outside
+   * of a configuration during the search more efficiently: the moment
+   * you discover an event contained in the configuration, you
+   * do not need to search that event or any of its ancestors as
+   * they will all be contained in the configuration
+   */
   EventSet get_event_diff_with(const Configuration& config) const;
+
+private:
+  /**
+   * @brief An iterator which traverses the history of a set of events
+   */
+  struct Iterator : boost::iterator_facade<Iterator, const UnfoldingEvent* const, boost::forward_traversal_tag> {
+  public:
+    using optional_configuration = std::optional<std::reference_wrapper<const Configuration>>;
+    Iterator(const EventSet& initial_events, optional_configuration config = std::nullopt);
+
+  private:
+    /// @brief Points in the graph from where to continue the search
+    EventSet frontier;
+
+    /// @brief What the iterator currently believes to be the
+    /// entire history of the events in the graph it traverses
+    EventSet current_history = EventSet();
+
+    /// @brief What the iterator currently believes
+    // to be the set of maximal events
+    EventSet maximal_events;
+    optional_configuration configuration;
+
+    // boost::iterator_facade<...> interface to implement
+    void increment();
+    bool equal(const Iterator& other) const;
+
+    const UnfoldingEvent* const& dereference() const;
+
+    // Allows boost::iterator_facade<...> to function properly
+    friend class boost::iterator_core_access;
+
+    // Allow the `History` class to use some of the
+    // computation of the iterator
+    friend History;
+  };
 };
 
 } // namespace simgrid::mc::udpor