bigdynarray.h

#pragma once
 
APICALL void* _ExMalloc(int Size);
APICALL void _ExFree(void* Ptr);
#ifdef _DEBUG
#define STRICT_CHECK
#endif
void _error_box(const char* text);
#ifdef STRICT_CHECK
#define _strict_check(x) if(!(x))_error_box(#x)
#else
#define _strict_check(x)
#endif
 
template <class Elem,int CellSize=1024>
class BigDynArray
{
    Elem** Values;
    int NValues;
    int MaxValues;  
    int MaxCells;
public:
    
    BigDynArray(const BigDynArray& b);
    inline void EnsureCapacity(int N);
    inline BigDynArray();
    inline BigDynArray(int Size, Elem Filling);
    inline ~BigDynArray();
    inline int Add(const Elem& V);
    inline int Add(const Elem& V,int NTimes);
    template <class array>
    inline void AddRange(array& a);
    inline Elem& operator [](int pos);
    inline const Elem& operator [](int pos) const;
    inline int Count()const;
    inline void Clear();
    inline void FastClear();
    inline void Del(int pos,int num);
    inline void uSet(int pos, const Elem& e, const Elem& Default);
    inline Elem uGet(int pos, const Elem& Default);;
    
    Elem& ExpandTo(int pos,Elem def);
    bool IsEmpty() const;
 
    void RemoveAt(const int Index, const int Count = 1);
    void Insert(const int Index, const Elem& Value, const int Count = 1);
    template <class array>
    void Copy(const array& Src);
    template <class array>
    void AddRange(const array& Src);
    void SetCount(const int Count); // Sets the number of elements actually contained in the "cList"
    void SetCount(int Count, const Elem& Value);
    int IndexOf(const Elem& e);
    void RemoveLast();
    const Elem& GetLast() const;
    Elem& GetLast();
    void FastCopyFrom(const BigDynArray& src);
    void FastZeroMem();
    void Reverse();
    template <class Reader>
    void FromBS(Reader& BS, int count);
    template <class Writer>
    void ToBS(Writer& BS);
    void moveTo(BigDynArray& to);
 
    struct iterator {
        int pos;
        BigDynArray* array;
 
        iterator() {}
        iterator(int v, BigDynArray* b) : pos(v), array(b) {}
        void operator ++() {
            pos++;
        }
        bool operator != (const iterator& itr) const {
            return pos != itr.pos;
        }
        Elem& operator*() {
            return (*array)[pos];
        }
        Elem* operator->() {
            return &(*array)[pos];
        }
    };
    iterator begin() {
        return iterator(0, this);
    }
    iterator end() {
        return iterator(NValues, this);
    }
    void operator = (const BigDynArray& b);
    bool operator == (const BigDynArray& b) const;
};
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::operator=(const BigDynArray& b) {
    if (b.Count()) {
        if (std::is_trivially_copy_constructible<Elem>()) {
            FastCopyFrom(b);
        }
        else {
            EnsureCapacity(b.Count());
            NValues = b.Count();
            for (int i = 0; i < b.Count(); i++) {
                (*this)[i] = b[i];
            }
        }
    }
}
 
template <class Elem, int CellSize>
bool BigDynArray<Elem, CellSize>::operator==(const BigDynArray& b) const {
    if (NValues != b.Count())return false;
    for(int i=0;i<NValues;i++) {
        if ((*this)[i] != b[i])return false;
    }
    return true;
}
 
