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