aos/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 "./iterator.hpp"
#include "./block_util.hpp"
 
#ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
#include <iostream>
#endif
 
namespace mdds { namespace mtv { namespace aos {

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
    {
        size_type position;
        size_type size;
        base_element_block* data;
 
        block() noexcept(std::is_fundamental_v<size_type>);
        block(size_type _position, size_type _size) noexcept(std::is_fundamental_v<size_type>);
        block(size_type _position, size_type _size, base_element_block* _data) noexcept(
            std::is_fundamental_v<size_type>);
        block(const block& other) = default;
        block(block&& other) = default;
        ~block() = default;
 
        block& operator=(const block&) = default;
        block& operator=(block&&) = default;
 
        void swap(block& other) noexcept(std::is_fundamental_v<size_type>);
    };
 
    struct element_block_deleter
    {
        void operator()(const base_element_block* p)
        {
            block_funcs::delete_block(p);
        }
    };
 
    typedef std::vector<block> blocks_type;
 
    struct blocks_to_transfer
    {
        blocks_type blocks;
        size_type insert_index;
 
        blocks_to_transfer();
    };
 
    struct iterator_trait
    {
        typedef multi_type_vector parent;
        typedef blocks_type blocks;
        typedef typename blocks_type::iterator base_iterator;
    };
 
    struct reverse_iterator_trait
    {
        typedef multi_type_vector parent;
        typedef blocks_type blocks;
        typedef typename blocks_type::reverse_iterator base_iterator;
    };
 
    struct const_iterator_trait
    {
        typedef multi_type_vector parent;
        typedef blocks_type blocks;
        typedef typename blocks_type::const_iterator base_iterator;
    };
 
    struct const_reverse_iterator_trait
    {
        typedef multi_type_vector parent;
        typedef blocks_type blocks;
        typedef typename blocks_type::const_reverse_iterator base_iterator;
    };
 
    typedef mdds::detail::mtv::iterator_value_node<multi_type_vector, size_type> itr_node;
    typedef mdds::detail::mtv::private_data_forward_update<multi_type_vector, size_type> itr_forward_update;
    typedef mdds::detail::mtv::private_data_no_update<multi_type_vector, size_type> itr_no_update;
 
    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:
    typedef detail::iterator_base<iterator_trait, itr_forward_update> iterator;
    typedef detail::iterator_base<reverse_iterator_trait, itr_no_update> reverse_iterator;
 
    typedef detail::const_iterator_base<const_iterator_trait, itr_forward_update, iterator> const_iterator;
    typedef detail::const_iterator_base<const_reverse_iterator_trait, itr_no_update, reverse_iterator>
        const_reverse_iterator;

    typedef itr_node value_type;
 
    typedef std::pair<iterator, size_type> position_type;
    typedef std::pair<const_iterator, size_type> const_position_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);
 
    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;
 
    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;

    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);

    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);

    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);

    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 noexcept(std::is_nothrow_copy_constructible_v<size_type>);

    size_type block_size() const noexcept;

    bool empty() const noexcept;

    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(block& blk);

    void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
 
    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);
 
    template<typename T>
    iterator push_back_impl(T&& value);
 
    template<typename T, typename... Args>
    iterator emplace_back_impl(Args&&... args);

    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;
 
    void resize_impl(size_type new_size);
 
    template<typename T>
    void create_new_block_with_new_cell(base_element_block*& data, T&& cell);
 
    template<typename T, typename... Args>
    void create_new_block_with_emplace_back(base_element_block*& data, const T& t, Args&&... args);
 
    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 append_cell_to_block(size_type block_index, const T& cell);
 
    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_block_of_size_one(size_type block_index, 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);

    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);
 
    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);
 
    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);
 
    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_pos);

    iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
 
    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 insert_cells_impl(size_type row, size_type block_index, 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);

    size_type merge_with_adjacent_blocks(size_type block_index);

    bool merge_with_next_block(size_type block_index);
 
    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);

    block& set_new_block_to_middle(size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
 
    block* get_previous_block_of_type(size_type block_index, element_t cat);

    block* get_next_block_of_type(size_type block_index, element_t cat);

    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_data, 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)
    {
        typename blocks_type::iterator block_pos = m_blocks.begin();
        std::advance(block_pos, block_index);
        return iterator(block_pos, m_blocks.end(), this, block_index);
    }
 
    inline const_iterator get_const_iterator(size_type block_index) const
    {
        typename blocks_type::const_iterator block_pos = m_blocks.begin();
        std::advance(block_pos, block_index);
        return const_iterator(block_pos, m_blocks.end(), 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_blocks;
    size_type m_cur_size;
};
 
}}} // namespace mdds::mtv::aos
 
#include "main_def.inl"
 
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */