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