dynamic_bitset_base.hpp

Go to the documentation of this file.

// Copyright 2024 Man Group Operations Limited
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
#pragma once
 
 
#include <algorithm>
#include <stdexcept>
#include <string>
#include <type_traits>
 
#include "sparrow/buffer/dynamic_bitset/bitset_iterator.hpp"
#include "sparrow/buffer/dynamic_bitset/bitset_reference.hpp"
#include "sparrow/buffer/dynamic_bitset/null_count_policy.hpp"
#include "sparrow/utils/contracts.hpp"
 
namespace sparrow
{
    template <typename B, null_count_policy NCP = tracking_null_count<>>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    class dynamic_bitset_base : protected NCP
    {
    public:
 
        using self_type = dynamic_bitset_base<B, NCP>;  
        using null_count_policy_type = NCP;             
        using storage_type = B;                         
        using storage_type_without_cvrefpointer = std::remove_pointer_t<
            std::remove_cvref_t<storage_type>>;  
        using block_type = typename storage_type_without_cvrefpointer::value_type;  
        using value_type = bool;                        
        using reference = bitset_reference<self_type>;  
        using const_reference = bool;                   
        using size_type = typename storage_type_without_cvrefpointer::size_type;  
        using difference_type = typename storage_type_without_cvrefpointer::difference_type;  
        using iterator = bitset_iterator<self_type, false>;       
        using const_iterator = bitset_iterator<self_type, true>;  

        [[nodiscard]] constexpr size_type size() const noexcept;
 
        constexpr void set_size(size_type new_size) noexcept;

        [[nodiscard]] constexpr size_type offset() const noexcept;

        constexpr void set_offset(size_type offset) noexcept;

        [[nodiscard]] constexpr bool empty() const noexcept;

        [[nodiscard]] constexpr size_type null_count() const noexcept
            requires(NCP::track_null_count);

        [[nodiscard]] constexpr bool test(size_type pos) const;

        constexpr void set(size_type pos, value_type value);

        [[nodiscard]] constexpr const_reference at(size_type pos) const;

        [[nodiscard]] constexpr reference at(size_type pos);

        [[nodiscard]] constexpr reference operator[](size_type i);

        [[nodiscard]] constexpr const_reference operator[](size_type i) const;

        [[nodiscard]] constexpr block_type* data() noexcept;

        [[nodiscard]] constexpr const block_type* data() const noexcept;

        [[nodiscard]] constexpr size_type block_count() const noexcept;

        constexpr void swap(self_type& rhs) noexcept;

        [[nodiscard]] constexpr iterator begin();

        [[nodiscard]] constexpr iterator end();

        [[nodiscard]] constexpr const_iterator begin() const;

        [[nodiscard]] constexpr const_iterator end() const;

        [[nodiscard]] constexpr const_iterator cbegin() const;

        [[nodiscard]] constexpr const_iterator cend() const;

        [[nodiscard]] constexpr reference front();

        [[nodiscard]] constexpr const_reference front() const;

        [[nodiscard]] constexpr reference back();

        [[nodiscard]] constexpr const_reference back() const;

        [[nodiscard]] constexpr const storage_type_without_cvrefpointer& buffer() const noexcept
        {
            if constexpr (std::is_pointer_v<storage_type>)
            {
                return *m_buffer;
            }
            else
            {
                return m_buffer;
            }
        }

        [[nodiscard]] constexpr storage_type_without_cvrefpointer& buffer() noexcept
        {
            if constexpr (std::is_pointer_v<storage_type>)
            {
                return *m_buffer;
            }
            else
            {
                return m_buffer;
            }
        }

        [[nodiscard]] static constexpr size_type compute_block_count(size_type bits_count) noexcept;

        [[nodiscard]] storage_type extract_storage() noexcept
            requires std::same_as<storage_type, storage_type_without_cvrefpointer>
        {
            return std::move(m_buffer);
        }
 
    protected:

        constexpr dynamic_bitset_base(storage_type buffer, size_type size);

        constexpr dynamic_bitset_base(storage_type buffer, size_type size, size_type offset);

        constexpr dynamic_bitset_base(storage_type buffer, size_type size, size_type offset, size_type null_count)
            requires(NCP::track_null_count);
 
        constexpr ~dynamic_bitset_base() = default;
 
        constexpr dynamic_bitset_base(const dynamic_bitset_base&) = default;
        constexpr dynamic_bitset_base(dynamic_bitset_base&&) noexcept = default;
 
        constexpr dynamic_bitset_base& operator=(const dynamic_bitset_base&) = default;
        constexpr dynamic_bitset_base& operator=(dynamic_bitset_base&&) noexcept = default;

        constexpr void resize(size_type n, value_type b = false);

        constexpr void clear() noexcept;

        constexpr iterator insert(const_iterator pos, value_type value);

        constexpr iterator insert(const_iterator pos, size_type count, value_type value);

        template <std::input_iterator InputIt>
        constexpr iterator insert(const_iterator pos, InputIt first, InputIt last);

        constexpr iterator insert(const_iterator pos, std::initializer_list<value_type> ilist);

        constexpr iterator emplace(const_iterator pos, value_type value);

        constexpr iterator erase(const_iterator pos);

        constexpr iterator erase(const_iterator first, const_iterator last);

        constexpr void push_back(value_type value);

        constexpr void pop_back();

        constexpr void zero_unused_bits();
 
    private:
 
        static constexpr std::size_t s_bits_per_block = sizeof(block_type) * CHAR_BIT;  

        [[nodiscard]] static constexpr size_type block_index(size_type pos) noexcept;

        [[nodiscard]] static constexpr size_type bit_index(size_type pos) noexcept;

        [[nodiscard]] static constexpr block_type bit_mask(size_type pos) noexcept;

        [[nodiscard]] constexpr size_type count_extra_bits() const noexcept;

        constexpr void shift_bits_right(size_type start, size_type length, size_type shift_amount);

        constexpr void fill_bits(size_type start, size_type count, value_type value);
 
        storage_type m_buffer;  
        size_type m_size;       
        size_type m_offset;     
 
        friend class bitset_iterator<self_type, true>;   
        friend class bitset_iterator<self_type, false>;  
        friend class bitset_reference<self_type>;        
    };
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::size() const noexcept -> size_type
    {
        return m_size;
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void dynamic_bitset_base<B, NCP>::set_size(size_type new_size) noexcept
    {
        m_size = new_size;
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr bool dynamic_bitset_base<B, NCP>::empty() const noexcept
    {
        return m_size == 0;
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::offset() const noexcept -> size_type
    {
        return m_offset;
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void dynamic_bitset_base<B, NCP>::set_offset(size_type offset) noexcept
    {
        m_offset = offset;
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::null_count() const noexcept -> size_type
        requires(NCP::track_null_count)
    {
        return NCP::null_count();
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::operator[](size_type pos) -> reference
    {
        SPARROW_ASSERT_TRUE(pos < size());
        return reference(*this, pos);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr bool dynamic_bitset_base<B, NCP>::operator[](size_type pos) const
    {
        return test(pos);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr bool dynamic_bitset_base<B, NCP>::test(size_type pos) const
    {
        SPARROW_ASSERT_TRUE(pos < size());
        if constexpr (std::is_pointer_v<storage_type>)
        {
            if (m_buffer == nullptr)
            {
                return true;
            }
        }
        if (data() == nullptr)
        {
            return true;
        }
        const size_type actual_pos = m_offset + pos;
        // Ensure the specific bit we're accessing is within the buffer
        SPARROW_ASSERT_TRUE(block_index(actual_pos) < buffer().size());
        return buffer().data()[block_index(actual_pos)] & bit_mask(actual_pos);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void dynamic_bitset_base<B, NCP>::set(size_type pos, value_type value)
    {
        SPARROW_ASSERT_TRUE(pos < size());
        const size_type actual_pos = m_offset + pos;
        const size_type target_block = block_index(actual_pos);
 
        if (data() == nullptr)
        {
            if (value == true)  // In this case,  we don't need to set the bit
            {
                return;
            }
            else
            {
                if constexpr (requires(storage_type_without_cvrefpointer s) { s.resize(0); })
                {
                    constexpr block_type true_value = block_type(~block_type(0));
                    const auto block_count = compute_block_count(size() + m_offset);
                    buffer().resize(block_count, true_value);
                    zero_unused_bits();
                }
                else
                {
                    throw std::runtime_error("Cannot set a bit in a null buffer.");
                }
            }
        }
        else if (target_block >= buffer().size())
        {
            // Buffer exists but is too small for the bit we're accessing
            if constexpr (requires(storage_type_without_cvrefpointer s) { s.resize(0); })
            {
                constexpr block_type true_value = block_type(~block_type(0));
                buffer().resize(target_block + 1, true_value);
                zero_unused_bits();
            }
            else
            {
                SPARROW_ASSERT_TRUE(target_block < buffer().size());
            }
        }
 
        block_type& block = buffer().data()[target_block];
        const bool old_value = block & bit_mask(actual_pos);
        if (value)
        {
            block |= bit_mask(actual_pos);
        }
        else
        {
            block &= block_type(~bit_mask(actual_pos));
        }
        this->update_null_count(old_value, value);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::data() noexcept -> block_type*
    {
        if constexpr (std::is_pointer_v<storage_type>)
        {
            if (m_buffer == nullptr)
            {
                return nullptr;
            }
        }
        return buffer().data();
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::data() const noexcept -> const block_type*
    {
        return buffer().data();
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::block_count() const noexcept -> size_type
    {
        return buffer().size();
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void dynamic_bitset_base<B, NCP>::swap(self_type& rhs) noexcept
    {
        using std::swap;
        swap(m_buffer, rhs.m_buffer);
        swap(m_size, rhs.m_size);
        swap(m_offset, rhs.m_offset);
        this->swap_null_count(rhs);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::begin() -> iterator
    {
        return iterator(this, 0u);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::end() -> iterator
    {
        return iterator(this, size());
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::begin() const -> const_iterator
    {
        return cbegin();
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::end() const -> const_iterator
    {
        return cend();
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::cbegin() const -> const_iterator
    {
        return const_iterator(this, 0);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::cend() const -> const_iterator
    {
        return const_iterator(this, size());
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::at(size_type pos) -> reference
    {
        if (pos >= size())
        {
            throw std::out_of_range(
                "dynamic_bitset_base::at: index out of range for dynamic_bitset_base of size"
                + std::to_string(size()) + " at index " + std::to_string(pos)
            );
        }
        return (*this)[pos];
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::at(size_type pos) const -> const_reference
    {
        if (pos >= size())
        {
            throw std::out_of_range(
                "dynamic_bitset_base::at: index out of range for dynamic_bitset_base of size"
                + std::to_string(size()) + " at index " + std::to_string(pos)
            );
        }
        return test(pos);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::front() -> reference
    {
        SPARROW_ASSERT_TRUE(size() >= 1);
        return (*this)[0];
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::front() const -> const_reference
    {
        SPARROW_ASSERT_TRUE(size() >= 1);
        if (data() == nullptr)
        {
            return true;
        }
        return (*this)[0];
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::back() -> reference
    {
        SPARROW_ASSERT_TRUE(size() >= 1);
        return (*this)[size() - 1];
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::back() const -> const_reference
    {
        SPARROW_ASSERT_TRUE(size() >= 1);
        if (data() == nullptr)
        {
            return true;
        }
        return (*this)[size() - 1];
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr dynamic_bitset_base<B, NCP>::dynamic_bitset_base(storage_type buf, size_type size)
        : m_buffer(std::move(buf))
        , m_size(size)
        , m_offset(0)
    {
        this->initialize_null_count(data(), m_size, buffer().size(), m_offset);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr dynamic_bitset_base<B, NCP>::dynamic_bitset_base(storage_type buf, size_type size, size_type offset)
        : m_buffer(std::move(buf))
        , m_size(size)
        , m_offset(offset)
    {
        this->initialize_null_count(data(), m_size, buffer().size(), m_offset);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr dynamic_bitset_base<B, NCP>::dynamic_bitset_base(
        storage_type buf,
        size_type size,
        size_type offset,
        size_type null_count
    )
        requires(NCP::track_null_count)
        : m_buffer(std::move(buf))
        , m_size(size)
        , m_offset(offset)
    {
        this->set_null_count(null_count);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::compute_block_count(size_type bits_count) noexcept -> size_type
    {
        return bits_count / s_bits_per_block + static_cast<size_type>(bits_count % s_bits_per_block != 0);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::block_index(size_type pos) noexcept -> size_type
    {
        return pos / s_bits_per_block;
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::bit_index(size_type pos) noexcept -> size_type
    {
        return pos % s_bits_per_block;
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::bit_mask(size_type pos) noexcept -> block_type
    {
        const size_type bit = bit_index(pos);
        return static_cast<block_type>(block_type(1) << bit);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr auto dynamic_bitset_base<B, NCP>::count_extra_bits() const noexcept -> size_type
    {
        return bit_index(size() + m_offset);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void dynamic_bitset_base<B, NCP>::zero_unused_bits()
    {
        if (data() == nullptr)
        {
            return;
        }
        const size_type extra_bits = count_extra_bits();
        if (extra_bits != 0)
        {
            buffer().back() &= block_type(~(~block_type(0) << extra_bits));
        }
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void dynamic_bitset_base<B, NCP>::resize(size_type n, value_type b)
    {
        if ((data() == nullptr) && b)
        {
            m_size = n;
            return;
        }
        auto& buffer = this->buffer();
        const size_type old_size = m_size;
        size_type old_block_count = buffer.size();
        const size_type new_block_count = compute_block_count(n + m_offset);
        const block_type value = b ? block_type(~block_type(0)) : block_type(0);
 
        if (new_block_count != old_block_count)
        {
            if (data() == nullptr)
            {
                constexpr block_type true_value = block_type(~block_type(0));
                old_block_count = compute_block_count(old_size + m_offset);
                buffer.resize(old_block_count, true_value);
                // Zero out bits beyond old_size in the last block
                const size_type old_extra_bits = bit_index(old_size + m_offset);
                if (old_extra_bits != 0)
                {
                    buffer.back() &= block_type(~(~block_type(0) << old_extra_bits));
                }
            }
            buffer.resize(new_block_count, value);
        }
 
        if (n > old_size)
        {
            // Calculate extra bits based on OLD size
            const size_type old_extra_bits = bit_index(old_size + m_offset);
            if (old_extra_bits > 0)
            {
                const size_type old_last_block_idx = compute_block_count(old_size + m_offset) - 1;
                auto& last_block = buffer.data()[old_last_block_idx];
                if (b)
                {
                    // Set bits from old_extra_bits to end of block to true
                    const auto mask = static_cast<block_type>(value << old_extra_bits);
                    last_block |= mask;
                }
                else
                {
                    // Clear bits from old_extra_bits to end of block
                    const auto mask = static_cast<block_type>(~(~block_type(0) << old_extra_bits));
                    last_block &= mask;
                }
            }
        }
 
        m_size = n;
        zero_unused_bits();
        this->recompute_null_count(data(), m_size, buffer.size(), m_offset);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void dynamic_bitset_base<B, NCP>::clear() noexcept
    {
        buffer().clear();
        m_size = 0;
        this->clear_null_count();
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr dynamic_bitset_base<B, NCP>::iterator
    dynamic_bitset_base<B, NCP>::insert(const_iterator pos, value_type value)
    {
        return insert(pos, 1, value);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr dynamic_bitset_base<B, NCP>::iterator
    dynamic_bitset_base<B, NCP>::insert(const_iterator pos, size_type count, value_type value)
    {
        SPARROW_ASSERT_TRUE(cbegin() <= pos);
        SPARROW_ASSERT_TRUE(pos <= cend());
        const auto index = static_cast<size_type>(std::distance(cbegin(), pos));
        if (data() == nullptr && value)
        {
            m_size += count;
        }
        else
        {
            const size_type old_size = size();
            const size_type new_size = old_size + count;
 
            resize(new_size);
 
            // Shift existing bits to make room for new ones
            const size_type bits_to_shift = old_size - index;
            if (bits_to_shift > 0)
            {
                shift_bits_right(index + m_offset, bits_to_shift, count);
            }
 
            // Fill the inserted region with the specified value
            fill_bits(index + m_offset, count, value);
 
            // Recompute null count after all bit manipulations are complete
            this->recompute_null_count(data(), m_size, buffer().size(), m_offset);
        }
 
        return iterator(this, index);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    template <std::input_iterator InputIt>
    constexpr dynamic_bitset_base<B, NCP>::iterator
    dynamic_bitset_base<B, NCP>::insert(const_iterator pos, InputIt first, InputIt last)
    {
        const auto index = static_cast<size_type>(std::distance(cbegin(), pos));
        const auto count = static_cast<size_type>(std::distance(first, last));
        if (data() == nullptr)
        {
            if (std::all_of(
                    first,
                    last,
                    [](auto v)
                    {
                        return bool(v);
                    }
                ))
            {
                m_size += count;
            }
            return iterator(this, index);
        }
        SPARROW_ASSERT_TRUE(cbegin() <= pos);
        SPARROW_ASSERT_TRUE(pos <= cend());
 
        const size_type old_size = size();
        const size_type new_size = old_size + count;
 
        resize(new_size);
 
        // Shift existing bits to make room for new ones
        const size_type bits_to_shift = old_size - index;
        if (bits_to_shift > 0)
        {
            shift_bits_right(index + m_offset, bits_to_shift, count);
        }
 
        // Insert bits from the iterator range
        for (size_type i = 0; i < count; ++i)
        {
            set(index + i, *first++);
        }
 
        // Recompute null count after all bit manipulations are complete
        this->recompute_null_count(data(), m_size, buffer().size(), m_offset);
 
        return iterator(this, index);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr dynamic_bitset_base<B, NCP>::iterator
    dynamic_bitset_base<B, NCP>::emplace(const_iterator pos, value_type value)
    {
        return insert(pos, value);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr dynamic_bitset_base<B, NCP>::iterator dynamic_bitset_base<B, NCP>::erase(const_iterator pos)
    {
        SPARROW_ASSERT_TRUE(cbegin() <= pos);
        SPARROW_ASSERT_TRUE(pos < cend());
 
        return erase(pos, pos + 1);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr dynamic_bitset_base<B, NCP>::iterator
    dynamic_bitset_base<B, NCP>::erase(const_iterator first, const_iterator last)
    {
        SPARROW_ASSERT_TRUE(cbegin() <= first);
        SPARROW_ASSERT_TRUE(first <= last);
        SPARROW_ASSERT_TRUE(last <= cend());
 
        const auto first_index = static_cast<size_type>(std::distance(cbegin(), first));
        const auto last_index = static_cast<size_type>(std::distance(cbegin(), last));
        const size_type count = last_index - first_index;
 
        if (data() == nullptr)
        {
            m_size -= count;
        }
        else
        {
            if (last == cend())
            {
                resize(first_index);
                return end();
            }
 
            // Shift bits left using block-level operations
            const size_type bits_to_move = size() - last_index;
            if (bits_to_move > 0)
            {
                // Copy bits from [last_index, end) to [first_index, ...)
                for (size_type i = 0; i < bits_to_move; ++i)
                {
                    const bool bit_value = test(last_index + i);
                    set(first_index + i, bit_value);
                }
            }
 
            resize(size() - count);
        }
        return iterator(this, first_index);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void dynamic_bitset_base<B, NCP>::push_back(value_type value)
    {
        resize(size() + 1, value);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void dynamic_bitset_base<B, NCP>::pop_back()
    {
        if (empty())
        {
            return;
        }
        resize(size() - 1);
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void
    dynamic_bitset_base<B, NCP>::shift_bits_right(size_type start, size_type length, size_type shift_amount)
    {
        if (length == 0 || shift_amount == 0)
        {
            return;
        }
 
        auto* blocks = data();
        const size_type src_start_bit = start;
        const size_type dst_start_bit = start + shift_amount;
 
        // Work backwards to avoid overwriting source data
        // Process bit-by-bit in reverse order, but in block-sized chunks where possible
        size_type remaining = length;
 
        while (remaining > 0)
        {
            // Calculate position for this iteration (working backwards)
            const size_type current_offset = remaining - 1;
            const size_type src_bit = src_start_bit + current_offset;
            const size_type dst_bit = dst_start_bit + current_offset;
 
            const size_type src_block_idx = block_index(src_bit);
            const size_type dst_block_idx = block_index(dst_bit);
            const size_type src_bit_offset = bit_index(src_bit);
            const size_type dst_bit_offset = bit_index(dst_bit);
 
            // Determine how many bits we can process in this iteration
            // We can process up to the start of the current block, or all remaining bits
            const size_type bits_available_in_src_block = src_bit_offset + 1;
            const size_type bits_available_in_dst_block = dst_bit_offset + 1;
            const size_type bits_this_iter = std::min(
                {remaining, bits_available_in_src_block, bits_available_in_dst_block}
            );
 
            // Extract bits from source
            const size_type extract_start_offset = src_bit_offset - (bits_this_iter - 1);
            const block_type mask = static_cast<block_type>(
                ((block_type(1) << bits_this_iter) - 1) << extract_start_offset
            );
            const block_type src_bits = static_cast<block_type>(
                (blocks[src_block_idx] & mask) >> extract_start_offset
            );
 
            // Write bits to destination
            const size_type write_start_offset = dst_bit_offset - (bits_this_iter - 1);
            const block_type dst_mask = static_cast<block_type>(
                ((block_type(1) << bits_this_iter) - 1) << write_start_offset
            );
            blocks[dst_block_idx] = static_cast<block_type>(
                (blocks[dst_block_idx] & ~dst_mask) | ((src_bits << write_start_offset) & dst_mask)
            );
 
            remaining -= bits_this_iter;
        }
    }
 
    template <typename B, null_count_policy NCP>
        requires std::ranges::random_access_range<std::remove_pointer_t<B>>
    constexpr void dynamic_bitset_base<B, NCP>::fill_bits(size_type start, size_type count, value_type value)
    {
        if (count == 0)
        {
            return;
        }
 
        auto* blocks = data();
        const block_type fill_pattern = value ? static_cast<block_type>(~block_type(0)) : block_type(0);
 
        size_type current_bit = start;
        size_type remaining = count;
 
        // Handle first partial block if not aligned
        const size_type first_bit_offset = bit_index(current_bit);
        if (first_bit_offset != 0)
        {
            const size_type bits_in_first = std::min(remaining, s_bits_per_block - first_bit_offset);
            const block_type mask = static_cast<block_type>(
                ((block_type(1) << bits_in_first) - 1) << first_bit_offset
            );
 
            const size_type block_idx = block_index(current_bit);
            if (value)
            {
                blocks[block_idx] |= mask;
            }
            else
            {
                blocks[block_idx] &= ~mask;
            }
 
            current_bit += bits_in_first;
            remaining -= bits_in_first;
        }
 
        // Fill complete blocks
        while (remaining >= s_bits_per_block)
        {
            blocks[block_index(current_bit)] = fill_pattern;
            current_bit += s_bits_per_block;
            remaining -= s_bits_per_block;
        }
 
        // Handle last partial block
        if (remaining > 0)
        {
            const block_type mask = static_cast<block_type>((block_type(1) << remaining) - 1);
            const size_type block_idx = block_index(current_bit);
            if (value)
            {
                blocks[block_idx] |= mask;
            }
            else
            {
                blocks[block_idx] &= ~mask;
            }
        }
    }
 
}