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>
95 class multi_type_vector
96 {
97 public:
98  typedef size_t size_type;
99 
100  typedef typename mdds::mtv::base_element_block element_block_type;
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_position;
128  size_type m_size;
129  element_block_type* mp_data;
130 
131  block();
132  block(size_type _position, size_type _size);
133  block(size_type _position, size_type _size, element_block_type* _data);
134  block(const block& other);
135  block(block&& other);
136  ~block();
137  void swap(block& other);
138  void clone_to(block& other) const;
139 
140  block& operator=(block);
141  };
142 
143  struct element_block_deleter
144  {
145  void operator() (const element_block_type* p)
146  {
147  element_block_func::delete_block(p);
148  }
149  };
150 
151  typedef std::vector<block> blocks_type;
152 
153  struct blocks_to_transfer
154  {
155  blocks_type blocks;
156  size_type insert_index;
157 
158  blocks_to_transfer();
159  };
160 
161  struct iterator_trait
162  {
163  typedef multi_type_vector parent;
164  typedef blocks_type blocks;
165  typedef typename blocks_type::iterator base_iterator;
166  };
167 
168  struct reverse_iterator_trait
169  {
170  typedef multi_type_vector parent;
171  typedef blocks_type blocks;
172  typedef typename blocks_type::reverse_iterator base_iterator;
173  };
174 
175  struct const_iterator_trait
176  {
177  typedef multi_type_vector parent;
178  typedef blocks_type blocks;
179  typedef typename blocks_type::const_iterator base_iterator;
180  };
181 
182  struct const_reverse_iterator_trait
183  {
184  typedef multi_type_vector parent;
185  typedef blocks_type blocks;
186  typedef typename blocks_type::const_reverse_iterator base_iterator;
187  };
188 
189  typedef detail::mtv::iterator_value_node<size_type, element_block_type> itr_node;
190  typedef detail::mtv::private_data_forward_update<itr_node> itr_forward_update;
191  typedef detail::mtv::private_data_no_update<itr_node> itr_no_update;
192 
193 public:
194 
195  typedef detail::mtv::iterator_base<iterator_trait, itr_forward_update> iterator;
196  typedef detail::mtv::iterator_base<reverse_iterator_trait, itr_no_update> reverse_iterator;
197 
198  typedef detail::mtv::const_iterator_base<const_iterator_trait, itr_forward_update, iterator> const_iterator;
199  typedef detail::mtv::const_iterator_base<const_reverse_iterator_trait, itr_no_update, reverse_iterator> const_reverse_iterator;
200 
216  typedef itr_node value_type;
217 
218  typedef std::pair<iterator, size_type> position_type;
219  typedef std::pair<const_iterator, size_type> const_position_type;
220 
229  static position_type next_position(const position_type& pos);
230 
240  static position_type advance_position(const position_type& pos, int steps);
241 
250  static const_position_type next_position(const const_position_type& pos);
251 
261  static const_position_type advance_position(const const_position_type& pos, int steps);
262 
271  static size_type logical_position(const const_position_type& pos);
272 
281  template<typename _Blk>
282  static typename _Blk::value_type get(const const_position_type& pos);
283 
284  iterator begin();
285  iterator end();
286 
287  const_iterator begin() const;
288  const_iterator end() const;
289 
290  const_iterator cbegin() const;
291  const_iterator cend() const;
292 
293  reverse_iterator rbegin();
294  reverse_iterator rend();
295 
296  const_reverse_iterator rbegin() const;
297  const_reverse_iterator rend() const;
298 
299  const_reverse_iterator crbegin() const;
300  const_reverse_iterator crend() const;
301 
302  event_func& event_handler();
303  const event_func& event_handler() const;
304 
309 
316  multi_type_vector(const event_func& hdl);
317 
325 
333  multi_type_vector(size_type init_size);
334 
344  template<typename _T>
345  multi_type_vector(size_type init_size, const _T& value);
346 
360  template<typename _T>
361  multi_type_vector(size_type init_size, const _T& it_begin, const _T& it_end);
362 
368  multi_type_vector(const multi_type_vector& other);
369 
374 
391  template<typename _T>
392  iterator set(size_type pos, const _T& value);
393 
426  template<typename _T>
427  iterator set(const iterator& pos_hint, size_type pos, const _T& value);
428 
450  template<typename _T>
451  iterator set(size_type pos, const _T& it_begin, const _T& it_end);
452 
490  template<typename _T>
491  iterator set(const iterator& pos_hint, size_type pos, const _T& it_begin, const _T& it_end);
492 
502  template<typename _T>
503  iterator push_back(const _T& value);
504 
512  iterator push_back_empty();
513 
535  template<typename _T>
536  iterator insert(size_type pos, const _T& it_begin, const _T& it_end);
537 
575  template<typename _T>
576  iterator insert(const iterator& pos_hint, size_type pos, const _T& it_begin, const _T& it_end);
577 
588  template<typename _T>
589  void get(size_type pos, _T& value) const;
590 
602  template<typename _T>
603  _T get(size_type pos) const;
604 
619  template<typename _T>
620  _T release(size_type pos);
621 
638  template<typename _T>
639  iterator release(size_type pos, _T& value);
640 
657  template<typename _T>
658  iterator release(const iterator& pos_hint, size_type pos, _T& value);
659 
668  void release();
669 
685  iterator release_range(size_type start_pos, size_type end_pos);
686 
711  iterator release_range(const iterator& pos_hint, size_type start_pos, size_type end_pos);
712 
729  position_type position(size_type pos);
730 
750  position_type position(const iterator& pos_hint, size_type pos);
751 
765  const_position_type position(size_type pos) const;
766 
783  const_position_type position(const const_iterator& pos_hint, size_type pos) const;
784 
809  iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
810 
838  iterator transfer(const iterator& pos_hint, size_type start_pos, size_type end_pos, multi_type_vector& dest, size_type dest_pos);
839 
847  mtv::element_t get_type(size_type pos) const;
848 
860  bool is_empty(size_type pos) const;
861 
875  iterator set_empty(size_type start_pos, size_type end_pos);
876 
906  iterator set_empty(const iterator& pos_hint, size_type start_pos, size_type end_pos);
907 
923  void erase(size_type start_pos, size_type end_pos);
924 
943  iterator insert_empty(size_type pos, size_type length);
944 
979  iterator insert_empty(const iterator& pos_hint, size_type pos, size_type length);
980 
985  void clear();
986 
992  size_type size() const;
993 
1011  size_type block_size() const;
1012 
1018  bool empty() const;
1019 
1027  void resize(size_type new_size);
1028 
1034  void swap(multi_type_vector& other);
1035 
1044  void swap(size_type start_pos, size_type end_pos, multi_type_vector& other, size_type other_pos);
1045 
1049  void shrink_to_fit();
1050 
1051  bool operator== (const multi_type_vector& other) const;
1052  bool operator!= (const multi_type_vector& other) const;
1053 
1054  multi_type_vector& operator= (const multi_type_vector& other);
1055 
1063  template<typename _T>
1064  static mtv::element_t get_element_type(const _T& elem);
1065 
1066 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
1067  void dump_blocks(std::ostream& os) const;
1068 
1069  bool check_block_integrity() const;
1070 #endif
1071 
1072 private:
1073 
1074  void adjust_block_positions(int64_t start_block_index, size_type delta);
1075 
1082  void delete_element_block(block& blk);
1083 
1091  void delete_element_blocks(typename blocks_type::iterator it, typename blocks_type::iterator it_end);
1092 
1093  template<typename _T>
1094  iterator set_impl(size_type pos, size_type block_index, const _T& value);
1095 
1096  template<typename _T>
1097  iterator release_impl(size_type pos, size_type block_index, _T& value);
1098 
1099  template<typename _T>
1100  iterator push_back_impl(const _T& value);
1101 
1110  size_type get_block_position(size_type row, size_type start_block_index=0) const;
1111 
1116  size_type get_block_position(const const_iterator& pos_hint, size_type row) const;
1117 
1118  template<typename _T>
1119  void create_new_block_with_new_cell(element_block_type*& data, const _T& cell);
1120 
1121  template<typename _T>
1122  iterator set_cell_to_middle_of_block(
1123  size_type block_index, size_type pos_in_block, const _T& cell);
1124 
1125  template<typename _T>
1126  void append_cell_to_block(size_type block_index, const _T& cell);
1127 
1128  template<typename _T>
1129  iterator set_cell_to_empty_block(
1130  size_type start_row, size_type block_index, size_type pos_in_block, const _T& cell);
1131 
1132  template<typename _T>
1133  iterator set_cell_to_block_of_size_one(
1134  size_type block_index, const _T& cell);
1135 
1136  template<typename _T>
1137  void set_cell_to_top_of_data_block(
1138  size_type block_index, const _T& cell);
1139 
1140  template<typename _T>
1141  void set_cell_to_bottom_of_data_block(
1142  size_type block_index, const _T& cell);
1143 
1144  iterator transfer_impl(
1145  size_type start_pos, size_type end_pos, size_type block_index1,
1146  multi_type_vector& dest, size_type dest_pos);
1147 
1151  iterator transfer_single_block(
1152  size_type start_pos, size_type end_pos, size_type block_index1,
1153  multi_type_vector& dest, size_type dest_pos);
1154 
1159  iterator transfer_multi_blocks(
1160  size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2,
1161  multi_type_vector& dest, size_type dest_pos);
1162 
1173  iterator set_empty_impl(
1174  size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1175 
1176  void swap_impl(
1177  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1178  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1179 
1180  void swap_single_block(
1181  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1182  size_type block_index, size_type other_block_index);
1183 
1184  void swap_single_to_multi_blocks(
1185  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1186  size_type block_index, size_type dst_block_index1, size_type dst_block_index2);
1187 
1188  void swap_multi_to_multi_blocks(
1189  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1190  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1191 
1192  void insert_blocks_at(size_type position, 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, bool overwrite);
1197 
1198  iterator set_empty_in_single_block(
1199  size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1200 
1210  iterator set_empty_in_multi_blocks(
1211  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1212  bool overwrite);
1213 
1214  void erase_impl(size_type start_pos, size_type end_pos);
1215  void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_pos);
1216 
1222  iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1223 
1224  template<typename _T>
1225  bool set_cells_precheck(
1226  size_type row, const _T& it_begin, const _T& it_end, size_type& end_pos);
1227 
1228  template<typename _T>
1229  iterator set_cells_impl(
1230  size_type row, size_type end_row, size_type block_index1, const _T& it_begin, const _T& it_end);
1231 
1232  template<typename _T>
1233  iterator insert_cells_impl(size_type row, size_type block_index, const _T& it_begin, const _T& it_end);
1234 
1235  template<typename _T>
1236  iterator set_cells_to_single_block(
1237  size_type start_row, size_type end_row, size_type block_index,
1238  const _T& it_begin, const _T& it_end);
1239 
1240  template<typename _T>
1241  iterator set_cells_to_multi_blocks(
1242  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1243  const _T& it_begin, const _T& it_end);
1244 
1245  template<typename _T>
1246  iterator set_cells_to_multi_blocks_block1_non_equal(
1247  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1248  const _T& it_begin, const _T& it_end);
1249 
1250  template<typename _T>
1251  iterator set_cells_to_multi_blocks_block1_non_empty(
1252  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1253  const _T& it_begin, const _T& it_end);
1254 
1263  size_type merge_with_adjacent_blocks(size_type block_index);
1264 
1272  bool merge_with_next_block(size_type block_index);
1273 
1274  template<typename _T>
1275  bool append_to_prev_block(
1276  size_type block_index, element_category_type cat, size_type length,
1277  const _T& it_begin, const _T& it_end);
1278 
1279  template<typename _T>
1280  void insert_cells_to_middle(
1281  size_type row, size_type block_index, const _T& it_begin, const _T& it_end);
1282 
1296  block& set_new_block_to_middle(
1297  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1298 
1299  block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1300 
1308  block* get_next_block_of_type(size_type block_index, element_category_type cat);
1309 
1327  element_block_type* exchange_elements(
1328  const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1329 
1330  void exchange_elements(
1331  const element_block_type& src_data, size_type src_offset,
1332  size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1333  size_type len, blocks_type& new_blocks);
1334 
1335  bool append_empty(size_type len);
1336 
1337  inline iterator get_iterator(size_type block_index)
1338  {
1339  typename blocks_type::iterator block_pos = m_blocks.begin();
1340  std::advance(block_pos, block_index);
1341  return iterator(block_pos, m_blocks.end(), block_index);
1342  }
1343 
1344  inline const_iterator get_const_iterator(size_type block_index) const
1345  {
1346  typename blocks_type::const_iterator block_pos = m_blocks.begin();
1347  std::advance(block_pos, block_index);
1348  return const_iterator(block_pos, m_blocks.end(), block_index);
1349  }
1350 
1351 private:
1352  event_func m_hdl_event;
1353  blocks_type m_blocks;
1354  size_type m_cur_size;
1355 };
1356 
1357 }
1358 
1359 #include "multi_type_vector_def.inl"
1360 
1361 #endif
mdds::multi_type_vector::logical_position
static size_type logical_position(const const_position_type &pos)
mdds::multi_type_vector::event_func
_EventFunc event_func
Definition: multi_type_vector.hpp:144
mdds::multi_type_vector::value_type
itr_node value_type
Definition: multi_type_vector.hpp:239
mdds::multi_type_vector::shrink_to_fit
void shrink_to_fit()
mdds::multi_type_vector::size
size_type size() const
mdds::multi_type_vector::erase
void erase(size_type start_pos, size_type end_pos)
mdds::multi_type_vector::is_empty
bool is_empty(size_type pos) const
mdds::multi_type_vector::insert
iterator insert(size_type pos, const _T &it_begin, const _T &it_end)
mdds::multi_type_vector::next_position
static position_type next_position(const position_type &pos)
mdds::multi_type_vector::clear
void clear()
mdds::multi_type_vector::get
static _Blk::value_type get(const const_position_type &pos)
mdds::multi_type_vector::advance_position
static position_type advance_position(const position_type &pos, int steps)
mdds::multi_type_vector::set_empty
iterator set_empty(size_type start_pos, size_type end_pos)
mdds::multi_type_vector::block_size
size_type block_size() const
mdds::multi_type_vector::~multi_type_vector
~multi_type_vector()
mdds::multi_type_vector::position
position_type position(size_type pos)
mdds::multi_type_vector::get_type
mtv::element_t get_type(size_type pos) const
mdds::multi_type_vector::transfer
iterator transfer(size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
mdds::multi_type_vector::get_element_type
static mtv::element_t get_element_type(const _T &elem)
mdds::multi_type_vector::release_range
iterator release_range(size_type start_pos, size_type end_pos)
mdds::multi_type_vector::release
void release()
mdds::multi_type_vector::resize
void resize(size_type new_size)
mdds::multi_type_vector::swap
void swap(multi_type_vector &other)
mdds::multi_type_vector::set
iterator set(size_type pos, const _T &value)
mdds::multi_type_vector::push_back_empty
iterator push_back_empty()
mdds::multi_type_vector::insert_empty
iterator insert_empty(size_type pos, size_type length)
mdds::multi_type_vector::empty
bool empty() const
mdds::multi_type_vector::multi_type_vector
multi_type_vector()
mdds::multi_type_vector::push_back
iterator push_back(const _T &value)
mdds::mtv::base_element_block
Definition: multi_type_vector_types.hpp:136