main.hpp

/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */

// SPDX-FileCopyrightText: 2021 - 2025 Kohei Yoshida
//
// SPDX-License-Identifier: MIT

#pragma once

#include "../../global.hpp"
#include "../types.hpp"
#include "../util.hpp"
#include "./block_util.hpp"
#include "./iterator.hpp"

#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
#include <iostream>
#endif

namespace mdds { namespace mtv { namespace soa {

template<typename Traits = mdds::mtv::default_traits>
class multi_type_vector
{
public:
    using size_type = std::size_t;
    using block_funcs = typename Traits::block_funcs;

    using event_func = typename Traits::event_func;

private:
    struct block_slot_type
    {
        size_type position = 0;
        size_type size = 0;
        base_element_block* element_block = nullptr;

        block_slot_type() noexcept(std::is_fundamental_v<size_type>)
        {}
        block_slot_type(size_type _position, size_type _size) noexcept(std::is_fundamental_v<size_type>)
            : position(_position), size(_size)
        {}
    };

    struct blocks_type
    {
        std::vector<size_type> positions;
        std::vector<size_type> sizes;
        std::vector<base_element_block*> element_blocks;

        static constexpr bool nothrow_default_constructible_v =
            std::is_nothrow_default_constructible_v<std::vector<size_type>> &&
            std::is_nothrow_default_constructible_v<std::vector<base_element_block*>>;

        static constexpr bool nothrow_move_constructible_v =
            std::is_nothrow_move_constructible_v<std::vector<size_type>> &&
            std::is_nothrow_move_constructible_v<std::vector<base_element_block*>>;

        static constexpr bool nothrow_value_swappable_v =
            noexcept(std::swap(std::declval<size_type&>(), std::declval<size_type&>())) &&
            noexcept(std::swap(std::declval<base_element_block*&>(), std::declval<base_element_block*&>()));

        static constexpr bool nothrow_swappable_v = std::is_nothrow_swappable_v<std::vector<size_type>> &&
                                                    std::is_nothrow_swappable_v<std::vector<base_element_block*>>;

        blocks_type() noexcept(nothrow_default_constructible_v);
        blocks_type(mtv::detail::clone_construction_type, const blocks_type& other);
        blocks_type(const blocks_type& other);
        blocks_type(blocks_type&& other) noexcept(nothrow_move_constructible_v);

        void pop_back()
        {
            positions.pop_back();
            sizes.pop_back();
            element_blocks.pop_back();
        }

        void push_back(size_type pos, size_type size, base_element_block* data)
        {
            positions.push_back(pos);
            sizes.push_back(size);
            element_blocks.push_back(data);
        }

        void push_back(const block_slot_type& slot)
        {
            positions.push_back(slot.position);
            sizes.push_back(slot.size);
            element_blocks.push_back(slot.element_block);
        }

        void erase(size_type index);
        void erase(size_type index, size_type size);
        void insert(size_type index, size_type size);
        void insert(size_type index, size_type pos, size_type size, base_element_block* data);
        void insert(size_type index, const blocks_type& new_blocks);

        void calc_block_position(size_type index);

        size_type calc_next_block_position(size_type index);

        void swap(size_type index1, size_type index2) noexcept(nothrow_value_swappable_v);

        void swap(blocks_type& other) noexcept(nothrow_swappable_v);

        void reserve(size_type n);

        bool equals(const blocks_type& other) const;

        void clear();

        void check_integrity() const;
    };

    struct blocks_to_transfer
    {
        blocks_type blocks;
        size_type insert_index = 0;
    };

    struct iterator_trait
    {
        using parent = multi_type_vector;
        using positions_type = std::vector<size_type>;
        using sizes_type = std::vector<size_type>;
        using element_blocks_type = std::vector<base_element_block*>;

        using positions_iterator_type = typename positions_type::iterator;
        using sizes_iterator_type = typename sizes_type::iterator;
        using element_blocks_iterator_type = typename element_blocks_type::iterator;

        using private_data_update = mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type>;
    };

    struct const_iterator_trait
    {
        using parent = multi_type_vector;
        using positions_type = std::vector<size_type>;
        using sizes_type = std::vector<size_type>;
        using element_blocks_type = std::vector<base_element_block*>;

