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