farray.h

Go to the documentation of this file.

#pragma once
#include "base.h"
 
template <typename T, uint64 S = 32,typename I=uint64>
class FArray {
public:
    using size_type = uint64;          
    using value_type = T;              
    using iterator = T *;              
    using const_iterator = const T *;  
 
    constexpr FArray() {}
    explicit FArray(size_type s, const T &t = T());
    template <uint64 S2> FArray(const FArray<T, S2,I> &f) { operator=(f); }
    constexpr FArray(const FArray<T, S,I> &f)  { operator=(f); }
    FArray(std::initializer_list<T> l);
    ~FArray() { reset(); }
    constexpr const FArray<T,S,I> &operator=(const FArray<T,S,I> &f);
    template <uint64 S2> constexpr const FArray<T,S,I> &operator=(const FArray<T, S2,I> &f);
    template <uint64 S2> bool operator==(const FArray<T,S2,I> &f) const;
 
    // Accessors
    I 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); }
    I 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(size_type n);
    void pop_back() { assert(size()); --end_; end_->~T(); }
    void resize(I i, const T &t = T());
    iterator insert(I i, const T &t);
    void put(I i, const T &t);
    template <class C> void append(const C &in);
    iterator insert(iterator it, const T &t);
    bool remove(I 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(I i) { assert(i<size()); return begin_[static_cast<size_type>(i)]; }
    const T &at(I i) const { assert(i<size()); return begin_[static_cast<size_type>(i)]; }
    T &operator[](I i) { return at(i); }
    const T &operator[](I i) const { return at(i); }
    T              value(I i, const T &t = {}) const { if (to<size_type>(i) >= size()) return t;  return at(i); }
    //T              value(uint32 i, const T &t = {}) const { if (to<size_type>(i) >= size()) return t;  return at(i); }
    //T              value(uint64 i, const 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,typename I>
FArray<T,S,I>::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,typename I>
FArray<T,S,I>::FArray(std::initializer_list<T> l) {
    for (auto it = l.begin(); it != l.end(); ++it)
        push_back(*it);
}
 
template <typename T,uint64 S,typename I>
constexpr const FArray<T, S,I> &FArray<T,S,I>::operator=(const FArray<T, S,I> &f) {
    return operator=<S>(f);
}
 
template <typename T,uint64 S,typename I>
template <uint64 S2>
bool FArray<T,S,I>::operator==(const FArray<T,S2,I> &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,typename I>
template <uint64 S2>
constexpr const FArray<T, S,I> &FArray<T,S,I>::operator=(const FArray<T, S2,I> &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 I>
I FArray<T,S,I>::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,typename I>
T *FArray<T,S,I>::emplace_n_back(size_type n) {
    checkAllocated(size() + n);
    T *ret = end_;
    end_ += n;
    return ret;
}
 
template <typename T,uint64 S,typename I>
void FArray<T,S,I>::resize(I i, const T &t) {
    if (size() == static_cast<uint64>(i)) return;
    if (size() > static_cast<uint64>(i)) {
        T *e = end_;
        end_ = begin_ + static_cast<uint64>(i);
        for (T *p = e - 1; p >= end_; --p)
            p->~T();
        return;
    }
    size_type s = size();
    checkAllocated(i);
    end_ = begin_ + static_cast<uint64>(i);
    for (T *p = begin_ + s; p < end_; ++p)
        new(p) T(t);
}
 
template <typename T,uint64 S,typename I>
typename FArray<T,S,I>::iterator FArray<T,S,I>::insert(I 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,typename I>
void FArray<T,S,I>::put(I i, const T &t) {
    if (size() <= i) {
        resize(i);
        push_back(t);
    } else
        at(i) = t;
}
 
template <typename T,uint64 S,typename I>
template <class C>
void FArray<T,S,I>::append(const C &in) {
    for (auto i = in.begin(); i != in.end(); ++i)
        push_back(*i);
}
 
template  <typename T,uint64 S,typename I>
typename FArray<T,S,I>::iterator FArray<T,S,I>::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,typename I>
bool FArray<T,S,I>::remove(I 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 I>
typename FArray<T,S,I>::size_type FArray<T,S,I>::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,typename I>
void FArray<T,S,I>::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,typename I>
void FArray<T,S,I>::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,typename I>
void FArray<T,S,I>::checkAllocated(size_type target) {
    static constexpr uint64 max_increase = 1024*1000;
    if (begin_+target <= capacity_) return;
    uint64 newsize = std::max<uint64>(capacity(), 4) * 2;
    while (newsize < target)
        newsize += to<size_type>(std::min(max_increase, newsize));
    changeAllocated(newsize);
}
 
template <typename T,uint64 S,typename I>
void FArray<T,S,I>::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