Library/Range/bit.hpp

• View this file on GitHub
• Last update: 2024-12-27 17:07:26+09:00
• Include: #include "Library/Range/bit.hpp"

Depends on

• Library/Math/Bit.hpp

Verified with

• Test/Range/bit_subset.test.cpp

Code

#pragma once

#include <ranges>

#include "./../Math/Bit.hpp"

namespace mtd {
  namespace ranges {
    struct bit_index_view : public std::ranges::view_interface<bit_index_view> {
      class iterator {
        int i;
        int bit;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::forward_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _bit) : i(ctz(_bit)), bit(_bit) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          bit ^= (1 << i);
          i = ctz(bit);
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return bit == other.bit;
        }
      };

      int bit;

      constexpr explicit bit_index_view(int _bit) : bit(_bit) {}
      constexpr auto begin() const { return iterator(bit); }
      constexpr auto end() const { return iterator(); }
    };

    struct bit_subset_view
        : public std::ranges::view_interface<bit_subset_view> {
      class iterator {
        int i;
        int bit;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::bidirectional_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _bit) : i(_bit), bit(_bit) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          i = (i - 1) & bit;
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return i == other.i;
        }
      };

      int bit;

      constexpr explicit bit_subset_view(int _bit) : bit(_bit) {}
      constexpr auto begin() const { return iterator(bit); }
      constexpr auto end() const { return iterator(); }
    };

    struct bit_supset_view
        : public std::ranges::view_interface<bit_supset_view> {
      class iterator {
        int i;
        int bit;
        int n;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::bidirectional_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _bit, int _n)
            : i(_bit), bit(_bit), n(_n) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          i = (i + 1) | bit;
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return i == other.i && bit == other.bit && n == other.n;
        }
        constexpr auto operator==(const std::default_sentinel_t &) const {
          return i >= (1 << n);
        }
      };

      int bit;
      int n;

      constexpr explicit bit_supset_view(int _bit, int _n) : bit(_bit), n(_n) {}
      constexpr auto begin() const { return iterator(bit, n); }
      constexpr auto end() const { return std::default_sentinel; }
    };

    struct k_bit_subset_view
        : public std::ranges::view_interface<k_bit_subset_view> {
      class iterator {
        int i;
        int n;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::bidirectional_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _n, int _k) : i((1 << _k) - 1), n(_n) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          int x = i & -i;
          int y = i + x;
          i = (((i & ~y) / x) >> 1) | y;
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return i == other.i && n == other.n;
        }
        constexpr auto operator==(const std::default_sentinel_t &) const {
          return i >= (1 << n);
        }
      };

      int n, k;
      constexpr explicit k_bit_subset_view(int _n, int _k) : n(_n), k(_k) {}
      constexpr auto begin() const { return iterator(n, k); }
      constexpr auto end() const { return std::default_sentinel; }
    };
  }  // namespace ranges

  namespace views {
    namespace __detail {
      template <typename... _Args>
      concept __can_bit_index_view = requires {
        ranges::bit_index_view(std::declval<_Args>()...);
      };
      template <typename... _Args>
      concept __can_bit_subset_view = requires {
        ranges::bit_subset_view(std::declval<_Args>()...);
      };
      template <typename... _Args>
      concept __can_bit_supset_view = requires {
        ranges::bit_supset_view(std::declval<_Args>()...);
      };
      template <typename... _Args>
      concept __can_k_bit_subset_view = requires {
        ranges::k_bit_subset_view(std::declval<_Args>()...);
      };
    }  // namespace __detail

    struct _BitIndex {
      template <class... _Tp>
      requires __detail::__can_bit_index_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::bit_index_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _BitIndex bit_index{};

    struct _BitSubsetView {
      template <class... _Tp>
      requires __detail::__can_bit_subset_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::bit_subset_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _BitSubsetView bit_subset{};

    struct _BitSupsetView {
      template <class... _Tp>
      requires __detail::__can_bit_supset_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::bit_supset_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _BitSupsetView bit_supset{};

    struct _KBitSubsetView {
      template <class... _Tp>
      requires __detail::__can_k_bit_subset_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::k_bit_subset_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _KBitSubsetView k_bit_subset{};
  }  // namespace views

}  // namespace mtd

#line 2 "Library/Range/bit.hpp"

#include <ranges>

#line 2 "Library/Math/Bit.hpp"

namespace mtd {

  constexpr unsigned clz(unsigned int x) {
    int c = 0;
    if (x == 0) { return 0; }
    if (x & 0xffff0000) {
      x &= 0xffff0000;
      c |= 0x10;
    }
    if (x & 0xff00ff00) {
      x &= 0xff00ff00;
      c |= 0x08;
    }
    if (x & 0xf0f0f0f0) {
      x &= 0xf0f0f0f0;
      c |= 0x04;
    }
    if (x & 0xcccccccc) {
      x &= 0xcccccccc;
      c |= 0x02;
    }
    if (x & 0xaaaaaaaa) { c |= 0x01; }
    return c + 1;
  }

  constexpr unsigned ctz(unsigned int n) {
    if (!n) return -1;
    unsigned int c = 32;
    n &= -static_cast<signed int>(n);
    if (n) c--;
    if (n & 0x0000FFFF) c -= 16;
    if (n & 0x00FF00FF) c -= 8;
    if (n & 0x0F0F0F0F) c -= 4;
    if (n & 0x33333333) c -= 2;
    if (n & 0x55555555) c -= 1;
    return c;
  }

  constexpr unsigned long long popcount(unsigned long long x) {
    x = x - ((x >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x + (x >> 32);
    return x & 0x0000007f;
  }

}  // namespace mtd
#line 6 "Library/Range/bit.hpp"

namespace mtd {
  namespace ranges {
    struct bit_index_view : public std::ranges::view_interface<bit_index_view> {
      class iterator {
        int i;
        int bit;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::forward_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _bit) : i(ctz(_bit)), bit(_bit) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          bit ^= (1 << i);
          i = ctz(bit);
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return bit == other.bit;
        }
      };

      int bit;

      constexpr explicit bit_index_view(int _bit) : bit(_bit) {}
      constexpr auto begin() const { return iterator(bit); }
      constexpr auto end() const { return iterator(); }
    };

    struct bit_subset_view
        : public std::ranges::view_interface<bit_subset_view> {
      class iterator {
        int i;
        int bit;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::bidirectional_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _bit) : i(_bit), bit(_bit) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          i = (i - 1) & bit;
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return i == other.i;
        }
      };

      int bit;

      constexpr explicit bit_subset_view(int _bit) : bit(_bit) {}
      constexpr auto begin() const { return iterator(bit); }
      constexpr auto end() const { return iterator(); }
    };

    struct bit_supset_view
        : public std::ranges::view_interface<bit_supset_view> {
      class iterator {
        int i;
        int bit;
        int n;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::bidirectional_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _bit, int _n)
            : i(_bit), bit(_bit), n(_n) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          i = (i + 1) | bit;
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return i == other.i && bit == other.bit && n == other.n;
        }
        constexpr auto operator==(const std::default_sentinel_t &) const {
          return i >= (1 << n);
        }
      };

      int bit;
      int n;

      constexpr explicit bit_supset_view(int _bit, int _n) : bit(_bit), n(_n) {}
      constexpr auto begin() const { return iterator(bit, n); }
      constexpr auto end() const { return std::default_sentinel; }
    };

    struct k_bit_subset_view
        : public std::ranges::view_interface<k_bit_subset_view> {
      class iterator {
        int i;
        int n;

      public:
        using difference_type = int;
        using value_type = int;
        using iterator_concept = std::bidirectional_iterator_tag;

        constexpr iterator() = default;
        constexpr explicit iterator(int _n, int _k) : i((1 << _k) - 1), n(_n) {}
        constexpr auto operator*() const { return i; }
        constexpr auto &operator++() {
          int x = i & -i;
          int y = i + x;
          i = (((i & ~y) / x) >> 1) | y;
          return *this;
        }
        constexpr auto operator++(int) { return ++*this; }
        constexpr auto operator==(const iterator &other) const {
          return i == other.i && n == other.n;
        }
        constexpr auto operator==(const std::default_sentinel_t &) const {
          return i >= (1 << n);
        }
      };

      int n, k;
      constexpr explicit k_bit_subset_view(int _n, int _k) : n(_n), k(_k) {}
      constexpr auto begin() const { return iterator(n, k); }
      constexpr auto end() const { return std::default_sentinel; }
    };
  }  // namespace ranges

  namespace views {
    namespace __detail {
      template <typename... _Args>
      concept __can_bit_index_view = requires {
        ranges::bit_index_view(std::declval<_Args>()...);
      };
      template <typename... _Args>
      concept __can_bit_subset_view = requires {
        ranges::bit_subset_view(std::declval<_Args>()...);
      };
      template <typename... _Args>
      concept __can_bit_supset_view = requires {
        ranges::bit_supset_view(std::declval<_Args>()...);
      };
      template <typename... _Args>
      concept __can_k_bit_subset_view = requires {
        ranges::k_bit_subset_view(std::declval<_Args>()...);
      };
    }  // namespace __detail

    struct _BitIndex {
      template <class... _Tp>
      requires __detail::__can_bit_index_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::bit_index_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _BitIndex bit_index{};

    struct _BitSubsetView {
      template <class... _Tp>
      requires __detail::__can_bit_subset_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::bit_subset_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _BitSubsetView bit_subset{};

    struct _BitSupsetView {
      template <class... _Tp>
      requires __detail::__can_bit_supset_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::bit_supset_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _BitSupsetView bit_supset{};

    struct _KBitSubsetView {
      template <class... _Tp>
      requires __detail::__can_k_bit_subset_view<_Tp...>
      constexpr auto operator() [[nodiscard]] (_Tp &&...__e) const {
        return ranges::k_bit_subset_view(std::forward<_Tp>(__e)...);
      }
    };
    inline constexpr _KBitSubsetView k_bit_subset{};
  }  // namespace views

}  // namespace mtd

Back to top page