dynamic_bitset.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// Copyright (c) 2022 deCODE Genetics
// Copyright (c) 2006-2020, Knut Reinert & Freie Universität Berlin
// Copyright (c) 2016-2020, Knut Reinert & MPI für molekulare Genetik
// This file may be used, modified and/or redistributed under the terms of the 3-clause BSD-License
// shipped with this file and also available at: https://github.com/biocpp/biocpp-core/blob/main/LICENSE.md
// -----------------------------------------------------------------------------------------------------
 
#pragma once
 
#include <bit>
 
#include <bio/meta/detail/int_types.hpp>
#include <bio/ranges/to.hpp>
#include <bio/ranges/views/interleave.hpp>
#include <bio/ranges/views/repeat_n.hpp>
 
namespace bio::ranges::detail
{
 
struct dynamic_bitset_bitfield
{
    uint64_t size : 6u;
    uint64_t bits : 58u;
};
 
class dynamic_bitset_reference_proxy
{
public:
    constexpr dynamic_bitset_reference_proxy()                                                = delete;  
    constexpr dynamic_bitset_reference_proxy(dynamic_bitset_reference_proxy const &) noexcept = default; 
    constexpr dynamic_bitset_reference_proxy(dynamic_bitset_reference_proxy &&) noexcept      = default; 
 
    constexpr dynamic_bitset_reference_proxy const & operator=(dynamic_bitset_reference_proxy const rhs) const noexcept
    {
        rhs ? set() : reset();
        return *this;
    }
 
    constexpr dynamic_bitset_reference_proxy const & operator=(bool const value) const noexcept
    {
        value ? set() : reset();
        return *this;
    }
 
    ~dynamic_bitset_reference_proxy() noexcept = default; 
 
    constexpr dynamic_bitset_reference_proxy(dynamic_bitset_bitfield & internal_, size_t const pos) noexcept :
      internal{internal_}, mask{1ULL << pos}
    {}
 
    constexpr operator bool() const noexcept { return static_cast<bool>(internal.bits & mask); }
 
    constexpr bool operator~() const noexcept { return !static_cast<bool>(internal.bits & mask); }
 
    constexpr dynamic_bitset_reference_proxy const & operator|=(bool const value) const noexcept
    {
        if (value)
            set();
 
        return *this;
    }
 
    constexpr dynamic_bitset_reference_proxy const & operator&=(bool const value) const noexcept
    {
        if (!value)
            reset();
 
        return *this;
    }
 
    constexpr dynamic_bitset_reference_proxy const & operator^=(bool const value) const noexcept
    {
        operator bool() && value ? reset() : set();
        return *this;
    }
 
private:
    dynamic_bitset_bitfield & internal;
    uint64_t                  mask;
 
    constexpr void set() const noexcept { internal.bits |= mask; }
 
    constexpr void reset() const noexcept { internal.bits &= ~mask; }
};
 
} // namespace bio::ranges::detail
 
namespace bio::ranges
{
 
template <size_t bit_capacity = 58>
class dynamic_bitset
{
private:
    template <size_t>
    friend class dynamic_bitset;
 
    detail::dynamic_bitset_bitfield data{
      0u,
      0u}; // Specifying values prevents ICE on gcc < 9 when comparing to default constructed bitset
 
public:
    static_assert(bit_capacity <= 58, "The capacity of the dynamic_bitset exceeds the limit of 58.");
 
    using value_type      = bool;
    using reference       = detail::dynamic_bitset_reference_proxy;
    using const_reference = bool;
    using iterator        = detail::random_access_iterator<dynamic_bitset>;
    using const_iterator  = detail::random_access_iterator<dynamic_bitset const>;
    using difference_type = ptrdiff_t;
    using size_type       = meta::detail::min_viable_uint_t<bit_capacity>;
 
    // this signals to range-v3 that something is a container :|
    using allocator_type = void;
 
    constexpr dynamic_bitset() noexcept                                   = default; 
    constexpr dynamic_bitset(dynamic_bitset const &) noexcept             = default; 
    constexpr dynamic_bitset(dynamic_bitset &&) noexcept                  = default; 
    constexpr dynamic_bitset & operator=(dynamic_bitset const &) noexcept = default; 
    constexpr dynamic_bitset & operator=(dynamic_bitset &&) noexcept      = default; 
    ~dynamic_bitset() noexcept                                            = default; 
 
