1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#pragma once


#include <cassert><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.
#include <tuple><--- Include file:  not found. Please note: Cppcheck does not need standard library headers to get proper results.

#include "internal/dev_env.hpp"
#include "internal/iterator.hpp"
#include "internal/types.hpp"

#include "numeric/arithmetic.hpp"
#include "numeric/bit.hpp"


namespace uni {


template<std::unsigned_integral T>
struct subset_enumerator {
    using value_type = T;
    using size_type = internal::size_t;

  private:
    T _n = 0;

  protected:
    using iterator_interface = internal::bidirectional_iterator_interface<const value_type>;

  public:
    // Enumerate tuple of (q, l, r), which means (floor/ceil)(_n/k) == q (l <= k <= r).
    subset_enumerator(const T n) noexcept(NO_EXCEPT) : _n(n) { assert(n >= 0); }

    struct iterator;
    using const_iterator = iterator;

    inline auto begin() noexcept(NO_EXCEPT) { return iterator(this->_n, this->_n); }
    inline auto end() noexcept(NO_EXCEPT) { return iterator(this->_n, 0, true); }

    inline auto rbegin() noexcept(NO_EXCEPT) { return std::make_reverse_iterator(this->end()); }
    inline auto rend() noexcept(NO_EXCEPT) { return std::make_reverse_iterator(this->begin()); }

    inline auto size() noexcept(NO_EXCEPT) { return static_cast<size_type>(1) << std::popcount(this->_n); }

    struct iterator : iterator_interface {
      protected:
        value_type _n = 0, _v = 0;
        bool _end = false;

      public:
        iterator() noexcept = default;
        iterator(const T n, const T v, const bool end = false) noexcept(NO_EXCEPT) : _n(n), _v(v), _end(end) {};


        friend inline bool operator==(const iterator& lhs, const iterator& rhs) noexcept(NO_EXCEPT) {
            if(rhs._end) return lhs._end;
            if(lhs._end) return false;

            return lhs._v == rhs._v;
        };

        friend inline auto operator<=>(const iterator& lhs, const iterator& rhs) noexcept(NO_EXCEPT) {
            if(rhs._end) {
                if(lhs._end) return std::partial_ordering::equivalent;
                return std::partial_ordering::less;
            }
            if(lhs._end) {
                return std::partial_ordering::greater;
            }

            return comapre_as_bitset(rhs._v, lhs._v);
        };


        inline auto operator*() const noexcept(NO_EXCEPT) { return this->_v; }

        inline auto& operator++() noexcept(NO_EXCEPT) {
            if(this->_v == 0) {
                this->_end = true;
            }
            else {
                this->_v = (this->_v - 1) & this->_n;
            }

            return *this;
        }

        inline auto& operator--() noexcept(NO_EXCEPT) {
            if(this->_end) {
                this->_end = false;
            }
            else {
                const auto lsb = lowest_bit_pos(this->_n & ~this->_v);
                this->_v = ((this->_v >> lsb) | 1) << lsb;
            }

            return *this;
        }

        inline auto operator++(int) noexcept(NO_EXCEPT) { auto res = *this; ++res; return res; }
        inline auto operator--(int) noexcept(NO_EXCEPT) { auto res = *this; --res; return res; }
    };

};


} // namespace uni


namespace std::ranges {

template<class T>
inline constexpr bool enable_borrowed_range<uni::subset_enumerator<T>> = true;

} // namespace std::ranges