//#####################################################################
// Copyright 2004-2007, Ronald Fedkiw, Geoffrey Irving, Tamar Shinar, Eftychios Sifakis, Jerry Talton.
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
// Class ARRAY
//#####################################################################
#ifndef __ARRAY__
#define __ARRAY__

#include <Core/Arrays/ARRAY_BASE.h>
#include <Core/Log/DEBUG_UTILITIES.h>
#include <Core/Math_Tools/exchange.h>
#include <Core/Math_Tools/minmax.h>
#include <Core/Read_Write/READ_WRITE_FORWARD.h>
#include <Core/Utilities/EXCEPTIONS.h>
#include <Core/Utilities/PHYSBAM_ATTRIBUTE.h>
#include <Core/Utilities/TYPE_UTILITIES.h>
#include <initializer_list>
namespace PhysBAM{

template<class T,class ID> class ARRAY;
template<class T,class ID> struct IS_ARRAY<ARRAY<T,ID> > {static const bool value=true;};
template<class T,class ID> struct IS_ARRAY_VIEW<ARRAY<T,ID> > {static const bool value=false;};
template<class T,class ID> struct HAS_POINTER<ARRAY<T,ID> > {static const bool value=true;};

template<class T,class ID> struct CANONICALIZE_CONST_ARRAY<ARRAY<T,ID> >:public FIRST<ARRAY_VIEW<const T,ID> >{};

template<class T,class ID>
class ARRAY:public ARRAY_BASE<T,ARRAY<T,ID>,ID>
{
    struct UNUSABLE{};
public:
    static constexpr int fixed_m=-1;
    template<class T2> struct REBIND{typedef ARRAY<T2,ID> TYPE;};
    typedef T ELEMENT;typedef ID INDEX;
    typedef ARRAY_BASE<T,ARRAY<T,ID>,ID> BASE;
    using BASE::Same_Array;using BASE::Last;
    typedef T* iterator; // for stl
    typedef const T* const_iterator; // for stl
    typedef T& RESULT_TYPE;
    typedef const T& CONST_RESULT_TYPE;
    T* base_pointer=nullptr;
    ID buffer_size{};

    ID m{}; // the current size of the array (buffer_size may be larger for elbow room)

    // No data source
    ARRAY() = default;

    explicit ARRAY(ID m_input) PHYSBAM_NEVER_INLINE
        :base_pointer(0),buffer_size(m_input),m(m_input)
    {
        assert(m>=ID());
        if(m<=ID()) return;
        base_pointer=(T*)new unsigned char[sizeof(T)*Value(m)];
        for(int i=0,j=Value(m);i<j;i++) new(base_pointer+i)T();
    }

    ARRAY(ID m_input,NO_INIT) PHYSBAM_NEVER_INLINE
        :base_pointer(0),buffer_size(m_input),m(m_input)
    {
        assert(m>=ID());
        if(m<=ID()) return;
        base_pointer=(T*)new unsigned char[sizeof(T)*Value(m)];
        for(int i=0,j=Value(m);i<j;i++) new(base_pointer+i)T;
    }

    ARRAY(ID m_input,INIT_NEW,const T& __restrict__ initialization_value) PHYSBAM_NEVER_INLINE
        :base_pointer(0),buffer_size(m_input),m(m_input)
    {
        assert(m>=ID());
        if(m<=ID()) return;
        base_pointer=(T*)new unsigned char[sizeof(T)*Value(m)];
        for(int i=0,j=Value(m);i<j;i++) new(base_pointer+i)T(initialization_value);
    }

    explicit ARRAY(const INITIAL_SIZE m_input)
        :ARRAY(ID(Value(m_input)))
    {
    }

    ARRAY(const INITIAL_SIZE m_input,NO_INIT)
        :ARRAY(ID(Value(m_input)),no_init)
    {
    }

    ARRAY(const INITIAL_SIZE m_input,INIT_NEW,const T& __restrict__ initialization_value)
        :ARRAY(ID(Value(m_input)),init_new,initialization_value)
    {
    }

    // Non-array data source
    ARRAY(std::initializer_list<T> init) PHYSBAM_NEVER_INLINE
        :base_pointer(0),buffer_size(init.size()),m(init.size())
    {
        if(m<=ID()) return;
        base_pointer=(T*)new unsigned char[sizeof(T)*Value(m)];
        T* p=base_pointer;
        for(const auto& a:init) new(p++)T(a);
    }

