mdds
multi_type_vector_types.hpp
1 /*************************************************************************
2  *
3  * Copyright (c) 2012-2016 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 typename store_type::size_type size(const base_element_block& block)
155  {
156  return get(block).m_array.size();
157  }
158 
159  static iterator begin(base_element_block& block)
160  {
161  return get(block).m_array.begin();
162  }
163 
164  static iterator end(base_element_block& block)
165  {
166  return get(block).m_array.end();
167  }
168 
169  static const_iterator begin(const base_element_block& block)
170  {
171  return get(block).m_array.begin();
172  }
173 
174  static const_iterator end(const base_element_block& block)
175  {
176  return get(block).m_array.end();
177  }
178 
179  static reverse_iterator rbegin(base_element_block& block)
180  {
181  return get(block).m_array.rbegin();
182  }
183 
184  static reverse_iterator rend(base_element_block& block)
185  {
186  return get(block).m_array.rend();
187  }
188 
189  static const_reverse_iterator rbegin(const base_element_block& block)
190  {
191  return get(block).m_array.rbegin();
192  }
193 
194  static const_reverse_iterator rend(const base_element_block& block)
195  {
196  return get(block).m_array.rend();
197  }
198 
199  static _Self& get(base_element_block& block)
200  {
201 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
202  if (get_block_type(block) != _TypeId)
203  {
204  std::ostringstream os;
205  os << "incorrect block type: expected block type=" << _TypeId << ", passed block type=" << get_block_type(block);
206  throw general_error(os.str());
207  }
208 #endif
209  return static_cast<_Self&>(block);
210  }
211 
212  static const _Self& get(const base_element_block& block)
213  {
214 #ifdef MDDS_MULTI_TYPE_VECTOR_DEBUG
215  if (get_block_type(block) != _TypeId)
216  {
217  std::ostringstream os;
218  os << "incorrect block type: expected block type=" << _TypeId << ", passed block type=" << get_block_type(block);
219  throw general_error(os.str());
220  }
221 #endif
222  return static_cast<const _Self&>(block);
223  }
224 
225  static void set_value(base_element_block& blk, size_t pos, const _Data& val)
226  {
227  get(blk).m_array[pos] = val;
228  }
229 
230  static void get_value(const base_element_block& blk, size_t pos, _Data& val)
231  {
232  val = get(blk).m_array[pos];
233  }
234 
235  static value_type get_value(const base_element_block& blk, size_t pos)
236  {
237  return get(blk).m_array[pos];
238  }
239 
240  static void append_value(base_element_block& blk, const _Data& val)
241  {
242  get(blk).m_array.push_back(val);
243  }
244 
245  static void prepend_value(base_element_block& blk, const _Data& val)
246  {
247  store_type& blk2 = get(blk).m_array;
248  blk2.insert(blk2.begin(), val);
249  }
250 
251  static _Self* create_block(size_t init_size)
252  {
253  return new _Self(init_size);
254  }
255 
256  static void delete_block(const base_element_block* p)
257  {
258  delete static_cast<const _Self*>(p);
259  }
260 
261  static void resize_block(base_element_block& blk, size_t new_size)
262  {
263  store_type& st = get(blk).m_array;
264  st.resize(new_size);
265 
266  // Test if the vector's capacity is larger than twice its current
267  // size, and if so, shrink its capacity to free up some memory.
268  if (new_size < (st.capacity() / 2))
269  st.shrink_to_fit();
270  }
271 
272 #ifdef MDDS_UNIT_TEST
273  static void print_block(const base_element_block& blk)
274  {
275  const store_type& blk2 = get(blk).m_array;
276  std::for_each(blk2.begin(), blk2.end(), print_block_array());
277  std::cout << std::endl;
278  }
279 #else
280  static void print_block(const base_element_block&) {}
281 #endif
282 
283  static void erase_block(base_element_block& blk, size_t pos)
284  {
285  store_type& blk2 = get(blk).m_array;
286  blk2.erase(blk2.begin()+pos);
287  }
288 
289  static void erase_block(base_element_block& blk, size_t pos, size_t size)
290  {
291  store_type& blk2 = get(blk).m_array;
292  blk2.erase(blk2.begin()+pos, blk2.begin()+pos+size);
293  }
294 
295  static void append_values_from_block(base_element_block& dest, const base_element_block& src)
296  {
297  store_type& d = get(dest).m_array;
298  const store_type& s = get(src).m_array;
299  d.insert(d.end(), s.begin(), s.end());
300  }
301 
302  static void append_values_from_block(
303  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
304  {
305  store_type& d = get(dest).m_array;
306  const store_type& s = get(src).m_array;
307  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
308 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
309  d.reserve(d.size() + len);
310 #endif
311  d.insert(d.end(), its.first, its.second);
312  }
313 
314  static void assign_values_from_block(
315  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
316  {
317  store_type& d = get(dest).m_array;
318  const store_type& s = get(src).m_array;
319  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
320  d.assign(its.first, its.second);
321  }
322 
323  static void prepend_values_from_block(
324  base_element_block& dest, const base_element_block& src, size_t begin_pos, size_t len)
325  {
326  store_type& d = get(dest).m_array;
327  const store_type& s = get(src).m_array;
328  std::pair<const_iterator,const_iterator> its = get_iterator_pair(s, begin_pos, len);
329 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
330  d.reserve(d.size() + len);
331 #endif
332  d.insert(d.begin(), its.first, its.second);
333  }
334 
335  static void swap_values(
336  base_element_block& blk1, base_element_block& blk2, size_t pos1, size_t pos2, size_t len)
337  {
338  store_type& st1 = get(blk1).m_array;
339  store_type& st2 = get(blk2).m_array;
340  assert(pos1 + len <= st1.size());
341  assert(pos2 + len <= st2.size());
342 
343  typename store_type::iterator it1 = st1.begin(), it2 = st2.begin();
344  std::advance(it1, pos1);
345  std::advance(it2, pos2);
346  for (size_t i = 0; i < len; ++i, ++it1, ++it2)
347  {
348 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
349  std::swap(*it1, *it2);
350 #else
351  value_type v1 = *it1, v2 = *it2;
352  *it1 = v2;
353  *it2 = v1;
354 #endif
355  }
356  }
357 
358  template<typename _Iter>
359  static void set_values(
360  base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
361  {
362  store_type& d = get(block).m_array;
363  typename store_type::iterator it_dest = d.begin();
364  std::advance(it_dest, pos);
365  for (_Iter it = it_begin; it != it_end; ++it, ++it_dest)
366  *it_dest = *it;
367  }
368 
369  template<typename _Iter>
370  static void append_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
371  {
372  store_type& d = get(block).m_array;
373  typename store_type::iterator it = d.end();
374  d.insert(it, it_begin, it_end);
375  }
376 
377  template<typename _Iter>
378  static void prepend_values(base_element_block& block, const _Iter& it_begin, const _Iter& it_end)
379  {
380  store_type& d = get(block).m_array;
381  d.insert(d.begin(), it_begin, it_end);
382  }
383 
384  template<typename _Iter>
385  static void assign_values(base_element_block& dest, const _Iter& it_begin, const _Iter& it_end)
386  {
387  store_type& d = get(dest).m_array;
388  d.assign(it_begin, it_end);
389  }
390 
391  template<typename _Iter>
392  static void insert_values(
393  base_element_block& block, size_t pos, const _Iter& it_begin, const _Iter& it_end)
394  {
395  store_type& blk = get(block).m_array;
396  blk.insert(blk.begin()+pos, it_begin, it_end);
397  }
398 
399  static size_t capacity(const base_element_block& block)
400  {
401 #ifdef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
402  return 0;
403 #else
404  const store_type& blk = get(block).m_array;
405  return blk.capacity();
406 #endif
407  }
408 
409  static void shrink_to_fit(base_element_block& block)
410  {
411 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
412  get(block).m_array.shrink_to_fit();
413 #endif
414  }
415 
416 private:
417  static std::pair<const_iterator,const_iterator>
418  get_iterator_pair(const store_type& array, size_t begin_pos, size_t len)
419  {
420  assert(begin_pos + len <= array.size());
421  const_iterator it = array.begin();
422  std::advance(it, begin_pos);
423  const_iterator it_end = it;
424  std::advance(it_end, len);
425  return std::pair<const_iterator,const_iterator>(it, it_end);
426  }
427 };
428 
429 template<typename _Self, element_t _TypeId, typename _Data>
430 class copyable_element_block : public element_block<_Self, _TypeId, _Data>
431 {
433 protected:
434  copyable_element_block() : base_type() {}
435  copyable_element_block(size_t n) : base_type(n) {}
436  copyable_element_block(size_t n, const _Data& val) : base_type(n, val) {}
437 
438  template<typename _Iter>
439  copyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
440 
441 public:
442  using base_type::get;
443 
444  static _Self* clone_block(const base_element_block& blk)
445  {
446  // Use copy constructor to copy the data.
447  return new _Self(get(blk));
448  }
449 };
450 
451 template<typename _Self, element_t _TypeId, typename _Data>
452 class noncopyable_element_block : public element_block<_Self, _TypeId, _Data>
453 {
455 protected:
456  noncopyable_element_block() : base_type() {}
457  noncopyable_element_block(size_t n) : base_type(n) {}
458  noncopyable_element_block(size_t n, const _Data& val) : base_type(n, val) {}
459 
460  template<typename _Iter>
461  noncopyable_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
462 
463 public:
465  noncopyable_element_block& operator=(const noncopyable_element_block&) = delete;
466 
467  static _Self* clone_block(const base_element_block&)
468  {
469  throw element_block_error("attempted to clone a noncopyable element block.");
470  }
471 };
472 
480 inline element_t get_block_type(const base_element_block& blk)
481 {
482  return blk.type;
483 }
484 
489 template<element_t _TypeId, typename _Data>
490 struct default_element_block : public copyable_element_block<default_element_block<_TypeId,_Data>, _TypeId, _Data>
491 {
494 
495  default_element_block() : base_type() {}
496  default_element_block(size_t n) : base_type(n) {}
497  default_element_block(size_t n, const _Data& val) : base_type(n, val) {}
498 
499  template<typename _Iter>
500  default_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
501 
502  static self_type* create_block_with_value(size_t init_size, const _Data& val)
503  {
504  return new self_type(init_size, val);
505  }
506 
507  template<typename _Iter>
508  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
509  {
510  return new self_type(it_begin, it_end);
511  }
512 
513  static void overwrite_values(base_element_block&, size_t, size_t)
514  {
515  // Do nothing.
516  }
517 };
518 
523 template<element_t _TypeId, typename _Data>
524 struct managed_element_block : public copyable_element_block<managed_element_block<_TypeId,_Data>, _TypeId, _Data*>
525 {
528 
529  using base_type::get;
530  using base_type::set_value;
531  using base_type::m_array;
532 
533  managed_element_block() : base_type() {}
534  managed_element_block(size_t n) : base_type(n) {}
536  {
537 #ifndef MDDS_MULTI_TYPE_VECTOR_USE_DEQUE
538  m_array.reserve(r.m_array.size());
539 #endif
540  typename managed_element_block::store_type::const_iterator it = r.m_array.begin(), it_end = r.m_array.end();
541  for (; it != it_end; ++it)
542  m_array.push_back(new _Data(**it));
543  }
544 
545  template<typename _Iter>
546  managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
547 
549  {
550  std::for_each(m_array.begin(), m_array.end(), mdds::default_deleter<_Data>());
551  }
552 
553  static self_type* create_block_with_value(size_t init_size, _Data* val)
554  {
555  // Managed blocks don't support initialization with value.
556  if (init_size > 1)
557  throw general_error("You can't create a managed block with initial value.");
558 
559  std::unique_ptr<self_type> blk = make_unique<self_type>(init_size);
560  if (init_size == 1)
561  set_value(*blk, 0, val);
562 
563  return blk.release();
564  }
565 
566  template<typename _Iter>
567  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
568  {
569  return new self_type(it_begin, it_end);
570  }
571 
572  static void overwrite_values(base_element_block& block, size_t pos, size_t len)
573  {
574  managed_element_block& blk = get(block);
575  typename managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
576  typename managed_element_block::store_type::iterator it_end = it + len;
577  std::for_each(it, it_end, mdds::default_deleter<_Data>());
578  }
579 };
580 
581 template<element_t _TypeId, typename _Data>
582 struct noncopyable_managed_element_block : public noncopyable_element_block<noncopyable_managed_element_block<_TypeId,_Data>, _TypeId, _Data*>
583 {
586 
587  using base_type::get;
588  using base_type::m_array;
589  using base_type::set_value;
590 
591  noncopyable_managed_element_block() : base_type() {}
592  noncopyable_managed_element_block(size_t n) : base_type(n) {}
593 
594  template<typename _Iter>
595  noncopyable_managed_element_block(const _Iter& it_begin, const _Iter& it_end) : base_type(it_begin, it_end) {}
596 
598  {
599  std::for_each(m_array.begin(), m_array.end(), mdds::default_deleter<_Data>());
600  }
601 
602  static self_type* create_block_with_value(size_t init_size, _Data* val)
603  {
604  // Managed blocks don't support initialization with value.
605  if (init_size > 1)
606  throw general_error("You can't create a managed block with initial value.");
607 
608  std::unique_ptr<self_type> blk = make_unique<self_type>(init_size);
609  if (init_size == 1)
610  set_value(*blk, 0, val);
611 
612  return blk.release();
613  }
614 
615  template<typename _Iter>
616  static self_type* create_block_with_values(const _Iter& it_begin, const _Iter& it_end)
617  {
618  return new self_type(it_begin, it_end);
619  }
620 
621  static void overwrite_values(base_element_block& block, size_t pos, size_t len)
622  {
623  noncopyable_managed_element_block& blk = get(block);
624  typename noncopyable_managed_element_block::store_type::iterator it = blk.m_array.begin() + pos;
625  typename noncopyable_managed_element_block::store_type::iterator it_end = it + len;
626  std::for_each(it, it_end, mdds::default_deleter<_Data>());
627  }
628 };
629 
641 
642 }}
643 
644 #endif
Definition: multi_type_vector_types.hpp:75
Definition: multi_type_vector_types.hpp:582
Definition: multi_type_vector_types.hpp:88
Definition: multi_type_vector_types.hpp:430
Definition: multi_type_vector_types.hpp:524
Definition: default_deleter.hpp:36
Definition: multi_type_vector_types.hpp:98
Definition: multi_type_vector_types.hpp:490
Definition: global.hpp:58
Definition: default_deleter.hpp:33
Definition: multi_type_vector_types.hpp:452