1 /* Copyright (c) 2007-2023. The SimGrid Team. All rights reserved. */
3 /* This program is free software; you can redistribute it and/or modify it
4 * under the terms of the license (GNU LGPL) which comes with this package. */
6 #ifndef SIMGRID_MC_ODPOR_WAKEUP_TREE_ITERATOR_HPP
7 #define SIMGRID_MC_ODPOR_WAKEUP_TREE_ITERATOR_HPP
9 #include "src/mc/explo/odpor/odpor_forward.hpp"
11 #include <boost/iterator/iterator_facade.hpp>
15 namespace simgrid::mc::odpor {
17 struct WakeupTreeIterator
18 : public boost::iterator_facade<WakeupTreeIterator, WakeupTreeNode*, boost::forward_traversal_tag> {
20 WakeupTreeIterator() = default;
21 explicit WakeupTreeIterator(const WakeupTree& tree);
24 using node_handle = std::list<WakeupTreeNode*>::iterator;
27 * @brief A list which is used to "store" the root node of the traversed
30 * The root node is, by definition, not the child of any other node. This
31 * means that the root node also is contained in any list into which the
32 * iterator can generate a pointer (iterator). This list takes the role
33 * of allowing the iterator to treat the root node like any other.
35 std::list<WakeupTreeNode*> root_list;
38 * @brief The current "view" of the iteration in post-order traversal
40 std::stack<node_handle> post_order_iteration;
43 * @brief Search the wakeup tree until a leaf node appears at the front
44 * of the iteration, pushing all children towards the top of the stack
45 * as the search progresses
47 void push_until_left_most_found();
49 // boost::iterator_facade<...> interface to implement
51 bool equal(const WakeupTreeIterator& other) const { return post_order_iteration == other.post_order_iteration; }
52 WakeupTreeNode*& dereference() const { return *post_order_iteration.top(); }
54 // Allows boost::iterator_facade<...> to function properly
55 friend class boost::iterator_core_access;
58 } // namespace simgrid::mc::odpor