Itasca C++ Interface
Loading...
Searching...
No Matches
farray.h
Go to the documentation of this file.
1#pragma once
22#include "basetoqt.h"
23
24template <typename T, uint64 S = 32>
25class FArray {
26public:
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 end_ - begin_; }
55 size_type stackSize() const { return S; }
58 size_type allocated() const { return capacity_ - begin_; }
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 size_type capacity() const { return capacity_ - begin_; }
80
81 // Manipulators
83 void push_back(const T &t) { checkAllocated(size() + 1); new(end_) T(t); ++end_; }
87 T *emplace_back() { checkAllocated(size() + 1); return end_++; }
90 T *emplace_n_back(uint64 n);
92 void pop_back() { assert(size()); --end_; end_->~T(); }
97 void resize(size_type i, const T &t = T());
100 iterator insert(size_type i, const T &t);
102 void put(size_type i, const T &t);
104 template <class C> void append(const C &in);
107 iterator insert(iterator it, const T &t);
113 size_type removeAll(const T &t);
116 void clear();
120 void reset();
124 void clip() { if (size() * 2 < capacity() && size() > S) changeAllocated(size()); }
125
126 // Member access functions
129 iterator begin() { return begin_; }
132 const_iterator begin() const { return begin_; }
135 const_iterator constBegin() const { return begin_; }
138 iterator end() { return end_; }
141 const_iterator end() const { return end_; }
144 const_iterator constEnd() const { return end_; }
148 T &at(size_type i) { return begin_[i]; }
152 const T &at(size_type i) const { return begin_[i]; }
156 T &operator[](size_type i) { return at(i); }
160 const T &operator[](size_type i) const { return at(i); }
164 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); }
168 T value(uint32 i, const T &t = T()) const { if (to<size_type>(i) >= size()) return t; return at(i); }
172 T value(uint64 i, const T &t = T()) const { if (to<size_type>(i) >= size()) return t; return at(i); }
173private:
174 void checkAllocated(size_type target);
175 void changeAllocated(size_type newSize);
176 union { // Note: std::array<> used so you can see contents in debugger (which has been really irritating).
177 T *start_; // Placed in this union so constructors don't get called on creation.
178 std::array<T, S> arr_;
179 char buffer[sizeof(T)*S];
180 };
181 T *begin_ = reinterpret_cast<T *>(buffer);
182 T *end_ = begin_;
183 T *capacity_ = begin_ + S;
184};
185
189template <class T>
190class FArray<T, 0> : public std::vector<T> {
191public:
192 using std::vector<T>::vector;
193};
194
195
196
197// ---------------------------------------------------------------------------
198// IMPLEMENTATIONS
199// ---------------------------------------------------------------------------
200
201template <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}
208
209template <typename T,uint64 S>
210FArray<T,S>::FArray(std::initializer_list<T> l) {
211 for (auto it = l.begin(); it != l.end(); ++it)
212 push_back(*it);
213}
214
215template <typename T,uint64 S>
217 return operator=<S>(f);
218}
219
220template <typename T,uint64 S>
221template <uint64 S2>
222bool FArray<T,S>::operator==(const FArray<T,S2> &f) const {
223 if (size()!=f.size()) return false;
224 for (uint64 i=0;i<size();++i) {
225 if (operator[](i)!=f[i])
226 return false;
227 }
228 return true;
229}
230
231template <typename T,uint64 S>
232template <uint64 S2>
234 clear();
235 checkAllocated(f.size());
236 end_ = begin_ + f.size();
237 T *bl = begin_;
238 for (auto br = f.begin(); bl < end(); ++bl, ++br)
239 new(bl) T(*br);
240 return *this;
241}
242
243template <typename T,uint64 S>
244typename FArray<T,S>::size_type FArray<T,S>::find(const T &t) const {
245 for (size_type i = 0; i < size(); ++i) {
246 if (at(i) == t) return i;
247 }
248 return limits<size_type>::max();
249}
250
251template <typename T,uint64 S>
253 checkAllocated(size() + n);
254 T *ret = end_;
255 end_ += n;
256 return ret;
257}
258
259template <typename T,uint64 S>
260void FArray<T,S>::resize(size_type i, const T &t) {
261 if (size() == i) return;
262 if (size() > i) {
263 T *e = end_;
264 end_ = begin_ + i;
265 for (T *p = e - 1; p >= end_; --p)
266 p->~T();
267 return;
268 }
269 size_type s = size();
270 checkAllocated(i);
271 end_ = begin_ + i;
272 for (T *p = begin_ + s; p < end_; ++p)
273 new(p) T(t);
274}
275
276template <typename T,uint64 S>
278 i = std::min(size(), i);
279 if (i + 1 > size()) push_back(t);
280 else {
281 push_back(back());
282 for (iterator p = end_ - 2; p > begin_ + i; --p)
283 *p = *(p - 1);
284 *(begin_ + i) = t;
285 }
286 return begin_ + i;
287}
288
289template <typename T,uint64 S>
290void FArray<T,S>::put(size_type i, const T &t) {
291 if (size() <= i) {
292 resize(i);
293 push_back(t);
294 } else
295 at(i) = t;
296}
297
298template <typename T,uint64 S>
299template <class C>
300void FArray<T,S>::append(const C &in) {
301 for (auto i = in.begin(); i != in.end(); ++i)
302 push_back(*i);
303}
304
305template <typename T,uint64 S>
307 size_type i = it - begin_;
308 i = std::min(size(), i);
309 if (i + 1 > size()) push_back(t);
310 else {
311 push_back(back());
312 for (iterator p = end_ - 2; p > begin_ + i; --p)
313 *p = *(p - 1);
314 *(begin_ + i) = t;
315 }
316 return begin_ + i;
317}
318
319template <typename T,uint64 S>
321 if (i >= size()) return false;
322 for (iterator it = begin_ + i; it + 1 < end_; ++it)
323 *it = *(it + 1);
324 pop_back();
325 return true;
326}
327
328template <typename T,uint64 S>
330 size_type ret = 0;
331 for (size_type i = 0; i < size();) {
332 if (t == at(i)) {
333 remove(i);
334 ++ret;
335 } else
336 ++i;
337 }
338 return ret;
339}
340
341template <typename T,uint64 S>
343 // if type T is not plain old data, call the destructor for each array element;
344 if (!std::is_trivially_copyable<T>::value)
345 for (T *b = begin_; b < end_; ++b)
346 b->~T();
347 end_ = begin_;
348}
349
350template <typename T,uint64 S>
352 clear();
353 if (begin_ != reinterpret_cast<T *>(arr_.data()))
354 ::free(begin_);
355 end_ = begin_ = reinterpret_cast<T *>(arr_.data());
356 capacity_ = begin_ + S;
357}
358
359template <typename T,uint64 S>
360void FArray<T,S>::checkAllocated(size_type target) {
361 static constexpr size_type max_increase = 1024*1000;
362 if (begin_+target <= capacity_) return;
363 size_type newsize = std::max<size_type>(capacity(), 4) * 2;
364 while (newsize < target)
365 newsize += to<size_type>(std::min(max_increase, newsize));
366 changeAllocated(newsize);
367}
368
369template <typename T,uint64 S>
370void FArray<T,S>::changeAllocated(size_type newSize) {
371 size_type old_size = size();
372 assert(old_size <= newSize);
373 T *newBegin = reinterpret_cast<T *>(arr_.data());
374 if (newSize > S)
375#ifdef _DEBUG
376 newBegin = reinterpret_cast<T *>(itasca::memory::imalloc(newSize * sizeof(T), __FILE__, __LINE__));
377#else
378 newBegin = reinterpret_cast<T *>(std::malloc(newSize * sizeof(T)));
379#endif
380 T *tl = newBegin;
381 for (T *tr = begin_; tr < end_; ++tl, ++tr) {
382 new(tl) T(std::move(*tr));
383 tr->~T();
384 }
385 if (begin_ != reinterpret_cast<T *>(arr_.data()))
386 std::free(begin_);
387 begin_ = newBegin;
388 end_ = begin_ + old_size;
389 capacity_ = begin_ + newSize;
390}
392// 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 & front()
Definition farray.h:68
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:83
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
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 & operator[](size_type i)
Definition farray.h:156
iterator begin()
Definition farray.h:129
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:144
uint64 size_type
Typedef to assist in STL compatibility.
Definition farray.h:27
void clip()
Definition farray.h:124
const T & front() const
Definition farray.h:70
T value(uint64 i, const T &t=T()) const
Definition farray.h:172
T * emplace_back()
Definition farray.h:87
const_iterator begin() const
Definition farray.h:132
const T & operator[](size_type i) const
Definition farray.h:160
T & at(size_type i)
Definition farray.h:148
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 & back() const
Definition farray.h:74
~FArray()
Destructor.
Definition farray.h:45
const_iterator end() const
Definition farray.h:141
size_type allocated() const
Definition farray.h:58
iterator end()
Definition farray.h:138
void pop_back()
Removes the last element in the array. The results are undefined if the array is of zero length.
Definition farray.h:92
T value(int i, const T &t=T()) const
Definition farray.h:164
T value(uint32 i, const T &t=T()) const
Definition farray.h:168
const_iterator constBegin() const
Definition farray.h:135
T * data()
Definition farray.h:63
T * iterator
Typedef to assist in STL compatibility.
Definition farray.h:29
size_type size() const
Definition farray.h:53
T & back()
Definition farray.h:72
const T * const_iterator
Typedef to assist in STL compatibility.
Definition farray.h:30
const T & at(size_type i) const
Definition farray.h:152
const T * data() const
Definition farray.h:66
debug checked shorthand for std::numeric_limits<T>::
Definition limit.h:25
bool remove(size_type i)
Definition farray.h:320
iterator insert(iterator it, const T &t)
Definition farray.h:306
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:233
iterator insert(size_type i, const T &t)
Definition farray.h:277
void resize(size_type i, const T &t=T())
Definition farray.h:260
void append(const C &in)
Appends the contents of one FArray onto another.
Definition farray.h:300
size_type find(const T &t) const
Definition farray.h:244
void reset()
Definition farray.h:351
void clear()
Definition farray.h:342
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:290
FArray(size_type s, const T &t=T())
Definition farray.h:202
size_type removeAll(const T &t)
Definition farray.h:329
T * emplace_n_back(uint64 n)
Definition farray.h:252