#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>
/**
* @brief An iterator over the tree of sets of (non-empty) maximal events that
- * can be generated from a given configuration
+ * 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
using node_filter_function = std::function<bool(const UnfoldingEvent*)>;
using topological_order_position = std::vector<const UnfoldingEvent*>::const_iterator;
- maximal_subsets_iterator() = default;
- explicit maximal_subsets_iterator(const Configuration& config) : maximal_subsets_iterator(config, std::nullopt) {}
- maximal_subsets_iterator(const Configuration& config, std::optional<node_filter_function> filter);
+ maximal_subsets_iterator() = default;
+ explicit maximal_subsets_iterator(const Configuration& config,
+ const std::optional<node_filter_function>& filter = std::nullopt,
+ std::optional<size_t> maximum_subset_size = std::nullopt)
+ : maximal_subsets_iterator(config.get_events(), filter, maximum_subset_size)
+ {
+ }
+ explicit maximal_subsets_iterator(const EventSet& events,
+ const std::optional<node_filter_function>& filter = std::nullopt,
+ std::optional<size_t> maximum_subset_size = std::nullopt);
private:
- const std::optional<std::reference_wrapper<const Configuration>> config = std::nullopt;
std::vector<const UnfoldingEvent*> topological_ordering;
// The boolean is a bit of an annoyance, but it works. Effectively,
// 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<size_t> maximum_subset_size = std::nullopt;
std::optional<EventSet> current_maximal_set = std::nullopt;
- std::stack<topological_order_position> backtrack_points = std::stack<topological_order_position>();
+ std::stack<topological_order_position, std::vector<topological_order_position>> backtrack_points;
/**
* @brief A small class which provides functionality for managing
* with events that are its current maximal event set (i.e.
* its `current_maximal_set`)
*/
- struct bookkeeper {
+ struct Bookkeeper {
public:
using topological_order_position = maximal_subsets_iterator::topological_order_position;
/// bookkeeping that has been done thus far, can be added to the
/// current candidate maximal set
bool is_candidate_event(const UnfoldingEvent*) const;
- } bookkeeper;
+ };
+ Bookkeeper bookkeeper;
void add_element_to_current_maximal_set(const UnfoldingEvent*);
void remove_element_from_current_maximal_set(const UnfoldingEvent*);
*/
topological_order_position continue_traversal_of_maximal_events_tree();
+ /**
+ * @brief: Whether or not the current maximal set can
+ * grow based on the size limit imposed on the maximal
+ * sets that can be produced
+ */
+ bool can_grow_maximal_set() const;
+
// 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
{
- static const EventSet empty_set = EventSet();
+ static const EventSet empty_set;
if (current_maximal_set.has_value()) {
return current_maximal_set.value();
}
friend class boost::iterator_core_access;
};
-/**
- * @brief A collection whose contents consist of
- * the maximal event sets of some configuration
- *
- * @note You should treat this class as a small
- * wrapper that is more convenient and readable
- * than creating iterators directly, and thus should
- * not e.g. store instanca
- */
-class maximal_subsets_iterator_wrapper {
-public:
- using node_filter_function = maximal_subsets_iterator::node_filter_function;
-
- maximal_subsets_iterator_wrapper(const maximal_subsets_iterator_wrapper&) = delete;
- maximal_subsets_iterator_wrapper& operator=(const maximal_subsets_iterator_wrapper&) = delete;
- maximal_subsets_iterator_wrapper(const maximal_subsets_iterator_wrapper&&) = delete;
- maximal_subsets_iterator_wrapper& operator=(const maximal_subsets_iterator_wrapper&&) = delete;
-
- explicit maximal_subsets_iterator_wrapper(const Configuration& config) : config(config) {}
- maximal_subsets_iterator_wrapper(const Configuration& config, node_filter_function filter)
- : config(config), filter({filter})
- {
- }
-
- auto begin() const { return maximal_subsets_iterator(config, filter); }
- auto end() const { return maximal_subsets_iterator(); }
-
-private:
- const Configuration& config;
- std::optional<node_filter_function> filter = std::nullopt;
-};
+template <typename T>
+using maximal_subsets_iterator_wrapper = simgrid::xbt::iterator_wrapping<maximal_subsets_iterator, const T&>;
} // namespace simgrid::mc::udpor
#endif