        using positions_iterator_type = typename positions_type::const_iterator;
        using sizes_iterator_type = typename sizes_type::const_iterator;
        using element_blocks_iterator_type = typename element_blocks_type::const_iterator;

        using private_data_update = mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type>;
    };

    struct reverse_iterator_trait
    {
        using parent = multi_type_vector;
        using positions_type = std::vector<size_type>;
        using sizes_type = std::vector<size_type>;
        using element_blocks_type = std::vector<base_element_block*>;

        using positions_iterator_type = typename positions_type::reverse_iterator;
        using sizes_iterator_type = typename sizes_type::reverse_iterator;
        using element_blocks_iterator_type = typename element_blocks_type::reverse_iterator;

        using private_data_update = mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type>;
    };

    struct const_reverse_iterator_trait
    {
        using parent = multi_type_vector;
        using positions_type = std::vector<size_type>;
        using sizes_type = std::vector<size_type>;
        using element_blocks_type = std::vector<base_element_block*>;

        using positions_iterator_type = typename positions_type::const_reverse_iterator;
        using sizes_iterator_type = typename sizes_type::const_reverse_iterator;
        using element_blocks_iterator_type = typename element_blocks_type::const_reverse_iterator;

        using private_data_update = mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type>;
    };

    struct element_block_deleter
    {
        void operator()(const base_element_block* p)
        {
            block_funcs::delete_block(p);
        }
    };

    static constexpr bool nothrow_default_constructible_v = std::is_nothrow_default_constructible_v<event_func> &&
                                                            std::is_nothrow_default_constructible_v<blocks_type> &&
                                                            std::is_nothrow_default_constructible_v<size_type>;

    static constexpr bool nothrow_move_constructible_v = std::is_nothrow_move_constructible_v<event_func> &&
                                                         std::is_nothrow_move_constructible_v<blocks_type> &&
                                                         std::is_nothrow_move_constructible_v<size_type>;

    static constexpr bool nothrow_swappable_v = std::is_nothrow_swappable_v<event_func> &&
                                                std::is_nothrow_swappable_v<size_type> &&
                                                std::is_nothrow_swappable_v<blocks_type>;

    static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;

    multi_type_vector(mtv::detail::clone_construction_type, const multi_type_vector& other);

public:
    using iterator = detail::iterator_base<iterator_trait>;
    using const_iterator = detail::const_iterator_base<const_iterator_trait, iterator>;

    using reverse_iterator = detail::iterator_base<reverse_iterator_trait>;
    using const_reverse_iterator = detail::const_iterator_base<const_reverse_iterator_trait, reverse_iterator>;

    using position_type = std::pair<iterator, size_type>;
    using const_position_type = std::pair<const_iterator, size_type>;

    using value_type = mdds::detail::mtv::iterator_value_node<multi_type_vector, size_type>;

    static position_type next_position(const position_type& pos);

    static position_type advance_position(const position_type& pos, int steps);

    static const_position_type next_position(const const_position_type& pos);

    static const_position_type advance_position(const const_position_type& pos, int steps);

    static size_type logical_position(const const_position_type& pos) noexcept(std::is_fundamental_v<size_type>);

    template<typename _Blk>
    static typename _Blk::value_type get(const const_position_type& pos);

    event_func& event_handler();
    const event_func& event_handler() const;

    multi_type_vector() noexcept(nothrow_default_constructible_v);

    multi_type_vector(const event_func& hdl);

    multi_type_vector(event_func&& hdl);

    multi_type_vector(size_type init_size);

    template<typename T>
    multi_type_vector(size_type init_size, const T& value);

    template<typename T>
    multi_type_vector(size_type init_size, const T& it_begin, const T& it_end);

    multi_type_vector(const multi_type_vector& other);

    multi_type_vector(multi_type_vector&& other) noexcept(nothrow_move_constructible_v);

    ~multi_type_vector();

    multi_type_vector clone() const;

    position_type position(size_type pos);

    position_type position(const iterator& pos_hint, size_type pos);

    const_position_type position(size_type pos) const;

    const_position_type position(const const_iterator& pos_hint, size_type pos) const;

    iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);

    iterator transfer(
        const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);

    template<typename T>
    iterator set(size_type pos, const T& value);

    template<typename T>
    iterator set(const iterator& pos_hint, size_type pos, const T& value);

