src/mc/explo/odpor/WakeupTreeIterator.cpp

   1 /* Copyright (c) 2008-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 #include "src/mc/explo/odpor/WakeupTreeIterator.hpp"
   7 #include "src/mc/explo/odpor/WakeupTree.hpp"
   8
   9 namespace simgrid::mc::odpor {
  10
  11 WakeupTreeIterator::WakeupTreeIterator(const WakeupTree& tree) : root_list{tree.root_}
  12 {
  13   post_order_iteration.push(root_list.begin());
  14   push_until_left_most_found();
  15 }
  16
  17 void WakeupTreeIterator::push_until_left_most_found()
  18 {
  19   // INVARIANT: Since we are traversing over a tree,
  20   // there are no cycles. This means that at least
  21   // one node in the tree won't have any children,
  22   // so the loop will eventually terminate
  23   auto* cur_top_node = *post_order_iteration.top();
  24   while (!cur_top_node->is_leaf()) {
  25     // INVARIANT: Since we push children in
  26     // reverse order (right-most to left-most),
  27     // we ensure that we'll always process left-most
  28     // children first
  29     auto& children = cur_top_node->children_;
  30
  31     for (auto iter = children.rbegin(); iter != children.rend(); ++iter) {
  32       post_order_iteration.push(iter.base());
  33     }
  34   }
  35 }
  36
  37 void WakeupTreeIterator::increment()
  38 {
  39   // If there are no nodes in the stack, we've
  40   // completed the traversal: there's nothing left
  41   // to do
  42   if (post_order_iteration.empty()) {
  43     return;
  44   }
  45
  46   auto prev_top_handle = post_order_iteration.top();
  47   post_order_iteration.pop();
  48
  49   // If there are now no longer any nodes left,
  50   // we know that `prev_top` must be the original
  51   // root; that is, we were *just* pointing at the
  52   // original root, so we're done
  53   if (post_order_iteration.empty()) {
  54     return;
  55   }
  56
  57   // Otherwise, look at the next top node. If
  58   // `prev_top` is that node's right-most child,
  59   // then we don't attempt to re-add `next_top`'s
  60   // children again for we would have already seen them.
  61   // To actually determine "right-most", we check if
  62   // moving over to the right one spot brings us to the
  63   // end of the candidate parent's list
  64   const auto* next_top_node = *post_order_iteration.top();
  65   if ((++prev_top_handle) != next_top_node->get_ordered_children().end()) {
  66     push_until_left_most_found();
  67   }
  68 }
  69
  70 } // namespace simgrid::mc::odpor