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