bitset.h

Go to the documentation of this file.

 
#pragma once
 
#include <array>
#include <cstdint>
#include <cstddef>
 
namespace lampda {
namespace common {
 
template<uint16_t N> class BitSet
{
public:
  using storage_t = uint32_t;
  static constexpr uint16_t storageSize = (N + sizeof(storage_t) * 8 - 1) / (sizeof(storage_t) * 8);
  static constexpr uint16_t bitsPerStorage = sizeof(storage_t) * 8;
 
private:
  std::array<storage_t, storageSize> _data;
 
  static constexpr uint16_t word_index(uint16_t i) noexcept { return i / bitsPerStorage; }
 
  static constexpr storage_t bit_mask(uint16_t i) noexcept { return static_cast<storage_t>(1) << (i % bitsPerStorage); }
 
  static constexpr storage_t last_word_mask() noexcept
  {
    const uint16_t lastWordBits = N % bitsPerStorage;
    if (lastWordBits == 0)
      return static_cast<storage_t>(~storage_t {0});
    storage_t mask = static_cast<storage_t>(1) << lastWordBits;
    return mask - 1;
  }
 
public:
  constexpr BitSet() : _data {} { reset(); }
 
  explicit constexpr BitSet(storage_t value) : _data {}
  {
    for (uint16_t i = 0; i < storageSize - 1; ++i)
      _data[i] = value;
    _data[storageSize - 1] = value & last_word_mask();
  }
 
  void set() noexcept
  {
    storage_t fullMask = static_cast<storage_t>(~storage_t {0});
    for (uint16_t i = 0; i < storageSize - 1; ++i)
      _data[i] = fullMask;
    _data[storageSize - 1] = last_word_mask();
  }
 
  void reset() noexcept
  {
    for (auto& word: _data)
      word = 0;
  }
 
  void set(uint16_t pos) noexcept
  {
    if (pos >= N)
      return;
    _data[word_index(pos)] |= bit_mask(pos);
  }
 
  void set(uint16_t pos, bool value) noexcept
  {
    if (pos >= N)
      return;
    if (value)
      _data[word_index(pos)] |= bit_mask(pos);
    else
      _data[word_index(pos)] &= ~bit_mask(pos);
  }
 
  void reset(uint16_t pos) noexcept
  {
    if (pos >= N)
      return;
    _data[word_index(pos)] &= ~bit_mask(pos);
  }
 
  void flip(uint16_t pos) noexcept
  {
    if (pos >= N)
      return;
    _data[word_index(pos)] ^= bit_mask(pos);
  }
 
  constexpr bool test(uint16_t pos) const noexcept
  {
    if (pos >= N)
      return false;
    return (_data[word_index(pos)] & bit_mask(pos)) != 0;
  }
 
  constexpr bool operator[](uint16_t pos) const noexcept { return test(pos); }
 
  struct reference
  {
    BitSet* parent;
    uint16_t pos;
 
    reference& operator=(bool v) noexcept
    {
      if (pos >= parent->size())
        return *this;
      if (v)
        parent->_data[parent->word_index(pos)] |= parent->bit_mask(pos);
      else
        parent->_data[parent->word_index(pos)] &= ~parent->bit_mask(pos);
      return *this;
    }
 
    reference& operator=(const reference& other) noexcept
    {
      if (pos >= parent->size())
        return *this;
      bool val = other;
      if (val)
        parent->_data[parent->word_index(pos)] |= parent->bit_mask(pos);
      else
        parent->_data[parent->word_index(pos)] &= ~parent->bit_mask(pos);
      return *this;
    }
 
    constexpr operator bool() const noexcept
    {
      if (pos >= parent->size())
        return false;
      return (parent->_data[parent->word_index(pos)] & parent->bit_mask(pos)) != 0;
    }
 
    reference& flip() noexcept
    {
      if (pos >= parent->size())
        return *this;
      parent->_data[parent->word_index(pos)] ^= parent->bit_mask(pos);
      return *this;
    }
  };
 
  reference operator[](uint16_t pos) noexcept { return reference {this, pos}; }
 
  constexpr uint16_t count() const noexcept
  {
    uint16_t total = 0;
    for (const auto& word: _data)
    {
      storage_t w = word;
      while (w)
      {
        total += static_cast<uint16_t>(w & 1);
        w >>= 1;
      }
    }
    return total;
  }
 
  constexpr bool any() const noexcept
  {
    for (const auto& word: _data)
      if (word != 0)
        return true;
    return false;
  }
 
  constexpr bool all() const noexcept
  {
    storage_t fullMask = static_cast<storage_t>(~storage_t {0});
    for (uint16_t i = 0; i < storageSize - 1; ++i)
      if (_data[i] != fullMask)
        return false;
    return (_data[storageSize - 1] & last_word_mask()) == last_word_mask();
  }
 
  constexpr bool none() const noexcept
  {
    for (const auto& word: _data)
      if (word != 0)
        return false;
    return true;
  }
 
  void flip() noexcept
  {
    storage_t fullMask = static_cast<storage_t>(~storage_t {0});
    for (uint16_t i = 0; i < storageSize - 1; ++i)
      _data[i] ^= fullMask;
    _data[storageSize - 1] ^= last_word_mask();
  }
 
  constexpr BitSet<N> operator&(const BitSet<N>& other) const noexcept
  {
    BitSet<N> result;
    for (uint16_t i = 0; i < storageSize; ++i)
      result._data[i] = _data[i] & other._data[i];
    return result;
  }
 
  constexpr BitSet<N> operator|(const BitSet<N>& other) const noexcept
  {
    BitSet<N> result;
    for (uint16_t i = 0; i < storageSize; ++i)
      result._data[i] = _data[i] | other._data[i];
    return result;
  }
 
  constexpr BitSet<N> operator-(const BitSet<N>& other) const noexcept
  {
    BitSet<N> result;
    for (uint16_t i = 0; i < storageSize; ++i)
      result._data[i] = _data[i] & ~other._data[i];
    return result;
  }
 
  BitSet<N> operator~() const noexcept
  {
    BitSet<N> result;
    storage_t fullMask = static_cast<storage_t>(~storage_t {0});
    for (uint16_t i = 0; i < storageSize - 1; ++i)
      result._data[i] = ~_data[i];
    result._data[storageSize - 1] = ~_data[storageSize - 1] & last_word_mask(); // <-- use helper
    return result;
  }
 
  BitSet<N>& operator&=(const BitSet<N>& other) noexcept
  {
    for (uint16_t i = 0; i < storageSize; ++i)
      _data[i] &= other._data[i];
    return *this;
  }
 
  BitSet<N>& operator|=(const BitSet<N>& other) noexcept
  {
    for (uint16_t i = 0; i < storageSize; ++i)
      _data[i] |= other._data[i];
    return *this;
  }
 
  BitSet<N>& operator^=(const BitSet<N>& other) noexcept
  {
    for (uint16_t i = 0; i < storageSize; ++i)
      _data[i] ^= other._data[i];
    return *this;
  }
 
  constexpr bool operator==(const BitSet<N>& other) const noexcept
  {
    for (uint16_t i = 0; i < storageSize; ++i)
      if (_data[i] != other._data[i])
        return false;
    return true;
  }
 
  constexpr bool operator!=(const BitSet<N>& other) const noexcept { return not operator==(other); }
 
  static constexpr uint16_t size() noexcept { return N; }
 
  static constexpr uint16_t size_words() noexcept { return storageSize; }
};
 
} // namespace common
} // namespace lampda