X-Git-Url: http://bilbo.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/blobdiff_plain/e1f88a566aca6e3072f9158aabe6a33c5de343e3..3f4f5e63dadc0023c0a02a08af8e9e9801b38e8e:/src/xbt/utils/iter/subsets.hpp diff --git a/src/xbt/utils/iter/subsets.hpp b/src/xbt/utils/iter/subsets.hpp index eb8c8ff874..ec3cac8377 100644 --- a/src/xbt/utils/iter/subsets.hpp +++ b/src/xbt/utils/iter/subsets.hpp @@ -1,5 +1,3 @@ -/* A thread pool (C++ version). */ - /* Copyright (c) 2004-2023 The SimGrid Team. All rights reserved. */ /* This program is free software; you can redistribute it and/or modify it @@ -8,6 +6,7 @@ #ifndef XBT_UTILS_ITER_SUBSETS_HPP #define XBT_UTILS_ITER_SUBSETS_HPP +#include #include #include #include @@ -15,51 +14,37 @@ namespace simgrid::xbt { -// template struct LazyPowerSet { -// }; - -// template struct LazyKSubsets { -// private: -// const Iterable& universe; - -// public: -// LazyKSubsets(const Iterable& universe) : universe(universe) {} -// }; - -template struct subsets_iterator { - - subsets_iterator(unsigned k); - subsets_iterator(unsigned k, Iterator begin, Iterator end = Iterator()); - - subsets_iterator& operator++(); - auto operator->() const { return ¤t_subset; } - auto& operator*() const { return current_subset; } - - bool operator==(const subsets_iterator& other) const - { - if (this->k != other.k) { - return false; - } - if (this->k == 0) { - return true; - } - return this->P[0] == other.P[0]; - } - bool operator!=(const subsets_iterator& other) const { return not(this->operator==(other)); } - - using iterator_category = std::forward_iterator_tag; - using difference_type = int; // # of steps between - using value_type = std::vector; - using pointer = value_type*; - using reference = value_type&; +/** + * @brief A higher-order forward-iterator which traverses all possible subsets + * of a given fixed size `k` of an iterable sequence + * + * @class Iterator: The iterator over which this higher-order iterator + * generates elements. + */ +template +struct subsets_iterator : public boost::iterator_facade, const std::vector, + boost::forward_traversal_tag> { + subsets_iterator(); + explicit subsets_iterator(unsigned k); + explicit subsets_iterator(unsigned k, Iterator begin, Iterator end = Iterator()); private: - unsigned k; + unsigned k; // The size of the subsets generated std::optional end = std::nullopt; std::vector current_subset; - std::vector P; + std::vector P; // Increment counts to determine which combinations need to be traversed + + // boost::iterator_facade<...> interface to implement + void increment(); + bool equal(const subsets_iterator& other) const; + const std::vector& dereference() const; + + // Allows boost::iterator_facade<...> to function properly + friend class boost::iterator_core_access; }; +template subsets_iterator::subsets_iterator() : subsets_iterator(0) {} + template subsets_iterator::subsets_iterator(unsigned k) : k(k), current_subset(std::vector(k)), P(std::vector(k)) @@ -86,45 +71,96 @@ subsets_iterator::subsets_iterator(unsigned k, Iterator begin, Iterato std::iota(P.begin(), P.end(), 0); } -template subsets_iterator& subsets_iterator::operator++() +template bool subsets_iterator::equal(const subsets_iterator& other) const { + if (this->end == std::nullopt && other.end == std::nullopt) { + return true; + } + if (this->k != other.k) { + return false; + } + if (this->k == 0) { // this->k == other.k == 0 + return true; + } + return this->end != std::nullopt && other.end != std::nullopt && this->P[0] == other.P[0]; +} + +template const std::vector& subsets_iterator::dereference() const +{ + return this->current_subset; +} + +template void subsets_iterator::increment() +{ + // If k == 0, there's nothing to do + // If end == std::nullopt, we've finished + // iterating over all subsets of size `k` if (end == std::nullopt || k == 0) { - return *this; + return; } // Move the last element over each time ++current_subset[k - 1]; ++P[k - 1]; - const auto end = this->end.value(); - const bool shift_other_elements = current_subset[k - 1] == end; + const bool shift_other_elements = current_subset[k - 1] == end.value(); if (shift_other_elements) { + if (k == 1) { + // We're done in the case that k = 1; here, we've iterated + // through the list once, which is all that is needed + end = std::nullopt; + return; + } + + // At this point, k >= 2 + // The number of elements is now equal to the "index" // of the last element (it is at the end, which means we added - // for the finalth time) + // for the last time) const unsigned n = P[k - 1]; - auto l = 0; - for (int j = static_cast(k - 2); j >= 0; j--) { + // We're looking to determine + // + // argmax_{0 <= j <= k - 2}(P[j] != (n - (k - j))) + // + // If P[j] == (n - (k - j)) for some `j`, that means + // the `j`th element of the current subset has moved + // "as far as it can move" to the right; in other words, + // this is our signal that some element before the `j`th + // has to move over + // + // std::max_element() would work here too, but it seems + // overkill to create a vector full of numbers when a simple + // range-based for-loop can do the trick + unsigned l = 0; + for (unsigned j = k - 2; j > 0; j--) { if (P[j] != (n - (k - j))) { l = j; break; } } - P[l] += 1; + ++P[l]; + ++current_subset[l]; - if (l == 0 and P[0] > (n - k)) { - return *this; + // Plugging in `j = 0` to the above formula yields + // `n - k`, which is the furthest point that the first (i.e. `0th`) + // element can be located. Thus, if `P[0] > (n - k)`, this means + // we've sucessfully iterated through all subsets so we're done + if (P[0] > (n - k)) { + end = std::nullopt; + return; } + // Otherwise, all elements past element `l` are reset + // to follow one after another immediately after `l` + auto iter_at_l = current_subset[l]; for (auto i = l + 1; i <= (k - 1); i++) { - P[i] = P[l] + (i - l); + P[i] = P[l] + (i - l); + current_subset[i] = ++iter_at_l; } } - - return *this; } } // namespace simgrid::xbt