dynamic_bitset.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 <type_traits>
 
#include "sparrow/buffer/buffer.hpp"
#include "sparrow/buffer/dynamic_bitset/dynamic_bitset_base.hpp"
#include "sparrow/utils/ranges.hpp"
 
namespace sparrow
{
    template <std::integral T>
    class dynamic_bitset : public dynamic_bitset_base<buffer<T>>
    {
    public:
 
        using base_type = dynamic_bitset_base<buffer<T>>;       
        using storage_type = typename base_type::storage_type;  
        using default_allocator = typename storage_type::default_allocator;  
        using block_type = typename base_type::block_type;  
        using value_type = typename base_type::value_type;  
        using size_type = typename base_type::size_type;    

        template <std::ranges::input_range R, allocator A>
            requires std::convertible_to<std::ranges::range_value_t<R>, value_type>
        constexpr explicit dynamic_bitset(const R& r, const A& a)
            : dynamic_bitset(std::ranges::size(r), true, a)
        {
            std::size_t i = 0;
            for (auto value : r)
            {
                if (!value)
                {
                    this->set(i, false);
                }
                i++;
            }
        }

        template <typename A>
            requires(not std::same_as<A, dynamic_bitset<T>> and allocator<A>)
        constexpr dynamic_bitset(const A& a);

        template <allocator A>
        constexpr explicit dynamic_bitset(size_type n, const A& a);

        template <allocator A>
        constexpr dynamic_bitset(size_type n, value_type v, const A& a);

        template <allocator A>
        constexpr dynamic_bitset(block_type* p, size_type n, const A& a);

        template <allocator A>
        constexpr dynamic_bitset(block_type* p, size_type n, size_type offset, const A& a);

        template <allocator A>
        constexpr dynamic_bitset(block_type* p, size_type n, size_type offset, size_type null_count, const A& a);

        constexpr dynamic_bitset(storage_type&& buf, size_type size, size_type offset);

        constexpr dynamic_bitset(storage_type&& buf, size_type size, size_type offset, size_type null_count);
 
        constexpr ~dynamic_bitset() = default;
        constexpr dynamic_bitset(const dynamic_bitset&) = default;
        constexpr dynamic_bitset(dynamic_bitset&&) noexcept = default;
 
        template <allocator A>
        constexpr dynamic_bitset(const dynamic_bitset& rhs, const A& a);
 
        template <allocator A>
        constexpr dynamic_bitset(dynamic_bitset&& rhs, const A& a);
 
        constexpr dynamic_bitset& operator=(const dynamic_bitset&) = default;
        constexpr dynamic_bitset& operator=(dynamic_bitset&&) noexcept = default;

        [[nodiscard]] constexpr dynamic_bitset slice(size_type start, size_type length) const;

        [[nodiscard]] constexpr dynamic_bitset slice(size_type start) const;
 
        // Inherit container-like operations from base class
        using base_type::clear;      
        using base_type::emplace;    
        using base_type::erase;      
        using base_type::insert;     
        using base_type::pop_back;   
        using base_type::push_back;  
        using base_type::resize;     
    };
 
    template <std::integral T>
    template <class A>
        requires(not std::same_as<A, dynamic_bitset<T>> and allocator<A>)
    constexpr dynamic_bitset<T>::dynamic_bitset(const A& a)
        : base_type(storage_type(a), 0u)
    {
        base_type::zero_unused_bits();
    }
 
    template <std::integral T>
    template <allocator A>
    constexpr dynamic_bitset<T>::dynamic_bitset(size_type n, const A& a)
        : dynamic_bitset(n, false, a)
    {
        base_type::zero_unused_bits();
    }
 
    template <std::integral T>
    template <allocator A>
    constexpr dynamic_bitset<T>::dynamic_bitset(size_type n, value_type value, const A& a)
        : base_type(
              storage_type(this->compute_block_count(n), value ? block_type(~block_type(0)) : block_type(0), a),
              n,
              0,
              value ? 0u : n
          )
    {
        base_type::zero_unused_bits();
    }
 
    template <std::integral T>
    template <allocator A>
    constexpr dynamic_bitset<T>::dynamic_bitset(block_type* p, size_type n, const A& a)
        : base_type(storage_type(p, p != nullptr ? this->compute_block_count(n) : 0, a), n)
    {
        base_type::zero_unused_bits();
    }
 
    template <std::integral T>
    template <allocator A>
    constexpr dynamic_bitset<T>::dynamic_bitset(block_type* p, size_type n, size_type offset, const A& a)
        : base_type(storage_type(p, this->compute_block_count(n + offset), a), n, offset)
    {
        base_type::zero_unused_bits();
    }
 
