X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/01ee0802dc993fc4f9e0c9e2e3babe352bf9df68..bc2253e2c879ee28ae5153f1d56497ab802aeea9:/src/mc/explo/odpor/WakeupTree.hpp

diff --git a/src/mc/explo/odpor/WakeupTree.hpp b/src/mc/explo/odpor/WakeupTree.hpp
index 2a12641284..def2840e0f 100644
--- a/src/mc/explo/odpor/WakeupTree.hpp
+++ b/src/mc/explo/odpor/WakeupTree.hpp
@@ -21,12 +21,20 @@ namespace simgrid::mc::odpor {
 /**
  * @brief A single node in a wakeup tree
  *
- * Each node in a wakeup tree contains
+ * Each node in a wakeup tree represents a single step
+ * taken in an extension of the execution represented
+ * by the tree within which the node is contained. That is,
+ * a node in the tree is one step on a "pre-defined"
+ * path forward for some execution sequence. The partial
+ * execution that is implicitly represented by the node
+ * is that formed by taking each step on the (unique)
+ * path in the tree from the root node to this node.
+ * Thus, the tree itself contains all of the paths
+ * that "should be" searched, while each node is
+ * simply a step on each path.
  */
 class WakeupTreeNode {
 private:
-  explicit WakeupTreeNode(std::shared_ptr<Transition> u) : action_(u) {}
-
   WakeupTreeNode* parent_ = nullptr;
 
   /** An ordered list of children of for this node in the tree */
@@ -43,16 +51,19 @@ private:
   friend WakeupTreeIterator;
 
 public:
+  explicit WakeupTreeNode(std::shared_ptr<Transition> u) : action_(u) {}
+
+  WakeupTreeNode()                                 = default;
   ~WakeupTreeNode()                                = default;
   WakeupTreeNode(const WakeupTreeNode&)            = delete;
   WakeupTreeNode(WakeupTreeNode&&)                 = default;
   WakeupTreeNode& operator=(const WakeupTreeNode&) = delete;
   WakeupTreeNode& operator=(WakeupTreeNode&&)      = default;
 
-  const auto begin() const { return this->children_.begin(); }
-  const auto end() const { return this->children_.end(); }
-  const auto rbegin() const { return this->children_.rbegin(); }
-  const auto rend() const { return this->children_.rend(); }
+  auto begin() const { return this->children_.begin(); }
+  auto end() const { return this->children_.end(); }
+  auto rbegin() const { return this->children_.rbegin(); }
+  auto rend() const { return this->children_.rend(); }
 
   bool is_leaf() const { return children_.empty(); }
   bool is_root() const { return parent_ == nullptr; }
@@ -61,6 +72,8 @@ public:
   std::shared_ptr<Transition> get_action() const { return action_; }
   const std::list<WakeupTreeNode*>& get_ordered_children() const { return children_; }
 
+  std::string string_of_whole_tree(int indentation_level) const;
+
   /** Insert a node `node` as a new child of this node */
   void add_child(WakeupTreeNode* node);
 };
@@ -105,7 +118,7 @@ private:
   void insert_node(std::unique_ptr<WakeupTreeNode> node);
   void insert_sequence_after(WakeupTreeNode* node, const PartialExecution& w);
   void remove_node(WakeupTreeNode* node);
-  bool contains(WakeupTreeNode* node) const;
+  bool contains(const WakeupTreeNode* node) const;
 
   /**
    * @brief Removes the node `root` and all of its descendants from
@@ -141,6 +154,8 @@ public:
 
   std::vector<std::string> get_single_process_texts() const;
 
+  std::string string_of_whole_tree() const;
+
   /**
    * @brief Remove the subtree of the smallest (with respect
    * to the tree's "<" relation) single-process node.
@@ -154,6 +169,8 @@ public:
    */
   void remove_min_single_process_subtree();
 
+  void remove_subtree_at_aid(aid_t proc);
+
   /**
    * @brief Whether or not this tree is considered empty
    *
@@ -167,7 +184,7 @@ public:
    * @brief Returns the number of *non-empty* entries in the tree, viz. the
    * number of nodes in the tree that have an action mapped to them
    */
-  size_t get_num_entries() const { return !empty() ? (nodes_.size() - 1) : static_cast<size_t>(0); }
+  size_t get_num_entries() const { return not empty() ? (nodes_.size() - 1) : static_cast<size_t>(0); }
 
   /**
    * @brief Returns the number of nodes in the tree, including the root node
@@ -190,6 +207,9 @@ public:
    */
   std::optional<WakeupTreeNode*> get_min_single_process_node() const;
 
+  /** @brief Describes how a tree insertion was carried out */
+  enum class InsertionResult { leaf, interior_node, root };
+
   /**
    * @brief Inserts an sequence `seq` of processes into the tree
    * such that that this tree is a wakeup tree relative to the
@@ -214,8 +234,11 @@ public:
    *
    * @invariant: It is assumed that this tree is a wakeup tree
    * with respect to the given execution `E`
+   *
+   * @return Whether a sequence equivalent to `seq` is already contained
+   * as a leaf node in the tree
    */
-  void insert(const Execution& E, const PartialExecution& seq);
+  InsertionResult insert(const Execution& E, const PartialExecution& seq);
 };
 
 } // namespace simgrid::mc::odpor