BioDynaMo  v1.05.0-137fdb15
inline_vector.h
Go to the documentation of this file.
1 // -----------------------------------------------------------------------------
2 //
3 // Copyright (C) 2021 CERN & University of Surrey for the benefit of the
4 // BioDynaMo collaboration. All Rights Reserved.
5 //
6 // Licensed under the Apache License, Version 2.0 (the "License");
7 // you may not use this file except in compliance with the License.
8 //
9 // See the LICENSE file distributed with this work for details.
10 // See the NOTICE file distributed with this work for additional information
11 // regarding copyright ownership.
12 //
13 // -----------------------------------------------------------------------------
14 
15 #ifndef CORE_CONTAINER_INLINE_VECTOR_H_
16 #define CORE_CONTAINER_INLINE_VECTOR_H_
17 
18 #include <algorithm>
19 #include <array>
20 #include <cassert>
21 #include <limits>
22 #include <sstream>
23 #include <typeinfo>
24 #include <vector>
25 
26 #include "core/util/io.h"
27 #include "core/util/log.h"
28 #include "core/util/root.h"
29 
30 #include "Rtypes.h"
31 
32 // Only used for our custom streamer
33 #if (!defined(__CLING__) || defined(__ROOTCLING__)) && defined(USE_DICT)
34 #include "TBuffer.h"
35 #include "TClassTable.h"
36 #include "TObject.h"
37 #endif
38 
39 namespace bdm {
40 
48 template <typename T, uint16_t N>
49 class InlineVector final {
50  public:
51  template <typename TT, typename TIV>
52  struct Iterator {
53  uint16_t index_ = 0;
54  TIV* vector_;
55 
56  Iterator(uint16_t index, TIV* iv) : index_(index), vector_(iv) {}
57  Iterator(const Iterator& other)
58  : index_(other.index_), vector_(other.vector_) {}
59 
60  TT& operator*() const { return (*vector_)[index_]; }
61 
62  Iterator& operator=(const Iterator& other) {
63  if (this != &other) {
64  index_ = other.index_;
65  vector_ = other.vector_;
66  }
67  return *this;
68  }
69 
70  bool operator==(const Iterator& other) const {
71  if (other.index_ != index_ || other.vector_ != vector_) {
72  return false;
73  }
74  return true;
75  }
76 
77  bool operator!=(const Iterator& other) const {
78  return !this->operator==(other);
79  }
80 
82  ++index_;
83  return *this;
84  }
85 
87  Iterator tmp(*this);
88  operator++();
89  return tmp;
90  }
91 
93  --index_;
94  return *this;
95  }
96 
98  Iterator tmp(*this);
99  operator--();
100  return tmp;
101  }
102 
103  Iterator& operator+=(const Iterator& rhs) {
104  assert(vector_ == rhs.vector_);
105  index_ += rhs.index_;
106  return *this;
107  }
108 
110  assert(vector_ == rhs.vector_);
111  Iterator tmp(*this);
112  tmp.index_ += rhs.index_;
113  return tmp;
114  }
115 
116  Iterator& operator+=(uint16_t i) {
117  index_ += i;
118  return *this;
119  }
120 
121  Iterator operator+(uint16_t i) {
122  Iterator tmp(*this);
123  tmp.index_ += i;
124  return tmp;
125  }
126 
127  Iterator& operator-=(const Iterator& rhs) {
128  assert(vector_ == rhs.vector_);
129  index_ -= rhs.index_;
130  return *this;
131  }
132 
134  assert(vector_ == rhs.vector_);
135  Iterator tmp(*this);
136  tmp.index_ -= rhs.index_;
137  return tmp;
138  }
139 
140  Iterator& operator-=(uint16_t i) {
141  index_ -= i;
142  return *this;
143  }
144 
145  Iterator operator-(uint16_t i) {
146  Iterator tmp(*this);
147  tmp.index_ -= i;
148  return tmp;
149  }
150  };
151 
152  using value_type = T;
153  using iterator = typename InlineVector::template Iterator<T, InlineVector>;
154  using const_iterator =
155  typename InlineVector::template Iterator<const T, const InlineVector>;
156 
157  explicit InlineVector(TRootIOCtor* io_ctor) {} // Constructor for ROOT I/O
158  InlineVector() = default;
159 
161  data_ = std::move(other.data_);
162  size_ = other.size_;
164  if (other.heap_data_ != nullptr) {
165  heap_data_ = new T[heap_capacity_];
166  std::copy_n(other.heap_data_, HeapSize(), heap_data_);
167  }
168  }
169 
170  InlineVector(InlineVector<T, N>&& other) noexcept {
171  data_ = other.data_;
172  size_ = other.size_;
173  heap_capacity_ = other.heap_capacity_;
174  heap_data_ = other.heap_data_;
175  other.heap_data_ = nullptr;
176  }
177 
179  if (heap_data_ != nullptr) {
180  heap_capacity_ = 0;
181  delete[] heap_data_;
182  }
183  }
184 
187  uint16_t capacity() const { return N + heap_capacity_; } // NOLINT
188 
191  void clear() { // NOLINT
192  size_ = 0;
193  }
194 
202  void reserve(uint16_t new_capacity) { // NOLINT
203  if (new_capacity > capacity()) {
204  heap_capacity_ = new_capacity - N;
205  T* new_heap_data = new T[heap_capacity_];
206  if (heap_data_ != nullptr) {
207  std::copy_n(heap_data_, HeapSize(), new_heap_data);
208  delete[] heap_data_;
209  }
210  heap_data_ = new_heap_data;
211  }
212  }
213 
215  uint16_t size() const { return size_; } // NOLINT
216 
219  void push_back(const T& element) { // NOLINT
220  if (size_ < N) {
221  data_[size_++] = element;
222  } else {
223  // allocate heap memory
224  assert(size_ != std::numeric_limits<uint16_t>::max() &&
225  "Maxium number of elements exceeded");
226  if (size_ == capacity()) {
227  uint64_t tmp =
228  static_cast<uint64_t>(static_cast<float>(capacity()) * kGrowFactor);
229  uint16_t new_capacity = static_cast<uint16_t>(tmp);
230  if (tmp > std::numeric_limits<uint16_t>::max()) {
231  new_capacity = std::numeric_limits<uint16_t>::max();
232  }
233  reserve(new_capacity);
234  }
235  heap_data_[HeapSize()] = element;
236  size_++;
237  }
238  }
239 
240  iterator erase(const iterator& it) {
241  auto idx = it.index_;
242  if (idx >= size_) {
243  Log::Fatal(
244  "InlineVector::erase",
245  "You tried to erase an element that is outside the InlineVector.");
246  return it;
247  } else if (idx == size_ - 1) {
248  // last element
249  size_--;
250  return end();
251  }
252 
253  // element in the middle
254  for (uint16_t i = it.index_; i < size_ - 1; i++) {
255  (*this)[i] = (*this)[i + 1];
256  }
257  size_--;
258  return iterator(idx, this);
259  }
260 
261  std::vector<T> make_std_vector() const { // NOLINT
262  std::vector<T> std_vector(size_);
263  for (uint16_t i = 0; i < size_; i++) {
264  std_vector[i] = (*this)[i];
265  }
266  return std_vector;
267  }
268 
270  if (this != &other) {
271  data_ = other.data_;
272  size_ = other.size_;
274  if (other.heap_data_ != nullptr) {
275  if (heap_data_ != nullptr) {
276  delete[] heap_data_;
277  }
278  heap_data_ = new T[heap_capacity_];
279  if (size_ > N) {
280  std::copy_n(other.heap_data_, HeapSize(), heap_data_);
281  }
282  }
283  }
284  return *this;
285  }
286 
288  if (this != &other) {
289  data_ = std::move(other.data_);
290  size_ = other.size_;
291  heap_capacity_ = other.heap_capacity_;
292  heap_data_ = other.heap_data_;
293  other.heap_data_ = nullptr;
294  other.heap_capacity_ = 0;
295  }
296  return *this;
297  }
298 
299  T& operator[](uint16_t index) {
300  if (index < N) {
301  return data_[index];
302  } else {
303  return heap_data_[index - N];
304  }
305  }
306 
307  const T& operator[](uint16_t index) const {
308  if (index < N) {
309  return data_[index];
310  } else {
311  return heap_data_[index - N];
312  }
313  }
314 
315  bool operator==(const InlineVector<T, N>& other) const {
316  if (size_ != other.size_) {
317  return false;
318  }
319  // inline data
320  for (uint16_t i = 0; i < std::min(size_, N); i++) {
321  if (data_[i] != other.data_[i]) {
322  return false;
323  }
324  }
325  // heap data
326  if (size_ > N) {
327  for (uint16_t i = 0; i < HeapSize(); i++) {
328  if (heap_data_[i] != other.heap_data_[i]) {
329  return false;
330  }
331  }
332  }
333  return true;
334  }
335 
336  friend std::ostream& operator<<(std::ostream& out,
337  const InlineVector<T, N>& other) {
338  for (uint16_t i = 0; i < other.size_; i++) {
339  out << other[i] << ", ";
340  }
341  return out;
342  }
343 
344  iterator begin() { return iterator(0, this); }
345  iterator end() { return iterator(size_, this); }
346  const_iterator begin() const { return const_iterator(0, this); }
347  const_iterator end() const { return const_iterator(size_, this); }
348 
349  private:
350  static constexpr float kGrowFactor = 1.5;
351  std::array<T, N> data_;
352  uint16_t size_ = 0;
353  uint16_t heap_capacity_ = 0;
354  T* heap_data_ = nullptr;
355 
356  uint16_t HeapSize() const {
357  if (size_ < N) {
358  return 0;
359  }
360  return size_ - N;
361  }
362 
363  BDM_CLASS_DEF_NV(InlineVector, 2); // NOLINT
364 };
365 
366 // The following custom streamer should be visible to rootcling for dictionary
367 // generation, but not to the interpreter!
368 #if (!defined(__CLING__) || defined(__ROOTCLING__)) && defined(USE_DICT)
369 
370 template <typename T, uint16_t N>
371 inline void InlineVector<T, N>::Streamer(TBuffer& R__b) {
372  if (R__b.IsReading()) {
373  VectorTypeWrapper<T> vw;
374  R__b.ReadClassBuffer(VectorTypeWrapper<T>::Class(), &vw);
375  for (auto ve : vw.vector_) {
376  this->push_back(ve);
377  }
378  } else {
379  VectorTypeWrapper<T> vw;
380  vw.vector_.resize(size_);
381  for (uint16_t i = 0; i < size_; i++) {
382  vw.vector_[i] = (*this)[i];
383  }
384  R__b.WriteClassBuffer(VectorTypeWrapper<T>::Class(), &vw);
385  }
386 }
387 
388 #endif // !defined(__CLING__) || defined(__ROOTCLING__)
389 
390 } // namespace bdm
391 
392 #endif // CORE_CONTAINER_INLINE_VECTOR_H_
bdm::InlineVector::Iterator::Iterator
Iterator(const Iterator &other)
Definition: inline_vector.h:57
bdm::InlineVector::Iterator::Iterator
Iterator(uint16_t index, TIV *iv)
Definition: inline_vector.h:56
bdm::InlineVector::Iterator::operator!=
bool operator!=(const Iterator &other) const
Definition: inline_vector.h:77
bdm::InlineVector::kGrowFactor
static constexpr float kGrowFactor
Definition: inline_vector.h:350
bdm::InlineVector::Iterator::operator+
Iterator operator+(const Iterator &rhs)
Definition: inline_vector.h:109
bdm
Definition: agent.cc:39
bdm::Behavior
Definition: behavior.h:29
bdm::Iterator
Definition: iterator.h:21
bdm::InlineVector::Iterator::operator+=
Iterator & operator+=(uint16_t i)
Definition: inline_vector.h:116
bdm::InlineVector::end
iterator end()
Definition: inline_vector.h:345
bdm::InlineVector::Iterator::operator-
Iterator operator-(uint16_t i)
Definition: inline_vector.h:145
bdm::InlineVector::clear
void clear()
Definition: inline_vector.h:191
bdm::InlineVector::Iterator::operator+=
Iterator & operator+=(const Iterator &rhs)
Definition: inline_vector.h:103
bdm::InlineVector::HeapSize
uint16_t HeapSize() const
Definition: inline_vector.h:356
bdm::InlineVector::operator[]
T & operator[](uint16_t index)
Definition: inline_vector.h:299
bdm::InlineVector::Iterator::operator=
Iterator & operator=(const Iterator &other)
Definition: inline_vector.h:62
bdm::InlineVector::Iterator::operator==
bool operator==(const Iterator &other) const
Definition: inline_vector.h:70
bdm::InlineVector::reserve
void reserve(uint16_t new_capacity)
Definition: inline_vector.h:202
bdm::InlineVector::InlineVector
InlineVector(InlineVector< T, N > &&other) noexcept
Definition: inline_vector.h:170
bdm::InlineVector::InlineVector
InlineVector(const InlineVector< T, N > &other)
Definition: inline_vector.h:160
bdm::InlineVector::operator=
InlineVector< T, N > & operator=(InlineVector< T, N > &&other) noexcept
Definition: inline_vector.h:287
bdm::InlineVector::end
const_iterator end() const
Definition: inline_vector.h:347
bdm::InlineVector::Iterator::operator*
TT & operator*() const
Definition: inline_vector.h:60
bdm::InlineVector::Iterator::index_
uint16_t index_
Definition: inline_vector.h:53
bdm::InlineVector::data_
std::array< T, N > data_
Definition: inline_vector.h:351
bdm::InlineVector::heap_capacity_
uint16_t heap_capacity_
Definition: inline_vector.h:353
bdm::InlineVector::operator=
InlineVector< T, N > & operator=(const InlineVector< T, N > &other)
Definition: inline_vector.h:269
bdm::InlineVector::size_
uint16_t size_
Definition: inline_vector.h:352
bdm::InlineVector::Iterator
Definition: inline_vector.h:52
bdm::InlineVector::size
uint16_t size() const
returns the number of elements in this container
Definition: inline_vector.h:215
root.h
bdm::InlineVector::Iterator::operator++
Iterator & operator++()
Definition: inline_vector.h:81
bdm::InlineVector::capacity
uint16_t capacity() const
Definition: inline_vector.h:187
bdm::InlineVector::Iterator::operator--
Iterator operator--(int)
Definition: inline_vector.h:97
bdm::Log::Fatal
static void Fatal(const std::string &location, const Args &... parts)
Prints fatal error message.
Definition: log.h:115
log.h
bdm::InlineVector::erase
iterator erase(const iterator &it)
Definition: inline_vector.h:240
bdm::InlineVector::Iterator::operator-=
Iterator & operator-=(const Iterator &rhs)
Definition: inline_vector.h:127
bdm::InlineVector< bdm::Behavior *, 3 >::iterator
typename InlineVector::template Iterator< bdm::Behavior *, InlineVector > iterator
Definition: inline_vector.h:153
io.h
bdm::InlineVector::~InlineVector
~InlineVector()
Definition: inline_vector.h:178
bdm::InlineVector::BDM_CLASS_DEF_NV
BDM_CLASS_DEF_NV(InlineVector, 2)
bdm::InlineVector::operator==
bool operator==(const InlineVector< T, N > &other) const
Definition: inline_vector.h:315
bdm::InlineVector::Iterator::operator--
Iterator & operator--()
Definition: inline_vector.h:92
bdm::InlineVector::push_back
void push_back(const T &element)
Definition: inline_vector.h:219
bdm::InlineVector::begin
iterator begin()
Definition: inline_vector.h:344
bdm::InlineVector::operator[]
const T & operator[](uint16_t index) const
Definition: inline_vector.h:307
bdm::InlineVector
Definition: inline_vector.h:49
bdm::InlineVector::InlineVector
InlineVector()=default
bdm::InlineVector::make_std_vector
std::vector< T > make_std_vector() const
Definition: inline_vector.h:261
bdm::InlineVector::Iterator::operator++
Iterator operator++(int)
Definition: inline_vector.h:86
bdm::InlineVector::Iterator::operator-
Iterator operator-(const Iterator &rhs)
Definition: inline_vector.h:133
bdm::InlineVector::Iterator::operator+
Iterator operator+(uint16_t i)
Definition: inline_vector.h:121
bdm::InlineVector::operator<<
friend std::ostream & operator<<(std::ostream &out, const InlineVector< T, N > &other)
Definition: inline_vector.h:336
bdm::InlineVector::begin
const_iterator begin() const
Definition: inline_vector.h:346
bdm::InlineVector< bdm::Behavior *, 3 >::const_iterator
typename InlineVector::template Iterator< const bdm::Behavior *, const InlineVector > const_iterator
Definition: inline_vector.h:155
bdm::InlineVector::heap_data_
T * heap_data_
Definition: inline_vector.h:354
bdm::InlineVector::Iterator::vector_
TIV * vector_
Definition: inline_vector.h:54
bdm::InlineVector::Iterator::operator-=
Iterator & operator-=(uint16_t i)
Definition: inline_vector.h:140
bdm::InlineVector::InlineVector
InlineVector(TRootIOCtor *io_ctor)
Definition: inline_vector.h:157