    // Array source
    ARRAY(const ARRAY& array) PHYSBAM_NEVER_INLINE
        :base_pointer(0),buffer_size(array.m),m(array.m)
    {
        if(m<=ID()) return;
        base_pointer=(T*)new unsigned char[sizeof(T)*Value(array.m)];
        for(int i=0,j=Value(m);i<j;i++) new(base_pointer+i)T(array.base_pointer[i]);
    }

    ARRAY(ARRAY&& array)
        :base_pointer(array.base_pointer),buffer_size(array.buffer_size),m(array.m)
    {
        array.base_pointer=0;
        array.buffer_size=ID();
        array.m=ID();
    }

    template<class T_ARRAY>
    explicit ARRAY(const ARRAY_BASE<T,T_ARRAY,ID>& array)
        :ARRAY(array,cast_data,force_idx)
    {}

    // Array source with forcing
    template<class I>
    ARRAY(ARRAY<T,I>&& array,FORCE_IDX)
        :base_pointer(array.base_pointer),buffer_size(ID(Value(array.buffer_size))),m(ID(Value(array.m)))
    {
        array.base_pointer=0;
        array.buffer_size=I();
        array.m=I();
    }

    template<class T_ARRAY,class I>
    ARRAY(const ARRAY_BASE<T,T_ARRAY,I>& array,FORCE_IDX)
        :ARRAY(array,cast_data,force_idx)
    {}

    template<class U,class T_ARRAY>
    ARRAY(const ARRAY_BASE<U,T_ARRAY,ID>& array,CAST_DATA)
        :ARRAY(array,cast_data,force_idx)
    {}

    template<class U,class T_ARRAY,class I>
    ARRAY(const ARRAY_BASE<U,T_ARRAY,I>& array,FORCE_IDX,CAST_DATA)
        :ARRAY(array,cast_data,force_idx)
    {}

    template<class U,class T_ARRAY,class I>
    ARRAY(const ARRAY_BASE<U,T_ARRAY,I>& array,CAST_DATA,FORCE_IDX)
        :base_pointer(0),buffer_size(ID(Value(array.Size()))),m(ID(Value(array.Size())))
    {
        if(m<=ID()) return;
        base_pointer=(T*)new unsigned char[sizeof(T)*Value(m)];
        for(int i=0,j=Value(m);i<j;i++) new(base_pointer+i)T(array(I(i)));
    }

    ~ARRAY() PHYSBAM_NEVER_INLINE
    {
        Call_Destructors_And_Free();
    }

    ID Size() const
    {return m;}

    T& operator()(ID i)
    {assert((unsigned)Value(i)<(unsigned)Value(m));return base_pointer[Value(i)];}

    const T& operator()(ID i) const
    {assert((unsigned)Value(i)<(unsigned)Value(m));return base_pointer[Value(i)];}

    ARRAY& operator=(const ARRAY& array) PHYSBAM_NEVER_INLINE
    {
        if(buffer_size<array.m){
            Call_Destructors_And_Free();
            buffer_size=m=array.m;
            base_pointer=(T*)new unsigned char[sizeof(T)*Value(array.m)];
            for(int i=0,j=Value(m);i<j;i++) new(base_pointer+i)T(array.base_pointer[i]);
            return *this;}
        if(Same_Array(*this,array)) return *this;
        int n=Value(m),p=Value(array.m);
        for(int i=0,j=min(n,p);i<j;i++) base_pointer[i]=array.base_pointer[i];
        for(int i=n;i<p;i++) new(base_pointer+i)T(array.base_pointer[i]);
        for(int i=p;i<n;i++) base_pointer[i].~T();
        m=array.m;
        return *this;
    }

    ARRAY& operator=(ARRAY&& array)
    {
        Call_Destructors_And_Free();
        base_pointer=array.base_pointer;
        buffer_size=array.buffer_size;
        m=array.m;
        array.base_pointer=0;
        array.buffer_size=ID();
        array.m=ID();
        return *this;
    }

    template<class T_ARRAY>
    PHYSBAM_NEVER_INLINE ARRAY& operator=(const ARRAY_BASE<T,T_ARRAY,ID>& array)
    {
        ID array_m=array.Size();
        if(buffer_size<array_m){
            Call_Destructors_And_Free();
            buffer_size=m=array_m;
            base_pointer=(T*)new unsigned char[sizeof(T)*Value(m)];
            for(int i=0,j=Value(m);i<j;i++) new(base_pointer+i)T(array(ID(i)));
            return *this;}
        int n=Value(m),p=Value(array_m);
        for(int i=0,j=min(n,p);i<j;i++) base_pointer[i]=array(ID(i));
        for(int i=n;i<p;i++) new(base_pointer+i)T(array(ID(i)));
        for(int i=p;i<n;i++) base_pointer[i].~T();
        m=array_m;
        return *this;
    }

