farray.h

Go to the documentation of this file.

#pragma once
#include "basetoqt.h"
 
template <typename T, uint64 S = 32>
class FArray {
public:
 using size_type = uint64; 
 using value_type = T; 
 using iterator = T *; 
 using const_iterator = const T *; 
 
 FArray() {}
 explicit FArray(size_type s, const T &t = T());
 template <uint64 S2> FArray(const FArray<T, S2> &f) { operator=(f); }
 FArray(const FArray<T, S> &f) { operator=(f); }
 FArray(std::initializer_list<T> l);
 ~FArray() { reset(); }
 const FArray<T,S> &operator=(const FArray<T,S> &f);
 template <uint64 S2> const FArray<T, S> &operator=(const FArray<T, S2> &f);
 template <uint64 S2> bool operator==(const FArray<T,S2> &f) const;
 
 // Accessors
 size_type size() const { return end_ - begin_; }
 size_type stackSize() const { return S; }
 size_type allocated() const { return capacity_ - begin_; }
 bool empty() const { return end_ == begin_; }
 T *data() { return begin_; }
 const T *data() const { return begin_; }
 T &front() { return *begin_; }
 const T &front() const { return *begin_; }
 T &back() { return *(end_ - 1); }
 const T &back() const { return *(end_ - 1); }
 size_type find(const T &t) const;
 size_type capacity() const { return capacity_ - begin_; }
 
 // Manipulators
 void push_back(const T &t) { checkAllocated(size() + 1); new(end_) T(t); ++end_; }
 T *emplace_back() { checkAllocated(size() + 1); return end_++; }
 T *emplace_n_back(uint64 n);
 void pop_back() { assert(size()); --end_; end_->~T(); }
 void resize(size_type i, const T &t = T());
 iterator insert(size_type i, const T &t);
 void put(size_type i, const T &t);
 template <class C> void append(const C &in);
 iterator insert(iterator it, const T &t);
 bool remove(size_type i);
 size_type removeAll(const T &t);
 void clear();
 void reset();
 void reserve(size_type s) { checkAllocated(s); }
 void clip() { if (size() * 2 < capacity() && size() > S) changeAllocated(size()); }
 
 // Member access functions
 iterator begin() { return begin_; }
 const_iterator begin() const { return begin_; }
 const_iterator constBegin() const { return begin_; }
 iterator end() { return end_; }
 const_iterator end() const { return end_; }
 const_iterator constEnd() const { return end_; }
 T &at(size_type i) { return begin_[i]; }
 const T &at(size_type i) const { return begin_[i]; }
 T &operator[](size_type i) { return at(i); }
 const T &operator[](size_type i) const { return at(i); }
 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); }
 T value(uint32 i, const T &t = T()) const { if (to<size_type>(i) >= size()) return t; return at(i); }
 T value(uint64 i, const T &t = T()) const { if (to<size_type>(i) >= size()) return t; return at(i); }
private:
 void checkAllocated(size_type target);
 void changeAllocated(size_type newSize);
 union { // Note: std::array<> used so you can see contents in debugger (which has been really irritating).
 T *start_; // Placed in this union so constructors don't get called on creation.
 std::array<T, S> arr_;
 char buffer[sizeof(T)*S];
 };
 T *begin_ = reinterpret_cast<T *>(buffer);
 T *end_ = begin_;
 T *capacity_ = begin_ + S;
};
 
template <class T>
class FArray<T, 0> : public std::vector<T> {
public:
 using std::vector<T>::vector;
};
 
 
 
// ---------------------------------------------------------------------------
// IMPLEMENTATIONS
// ---------------------------------------------------------------------------
 
template <typename T,uint64 S>
FArray<T,S>::FArray(size_type s,const T &t) {
 checkAllocated(s);
 end_ = begin_ + s;
 for (T *b = begin_; b < end_; ++b)
 new(b) T(t);
}
 
template <typename T,uint64 S>
FArray<T,S>::FArray(std::initializer_list<T> l) {
 for (auto it = l.begin(); it != l.end(); ++it)
 push_back(*it);
}
 
template <typename T,uint64 S>
const FArray<T, S> &FArray<T,S>::operator=(const FArray<T, S> &f) {
 return operator=<S>(f);
}
 
template <typename T,uint64 S>
template <uint64 S2>
bool FArray<T,S>::operator==(const FArray<T,S2> &f) const {
 if (size()!=f.size()) return false;
 for (uint64 i=0;i<size();++i) {
 if (operator[](i)!=f[i])
 return false;
 }
 return true;
}
 
template <typename T,uint64 S>
template <uint64 S2>
const FArray<T, S> &FArray<T,S>::operator=(const FArray<T, S2> &f) {
 clear();
 checkAllocated(f.size());
 end_ = begin_ + f.size();
 T *bl = begin_;
 for (auto br = f.begin(); bl < end(); ++bl, ++br)
 new(bl) T(*br);
 return *this;
}
 
