From fc8187ba6533e0de6a4f1cedea11dba6bba428d1 Mon Sep 17 00:00:00 2001
From: Maxwell Pirtle <maxwellpirtle@gmail.com>
Date: Mon, 20 Mar 2023 09:33:34 +0100
Subject: [PATCH] Add documentation for Comb data structure

The Comb data structure lacked documentation
prior to this commit. Since it plays a pretty
important role in the computation of `K`-partial
alternatives, it was given a more extensive
explanation to ensure that it was used properly.
---
 src/mc/explo/udpor/Comb.hpp | 69 +++++++++++++++++++++++++++++--------
 1 file changed, 55 insertions(+), 14 deletions(-)

diff --git a/src/mc/explo/udpor/Comb.hpp b/src/mc/explo/udpor/Comb.hpp
index b7f017b16a..ab0ec7a08e 100644
--- a/src/mc/explo/udpor/Comb.hpp
+++ b/src/mc/explo/udpor/Comb.hpp
@@ -17,34 +17,75 @@
 
 namespace simgrid::mc::udpor {
 
+/**
+ * @brief  An individual element of a `Comb`, i.e. a
+ * sequence of `const UnfoldingEvent*`s
+ */
 using Spike = std::vector<const UnfoldingEvent*>;
 
-class Comb {
+/**
+ * @brief A two-dimensional data structure that is used
+ * to compute partial alternatives in UDPOR
+ *
+ * The comb data structure is described in the paper
+ * "Quasi-Optimal DPOR" by Nguyen et al. Formally,
+ * if `A` is a set:
+ *
+ * """
+ * An **A-Comb C of size `n` (`n` a natural number)**
+ * is an *ordered* collection of spikes <s_1, s_2, ..., s_n>,
+ * where each spike is a sequence of elements over A.
+ *
+ * Furthermore, a **combination over C** is any tuple
+ * <a_1, a_2, ..., a_n> where a_i is a member of s_i
+ * """
+ *
+ * The name probably comes from what the structure looks
+ * like if you draw it out. For example, if `A = {1, 2, 3, ..., 10}`,
+ * then a possible `A-comb` of size 8 might look like
+ *
+ * 1 2 3 4 5 6
+ * 2 4 5 9 8
+ * 10 9 2 1 1
+ * 8 9 10 5
+ * 1
+ * 3 4 5
+ * 1 4 4 5 1 6
+ * 8 8 9
+ *
+ * which, if you squint a bit, looks like a comb (albeit with some
+ * broken bristles [or spikes]). A combination is any selection of
+ * one element within each spike; e.g. (where _x_ denotes element `x`
+ * is selected)
+ *
+ * 1 2 _3_ 4 5 6
+ * 2 _4_ 5 9 8
+ * 10 9 2 _1_ 1
+ * 8 _9_ 10 5
+ * _1_
+ * 3 4 _5_
+ * 1 _4_ 4 5 1 6
+ * _8_ 8 9
+ *
+ * A `Comb` as described by this C++ class is a `U-comb`, where
+ * `U` is the set of events that UDPOR has explored. That is,
+ * the comb is over a set of events
+ */
+class Comb : public std::vector<Spike> {
 public:
-  explicit Comb(unsigned k) : k(k), spikes(k) {}
+  explicit Comb(unsigned k) : std::vector<Spike>(k) {}
   Comb(const Comb& other)            = default;
   Comb(Comb&& other)                 = default;
   Comb& operator=(const Comb& other) = default;
   Comb& operator=(Comb&& other)      = default;
 
-  Spike& operator[](unsigned i) { return spikes[i]; }
-  const Spike& operator[](unsigned i) const { return spikes[i]; }
-
   auto combinations_begin() const
   {
     std::vector<std::reference_wrapper<const Spike>> references;
-    std::transform(spikes.begin(), spikes.end(), std::back_inserter(references),
-                   [](const Spike& spike) { return std::cref(spike); });
+    std::transform(begin(), end(), std::back_inserter(references), [](const Spike& spike) { return std::cref(spike); });
     return simgrid::xbt::variable_for_loop<const Spike>(std::move(references));
   }
-
   auto combinations_end() const { return simgrid::xbt::variable_for_loop<const Spike>(); }
-  auto begin() const { return spikes.begin(); }
-  auto end() const { return spikes.end(); }
-
-private:
-  unsigned k;
-  std::vector<Spike> spikes;
 };
 
 } // namespace simgrid::mc::udpor
-- 
2.20.1