dynamic_bitset.hpp

Go to the documentation of this file.

// -----------------------------------------------------------------------------------------------------
// 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/seqan/seqan3/blob/master/LICENSE.md
// -----------------------------------------------------------------------------------------------------
 
#pragma once
 
#include <seqan3/core/bit_manipulation.hpp>
#include <seqan3/core/concept/cereal.hpp>
#include <seqan3/core/detail/debug_stream_type.hpp>
#include <seqan3/range/views/interleave.hpp>
#include <seqan3/range/views/repeat_n.hpp>
#include <seqan3/range/views/to.hpp>
 
namespace seqan3
{
 
template <size_t bit_capacity = 58>
class dynamic_bitset
{
private:
    template <size_t>
    friend class dynamic_bitset;
 
    struct bitfield
    {
        uint64_t size : 6u;
        uint64_t bits : 58u;
    };
 
    bitfield data{0u, 0u}; // Specifying values prevents ICE on gcc < 9 when comparing to default constructed bitset
 
    class reference_proxy_type
    {
    public:
        constexpr reference_proxy_type() noexcept = default; 
        constexpr reference_proxy_type(reference_proxy_type const &) noexcept = default; 
        constexpr reference_proxy_type(reference_proxy_type &&) noexcept = default; 
 
        constexpr reference_proxy_type & operator=(reference_proxy_type const rhs) noexcept
        {
            rhs ? set() : reset();
            return *this;
        }
 
        constexpr reference_proxy_type & operator=(bool const value) noexcept
        {
            value ? set() : reset();
            return *this;
        }
 
        ~reference_proxy_type() noexcept = default; 
 
        constexpr reference_proxy_type(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 reference_proxy_type & operator|=(bool const value)
        {
            if (value)
                set();
 
            return *this;
        }
 
        constexpr reference_proxy_type & operator&=(bool const value)
        {
            if (!value)
                reset();
 
            return *this;
        }
 
        constexpr reference_proxy_type & operator^=(bool const value)
        {
            operator bool() && value ? reset() : set();
            return *this;
        }
 
    private:
        bitfield & internal;
        uint64_t mask;
 
        constexpr void set() noexcept
        {
            internal.bits |= mask;
        }
 
        constexpr void reset() noexcept
        {
            internal.bits &= ~mask;
        }
    };
 
public:
    static_assert(bit_capacity <= 58, "The capacity of the dynamic_bitset exceeds the limit of 58.");
 
    using value_type      = bool;
    using reference       = reference_proxy_type;
    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       = 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 (detail::popcount(value >> 58) != 0)
            throw std::invalid_argument{"The dynamic_bitset can be at most 58 long."};
        data.bits |= value;
        data.size |= value ? detail::most_significant_bit_set(value) + 1 : 0u;
    }
 
    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 <std::ranges::input_range other_range_t>
        requires (!std::same_as<std::remove_cvref_t<other_range_t>, dynamic_bitset>)
    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 detail::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 seqan3::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 seqan3::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 bitfield * raw_data() noexcept
    {
        return &data;
    }
 
    constexpr 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
    {
        bitfield tmp = std::move(data);
        data = std::move(rhs.data);
        rhs.data = std::move(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 bool operator!=(dynamic_bitset const & lhs, dynamic_bitset<cap> const & rhs) noexcept
    {
        return !(lhs == rhs);
    }
 
    template <size_t cap>
    friend constexpr bool operator<(dynamic_bitset const & lhs, dynamic_bitset<cap> const & rhs) noexcept
    {
        return lhs.data.bits < rhs.raw_data()->bits;
    }
 
    template <size_t cap>
    friend constexpr bool operator>(dynamic_bitset const & lhs, dynamic_bitset<cap> const & rhs) noexcept
    {
        return lhs.data.bits > rhs.raw_data()->bits;
    }
 
    template <size_t cap>
    friend constexpr bool operator<=(dynamic_bitset const & lhs, dynamic_bitset<cap> const & rhs) noexcept
    {
        return !(lhs > rhs);
    }
 
    template <size_t cap>
    friend constexpr bool operator>=(dynamic_bitset const & lhs, dynamic_bitset<cap> const & rhs) noexcept
    {
        return !(lhs < rhs);
    }
 
    template <typename char_t = char>
    std::string to_string(char_t zero = char_t{'0'}, char_t one = char_t{'1'}) const
    {
        std::string str{};
        str.reserve(size());
        for (bool const bit : std::views::reverse(*this))
            bit ? str.push_back(one) : str.push_back(zero);
 
        return str;
    }
 
    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{"seqan3::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{"seqan3::dynamic_bitset cannot be represented as unsigned long long."};
        }
 
        return static_cast<unsigned long long>(data.bits);
    }
 
    friend std::ostream & operator<<(std::ostream & os, dynamic_bitset const & arg)
    {
        os << arg.to_string();
        return os;
    }
 
    friend std::istream & operator>>(std::istream & is, dynamic_bitset & arg)
    {
        // Check if stream is ok and skip leading whitespaces.
        std::istream::sentry s(is);
        if (s)
        {
            arg.clear(); // clear the bitset
            std::streamsize num_char = (is.width() > 0)
                ? std::min<std::streamsize>(is.width(), arg.max_size())
                : arg.max_size();
            assert(num_char > 0);
            std::vector<bool> tmp{};
            tmp.reserve(num_char);
            for (std::streamsize n = num_char; n > 0 && (is.peek() == is.widen('0') || is.peek() == is.widen('1')); --n)
            {
                char c = is.get();
                c == is.widen('0') ? tmp.push_back(false) : tmp.push_back(true);
            }
 
            arg.assign(std::views::reverse(tmp));
 
            if (arg.size() == 0) // nothing extracted so we set the fail bit.
                is.setstate(std::ios_base::failbit); // LCOV_EXCL_LINE
 
            is.width(0); // cancel the effects of std::setw, if any.
        }
        return is;
    }
 
    template <typename char_t>
    friend debug_stream_type<char_t> & operator<<(debug_stream_type<char_t> & s, dynamic_bitset arg)
    {
        s << (std::string_view{arg.to_string()} | views::interleave(4, std::string_view{"'"}) | views::to<std::string>);
        return s;
    }
 
 
    template <cereal_archive archive_t>
    void CEREAL_SERIALIZE_FUNCTION_NAME(archive_t & archive)
    {
        uint64_t size = data.size;
        archive(size);
        data.size = size;
        uint64_t bits = data.bits;
        archive(bits);
        data.bits = bits;
    }
};
 
} // namespace seqan3
 
namespace std
{
 
template <size_t cap>
struct hash<seqan3::dynamic_bitset<cap>>
{
    size_t operator()(seqan3::dynamic_bitset<cap> const arg) const noexcept
    {
        return static_cast<size_t>(arg.to_ullong());
    }
};
 
} //namespace std