template <class Elem, int CellSize>
BigDynArray<Elem, CellSize>::BigDynArray(const BigDynArray& b) {
    NValues = MaxCells = MaxValues = 0;
    Values = nullptr;
    operator=(b);
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::EnsureCapacity(int N) {
    if(N>=MaxValues){
        int n=1+(N/CellSize);
        int n0=MaxCells;
        if(n>=MaxCells){                
            MaxCells=std::max(MaxCells+512,n+1);
            Elem** np=(Elem**)_ExMalloc(MaxCells*sizeof(Elem*));
            memset(np,0,MaxCells*sizeof(Elem*));
            if(Values){
                memcpy(np,Values,n0*sizeof(Elem*));
                _ExFree(Values);
            }
            Values=np;
        }
        for(int i=MaxValues/CellSize;i<n;i++){
            Values[i]=(Elem*)_ExMalloc(CellSize*sizeof(Elem));
        }
        MaxValues=n*CellSize;
    }
}
 
template <class Elem, int CellSize>
BigDynArray<Elem, CellSize>::BigDynArray() {
    Values=NULL;
    NValues=0;
    MaxValues=0;        
    MaxCells=0;
}
 
template <class Elem, int CellSize>
BigDynArray<Elem, CellSize>::BigDynArray(int Size, Elem Filling) {
    Values=NULL;
    NValues=0;
    MaxValues=0;        
    MaxCells=0;
    Add(Filling,Size);
}
 
template <class Elem, int CellSize>
BigDynArray<Elem, CellSize>::~BigDynArray() {
    Clear();        
}
 
template <class Elem, int CellSize>
int BigDynArray<Elem, CellSize>::Add(const Elem& V) {
    EnsureCapacity(NValues+1);
    int p1=NValues/CellSize;
    Values[p1][NValues%CellSize]=V;
    NValues++;
    return NValues-1;
}
 
template <class Elem, int CellSize>
int BigDynArray<Elem, CellSize>::Add(const Elem& V, int NTimes) {       
    int r=NValues-1;
    for(int i=0;i<NTimes;i++){
        r=Add(V);
    }
    return r;
}
 
template <class Elem, int CellSize>
template <class array>
void BigDynArray<Elem, CellSize>::AddRange(array& a) {
    int N = a.Count();
    for (int i = 0; i < N; i++) {
        Add(a[i]);
    }
}
 
template <class Elem, int CellSize>
Elem& BigDynArray<Elem, CellSize>::operator[](int pos) {
    _strict_check(pos >= 0 && pos < NValues);
    return Values[pos/CellSize][pos%CellSize];
}
 
template <class Elem, int CellSize>
const Elem& BigDynArray<Elem, CellSize>::operator[](int pos) const {
    _strict_check(pos >= 0 && pos < NValues);
    return Values[pos/CellSize][pos%CellSize];
}
 
template <class Elem, int CellSize>
int BigDynArray<Elem, CellSize>::Count() const {
    return NValues;
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::Clear() {
    if(Values){
        if (std::is_compound<Elem>()) {
            for (int i = 0; i < NValues; i++) {
                (*this)[i].~Elem();
            }
        }
        for(int i=0;i<MaxCells;i++){
            if(Values[i])_ExFree(Values[i]);
        }
        _ExFree(Values);
    }
    Values=NULL;
    NValues=0;
    MaxValues=0;        
    MaxCells=0;
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::FastClear() {     
    NValues=0;
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::Del(int pos, int num) {
    if(pos<0) {
        num += pos;
        pos = 0;
    }
    if (pos + num > NValues) {
        num = NValues - pos;
    }
    if (num <= 0)return;
    for (int p = pos + num; p < NValues; p++) {
        (*this)[p - num] = (*this)[p];
    }
    NValues -= num;
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::uSet(int pos, const Elem& e, const Elem& Default) {
    if (pos >= Count())Add(Default, pos - Count() + 1);
    (*this)[pos] = e;
}
 
template <class Elem, int CellSize>
Elem BigDynArray<Elem, CellSize>::uGet(int pos, const Elem& Default) {
    if (pos < 0 || pos >= Count())return Default;
    return (*this)[pos];
}
 
template <class Elem, int CellSize>
Elem& BigDynArray<Elem, CellSize>::ExpandTo(int pos, Elem def) {    
    if ( pos >= Count() )Add( def, pos - Count() + 1 );
    return (*this)[ pos ];
}
 
template <class Elem, int CellSize>
bool BigDynArray<Elem, CellSize>::IsEmpty() const {
    return NValues == 0;
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::RemoveAt(const int Index, const int Count) {
    Del(Index, Count);
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::Insert(const int Index, const Elem& Value, const int Count) {
    EnsureCapacity(NValues + Count);
    int start = NValues - 1;
    NValues += Count;
    for (int k = start; k >= Index; k--) {
        (*this)[k + Count] = (*this)[k];
    }
    for(int k=0;k<Count;k++) {
        (*this)[k + Index] = Value;
    }
}
 
template <class Elem, int CellSize>
template <class array>
void BigDynArray<Elem, CellSize>::Copy(const array& Src) {
    int ns = Src.Count();
    EnsureCapacity(ns);
    NValues = ns;
    for (int i = 0; i < ns; i++) {
        (*this)[i] = Src[i];
    }
}
 
template <class Elem, int CellSize>
template <class array>
void BigDynArray<Elem, CellSize>::AddRange(const array& Src) {
    int ns = Src.Count();
    EnsureCapacity(ns + Count());
    for(int k=0;k<ns;k++) {
        (*this)[NValues++] = Src[k];
    }
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::SetCount(const int Count) {
    EnsureCapacity(Count);
    NValues = Count;
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::SetCount(int Count, const Elem& Value) {
    EnsureCapacity(Count);
    NValues = Count;
    for(int i=0;i<Count;i++) {
        (*this)[i] = Value;
    }
}
 
template <class Elem, int CellSize>
int BigDynArray<Elem, CellSize>::IndexOf(const Elem& e) {
    for (int i = 0; i < NValues; i++)if (e == (*this)[i])return i;
    return -1;
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::RemoveLast() {
    if (NValues)NValues--;
}
 
template <class Elem, int CellSize>
const Elem& BigDynArray<Elem, CellSize>::GetLast() const {
    _strict_check(NValues > 0);
    return (*this)[NValues - 1];
}
 
template <class Elem, int CellSize>
Elem& BigDynArray<Elem, CellSize>::GetLast() {
    return (*this)[NValues - 1];
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::FastCopyFrom(const BigDynArray& src) {
    EnsureCapacity(src.Count());
    NValues = src.Count();
    for (int k = 0, p = 0; k < NValues; k += CellSize, p++) {
        int nel = std::min(CellSize, NValues - k);
        memcpy(Values[p], src.Values[p], nel * sizeof(Elem));
    }
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::FastZeroMem() {
    for (int k = 0, p = 0; k < NValues; k += CellSize, p++) {
        int nel = std::min(CellSize, NValues - k);
        memset(Values[p], 0, nel * sizeof(Elem));
    }
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::Reverse() {
    for(int i=0,j=NValues-1;i<j;i++,j--) {
        std::swap((*this)[i], (*this)[j]);
    }
}
 
template <class Elem, int CellSize>
template <class Reader>
void BigDynArray<Elem, CellSize>::FromBS(Reader& BS, int count) {
    Clear();
    if (count) {
        SetCount(count);
        for (int i = 0;;) {
            int sz = Count() - i;
            if (sz > CellSize)sz = CellSize;
            if (sz > 0)BS.Read(Values[i/CellSize], sz * sizeof(Elem));
            else break;
            i += CellSize;
        }
    }
}
 
template <class Elem, int CellSize>
template <class Writer>
void BigDynArray<Elem, CellSize>::ToBS(Writer& BS) {
    for (int i = 0;;) {
        int sz = Count() - i;
        if (sz > CellSize)sz = CellSize;
        if (sz > 0)BS.Write(Values[i/CellSize], sz * sizeof(Elem));
        else break;
        i += CellSize;
    }
}
 
template <class Elem, int CellSize>
void BigDynArray<Elem, CellSize>::moveTo(BigDynArray& to) {
    to.Clear();
    to.NValues = NValues;
    to.Values = Values;
    to.MaxValues = MaxValues;
    to.MaxCells = MaxCells;
    NValues = MaxCells = MaxValues = 0;
    Values = nullptr;
}