src/mc/explo/odpor/WakeupTreeIterator.hpp

   1 /* Copyright (c) 2007-2023. The SimGrid Team. All rights reserved.          */
   2
   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. */
   5
   6 #ifndef SIMGRID_MC_ODPOR_WAKEUP_TREE_ITERATOR_HPP
   7 #define SIMGRID_MC_ODPOR_WAKEUP_TREE_ITERATOR_HPP
   8
   9 #include "src/mc/explo/odpor/odpor_forward.hpp"
  10
  11 #include <boost/iterator/iterator_facade.hpp>
  12 #include <list>
  13 #include <stack>
  14
  15 namespace simgrid::mc::odpor {
  16
  17 /**
  18  * @brief A forward-iterator that performs a postorder traversal
  19  * of the nodes of a WakeupTree
  20  *
  21  * Inserting a sequence `w` into a wakeup tree `B` with respect to
  22  * some execution `E` requires determining the "<-minimal" node `N`
  23  * with sequence `v` in the tree such that `v ~_[E] w`. The "<" relation
  24  * over a wakeup tree orders its nodes by first recursively ordering all
  25  * children of a node `N` followed by the node `N` itself, viz. a postorder.
  26  * This iterator provides such a postorder traversal over the nodes in the
  27  * wakeup tree.
  28  */
  29 class WakeupTreeIterator
  30     : public boost::iterator_facade<WakeupTreeIterator, WakeupTreeNode*, boost::forward_traversal_tag> {
  31 public:
  32   // Use rule-of-three, and implicitely disable the move constructor which cannot be 'noexcept' (as required by C++ Core
  33   // Guidelines), due to the std::list and std:stack<std::deque> members.
  34   WakeupTreeIterator()                          = default;
  35   WakeupTreeIterator(const WakeupTreeIterator&) = default;
  36   ~WakeupTreeIterator()                         = default;
  37
  38   explicit WakeupTreeIterator(const WakeupTree& tree);
  39
  40 private:
  41   using node_handle = std::list<WakeupTreeNode*>::iterator;
  42
  43   /**
  44    *  @brief A list which is used to "store" the root node of the traversed
  45    * wakeup tree
  46    *
  47    * The root node is, by definition, not the child of any other node. This
  48    * means that the root node also is contained in any list into which the
  49    * iterator can generate a pointer (iterator). This list takes the role
  50    * of allowing the iterator to treat the root node like any other.
  51    */
  52   std::list<WakeupTreeNode*> root_list;
  53
  54   /**
  55    * @brief The current "view" of the iteration in post-order traversal
  56    */
  57   std::stack<node_handle> post_order_iteration;
  58
  59   /**
  60    * @brief Search the wakeup tree until a leaf node appears at the front
  61    * of the iteration, pushing all children towards the top of the stack
  62    * as the search progresses
  63    */
  64   void push_until_left_most_found();
  65
  66   // boost::iterator_facade<...> interface to implement
  67   void increment();
  68   bool equal(const WakeupTreeIterator& other) const { return post_order_iteration == other.post_order_iteration; }
  69   WakeupTreeNode*& dereference() const { return *post_order_iteration.top(); }
  70
  71   // Allows boost::iterator_facade<...> to function properly
  72   friend class boost::iterator_core_access;
  73 };
  74
  75 } // namespace simgrid::mc::odpor
  76 #endif