Quelle  bitset.hpp

//
// libsemigroups - C++ library for semigroups and monoids
// Copyright (C) 2020 James D. Mitchell
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//

// TODO(later)
// 1) doc

#ifndef LIBSEMIGROUPS_BITSET_HPP_
#define LIBSEMIGROUPS_BITSET_HPP_

#include <array>        // for array
#include <bitset>       // for bitset
#include <climits>      // for CHAR_BIT
#include <cstddef>      // for size_t
#include <iosfwd>       // for operator<<, ostringstream
#include <type_traits>  // for false_type
#include <utility>      // for hash

#include "config.hpp"     // for LIBSEMIGROUPS_SIZEOF_VOID_P
#include "debug.hpp"      // for LIBSEMIGROUPS_ASSERT
#include "exception.hpp"  // for LIBSEMIGROUPS_EXCEPTION
#include "string.hpp"     // for detail::to_string

namespace libsemigroups {

  // The code below for popcnt is borrowed/adapted from GAP.

#if LIBSEMIGROUPS_USE_POPCNT && defined(LIBSEMIGROUPS_HAVE___BUILTIN_POPCOUNTL)
  template <typename T>
  static inline size_t COUNT_TRUES_BLOCK(T block) {
    return __builtin_popcountl(block);
  }
#else
#if LIBSEMIGROUPS_SIZEOF_VOID_P == 8
  template <typename T>
  static inline auto COUNT_TRUES_BLOCK(T block)
      -> std::enable_if_t<sizeof(T) == 8, size_t> {
    block
        = (block & 0x5555555555555555L) + ((block >> 1) & 0x5555555555555555L);
    block
        = (block & 0x3333333333333333L) + ((block >> 2) & 0x3333333333333333L);
    block = (block + (block >> 4)) & 0x0f0f0f0f0f0f0f0fL;
    block = (block + (block >> 8));
    block = (block + (block >> 16));
    block = (block + (block >> 32)) & 0x00000000000000ffL;
    return block;
  }
#endif

  template <typename T>
  static inline auto COUNT_TRUES_BLOCK(T block)
      -> std::enable_if_t<sizeof(T) == 4, size_t> {
    block = (block & 0x55555555) + ((block >> 1) & 0x55555555);
    block = (block & 0x33333333) + ((block >> 2) & 0x33333333);
    block = (block + (block >> 4)) & 0x0f0f0f0f;
    block = (block + (block >> 8));
    block = (block + (block >> 16)) & 0x000000ff;
    return block;
  }

  template <typename T>
  static inline auto COUNT_TRUES_BLOCK(T block)
      -> std::enable_if_t<sizeof(T) == 2, size_t> {
    block = (block & 0x5555) + ((block >> 1) & 0x5555);
    block = (block & 0x3333) + ((block >> 2) & 0x3333);
    block = (block + (block >> 4)) & 0x0f0f;
    block = (block + (block >> 8)) & 0x00ff;
    return block;
  }

  template <typename T>
  static inline auto COUNT_TRUES_BLOCK(T block)
      -> std::enable_if_t<sizeof(T) == 1, size_t> {
    static constexpr std::array<size_t, 256> const lookup = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4,
        2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4,
        2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
        4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5,
        3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6,
        4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
    return lookup[block];
  }
#endif

  template <size_t N>
  class BitSet {
    static_assert(N > 0, "BitSet does not support 0 entries");
#if LIBSEMIGROUPS_SIZEOF_VOID_P == 8
    static_assert(N <= 64, "BitSet does not support more than 64 entries");
#else
    static_assert(N <= 32, "BitSet does not support more than 32 entries");
#endif

   public:
    using block_type = std::conditional_t<
        N <= 8,
        uint_fast8_t,
        std::conditional_t<
            N <= 16,
            uint_fast16_t,
            std::conditional_t<N <= 32, uint_fast32_t, uint64_t>>>;

