Itasca C++ Interface
farray.h
Go to the documentation of this file.
1 #pragma once
22 #include "basetoqt.h"
23 
24 template <typename T, uint64 S = 32>
25 class FArray {
26 public:
27  using size_type = uint64;
28  using value_type = T;
29  using iterator = T *;
30  using const_iterator = const T *;
31 
33  FArray() {}
38  explicit FArray(size_type s, const T &t = T());
40  template <uint64 S2> FArray(const FArray<T, S2> &f) { operator=(f); }
42  FArray(const FArray<T, S> &f) { operator=(f); }
43  FArray(std::initializer_list<T> l);
45  ~FArray() { reset(); }
46  const FArray<T,S> &operator=(const FArray<T,S> &f);
48  template <uint64 S2> const FArray<T, S> &operator=(const FArray<T, S2> &f);
49  template <uint64 S2> bool operator==(const FArray<T,S2> &f) const;
50 
51  // Accessors
53  size_type size() const { return size_; }
55  size_type stackSize() const { return S; }
58  size_type allocated() const { return allocated_; }
60  bool empty() const { return end_ == begin_; }
63  T *data() { return begin_; }
66  const T *data() const { return begin_; }
68  T &front() { return *begin_; }
70  const T &front() const { return *begin_; }
72  T &back() { return *(end_ - 1); }
74  const T &back() const { return *(end_ - 1); }
78  size_type find(const T &t) const;
79 
80  // Manipulators
82  void push_back(const T &t) { checkAllocated(size() + 1); new(end_) T(t); ++end_; ++size_; }
86  T *emplace_back() { checkAllocated(size() + 1); ++size_; return end_++; }
89  T *emplace_n_back(uint64 n);
91  void pop_back() { assert(size()); --end_; end_->~T(); --size_; }
96  void resize(size_type i, const T &t = T());
99  iterator insert(size_type i, const T &t);
101  void put(size_type i, const T &t);
103  template <class C> void append(const C &in);
106  iterator insert(iterator it, const T &t);
109  bool remove(size_type i);
112  size_type removeAll(const T &t);
115  void clear();
119  void reset();
123  void clip() { if (size() * 2 < allocated_ && size() > S) changeAllocated(size()); }
124 
125  // Member access functions
128  iterator begin() { return begin_; }
131  const_iterator begin() const { return begin_; }
134  const_iterator constBegin() const { return begin_; }
137  iterator end() { return end_; }
140  const_iterator end() const { return end_; }
143  const_iterator constEnd() const { return end_; }
147  T &at(size_type i) { return begin_[i]; }
151  const T &at(size_type i) const { return begin_[i]; }
155  T &operator[](size_type i) { return at(i); }
159  const T &operator[](size_type i) const { return at(i); }
163  T value(int i, const T &t = T()) const { if (i < 0) return t; if (to<size_type>(i) >= size()) return t; return at(i); }
167  T value(uint32 i, const T &t = T()) const { if (to<size_type>(i) >= size()) return t; return at(i); }
171  T value(uint64 i, const T &t = T()) const { if (to<size_type>(i) >= size()) return t; return at(i); }
172 private:
173  void checkAllocated(size_type target);
174  void changeAllocated(size_type newSize);
175  union { // Note: std::array<> used so you can see contents in debugger (which has been really irritating).
176  T *start_; // Placed in this union so constructors don't get called on creation.
177  std::array<T, S> arr_;
178  char buffer[sizeof(T)*S];
179  };
180  T *begin_ = reinterpret_cast<T *>(buffer);
181  T *end_ = begin_;
182  size_type allocated_ = S;
183  size_type size_ = 0;
184 };
185 
189 template <class T>
190 class FArray<T, 0> : public std::vector<T> {
191 public:
192  using std::vector<T>::vector;
193 };
194 
195 
196 
197 // ---------------------------------------------------------------------------
198 // IMPLEMENTATIONS
199 // ---------------------------------------------------------------------------
200 
201 template <typename T,uint64 S>
203  checkAllocated(s);
204  end_ = begin_ + s;
205  for (T *b = begin_; b < end_; ++b)
206  new(b) T(t);
207  size_ = s;
208 }
209 
210 template <typename T,uint64 S>
211 FArray<T,S>::FArray(std::initializer_list<T> l) {
212  for (auto it = l.begin(); it != l.end(); ++it)
213  push_back(*it);
214 }
215 
216 template <typename T,uint64 S>
218  return operator=<S>(f);
219  //clear();
220  //checkAllocated(f.size());
221  //end_ = begin_ + f.size();
222  //size_ = f.size();
223  //T *bl = begin_;
224  //for (auto br = f.begin(); bl < end(); ++bl, ++br)
225  // new(bl) T(*br);
226  //return *this;
227 }
228 
229 template <typename T,uint64 S>
230 template <uint64 S2>
231 bool FArray<T,S>::operator==(const FArray<T,S2> &f) const {
232  if (size()!=f.size()) return false;
233  for (uint64 i=0;i<size();++i) {
234  if (operator[](i)!=f[i])
235  return false;
236  }
237  return true;
238 }
239 
240 template <typename T,uint64 S>
241 template <uint64 S2>
243  clear();
244  checkAllocated(f.size());
245  end_ = begin_ + f.size();
246  size_ = f.size();
247  T *bl = begin_;
248  for (auto br = f.begin(); bl < end(); ++bl, ++br)
249  new(bl) T(*br);
250  return *this;
251 }
252 
253 template <typename T,uint64 S>
254 typename FArray<T,S>::size_type FArray<T,S>::find(const T &t) const {
255  for (size_type i = 0; i < size(); ++i) {
256  if (at(i) == t) return i;
257  }
258  return limits<size_type>::max();
259 }
260 
261 template <typename T,uint64 S>
263  checkAllocated(size() + n);
264  T *ret = end_;
265  end_ += n;
266  size_ += n;
267  return ret;
268 }
269 
270 template <typename T,uint64 S>
271 void FArray<T,S>::resize(size_type i, const T &t) {
272  if (size() == i) return;
273  if (size() > i) {
274  T *e = end_;
275  end_ = begin_ + i;
276  for (T *p = e - 1; p >= end_; --p)
277  p->~T();
278  size_ = i;
279  return;
280  }
281  size_type s = size();
282  checkAllocated(i);
283  end_ = begin_ + i;
284  size_ = i;
285  for (T *p = begin_ + s; p < end_; ++p)
286  new(p) T(t);
287 }
288 
289 template <typename T,uint64 S>
291  i = std::min(size(), i);
292  if (i + 1 > size()) push_back(t);
293  else {
294  push_back(back());
295  for (iterator p = end_ - 2; p > begin_ + i; --p)
296  *p = *(p - 1);
297  *(begin_ + i) = t;
298  }
299  return begin_ + i;
300 }
301 
302 template <typename T,uint64 S>
303 void FArray<T,S>::put(size_type i, const T &t) {
304  if (size() <= i) {
305  resize(i);
306  push_back(t);
307  } else
308  at(i) = t;
309 }
310 
311 template <typename T,uint64 S>
312 template <class C>
313 void FArray<T,S>::append(const C &in) {
314  for (auto i = in.begin(); i != in.end(); ++i)
315  push_back(*i);
316 }
317 
318 template <typename T,uint64 S>
320  size_type i = it - begin_;
321  i = std::min(size(), i);
322  if (i + 1 > size()) push_back(t);
323  else {
324  push_back(back());
325  for (iterator p = end_ - 2; p > begin_ + i; --p)
326  *p = *(p - 1);
327  *(begin_ + i) = t;
328  }
329  return begin_ + i;
330 }
331 
332 template <typename T,uint64 S>
334  if (i >= size()) return false;
335  for (iterator it = begin_ + i; it + 1 < end_; ++it)
336  *it = *(it + 1);
337  pop_back();
338  return true;
339 }
340 
341 template <typename T,uint64 S>
343  size_type ret = 0;
344  for (size_type i = 0; i < size();) {
345  if (t == at(i)) {
346  remove(i);
347  ++ret;
348  } else
349  ++i;
350  }
351  return ret;
352 }
353 
354 template <typename T,uint64 S>
356  // if type T is not plain old data, call the destructor for each array element;
357  if (!std::is_trivially_copyable<T>::value)
358  for (T *b = begin_; b < end_; ++b)
359  b->~T();
360  end_ = begin_;
361  size_ = 0;
362 }
363 
364 template <typename T,uint64 S>
366  clear();
367  if (begin_ != reinterpret_cast<T *>(arr_.data()))
368  ::free(begin_);
369  end_ = begin_ = reinterpret_cast<T *>(arr_.data());
370  allocated_ = S;
371 }
372 
373 template <typename T,uint64 S>
374 void FArray<T,S>::checkAllocated(size_type target) {
375  static const size_type max_increase = 1000000;
376  if (target <= allocated_) return;
377  size_type newsize = std::max<size_type>(allocated_, 8);
378  while (newsize < target)
379  newsize += to<size_type>(std::min(max_increase, newsize));
380  changeAllocated(newsize);
381 }
382 
383 template <typename T,uint64 S>
384 void FArray<T,S>::changeAllocated(size_type newSize) {
385  size_type old_size = size();
386  assert(old_size <= newSize);
387  T *newBegin = reinterpret_cast<T *>(arr_.data());
388  if (newSize > S)
389 #ifdef _DEBUG
390  newBegin = reinterpret_cast<T *>(itasca::memory::imalloc(newSize * sizeof(T), __FILE__, __LINE__));
391 #else
392  newBegin = reinterpret_cast<T *>(std::malloc(newSize * sizeof(T)));
393 #endif
394  T *tl = newBegin;
395  for (T *tr = begin_; tr < end_; ++tl, ++tr) {
396  new(tl) T(std::move(*tr));
397  tr->~T();
398  }
399  if (begin_ != reinterpret_cast<T *>(arr_.data()))
400  std::free(begin_);
401  begin_ = newBegin;
402  end_ = begin_ + old_size;
403  allocated_ = newSize;
404 }
406 // EoF
Combines base interface with Qt – allows Qt to interact with other Base types transparently.
An array class that attempts to minimize unnecessary heap access.
Definition: farray.h:25
T * data()
Definition: farray.h:63
void push_back(const T &t)
Adds a new element to the end of the array, increasing the array size by one.
Definition: farray.h:82
bool empty() const
Definition: farray.h:60
size_type stackSize() const
Returns the size of the array pre-allocated on the stack.
Definition: farray.h:55
const T & back() const
Definition: farray.h:74
T value_type
Typedef to assist in STL compatibility.
Definition: farray.h:28
FArray()
Default constructor - the array size is zero.
Definition: farray.h:33
T & back()
Definition: farray.h:72
iterator begin()
Definition: farray.h:128
T & operator[](size_type i)
Definition: farray.h:155
T & front()
Definition: farray.h:68
FArray(const FArray< T, S2 > &f)
Copy constructor, valid for FArrays of the same data type but different stack lengths.
Definition: farray.h:40
const_iterator constEnd() const
Definition: farray.h:143
uint64 size_type
Typedef to assist in STL compatibility.
Definition: farray.h:27
const T & front() const
Definition: farray.h:70
void clip()
Definition: farray.h:123
T value(uint64 i, const T &t=T()) const
Definition: farray.h:171
const_iterator begin() const
Definition: farray.h:131
FArray(const FArray< T, S > &f)
Specialized copy constructor, for the special case of when the stack lengths are the same.
Definition: farray.h:42
const T * data() const
Definition: farray.h:66
~FArray()
Destructor.
Definition: farray.h:45
const T & operator[](size_type i) const
Definition: farray.h:159
const_iterator end() const
Definition: farray.h:140
size_type allocated() const
Definition: farray.h:58
iterator end()
Definition: farray.h:137
void pop_back()
Removes the last element in the array. The results are undefined if the array is of zero length.
Definition: farray.h:91
T value(int i, const T &t=T()) const
Definition: farray.h:163
T value(uint32 i, const T &t=T()) const
Definition: farray.h:167
const_iterator constBegin() const
Definition: farray.h:134
const T & at(size_type i) const
Definition: farray.h:151
T * iterator
Typedef to assist in STL compatibility.
Definition: farray.h:29
size_type size() const
Definition: farray.h:53
const T * const_iterator
Typedef to assist in STL compatibility.
Definition: farray.h:30
T * emplace_back()
Definition: farray.h:86
T & at(size_type i)
Definition: farray.h:147
debug checked shorthand for std::numeric_limits<T>::
Definition: limit.h:25
bool remove(size_type i)
Definition: farray.h:333
iterator insert(iterator it, const T &t)
Definition: farray.h:319
const FArray< T, S > & operator=(const FArray< T, S2 > &f)
Assignment operator, valid for FArrays of the same data type but different stack lengths.
Definition: farray.h:242
iterator insert(size_type i, const T &t)
Definition: farray.h:290
void resize(size_type i, const T &t=T())
Definition: farray.h:271
void append(const C &in)
Appends the contents of one FArray onto another.
Definition: farray.h:313
size_type find(const T &t) const
Definition: farray.h:254
void reset()
Definition: farray.h:365
void clear()
Definition: farray.h:355
void put(size_type i, const T &t)
Adds a value to the array, first making certain it is big enough to hold it.
Definition: farray.h:303
FArray(size_type s, const T &t=T())
Definition: farray.h:202
size_type removeAll(const T &t)
Definition: farray.h:342
T * emplace_n_back(uint64 n)
Definition: farray.h:262