    bool Valid_Index(ID i) const
    {return (unsigned)Value(i)<(unsigned)Value(m);}

    T* Get_Array_Pointer()
    {return base_pointer;}

    const T* Get_Array_Pointer() const
    {return base_pointer;}

    ID Max_Size() const
    {return buffer_size;}

    void Compact()
    {Exact_Resize(m);}

private:
    void Call_Destructors_And_Free() PHYSBAM_ALWAYS_INLINE
    {
        for(int i=Value(m)-1;i>=0;i--) base_pointer[i].~T();
        delete[] (unsigned char*)base_pointer;
    }

    void Resize_Helper_Fill(int n) PHYSBAM_ALWAYS_INLINE
    {
        for(int i=0;i<n;i++) base_pointer[i]=T();
    }

    void Resize_Helper_Fill(int n,const T& initialization_value) PHYSBAM_ALWAYS_INLINE
    {
        for(int i=0;i<n;i++) base_pointer[i]=initialization_value;
    }

    template<bool exact,bool copy,bool init,bool fill,class... Args>
    void Resize_Helper(ID m_new,Args&&... initialization_value)
    {
        int n=Value(m),p=Value(m_new);
        if(buffer_size<m_new){
            int new_buffer_size=exact?p:(p?2*p:2);
            T* new_buffer=0;
            if(new_buffer_size>0)
            {
                new_buffer=(T*)new unsigned char[sizeof(T)*new_buffer_size];
                n=max(n,0); // Silence compiler warnings
                if constexpr(copy) for(int i=0;i<n;i++) new(new_buffer+i)T(std::move(base_pointer[i]));
                if constexpr(init) for(int i=(fill?0:n);i<p;i++) new(new_buffer+i)T(initialization_value...);
                else for(int i=(copy?n:0);i<p;i++) new(new_buffer+i)T;
            }
            Call_Destructors_And_Free();
            base_pointer=new_buffer;
            buffer_size=ID(new_buffer_size);}
        else if(p>0){
            if constexpr(fill) Resize_Helper_Fill(min(n,p),initialization_value...);
            if constexpr(init) for(int i=n;i<p;i++) new(base_pointer+i)T(initialization_value...);
            else for(int i=n;i<p;i++) new(base_pointer+i)T;
            for(int i=p;i<n;i++) base_pointer[i].~T();}
        m=m_new;
    }

    template<class... Args>
    PHYSBAM_NEVER_INLINE void Append_Helper(Args&&... initialization_value)
    {
        int n=Value(m);
        int new_buffer_size=(n?2*n:2);
        T* new_buffer=(T*)new unsigned char[sizeof(T)*new_buffer_size];
        for(int i=0;i<n;i++) new(new_buffer+i)T(std::move(base_pointer[i]));
        new(new_buffer+n)T(std::forward<Args>(initialization_value)...);
        Call_Destructors_And_Free();
        base_pointer=new_buffer;
        buffer_size=ID(new_buffer_size);
    }

public:
    void Preallocate(ID max_size)
    {
        if(buffer_size<max_size && max_size>ID()){
            int n=Value(m);
            T* new_buffer=(T*)new unsigned char[sizeof(T)*Value(max_size)];
            for(int i=0;i<n;i++) new(new_buffer+i)T(std::move(base_pointer[i]));
            Call_Destructors_And_Free();
            base_pointer=new_buffer;
            buffer_size=max_size;}
    }

    void Resize(ID m_new) PHYSBAM_NEVER_INLINE
    {Resize_Helper<false,true,true,false>(m_new);}
    
    void Resize(ID m_new,NO_INIT) PHYSBAM_NEVER_INLINE
    {Resize_Helper<false,false,false,false>(m_new);}

    // Aliasing with initialization_value is okay.
    void Resize(ID m_new,INIT_NEW,const T& initialization_value) PHYSBAM_NEVER_INLINE
    {Resize_Helper<false,true,true,false>(m_new,initialization_value);}