    explicit constexpr BitSet(block_type block) noexcept : _block(block) {}
    constexpr BitSet() noexcept : BitSet(0) {}
    constexpr BitSet(BitSet const&) noexcept  = default;
    constexpr BitSet(BitSet&&) noexcept       = default;
    BitSet& operator=(BitSet const&) noexcept = default;
    BitSet& operator=(BitSet&&) noexcept      = default;

    template <typename T>
    BitSet(T first, T last) : BitSet() {
      LIBSEMIGROUPS_ASSERT(first <= last);
      size_t const K = std::distance(first, last);
      if (K > size()) {
        LIBSEMIGROUPS_EXCEPTION(
            "the size of the container is %llu, trying to initialize with %llu "
            "items",
            static_cast<uint64_t>(size()),
            static_cast<uint64_t>(K))
      }
      auto it = first;
      for (size_t i = 0; i < K; ++i, ++it) {
        set(i, *it);
      }
    }

    ~BitSet() = default;

    // Could be static
    constexpr size_t size() const noexcept {
      return N;
    }

    static constexpr size_t max_size() noexcept {
#if LIBSEMIGROUPS_SIZEOF_VOID_P == 8
      return 64;
#else
      return 32;
#endif
    }

    bool operator<(BitSet const& that) const noexcept {
      clear_hi_bits();
      that.clear_hi_bits();
      return _block < that._block;
    }

    bool operator==(BitSet const& that) const noexcept {
      clear_hi_bits();
      that.clear_hi_bits();
      return _block == that._block;
    }

    bool operator!=(BitSet const& that) const noexcept {
      return !(*this == that);
    }

    void operator&=(BitSet const& that) const noexcept {
      _block &= that._block;
    }

    BitSet<N> operator&(BitSet const& that) const noexcept {
      return BitSet(_block & that._block);
    }

    void operator|=(BitSet const& that) const noexcept {
      _block |= that._block;
    }

    bool test(size_t pos) const noexcept {
      LIBSEMIGROUPS_ASSERT(pos < N);
      return _block & mask(pos);
    }

    bool operator[](size_t pos) const noexcept {
      return test(pos);
    }

    BitSet& set() noexcept {
      _block = ~0;
      return *this;
    }

    BitSet& set(size_t pos, bool value = true) noexcept {
      LIBSEMIGROUPS_ASSERT(pos < N);
      if (value) {
        _block |= mask(pos);
      } else {
        _block &= ~mask(pos);
      }
      return *this;
    }

    BitSet& set(size_t first, size_t last, bool value) noexcept {
      LIBSEMIGROUPS_ASSERT(first < N);
      LIBSEMIGROUPS_ASSERT(last <= N);
      LIBSEMIGROUPS_ASSERT(first < last);
      block_type m = ~0;
      m            = (m >> first);
      m            = (m << (first + (block_count() - last)));
      m            = (m >> (block_count() - last));
      if (value) {
        _block |= m;
      } else {
        _block &= ~m;
      }
      return *this;
    }

    BitSet& reset() noexcept {
      _block = 0;
      return *this;
    }

    BitSet& reset(size_t pos) noexcept {
      LIBSEMIGROUPS_ASSERT(pos < N);
      _block &= ~mask(pos);
      return *this;
    }

    BitSet& reset(size_t first, size_t last) {
      LIBSEMIGROUPS_ASSERT(first < N);
      LIBSEMIGROUPS_ASSERT(last <= N);
      LIBSEMIGROUPS_ASSERT(first < last);
      return set(first, last, false);
    }

    size_t count() const noexcept {
      clear_hi_bits();
      return COUNT_TRUES_BLOCK(_block);
    }

    template <typename S>
    void apply(S&& func) const {
#if LIBSEMIGROUPS_USE_CLZLL && defined(LIBSEMIGROUPS_HAVE___BUILTIN_CLZLL)
      block_type block = _block;
      while (block != 0) {
        block_type t = block & -block;
        size_t     i = static_cast<size_t>(__builtin_ctzll(block));
        if (i >= size()) {
          break;
        }
        func(i);
        block ^= t;
      }
#else
      for (size_t i = 0; i < size(); ++i) {
        if (test(i)) {
          func(i);
        }
      }
#endif
    }

