std::vector<const UnfoldingEvent*> Configuration::get_topologically_sorted_events() const
{
+ // This is essentially an implementation of detecting cycles
+ // in a graph with coloring, except it makes a topological
+ // ordering out of it
+
if (events_.empty()) {
return std::vector<const UnfoldingEvent*>();
}
if (not temporarily_marked_events.contains(evt)) {
// If this event hasn't yet been marked, do
- // so now so that if we see it again in a child we can
- // detect a cycle and if we see it again here
- // we can detect that the node is re-processed
+ // so now so that if we both see it
+ // again in a child we can detect a cycle
temporarily_marked_events.insert(evt);
EventSet immediate_causes = evt->get_immediate_causes();
}
immediate_causes.subtract(discovered_events);
immediate_causes.subtract(permanently_marked_events);
- const EventSet undiscovered_causes = std::move(immediate_causes);
-
- for (const auto cause : undiscovered_causes) {
- event_stack.push(cause);
- }
+ std::for_each(immediate_causes.begin(), immediate_causes.end(),
+ [&event_stack](const UnfoldingEvent* cause) { event_stack.push(cause); });
} else {
unknown_events.remove(evt);
temporarily_marked_events.remove(evt);
#include "src/3rd-party/catch.hpp"
#include "src/xbt/utils/iter/LazyKSubsets.hpp"
#include "src/xbt/utils/iter/LazyPowerset.hpp"
+#include "src/xbt/utils/iter/variable_for_loop.hpp"
#include <unordered_map>
#include <unordered_set>
{
std::vector<int> example_vec{0, 1, 2, 3, 4, 5, 6, 7};
- SECTION("Each element of each subset is distinct and appears half of the time")
+ SECTION("Each element of each subset is distinct")
{
for (unsigned k = 0; static_cast<size_t>(k) < example_vec.size(); k++) {
for (auto& subset : make_k_subsets_iter(k, example_vec)) {
REQUIRE(iter.second == expected_count);
}
}
+}
+
+TEST_CASE("simgrid::xbt::variable_for_loop: Edge Cases")
+{
+
+ SECTION("Iterations without effect")
+ {
+ SECTION("Iteration over no collections") {}
+
+ SECTION("Iteration with an empty collection") {}
+ }
}
\ No newline at end of file
--- /dev/null
+/* Copyright (c) 2004-2023 The SimGrid Team. All rights reserved. */
+
+/* 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_UTILS_ITER_VARIABLE_FOR_LOOP_HPP
+#define XBT_UTILS_ITER_VARIABLE_FOR_LOOP_HPP
+
+#include <algorithm>
+#include <boost/iterator/iterator_facade.hpp>
+#include <functional>
+#include <limits>
+#include <optional>
+
+namespace simgrid::xbt {
+
+/**
+ * @brief A higher-order forward-iterator which traverses all possible
+ * combinations of selections of elements from a collection of iterable
+ * sequences
+ *
+ * This iterator provides a means of iteratively traversing all combinations
+ * of elements of `k` collections (albeit of a single type), selecting a
+ * single element from each of the `k` collections in the same way a
+ * nested for-loop may select a set of elements. The benefit is that
+ * you do not need to actually physically write the for-loop statements
+ * directly, and you can dynamically adjust the number of levels of the
+ * for-loop according to the situation
+ *
+ * @class IterableType: The collections from which this iterator
+ * selects elements
+ */
+template <class IterableType>
+struct variable_for_loop : public boost::iterator_facade<variable_for_loop<IterableType>,
+ const std::vector<typename IterableType::const_iterator>,
+ boost::forward_traversal_tag> {
+public:
+ using underlying_iterator = typename IterableType::const_iterator;
+
+ variable_for_loop() = default;
+ explicit variable_for_loop(std::vector<std::reference_wrapper<IterableType>> collections)
+ {
+ // All collections should be non-empty: if one is empty, the
+ // for-loop has no effect (since there would be no way to choose
+ // one element from the empty collection(s))
+ const auto has_effect =
+ std::none_of(collections.begin(), collections.end(), [](const auto c) { return c.empty(); });
+
+ if (has_effect and (not collections.empty())) {
+ underlying_collections = std::move(collections);
+ std::copy(collections.begin(), collections.end(), std::back_inserter(current_subset),
+ [](const auto c) { return c.begin(); });
+ }
+ // Otherwise leave `underlying_collections` as default-initialized (i.e. empty)
+ }
+
+private:
+ std::vector<std::reference_wrapper<IterableType>> underlying_collections;
+
+ std::vector<underlying_iterator> current_subset;
+
+ // boost::iterator_facade<...> interface to implement
+ void increment();
+ bool equal(const variable_for_loop<IterableType>& other) const { return current_subset == other.current_subset; }
+ const std::vector<underlying_iterator>& dereference() const { return current_subset; }
+
+ // Allows boost::iterator_facade<...> to function properly
+ friend class boost::iterator_core_access;
+};
+
+template <typename IterableType> void variable_for_loop<IterableType>::increment()
+{
+ // Termination occurs when `current_subset := the empty set`
+ // or if we have nothing to iterate over
+ if (current_subset.empty() or underlying_collections.empty()) {
+ return;
+ }
+
+ size_t l = 0;
+ const size_t k = underlying_collections.size() - 1;
+
+ for (auto j = k - 1; j != std::numeric_limits<size_t>::max(); j--) {
+ // Attempt to move to the next element of the `j`th collection
+ const auto& new_position = ++current_subset[j];
+
+ // If the `j`th element has reached its own end, reset it
+ // back to the beginning and keep moving forward
+ if (new_position == underlying_collections[j].end()) {
+ current_subset[j] = underlying_collections[j].begin();
+ } else {
+ // Otherwise we've found the largest element which needed to
+ // be moved down, and everyone else before us has been reset
+ // to properly to point at their beginnings
+ l = j;
+ break;
+ }
+ }
+
+ if (l == 0) {
+ // We've iterated over all subsets at this point:
+ // set the termination condition
+ current_subset.clear();
+ return;
+ }
+}
+
+} // namespace simgrid::xbt
+
+#endif
