mdds
multi_type_vector.hpp
1 /*************************************************************************
2  *
3  * Copyright (c) 2011-2018 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 INCLUDED_MDDS_MULTI_TYPE_VECTOR_HPP
29 #define INCLUDED_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 { namespace mtv {
50 
57 struct event_func
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 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
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  const_iterator cbegin() const;
290  const_iterator cend() const;
291 
292  reverse_iterator rbegin();
293  reverse_iterator rend();
294 
295  const_reverse_iterator rbegin() const;
296  const_reverse_iterator rend() const;
297 
298  const_reverse_iterator crbegin() const;
299  const_reverse_iterator crend() const;
300 
301  event_func& event_handler();
302  const event_func& event_handler() const;
303 
308 
315  multi_type_vector(const event_func& hdl);
316 
323  multi_type_vector(event_func&& hdl);
324 
332  multi_type_vector(size_type init_size);
333 
343  template<typename _T>
344  multi_type_vector(size_type init_size, const _T& value);
345 
359  template<typename _T>
360  multi_type_vector(size_type init_size, const _T& it_begin, const _T& it_end);
361 
367  multi_type_vector(const multi_type_vector& other);
368 
373 
390  template<typename _T>
391  iterator set(size_type pos, const _T& value);
392 
425  template<typename _T>
426  iterator set(const iterator& pos_hint, size_type pos, const _T& value);
427 
449  template<typename _T>
450  iterator set(size_type pos, const _T& it_begin, const _T& it_end);
451 
489  template<typename _T>
490  iterator set(const iterator& pos_hint, size_type pos, const _T& it_begin, const _T& it_end);
491 
501  template<typename _T>
502  iterator push_back(const _T& value);
503 
511  iterator push_back_empty();
512 
534  template<typename _T>
535  iterator insert(size_type pos, const _T& it_begin, const _T& it_end);
536 
574  template<typename _T>
575  iterator insert(const iterator& pos_hint, size_type pos, const _T& it_begin, const _T& it_end);
576 
587  template<typename _T>
588  void get(size_type pos, _T& value) const;
589 
601  template<typename _T>
602  _T get(size_type pos) const;
603 
618  template<typename _T>
619  _T release(size_type pos);
620 
637  template<typename _T>
638  iterator release(size_type pos, _T& value);
639 
656  template<typename _T>
657  iterator release(const iterator& pos_hint, size_type pos, _T& value);
658 
667  void release();
668 
684  iterator release_range(size_type start_pos, size_type end_pos);
685 
710  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
711 
728  position_type position(size_type pos);
729 
749  position_type position(const iterator& pos_hint, size_type pos);
750 
764  const_position_type position(size_type pos) const;
765 
782  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
783 
808  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
809 
837  iterator transfer(const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
838 
846  mtv::element_t get_type(size_type pos) const;
847 
859  bool is_empty(size_type pos) const;
860 
874  iterator set_empty(size_type start_pos, size_type end_pos);
875 
905  iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
906 
922  void erase(size_type start_pos, size_type end_pos);
923 
942  iterator insert_empty(size_type pos, size_type length);
943 
978  iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
979 
984  void clear();
985 
991  size_type size() const;
992 
1010  size_type block_size() const;
1011 
1017  bool empty() const;
1018 
1026  void resize(size_type new_size);
1027 
1033  void swap(multi_type_vector& other);
1034 
1043  void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1044 
1048  void shrink_to_fit();
1049 
1050  bool operator== (const multi_type_vector& other) const;
1051  bool operator!= (const multi_type_vector& other) const;
1052 
1053  multi_type_vector& operator= (const multi_type_vector& other);
1054 
1062  template<typename _T>
1063  static mtv::element_t get_element_type(const _T& elem);
1064 
1065 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1066  void dump_blocks(std::ostream& os) const;
1067 
1068  bool check_block_integrity() const;
1069 #endif
1070 
1071 private:
1072 
1079  void delete_element_block(block& blk);
1080 
1088  void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1089 
1090  template<typename _T>
1091  iterator set_impl(size_type pos, size_type start_row, size_type block_index, const _T& value);
1092 
1093  template<typename _T>
1094  iterator release_impl(size_type pos, size_type start_pos, size_type block_index, _T& value);
1095 
1115  bool get_block_position(size_type row, size_type& start_pos, size_type& block_index) const;
1116 
1121  void get_block_position(const const_iterator& pos_hint, size_type pos, size_type& start_pos, size_type& block_index) const;
1122 
1123  template<typename _T>
1124  void create_new_block_with_new_cell(element_block_type*& data, const _T& cell);
1125 
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);
1129 
1130  template<typename _T>
1131  void append_cell_to_block(size_type block_index, const _T& cell);
1132 
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);
1136 
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);
1140 
1141  template<typename _T>
1142  void set_cell_to_top_of_data_block(
1143  size_type block_index, const _T& cell);
1144 
1145  template<typename _T>
1146  void set_cell_to_bottom_of_data_block(
1147  size_type block_index, const _T& cell);
1148 
1149  iterator transfer_impl(
1150  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1151  multi_type_vector& dest, size_type dest_pos);
1152 
1156  iterator transfer_single_block(
1157  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1158  multi_type_vector& dest, size_type dest_pos);
1159 
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,
1167  multi_type_vector& dest, size_type dest_pos);
1168 
1169  iterator set_empty_impl(
1170  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1171  bool overwrite);
1172 
1173  void swap_impl(
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);
1177 
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);
1181 
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);
1186 
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);
1191 
1192  void insert_blocks_at(size_type insert_pos, blocks_type& new_blocks);
1193 
1194  void prepare_blocks_to_transfer(blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1195 
1196  iterator set_whole_block_empty(size_type block_index, size_type start_pos_in_block, bool overwrite);
1197 
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,
1200  bool overwrite);
1201 
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);
1206 
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);
1210 
1211  iterator insert_empty_impl(size_type row, size_type start_pos, size_type block_index, size_type length);
1212 
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);
1216 
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);
1220 
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);
1223 
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);
1228 
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);
1235 
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);
1242 
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);
1249 
1258  size_type merge_with_adjacent_blocks(size_type block_index);
1259 
1267  bool merge_with_next_block(size_type block_index);
1268 
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);
1273 
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);
1278 
1292  block& set_new_block_to_middle(
1293  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1294 
1295  block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1296 
1304  block* get_next_block_of_type(size_type block_index, element_category_type cat);
1305 
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);
1325 
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);
1330 
1331  bool append_empty(size_type len);
1332 
1333  inline iterator get_iterator(size_type block_index, size_type start_row)
1334  {
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);
1338  }
1339 
1340  inline const_iterator get_const_iterator(size_type block_index, size_type start_row) const
1341  {
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);
1345  }
1346 
1347 private:
1348  event_func m_hdl_event;
1349  blocks_type m_blocks;
1350  size_type m_cur_size;
1351 };
1352 
1353 }
1354 
1355 #include "multi_type_vector_def.inl"
1356 
1357 #endif
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