mdds
multi_type_vector.hpp
1 /*************************************************************************
2  *
3  * Copyright (c) 2011-2014 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 }
66 
92 template<typename _ElemBlockFunc, typename _EventFunc = detail::mtv_event_func>
94 {
95 public:
96  typedef size_t size_type;
97 
99  typedef typename mdds::mtv::element_t element_category_type;
100  typedef _ElemBlockFunc element_block_func;
101 
119  typedef _EventFunc event_func;
120 
121 private:
122 
123  struct block
124  {
125  size_type m_size;
126  element_block_type* mp_data;
127 
128  block();
129  block(size_type _size);
130  block(const block& other);
131  ~block();
132  };
133 
134  struct element_block_deleter : public std::unary_function<void, const element_block_type*>
135  {
136  void operator() (const element_block_type* p)
137  {
138  element_block_func::delete_block(p);
139  }
140  };
141 
142  typedef std::vector<block*> blocks_type;
143 
144  struct blocks_to_transfer
145  {
146  blocks_type blocks;
147  size_type insert_index;
148 
149  blocks_to_transfer();
150  };
151 
152  struct iterator_trait
153  {
154  typedef multi_type_vector parent;
155  typedef blocks_type blocks;
156  typedef typename blocks_type::iterator base_iterator;
157  };
158 
159  struct reverse_iterator_trait
160  {
161  typedef multi_type_vector parent;
162  typedef blocks_type blocks;
163  typedef typename blocks_type::reverse_iterator base_iterator;
164  };
165 
166  struct const_iterator_trait
167  {
168  typedef multi_type_vector parent;
169  typedef blocks_type blocks;
170  typedef typename blocks_type::const_iterator base_iterator;
171  };
172 
173  struct const_reverse_iterator_trait
174  {
175  typedef multi_type_vector parent;
176  typedef blocks_type blocks;
177  typedef typename blocks_type::const_reverse_iterator base_iterator;
178  };
179 
183 
184 public:
185 
188 
191 
207  typedef itr_node value_type;
208 
209  typedef std::pair<iterator, size_type> position_type;
210  typedef std::pair<const_iterator, size_type> const_position_type;
211 
220  static position_type next_position(const position_type& pos);
221 
231  static position_type advance_position(const position_type& pos, int steps);
232 
241  static const_position_type next_position(const const_position_type& pos);
242 
251  static size_type logical_position(const const_position_type& pos);
252 
261  template<typename _Blk>
262  static typename _Blk::value_type get(const const_position_type& pos);
263 
264  iterator begin();
265  iterator end();
266 
267  const_iterator begin() const;
268  const_iterator end() const;
269 
270  reverse_iterator rbegin();
271  reverse_iterator rend();
272 
273  const_reverse_iterator rbegin() const;
274  const_reverse_iterator rend() const;
275 
276  event_func& event_handler();
277  const event_func& event_handler() const;
278 
283 
290  multi_type_vector(const event_func& hdl);
291 
298  multi_type_vector(event_func&& hdl);
299 
307  multi_type_vector(size_type init_size);
308 
318  template<typename _T>
319  multi_type_vector(size_type init_size, const _T& value);
320 
334  template<typename _T>
335  multi_type_vector(size_type init_size, const _T& it_begin, const _T& it_end);
336 
342  multi_type_vector(const multi_type_vector& other);
343 
348 
365  template<typename _T>
366  iterator set(size_type pos, const _T& value);
367 
400  template<typename _T>
401  iterator set(const iterator& pos_hint, size_type pos, const _T& value);
402 
424  template<typename _T>
425  iterator set(size_type pos, const _T& it_begin, const _T& it_end);
426 
464  template<typename _T>
465  iterator set(const iterator& pos_hint, size_type pos, const _T& it_begin, const _T& it_end);
466 
476  template<typename _T>
477  iterator push_back(const _T& value);
478 
486  iterator push_back_empty();
487 
509  template<typename _T>
510  iterator insert(size_type pos, const _T& it_begin, const _T& it_end);
511 
549  template<typename _T>
550  iterator insert(const iterator& pos_hint, size_type pos, const _T& it_begin, const _T& it_end);
551 
562  template<typename _T>
563  void get(size_type pos, _T& value) const;
564 
576  template<typename _T>
577  _T get(size_type pos) const;
578 
592  template<typename _T>
593  _T release(size_type pos);
594 
610  template<typename _T>
611  iterator release(size_type pos, _T& value);
612 
628  template<typename _T>
629  iterator release(const iterator& pos_hint, size_type pos, _T& value);
630 
638  void release();
639 
655  iterator release_range(size_type start_pos, size_type end_pos);
656 
681  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
682 
695  position_type position(size_type pos);
696 
712  position_type position(const iterator& pos_hint, size_type pos);
713 
726  const_position_type position(size_type pos) const;
727 
743  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
744 
768  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
769 
796  iterator transfer(const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
797 
805  mtv::element_t get_type(size_type pos) const;
806 
817  bool is_empty(size_type pos) const;
818 
832  iterator set_empty(size_type start_pos, size_type end_pos);
833 
863  iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
864 
879  void erase(size_type start_pos, size_type end_pos);
880 
897  iterator insert_empty(size_type pos, size_type length);
898 
931  iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
932 
937  void clear();
938 
944  size_type size() const;
945 
960  size_type block_size() const;
961 
967  bool empty() const;
968 
976  void resize(size_type new_size);
977 
983  void swap(multi_type_vector& other);
984 
993  void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
994 
998  void shrink_to_fit();
999 
1000  bool operator== (const multi_type_vector& other) const;
1001  bool operator!= (const multi_type_vector& other) const;
1002 
1003  multi_type_vector& operator= (const multi_type_vector& other);
1004 
1012  template<typename _T>
1013  static mtv::element_t get_element_type(const _T& elem);
1014 
1015 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1016  void dump_blocks(std::ostream& os) const;
1017 
1018  bool check_block_integrity() const;
1019 #endif
1020 
1021 private:
1022 
1029  void delete_element_block(block* p);
1030 
1036  void delete_block(block* p);
1037 
1044  void delete_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1045 
1046  template<typename _T>
1047  iterator set_impl(size_type pos, size_type start_row, size_type block_index, const _T& value);
1048 
1049  template<typename _T>
1050  iterator release_impl(size_type pos, size_type start_pos, size_type block_index, _T& value);
1051 
1071  bool get_block_position(size_type row, size_type& start_pos, size_type& block_index) const;
1072 
1077  void get_block_position(const const_iterator& pos_hint, size_type pos, size_type& start_pos, size_type& block_index) const;
1078 
1079  template<typename _T>
1080  void create_new_block_with_new_cell(element_block_type*& data, const _T& cell);
1081 
1082  template<typename _T>
1083  iterator set_cell_to_middle_of_block(
1084  size_type start_row, size_type block_index, size_type pos_in_block, const _T& cell);
1085 
1086  template<typename _T>
1087  void append_cell_to_block(size_type block_index, const _T& cell);
1088 
1089  template<typename _T>
1090  iterator set_cell_to_empty_block(
1091  size_type start_row, size_type block_index, size_type pos_in_block, const _T& cell);
1092 
1093  template<typename _T>
1094  iterator set_cell_to_block_of_size_one(
1095  size_type start_row, size_type block_index, const _T& cell);
1096 
1097  template<typename _T>
1098  void set_cell_to_top_of_data_block(
1099  size_type block_index, const _T& cell);
1100 
1101  template<typename _T>
1102  void set_cell_to_bottom_of_data_block(
1103  size_type block_index, const _T& cell);
1104 
1105  iterator transfer_impl(
1106  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1107  multi_type_vector& dest, size_type dest_pos);
1108 
1112  iterator transfer_single_block(
1113  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1114  multi_type_vector& dest, size_type dest_pos);
1115 
1120  iterator transfer_multi_blocks(
1121  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1122  size_type start_pos_in_block2, size_type block_index2,
1123  multi_type_vector& dest, size_type dest_pos);
1124 
1125  iterator set_empty_impl(
1126  size_type start_pos, size_type end_pos, size_type start_pos_in_block1, size_type block_index1,
1127  bool overwrite);
1128 
1129  void swap_impl(
1130  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1131  size_type start_pos_in_block1, size_type block_index1, size_type start_pos_in_block2, size_type block_index2,
1132  size_type start_pos_in_dblock1, size_type dblock_index1, size_type start_pos_in_dblock2, size_type dblock_index2);
1133 
1134  void swap_single_block(
1135  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1136  size_type start_pos_in_block, size_type block_index, size_type start_pos_in_other_block, size_type other_block_index);
1137 
1138  void swap_single_to_multi_blocks(
1139  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1140  size_type start_pos_in_block, size_type block_index, size_type dst_start_pos_in_block1, size_type dst_block_index1,
1141  size_type dst_start_pos_in_block2, size_type dst_block_index2);
1142 
1143  void swap_multi_to_multi_blocks(
1144  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1145  size_type start_pos_in_block1, size_type block_index1, size_type start_pos_in_block2, size_type block_index2,
1146  size_type start_pos_in_dblock1, size_type dblock_index1, size_type start_pos_in_dblock2, size_type dblock_index2);
1147 
1148  void insert_blocks_at(size_type insert_pos, blocks_type& new_blocks);
1149 
1150  void prepare_blocks_to_transfer(blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1151 
1152  iterator set_whole_block_empty(size_type block_index, size_type start_pos_in_block, bool overwrite);
1153 
1154  iterator set_empty_in_single_block(
1155  size_type start_pos, size_type end_pos, size_type block_index, size_type start_pos_in_block,
1156  bool overwrite);
1157 
1158  iterator set_empty_in_multi_blocks(
1159  size_type start_pos, size_type end_pos,
1160  size_type block_index1, size_type start_pos_in_block1,
1161  size_type block_index2, size_type start_pos_in_block2, bool overwrite);
1162 
1163  void erase_impl(size_type start_pos, size_type end_pos);
1164  void erase_in_single_block(
1165  size_type start_pos, size_type end_pos, size_type block_pos, size_type start_pos_in_block);
1166 
1167  iterator insert_empty_impl(size_type row, size_type start_pos, size_type block_index, size_type length);
1168 
1169  template<typename _T>
1170  bool set_cells_precheck(
1171  size_type row, const _T& it_begin, const _T& it_end, size_type& end_pos);
1172 
1173  template<typename _T>
1174  iterator set_cells_impl(
1175  size_type row, size_type end_row, size_type start_row1, size_type block_index1, const _T& it_begin, const _T& it_end);
1176 
1177  template<typename _T>
1178  iterator insert_cells_impl(size_type row, size_type start_row, size_type block_index, const _T& it_begin, const _T& it_end);
1179 
1180  template<typename _T>
1181  iterator set_cells_to_single_block(
1182  size_type start_pos, size_type end_pos, size_type block_index,
1183  size_type start_pos_in_block, const _T& it_begin, const _T& it_end);
1184 
1185  template<typename _T>
1186  iterator set_cells_to_multi_blocks(
1187  size_type start_pos, size_type end_pos,
1188  size_type block_index1, size_type start_pos_in_block1,
1189  size_type block_index2, size_type start_pos_in_block2,
1190  const _T& it_begin, const _T& it_end);
1191 
1192  template<typename _T>
1193  iterator set_cells_to_multi_blocks_block1_non_equal(
1194  size_type start_pos, size_type end_pos,
1195  size_type block_index1, size_type start_pos_in_block1,
1196  size_type block_index2, size_type start_pos_in_block2,
1197  const _T& it_begin, const _T& it_end);
1198 
1199  template<typename _T>
1200  iterator set_cells_to_multi_blocks_block1_non_empty(
1201  size_type start_pos, size_type end_pos,
1202  size_type block_index1, size_type start_pos_in_block1,
1203  size_type block_index2, size_type start_pos_in_block2,
1204  const _T& it_begin, const _T& it_end);
1205 
1214  size_type merge_with_adjacent_blocks(size_type block_index);
1215 
1223  bool merge_with_next_block(size_type block_index);
1224 
1225  template<typename _T>
1226  bool append_to_prev_block(
1227  size_type block_index, element_category_type cat, size_type length,
1228  const _T& it_begin, const _T& it_end);
1229 
1230  template<typename _T>
1231  void insert_cells_to_middle(
1232  size_type row, size_type block_index, size_type start_pos,
1233  const _T& it_begin, const _T& it_end);
1234 
1248  block* set_new_block_to_middle(
1249  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1250 
1251  block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1252 
1260  block* get_next_block_of_type(size_type block_index, element_category_type cat);
1261 
1279  element_block_type* exchange_elements(
1280  const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1281 
1282  void exchange_elements(
1283  const element_block_type& src_data, size_type src_offset,
1284  size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1285  size_type len, blocks_type& new_blocks);
1286 
1287  bool append_empty(size_type len);
1288 
1289  inline iterator get_iterator(size_type block_index, size_type start_row)
1290  {
1291  typename blocks_type::iterator block_pos = m_blocks.begin();
1292  std::advance(block_pos, block_index);
1293  return iterator(block_pos, m_blocks.end(), start_row, block_index);
1294  }
1295 
1296  inline const_iterator get_const_iterator(size_type block_index, size_type start_row) const
1297  {
1298  typename blocks_type::const_iterator block_pos = m_blocks.begin();
1299  std::advance(block_pos, block_index);
1300  return const_iterator(block_pos, m_blocks.end(), start_row, block_index);
1301  }
1302 
1303 private:
1304  event_func m_hdl_event;
1305  blocks_type m_blocks;
1306  size_type m_cur_size;
1307 };
1308 
1309 }
1310 
1311 #include "multi_type_vector_def.inl"
1312 
1313 #endif
_EventFunc event_func
Definition: multi_type_vector.hpp:119
Definition: multi_type_vector_types.hpp:88
Definition: multi_type_vector_itr.hpp:109
itr_node value_type
Definition: multi_type_vector.hpp:207
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:93