    constexpr dynamic_bitset(uint64_t const value)
    {
        if (std::popcount(value >> 58) != 0)
            throw std::invalid_argument{"The dynamic_bitset can be at most 58 long."};
        data.bits = value;
        data.size = std::bit_width(value);
    }
 
    template <std::forward_iterator begin_it_type, typename end_it_type>
        requires(std::sentinel_for<end_it_type, begin_it_type> &&
                 std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>)
    constexpr dynamic_bitset(begin_it_type begin_it, end_it_type end_it) noexcept : dynamic_bitset{}
    {
        assign(begin_it, end_it);
    }
 
    template <meta::different_from<dynamic_bitset> other_range_t>
        requires std::ranges::input_range<other_range_t>
    explicit constexpr dynamic_bitset(other_range_t && range) noexcept :
      dynamic_bitset{std::ranges::begin(range), std::ranges::end(range)}
    {}
 
    constexpr dynamic_bitset(size_type const n, value_type const value) noexcept : dynamic_bitset{}
    {
        assign(n, value);
    }
 
    constexpr dynamic_bitset & operator=(std::initializer_list<value_type> const ilist) noexcept
    {
        assign(std::ranges::begin(ilist), std::ranges::end(ilist));
        return *this;
    }
 
    template <size_t N>
    constexpr dynamic_bitset(char const (&lit)[N]) : dynamic_bitset{}
    {
        static_assert(N <= bit_capacity + 1, "Length of string literal exceeds capacity of dynamic_bitset.");
        assign(lit);
    }
 
    template <size_t N>
    constexpr dynamic_bitset & operator=(char const (&lit)[N])
    {
        static_assert(N <= bit_capacity + 1, "Length of string literal exceeds capacity of dynamic_bitset.");
        assign(lit);
        return *this;
    }
 
    template <size_t N>
    constexpr void assign(char const (&lit)[N])
    {
        static_assert(N <= bit_capacity + 1, "Length of string literal exceeds capacity of dynamic_bitset.");
        assert(lit[N - 1] == '\0');
        uint64_t value{};
 
        for (size_t i = 0; i != N - 1; ++i)
        {
            if (lit[i] == '0')
            {
                value <<= 1;
            }
            else if (lit[i] == '1')
            {
                value <<= 1;
                value |= 1u;
            }
            else
            {
                throw std::invalid_argument{"The string to construct a dynamic_bitset from may only contain 0 and 1."};
            }
        }
 
        *this = value;
        resize(N - 1);
    }
 
    constexpr void assign(std::initializer_list<value_type> const ilist) noexcept
    {
        assign(std::ranges::begin(ilist), std::ranges::end(ilist));
    }
 
    constexpr void assign(size_type const count, value_type const value) noexcept
    {
        clear();
        auto tmp = views::repeat_n(value, count);
        assign(std::ranges::begin(tmp), std::ranges::end(tmp));
    }
 
    template <std::ranges::input_range other_range_t>
        requires std::constructible_from<value_type, std::ranges::range_reference_t<other_range_t>>
    constexpr void assign(other_range_t && range) noexcept
    {
        assign(std::ranges::begin(range), std::ranges::end(range));
    }
 
    template <std::forward_iterator begin_it_type, typename end_it_type>
        requires(std::sentinel_for<end_it_type, begin_it_type> &&
                 std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>)
    constexpr void assign(begin_it_type begin_it, end_it_type end_it) noexcept
    {
        clear();
        insert(cbegin(), begin_it, end_it);
    }
 
    constexpr iterator begin() noexcept { return iterator{*this}; }
 
    constexpr const_iterator begin() const noexcept { return const_iterator{*this}; }
 
    constexpr const_iterator cbegin() const noexcept { return begin(); }
 
    constexpr iterator end() noexcept { return iterator{*this, size()}; }
 
    constexpr const_iterator end() const noexcept { return const_iterator{*this, size()}; }
 
    constexpr const_iterator cend() const noexcept { return end(); }
 
    constexpr dynamic_bitset & operator&=(dynamic_bitset const & rhs) noexcept
    {
        assert(size() == rhs.size());
        data.bits &= rhs.data.bits;
        return *this;
    }
 
