farray.h

Go to the documentation of this file.

#pragma once

//#pragma warning(disable:4244)
//#pragma warning(disable:4267)
#ifdef __LINUX
#include "basetoqt.h"
#endif
template <class T,uint64 S=32> class FArray {
public:
    using size_type = uint64;          
    using value_type = T;              
    using iterator = T *;              
    using const_iterator = const T *;  

    FArray() : begin_(reinterpret_cast<T *>(arr_.data())), end_(begin_), allocated_(S), size_(0) { }
    explicit FArray(size_type s,const T &t=T()) : begin_(reinterpret_cast<T *>(arr_.data())), end_(begin_), allocated_(S), size_(0) { checkAllocated(s); end_ = begin_ + s; for (T *b=begin_;b<end_;++b) new(b) T(t); size_ = s; }
    template <uint64 S2> FArray(const FArray<T,S2> &f) : begin_(reinterpret_cast<T *>(arr_.data())), end_(begin_), allocated_(S), size_(0) { operator=(f); }
    FArray(const FArray<T,S> &f) : begin_(reinterpret_cast<T *>(arr_.data())), end_(begin_), allocated_(S), size_(0) { operator=(f); }
    FArray(std::initializer_list<T> l) : begin_(reinterpret_cast<T *>(arr_.data())), end_(begin_), allocated_(S), size_(0) { 
        for (auto it=l.begin();it!=l.end();++it)
            push_back(*it);
    }
    ~FArray() { reset(); }
    template <uint64 S2> const FArray<T,S> &operator=(const FArray<T,S2> &f) { 
        clear(); 
        checkAllocated(f.size());
        end_ = begin_ + f.size(); 
        size_ = f.size();
        T *bl = begin_;
        for (auto br=f.begin();bl<end();++bl,++br) 
            new(bl) T(*br); 
        return *this; 
    }
    const FArray<T,S> &operator=(const FArray<T,S> &f) {
        clear();
        checkAllocated(f.size());
        end_ = begin_ + f.size();
        size_ = f.size_;
        T *bl=begin_;
        for (T *br=f.begin_;bl<end_;++bl,++br) 
            new(bl) T(*br); 
        return *this; 
    }

    // Accessors
    size_type size() const { return size_; }
    size_type stackSize() const { return S; }
    size_type allocated() const { return allocated_; }
    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 {
        for (size_type i=0;i<size();++i) {
            if (at(i)==t) return i;
        }
        return limits<size_type>::max();
    }

    // Manipulators
    void push_back(const T &t) { checkAllocated(size()+1); new(end_) T(t); ++end_; ++size_; }
    T *emplace_back() { checkAllocated(size()+1); ++size_; return end_++; }    
    T *emplace_n_back(uint64 n) { checkAllocated(size() + n);  T *ret = end_; end_ += n;  size_ += n;  return ret; }
    void pop_back() { assert(size()); --end_; end_->~T(); --size_; }
    void resize(size_type i,const T &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();
            size_ = i;
            return;
        }
        size_type s = size();
        checkAllocated(i); 
        end_ = begin_ + i; 
        size_ = i;
        for (T *p=begin_+s;p<end_;++p)
            new(p) T(t);
    }
    iterator 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;
    }
    void put(size_type i,const T &t) {
        if (size()<=i) {
            resize(i);
            push_back(t);
        } else
            at(i) = t;
    }
    template <class C> void append(const C &in) { for (auto i=in.begin();i!=in.end();++i) push_back(*i); }
    iterator 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;
    }
    bool 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;
    }
    size_type 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;
    }
        void clear() {
        // if type T is not plain old data, call the destructor for each array element;
        // std::is_pod is deprecated in C++20; can be replaced with is_integral, is_floating_point etc.
        if (!std::is_pod<T>::value)
            for (T *b=begin_;b<end_;++b) 
                b->~T();
        end_ = begin_; 
        size_ = 0; 
        }
    void clear_no_destruct() { end_ = begin_; size_ = 0; }
    void reset() { 
        clear(); 
        if (begin_!=reinterpret_cast<T *>(arr_.data())) 
            ::free(begin_); 
        end_ = begin_ = reinterpret_cast<T *>(arr_.data()); 
        allocated_ = S; 
    }
    void clip() { if (size()*2<allocated_ && 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(quint32 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) {
        static const size_type max_increase = 1000000;
        if (target<=allocated_) return;
        size_type newsize = std::max<size_type>(allocated_,8);
        while (newsize<target)
            newsize += to<size_type>(std::min(max_increase,newsize));
        changeAllocated(newsize);
    }
    void changeAllocated(size_type newSize) {
        size_type old_size = size();
        assert(old_size<=newSize);
        T *newBegin = reinterpret_cast<T *>(arr_.data());
        if (newSize>S)
#ifdef _DEBUG
            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(*tr);
            tr->~T();
        }
        if (begin_!=reinterpret_cast<T *>(arr_.data())) 
            std::free(begin_);
        begin_ = newBegin;
        end_ = begin_ + old_size;
        allocated_ = 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_;
    };
    T* begin_ = arr_.data();
    T* end_ = &begin_;
    size_type allocated_ = S;
    size_type size_ = 0;
};
template <class T> class FArray<T,0> {
public:
    using size_type = uint64;     
    using iterator = T *;        
    using const_iterator = const T *;  
    using value_type = T;

    FArray() : begin_(0), end_(0), allocated_(0), size_(0) { }
    FArray(size_type s,const T &t=T()) : begin_(0), end_(begin_), allocated_(0), size_(0) { checkAllocated(s); end_ = begin_ + s; for (T *b=begin_;b<end_;++b) new(b) T(t); size_ = s; }
    template <uint64 S2> FArray(const FArray<T,S2> &f) : begin_(0), end_(begin_), allocated_(0), size_(0) { operator=(f); }
    FArray(const FArray<T,0> &f) : begin_(0), end_(begin_), allocated_(0), size_(0) { operator=(f); }
    FArray(std::initializer_list<T> l) : begin_(0), end_(begin_), allocated_(0), size_(0) { 
        for (auto it=l.begin();it!=l.end();++it)
            push_back(*it);
    }
    ~FArray() { reset(); }
    template <uint64 S2> const FArray<T,0> &operator=(const FArray<T,S2> &f) { 
        clear(); 
        checkAllocated(f.size());
        end_ = begin_ + f.size(); 
        size_ = f.size();
        T *bl=begin_;
        for (T *br=f.begin();bl<end();++bl,++br) 
            new(bl) T(*br); 
        return *this; 
    }
    const FArray<T,0> &operator=(const FArray<T,0> &f) {
        clear();
        checkAllocated(f.size());
        end_ = begin_ + f.size();
        size_ = f.size_;
        T *bl=begin_;
        for (T *br=f.begin_;bl<end_;++bl,++br) 
            new(bl) T(*br); 
        return *this; 
    }

    // Accessors
    const size_type &size() const { return size_; }
    const size_type &allocated() const { return allocated_; }
    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); }

    // Manipulators
    void push_back(const T &t) { checkAllocated(size()+1); new(end_) T(t); ++end_; ++size_; }
    T *emplace_back() { checkAllocated(size()+1); ++size_; return end_++; }
    T *emplace_n_back(uint64 n) { checkAllocated(size() + n);  T *ret = end_; end_ += n;  size_ += n;  return ret; }
    void pop_back() { assert(size()); --end_; end_->~T(); --size_; }
    void resize(size_type i,const T &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();
            size_ = i;
            return;
        }
        auto s = size();
        checkAllocated(i); 
        end_ = begin_ + i; 
        size_ = i;
        for (T *p=begin_+s;p<end_;++p)
            new(p) T(t);
    }
    iterator 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;
    }
    iterator 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;
    }
    void put(size_type i,const T &t) {
        if (size()<=i) {
            resize(i);
            push_back(t);
        } else
            at(i) = t;
    }
    template <class C> void append(const C &in) { for (auto i=in.begin();i!=in.end();++i) push_back(*i); }
    bool remove(size_type i) {
        if (i>=size()) return false;
        for (iterator it=begin_+i;it<end_;++it)
            *it = *(it+1);
        pop_back();
        return true;
    }
    size_type 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;
    }
        void clear() {
        // if type T is not plain old data, call the destructor for each array element;
        // std::is_pod is deprecated in C++20; can be replaced with is_integral, is_floating_point etc.
        if (!std::is_pod<T>::value)
            for (T *b=begin_;b<end_;++b) 
                b->~T();
        end_ = begin_; 
        size_ = 0; 
        }
    void clear_no_destruct() { end_ = begin_; size_ = 0; }
    void reset() { 
        clear(); 
        if (begin_) 
            std::free(begin_); 
        end_ = begin_ = 0; 
        allocated_ = 0; 
    }
    void clip() { if (size()*2<allocated_) 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(quint32 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) {
        if (target<=allocated_) return;
        size_type newsize = std::max<size_type>(allocated_,8);
        while (newsize<target)
            newsize += std::min<size_type>(1000000,newsize);
        changeAllocated(newsize);
    }
    void changeAllocated(size_type newSize) {
        size_type old_size = size();
        assert(old_size<=newSize);
        T *newBegin = 0;
        if (newSize)
#ifdef _DEBUG
            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(*tr);
            tr->~T();
        }
        std::free(begin_);
        begin_ = newBegin;
        end_ = begin_ + old_size;
        allocated_ = newSize;
    }
    T *       begin_;
    T *       end_;
    size_type allocated_;
    size_type size_;
};
//#pragma warning(default:4244)
//#pragma warning(default:4267)


// EoF