Quelle bitset.hpp Sprache: C

//
// 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_

quality98%

¤ Dauer der Verarbeitung: 0.15 Sekunden ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.