    constexpr dynamic_bitset & operator|=(dynamic_bitset const & rhs) noexcept
    {
        assert(size() == rhs.size());
        data.bits |= rhs.data.bits;
        return *this;
    }
 
    constexpr dynamic_bitset & operator^=(dynamic_bitset const & rhs) noexcept
    {
        assert(size() == rhs.size());
        data.bits ^= rhs.data.bits;
        return *this;
    }
 
    constexpr dynamic_bitset operator~() const noexcept
    {
        dynamic_bitset tmp{*this};
        tmp.flip();
        return tmp;
    }
 
    constexpr dynamic_bitset & operator<<=(size_t const count) noexcept
    {
        assert(count > 0);
        assert(count < size());
        data.bits <<= count;
        data.bits &= (1ULL << size()) - 1ULL;
        return *this;
    }
 
    constexpr dynamic_bitset & operator>>=(size_t const count) noexcept
    {
        assert(count > 0);
        assert(count < size());
        data.bits >>= count;
        return *this;
    }
 
    constexpr dynamic_bitset operator>>(size_t const count) const noexcept
    {
        assert(count > 0);
        assert(count < size());
        dynamic_bitset tmp{*this};
        tmp >>= count;
        return tmp;
    }
 
    constexpr dynamic_bitset operator<<(size_t const count) const noexcept
    {
        assert(count > 0);
        assert(count < size());
        dynamic_bitset tmp{*this};
        tmp <<= count;
        return tmp;
    }
 
    constexpr dynamic_bitset & set() noexcept
    {
        data.bits |= (1ULL << size()) - 1ULL;
        return *this;
    }
 
    constexpr dynamic_bitset & set(size_t const i, bool const value = true)
    {
        at(i) = value;
        return *this;
    }
 
    constexpr dynamic_bitset & reset() noexcept
    {
        data.bits = 0u;
        return *this;
    }
 
    constexpr dynamic_bitset & reset(size_t const i)
    {
        set(i, false);
        return *this;
    }
 
    constexpr dynamic_bitset & flip() noexcept
    {
        data.bits = ~data.bits;
        data.bits &= (1ULL << size()) - 1ULL;
        return *this;
    }
 
    constexpr dynamic_bitset & flip(size_t const i)
    {
        at(i) ? reset(i) : set(i);
        return *this;
    }
 
    constexpr bool all() const noexcept { return count() == size(); }
 
    constexpr bool any() const noexcept { return count() != 0; }
 
    constexpr bool none() const noexcept { return count() == 0; }
 
    constexpr size_type count() const noexcept { return std::popcount(data.bits); }
 
    constexpr reference at(size_t const i)
    {
        if (i >= size()) // [[unlikely]]
            throw std::out_of_range{"Trying to access position " + std::to_string(i) +
                                    " in a bio::ranges::dynamic_bitset of size " + std::to_string(size()) + "."};
        return (*this)[i];
    }
 
    constexpr const_reference at(size_t const i) const
    {
        if (i >= size()) // [[unlikely]]
            throw std::out_of_range{"Trying to access position " + std::to_string(i) +
                                    " in a bio::ranges::dynamic_bitset of size " + std::to_string(size()) + "."};
        return (*this)[i];
    }
 
    constexpr const_reference test(size_t const i) const { return at(i); }
 
    constexpr reference operator[](size_t const i) noexcept
    {
        assert(i < size());
        return {data, i};
    }
 
    constexpr const_reference operator[](size_t const i) const noexcept
    {
        assert(i < size());
        return data.bits & 1ULL << i;
    }
 
    constexpr reference front() noexcept
    {
        assert(size() > 0);
        return (*this)[0];
    }
 
    constexpr const_reference front() const noexcept
    {
        assert(size() > 0);
        return (*this)[0];
    }
 
    constexpr reference back() noexcept
    {
        assert(size() > 0);
        return (*this)[size() - 1];
    }
 
    constexpr const_reference back() const noexcept
    {
        assert(size() > 0);
        return (*this)[size() - 1];
    }
 
    constexpr detail::dynamic_bitset_bitfield * raw_data() noexcept { return &data; }
 
    constexpr detail::dynamic_bitset_bitfield const * raw_data() const noexcept { return &data; }
 