template <typename T,uint64 S>
typename FArray<T,S>::size_type FArray<T,S>::find(const T &t) const {
 for (size_type i = 0; i < size(); ++i) {
 if (at(i) == t) return i;
 }
 return limits<size_type>::max();
}
 
template <typename T,uint64 S>
T *FArray<T,S>::emplace_n_back(uint64 n) {
 checkAllocated(size() + n);
 T *ret = end_;
 end_ += n;
 return ret;
}
 
template <typename T,uint64 S>
void FArray<T,S>::resize(size_type i, const T &t) {
 if (size() == i) return;
 if (size() > i) {
 T *e = end_;
 end_ = begin_ + i;
 for (T *p = e - 1; p >= end_; --p)
 p->~T();
 return;
 }
 size_type s = size();
 checkAllocated(i);
 end_ = begin_ + i;
 for (T *p = begin_ + s; p < end_; ++p)
 new(p) T(t);
}
 
template <typename T,uint64 S>
typename FArray<T,S>::iterator FArray<T,S>::insert(size_type i, const T &t) {
 i = std::min(size(), i);
 if (i + 1 > size()) push_back(t);
 else {
 push_back(back());
 for (iterator p = end_ - 2; p > begin_ + i; --p)
 *p = *(p - 1);
 *(begin_ + i) = t;
 }
 return begin_ + i;
}
 
template <typename T,uint64 S>
void FArray<T,S>::put(size_type i, const T &t) {
 if (size() <= i) {
 resize(i);
 push_back(t);
 } else
 at(i) = t;
}
 
template <typename T,uint64 S>
template <class C>
void FArray<T,S>::append(const C &in) {
 for (auto i = in.begin(); i != in.end(); ++i)
 push_back(*i);
}
 
template <typename T,uint64 S>
typename FArray<T,S>::iterator FArray<T,S>::insert(iterator it, const T &t) {
 size_type i = it - begin_;
 i = std::min(size(), i);
 if (i + 1 > size()) push_back(t);
 else {
 push_back(back());
 for (iterator p = end_ - 2; p > begin_ + i; --p)
 *p = *(p - 1);
 *(begin_ + i) = t;
 }
 return begin_ + i;
}
 
template <typename T,uint64 S>
bool FArray<T,S>::remove(size_type i) {
 if (i >= size()) return false;
 for (iterator it = begin_ + i; it + 1 < end_; ++it)
 *it = *(it + 1);
 pop_back();
 return true;
}
 
template <typename T,uint64 S>
typename FArray<T,S>::size_type FArray<T,S>::removeAll(const T &t) {
 size_type ret = 0;
 for (size_type i = 0; i < size();) {
 if (t == at(i)) {
 remove(i);
 ++ret;
 } else
 ++i;
 }
 return ret;
}
 
template <typename T,uint64 S>
void FArray<T,S>::clear() {
 // if type T is not plain old data, call the destructor for each array element;
 if (!std::is_trivially_copyable<T>::value)
 for (T *b = begin_; b < end_; ++b)
 b->~T();
 end_ = begin_;
}
 
template <typename T,uint64 S>
void FArray<T,S>::reset() {
 clear();
 if (begin_ != reinterpret_cast<T *>(arr_.data()))
 ::free(begin_);
 end_ = begin_ = reinterpret_cast<T *>(arr_.data());
 capacity_ = begin_ + S;
}
 
template <typename T,uint64 S>
void FArray<T,S>::checkAllocated(size_type target) {
 static constexpr size_type max_increase = 1024*1000;
 if (begin_+target <= capacity_) return;
 size_type newsize = std::max<size_type>(capacity(), 4) * 2;
 while (newsize < target)
 newsize += to<size_type>(std::min(max_increase, newsize));
 changeAllocated(newsize);
}
 
template <typename T,uint64 S>
void FArray<T,S>::changeAllocated(size_type newSize) {
 size_type old_size = size();
 assert(old_size <= newSize);
 T *newBegin = reinterpret_cast<T *>(arr_.data());
 if (newSize > S)
#ifdef ITASCA_MEMORY_CHECKING
 newBegin = reinterpret_cast<T *>(itasca::memory::imalloc(newSize * sizeof(T), __FILE__, __LINE__));
#else
 newBegin = reinterpret_cast<T *>(std::malloc(newSize * sizeof(T)));
#endif
 T *tl = newBegin;
 for (T *tr = begin_; tr < end_; ++tl, ++tr) {
 new(tl) T(std::move(*tr));
 tr->~T();
 }
 if (begin_ != reinterpret_cast<T *>(arr_.data()))
 std::free(begin_);
 begin_ = newBegin;
 end_ = begin_ + old_size;
 capacity_ = begin_ + newSize;
}
// EoF