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