    constexpr bool empty() const noexcept { return size() == 0; }
 
    constexpr size_type size() const noexcept { return data.size; }
 
    constexpr size_type max_size() const noexcept { return capacity(); }
 
    constexpr size_type capacity() const noexcept { return bit_capacity; }
 
    constexpr void reserve(size_t) const noexcept
    {
        // no-op
    }
 
    constexpr void shrink_to_fit() const noexcept
    {
        // no-op
    }
 
    constexpr void clear() noexcept
    {
        data.size &= 0ULL;
        data.bits &= 0ULL;
    }
 
    constexpr iterator insert(const_iterator pos, value_type const value) noexcept { return insert(pos, 1, value); }
 
    constexpr iterator insert(const_iterator pos, size_type const count, value_type const value) noexcept
    {
        auto tmp = views::repeat_n(value, count);
        return insert(pos, std::ranges::begin(tmp), std::ranges::end(tmp));
    }
 
    template <std::forward_iterator begin_it_type, typename end_it_type>
        requires(std::sentinel_for<end_it_type, begin_it_type> &&
                 std::constructible_from<value_type, std::iter_reference_t<begin_it_type>>)
    constexpr iterator insert(const_iterator pos, begin_it_type begin_it, end_it_type end_it) noexcept
    {
        auto const pos_as_num = std::ranges::distance(cbegin(), pos);
        auto const length     = std::ranges::distance(begin_it, end_it);
 
        if (length == 0)
            return begin(); // nothing to insert
 
        size_type const tmp_size{size()};
        resize(tmp_size + length);
 
        for (size_type i = tmp_size + length - 1; i > pos_as_num + length - 1; --i)
            (*this)[i] = (*this)[i - length];
 
        // std::ranges::copy(begin_it, end_it, (*this)[pos_as_num]);
        for (auto i = pos_as_num; begin_it != end_it; ++i, ++begin_it)
            (*this)[i] = *begin_it;
 
        return begin() + pos_as_num;
    }
 
    constexpr iterator insert(const_iterator pos, std::initializer_list<value_type> const & ilist) noexcept
    {
        return insert(pos, ilist.begin(), ilist.end());
    }
 
    constexpr iterator erase(const_iterator begin_it, const_iterator end_it) noexcept
    {
        if (begin_it >= end_it) // [[unlikely]]
            return begin() + std::ranges::distance(cbegin(), end_it);
 
        auto const length = std::ranges::distance(begin_it, end_it);
        auto       out_it = begin() + std::ranges::distance(cbegin(), begin_it);
 
        while (end_it != cend())
            *(out_it++) = *(end_it++);
 
        resize(size() - length);
        return begin() + std::ranges::distance(cbegin(), begin_it);
    }
 
    constexpr iterator erase(const_iterator pos) noexcept { return erase(pos, pos + 1); }
 
    constexpr void push_back(value_type const value) noexcept
    {
        assert(size() < bit_capacity);
        resize(size() + 1);
        (*this)[size() - 1] = value;
    }
 
    constexpr void pop_back() noexcept
    {
        assert(size() > 0);
        resize(size() - 1);
    }
 
    constexpr void resize(size_type const count, value_type const value = false) noexcept
    {
        assert(count <= bit_capacity);
        // Enlarging.
        data.bits |= value && count > size() ? ((1ULL << (count - size())) - 1) << size() : 0ULL;
        // Set size bits.
        data.size = count;
        // Shrinking.
        data.bits &= (1ULL << size()) - 1ULL;
    }
 
    constexpr void swap(dynamic_bitset & rhs) noexcept
    {
        static_assert(meta::trivial<decltype(data)>); // if type is no longer trivially copyable, do actual moves:
        detail::dynamic_bitset_bitfield tmp = data;
        data                                = rhs.data;
        rhs.data                            = tmp;
    }
 
    constexpr void swap(dynamic_bitset && rhs) noexcept { data = std::move(rhs.data); }
 
 
    friend constexpr void swap(dynamic_bitset & lhs, dynamic_bitset & rhs) noexcept { lhs.swap(rhs); }
 
