mdds
multi_type_vector.hpp
1 /*************************************************************************
2  *
3  * Copyright (c) 2011-2016 Kohei Yoshida
4  *
5  * Permission is hereby granted, free of charge, to any person
6  * obtaining a copy of this software and associated documentation
7  * files (the "Software"), to deal in the Software without
8  * restriction, including without limitation the rights to use,
9  * copy, modify, merge, publish, distribute, sublicense, and/or sell
10  * copies of the Software, and to permit persons to whom the
11  * Software is furnished to do so, subject to the following
12  * conditions:
13  *
14  * The above copyright notice and this permission notice shall be
15  * included in all copies or substantial portions of the Software.
16  *
17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
18  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
19  * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
20  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
21  * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
22  * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24  * OTHER DEALINGS IN THE SOFTWARE.
25  *
26  ************************************************************************/
27 
28 #ifndef MDDS_MULTI_TYPE_VECTOR_HPP
29 #define MDDS_MULTI_TYPE_VECTOR_HPP
30 
31 #include "default_deleter.hpp"
32 #include "global.hpp"
33 #include "multi_type_vector_types.hpp"
34 #include "multi_type_vector_itr.hpp"
35 
36 #include <vector>
37 #include <algorithm>
38 #include <cassert>
39 #include <sstream>
40 
41 #if defined(MDDS_UNIT_TEST) || defined (MDDS_MULTI_TYPE_VECTOR_DEBUG)
42 #include <iostream>
43 using std::cout;
44 using std::cerr;
45 using std::endl;
46 #endif
47 
48 namespace mdds {
49 
50 namespace detail {
51 
59 {
60  void element_block_acquired(const mdds::mtv::base_element_block* /*block*/) {}
61 
62  void element_block_released(const mdds::mtv::base_element_block* /*block*/) {}
63 };
64 
65 template<typename T>
66 T mtv_advance_position(const T& pos, int steps);
67 
68 }
69 
95 template<typename _ElemBlockFunc, typename _EventFunc = detail::mtv_event_func>
97 {
98 public:
99  typedef size_t size_type;
100 
102  typedef typename mdds::mtv::element_t element_category_type;
103  typedef _ElemBlockFunc element_block_func;
104 
122  typedef _EventFunc event_func;
123 
124 private:
125 
126  struct block
127  {
128  size_type m_size;
129  element_block_type* mp_data;
130 
131  block();
132  block(size_type _size);
133  block(const block& other);
134  ~block();
135  };
136 
137  struct element_block_deleter : public std::unary_function<void, const element_block_type*>
138  {
139  void operator() (const element_block_type* p)
140  {
141  element_block_func::delete_block(p);
142  }
143  };
144 
145  typedef std::vector<block*> blocks_type;
146 
147  struct blocks_to_transfer
148  {
149  blocks_type blocks;
150  size_type insert_index;
151 
152  blocks_to_transfer();
153  };
154 
155  struct iterator_trait
156  {
157  typedef multi_type_vector parent;
158  typedef blocks_type blocks;
159  typedef typename blocks_type::iterator base_iterator;
160  };
161 
162  struct reverse_iterator_trait
163  {
164  typedef multi_type_vector parent;
165  typedef blocks_type blocks;
166  typedef typename blocks_type::reverse_iterator base_iterator;
167  };
168 
169  struct const_iterator_trait
170  {
171  typedef multi_type_vector parent;
172  typedef blocks_type blocks;
173  typedef typename blocks_type::const_iterator base_iterator;
174  };
175 
176  struct const_reverse_iterator_trait
177  {
178  typedef multi_type_vector parent;
179  typedef blocks_type blocks;
180  typedef typename blocks_type::const_reverse_iterator base_iterator;
181  };
182 
186 
187 public:
188 
191 
194 
210  typedef itr_node value_type;
211 
212  typedef std::pair<iterator, size_type> position_type;
213  typedef std::pair<const_iterator, size_type> const_position_type;
214 
223  static position_type next_position(const position_type& pos);
224 
234  static position_type advance_position(const position_type& pos, int steps);
235 
244  static const_position_type next_position(const const_position_type& pos);
245 
255  static const_position_type advance_position(const const_position_type& pos, int steps);
256 
265  static size_type logical_position(const const_position_type& pos);
266 
275  template<typename _Blk>
276  static typename _Blk::value_type get(const const_position_type& pos);
277 
278  iterator begin();
279  iterator end();
280 
281  const_iterator begin() const;
282  const_iterator end() const;
283 
284  reverse_iterator rbegin();
285  reverse_iterator rend();
286 
287  const_reverse_iterator rbegin() const;
288  const_reverse_iterator rend() const;
289 
290  event_func& event_handler();
291  const event_func& event_handler() const;
292 
297 
304  multi_type_vector(const event_func& hdl);
305 
312  multi_type_vector(event_func&& hdl);
313 
321  multi_type_vector(size_type init_size);
322 
332  template<typename _T>
333  multi_type_vector(size_type init_size, const _T& value);
334 
348  template<typename _T>
349  multi_type_vector(size_type init_size, const _T& it_begin, const _T& it_end);
350 
356  multi_type_vector(const multi_type_vector& other);
357 
362 
379  template<typename _T>
380  iterator set(size_type pos, const _T& value);
381 
414  template<typename _T>
415  iterator set(const iterator& pos_hint, size_type pos, const _T& value);
416 
438  template<typename _T>
439  iterator set(size_type pos, const _T& it_begin, const _T& it_end);
440 
478  template<typename _T>
479  iterator set(const iterator& pos_hint, size_type pos, const _T& it_begin, const _T& it_end);
480 
490  template<typename _T>
491  iterator push_back(const _T& value);
492 
500  iterator push_back_empty();
501 
523  template<typename _T>
524  iterator insert(size_type pos, const _T& it_begin, const _T& it_end);
525 
563  template<typename _T>
564  iterator insert(const iterator& pos_hint, size_type pos, const _T& it_begin, const _T& it_end);
565 
576  template<typename _T>
577  void get(size_type pos, _T& value) const;
578 
590  template<typename _T>
591  _T get(size_type pos) const;
592 
607  template<typename _T>
608  _T release(size_type pos);
609 
626  template<typename _T>
627  iterator release(size_type pos, _T& value);
628 
645  template<typename _T>
646  iterator release(const iterator& pos_hint, size_type pos, _T& value);
647 
656  void release();
657 
673  iterator release_range(size_type start_pos, size_type end_pos);
674 
699  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
700 
714  position_type position(size_type pos);
715 
732  position_type position(const iterator& pos_hint, size_type pos);
733 
747  const_position_type position(size_type pos) const;
748 
765  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
766 
791  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
792 
820  iterator transfer(const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
821 
829  mtv::element_t get_type(size_type pos) const;
830 
842  bool is_empty(size_type pos) const;
843 
857  iterator set_empty(size_type start_pos, size_type end_pos);
858 
888  iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
889 
905  void erase(size_type start_pos, size_type end_pos);
906 
925  iterator insert_empty(size_type pos, size_type length);
926 
961  iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
962 
967  void clear();
968 
974  size_type size() const;
975 
993  size_type block_size() const;
994 
1000  bool empty() const;
1001 
1009  void resize(size_type new_size);
1010 
1016  void swap(multi_type_vector& other);
1017 
1026  void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1027 
1031  void shrink_to_fit();
1032 
1033  bool operator== (const multi_type_vector& other) const;
1034  bool operator!= (const multi_type_vector& other) const;
1035 
1036  multi_type_vector& operator= (const multi_type_vector& other);
1037 
1045  template<typename _T>
1046  static mtv::element_t get_element_type(const _T& elem);
1047 
1048 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1049  void dump_blocks(std::ostream& os) const;
1050 
1051  bool check_block_integrity() const;
1052 #endif
1053 
1054 private:
1055 
1062  void delete_element_block(block* p);
1063 
1069  void delete_block(block* p);
1070 
1077  void delete_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1078 
1079  template<typename _T>
1080  iterator set_impl(size_type pos, size_type start_row, size_type block_index, const _T& value);
1081 
1082  template<typename _T>
1083  iterator release_impl(size_type pos, size_type start_pos, size_type block_index, _T& value);
1084 
1104  bool get_block_position(size_type row, size_type& start_pos, size_type& block_index) const;
1105 
1110  void get_block_position(const const_iterator& pos_hint, size_type pos, size_type& start_pos, size_type& block_index) const;
1111 
1112  template<typename _T>
1113  void create_new_block_with_new_cell(element_block_type*& data, const _T& cell);
1114 
1115  template<typename _T>
1116  iterator set_cell_to_middle_of_block(
1117  size_type start_row, size_type block_index, size_type pos_in_block, const _T& cell);
1118 
1119  template<typename _T>
1120  void append_cell_to_block(size_type block_index, const _T& cell);
1121 
1122  template<typename _T>
1123  iterator set_cell_to_empty_block(
1124  size_type start_row, size_type block_index, size_type pos_in_block, const _T& cell);
1125 
1126  template<typename _T>
1127  iterator set_cell_to_block_of_size_one(
1128  size_type start_row, size_type block_index, const _T& cell);
1129 
1130  template<typename _T>
1131  void set_cell_to_top_of_data_block(
1132  size_type block_index, const _T& cell);
1133 
1134  template<typename _T>
1135  void set_cell_to_bottom_of_data_block(
1136  size_type block_index, const _T& cell);
1137 
1138  iterator transfer_impl(
1139  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1140  multi_type_vector& dest, size_type dest_pos);
1141 
1145  iterator transfer_single_block(
1146  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1147  multi_type_vector& dest, size_type dest_pos);
1148 
1153  iterator transfer_multi_blocks(
1154  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1155  size_type start_pos_in_block2, size_type block_index2,
1156  multi_type_vector& dest, size_type dest_pos);
1157 
1158  iterator set_empty_impl(
1159  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1160  bool overwrite);
1161 
1162  void swap_impl(
1163  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1164  size_type start_pos_in_block1, size_type block_index1, size_type start_pos_in_block2, size_type block_index2,
1165  size_type start_pos_in_dblock1, size_type dblock_index1, size_type start_pos_in_dblock2, size_type dblock_index2);
1166 
1167  void swap_single_block(
1168  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1169  size_type start_pos_in_block, size_type block_index, size_type start_pos_in_other_block, size_type other_block_index);
1170 
1171  void swap_single_to_multi_blocks(
1172  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1173  size_type start_pos_in_block, size_type block_index, size_type dst_start_pos_in_block1, size_type dst_block_index1,
1174  size_type dst_start_pos_in_block2, size_type dst_block_index2);
1175 
1176  void swap_multi_to_multi_blocks(
1177  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1178  size_type start_pos_in_block1, size_type block_index1, size_type start_pos_in_block2, size_type block_index2,
1179  size_type start_pos_in_dblock1, size_type dblock_index1, size_type start_pos_in_dblock2, size_type dblock_index2);
1180 
1181  void insert_blocks_at(size_type insert_pos, blocks_type& new_blocks);
1182 
1183  void prepare_blocks_to_transfer(blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1184 
1185  iterator set_whole_block_empty(size_type block_index, size_type start_pos_in_block, bool overwrite);
1186 
1187  iterator set_empty_in_single_block(
1188  size_type start_pos, size_type end_pos, size_type block_index, size_type start_pos_in_block,
1189  bool overwrite);
1190 
1191  iterator set_empty_in_multi_blocks(
1192  size_type start_pos, size_type end_pos,
1193  size_type block_index1, size_type start_pos_in_block1,
1194  size_type block_index2, size_type start_pos_in_block2, bool overwrite);
1195 
1196  void erase_impl(size_type start_pos, size_type end_pos);
1197  void erase_in_single_block(
1198  size_type start_pos, size_type end_pos, size_type block_pos, size_type start_pos_in_block);
1199 
1200  iterator insert_empty_impl(size_type row, size_type start_pos, size_type block_index, size_type length);
1201 
1202  template<typename _T>
1203  bool set_cells_precheck(
1204  size_type row, const _T& it_begin, const _T& it_end, size_type& end_pos);
1205 
1206  template<typename _T>
1207  iterator set_cells_impl(
1208  size_type row, size_type end_row, size_type start_row1, size_type block_index1, const _T& it_begin, const _T& it_end);
1209 
1210  template<typename _T>
1211  iterator insert_cells_impl(size_type row, size_type start_row, size_type block_index, const _T& it_begin, const _T& it_end);
1212 
1213  template<typename _T>
1214  iterator set_cells_to_single_block(
1215  size_type start_pos, size_type end_pos, size_type block_index,
1216  size_type start_pos_in_block, const _T& it_begin, const _T& it_end);
1217 
1218  template<typename _T>
1219  iterator set_cells_to_multi_blocks(
1220  size_type start_pos, size_type end_pos,
1221  size_type block_index1, size_type start_pos_in_block1,
1222  size_type block_index2, size_type start_pos_in_block2,
1223  const _T& it_begin, const _T& it_end);
1224 
1225  template<typename _T>
1226  iterator set_cells_to_multi_blocks_block1_non_equal(
1227  size_type start_pos, size_type end_pos,
1228  size_type block_index1, size_type start_pos_in_block1,
1229  size_type block_index2, size_type start_pos_in_block2,
1230  const _T& it_begin, const _T& it_end);
1231 
1232  template<typename _T>
1233  iterator set_cells_to_multi_blocks_block1_non_empty(
1234  size_type start_pos, size_type end_pos,
1235  size_type block_index1, size_type start_pos_in_block1,
1236  size_type block_index2, size_type start_pos_in_block2,
1237  const _T& it_begin, const _T& it_end);
1238 
1247  size_type merge_with_adjacent_blocks(size_type block_index);
1248 
1256  bool merge_with_next_block(size_type block_index);
1257 
1258  template<typename _T>
1259  bool append_to_prev_block(
1260  size_type block_index, element_category_type cat, size_type length,
1261  const _T& it_begin, const _T& it_end);
1262 
1263  template<typename _T>
1264  void insert_cells_to_middle(
1265  size_type row, size_type block_index, size_type start_pos,
1266  const _T& it_begin, const _T& it_end);
1267 
1281  block* set_new_block_to_middle(
1282  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1283 
1284  block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1285 
1293  block* get_next_block_of_type(size_type block_index, element_category_type cat);
1294 
1312  element_block_type* exchange_elements(
1313  const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1314 
1315  void exchange_elements(
1316  const element_block_type& src_data, size_type src_offset,
1317  size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1318  size_type len, blocks_type& new_blocks);
1319 
1320  bool append_empty(size_type len);
1321 
1322  inline iterator get_iterator(size_type block_index, size_type start_row)
1323  {
1324  typename blocks_type::iterator block_pos = m_blocks.begin();
1325  std::advance(block_pos, block_index);
1326  return iterator(block_pos, m_blocks.end(), start_row, block_index);
1327  }
1328 
1329  inline const_iterator get_const_iterator(size_type block_index, size_type start_row) const
1330  {
1331  typename blocks_type::const_iterator block_pos = m_blocks.begin();
1332  std::advance(block_pos, block_index);
1333  return const_iterator(block_pos, m_blocks.end(), start_row, block_index);
1334  }
1335 
1336 private:
1337  event_func m_hdl_event;
1338  blocks_type m_blocks;
1339  size_type m_cur_size;
1340 };
1341 
1342 }
1343 
1344 #include "multi_type_vector_def.inl"
1345 
1346 #endif
_EventFunc event_func
Definition: multi_type_vector.hpp:122
Definition: multi_type_vector_types.hpp:88
Definition: multi_type_vector_itr.hpp:109
itr_node value_type
Definition: multi_type_vector.hpp:210
Definition: multi_type_vector_itr.hpp:44
Definition: multi_type_vector.hpp:58
Definition: multi_type_vector_itr.hpp:100
Definition: multi_type_vector_itr.hpp:241
Definition: multi_type_vector_itr.hpp:314
Definition: default_deleter.hpp:33
Definition: multi_type_vector.hpp:96