src/xbt/utils/iter/variable_for_loop.hpp

   1 /* Copyright (c) 2004-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 #ifndef XBT_UTILS_ITER_VARIABLE_FOR_LOOP_HPP
   7 #define XBT_UTILS_ITER_VARIABLE_FOR_LOOP_HPP
   8
   9 #include <algorithm>
  10 #include <boost/iterator/iterator_facade.hpp>
  11 #include <functional>
  12 #include <limits>
  13 #include <optional>
  14
  15 namespace simgrid::xbt {
  16
  17 /**
  18  * @brief A higher-order forward-iterator which traverses all possible
  19  * combinations of selections of elements from a collection of iterable
  20  * sequences
  21  *
  22  * This iterator provides a means of iteratively traversing all combinations
  23  * of elements of `k` collections (albeit of a single type), selecting a
  24  * single element from each of the `k` collections in the same way a
  25  * nested for-loop may select a set of elements. The benefit is that
  26  * you do not need to actually physically write the for-loop statements
  27  * directly, and you can dynamically adjust the number of levels of the
  28  * for-loop according to the situation
  29  *
  30  * @class IterableType: The collections from which this iterator
  31  * selects elements
  32  */
  33 template <class IterableType>
  34 struct variable_for_loop : public boost::iterator_facade<variable_for_loop<IterableType>,
  35                                                          const std::vector<typename IterableType::const_iterator>,
  36                                                          boost::forward_traversal_tag> {
  37 public:
  38   using underlying_iterator = typename IterableType::const_iterator;
  39
  40   variable_for_loop() = default;
  41   explicit variable_for_loop(std::vector<std::reference_wrapper<IterableType>> collections)
  42   {
  43     // All collections should be non-empty: if one is empty, the
  44     // for-loop has no effect (since there would be no way to choose
  45     // one element from the empty collection(s))
  46     const auto has_effect =
  47         std::none_of(collections.begin(), collections.end(), [](const auto c) { return c.empty(); });
  48
  49     if (has_effect and (not collections.empty())) {
  50       underlying_collections = std::move(collections);
  51       std::copy(collections.begin(), collections.end(), std::back_inserter(current_subset),
  52                 [](const auto c) { return c.begin(); });
  53     }
  54     // Otherwise leave `underlying_collections` as default-initialized (i.e. empty)
  55   }
  56
  57 private:
  58   std::vector<std::reference_wrapper<IterableType>> underlying_collections;
  59
  60   std::vector<underlying_iterator> current_subset;
  61
  62   // boost::iterator_facade<...> interface to implement
  63   void increment();
  64   bool equal(const variable_for_loop<IterableType>& other) const { return current_subset == other.current_subset; }
  65   const std::vector<underlying_iterator>& dereference() const { return current_subset; }
  66
  67   // Allows boost::iterator_facade<...> to function properly
  68   friend class boost::iterator_core_access;
  69 };
  70
  71 template <typename IterableType> void variable_for_loop<IterableType>::increment()
  72 {
  73   // Termination occurs when `current_subset := the empty set`
  74   // or if we have nothing to iterate over
  75   if (current_subset.empty() or underlying_collections.empty()) {
  76     return;
  77   }
  78
  79   size_t l       = 0;
  80   const size_t k = underlying_collections.size() - 1;
  81
  82   for (auto j = k - 1; j != std::numeric_limits<size_t>::max(); j--) {
  83     // Attempt to move to the next element of the `j`th collection
  84     const auto& new_position = ++current_subset[j];
  85
  86     // If the `j`th element has reached its own end, reset it
  87     // back to the beginning and keep moving forward
  88     if (new_position == underlying_collections[j].end()) {
  89       current_subset[j] = underlying_collections[j].begin();
  90     } else {
  91       // Otherwise we've found the largest element which needed to
  92       // be moved down, and everyone else before us has been reset
  93       // to properly to point at their beginnings
  94       l = j;
  95       break;
  96     }
  97   }
  98
  99   if (l == 0) {
 100     // We've iterated over all subsets at this point:
 101     // set the termination condition
 102     current_subset.clear();
 103     return;
 104   }
 105 }
 106
 107 } // namespace simgrid::xbt
 108
 109 #endif