    void Resize(ID m_new,INIT_ALL) PHYSBAM_NEVER_INLINE
    {Resize_Helper<false,false,true,true>(m_new);}

    // Aliasing with initialization_value is okay.
    void Resize(ID m_new,INIT_ALL,const T& initialization_value) PHYSBAM_NEVER_INLINE
    {Resize_Helper<false,false,true,true>(m_new,initialization_value);}

    void Exact_Resize(ID m_new) PHYSBAM_NEVER_INLINE
    {Resize_Helper<true,true,true,false>(m_new);}
    
    void Exact_Resize(ID m_new,NO_INIT) PHYSBAM_NEVER_INLINE
    {Resize_Helper<true,false,false,false>(m_new);}

    // Aliasing with initialization_value is okay.
    void Exact_Resize(ID m_new,INIT_NEW,const T& initialization_value) PHYSBAM_NEVER_INLINE
    {Resize_Helper<true,true,true,false>(m_new,initialization_value);}

    void Exact_Resize(ID m_new,INIT_ALL) PHYSBAM_NEVER_INLINE
    {Resize_Helper<true,false,true,true>(m_new);}

    // Aliasing with initialization_value is okay.
    void Exact_Resize(ID m_new,INIT_ALL,const T& initialization_value) PHYSBAM_NEVER_INLINE
    {Resize_Helper<true,false,true,true>(m_new,initialization_value);}

    // Aliasing with element is okay.
    ID Append(const T& element) PHYSBAM_ALWAYS_INLINE
    {if(buffer_size<=m) Append_Helper(T(element));else new(base_pointer+Value(m))T(element);return m++;}

    // Aliasing with element is okay.
    ID Append(T&& element) PHYSBAM_ALWAYS_INLINE
    {if(buffer_size<=m) Append_Helper(std::move(element));else new(base_pointer+Value(m))T(std::move(element));return m++;}

    // Aliasing is not allowed
    template<class T_ARRAY> PHYSBAM_NEVER_INLINE void
    Append(const ARRAY_BASE<T,T_ARRAY,ID>& append_array)
    {ID n=append_array.Size(),p=Value(m);Resize_Helper<false,true,false,false>(m+n);for(ID i(0);i<n;i++) (*this)(i+p)=append_array(i);}

    // Note: not very efficient
    void Append_Unique(const T& element)
    {for(ID i(0);i<m;i++) if((*this)(i)==element) return;Append(element);}

    // Note: not efficient
    template<class T_ARRAY>
    void Append_Unique(const ARRAY_BASE<T,T_ARRAY,ID>& append_array)
    {ID n=append_array.Size();for(ID i(0);i<n;i++) Append_Unique(append_array(i));}

    ID Add_End() PHYSBAM_ALWAYS_INLINE
    {if(buffer_size<=m) Append_Helper();else new(base_pointer+Value(m))T();return m++;}

    void Remove_End()
    {assert(m>ID());base_pointer[Value(--m)].~T();}

    void Remove_Index(ID index) // preserves ordering of remaining elements
    {assert((unsigned)Value(index)<(unsigned)Value(m));for(ID i=index;i<m-1;i++) (*this)(i)=std::move((*this)(i+1));Remove_End();}

    void Remove_Index_Lazy(ID index)
    {assert((unsigned)Value(index)<(unsigned)Value(m));if(index<m-1) (*this)(index)=std::move((*this)(m-1));Remove_End();}

    void Remove_All() // if elements are non-primitive this may waste memory
    {for(int i=Value(m)-1;i>=0;i--) base_pointer[i].~T();m=ID();}

    void Clean_Memory()
    {Call_Destructors_And_Free();base_pointer=0;buffer_size=m=ID();}

    void Delete_Pointers_And_Clean_Memory() // only valid if T is a pointer type
    {for(ID i(0);i<m;i++) delete (*this)(i);Clean_Memory();}

    // Aliasing is not allowed
    void Insert(const T& element,ID index)
    {Add_End();for(ID i=m-1;i>index;i--) (*this)(i)=std::move((*this)(i-1));(*this)(index)=element;}

    T Pop_Value()
    {T copy=base_pointer[Value(m)-1];Remove_End();return copy;}

    void Pop()
    {Remove_End();}

    void Pop(const int count) // return value should be copied immediately, not kept around
    {int n=Value(m);assert(n-count>=0);for(int i=n-1;i>=n-count;i--) base_pointer[i].~T();m-=count;}

    T* begin() // for stl
    {return Get_Array_Pointer();}

