/*
=============================================================================
    File:   DynamicArray.h
    Desc:   Dynamic (variable sized) templated array.
    The array is always stored in a contiguous chunk.
    The array can be resized.
    A size increase will cause more memory to be allocated,
    and may result in relocation of the array memory.
    A size decrease has no effect on the memory allocation.
=============================================================================
*/
#pragma once

#include <Base/Template/Containers/Array/Array.h>

template
<
    typename TYPE,  //!< The type of stored elements
    UINT ALIGNMENT = GET_ALIGNMENT_FOR_CONTAINERS(TYPE) //!< Alignment of allocated memory
>
class DynamicArray
    : public TArrayTraits< TYPE, DynamicArray< TYPE > >
{
public_internal:    // Calling member functions is slow in debug builds.
    TYPE *  mData;  //!< The pointer to the allocated memory.
    AHeap & mHeap;  //!< The allocator used by this array.
    U32     mNum;   //!< The number of valid, 'live' elements, this should be inside the range [0..mMax).
    U32     mMax;   //!< The number of allocated entries + highest bit is set if we cannot deallocate the memory.
    friend class ArrayUtil;
public:
    // 1 bit is used for indicating if the memory was externally allocated (and the array cannot delete it)
    enum { CAPACITY_BITS = (sizeof(U32) * BITS_IN_BYTE) - 1 };

    enum We_Store_Capacity_And_Bit_Flags_In_One_Int
    {
        DONT_FREE_MEMORY_MASK = U32(1 << CAPACITY_BITS),    //!< Indicates that the storage is not the array's to delete.
        EXTRACT_CAPACITY_MASK = U32(~DONT_FREE_MEMORY_MASK),
        //TODO: CAN_MODIFY_MEMORY_MASK
    };

public:
    DynamicArray( AHeap & _heap )
        : mHeap( _heap )
    {
        mData = nil;
        mNum = 0;
        mMax = 0;
    }
    explicit DynamicArray( const DynamicArray& other )
        : mHeap( other.mHeap )
    {
        mData = nil;
        mNum = 0;
        mMax = 0;
        this->Copy( other );
    }
    /// NOTE: the 'externalStorage' must be uninitialized!
    DynamicArray( TYPE* externalStorage, U32 maxCount )
    {
        mData = nil;
        mNum = 0;   // data is preallocated, but not constructed yet
        mMax = 0;
        this->SetExternalData( externalStorage, maxCount );
    }

    /// Use it only if you know what you're doing.
    explicit DynamicArray(ENoInit)
    {}

    /// Destructs array elements and deallocates array memory.
    ~DynamicArray()
    {
        this->clear();
    }

    /// use it only if you know whatcha doin'
    void SetExternalData( TYPE* data, U32 maxCount, U32 newCount = 0 )
    {
        mxASSERT(mData == nil && mMax == 0);
        mData = data;
        mNum = newCount;
        mMax = maxCount;
        mMax |= DONT_FREE_MEMORY_MASK;
    }

    // Returns the current capacity of this array.
    U32 capacity() const
    {
        U32 capacity = (mMax & EXTRACT_CAPACITY_MASK);
        return capacity;
    }

    /// Convenience function to get the number of elements in this array.
    /// Returns the size (the number of elements in the array).
    U32 num() const {
        return mNum;
    }

    TYPE * raw() {
        return mData;
    }
    const TYPE* raw() const {
        return mData;
    }

    mxFORCEINLINE const Range< TYPE > getSlice() const
    {
        return Range< TYPE >( mData, mNum );
    }

    mxFORCEINLINE Range< TYPE > getSlice()
    {
        return Range< TYPE >( mData, mNum );
    }

    /// use it only if you know whatcha doin'
    void setReference( Range< TYPE > & slice )
    {
        mxASSERT(mData == nil && mMax == 0);
        mData = slice.raw();
        mNum = slice.num();
        mMax = slice.num();
        mMax |= DONT_FREE_MEMORY_MASK;
    }


    /// Convenience function to empty the array. Doesn't release allocated memory.
    /// Doesn't call objects' destructors.
    void empty()
    {
        mNum = 0;
    }

    /// Convenience function to empty the array. Doesn't release allocated memory.
    /// Invokes objects' destructors.
    void destroyAndEmpty()
    {
        TDestructN_IfNonPOD( mData, mNum );
        this->empty();
    }

    /// Releases allocated memory (calling destructors of elements) and empties the array.
    void clear()
    {
        if(PtrToBool( mData ))
        {
            TDestructN_IfNonPOD( mData, mNum );
            this->_releaseMemory();
            mData = nil;
        }
        mNum = 0;
        mMax = 0;
    }

    /// Resizes the array to exactly the number of elements it contains or frees up memory if empty.
    void shrink()
    {
        // Condense the array.
        if( mNum > 0 ) {
            this->resize( mNum );
        } else {
            this->clear();
        }
    }

    /// See: http://www.codercorner.com/blog/?p=494
    void EmptyOrClear()
    {
        const U32 capacity = this->capacity();
        const U32 num = this->num();
        if( num > capacity/2 ) {
            this->empty();
        } else {
            this->clear();
        }
    }

    /// Adds an element to the end.
    ERet add( const TYPE& newOne )
    {
        mxDO(this->reserve( mNum + 1 ));
        new(&mData[ mNum++ ]) TYPE( newOne );   // copy-construct
        return ALL_OK;
    }

    /// Increments the size and returns a reference to the first default-constructed element.
    TYPE & AddNew()
    {
        this->reserve( mNum + 1 );
        //NOTE: do not use TYPE(), because it zeroes out PODs, stealing CPU cycles
        return *new(&mData[ mNum++ ]) TYPE;
    }
    ERet AddMany( const TYPE* items, U32 numItems )
    {
        const U32 oldNum = mNum;
        const U32 newNum = oldNum + numItems;
        mxDO(this->setNum( newNum ));
        TCopyArray( mData + oldNum, items, numItems );
        return ALL_OK;
    }

    TYPE & AddUninitialized()
    {
        this->reserve( mNum + 1 );
        return mData[ mNum++ ];
    }
    TYPE* AddManyUninitialized( U32 numElements )
    {
        const U32 oldNum = mNum;
        const U32 newNum = oldNum + numElements;
        if(mxFAILED(this->reserve( newNum ))) {return nil;}
        mNum = newNum;
        return mData + oldNum;
    }
    ERet AddZeroed( U32 numElements )
    {
        mxSTATIC_ASSERT(TypeTrait<TYPE>::IsPlainOldDataType);
        const U32 newNum = mNum + numElements;
        mxDO(this->reserve( newNum ));
        MemZero( (BYTE*)mData + mNum*sizeof(TYPE), numElements*sizeof(TYPE) );
        mNum = newNum;
        return ALL_OK;
    }

    /// assumes that the user has allocated enough space
    void AddFast_Unsafe( const TYPE& newOne )
    {
        mxASSERT( mNum < this->capacity() );
        new(&mData[ mNum++ ]) TYPE( newOne );   // copy-construct
    }

    // Slow!
    bool AddUnique( const TYPE& item )
    {
        const U32 num = mNum;
        for( U32 i = 0; i < num; i++ )
        {
            if( mData[i] == item ) {
                return false;
            }
        }
        this->add( item );
        return true;
    }

    // Slow!
    bool Remove( const TYPE& item )
    {
        return Arrays::RemoveElement( *this, item );
    }

    // Slow!
    void RemoveAt( U32 index, U32 count = 1 )
    {
        Arrays::RemoveAt( mData, mNum, index, count );
    }

    // this method is faster (uses the 'swap trick')
    // Doesn't preserve the relative order of elements.
    void RemoveAt_Fast( U32 index )
    {//I KNOW THIS IS CRAP!
        Arrays::RemoveAt_Fast( mData, mNum, index );
    }

    // Removes all occurrences of value in the array
    // and returns the number of entries removed.
    //
    U32 RemoveAll( const TYPE& theValue )
    {
        U32 numRemoved = 0;
        for( U32 i = 0; i < mNum; ++i )
        {
            if( mData[i] == theValue ) {
                this->RemoveAt( i );
                numRemoved++;
            }
        }
        return numRemoved;
    }

    // removes the last element
    TYPE PopLastValue()
    {
        mxASSERT(mNum > 0);
        return mData[ --mNum ];
    }

    // Slow!
    // inserts a new element at the given index and keeps the relative order of elements.
    TYPE & InsertAt( U32 index )
    {
        mxASSERT( this->isValidIndex( index ) );
        const U32 oldNum = mNum;
        const U32 newNum = oldNum + 1;
        TYPE* data = mData;
        this->reserve( newNum );
        for ( U32 i = oldNum; i > index; --i )
        {
            data[i] = data[i-1];
        }
        mNum = newNum;
        return data[ index ];
    }

    U32 RemoveContainedItem( const TYPE* o )
    {
        const U32 itemIndex = this->GetContainedItemIndex( o );
        chkRET_X_IF_NOT( this->isValidIndex( itemIndex ), INDEX_NONE );
        this->RemoveAt( itemIndex );
        return itemIndex;
    }

    /// Ensures no reallocation occurs until at least size 'numElements'.
    ERet reserve( U32 numElements )
    {
    //  mxASSERT( numElements > 0 );//<- this helped me to catch errors
        mxASSERT( numElements <= DBG_MAX_ARRAY_CAPACITY );
        // resize if necessary
        if( numElements > this->capacity() )
        {
            const U32 newCapacity = ArrayUtil::CalculateNewCapacity( numElements );
            mxDO(this->resize( newCapacity ));
        }
        return ALL_OK;
    }

    /// Sets the new number of elements. Resizes the array to this number if necessary.
    /// NOTE: invokes the new objects' constructors!
    ERet setNum( U32 numElements )
    {
        // resize to the exact size specified irregardless of granularity.
        if( numElements > this->capacity() )
        {
            mxDO(this->resize( numElements ));
        }
        // Call default constructors for new elements.
        if( numElements > mNum )
        {
            const U32 numNewItems = numElements - mNum;
            TConstructN_IfNonPOD( mData + mNum, numNewItems );
        }
        mNum = numElements;
        return ALL_OK;
    }

    bool ownsMemory() const
    {
        return (mMax & DONT_FREE_MEMORY_MASK) == 0;
    }

    // Returns the amount of reserved memory in bytes (memory allocated for storing the elements).
    size_t allocatedMemorySize() const
    {
        return this->capacity() * sizeof(TYPE);
    }

    // Returns the total amount of occupied memory in bytes.
    size_t usedMemorySize() const
    {
        return this->allocatedMemorySize() + sizeof(*this);
    }

    friend void F_UpdateMemoryStats( MemStatsCollector& stats, const DynamicArray& o )
    {
        stats.staticMem += sizeof(o);
        stats.dynamicMem += o.allocatedMemorySize();
    }

public: // Reflection.

    typedef
    DynamicArray
    ARRAY_TYPE;

    class ArrayDescriptor : public MetaArray
    {
    public:
        ArrayDescriptor( const Chars& typeName )
            : MetaArray( typeName, STypeDescription::For_Type<ARRAY_TYPE>(), T_DeduceTypeInfo<TYPE>(), sizeof(TYPE) )
        {}
        //=-- MetaArray
        virtual bool IsDynamic() const override
        {
            return true;
        }
        virtual void* Get_Array_Pointer_Address( const void* pArrayObject ) const override
        {
            const ARRAY_TYPE* theArray = static_cast< const ARRAY_TYPE* >( pArrayObject );
            return c_cast(void*) &theArray->mData;
        }
        virtual U32 Generic_Get_Count( const void* pArrayObject ) const override
        {
            const ARRAY_TYPE* theArray = static_cast< const ARRAY_TYPE* >( pArrayObject );
            return theArray->num();
        }
        virtual ERet Generic_Set_Count( void* pArrayObject, U32 newNum ) const override
        {
            ARRAY_TYPE* theArray = static_cast< ARRAY_TYPE* >( pArrayObject );
            mxDO(theArray->setNum( newNum ));
            return ALL_OK;
        }
        virtual U32 Generic_Get_Capacity( const void* pArrayObject ) const override
        {
            const ARRAY_TYPE* theArray = static_cast< const ARRAY_TYPE* >( pArrayObject );
            return theArray->capacity();
        }
        virtual ERet Generic_Set_Capacity( void* pArrayObject, U32 newNum ) const override
        {
            ARRAY_TYPE* theArray = static_cast< ARRAY_TYPE* >( pArrayObject );
            mxDO(theArray->reserve( newNum ));
            return ALL_OK;
        }
        virtual void* Generic_Get_Data( void* pArrayObject ) const override
        {
            ARRAY_TYPE* theArray = static_cast< ARRAY_TYPE* >( pArrayObject );
            return theArray->raw();
        }
        virtual const void* Generic_Get_Data( const void* pArrayObject ) const override
        {
            const ARRAY_TYPE* theArray = static_cast< const ARRAY_TYPE* >( pArrayObject );
            return theArray->raw();
        }
        virtual void SetDontFreeMemory( void* pArrayObject ) const override
        {
            ARRAY_TYPE* theArray = static_cast< ARRAY_TYPE* >( pArrayObject );
            theArray->mMax |= DONT_FREE_MEMORY_MASK;
        }
    };

public: // Binary Serialization.

    friend AWriter& operator << ( AWriter& file, const DynamicArray& o )
    {
        const U32 number = o.mNum;
        file << number;

        file.SerializeArray( o.mData, number );

        return file;
    }
    friend AReader& operator >> ( AReader& file, DynamicArray& o )
    {
        U32 number;
        file >> number;
        o.setNum( number );

        file.SerializeArray( o.mData, number );

        return file;
    }
    friend mxArchive& operator && ( mxArchive & archive, DynamicArray & o )
    {
        U32 num = o.num();
        archive && num;

        if( archive.IsReading() )
        {
            o.setNum( num );
        }

        TSerializeArray( archive, o.mData, num );

        return archive;
    }

public:
    //TODO: make special shrink(), ReserveAndGrowByHalf(newCapacity) and ReserveAndGrowByNumber(newCapacity,granularity) ?

    //TODO: sorting, binary search, algorithms & iterators

    // Deep copy. Slow!
    /// copy-assignment operator
    void operator = ( const DynamicArray& other )
    {
        this->Copy( other );
    }
    mxTODO("move-assignment operator");

    template< class OTHER_ARRAY >
    ERet Copy( const OTHER_ARRAY& other )
    {
        const U32 newNum = other.num();
        mxASSERT(newNum < DBG_MAX_ARRAY_CAPACITY);
        //@todo: copy memory allocator?
        mxDO(this->setNum( newNum ));
        if( newNum )
        {
            mxWARNING_NOTE("untested: CopyConstruct should be faster then Assignment");
            //TCopyArray( mData, other.raw(), newNum );
            TCopyConstructArray( mData, other.raw(), newNum );
        }
        return ALL_OK;
    }

    void AddBytes( const void* src, size_t numBytes )
    {
        mxSTATIC_ASSERT( sizeof(TYPE) == sizeof(BYTE) );
        const size_t oldNum = mNum;
        const size_t newNum = oldNum + numBytes;
        this->setNum( newNum );
        memcpy( (BYTE*)mData + oldNum, src, numBytes );
    }

    template< typename U >
    void CopyFromArray( const U* src, U32 num )
    {
        this->setNum( num );
        for( U32 i = 0; i < num; i++ )
        {
            mData[ i ] = src[ i ];
        }
    }
    template< typename U, size_t N >
    void CopyFromArray( const U (&src)[N] )
    {
        this->CopyFromArray( src, N );
    }

    ERet AppendOther( const DynamicArray& other )
    {
        const U32 oldNum = mNum;
        const U32 newNum = oldNum + other.num();
        mxDO(this->setNum( newNum ));
        TCopyArray( mData + oldNum, other.mData, other.num() );
        return ALL_OK;
    }

    //NOTE:extremely slow!
    DynamicArray& AppendUniqueElements( const DynamicArray& other )
    {
        for( U32 i = 0; i < other.num(); i++ )
        {
            if(!this->contains( other[i] ))
            {
                this->add( other[i] );
            }
        }
        return *this;
    }

    // works only with types that can be copied via assignment
    // returns the number of removed elements
    //
    template< class FUNCTOR >
    U32 Do_RemoveIf( FUNCTOR& functor )
    {
        const U32 oldNum = mNum;
        U32 newNum = 0;
        for( U32 i = 0; i < oldNum; i++ )
        {
            // if no need to remove this element
            if( !functor( mData[i] ) )
            {
                // then copy it
                mData[ newNum++ ] = mData[ i ];
            }
            // otherwise, skip it
        }
        mNum = newNum;
        return (oldNum - newNum);
    }

public:
    // Testing, Checking & Debugging.

    // you better check urself, before u wreck urself
    bool DbgCheckSelf() const
    {
        //chkRET_FALSE_IF_NOT( IsPowerOfTwo( this->capacity() ) );
        chkRET_FALSE_IF_NOT( this->capacity() <= DBG_MAX_ARRAY_CAPACITY );
        chkRET_FALSE_IF_NOT( mNum <= this->capacity() );//this can happen after AddFast_Unsafe()
        chkRET_FALSE_IF_NOT( mData );
        chkRET_FALSE_IF_NOT( sizeof(U32) <= sizeof(U32) );//need to impl size_t for 64-bit systems
        return true;
    }

private:
    void _releaseMemory()
    {
        if( this->ownsMemory() )
        {
            mHeap.Deallocate( mData/*, this->capacity() * sizeof(TYPE)*/ );
            mData = nil;
        }
    }

    /// allocates more memory if needed, but doesn't initialize new elements (doesn't change array count)
    ERet resize( U32 newCapacity )
    {
        return ArrayUtil::resize( *this, newCapacity, mHeap, ALIGNMENT );
    }

public_internal:

    /// For serialization, we want to initialize the vtables
    /// in classes post data load, and NOT call the default constructor
    /// for the arrays (as the data has already been set).
    explicit DynamicArray( _FinishedLoadingFlag )
    {
    }

    mxFORCEINLINE AHeap &   GetAllocator() const { return mHeap; }

private:
    NO_COMPARES(DynamicArray);
};

//---------------------------------------------------------------------------
// Reflection.
//
template< typename TYPE >
struct TypeDeducer< DynamicArray< TYPE > >
{
    static inline const MetaType& GetType()
    {
        static DynamicArray< TYPE >::ArrayDescriptor staticTypeInfo(mxEXTRACT_TYPE_NAME(DynamicArray));
        return staticTypeInfo;
    }
    static inline ETypeKind GetTypeKind()
    {
        return ETypeKind::Type_Array;
    }
};

//--------------------------------------------------------------//
//              End Of File.                                    //
//--------------------------------------------------------------//