From 19ac7578ffba786dbf458aa6afc8822ea73f78b6 Mon Sep 17 00:00:00 2001
From: Maxwell Pirtle <maxwellpirtle@gmail.com>
Date: Wed, 10 May 2023 15:03:08 +0200
Subject: [PATCH] Finish post-order travesal with WakeupTreeIterator

The WakeupTreeIterator is now full implemented:
we now properly add nodes to the top of the
stack in reverse order, resulting in a post-order
traversal as desired.

One subtlety arose with the implementation: the
root node is not contained in the list of any
other node in the tree. To handle this issue,
a "fake" list managed by the iterator was added
into which the root is placed at construction-time.
This prevents us from needing to change any of the
logic, and we can simply treat the root as any other
node in the traversal
---
 src/mc/explo/odpor/WakeupTree.hpp         |  1 +
 src/mc/explo/odpor/WakeupTreeIterator.cpp | 14 +++++++++-----
 src/mc/explo/odpor/WakeupTreeIterator.hpp | 15 ++++++++++++++-
 3 files changed, 24 insertions(+), 6 deletions(-)

diff --git a/src/mc/explo/odpor/WakeupTree.hpp b/src/mc/explo/odpor/WakeupTree.hpp
index e0fc5a6212..8ffbe61854 100644
--- a/src/mc/explo/odpor/WakeupTree.hpp
+++ b/src/mc/explo/odpor/WakeupTree.hpp
@@ -27,6 +27,7 @@ private:
 
   /** Allows the owning tree to insert directly into the child */
   friend WakeupTree;
+  friend WakeupTreeIterator;
 
 public:
   WakeupTreeNode(const WakeupTreeNode&)            = delete;
diff --git a/src/mc/explo/odpor/WakeupTreeIterator.cpp b/src/mc/explo/odpor/WakeupTreeIterator.cpp
index bb479f37cf..faaa90a7a4 100644
--- a/src/mc/explo/odpor/WakeupTreeIterator.cpp
+++ b/src/mc/explo/odpor/WakeupTreeIterator.cpp
@@ -8,9 +8,9 @@
 
 namespace simgrid::mc::odpor {
 
-WakeupTreeIterator::WakeupTreeIterator(const WakeupTree& tree)
+WakeupTreeIterator::WakeupTreeIterator(const WakeupTree& tree) : root_list{tree.root_}
 {
-  //   post_order_iteration.push(tree.root);
+  post_order_iteration.push(root_list.begin());
   push_until_left_most_found();
 }
 
@@ -26,6 +26,11 @@ void WakeupTreeIterator::push_until_left_most_found()
     // reverse order (right-most to left-most),
     // we ensure that we'll always process left-most
     // children first
+    auto& children = cur_top_node->children_;
+
+    for (auto iter = children.rbegin(); iter != children.rend(); ++iter) {
+      post_order_iteration.push(iter.base());
+    }
   }
 }
 
@@ -52,12 +57,11 @@ void WakeupTreeIterator::increment()
   // Otherwise, look at the next top node. If
   // `prev_top` is that node's right-most child,
   // then we don't attempt to re-add `next_top`'s
-  // children again for we would have already seen them
-  const auto* next_top_node = *post_order_iteration.top();
-
+  // children again for we would have already seen them.
   // To actually determine "right-most", we check if
   // moving over to the right one spot brings us to the
   // end of the candidate parent's list
+  const auto* next_top_node = *post_order_iteration.top();
   if ((++prev_top_handle) != next_top_node->get_ordered_children().end()) {
     push_until_left_most_found();
   }
diff --git a/src/mc/explo/odpor/WakeupTreeIterator.hpp b/src/mc/explo/odpor/WakeupTreeIterator.hpp
index 9254829867..8d65829346 100644
--- a/src/mc/explo/odpor/WakeupTreeIterator.hpp
+++ b/src/mc/explo/odpor/WakeupTreeIterator.hpp
@@ -23,13 +23,26 @@ public:
 private:
   using node_handle = std::list<WakeupTreeNode*>::iterator;
 
+  /**
+   *  @brief A list which is used to "store" the root node of the traversed
+   * wakeup tree
+   *
+   * The root node is, by definition, not the child of any other node. This
+   * means that the root node also is contained in any list into which the
+   * iterator can generate a pointer (iterator). This list takes the role
+   * of allowing the iterator to treat the root node like any other.
+   */
+  std::list<WakeupTreeNode*> root_list;
+
   /**
    * @brief The current "view" of the iteration in post-order traversal
    */
   std::stack<node_handle> post_order_iteration;
 
   /**
-   *
+   * @brief Search the wakeup tree until a leaf node appears at the front
+   * of the iteration, pushing all children towards the top of the stack
+   * as the search progresses
    */
   void push_until_left_most_found();
 
-- 
2.20.1