    template <size_t cap>
        requires(cap <= bit_capacity)
    friend constexpr dynamic_bitset operator&(dynamic_bitset const & lhs, dynamic_bitset<cap> const & rhs) noexcept
    {
        assert(lhs.size() == rhs.size());
        dynamic_bitset tmp{lhs};
        tmp &= rhs;
        return tmp;
    }
 
    template <size_t cap>
        requires(cap <= bit_capacity)
    friend constexpr dynamic_bitset operator^(dynamic_bitset const & lhs, dynamic_bitset<cap> const & rhs) noexcept
    {
        assert(lhs.size() == rhs.size());
        dynamic_bitset tmp{lhs};
        tmp ^= rhs;
        return tmp;
    }
 
    template <size_t cap>
        requires(cap <= bit_capacity)
    friend constexpr dynamic_bitset operator|(dynamic_bitset const & lhs, dynamic_bitset<cap> const & rhs) noexcept
    {
        assert(lhs.size() == rhs.size());
        dynamic_bitset tmp{lhs};
        tmp |= rhs;
        return tmp;
    }
 
    template <size_t cap>
    friend constexpr bool operator==(dynamic_bitset const & lhs, dynamic_bitset<cap> const & rhs) noexcept
    {
        return lhs.data.size == rhs.raw_data()->size && lhs.data.bits == rhs.raw_data()->bits;
    }
 
    template <size_t cap>
    friend constexpr auto operator<=>(dynamic_bitset const & lhs, dynamic_bitset<cap> const & rhs) noexcept
    {
        return lhs.data.bits <=> rhs.raw_data()->bits;
    }
 
    inline constexpr unsigned long to_ulong() const
    {
        if constexpr (std::numeric_limits<unsigned long>::max() < std::numeric_limits<size_t>::max())
        {
            if (data.bits > std::numeric_limits<unsigned long>::max())
                throw std::overflow_error{"bio::ranges::dynamic_bitset cannot be represented as unsigned long."};
        }
 
        return static_cast<unsigned long>(data.bits);
    }
 
    inline constexpr unsigned long long to_ullong() const
    {
        if constexpr (std::numeric_limits<unsigned long long>::max() < std::numeric_limits<size_t>::max())
        {
            if (data.bits >= std::numeric_limits<unsigned long long>::max())
                throw std::overflow_error{"bio::ranges::dynamic_bitset cannot be represented as unsigned long long."};
        }
 
        return static_cast<unsigned long long>(data.bits);
    }
 
 
    template <typename archive_t>
    void serialize(archive_t & archive)
    {
        uint64_t size = data.size;
        archive(size);
        data.size     = size;
        uint64_t bits = data.bits;
        archive(bits);
        data.bits = bits;
    }
};
 
} // namespace bio::ranges
 
namespace std
{
 
template <size_t cap>
struct hash<bio::ranges::dynamic_bitset<cap>>
{
    size_t operator()(bio::ranges::dynamic_bitset<cap> const arg) const noexcept
    {
        return static_cast<size_t>(arg.to_ullong());
    }
};
 
} //namespace std
 
#if __has_include(<fmt/format.h>)
 
#    include <fmt/ranges.h>
 
template <>
struct fmt::formatter<bio::ranges::detail::dynamic_bitset_reference_proxy> : fmt::formatter<bool>
{
    constexpr auto format(bio::ranges::detail::dynamic_bitset_reference_proxy const a, auto & ctx) const
    {
        return fmt::formatter<bool>::format(static_cast<bool>(a), ctx);
    }
};
 
template <size_t bit_capacity>
struct fmt::is_range<bio::ranges::dynamic_bitset<bit_capacity>, char> : std::false_type
{};
 
template <size_t bit_capacity>
struct fmt::formatter<bio::ranges::dynamic_bitset<bit_capacity>> : fmt::formatter<std::string>
{
    constexpr auto format(bio::ranges::dynamic_bitset<bit_capacity> const s, auto & ctx) const
    {
        std::string str{"0b"};
        str.reserve(2 + s.size() + s.size() / 4); // TODO fix me
        auto v = s | std::views::transform([](bool const bit) { return bit ? '1' : '0'; }) |
                 bio::ranges::views::interleave(4, std::string_view{"'"}) | std::views::reverse;
        std::ranges::copy(v, std::back_inserter(str));
        return fmt::formatter<std::string>::format(str, ctx);
    }
};
 
#endif