29 #ifndef INCLUDED_MDDS_MULTI_TYPE_VECTOR_DIR_AOS_MAIN_HPP
30 #define INCLUDED_MDDS_MULTI_TYPE_VECTOR_DIR_AOS_MAIN_HPP
32 #include "../../global.hpp"
33 #include "../types.hpp"
34 #include "../util.hpp"
35 #include "./iterator.hpp"
36 #include "./block_util.hpp"
38 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
42 namespace mdds {
namespace mtv {
namespace aos {
71 template<
typename Traits = mdds::mtv::default_traits>
75 typedef size_t size_type;
78 typedef mdds::mtv::element_t element_category_type;
79 using block_funcs =
typename Traits::block_funcs;
105 element_block_type* data;
108 block(size_type _position, size_type _size);
109 block(size_type _position, size_type _size, element_block_type* _data);
110 block(
const block& other) =
default;
111 block(block&& other) =
default;
113 void swap(block& other);
114 void clone_to(block& other)
const;
116 block& operator=(
const block&) =
default;
119 struct element_block_deleter
121 void operator()(
const element_block_type* p)
123 block_funcs::delete_block(p);
127 typedef std::vector<block> blocks_type;
129 struct blocks_to_transfer
132 size_type insert_index;
134 blocks_to_transfer();
137 struct iterator_trait
140 typedef blocks_type blocks;
141 typedef typename blocks_type::iterator base_iterator;
144 struct reverse_iterator_trait
147 typedef blocks_type blocks;
148 typedef typename blocks_type::reverse_iterator base_iterator;
151 struct const_iterator_trait
154 typedef blocks_type blocks;
155 typedef typename blocks_type::const_iterator base_iterator;
158 struct const_reverse_iterator_trait
161 typedef blocks_type blocks;
162 typedef typename blocks_type::const_reverse_iterator base_iterator;
170 typedef detail::iterator_base<iterator_trait, itr_forward_update> iterator;
171 typedef detail::iterator_base<reverse_iterator_trait, itr_no_update> reverse_iterator;
173 typedef detail::const_iterator_base<const_iterator_trait, itr_forward_update, iterator> const_iterator;
174 typedef detail::const_iterator_base<const_reverse_iterator_trait, itr_no_update, reverse_iterator>
175 const_reverse_iterator;
194 typedef std::pair<iterator, size_type> position_type;
195 typedef std::pair<const_iterator, size_type> const_position_type;
205 static position_type
next_position(
const position_type& pos);
226 static const_position_type
next_position(
const const_position_type& pos);
237 static const_position_type
advance_position(
const const_position_type& pos,
int steps);
257 template<
typename Blk>
258 static typename Blk::value_type
get(
const const_position_type& pos);
263 const_iterator begin()
const;
264 const_iterator end()
const;
266 const_iterator cbegin()
const;
267 const_iterator cend()
const;
269 reverse_iterator rbegin();
270 reverse_iterator rend();
272 const_reverse_iterator rbegin()
const;
273 const_reverse_iterator rend()
const;
275 const_reverse_iterator crbegin()
const;
276 const_reverse_iterator crend()
const;
375 iterator
set(size_type pos,
const T& value);
410 iterator
set(
const iterator& pos_hint, size_type pos,
const T& value);
434 iterator
set(size_type pos,
const T& it_begin,
const T& it_end);
474 iterator
set(
const iterator& pos_hint, size_type pos,
const T& it_begin,
const T& it_end);
519 iterator
insert(size_type pos,
const T& it_begin,
const T& it_end);
559 iterator
insert(
const iterator& pos_hint, size_type pos,
const T& it_begin,
const T& it_end);
572 void get(size_type pos, T& value)
const;
586 T
get(size_type pos)
const;
622 iterator
release(size_type pos, T& value);
644 iterator
release(
const iterator& pos_hint, size_type pos, T& value);
671 iterator
release_range(size_type start_pos, size_type end_pos);
697 iterator
release_range(
const iterator& pos_hint, size_type start_pos, size_type end_pos);
715 position_type
position(size_type pos);
736 position_type
position(
const iterator& pos_hint, size_type pos);
751 const_position_type
position(size_type pos)
const;
769 const_position_type
position(
const const_iterator& pos_hint, size_type pos)
const;
825 const iterator& pos_hint, size_type start_pos, size_type end_pos,
multi_type_vector& dest, size_type dest_pos);
834 mtv::element_t
get_type(size_type pos)
const;
862 iterator
set_empty(size_type start_pos, size_type end_pos);
893 iterator
set_empty(
const iterator& pos_hint, size_type start_pos, size_type end_pos);
910 void erase(size_type start_pos, size_type end_pos);
966 iterator
insert_empty(
const iterator& pos_hint, size_type pos, size_type length);
979 size_type
size()
const;
1014 void resize(size_type new_size);
1051 template<
typename T>
1054 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1055 void dump_blocks(std::ostream& os)
const;
1057 void check_block_integrity()
const;
1067 void delete_element_block(block& blk);
1076 void delete_element_blocks(
typename blocks_type::iterator it,
typename blocks_type::iterator it_end);
1078 template<
typename T>
1079 iterator set_impl(size_type pos, size_type block_index,
const T& value);
1081 template<
typename T>
1082 iterator release_impl(size_type pos, size_type block_index, T& value);
1084 template<
typename T>
1085 iterator push_back_impl(
const T& value);
1096 size_type get_block_position(size_type row, size_type start_block_index = 0)
const;
1104 void resize_impl(size_type new_size);
1106 template<
typename T>
1107 void create_new_block_with_new_cell(element_block_type*& data,
const T& cell);
1109 template<
typename T>
1110 iterator set_cell_to_middle_of_block(size_type block_index, size_type pos_in_block,
const T& cell);
1112 template<
typename T>
1113 void append_cell_to_block(size_type block_index,
const T& cell);
1115 template<
typename T>
1116 iterator set_cell_to_empty_block(size_type block_index, size_type pos_in_block,
const T& cell);
1118 template<
typename T>
1119 iterator set_cell_to_block_of_size_one(size_type block_index,
const T& cell);
1121 template<
typename T>
1122 void set_cell_to_top_of_data_block(size_type block_index,
const T& cell);
1124 template<
typename T>
1125 void set_cell_to_bottom_of_data_block(size_type block_index,
const T& cell);
1127 iterator transfer_impl(
1128 size_type start_pos, size_type end_pos, size_type block_index1,
multi_type_vector& dest, size_type dest_pos);
1133 iterator transfer_single_block(
1134 size_type start_pos, size_type end_pos, size_type block_index1,
multi_type_vector& dest, size_type dest_pos);
1140 iterator transfer_multi_blocks(
1141 size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2,
multi_type_vector& dest,
1142 size_type dest_pos);
1152 iterator set_empty_impl(size_type start_pos, size_type end_pos, size_type block_index1,
bool overwrite);
1155 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1156 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1158 void swap_single_block(
1159 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1160 size_type other_block_index);
1162 void swap_single_to_multi_blocks(
1163 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index,
1164 size_type dst_block_index1, size_type dst_block_index2);
1166 void swap_multi_to_multi_blocks(
1167 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos, size_type block_index1,
1168 size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1170 void insert_blocks_at(size_type
position, size_type insert_pos, blocks_type& new_blocks);
1172 void prepare_blocks_to_transfer(
1173 blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2,
1176 iterator set_whole_block_empty(size_type block_index,
bool overwrite);
1178 iterator set_empty_in_single_block(size_type start_row, size_type end_row, size_type block_index,
bool overwrite);
1189 iterator set_empty_in_multi_blocks(
1190 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
bool overwrite);
1192 void erase_impl(size_type start_pos, size_type end_pos);
1193 void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_pos);
1200 iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1202 template<
typename T>
1203 iterator set_cells_impl(
1204 size_type row, size_type end_row, size_type block_index1,
const T& it_begin,
const T& it_end);
1206 template<
typename T>
1207 iterator insert_cells_impl(size_type row, size_type block_index,
const T& it_begin,
const T& it_end);
1209 template<
typename T>
1210 iterator set_cells_to_single_block(
1211 size_type start_row, size_type end_row, size_type block_index,
const T& it_begin,
const T& it_end);
1213 template<
typename T>
1214 iterator set_cells_to_multi_blocks(
1215 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
const T& it_begin,
1218 template<
typename T>
1219 iterator set_cells_to_multi_blocks_block1_non_equal(
1220 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
const T& it_begin,
1223 template<
typename T>
1224 iterator set_cells_to_multi_blocks_block1_non_empty(
1225 size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
const T& it_begin,
1236 size_type merge_with_adjacent_blocks(size_type block_index);
1245 bool merge_with_next_block(size_type block_index);
1247 template<
typename T>
1248 bool append_to_prev_block(
1249 size_type block_index, element_category_type cat, size_type length,
const T& it_begin,
const T& it_end);
1251 template<
typename T>
1252 void insert_cells_to_middle(size_type row, size_type block_index,
const T& it_begin,
const T& it_end);
1267 block& set_new_block_to_middle(size_type block_index, size_type offset, size_type new_block_size,
bool overwrite);
1269 block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1278 block* get_next_block_of_type(size_type block_index, element_category_type cat);
1297 element_block_type* exchange_elements(
1298 const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset,
1301 void exchange_elements(
1302 const element_block_type& src_data, size_type src_offset, size_type dst_index1, size_type dst_offset1,
1303 size_type dst_index2, size_type dst_offset2, size_type len, blocks_type& new_blocks);
1305 bool append_empty(size_type len);
1307 inline iterator get_iterator(size_type block_index)
1309 typename blocks_type::iterator block_pos = m_blocks.begin();
1310 std::advance(block_pos, block_index);
1311 return iterator(block_pos, m_blocks.end(),
this, block_index);
1314 inline const_iterator get_const_iterator(size_type block_index)
const
1316 typename blocks_type::const_iterator block_pos = m_blocks.begin();
1317 std::advance(block_pos, block_index);
1318 return const_iterator(block_pos, m_blocks.end(),
this, block_index);
1322 using adjust_block_positions_func = detail::adjust_block_positions<blocks_type, Traits::loop_unrolling>;
1325 blocks_type m_blocks;
1326 size_type m_cur_size;
1331 #include "main_def.inl"
static mtv::element_t get_element_type(const T &elem)
Definition: iterator_node.hpp:41
void swap(multi_type_vector &other)
static position_type next_position(const position_type &pos)
static size_type logical_position(const const_position_type &pos)
iterator insert_empty(size_type pos, size_type length)
size_type block_size() const
typename Traits::event_func event_func
Definition: main.hpp:98
Definition: iterator_node.hpp:108
iterator insert(size_type pos, const T &it_begin, const T &it_end)
iterator push_back(const T &value)
void resize(size_type new_size)
iterator push_back_empty()
iterator release_range(size_type start_pos, size_type end_pos)
Definition: iterator_node.hpp:97
position_type position(size_type pos)
iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
static position_type advance_position(const position_type &pos, int steps)
Definition: flat_segment_tree.hpp:46
iterator set(size_type pos, const T &value)
Definition: types.hpp:159
void erase(size_type start_pos, size_type end_pos)
itr_node value_type
Definition: main.hpp:192
iterator set_empty(size_type start_pos, size_type end_pos)
bool is_empty(size_type pos) const
mtv::element_t get_type(size_type pos) const
Definition: iterator_node.hpp:65