28 #ifndef INCLUDED_MDDS_MULTI_TYPE_VECTOR_HPP 29 #define INCLUDED_MDDS_MULTI_TYPE_VECTOR_HPP 32 #include "multi_type_vector_types.hpp" 33 #include "multi_type_vector_itr.hpp" 40 #if defined(MDDS_UNIT_TEST) || defined (MDDS_MULTI_TYPE_VECTOR_DEBUG) 49 namespace detail {
namespace mtv {
65 T advance_position(
const T& pos,
int steps);
94 template<
typename _ElemBlockFunc,
typename _EventFunc = detail::mtv::event_func>
98 typedef size_t size_type;
101 typedef typename mdds::mtv::element_t element_category_type;
102 typedef _ElemBlockFunc element_block_func;
128 element_block_type* mp_data;
131 block(size_type _size);
132 block(size_type _size, element_block_type* _data);
133 block(
const block& other);
134 block(block&& other);
136 void swap(block& other);
137 void clone_to(block& other)
const;
139 block& operator=(block);
142 struct element_block_deleter
144 void operator() (
const element_block_type* p)
146 element_block_func::delete_block(p);
150 typedef std::vector<block> blocks_type;
152 struct blocks_to_transfer
155 size_type insert_index;
157 blocks_to_transfer();
160 struct iterator_trait
163 typedef blocks_type blocks;
164 typedef typename blocks_type::iterator base_iterator;
167 struct reverse_iterator_trait
170 typedef blocks_type blocks;
171 typedef typename blocks_type::reverse_iterator base_iterator;
174 struct const_iterator_trait
177 typedef blocks_type blocks;
178 typedef typename blocks_type::const_iterator base_iterator;
181 struct const_reverse_iterator_trait
184 typedef blocks_type blocks;
185 typedef typename blocks_type::const_reverse_iterator base_iterator;
217 typedef std::pair<iterator, size_type> position_type;
218 typedef std::pair<const_iterator, size_type> const_position_type;
228 static position_type next_position(
const position_type& pos);
239 static position_type advance_position(
const position_type& pos,
int steps);
249 static const_position_type next_position(
const const_position_type& pos);
260 static const_position_type advance_position(
const const_position_type& pos,
int steps);
270 static size_type logical_position(
const const_position_type& pos);
280 template<
typename _Blk>
281 static typename _Blk::value_type
get(
const const_position_type& pos);
286 const_iterator begin()
const;
287 const_iterator end()
const;
289 const_iterator cbegin()
const;
290 const_iterator cend()
const;
292 reverse_iterator rbegin();
293 reverse_iterator rend();
295 const_reverse_iterator rbegin()
const;
296 const_reverse_iterator rend()
const;
298 const_reverse_iterator crbegin()
const;
299 const_reverse_iterator crend()
const;
301 event_func& event_handler();
302 const event_func& event_handler()
const;
343 template<
typename _T>
359 template<
typename _T>
390 template<
typename _T>
391 iterator
set(size_type pos,
const _T& value);
425 template<
typename _T>
426 iterator
set(
const iterator& pos_hint, size_type pos,
const _T& value);
449 template<
typename _T>
450 iterator
set(size_type pos,
const _T& it_begin,
const _T& it_end);
489 template<
typename _T>
490 iterator
set(
const iterator& pos_hint, size_type pos,
const _T& it_begin,
const _T& it_end);
501 template<
typename _T>
502 iterator push_back(
const _T& value);
511 iterator push_back_empty();
534 template<
typename _T>
535 iterator insert(size_type pos,
const _T& it_begin,
const _T& it_end);
574 template<
typename _T>
575 iterator insert(
const iterator& pos_hint, size_type pos,
const _T& it_begin,
const _T& it_end);
587 template<
typename _T>
588 void get(size_type pos, _T& value)
const;
601 template<
typename _T>
602 _T
get(size_type pos)
const;
618 template<
typename _T>
619 _T release(size_type pos);
637 template<
typename _T>
638 iterator release(size_type pos, _T& value);
656 template<
typename _T>
657 iterator release(
const iterator& pos_hint, size_type pos, _T& value);
684 iterator release_range(size_type start_pos, size_type end_pos);
710 iterator release_range(
const iterator& pos_hint, size_type start_pos, size_type end_pos);
728 position_type position(size_type pos);
749 position_type position(
const iterator& pos_hint, size_type pos);
764 const_position_type position(size_type pos)
const;
782 const_position_type position(
const const_iterator& pos_hint, size_type pos)
const;
808 iterator transfer(size_type start_pos, size_type end_pos,
multi_type_vector& dest, size_type dest_pos);
837 iterator transfer(
const iterator& pos_hint, size_type start_pos, size_type end_pos,
multi_type_vector& dest, size_type dest_pos);
846 mtv::element_t get_type(size_type pos)
const;
859 bool is_empty(size_type pos)
const;
874 iterator set_empty(size_type start_pos, size_type end_pos);
905 iterator set_empty(
const iterator& pos_hint, size_type start_pos, size_type end_pos);
922 void erase(size_type start_pos, size_type end_pos);
942 iterator insert_empty(size_type pos, size_type length);
978 iterator insert_empty(
const iterator& pos_hint, size_type pos, size_type length);
991 size_type size()
const;
1010 size_type block_size()
const;
1026 void resize(size_type new_size);
1043 void swap(size_type start_pos, size_type end_pos,
multi_type_vector& other, size_type other_pos);
1048 void shrink_to_fit();
1062 template<
typename _T>
1063 static mtv::element_t get_element_type(
const _T& elem);
1065 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG 1066 void dump_blocks(std::ostream& os)
const;
1068 bool check_block_integrity()
const;
1079 void delete_element_block(block& blk);
1088 void delete_element_blocks(
typename blocks_type::iterator it,
typename blocks_type::iterator it_end);
1090 template<
typename _T>
1091 iterator set_impl(size_type pos, size_type start_row, size_type block_index,
const _T& value);
1093 template<
typename _T>
1094 iterator release_impl(size_type pos, size_type start_pos, size_type block_index, _T& value);
1115 bool get_block_position(size_type row, size_type& start_pos, size_type& block_index)
const;
1121 void get_block_position(
const const_iterator& pos_hint, size_type pos, size_type& start_pos, size_type& block_index)
const;
1123 template<
typename _T>
1124 void create_new_block_with_new_cell(element_block_type*& data,
const _T& cell);
1126 template<
typename _T>
1127 iterator set_cell_to_middle_of_block(
1128 size_type start_row, size_type block_index, size_type pos_in_block,
const _T& cell);
1130 template<
typename _T>
1131 void append_cell_to_block(size_type block_index,
const _T& cell);
1133 template<
typename _T>
1134 iterator set_cell_to_empty_block(
1135 size_type start_row, size_type block_index, size_type pos_in_block,
const _T& cell);
1137 template<
typename _T>
1138 iterator set_cell_to_block_of_size_one(
1139 size_type start_row, size_type block_index,
const _T& cell);
1141 template<
typename _T>
1142 void set_cell_to_top_of_data_block(
1143 size_type block_index,
const _T& cell);
1145 template<
typename _T>
1146 void set_cell_to_bottom_of_data_block(
1147 size_type block_index,
const _T& cell);
1149 iterator transfer_impl(
1150 size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1156 iterator transfer_single_block(
1157 size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1164 iterator transfer_multi_blocks(
1165 size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1166 size_type start_pos_in_block2, size_type block_index2,
1169 iterator set_empty_impl(
1170 size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1174 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1175 size_type start_pos_in_block1, size_type block_index1, size_type start_pos_in_block2, size_type block_index2,
1176 size_type start_pos_in_dblock1, size_type dblock_index1, size_type start_pos_in_dblock2, size_type dblock_index2);
1178 void swap_single_block(
1179 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1180 size_type start_pos_in_block, size_type block_index, size_type start_pos_in_other_block, size_type other_block_index);
1182 void swap_single_to_multi_blocks(
1183 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1184 size_type start_pos_in_block, size_type block_index, size_type dst_start_pos_in_block1, size_type dst_block_index1,
1185 size_type dst_start_pos_in_block2, size_type dst_block_index2);
1187 void swap_multi_to_multi_blocks(
1188 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1189 size_type start_pos_in_block1, size_type block_index1, size_type start_pos_in_block2, size_type block_index2,
1190 size_type start_pos_in_dblock1, size_type dblock_index1, size_type start_pos_in_dblock2, size_type dblock_index2);
1192 void insert_blocks_at(size_type insert_pos, blocks_type& new_blocks);
1194 void prepare_blocks_to_transfer(blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1196 iterator set_whole_block_empty(size_type block_index, size_type start_pos_in_block,
bool overwrite);
1198 iterator set_empty_in_single_block(
1199 size_type start_pos, size_type end_pos, size_type block_index, size_type start_pos_in_block,
1202 iterator set_empty_in_multi_blocks(
1203 size_type start_pos, size_type end_pos,
1204 size_type block_index1, size_type start_pos_in_block1,
1205 size_type block_index2, size_type start_pos_in_block2,
bool overwrite);
1207 void erase_impl(size_type start_pos, size_type end_pos);
1208 void erase_in_single_block(
1209 size_type start_pos, size_type end_pos, size_type block_pos, size_type start_pos_in_block);
1211 iterator insert_empty_impl(size_type row, size_type start_pos, size_type block_index, size_type length);
1213 template<
typename _T>
1214 bool set_cells_precheck(
1215 size_type row,
const _T& it_begin,
const _T& it_end, size_type& end_pos);
1217 template<
typename _T>
1218 iterator set_cells_impl(
1219 size_type row, size_type end_row, size_type start_row1, size_type block_index1,
const _T& it_begin,
const _T& it_end);
1221 template<
typename _T>
1222 iterator insert_cells_impl(size_type row, size_type start_row, size_type block_index,
const _T& it_begin,
const _T& it_end);
1224 template<
typename _T>
1225 iterator set_cells_to_single_block(
1226 size_type start_pos, size_type end_pos, size_type block_index,
1227 size_type start_pos_in_block,
const _T& it_begin,
const _T& it_end);
1229 template<
typename _T>
1230 iterator set_cells_to_multi_blocks(
1231 size_type start_pos, size_type end_pos,
1232 size_type block_index1, size_type start_pos_in_block1,
1233 size_type block_index2, size_type start_pos_in_block2,
1234 const _T& it_begin,
const _T& it_end);
1236 template<
typename _T>
1237 iterator set_cells_to_multi_blocks_block1_non_equal(
1238 size_type start_pos, size_type end_pos,
1239 size_type block_index1, size_type start_pos_in_block1,
1240 size_type block_index2, size_type start_pos_in_block2,
1241 const _T& it_begin,
const _T& it_end);
1243 template<
typename _T>
1244 iterator set_cells_to_multi_blocks_block1_non_empty(
1245 size_type start_pos, size_type end_pos,
1246 size_type block_index1, size_type start_pos_in_block1,
1247 size_type block_index2, size_type start_pos_in_block2,
1248 const _T& it_begin,
const _T& it_end);
1258 size_type merge_with_adjacent_blocks(size_type block_index);
1267 bool merge_with_next_block(size_type block_index);
1269 template<
typename _T>
1270 bool append_to_prev_block(
1271 size_type block_index, element_category_type cat, size_type length,
1272 const _T& it_begin,
const _T& it_end);
1274 template<
typename _T>
1275 void insert_cells_to_middle(
1276 size_type row, size_type block_index, size_type start_pos,
1277 const _T& it_begin,
const _T& it_end);
1292 block& set_new_block_to_middle(
1293 size_type block_index, size_type offset, size_type new_block_size,
bool overwrite);
1295 block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1304 block* get_next_block_of_type(size_type block_index, element_category_type cat);
1323 element_block_type* exchange_elements(
1324 const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1326 void exchange_elements(
1327 const element_block_type& src_data, size_type src_offset,
1328 size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1329 size_type len, blocks_type& new_blocks);
1331 bool append_empty(size_type len);
1333 inline iterator get_iterator(size_type block_index, size_type start_row)
1335 typename blocks_type::iterator block_pos = m_blocks.begin();
1336 std::advance(block_pos, block_index);
1337 return iterator(block_pos, m_blocks.end(), start_row, block_index);
1340 inline const_iterator get_const_iterator(size_type block_index, size_type start_row)
const 1342 typename blocks_type::const_iterator block_pos = m_blocks.begin();
1343 std::advance(block_pos, block_index);
1344 return const_iterator(block_pos, m_blocks.end(), start_row, block_index);
1348 event_func m_hdl_event;
1349 blocks_type m_blocks;
1350 size_type m_cur_size;
1355 #include "multi_type_vector_def.inl" Definition: multi_type_vector_itr.hpp:44
_EventFunc event_func
Definition: multi_type_vector.hpp:121
Definition: multi_type_vector_types.hpp:87
itr_node value_type
Definition: multi_type_vector.hpp:215
Definition: multi_type_vector_itr.hpp:106
Definition: multi_type_vector_itr.hpp:308
Definition: multi_type_vector.hpp:57
Definition: multi_type_vector_itr.hpp:97
Definition: flat_segment_tree.hpp:46
Definition: multi_type_vector.hpp:95
Definition: multi_type_vector_itr.hpp:238