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)
  12 {
  13   //   post_order_iteration.push(tree.root);
  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   }
  30 }
  31
  32 void WakeupTreeIterator::increment()
  33 {
  34   // If there are no nodes in the stack, we've
  35   // completed the traversal: there's nothing left
  36   // to do
  37   if (post_order_iteration.empty()) {
  38     return;
  39   }
  40
  41   auto prev_top_handle = post_order_iteration.top();
  42   post_order_iteration.pop();
  43
  44   // If there are now no longer any nodes left,
  45   // we know that `prev_top` must be the original
  46   // root; that is, we were *just* pointing at the
  47   // original root, so we're done
  48   if (post_order_iteration.empty()) {
  49     return;
  50   }
  51
  52   // Otherwise, look at the next top node. If
  53   // `prev_top` is that node's right-most child,
  54   // then we don't attempt to re-add `next_top`'s
  55   // children again for we would have already seen them
  56   const auto* next_top_node = *post_order_iteration.top();
  57
  58   // To actually determine "right-most", we check if
  59   // moving over to the right one spot brings us to the
  60   // end of the candidate parent's list
  61   if ((++prev_top_handle) != next_top_node->get_ordered_children().end()) {
  62     push_until_left_most_found();
  63   }
  64 }
  65
  66 } // namespace simgrid::mc::odpor