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 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 
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 
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 
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 
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 
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, int64_t 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(size_type block_index, size_type pos_in_block, const _T& cell);
1130 
1131  template<typename _T>
1132  iterator set_cell_to_block_of_size_one(
1133  size_type block_index, const _T& cell);
1134 
1135  template<typename _T>
1136  void set_cell_to_top_of_data_block(
1137  size_type block_index, const _T& cell);
1138 
1139  template<typename _T>
1140  void set_cell_to_bottom_of_data_block(
1141  size_type block_index, const _T& cell);
1142 
1143  iterator transfer_impl(
1144  size_type start_pos, size_type end_pos, size_type block_index1,
1145  multi_type_vector& dest, size_type dest_pos);
1146 
1150  iterator transfer_single_block(
1151  size_type start_pos, size_type end_pos, size_type block_index1,
1152  multi_type_vector& dest, size_type dest_pos);
1153 
1158  iterator transfer_multi_blocks(
1159  size_type start_pos, size_type end_pos, size_type block_index1, size_type block_index2,
1160  multi_type_vector& dest, size_type dest_pos);
1161 
1172  iterator set_empty_impl(
1173  size_type start_pos, size_type end_pos, size_type block_index1, bool overwrite);
1174 
1175  void swap_impl(
1176  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1177  size_type block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1178 
1179  void swap_single_block(
1180  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1181  size_type block_index, size_type other_block_index);
1182 
1183  void swap_single_to_multi_blocks(
1184  multi_type_vector& other, size_type start_pos, size_type end_pos, size_type other_pos,
1185  size_type block_index, size_type dst_block_index1, 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 block_index1, size_type block_index2, size_type dblock_index1, size_type dblock_index2);
1190 
1191  void insert_blocks_at(size_type position, size_type insert_pos, blocks_type& new_blocks);
1192 
1193  void prepare_blocks_to_transfer(blocks_to_transfer& bucket, size_type block_index1, size_type offset1, size_type block_index2, size_type offset2);
1194 
1195  iterator set_whole_block_empty(size_type block_index, bool overwrite);
1196 
1197  iterator set_empty_in_single_block(
1198  size_type start_row, size_type end_row, size_type block_index, bool overwrite);
1199 
1209  iterator set_empty_in_multi_blocks(
1210  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1211  bool overwrite);
1212 
1213  void erase_impl(size_type start_pos, size_type end_pos);
1214  void erase_in_single_block(size_type start_pos, size_type end_pos, size_type block_pos);
1215 
1221  iterator insert_empty_impl(size_type pos, size_type block_index, size_type length);
1222 
1223  template<typename _T>
1224  bool set_cells_precheck(
1225  size_type row, const _T& it_begin, const _T& it_end, size_type& end_pos);
1226 
1227  template<typename _T>
1228  iterator set_cells_impl(
1229  size_type row, size_type end_row, size_type block_index1, const _T& it_begin, const _T& it_end);
1230 
1231  template<typename _T>
1232  iterator insert_cells_impl(size_type row, size_type block_index, const _T& it_begin, const _T& it_end);
1233 
1234  template<typename _T>
1235  iterator set_cells_to_single_block(
1236  size_type start_row, size_type end_row, size_type block_index,
1237  const _T& it_begin, const _T& it_end);
1238 
1239  template<typename _T>
1240  iterator set_cells_to_multi_blocks(
1241  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1242  const _T& it_begin, const _T& it_end);
1243 
1244  template<typename _T>
1245  iterator set_cells_to_multi_blocks_block1_non_equal(
1246  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1247  const _T& it_begin, const _T& it_end);
1248 
1249  template<typename _T>
1250  iterator set_cells_to_multi_blocks_block1_non_empty(
1251  size_type start_row, size_type end_row, size_type block_index1, size_type block_index2,
1252  const _T& it_begin, const _T& it_end);
1253 
1262  size_type merge_with_adjacent_blocks(size_type block_index);
1263 
1271  bool merge_with_next_block(size_type block_index);
1272 
1273  template<typename _T>
1274  bool append_to_prev_block(
1275  size_type block_index, element_category_type cat, size_type length,
1276  const _T& it_begin, const _T& it_end);
1277 
1278  template<typename _T>
1279  void insert_cells_to_middle(
1280  size_type row, size_type block_index, const _T& it_begin, const _T& it_end);
1281 
1295  block& set_new_block_to_middle(
1296  size_type block_index, size_type offset, size_type new_block_size, bool overwrite);
1297 
1298  block* get_previous_block_of_type(size_type block_index, element_category_type cat);
1299 
1307  block* get_next_block_of_type(size_type block_index, element_category_type cat);
1308 
1326  element_block_type* exchange_elements(
1327  const element_block_type& src_data, size_type src_offset, size_type dst_index, size_type dst_offset, size_type len);
1328 
1329  void exchange_elements(
1330  const element_block_type& src_data, size_type src_offset,
1331  size_type dst_index1, size_type dst_offset1, size_type dst_index2, size_type dst_offset2,
1332  size_type len, blocks_type& new_blocks);
1333 
1334  bool append_empty(size_type len);
1335 
1336  inline iterator get_iterator(size_type block_index)
1337  {
1338  typename blocks_type::iterator block_pos = m_blocks.begin();
1339  std::advance(block_pos, block_index);
1340  return iterator(block_pos, m_blocks.end(), block_index);
1341  }
1342 
1343  inline const_iterator get_const_iterator(size_type block_index) const
1344  {
1345  typename blocks_type::const_iterator block_pos = m_blocks.begin();
1346  std::advance(block_pos, block_index);
1347  return const_iterator(block_pos, m_blocks.end(), block_index);
1348  }
1349 
1350 private:
1351  event_func m_hdl_event;
1352  blocks_type m_blocks;
1353  size_type m_cur_size;
1354 };
1355 
1356 }
1357 
1358 #include "multi_type_vector_def.inl"
1359 
1360 #endif
mdds::multi_type_vector::set
iterator set(size_type pos, const _T &it_begin, const _T &it_end)
mdds::detail::mtv::iterator_value_node
Definition: multi_type_vector_itr.hpp:45
mdds::multi_type_vector::release
_T release(size_type pos)
mdds::multi_type_vector::transfer
iterator transfer(const iterator &pos_hint, size_type start_pos, size_type end_pos, multi_type_vector &dest, size_type dest_pos)
mdds::multi_type_vector::logical_position
static size_type logical_position(const const_position_type &pos)
mdds::multi_type_vector::set
iterator set(const iterator &pos_hint, size_type pos, const _T &value)
mdds::multi_type_vector::event_func
_EventFunc event_func
Definition: multi_type_vector.hpp:121
mdds::multi_type_vector::value_type
itr_node value_type
Definition: multi_type_vector.hpp:216
mdds::multi_type_vector::position
position_type position(const iterator &pos_hint, size_type pos)
mdds::multi_type_vector::release
iterator release(size_type pos, _T &value)
mdds::multi_type_vector::shrink_to_fit
void shrink_to_fit()
mdds::multi_type_vector::size
size_type size() const
mdds::multi_type_vector::set
iterator set(const iterator &pos_hint, size_type pos, const _T &it_begin, const _T &it_end)
mdds::multi_type_vector::erase
void erase(size_type start_pos, size_type end_pos)
mdds::multi_type_vector::position
const_position_type position(size_type pos) const
mdds::multi_type_vector::is_empty
bool is_empty(size_type pos) const
mdds::detail::mtv::const_iterator_base
Definition: multi_type_vector_itr.hpp:302
mdds::multi_type_vector::multi_type_vector
multi_type_vector(size_type init_size, const _T &value)
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::multi_type_vector
multi_type_vector(size_type init_size, const _T &it_begin, const _T &it_end)
mdds::multi_type_vector::clear
void clear()
mdds::detail::mtv::event_func
Definition: multi_type_vector.hpp:58
mdds::multi_type_vector::position
const_position_type position(const const_iterator &pos_hint, size_type pos) const
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::insert_empty
iterator insert_empty(const iterator &pos_hint, size_type pos, size_type length)
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::multi_type_vector
multi_type_vector(const multi_type_vector &other)
mdds::multi_type_vector::swap
void swap(size_type start_pos, size_type end_pos, multi_type_vector &other, size_type other_pos)
mdds::multi_type_vector::position
position_type position(size_type pos)
mdds::multi_type_vector::multi_type_vector
multi_type_vector(event_func &&hdl)
mdds::multi_type_vector::advance_position
static const_position_type advance_position(const const_position_type &pos, int steps)
mdds::multi_type_vector::multi_type_vector
multi_type_vector(size_type init_size)
mdds::multi_type_vector::get_type
mtv::element_t get_type(size_type pos) const
mdds::multi_type_vector
Definition: multi_type_vector.hpp:96
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::next_position
static const_position_type next_position(const const_position_type &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::insert
iterator insert(const iterator &pos_hint, size_type pos, const _T &it_begin, const _T &it_end)
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::set_empty
iterator set_empty(const iterator &pos_hint, size_type start_pos, size_type end_pos)
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::release_range
iterator release_range(const iterator &pos_hint, size_type start_pos, size_type end_pos)
mdds::detail::mtv::iterator_base
Definition: multi_type_vector_itr.hpp:233
mdds::multi_type_vector::multi_type_vector
multi_type_vector(const event_func &hdl)
mdds::multi_type_vector::get
void get(size_type pos, _T &value) const
mdds::multi_type_vector::multi_type_vector
multi_type_vector()
mdds::multi_type_vector::release
iterator release(const iterator &pos_hint, size_type pos, _T &value)
mdds::multi_type_vector::push_back
iterator push_back(const _T &value)
mdds::mtv::base_element_block
Definition: multi_type_vector_types.hpp:90
mdds::multi_type_vector::get
_T get(size_type pos) const