src/xbt/utils/iter/powerset.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_POWERSET_HPP
   7 #define XBT_UTILS_ITER_POWERSET_HPP
   8
   9 #include "src/xbt/utils/iter/subsets.hpp"
  10
  11 #include <boost/iterator/iterator_facade.hpp>
  12 #include <optional>
  13
  14 namespace simgrid::xbt {
  15
  16 /**
  17  * @brief A higher-order iterator which traverses all possible subsets
  18  * of the elements of an iterable sequence.
  19  *
  20  * @note The power set `P(S)` of any finite set `S` is of exponential size relative
  21  * to the size of `S`. Be warned that attempting to iterate over the power set of
  22  * large sets will cost a LOT of time (but that the memory footprint will remain
  23  * very small). Alas, unless P = NP, there sometimes isn't a better known way to
  24  * solve a problem (e.g. determining all cliques in a graph)
  25  *
  26  * @class Iterator: The iterator over which this higher-order iterator
  27  * generates elements
  28  */
  29 template <class Iterator>
  30 struct powerset_iterator : public boost::iterator_facade<powerset_iterator<Iterator>, const std::vector<Iterator>,
  31                                                          boost::forward_traversal_tag> {
  32   powerset_iterator()                                                                 = default;
  33   explicit powerset_iterator(Iterator begin, Iterator end = Iterator());
  34
  35 private:
  36   // The current size of the subsets
  37   unsigned n = 0;
  38   std::optional<Iterator> iterator_begin;
  39   std::optional<Iterator> iterator_end;
  40   std::optional<subsets_iterator<Iterator>> current_subset_iter     = std::nullopt;
  41   std::optional<subsets_iterator<Iterator>> current_subset_iter_end = std::nullopt;
  42
  43   // boost::iterator_facade<...> interface to implement
  44   void increment();
  45   bool equal(const powerset_iterator<Iterator>& other) const;
  46   const std::vector<Iterator>& dereference() const;
  47
  48   // Allows boost::iterator_facade<...> to function properly
  49   friend class boost::iterator_core_access;
  50 };
  51
  52 template <typename Iterator>
  53 powerset_iterator<Iterator>::powerset_iterator(Iterator begin, Iterator end)
  54     : iterator_begin({begin})
  55     , iterator_end({end})
  56     , current_subset_iter({subsets_iterator<Iterator>(0, begin, end)})
  57     , current_subset_iter_end({subsets_iterator<Iterator>(0)})
  58 {
  59 }
  60
  61 template <typename Iterator> bool powerset_iterator<Iterator>::equal(const powerset_iterator<Iterator>& other) const
  62 {
  63   return current_subset_iter == other.current_subset_iter;
  64 }
  65
  66 template <typename Iterator> const std::vector<Iterator>& powerset_iterator<Iterator>::dereference() const
  67 {
  68   if (current_subset_iter.has_value()) {
  69     return *current_subset_iter.value();
  70   }
  71   static const std::vector<Iterator> empty_subset;
  72   return empty_subset;
  73 }
  74
  75 template <typename Iterator> void powerset_iterator<Iterator>::increment()
  76 {
  77   if (not current_subset_iter.has_value() || not current_subset_iter_end.has_value() ||
  78       not current_subset_iter.has_value() || not iterator_end.has_value()) {
  79     return; // We've traversed all subsets at this point, or we're the "last" iterator
  80   }
  81
  82   // Move the underlying subset iterator over
  83   ++current_subset_iter.value();
  84
  85   // If the current underlying subset iterator for size `n`
  86   // is finished, generate one for `n = n + 1`
  87   if (current_subset_iter == current_subset_iter_end) {
  88     n++;
  89     current_subset_iter     = {subsets_iterator<Iterator>(n, iterator_begin.value(), iterator_end.value())};
  90     current_subset_iter_end = {subsets_iterator<Iterator>(n)};
  91
  92     // If we've immediately hit a deadend, then we know that the last
  93     // value of `n` was the number of elements in the iteration, so
  94     // we're done
  95     if (current_subset_iter == current_subset_iter_end) {
  96       current_subset_iter     = std::nullopt;
  97       current_subset_iter_end = std::nullopt;
  98     }
  99   }
 100 }
 101
 102 } // namespace simgrid::xbt
 103
 104 #endif