    const T* begin() const // for stl
    {return Get_Array_Pointer();}

    T* end() // for stl
    {return Get_Array_Pointer()+Value(m);}

    const T* end() const // for stl
    {return Get_Array_Pointer()+Value(m);}

    void Exchange(ARRAY<T,ID>& other)
    {exchange(m,other.m);exchange(base_pointer,other.base_pointer);exchange(buffer_size,other.buffer_size);}

    // Takes ownership of data from array view; only suitable if the input
    // actually owns its data.
    void Take(ARRAY_VIEW<T,ID>&& array)
    {
        base_pointer=array.base_pointer;
        m=array.m;
        buffer_size=array.m;
        array.base_pointer=0;
        array.m=ID();
    }

    // Give up ownership of data to array view; output is responsible for
    // deallocating it.
    ARRAY_VIEW<T,ID> Give()
    {
        ARRAY_VIEW<T,ID> a(base_pointer,m);
        buffer_size=0;
        base_pointer=0;
        m=ID();
        return a;
    }

    template<class RW> PHYSBAM_NEVER_INLINE void
    Read(UNTYPED_ISTREAM<RW>& input)
    {
        Clean_Memory();
        if constexpr(!is_same<RW,char>::value)
        {
            ID n{};
            Read_Binary(input,n);
            if(n<ID()){
                char buff[100];
                sprintf(buff,"Invalid negative array size %d",Value(n));
                throw READ_ERROR(buff);}
            if(n<=ID()) return;
            Exact_Resize(n);
            Read_Binary_Array(input,Get_Array_Pointer(),Value(n));
        }
        else
        {
            Get(input,'(');
            while(!Try_Get(input,')'))
            {
                Add_End();
                Read_Binary(input,Last());
            }
        }
    }

    template<class RW> PHYSBAM_NEVER_INLINE void
    Write(UNTYPED_OSTREAM<RW>& output) const
    {ARRAY_VIEW<const T,ID>(*this).Write(output);}
//#####################################################################
};
// Avoid instantiating common non-trivial functions in large numbers of files.
#define COMMA_ARRAY ,
#define COMMON_ARRAY(T,ID,E)                                             \
    E template ARRAY<T,ID>::ARRAY(ID);                                  \
    E template ARRAY<T,ID>::ARRAY(ID,INIT_NEW,const T&);                \
    E template ARRAY<T,ID>::ARRAY(ID,NO_INIT);                          \
    E template ARRAY<T,ID>::ARRAY(std::initializer_list<T>);            \
    E template ARRAY<T,ID>::ARRAY(const ARRAY&);                        \
    E template ARRAY<T,ID>::~ARRAY();                                   \
    E template ARRAY<T,ID>& ARRAY<T,ID>::operator=(const ARRAY&);       \
    E template void ARRAY<T,ID>::Append_Helper();                       \
    E template void ARRAY<T,ID>::Append_Helper(T&&);                    \
    E template void ARRAY<T,ID>::Preallocate(ID);                       \
    E template void ARRAY<T,ID>::Resize(ID);                            \
    E template void ARRAY<T,ID>::Resize(ID,INIT_ALL);                   \
    E template void ARRAY<T,ID>::Resize(ID,INIT_ALL,const T&);          \
    E template void ARRAY<T,ID>::Resize(ID,INIT_NEW,const T&);          \
    E template void ARRAY<T,ID>::Resize(ID,NO_INIT);
#define COMMON_ARRAY_VECTOR(T,ID,E)             \
    COMMON_ARRAY(T,ID,E);                       \
    COMMON_ARRAY(VECTOR<T COMMA_ARRAY 1>,ID,E); \
    COMMON_ARRAY(VECTOR<T COMMA_ARRAY 2>,ID,E); \
    COMMON_ARRAY(VECTOR<T COMMA_ARRAY 3>,ID,E);
COMMON_ARRAY_VECTOR(bool,int,extern);
COMMON_ARRAY_VECTOR(int,int,extern);
COMMON_ARRAY_VECTOR(float,int,extern);
COMMON_ARRAY_VECTOR(double,int,extern);
COMMON_ARRAY(std::string,int,extern);
COMMON_ARRAY(ARRAY<bool>,int,extern);
COMMON_ARRAY(ARRAY<int>,int,extern);
COMMON_ARRAY(ARRAY<float>,int,extern);
COMMON_ARRAY(ARRAY<double>,int,extern);
}
#endif
