mdds
multi_type_vector_types.hpp
1 /*************************************************************************
2  *
3  * Copyright (c) 2012-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_TYPES_HPP
29 #define MDDS_MULTI_TYPE_VECTOR_TYPES_HPP
30 
31 #include "default_deleter.hpp"
32 #include "global.hpp"
33 
34 #include <algorithm>
35 #include <cassert>
36 #include <memory>
37 
38 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
39 #include <deque>
40 #else
41 #include <vector>
42 #endif
43 
44 #if defined(MDDS_UNIT_TEST) || defined (MDDS_MULTI_TYPE_VECTOR_DEBUG)
45 #include <iostream>
46 #include <sstream>
47 using std::cout;
48 using std::cerr;
49 using std::endl;
50 #endif
51 
52 namespace mdds { namespace mtv {
53 
54 typedef int element_t;
55 
56 const element_t element_type_empty = -1;
57 
58 const element_t element_type_numeric = 0;
59 const element_t element_type_string = 1;
60 const element_t element_type_short = 2;
61 const element_t element_type_ushort = 3;
62 const element_t element_type_int = 4;
63 const element_t element_type_uint = 5;
64 const element_t element_type_long = 6;
65 const element_t element_type_ulong = 7;
66 const element_t element_type_boolean = 8;
67 const element_t element_type_char = 9;
68 const element_t element_type_uchar = 10;
69 
70 const element_t element_type_user_start = 50;
71 
76 {
77 public:
78  element_block_error(const std::string& msg) : mdds::general_error(msg) {}
79 };
80 
81 struct base_element_block;
82 element_t get_block_type(const base_element_block&);
83 
89 {
90  friend element_t get_block_type(const base_element_block&);
91 protected:
92  element_t type;
93  base_element_block(element_t _t) : type(_t) {}
94  ~base_element_block() {}
95 };
96 
97 template<typename _Self, element_t _TypeId, typename _Data>
99 {
100 #ifdef MDDS_UNIT_TEST
101  struct print_block_array
102  {
103  void operator() (const _Data& val) const
104  {
105  std::cout << val << " ";
106  }
107  };
108 #endif
109 
110 protected:
111 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
112  typedef std::deque<_Data> store_type;
113 #else
114  typedef std::vector<_Data> store_type;
115 #endif
116  store_type m_array;
117 
118  element_block() : base_element_block(_TypeId) {}
119  element_block(size_t n) : base_element_block(_TypeId), m_array(n) {}
120  element_block(size_t n, const _Data& val) : base_element_block(_TypeId), m_array(n, val) {}
121 
122  template<typename _Iter>
123  element_block(const _Iter& it_begin, const _Iter& it_end) : base_element_block(_TypeId), m_array(it_begin, it_end) {}
124 
125 public:
126  static const element_t block_type = _TypeId;
127 
128  typedef typename store_type::iterator iterator;
129  typedef typename store_type::reverse_iterator reverse_iterator;
130  typedef typename store_type::const_iterator const_iterator;
131  typedef typename store_type::const_reverse_iterator const_reverse_iterator;
132  typedef _Data value_type;
133 
134  bool operator== (const _Self& r) const
135  {
136  return m_array == r.m_array;
137  }
138 
139  bool operator!= (const _Self& r) const
140  {
141  return !operator==(r);
142  }
143 
144  static const value_type& at(const base_element_block& block, typename store_type::size_type pos)
145  {
146  return get(block).m_array.at(pos);
147  }
148 
149  static value_type& at(base_element_block& block, typename store_type::size_type pos)
150  {
151  return get(block).m_array.at(pos);
152  }
153 
154  static iterator begin(base_element_block& block)
155  {
156  return get(block).m_array.begin();
157  }
158 
159  static iterator end(base_element_block& block)
160  {
161  return get(block).m_array.end();
162  }
163 
164  static const_iterator begin(const base_element_block& block)
165  {
166  return get(block).m_array.begin();
167  }
168 
169  static const_iterator end(const base_element_block& block)
170  {
171  return get(block).m_array.end();
172  }
173 
174  static reverse_iterator rbegin(base_element_block& block)
175  {
176  return get(block).m_array.rbegin();
177  }
178 
179  static reverse_iterator rend(base_element_block& block)
180  {
181  return get(block).m_array.rend();
182  }
183 
184  static const_reverse_iterator rbegin(const base_element_block& block)
185  {
186  return get(block).m_array.rbegin();
187  }
188 
189  static const_reverse_iterator rend(const base_element_block& block)
190  {
191  return get(block).m_array.rend();
192  }
193 
194  static _Self& get(base_element_block& block)
195  {
196 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
197  if (get_block_type(block) != _TypeId)
198  {
199  std::ostringstream os;
200  os << "incorrect block type: expected block type=" << _TypeId << ", passed block type=" << get_block_type(block);
201  throw general_error(os.str());
202  }
203 #endif
204  return static_cast<_Self&>(block);
205  }
206 
207  static const _Self& get(const base_element_block& block)
208  {
209 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
210  if (get_block_type(block) != _TypeId)
211  {
212  std::ostringstream os;
213  os << "incorrect block type: expected block type=" << _TypeId << ", passed block type=" << get_block_type(block);
214  throw general_error(os.str());
215  }
216 #endif
217  return static_cast<const _Self&>(block);
218  }
219 
220  static void set_value(base_element_block& blk, size_t pos, const _Data& val)
221  {
222  get(blk).m_array[pos] = val;
223  }
224 
225  static void get_value(const base_element_block& blk, size_t pos, _Data& val)
226  {
227  val = get(blk).m_array[pos];
228  }
229 
230  static void append_value(base_element_block& blk, const _Data& val)
231  {
232  get(blk).m_array.push_back(val);
233  }
234 
235  static void prepend_value(base_element_block& blk, const _Data& val)
236  {
237  store_type& blk2 = get(blk).m_array;
238  blk2.insert(blk2.begin(), val);
239  }
240 
241  static _Self* create_block(size_t init_size)
242  {
243  return new _Self(init_size);
244  }
245 
246  static void delete_block(const base_element_block* p)
247  {
248  delete static_cast<const _Self*>(p);
249  }
250 
251  static void resize_block(base_element_block& blk, size_t new_size)
252  {
253  store_type& st = get(blk).m_array;
254  st.resize(new_size);
255 
256  // Test if the vector's capacity is larger than twice its current
257  // size, and if so, shrink its capacity to free up some memory.
258  if (new_size < (st.capacity() / 2))
259  st.shrink_to_fit();
260  }
261 
262 #ifdef MDDS_UNIT_TEST
263  static void print_block(const base_element_block& blk)
264  {
265  const store_type& blk2 = get(blk).m_array;
266  std::for_each(blk2.begin(), blk2.end(), print_block_array());
267  std::cout << std::endl;
268  }
269 #else
270  static void print_block(const base_element_block&) {}
271 #endif
272 
273  static void erase_block(base_element_block& blk, size_t pos)
274  {
275  store_type& blk2 = get(blk).m_array;
276  blk2.erase(blk2.begin()+pos);
277  }
278 
279  static void erase_block(base_element_block& blk, size_t pos, size_t size)
280  {
281  store_type& blk2 = get(blk).m_array;
282  blk2.erase(blk2.begin()+pos, blk2.begin()+pos+size);
283  }
284 
285  static void append_values_from_block(base_element_block& dest, const base_element_block& src)
286  {
287  store_type& d = get(dest).m_array;
288  const store_type& s = get(src).m_array;
289  d.insert(d.end(), s.begin(), s.end());
290  }
291 
292  static void append_values_from_block(
293  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
294  {
295  store_type& d = get(dest).m_array;
296  const store_type& s = get(src).m_array;
297  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
298 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
299  d.reserve(d.size() + len);
300 #endif
301  d.insert(d.end(), its.first, its.second);
302  }
303 
304  static void assign_values_from_block(
305  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
306  {
307  store_type& d = get(dest).m_array;
308  const store_type& s = get(src).m_array;
309  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
310  d.assign(its.first, its.second);
311  }
312 
313  static void prepend_values_from_block(
314  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
315  {
316  store_type& d = get(dest).m_array;
317  const store_type& s = get(src).m_array;
318  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
319 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
320  d.reserve(d.size() + len);
321 #endif
322  d.insert(d.begin(), its.first, its.second);
323  }
324 
325  static void swap_values(
326  base_element_block& blk1, base_element_block& blk2, size_t pos1, size_t pos2, size_t len)
327  {
328  store_type& st1 = get(blk1).m_array;
329  store_type& st2 = get(blk2).m_array;
330  assert(pos1 + len <= st1.size());
331  assert(pos2 + len <= st2.size());
332 
333  typename store_type::iterator it1 = st1.begin(), it2 = st2.begin();
334  std::advance(it1, pos1);
335  std::advance(it2, pos2);
336  for (size_t i = 0; i < len; ++i, ++it1, ++it2)
337  {
338 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
339  std::swap(*it1, *it2);
340 #else
341  value_type v1 = *it1, v2 = *it2;
342  *it1 = v2;
343  *it2 = v1;
344 #endif
345  }
346  }
347 
348  template<typename _Iter>
349  static void set_values(
350  base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
351  {
352  store_type& d = get(block).m_array;
353  typename store_type::iterator it_dest = d.begin();
354  std::advance(it_dest, pos);
355  for (_Iter it = it_begin; it != it_end; ++it, ++it_dest)
356  *it_dest = *it;
357  }
358 
359  template<typename _Iter>
360  static void append_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
361  {
362  store_type& d = get(block).m_array;
363  typename store_type::iterator it = d.end();
364  d.insert(it, it_begin, it_end);
365  }
366 
367  template<typename _Iter>
368  static void prepend_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
369  {
370  store_type& d = get(block).m_array;
371  d.insert(d.begin(), it_begin, it_end);
372  }
373 
374  template<typename _Iter>
375  static void assign_values(base_element_block& dest, const _Iter& it_begin, const _Iter& it_end)
376  {
377  store_type& d = get(dest).m_array;
378  d.assign(it_begin, it_end);
379  }
380 
381  template<typename _Iter>
382  static void insert_values(
383  base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
384  {
385  store_type& blk = get(block).m_array;
386  blk.insert(blk.begin()+pos, it_begin, it_end);
387  }
388 
389  static size_t capacity(const base_element_block& block)
390  {
391 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
392  return 0;
393 #else
394  const store_type& blk = get(block).m_array;
395  return blk.capacity();
396 #endif
397  }
398 
399  static void shrink_to_fit(base_element_block& block)
400  {
401 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
402  get(block).m_array.shrink_to_fit();
403 #endif
404  }
405 
406 private:
407  static std::pair<const_iterator,const_iterator>
408  get_iterator_pair(const store_type& array, size_t begin_pos, size_t len)
409  {
410  assert(begin_pos + len <= array.size());
411  const_iterator it = array.begin();
412  std::advance(it, begin_pos);
413  const_iterator it_end = it;
414  std::advance(it_end, len);
415  return std::pair<const_iterator,const_iterator>(it, it_end);
416  }
417 };
418 
419 template<typename _Self, element_t _TypeId, typename _Data>
420 class copyable_element_block : public element_block<_Self, _TypeId, _Data>
421 {
423 protected:
424  copyable_element_block() : base_type() {}
425  copyable_element_block(size_t n) : base_type(n) {}
426  copyable_element_block(size_t n, const _Data& val) : base_type(n, val) {}
427 
428  template<typename _Iter>
429  copyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
430 
431 public:
432  using base_type::get;
433 
434  static _Self* clone_block(const base_element_block& blk)
435  {
436  // Use copy constructor to copy the data.
437  return new _Self(get(blk));
438  }
439 };
440 
441 template<typename _Self, element_t _TypeId, typename _Data>
442 class noncopyable_element_block : public element_block<_Self, _TypeId, _Data>
443 {
445 protected:
446  noncopyable_element_block() : base_type() {}
447  noncopyable_element_block(size_t n) : base_type(n) {}
448  noncopyable_element_block(size_t n, const _Data& val) : base_type(n, val) {}
449 
450  template<typename _Iter>
451  noncopyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
452 
453 public:
455  noncopyable_element_block& operator=(const noncopyable_element_block&) = delete;
456 
457  static _Self* clone_block(const base_element_block&)
458  {
459  throw element_block_error("attempted to clone a noncopyable element block.");
460  }
461 };
462 
470 inline element_t get_block_type(const base_element_block& blk)
471 {
472  return blk.type;
473 }
474 
479 template<element_t _TypeId, typename _Data>
480 struct default_element_block : public copyable_element_block<default_element_block<_TypeId,_Data>, _TypeId, _Data>
481 {
484 
485  default_element_block() : base_type() {}
486  default_element_block(size_t n) : base_type(n) {}
487  default_element_block(size_t n, const _Data& val) : base_type(n, val) {}
488 
489  template<typename _Iter>
490  default_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
491 
492  static self_type* create_block_with_value(size_t init_size, const _Data& val)
493  {
494  return new self_type(init_size, val);
495  }
496 
497  template<typename _Iter>
498  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
499  {
500  return new self_type(it_begin, it_end);
501  }
502 
503  static void overwrite_values(base_element_block&, size_t, size_t)
504  {
505  // Do nothing.
506  }
507 };
508 
513 template<element_t _TypeId, typename _Data>
514 struct managed_element_block : public copyable_element_block<managed_element_block<_TypeId,_Data>, _TypeId, _Data*>
515 {
518 
519  using base_type::get;
520  using base_type::set_value;
521  using base_type::m_array;
522 
523  managed_element_block() : base_type() {}
524  managed_element_block(size_t n) : base_type(n) {}
526  {
527 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
528  m_array.reserve(r.m_array.size());
529 #endif
530  typename managed_element_block::store_type::const_iterator it = r.m_array.begin(), it_end = r.m_array.end();
531  for (; it != it_end; ++it)
532  m_array.push_back(new _Data(**it));
533  }
534 
535  template<typename _Iter>
536  managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
537 
539  {
540  std::for_each(m_array.begin(), m_array.end(), mdds::default_deleter<_Data>());
541  }
542 
543  static self_type* create_block_with_value(size_t init_size, _Data* val)
544  {
545  // Managed blocks don't support initialization with value.
546  if (init_size > 1)
547  throw general_error("You can't create a managed block with initial value.");
548 
549  std::unique_ptr<self_type> blk = make_unique<self_type>(init_size);
550  if (init_size == 1)
551  set_value(*blk, 0, val);
552 
553  return blk.release();
554  }
555 
556  template<typename _Iter>
557  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
558  {
559  return new self_type(it_begin, it_end);
560  }
561 
562  static void overwrite_values(base_element_block& block, size_t pos, size_t len)
563  {
564  managed_element_block& blk = get(block);
565  typename managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
566  typename managed_element_block::store_type::iterator it_end = it + len;
567  std::for_each(it, it_end, mdds::default_deleter<_Data>());
568  }
569 };
570 
571 template<element_t _TypeId, typename _Data>
572 struct noncopyable_managed_element_block : public noncopyable_element_block<noncopyable_managed_element_block<_TypeId,_Data>, _TypeId, _Data*>
573 {
576 
577  using base_type::get;
578  using base_type::m_array;
579  using base_type::set_value;
580 
581  noncopyable_managed_element_block() : base_type() {}
582  noncopyable_managed_element_block(size_t n) : base_type(n) {}
583 
584  template<typename _Iter>
585  noncopyable_managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
586 
588  {
589  std::for_each(m_array.begin(), m_array.end(), mdds::default_deleter<_Data>());
590  }
591 
592  static self_type* create_block_with_value(size_t init_size, _Data* val)
593  {
594  // Managed blocks don't support initialization with value.
595  if (init_size > 1)
596  throw general_error("You can't create a managed block with initial value.");
597 
598  std::unique_ptr<self_type> blk = make_unique<self_type>(init_size);
599  if (init_size == 1)
600  set_value(*blk, 0, val);
601 
602  return blk.release();
603  }
604 
605  template<typename _Iter>
606  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
607  {
608  return new self_type(it_begin, it_end);
609  }
610 
611  static void overwrite_values(base_element_block& block, size_t pos, size_t len)
612  {
613  noncopyable_managed_element_block& blk = get(block);
614  typename noncopyable_managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
615  typename noncopyable_managed_element_block::store_type::iterator it_end = it + len;
616  std::for_each(it, it_end, mdds::default_deleter<_Data>());
617  }
618 };
619 
631 
632 }}
633 
634 #endif
Definition: multi_type_vector_types.hpp:75
Definition: multi_type_vector_types.hpp:572
Definition: multi_type_vector_types.hpp:88
Definition: multi_type_vector_types.hpp:420
Definition: multi_type_vector_types.hpp:514
Definition: default_deleter.hpp:36
Definition: multi_type_vector_types.hpp:98
Definition: multi_type_vector_types.hpp:480
Definition: global.hpp:58
Definition: default_deleter.hpp:33
Definition: multi_type_vector_types.hpp:442