    block_type to_int() const noexcept {
      clear_hi_bits();
      return _block;
    }

    friend std::ostringstream& operator<<(std::ostringstream& os,
                                          BitSet<N> const&    bs) {
      for (size_t i = 0; i < N; ++i) {
        os << bs.test(i);
      }
      return os;
    }

    friend std::ostream& operator<<(std::ostream& os, BitSet<N> const& bs) {
      os << detail::to_string(bs);
      return os;
    }

   private:
    void clear_hi_bits() const noexcept {
      size_t s = block_count() - N;
      _block   = _block << s;
      _block   = _block >> s;
    }

    constexpr size_t block_count() const noexcept {
      return sizeof(block_type) * CHAR_BIT;
    }

    constexpr block_type mask(size_t i) const noexcept {
      // LIBSEMIGROUPS_ASSERT(i < size());
      return static_cast<block_type>(MASK[i]);
    }

    static constexpr uint64_t MASK[64] = {0x1,
                                          0x2,
                                          0x4,
                                          0x8,
                                          0x10,
                                          0x20,
                                          0x40,
                                          0x80,
                                          0x100,
                                          0x200,
                                          0x400,
                                          0x800,
                                          0x1000,
                                          0x2000,
                                          0x4000,
                                          0x8000,
                                          0x10000,
                                          0x20000,
                                          0x40000,
                                          0x80000,
                                          0x100000,
                                          0x200000,
                                          0x400000,
                                          0x800000,
                                          0x1000000,
                                          0x2000000,
                                          0x4000000,
                                          0x8000000,
                                          0x10000000,
                                          0x20000000,
                                          0x40000000,
                                          0x80000000,
                                          0x100000000,
                                          0x200000000,
                                          0x400000000,
                                          0x800000000,
                                          0x1000000000,
                                          0x2000000000,
                                          0x4000000000,
                                          0x8000000000,
                                          0x10000000000,
                                          0x20000000000,
                                          0x40000000000,
                                          0x80000000000,
                                          0x100000000000,
                                          0x200000000000,
                                          0x400000000000,
                                          0x800000000000,
                                          0x1000000000000,
                                          0x2000000000000,
                                          0x4000000000000,
                                          0x8000000000000,
                                          0x10000000000000,
                                          0x20000000000000,
                                          0x40000000000000,
                                          0x80000000000000,
                                          0x100000000000000,
                                          0x200000000000000,
                                          0x400000000000000,
                                          0x800000000000000,
                                          0x1000000000000000,
                                          0x2000000000000000,
                                          0x4000000000000000,
                                          0x8000000000000000};
    mutable block_type        _block;
  };

  template <size_t N>
  constexpr uint64_t BitSet<N>::MASK[64];

  namespace detail {
    template <typename T>
    struct IsBitSetHelper : std::false_type {};

    template <size_t N>
    struct IsBitSetHelper<BitSet<N>> : std::true_type {};
  }  // namespace detail

  template <typename T>
  static constexpr bool IsBitSet = detail::IsBitSetHelper<T>::value;

  namespace detail {
    struct LessBitSet {
      // not noexcept because std::bitset<N>::to_ullong throws
      // std::overflow_error if N exceeds the capacity of a unsigned long
      // long.
      template <size_t N>
      bool operator()(std::bitset<N> const& x, std::bitset<N> const& y) const {
        return x.to_ullong() < y.to_ullong();
      }

      template <size_t N>
      bool operator()(BitSet<N> const& x, BitSet<N> const& y) const noexcept {
        return x < y;
      }
    };
  }  // namespace detail
}  // namespace libsemigroups

namespace std {
  template <size_t N>
  struct hash<libsemigroups::BitSet<N>> {
    using block_type = typename libsemigroups::BitSet<N>::block_type;
    size_t operator()(libsemigroups::BitSet<N> const& bs) const noexcept(
        std::is_nothrow_default_constructible<hash<block_type>>::value) {
      return hash<block_type>()(bs.to_int());
    }
  };
}  // namespace std
#endif  // LIBSEMIGROUPS_BITSET_HPP_