void maximal_subsets_iterator::increment()
{
- // Until we discover otherwise, we default to being done
- auto next_event_ref = topological_ordering.end();
+ if (current_maximal_set = std::nullopt) {
+ return;
+ }
+
+ const auto next_event_ref = continue_traversal_of_maximal_events_tree();
+ if (next_event_ref == topological_ordering.end()) {
+ current_maximal_set = std::nullopt;
+ return;
+ }
+ // We found some other event `e'` which is not in causally related with anything
+ // that currently exists in `current_maximal_set`. Add it in
+ add_element_to_current_maximal_set(*next_event_ref);
+ backtrack_points.push(next_event_ref);
+}
+
+maximal_subsets_iterator::topological_order_position
+maximal_subsets_iterator::continue_traversal_of_maximal_events_tree()
+{
while (not backtrack_points.empty()) {
// This is an iterator which points to the latest event `e` that
// was added to what is currently the maximal set
// will not change whether or not to now allow someone before `e`
// in the ordering (otherwise, they would have to be in `e`'s history
// and therefore would come after `e`)
- next_event_ref = bookkeeper.find_next_event(latest_event_ref, topological_ordering.end());
-
- // If we can't find another event to add after `e`,
- // then we retry after first removing the latest event.
- // This effectively tests "check now with all combinations that
- // exclude the latest event".
- //
- // Note: it is important to remove the element FIRST before performing
- // the second search, as removal may enable dependencies of `e` to be selected
- if (next_event_ref == topological_ordering.end()) {
+ auto next_event_ref = bookkeeper.find_next_candidate_event(latest_event_ref, topological_ordering.end());
+
+ // If we found some event, we can stop
+ if (next_event_ref != topological_ordering.end() and should_consider_event(*next_event_ref)) {
+ return next_event_ref;
+ } else {
+ // Otherwise, if we can't find another event to add after `e` that
+ // we need to consider, we retry after first removing the latest event.
+ // This effectively tests "check now with all combinations that3
+ // exclude the latest event".
+ //
+ // Note: it is important to remove the element FIRST before performing
+ // the second search, as removal may enable dependencies of `e` to be selected
remove_element_from_current_maximal_set(*latest_event_ref);
backtrack_points.pop();
// We begin the search AFTER the event we popped: we only want
// to consider those events that could be added AFTER `e` and
// not `e` itself again
- next_event_ref = bookkeeper.find_next_event(latest_event_ref + 1, topological_ordering.end());
+ next_event_ref = bookkeeper.find_next_candidate_event(latest_event_ref + 1, topological_ordering.end());
- // If we finally found some event, we can stop
- if (next_event_ref != topological_ordering.end()) {
- break;
+ // If we finally found some event AFTER removal, we can stop
+ if (next_event_ref != topological_ordering.end() and should_consider_event(*next_event_ref)) {
+ return next_event_ref;
}
}
}
+ return topological_ordering.end();
+}
- // If after all of the backtracking we still have no luck, we've finished
- if (next_event_ref == topological_ordering.end()) {
- return;
+bool maximal_subsets_iterator::should_consider_event(const UnfoldingEvent* e) const
+{
+ if (filter_function.has_value()) {
+ return filter_function.value()(e);
}
-
- // Otherwise we found some other event `e'` which is not in conflict with anything
- // that currently exists in `current_maximal_set`. Add it in and perform
- // some more bookkeeping
- add_element_to_current_maximal_set(*next_event_ref);
- backtrack_points.push(next_event_ref);
+ return true; // If nobody specified a filter, we default to considering the event
}
bool maximal_subsets_iterator::bookkeeper::is_candidate_event(const UnfoldingEvent* e) const
void maximal_subsets_iterator::add_element_to_current_maximal_set(const UnfoldingEvent* e)
{
- current_maximal_set.insert(e);
+ xbt_assert(current_maximal_set.has_value(), "Attempting to add an event to the maximal set "
+ "when iteration has completed. This indicates that "
+ "the termination condition for the iterator is broken");
+ current_maximal_set.value().insert(e);
bookkeeper.mark_included_in_maximal_set(e);
}
void maximal_subsets_iterator::remove_element_from_current_maximal_set(const UnfoldingEvent* e)
{
- current_maximal_set.remove(e);
+ xbt_assert(current_maximal_set.has_value(), "Attempting to remove an event to the maximal set "
+ "when iteration has completed. This indicates that "
+ "the termination condition for the iterator is broken");
+ current_maximal_set.value().remove(e);
bookkeeper.mark_removed_from_maximal_set(e);
}
maximal_subsets_iterator::topological_order_position
-maximal_subsets_iterator::bookkeeper::find_next_event(topological_order_position first,
- topological_order_position last) const
+maximal_subsets_iterator::bookkeeper::find_next_candidate_event(topological_order_position first,
+ topological_order_position last) const
{
return std::find_if(first, last, [&](const UnfoldingEvent* e) { return is_candidate_event(e); });
}
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, std::nullopt) {}
- maximal_subsets_iterator(const Configuration& config, node_filter_function filter)
+ maximal_subsets_iterator(const Configuration& config, std::optional<node_filter_function> filter)
: config({config})
, topological_ordering(config.get_topologically_sorted_events_of_reverse_graph())
- , filter(filter)
+ , filter_function(filter)
+ , current_maximal_set({EventSet()})
{
- // 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);
- }
}
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;
+ const std::optional<node_filter_function> filter_function = std::nullopt;
- EventSet current_maximal_set = EventSet();
+ std::optional<EventSet> current_maximal_set = std::nullopt;
std::stack<topological_order_position> backtrack_points;
/**
* its `current_maximal_set`)
*/
struct bookkeeper {
- private:
+ public:
using topological_order_position = maximal_subsets_iterator::topological_order_position;
+ 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;
+
+ 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;
- public:
- void mark_included_in_maximal_set(const UnfoldingEvent*);
- void mark_removed_from_maximal_set(const UnfoldingEvent*);
-
- topological_order_position find_next_event(topological_order_position first, topological_order_position last) 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
+ *
+ * @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();
+
+ /// @brief Whether or not we should even consider cases where the given
+ /// event `e` is included in the maximal configurations
+ bool should_consider_event(const UnfoldingEvent*) 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 { 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;