    template<typename T>
    iterator set(size_type pos, const T& it_begin, const T& it_end);

    template<typename T>
    iterator set(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);

    template<typename T>
    iterator push_back(T&& value);

    iterator push_back_empty();

    template<typename T, typename... Args>
    iterator emplace_back(Args&&... args);

    template<typename T>
    iterator insert(size_type pos, const T& it_begin, const T& it_end);

    template<typename T>
    iterator insert(const iterator& pos_hint, size_type pos, const T& it_begin, const T& it_end);

    mtv::element_t get_type(size_type pos) const;

    bool is_empty(size_type pos) const;

    iterator set_empty(size_type start_pos, size_type end_pos);

    iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);

    void erase(size_type start_pos, size_type end_pos);

    iterator insert_empty(size_type pos, size_type length);

    iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);

    void clear();

    size_type size() const;

    size_type block_size() const;

    bool empty() const;

    template<typename T>
    void get(size_type pos, T& value) const;

    template<typename T>
    T get(size_type pos) const;

    template<typename T>
    T release(size_type pos);

    template<typename T>
    iterator release(size_type pos, T& value);

    template<typename T>
    iterator release(const iterator& pos_hint, size_type pos, T& value);

    void release();

    iterator release_range(size_type start_pos, size_type end_pos);

    iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);

    iterator begin();
    iterator end();

    const_iterator begin() const;
    const_iterator end() const;

    const_iterator cbegin() const;
    const_iterator cend() const;

    reverse_iterator rbegin();
    reverse_iterator rend();

    const_reverse_iterator rbegin() const;
    const_reverse_iterator rend() const;

    const_reverse_iterator crbegin() const;
    const_reverse_iterator crend() const;

    void resize(size_type new_size);

    void swap(multi_type_vector& other) noexcept(nothrow_swappable_v);

    void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);

    void shrink_to_fit();

    bool operator==(const multi_type_vector& other) const;
    bool operator!=(const multi_type_vector& other) const;

    multi_type_vector& operator=(const multi_type_vector& other);
    multi_type_vector& operator=(multi_type_vector&& other) noexcept(nothrow_move_assignable_v);

    template<typename T>
    static mtv::element_t get_element_type(const T& elem);

#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
    void dump_blocks(std::ostream& os) const;

    void check_block_integrity() const;
#endif

