/home/runner/work/sparrow/sparrow/include/sparrow/layout/array_base.hpp

CRTP base class providing common immutable interface for arrays with bitmaps.

CRTP base class providing common immutable interface for arrays with bitmaps. This class defines and implements the standard interface for arrays that hold nullable elements using a validity bitmap. It provides efficient iteration, element access, and range-based operations while maintaining Arrow format compatibility.

Key features:

• Const-correct element access with bounds checking
• STL-compatible iterator interface
• Range-based operations for values and validity bitmap
• Efficient slicing operations
• Arrow metadata access

Template Parameters

D	The derived array implementation type (CRTP pattern)

Precondition

D must specialize array_inner_types<D>

D must implement required virtual methods (value, value_cbegin, value_cend, get_bitmap)

Postcondition

Provides complete const array interface

Maintains Arrow format compatibility

Thread-safe for read operations

class my_array : public array_crtp_base<my_array> {
    // Implement required methods
};
 
my_array arr = ...;
auto nullable_elem = arr[0];  // Access with null checking
for (const auto& elem : arr) { ... }  // Range-based iteration

// 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 mplied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
#pragma once
 
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <ranges>
#include <utility>
 
#include "sparrow/arrow_array_schema_proxy.hpp"
#include "sparrow/buffer/dynamic_bitset/dynamic_bitset_view.hpp"
#include "sparrow/layout/array_access.hpp"
#include "sparrow/layout/layout_iterator.hpp"
#include "sparrow/utils/crtp_base.hpp"
#include "sparrow/utils/iterator.hpp"
#include "sparrow/utils/nullable.hpp"
 
namespace sparrow
{
    struct array_inner_types_base
    {
        using bitmap_type = dynamic_bitset_view<std::uint8_t>;
    };

    template <class D>
    struct array_inner_types;

    template <class D>
    class array_crtp_base : public crtp_base<D>
    {
    public:
 
        using self_type = array_crtp_base<D>;
        using derived_type = D;
 
        using inner_types = array_inner_types<derived_type>;
 
        using size_type = std::size_t;
        using difference_type = std::ptrdiff_t;
 
        using bitmap_type = typename inner_types::bitmap_type;
        using bitmap_const_reference = bitmap_type::const_reference;
        using bitmap_iterator = bitmap_type::iterator;
        using const_bitmap_iterator = bitmap_type::const_iterator;
        using const_bitmap_range = std::ranges::subrange<const_bitmap_iterator>;
 
        using inner_value_type = typename inner_types::inner_value_type;
        using value_type = nullable<inner_value_type>;
 
        using inner_const_reference = typename inner_types::inner_const_reference;
        using const_reference = nullable<inner_const_reference, bitmap_const_reference>;
 
        using const_value_iterator = typename inner_types::const_value_iterator;
        using const_value_range = std::ranges::subrange<const_value_iterator>;
 
        using iterator_tag = typename inner_types::iterator_tag;
 
        struct iterator_types
        {
            using value_type = self_type::value_type;
            using reference = self_type::const_reference;
            using value_iterator = self_type::const_value_iterator;
            using bitmap_iterator = self_type::const_bitmap_iterator;
            using iterator_tag = self_type::iterator_tag;
        };
 
        using const_iterator = layout_iterator<iterator_types>;
        using const_reverse_iterator = std::reverse_iterator<const_iterator>;

        [[nodiscard]] constexpr std::optional<std::string_view> name() const;

        [[nodiscard]] std::optional<key_value_view> metadata() const;

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

        [[nodiscard]] constexpr size_type size() const;

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

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

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

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

