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 "global.hpp"
32 #include "multi_type_vector_types.hpp"
33 #include "multi_type_vector_itr.hpp"
34 
35 #include <vector>
36 #include <algorithm>
37 #include <cassert>
38 #include <sstream>
39 
40 #if defined(MDDS_UNIT_TEST) || defined (MDDS_MULTI_TYPE_VECTOR_DEBUG)
41 #include <iostream>
42 using std::cout;
43 using std::cerr;
44 using std::endl;
45 #endif
46 
47 namespace mdds {
48 
49 namespace detail {
50 
58 {
59  void element_block_acquired(const mdds::mtv::base_element_block* /*block*/) {}
60 
61  void element_block_released(const mdds::mtv::base_element_block* /*block*/) {}
62 };
63 
64 template<typename T>
65 T mtv_advance_position(const T& pos, int steps);
66 
67 }
68 
94 template<typename _ElemBlockFunc, typename _EventFunc = detail::mtv_event_func>
96 {
97 public:
98  typedef size_t size_type;
99 
101  typedef typename mdds::mtv::element_t element_category_type;
102  typedef _ElemBlockFunc element_block_func;
103 
121  typedef _EventFunc event_func;
122 
123 private:
124 
125  struct block
126  {
127  size_type m_size;
128  element_block_type* mp_data;
129 
130  block();
131  block(size_type _size);
132  block(size_type _size, element_block_type* _data);
133  block(const block& other);
134  block(block&& other);
135  ~block();
136  void swap(block& other);
137  void clone_to(block& other) const;
138 
139  block& operator=(block);
140  };
141 
142  struct element_block_deleter : public std::unary_function<void, const element_block_type*>
143  {
144  void operator() (const element_block_type* p)
145  {
146  element_block_func::delete_block(p);
147  }
148  };
149 
150  typedef std::vector<block> blocks_type;
151 
152  struct blocks_to_transfer
153  {
154  blocks_type blocks;
155  size_type insert_index;
156 
157  blocks_to_transfer();
158  };
159 
160  struct iterator_trait
161  {
162  typedef multi_type_vector parent;
163  typedef blocks_type blocks;
164  typedef typename blocks_type::iterator base_iterator;
165  };
166 
167  struct reverse_iterator_trait
168  {
169  typedef multi_type_vector parent;
170  typedef blocks_type blocks;
171  typedef typename blocks_type::reverse_iterator base_iterator;
172  };
173 
174  struct const_iterator_trait
175  {
176  typedef multi_type_vector parent;
177  typedef blocks_type blocks;
178  typedef typename blocks_type::const_iterator base_iterator;
179  };
180 
181  struct const_reverse_iterator_trait
182  {
183  typedef multi_type_vector parent;
184  typedef blocks_type blocks;
185  typedef typename blocks_type::const_reverse_iterator base_iterator;
186  };
187 
191 
192 public:
193 
196 
199 
215  typedef itr_node value_type;
216 
217  typedef std::pair<iterator, size_type> position_type;
218  typedef std::pair<const_iterator, size_type> const_position_type;
219 
228  static position_type next_position(const position_type& pos);
229 
239  static position_type advance_position(const position_type& pos, int steps);
240 
249  static const_position_type next_position(const const_position_type& pos);
250 
260  static const_position_type advance_position(const const_position_type& pos, int steps);
261 
270  static size_type logical_position(const const_position_type& pos);
271 
280  template<typename _Blk>
281  static typename _Blk::value_type get(const const_position_type& pos);
282 
283  iterator begin();
284  iterator end();
285 
286  const_iterator begin() const;
287  const_iterator end() const;
288 
289  reverse_iterator rbegin();
290  reverse_iterator rend();
291 
292  const_reverse_iterator rbegin() const;
293  const_reverse_iterator rend() const;
294 
295  event_func& event_handler();
296  const event_func& event_handler() const;
297 
302 
309  multi_type_vector(const event_func& hdl);
310 
317  multi_type_vector(event_func&& hdl);
318 
326  multi_type_vector(size_type init_size);
327 
337  template<typename _T>
338  multi_type_vector(size_type init_size, const _T& value);
339 
353  template<typename _T>
354  multi_type_vector(size_type init_size, const _T& it_begin, const _T& it_end);
355 
361  multi_type_vector(const multi_type_vector& other);
362 
367 
384  template<typename _T>
385  iterator set(size_type pos, const _T& value);
386 
419  template<typename _T>
420  iterator set(const iterator& pos_hint, size_type pos, const _T& value);
421 
443  template<typename _T>
444  iterator set(size_type pos, const _T& it_begin, const _T& it_end);
445 
483  template<typename _T>
484  iterator set(const iterator& pos_hint, size_type pos, const _T& it_begin, const _T& it_end);
485 
495  template<typename _T>
496  iterator push_back(const _T& value);
497 
505  iterator push_back_empty();
506 
528  template<typename _T>
529  iterator insert(size_type pos, const _T& it_begin, const _T& it_end);
530 
568  template<typename _T>
569  iterator insert(const iterator& pos_hint, size_type pos, const _T& it_begin, const _T& it_end);
570 
581  template<typename _T>
582  void get(size_type pos, _T& value) const;
583 
595  template<typename _T>
596  _T get(size_type pos) const;
597 
612  template<typename _T>
613  _T release(size_type pos);
614 
631  template<typename _T>
632  iterator release(size_type pos, _T& value);
633 
650  template<typename _T>
651  iterator release(const iterator& pos_hint, size_type pos, _T& value);
652 
661  void release();
662 
678  iterator release_range(size_type start_pos, size_type end_pos);
679 
704  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
705 
719  position_type position(size_type pos);
720 
737  position_type position(const iterator& pos_hint, size_type pos);
738 
752  const_position_type position(size_type pos) const;
753 
770  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
771 
796  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
797 
825  iterator transfer(const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
826 
834  mtv::element_t get_type(size_type pos) const;
835 
847  bool is_empty(size_type pos) const;
848 
862  iterator set_empty(size_type start_pos, size_type end_pos);
863 
893  iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
894 
910  void erase(size_type start_pos, size_type end_pos);
911 
930  iterator insert_empty(size_type pos, size_type length);
931 
966  iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
967 
972  void clear();
973 
979  size_type size() const;
980 
998  size_type block_size() const;
999 
1005  bool empty() const;
1006 
1014  void resize(size_type new_size);
1015 
1021  void swap(multi_type_vector& other);
1022 
1031  void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1032 
1036  void shrink_to_fit();
1037 
1038  bool operator== (const multi_type_vector& other) const;
1039  bool operator!= (const multi_type_vector& other) const;
1040 
1041  multi_type_vector& operator= (const multi_type_vector& other);
1042 
1050  template<typename _T>
1051  static mtv::element_t get_element_type(const _T& elem);
1052 
1053 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1054  void dump_blocks(std::ostream& os) const;
1055 
1056  bool check_block_integrity() const;
1057 #endif
1058 
1059 private:
1060 
1067  void delete_element_block(block& blk);
1068 
1076  void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1077 
1078  template<typename _T>
1079  iterator set_impl(size_type pos, size_type start_row, size_type block_index, const _T& value);
1080 
1081  template<typename _T>
1082  iterator release_impl(size_type pos, size_type start_pos, size_type block_index, _T& value);
1083 
1103  bool get_block_position(size_type row, size_type& start_pos, size_type& block_index) const;
1104 
1109  void get_block_position(const const_iterator& pos_hint, size_type pos, size_type& start_pos, size_type& block_index) const;
1110 
1111  template<typename _T>
1112  void create_new_block_with_new_cell(element_block_type*& data, const _T& cell);
1113 
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);
1117 
1118  template<typename _T>
1119  void append_cell_to_block(size_type block_index, const _T& cell);
1120 
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);
1124 
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);
1128 
1129  template<typename _T>
1130  void set_cell_to_top_of_data_block(
1131  size_type block_index, const _T& cell);
1132 
1133  template<typename _T>
1134  void set_cell_to_bottom_of_data_block(
1135  size_type block_index, const _T& cell);
1136 
1137  iterator transfer_impl(
1138  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1139  multi_type_vector& dest, size_type dest_pos);
1140 
1144  iterator transfer_single_block(
1145  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1146  multi_type_vector& dest, size_type dest_pos);
1147 
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,
1155  multi_type_vector& dest, size_type dest_pos);
1156 
1157  iterator set_empty_impl(
1158  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1159  bool overwrite);
1160 
1161  void swap_impl(
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);
1165 
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);
1169 
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);
1174 
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);
1179 
1180  void insert_blocks_at(size_type insert_pos, blocks_type& new_blocks);
1181 
1182  void prepare_blocks_to_transfer(blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1183 
1184  iterator set_whole_block_empty(size_type block_index, size_type start_pos_in_block, bool overwrite);
1185 
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,
1188  bool overwrite);
1189 
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);
1194 
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);
1198 
1199  iterator insert_empty_impl(size_type row, size_type start_pos, size_type block_index, size_type length);
1200 
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);
1204 
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);
1208 
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);
1211 
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);
1216 
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);
1223 
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);
1230 
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);
1237 
1246  size_type merge_with_adjacent_blocks(size_type block_index);
1247 
1255  bool merge_with_next_block(size_type block_index);
1256 
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);
1261 
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);
1266 
1280  block& set_new_block_to_middle(
1281  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1282 
1283  block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1284 
1292  block* get_next_block_of_type(size_type block_index, element_category_type cat);
1293 
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);
1313 
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);
1318 
1319  bool append_empty(size_type len);
1320 
1321  inline iterator get_iterator(size_type block_index, size_type start_row)
1322  {
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);
1326  }
1327 
1328  inline const_iterator get_const_iterator(size_type block_index, size_type start_row) const
1329  {
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);
1333  }
1334 
1335 private:
1336  event_func m_hdl_event;
1337  blocks_type m_blocks;
1338  size_type m_cur_size;
1339 };
1340 
1341 }
1342 
1343 #include "multi_type_vector_def.inl"
1344 
1345 #endif
_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