28 #ifndef MDDS_MULTI_TYPE_VECTOR_HPP 29 #define 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) 65 T mtv_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 :
public std::unary_function<void, const element_block_type*>
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 reverse_iterator rbegin();
290 reverse_iterator rend();
292 const_reverse_iterator rbegin()
const;
293 const_reverse_iterator rend()
const;
295 event_func& event_handler();
296 const event_func& event_handler()
const;
337 template<
typename _T>
353 template<
typename _T>
384 template<
typename _T>
385 iterator
set(size_type pos,
const _T& value);
419 template<
typename _T>
420 iterator
set(
const iterator& pos_hint, size_type pos,
const _T& value);
443 template<
typename _T>
444 iterator
set(size_type pos,
const _T& it_begin,
const _T& it_end);
483 template<
typename _T>
484 iterator
set(
const iterator& pos_hint, size_type pos,
const _T& it_begin,
const _T& it_end);
495 template<
typename _T>
496 iterator push_back(
const _T& value);
505 iterator push_back_empty();
528 template<
typename _T>
529 iterator insert(size_type pos,
const _T& it_begin,
const _T& it_end);
568 template<
typename _T>
569 iterator insert(
const iterator& pos_hint, size_type pos,
const _T& it_begin,
const _T& it_end);
581 template<
typename _T>
582 void get(size_type pos, _T& value)
const;
595 template<
typename _T>
596 _T
get(size_type pos)
const;
612 template<
typename _T>
613 _T release(size_type pos);
631 template<
typename _T>
632 iterator release(size_type pos, _T& value);
650 template<
typename _T>
651 iterator release(
const iterator& pos_hint, size_type pos, _T& value);
678 iterator release_range(size_type start_pos, size_type end_pos);
704 iterator release_range(
const iterator& pos_hint, size_type start_pos, size_type end_pos);
719 position_type position(size_type pos);
737 position_type position(
const iterator& pos_hint, size_type pos);
752 const_position_type position(size_type pos)
const;
770 const_position_type position(
const const_iterator& pos_hint, size_type pos)
const;
796 iterator transfer(size_type start_pos, size_type end_pos,
multi_type_vector& dest, size_type dest_pos);
825 iterator transfer(
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;
847 bool is_empty(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);
930 iterator insert_empty(size_type pos, size_type length);
966 iterator insert_empty(
const iterator& pos_hint, size_type pos, size_type length);
979 size_type size()
const;
998 size_type block_size()
const;
1014 void resize(size_type new_size);
1031 void swap(size_type start_pos, size_type end_pos,
multi_type_vector& other, size_type other_pos);
1036 void shrink_to_fit();
1050 template<
typename _T>
1051 static mtv::element_t get_element_type(
const _T& elem);
1053 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG 1054 void dump_blocks(std::ostream& os)
const;
1056 bool 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 start_row, size_type block_index,
const _T& value);
1081 template<
typename _T>
1082 iterator release_impl(size_type pos, size_type start_pos, size_type block_index, _T& value);
1103 bool get_block_position(size_type row, size_type& start_pos, size_type& block_index)
const;
1109 void get_block_position(
const const_iterator& pos_hint, size_type pos, size_type& start_pos, size_type& block_index)
const;
1111 template<
typename _T>
1112 void create_new_block_with_new_cell(element_block_type*& data,
const _T& cell);
1114 template<
typename _T>
1115 iterator set_cell_to_middle_of_block(
1116 size_type start_row, size_type block_index, size_type pos_in_block,
const _T& cell);
1118 template<
typename _T>
1119 void append_cell_to_block(size_type block_index,
const _T& cell);
1121 template<
typename _T>
1122 iterator set_cell_to_empty_block(
1123 size_type start_row, size_type block_index, size_type pos_in_block,
const _T& cell);
1125 template<
typename _T>
1126 iterator set_cell_to_block_of_size_one(
1127 size_type start_row, size_type block_index,
const _T& cell);
1129 template<
typename _T>
1130 void set_cell_to_top_of_data_block(
1131 size_type block_index,
const _T& cell);
1133 template<
typename _T>
1134 void set_cell_to_bottom_of_data_block(
1135 size_type block_index,
const _T& cell);
1137 iterator transfer_impl(
1138 size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1144 iterator transfer_single_block(
1145 size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1152 iterator transfer_multi_blocks(
1153 size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1154 size_type start_pos_in_block2, size_type block_index2,
1157 iterator set_empty_impl(
1158 size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1162 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1163 size_type start_pos_in_block1, size_type block_index1, size_type start_pos_in_block2, size_type block_index2,
1164 size_type start_pos_in_dblock1, size_type dblock_index1, size_type start_pos_in_dblock2, size_type dblock_index2);
1166 void swap_single_block(
1167 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1168 size_type start_pos_in_block, size_type block_index, size_type start_pos_in_other_block, size_type other_block_index);
1170 void swap_single_to_multi_blocks(
1171 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1172 size_type start_pos_in_block, size_type block_index, size_type dst_start_pos_in_block1, size_type dst_block_index1,
1173 size_type dst_start_pos_in_block2, size_type dst_block_index2);
1175 void swap_multi_to_multi_blocks(
1176 multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1177 size_type start_pos_in_block1, size_type block_index1, size_type start_pos_in_block2, size_type block_index2,
1178 size_type start_pos_in_dblock1, size_type dblock_index1, size_type start_pos_in_dblock2, size_type dblock_index2);
1180 void insert_blocks_at(size_type insert_pos, blocks_type& new_blocks);
1182 void prepare_blocks_to_transfer(blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1184 iterator set_whole_block_empty(size_type block_index, size_type start_pos_in_block,
bool overwrite);
1186 iterator set_empty_in_single_block(
1187 size_type start_pos, size_type end_pos, size_type block_index, size_type start_pos_in_block,
1190 iterator set_empty_in_multi_blocks(
1191 size_type start_pos, size_type end_pos,
1192 size_type block_index1, size_type start_pos_in_block1,
1193 size_type block_index2, size_type start_pos_in_block2,
bool overwrite);
1195 void erase_impl(size_type start_pos, size_type end_pos);
1196 void erase_in_single_block(
1197 size_type start_pos, size_type end_pos, size_type block_pos, size_type start_pos_in_block);
1199 iterator insert_empty_impl(size_type row, size_type start_pos, size_type block_index, size_type length);
1201 template<
typename _T>
1202 bool set_cells_precheck(
1203 size_type row,
const _T& it_begin,
const _T& it_end, size_type& end_pos);
1205 template<
typename _T>
1206 iterator set_cells_impl(
1207 size_type row, size_type end_row, size_type start_row1, size_type block_index1,
const _T& it_begin,
const _T& it_end);
1209 template<
typename _T>
1210 iterator insert_cells_impl(size_type row, size_type start_row, size_type block_index,
const _T& it_begin,
const _T& it_end);
1212 template<
typename _T>
1213 iterator set_cells_to_single_block(
1214 size_type start_pos, size_type end_pos, size_type block_index,
1215 size_type start_pos_in_block,
const _T& it_begin,
const _T& it_end);
1217 template<
typename _T>
1218 iterator set_cells_to_multi_blocks(
1219 size_type start_pos, size_type end_pos,
1220 size_type block_index1, size_type start_pos_in_block1,
1221 size_type block_index2, size_type start_pos_in_block2,
1222 const _T& it_begin,
const _T& it_end);
1224 template<
typename _T>
1225 iterator set_cells_to_multi_blocks_block1_non_equal(
1226 size_type start_pos, size_type end_pos,
1227 size_type block_index1, size_type start_pos_in_block1,
1228 size_type block_index2, size_type start_pos_in_block2,
1229 const _T& it_begin,
const _T& it_end);
1231 template<
typename _T>
1232 iterator set_cells_to_multi_blocks_block1_non_empty(
1233 size_type start_pos, size_type end_pos,
1234 size_type block_index1, size_type start_pos_in_block1,
1235 size_type block_index2, size_type start_pos_in_block2,
1236 const _T& it_begin,
const _T& it_end);
1246 size_type merge_with_adjacent_blocks(size_type block_index);
1255 bool merge_with_next_block(size_type block_index);
1257 template<
typename _T>
1258 bool append_to_prev_block(
1259 size_type block_index, element_category_type cat, size_type length,
1260 const _T& it_begin,
const _T& it_end);
1262 template<
typename _T>
1263 void insert_cells_to_middle(
1264 size_type row, size_type block_index, size_type start_pos,
1265 const _T& it_begin,
const _T& it_end);
1280 block& set_new_block_to_middle(
1281 size_type block_index, size_type offset, size_type new_block_size,
bool overwrite);
1283 block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1292 block* get_next_block_of_type(size_type block_index, element_category_type cat);
1311 element_block_type* exchange_elements(
1312 const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1314 void exchange_elements(
1315 const element_block_type& src_data, size_type src_offset,
1316 size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1317 size_type len, blocks_type& new_blocks);
1319 bool append_empty(size_type len);
1321 inline iterator get_iterator(size_type block_index, size_type start_row)
1323 typename blocks_type::iterator block_pos = m_blocks.begin();
1324 std::advance(block_pos, block_index);
1325 return iterator(block_pos, m_blocks.end(), start_row, block_index);
1328 inline const_iterator get_const_iterator(size_type block_index, size_type start_row)
const 1330 typename blocks_type::const_iterator block_pos = m_blocks.begin();
1331 std::advance(block_pos, block_index);
1332 return const_iterator(block_pos, m_blocks.end(), start_row, block_index);
1336 event_func m_hdl_event;
1337 blocks_type m_blocks;
1338 size_type m_cur_size;
1343 #include "multi_type_vector_def.inl" _EventFunc event_func
Definition: multi_type_vector.hpp:121
Definition: multi_type_vector_types.hpp:87
Definition: multi_type_vector_itr.hpp:109
itr_node value_type
Definition: multi_type_vector.hpp:215
Definition: multi_type_vector_itr.hpp:44
Definition: multi_type_vector.hpp:57
Definition: multi_type_vector_itr.hpp:100
Definition: multi_type_vector_itr.hpp:241
Definition: multi_type_vector_itr.hpp:314
Definition: flat_segment_tree.hpp:46
Definition: multi_type_vector.hpp:95