        [[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 const_reverse_iterator rbegin() const;

        [[nodiscard]] constexpr const_reverse_iterator rend() const;

        [[nodiscard]] constexpr const_reverse_iterator crbegin() const;

        [[nodiscard]] constexpr const_reverse_iterator crend() const;

        [[nodiscard]] constexpr const_bitmap_range bitmap() const;

        [[nodiscard]] constexpr const_value_range values() const;

        [[nodiscard]] constexpr D slice(size_type start, size_type end) const;

        [[nodiscard]] constexpr D slice_view(size_type start, size_type end) const;
 
    protected:

        explicit array_crtp_base(arrow_proxy);
 
        constexpr array_crtp_base(const array_crtp_base&) = default;
        constexpr array_crtp_base& operator=(const array_crtp_base&) = default;
 
        constexpr array_crtp_base(array_crtp_base&&) noexcept = default;
        constexpr array_crtp_base& operator=(array_crtp_base&&) noexcept = default;

        [[nodiscard]] constexpr arrow_proxy& get_arrow_proxy() noexcept;

        [[nodiscard]] constexpr const arrow_proxy& get_arrow_proxy() const noexcept;

        constexpr bitmap_const_reference has_value(size_type i) const;

        constexpr const_bitmap_iterator bitmap_begin() const;

        constexpr const_bitmap_iterator bitmap_end() const;

        constexpr const_bitmap_iterator bitmap_cbegin() const;

        constexpr const_bitmap_iterator bitmap_cend() const;
 
    private:
 
        arrow_proxy m_proxy;  
 
        // friend classes
        friend class layout_iterator<iterator_types>;
        friend class detail::array_access;
#if defined(__cpp_lib_format)
        friend struct std::formatter<D>;
#endif
    };
 
    template <class D>
    constexpr bool operator==(const array_crtp_base<D>& lhs, const array_crtp_base<D>& rhs);
 
    /**********************************
     * array_crtp_base implementation *
     **********************************/
 
    template <class D>
    constexpr std::optional<std::string_view> array_crtp_base<D>::name() const
    {
        return get_arrow_proxy().name();
    }
 
    template <class D>
    std::optional<key_value_view> array_crtp_base<D>::metadata() const
    {
        return get_arrow_proxy().metadata();
    }
 
    template <class D>
    constexpr bool array_crtp_base<D>::empty() const
    {
        return size() == size_type(0);
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::size() const -> size_type
    {
        return static_cast<size_type>(get_arrow_proxy().length());
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::at(size_type i) const -> const_reference
    {
        if (i >= size())
        {
            const std::string error_message = "Index " + std::to_string(i)
                                              + " is greater or equal to size of array ("
                                              + std::to_string(size()) + ")";
            throw std::out_of_range(error_message);
        }
        return (*this)[i];
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::operator[](size_type i) const -> const_reference
    {
        auto& derived_cast = this->derived_cast();
        SPARROW_ASSERT_TRUE(i < derived_cast.size());
        return const_reference(inner_const_reference(derived_cast.value(i)), derived_cast.has_value(i));
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::front() const -> const_reference
    {
        SPARROW_ASSERT_TRUE(!empty());
        return (*this)[size_type(0)];
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::back() const -> const_reference
    {
        SPARROW_ASSERT_TRUE(!empty());
        return (*this)[size() - 1];
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::begin() const -> const_iterator
    {
        return cbegin();
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::end() const -> const_iterator
    {
        return cend();
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::cbegin() const -> const_iterator
    {
        return const_iterator(this->derived_cast().value_cbegin(), bitmap_begin());
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::cend() const -> const_iterator
    {
        return const_iterator(this->derived_cast().value_cend(), bitmap_end());
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::rbegin() const -> const_reverse_iterator
    {
        return crbegin();
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::rend() const -> const_reverse_iterator
    {
        return crend();
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::crbegin() const -> const_reverse_iterator
    {
        return const_reverse_iterator(cend());
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::crend() const -> const_reverse_iterator
    {
        return const_reverse_iterator(cbegin());
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::bitmap() const -> const_bitmap_range
    {
        return const_bitmap_range(bitmap_begin(), bitmap_end());
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::values() const -> const_value_range
    {
        return const_value_range(this->derived_cast().value_cbegin(), this->derived_cast().value_cend());
    }
 
    template <class D>
    array_crtp_base<D>::array_crtp_base(arrow_proxy proxy)
        : m_proxy(std::move(proxy))
    {
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::get_arrow_proxy() noexcept -> arrow_proxy&
    {
        return m_proxy;
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::get_arrow_proxy() const noexcept -> const arrow_proxy&
    {
        return m_proxy;
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::has_value(size_type i) const -> bitmap_const_reference
    {
        SPARROW_ASSERT_TRUE(i < size());
        return *sparrow::next(bitmap_begin(), i);
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::bitmap_begin() const -> const_bitmap_iterator
    {
        return sparrow::next(this->derived_cast().get_bitmap().cbegin(), get_arrow_proxy().offset());
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::bitmap_end() const -> const_bitmap_iterator
    {
        return sparrow::next(bitmap_begin(), size());
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::bitmap_cbegin() const -> const_bitmap_iterator
    {
        return bitmap_begin();
    }
 
    template <class D>
    constexpr auto array_crtp_base<D>::bitmap_cend() const -> const_bitmap_iterator
    {
        return bitmap_end();
    }
 
    template <class D>
    constexpr D array_crtp_base<D>::slice(size_type start, size_type end) const
    {
        SPARROW_ASSERT_TRUE(start <= end);
        return D{get_arrow_proxy().slice(start, end)};
    }
 
    template <class D>
    constexpr D array_crtp_base<D>::slice_view(size_type start, size_type end) const
    {
        SPARROW_ASSERT_TRUE(start <= end);
        return D{get_arrow_proxy().slice_view(start, end)};
    }
 
    /*
     * @brief Equality comparison operator for arrays.
     *
     * Compares two arrays element-wise, including both values and validity flags.
     *
     * @tparam D Array type
     * @param lhs First array to compare
     * @param rhs Second array to compare
     * @return true if arrays are element-wise equal, false otherwise
     *
     * @post Returns true iff arrays have same size and all elements compare equal
     * @post Comparison includes both values and validity states
     */
    template <class D>
    constexpr bool operator==(const array_crtp_base<D>& lhs, const array_crtp_base<D>& rhs)
    {
        return std::ranges::equal(lhs, rhs);
    }
}
 
#if defined(__cpp_lib_format)
 
template <typename D>
    requires std::derived_from<D, sparrow::array_crtp_base<D>>
struct std::formatter<D>
{
    constexpr auto parse(std::format_parse_context& ctx)
    {
        return ctx.begin();  // Simple implementation
    }
 
    auto format(const D& ar, std::format_context& ctx) const
    {
        const auto& proxy = ar.get_arrow_proxy();
        std::string type;
        if (proxy.dictionary())
        {
            std::format_to(ctx.out(), "Dictionary<{}>", proxy.dictionary()->data_type());
        }
        else
        {
            std::format_to(ctx.out(), "{}", proxy.data_type());
        }
        std::format_to(ctx.out(), " [name={} | size={}] <", ar.name().value_or("nullptr"), proxy.length());
 
        std::for_each(
            ar.cbegin(),
            std::prev(ar.cend()),
            [&ctx](const auto& value)
            {
                std::format_to(ctx.out(), "{}, ", value);
            }
        );
        return std::format_to(ctx.out(), "{}>", ar.back());
    }
};
 
template <typename D>
    requires std::derived_from<D, sparrow::array_crtp_base<D>>
std::ostream& operator<<(std::ostream& os, const D& value)
{
    os << std::format("{}", value);
    return os;
}
 
#endif