private:
    void delete_element_block(size_type block_index);

    void delete_element_blocks(size_type start, size_type end);

    template<typename T>
    void get_impl(size_type pos, T& value) const;

    template<typename T>
    bool set_cells_precheck(size_type row, const T& it_begin, const T& it_end, size_type& end_pos);

    template<typename T>
    iterator set_impl(size_type pos, size_type block_index, const T& value);

    template<typename T>
    iterator release_impl(size_type pos, size_type block_index, T& value);

    void swap_impl(
        multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
        size_type block_index2, size_type dblock_index1, size_type dblock_index2);

    void swap_single_block(
        multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
        size_type other_block_index);

    void swap_single_to_multi_blocks(
        multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
        size_type dst_block_index1, size_type dst_block_index2);

    void swap_multi_to_multi_blocks(
        multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
        size_type block_index2, size_type dblock_index1, size_type dblock_index2);

    template<typename T>
    iterator insert_cells_impl(size_type row, size_type block_index, const T& it_begin, const T& it_end);

    void resize_impl(size_type new_size);

    iterator transfer_multi_blocks(
        size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2, multi_type_vector& dest,
        size_type dest_pos);

    iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);

    iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index, bool overwrite);

    iterator set_empty_in_multi_blocks(
        size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, bool overwrite);

    void erase_impl(size_type start_pos, size_type end_pos);
    void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_index);

    iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);

    void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);

    void prepare_blocks_to_transfer(
        blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
        size_type offset2);

    iterator set_whole_block_empty(size_type block_index, bool overwrite);

    template<typename T>
    iterator push_back_impl(T&& value);

    template<typename T, typename... Args>
    iterator emplace_back_impl(Args&&... args);

    template<typename T>
    iterator set_cells_impl(
        size_type row, size_type end_row, size_type block_index1, const T& it_begin, const T& it_end);

    template<typename T>
    iterator set_cells_to_single_block(
        size_type start_row, size_type end_row, size_type block_index, const T& it_begin, const T& it_end);

    template<typename T>
    iterator set_cells_to_multi_blocks(
        size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
        const T& it_end);

    template<typename T>
    iterator set_cells_to_multi_blocks_block1_non_equal(
        size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
        const T& it_end);

    template<typename T>
    iterator set_cells_to_multi_blocks_block1_non_empty(
        size_type start_row, size_type end_row, size_type block_index1, size_type block_index2, const T& it_begin,
        const T& it_end);

    template<typename T>
    iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block, const T& cell);

    template<typename T>
    iterator set_cell_to_non_empty_block_of_size_one(size_type block_index, const T& cell);

    size_type get_block_position(size_type row, size_type start_block_index = 0) const;

    size_type get_block_position(const typename value_type::private_data& pos_data, size_type row) const;

    template<typename T>
    void create_new_block_with_new_cell(size_type block_index, T&& cell);

    template<typename T, typename... Args>
    void create_new_block_with_emplace_back(size_type block_index, const T& t, Args&&... args);

    template<typename T>
    void append_cell_to_block(size_type block_index, const T& cell);

    template<typename T>
    bool append_to_prev_block(
        size_type block_index, element_t cat, size_type length, const T& it_begin, const T& it_end);

    template<typename T>
    void insert_cells_to_middle(size_type row, size_type block_index, const T& it_begin, const T& it_end);

    template<typename T>
    iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block, const T& cell);

    template<typename T>
    void set_cell_to_top_of_data_block(size_type block_index, const T& cell);

    template<typename T>
    void set_cell_to_bottom_of_data_block(size_type block_index, const T& cell);

    iterator transfer_impl(
        size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);

    iterator transfer_single_block(
        size_type start_pos, size_type end_pos, size_type block_index1, multi_type_vector& dest, size_type dest_pos);

    size_type merge_with_adjacent_blocks(size_type block_index);

    bool merge_with_next_block(size_type block_index);

    size_type set_new_block_to_middle(
        size_type block_index, size_type offset, size_type new_block_size, bool overwrite);

    bool is_previous_block_of_type(size_type block_index, element_t cat) const;

    bool is_next_block_of_type(size_type block_index, element_t cat) const;

    base_element_block* exchange_elements(
        const base_element_block& src_data, size_type src_offset, size_type dst_index, size_type dst_offset,
        size_type len);

    void exchange_elements(
        const base_element_block& src_blk, size_type src_offset, size_type dst_index1, size_type dst_offset1,
        size_type dst_index2, size_type dst_offset2, size_type len, blocks_type& new_blocks);

    bool append_empty(size_type len);

    inline iterator get_iterator(size_type block_index)
    {
        auto iter_pos = m_block_store.positions.begin();
        std::advance(iter_pos, block_index);
        auto iter_size = m_block_store.sizes.begin();
        std::advance(iter_size, block_index);
        auto iter_elem = m_block_store.element_blocks.begin();
        std::advance(iter_elem, block_index);

        return iterator(
            {iter_pos, iter_size, iter_elem},
            {m_block_store.positions.end(), m_block_store.sizes.end(), m_block_store.element_blocks.end()}, this,
            block_index);
    }

    inline const_iterator get_const_iterator(size_type block_index) const
    {
        auto iter_pos = m_block_store.positions.cbegin();
        std::advance(iter_pos, block_index);
        auto iter_size = m_block_store.sizes.cbegin();
        std::advance(iter_size, block_index);
        auto iter_elem = m_block_store.element_blocks.cbegin();
        std::advance(iter_elem, block_index);

        return const_iterator(
            {iter_pos, iter_size, iter_elem},
            {m_block_store.positions.cend(), m_block_store.sizes.cend(), m_block_store.element_blocks.cend()}, this,
            block_index);
    }

#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
    void debug_check_full(std::string_view location);
#endif

private:
    using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Traits::loop_unrolling>;

    event_func m_hdl_event;
    blocks_type m_block_store;
    size_type m_cur_size;

#ifdef MDDS_MULTI_TYPE_VECTOR_TRACE
    mutable int m_trace_call_depth = 0;
#endif
};

}}} // namespace mdds::mtv::soa

#include "main_def.inl"

/* vim:set shiftwidth=4 softtabstop=4 expandtab: */