    template <std::integral T>
    template <allocator A>
    constexpr dynamic_bitset<
        T>::dynamic_bitset(block_type* p, size_type n, size_type offset, size_type null_count, const A& a)
        : base_type(storage_type(p, this->compute_block_count(n + offset), a), n, offset, null_count)
    {
        base_type::zero_unused_bits();
    }
 
    template <std::integral T>
    constexpr dynamic_bitset<T>::dynamic_bitset(storage_type&& buf, size_type size, size_type offset)
        : base_type(std::move(buf), size, offset)
    {
        base_type::zero_unused_bits();
    }
 
    template <std::integral T>
    constexpr dynamic_bitset<T>::dynamic_bitset(storage_type&& buf, size_type size, size_type offset, size_type null_count)
        : base_type(std::move(buf), size, offset, null_count)
    {
        base_type::zero_unused_bits();
    }
 
    template <std::integral T>
    template <allocator A>
    constexpr dynamic_bitset<T>::dynamic_bitset(const dynamic_bitset& rhs, const A& a)
        : base_type(storage_type(rhs, a))
    {
    }
 
    template <std::integral T>
    template <allocator A>
    constexpr dynamic_bitset<T>::dynamic_bitset(dynamic_bitset&& rhs, const A& a)
        : base_type(storage_type(std::move(rhs), a))
    {
    }
 
    template <std::integral T>
    constexpr auto dynamic_bitset<T>::slice(size_type start, size_type length) const -> dynamic_bitset
    {
        if (start + length > this->size())
        {
            throw std::out_of_range("slice: start + length exceeds bitset size");
        }
 
        sparrow::buffer<T> buffer_copy = this->buffer();
 
        return dynamic_bitset<T>(std::move(buffer_copy), length, this->offset() + start);
    }
 
    template <std::integral T>
    constexpr auto dynamic_bitset<T>::slice(size_type start) const -> dynamic_bitset
    {
        if (start > this->size())
        {
            throw std::out_of_range("slice: start exceeds bitset size");
        }
 
        return slice(start, this->size() - start);
    }

    using validity_bitmap = dynamic_bitset<std::uint8_t>;
 
    namespace detail
    {
        using validity_bitmap = sparrow::validity_bitmap;
 
        inline validity_bitmap ensure_validity_bitmap_impl(std::size_t size, const validity_bitmap& bitmap)
        {
            if (bitmap.size() == 0)
            {
                return {size, true, bitmap.buffer().get_allocator()};
            }
            return bitmap;  // copy
        }
 
        inline validity_bitmap ensure_validity_bitmap_impl(std::size_t size, validity_bitmap&& bitmap)
        {
            if (bitmap.size() == 0)
            {
                bitmap.resize(size, true);
            }
            return std::move(bitmap);
        }
 
        // range of booleans
        template <std::ranges::input_range R>
            requires(std::same_as<std::ranges::range_value_t<R>, bool>)
        validity_bitmap ensure_validity_bitmap_impl(std::size_t size, R&& range)
        {
            SPARROW_ASSERT_TRUE(size == range_size(range) || range_size(range) == 0);
            validity_bitmap bitmap(size, true, validity_bitmap::default_allocator{});
            std::size_t i = 0;
            for (auto value : range)
            {
                if (!value)
                {
                    bitmap.set(i, false);
                }
                i++;
            }
            return bitmap;
        }
 
        // range of indices / integers (but not booleans)
        template <std::ranges::input_range R>
            requires(
                std::unsigned_integral<std::ranges::range_value_t<R>>
                && !std::same_as<std::ranges::range_value_t<R>, bool>
                && !std::same_as<std::decay_t<R>, validity_bitmap>
            )
        validity_bitmap ensure_validity_bitmap_impl(std::size_t size, R&& range_of_indices)
        {
            validity_bitmap bitmap(size, true, validity_bitmap::default_allocator{});
            for (auto index : range_of_indices)
            {
                bitmap.set(index, false);
            }
            return bitmap;
        }
    }  // namespace detail

    template <class T>
    concept validity_bitmap_input = (std::same_as<T, validity_bitmap> || std::same_as<T, const validity_bitmap&>
                                     || (std::ranges::input_range<T>
                                         && std::same_as<std::ranges::range_value_t<T>, bool>)
                                     || (std::ranges::input_range<T>
                                         && std::unsigned_integral<std::ranges::range_value_t<T>>) )
                                    && (!std::same_as<std::remove_cvref_t<T>, std::string>
                                        && !std::same_as<std::remove_cvref_t<T>, std::string_view>
                                        && !std::same_as<std::decay_t<T>, const char*>);

    template <validity_bitmap_input R>
    validity_bitmap ensure_validity_bitmap(std::size_t size, R&& validity_input)
    {
        return detail::ensure_validity_bitmap_impl(size, std::forward<R>(validity_input));
    }
 
}  // namespace sparrow