//------------------------------------------------------------------------------
// emArray.h
//
// Copyright (C) 2005-2009,2014-2016 Oliver Hamann.
//
// Homepage: http://eaglemode.sourceforge.net/
//
// This program is free software: you can redistribute it and/or modify it under
// the terms of the GNU General Public License version 3 as published by the
// Free Software Foundation.
//
// This program is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
// FOR A PARTICULAR PURPOSE. See the GNU General Public License version 3 for
// more details.
//
// You should have received a copy of the GNU General Public License version 3
// along with this program. If not, see <http://www.gnu.org/licenses/>.
//------------------------------------------------------------------------------

#ifndef emArray_h
#define emArray_h

#include <new>

#ifndef emStd1_h
#include <emCore/emStd1.h>
#endif


//==============================================================================
//============================== Array functions ===============================
//==============================================================================

template <class OBJ> bool emSortArray(
        OBJ * array, int count,
        int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
        void * context
);
        // Sort an array where the elements are of the type OBJ. The order of
        // equal elements is preserved. It is a merge-sort algorithm.
        // Arguments:
        //   array   - The array to be sorted.
        //   count   - Number of elements in the array.
        //   compare - Function for comparing two elements.
        //             If you want the elements to be compared via the operators
        //             '<' and '>', say:
        //               emStdComparer<OBJ>::Compare
        //             with OBJ replaced by the real type of the elements. The
        //             context argument is ignored then.
        //             Arguments:
        //               obj1    - Pointer to first element.
        //               obj2    - Pointer to second element.
        //               context - See below.
        //             Returns: Zero if the elements are equal, a value greater
        //               than zero if the first element is greater than the
        //               second one, and a value less than zero if the first
        //               element is less than the second one.
        //   context - Any pointer to be forwarded to the compare function.
        // Returns: true if there was a change, false otherwise.


template <class OBJ, class KEY> int emBinarySearch(
        const OBJ * array, int count, KEY key,
        int(*compare)(const OBJ * obj, KEY key, void * context),
        void * context
);
        // Perform a binary search in a sorted array of elements by comparing
        // the elements against a key.
        // Arguments:
        //   array   - The array.
        //   count   - Number of elements in the array.
        //   key     - The key to be searched for.
        //   compare - Function for comparing an element against the key.
        //             If KEY is 'const OBJ *', and if you want the operators
        //             '<' and '>' to be used, say:
        //               emStdComparer<OBJ>::Compare
        //             with OBJ replaced by the real type of the elements. The
        //             context argument is ignored then.
        //             Arguments:
        //               obj     - Pointer to the element.
        //               key     - The key.
        //               context - See below.
        //             Returns: Zero if the element matches the key, a value
        //               greater than zero if the element is greater, and a
        //               value less than zero if it is less.
        //   context - Any pointer to be forwarded to the compare function.
        // Returns:
        //   If a matching element could be found, the index of that element is
        //   returned. Otherwise a value less than zero is returned: the binary
        //   inversion of the index for insertion.


//==============================================================================
//================================== emArray ===================================
//==============================================================================

template <class OBJ> class emArray {

public:

        // Template class for a dynamic array with copy-on-write behavior. The
        // template parameter OBJ is the type of the elements. To avoid frequent
        // reallocations, the array manages a capacity (number of elements
        // memory is allocated for), which may be greater than the count (number
        // of valid elements). The capacity can be up to 3*count-1, or 2*count
        // after increasing only.

        emArray();
                // Construct an empty array.

        emArray(const emArray & array);
                // Construct a copied array.
                // Arguments:
                //   array - The array to be copied.

        emArray(const OBJ * array, int count, int tuningLevel=0);
                // Construct a copied array.
                // Arguments:
                //   array       - The array to be copied.
                //   count       - Number of elements in array.
                //   tuningLevel - Please read the comments on SetTuningLevel.

        emArray(const OBJ * array, int count, const OBJ * array2, int count2,
                int tuningLevel=0);
                // Construct an array by copying two source arrays.
                // Arguments:
                //   array       - The array to be copied to the beginning.
                //   count       - Number of elements in array.
                //   array2      - The array to be copied to the end.
                //   count2      - Number of elements in array2.
                //   tuningLevel - Please read the comments on SetTuningLevel.

        emArray(const OBJ & obj, int count=1, int tuningLevel=0);
                // Construct an array by filling.
                // Arguments:
                //   obj         - The object to be copied to all elements.
                //   count       - Number of elements in the array.
                //   tuningLevel - Please read the comments on SetTuningLevel.

        ~emArray();
                // Destructor.

        emArray & operator = (const emArray & array);
        emArray & operator = (const OBJ & obj);
                // Copy an array or an object to this array.

        int GetTuningLevel() const;
        void SetTuningLevel(int tuningLevel);
                // **************************************************
                // *** CAUTION: NEVER SET A TOO HIGH TUNING LEVEL ***
                // **************************************************
                // Get or set the tuning level. This has influence on the
                // performance. The maximum allowed tuning level depends
                // on the data type OBJ. Possible tuning levels are:
                //   0 - Default level. Can be used for every type.
                //   1 - Objects are moved in memory without calling copy
                //       constructors on the target and without calling
                //       destructors on the source. Can be used for
                //       emString, emArray, emImage... but NOT emList.
                //   2 - Like 1, but objects are copied in memory without
                //       calling copy constructors or copy operators.
                //   3 - Like 2, but destructors are never called. Could
                //       possibly be used for very simple classes which
                //       still have virtual methods.
                //   4 - Like 3, but constructors are never called. Can
                //       be used for primitive types like int, double,
                //       pointers and even emColor.

        int GetCount() const;
                // Get the number of elements in this array.

        void SetCount(int count, bool compact=false);
                // Set the number of elements in this array. Additional elements
                // are set to default state. But if OBJ is a primitive type, or
                // if the tuning level is 4, additional elements are not
                // initialized.
                // Arguments:
                //   count   - The new number of elements in the array.
                //   compact - Whether to make the capacity equal to the count.

        void Compact();
                // Make the capacity equal to the count.

        operator const OBJ * () const;
        const OBJ * Get() const;
                // Get a pointer to the first element in this array, that is,
                // get the array as a normal C array. At least because of the
                // copy-on-write feature, the pointer is valid only until
                // calling any non-const method or operator on this array, or
                // giving this array as a non-const argument to any call in the
                // world. Hint: Even methods like Add, Insert, Replace and
                // GetSubArray may make shallow copies, like the copy operator
                // and copy constructor do.

        const OBJ & operator [] (int index) const;
        const OBJ & Get(int index) const;
                // Get a reference to an element. The rules for the validity of
                // the reference are the same as with the pointer returned by
                // Get().
                // Arguments:
                //   index - The index of the desired element. This must be
                //           within the range of 0 to GetCount()-1.
                // Returns: The reference to the element.

        OBJ * GetWritable();
        OBJ & GetWritable(int index);
                // Like Get() and Get(index), but for modifying the elements.
                // There is no non-const version of the operator [], because
                // that would probably be used accidentally quite often just for
                // reading, producing unnecessary deep copies. The rules for the
                // validity of the pointer or reference are the same as with
                // Get(), but modification is allowed only until doing something
                // which could make a shallow copy of this array.

        void Set(int index, const OBJ & obj);
                // Set an element.
                // Arguments:
                //   index - The index of the element to be set. This must be
                //           within the range of 0 to GetCount()-1.
                //    obj  - The object to be copied to the element.

        void Add(const emArray & array, bool compact=false);
        void Add(const OBJ * array, int count, bool compact=false);
        void Add(const OBJ & obj, int count=1, bool compact=false);
        void AddNew(int count=1, bool compact=false);
                // Like the Insert methods, but with index=GetCount().

        emArray & operator += (const emArray & array);
        emArray & operator += (const OBJ & obj);
        emArray operator + (const emArray & array) const;
        emArray operator + (const OBJ & obj) const;
                // Similar to the Add methods...

        //friend emArray operator + (const OBJ & obj, const emArray & array);
                // This one even exists and can be used.
                // (Having the declaration here would not be portable)

        void Insert(int index, const emArray & array, bool compact=false);
        void Insert(int index, const OBJ * array, int count,
                    bool compact=false);
        void Insert(int index, const OBJ & obj, int count=1,
                    bool compact=false);
        void InsertNew(int index, int count=1, bool compact=false);
                // Like the Replace methods, but with remCount=0.

        void Replace(int index, int remCount, const emArray & array,
                     bool compact=false);
        void Replace(int index, int remCount, const OBJ * array, int count,
                     bool compact=false);
        void Replace(int index, int remCount, const OBJ & obj, int count=1,
                     bool compact=false);
        void ReplaceByNew(int index, int remCount, int count=1,
                          bool compact=false);
                // Remove and/or insert elements at a particular position. The
                // memory areas of source and target may overlap. That means, an
                // array could be inserted into itself, elements could be moved
                // within the array, and so on. With ReplaceByNew, the new
                // elements are set to default state, but if OBJ is a primitive
                // type, or if the tuning level is 4, the new elements are not
                // initialized. index and remCount are clipped if they are out
                // of range.
                // Arguments:
                //   index    - Index of first element to be removed, and where
                //              new elements are to be inserted.
                //   remCount - Number of elements to be removed.
                //   array    - An array whose elements are to be copied to the
                //              new elements.
                //   obj      - An object to be copied for filling the new
                //              elements.
                //   count or array.GetCount() - Number of elements to be
                //              inserted.
                //   compact  - Whether to minimize the capacity.

        emArray GetSubArray(int index, int count, bool compact=false) const;
                // Create a sub-array from elements of this array.
                // Arguments:
                //   index   - Index of first element to be copied into the
                //             returned array.
                //   count   - Number of elements to be copied into the
                //             returned array
                //   compact - Whether to minimize the capacity.
                // Returns: The sub-array.

        emArray Extract(int index, int count, bool compact=false);
                // Like GetSubArray, but remove the affected elements from this
                // array.

        void Remove(int index, int count=1, bool compact=false);
                // Remove elements from this array.
                // Arguments:
                //   index   - Index of first element to be removed.
                //   count   - Number of elements to be removed.
                //   compact - Whether to minimize the capacity.

        void Clear(bool compact=false);
                // Remove all elements (set zero count).
                // Arguments:
                //   compact - Whether to minimize the capacity.

        bool IsEmpty() const;
                // Ask whether the number of elements is zero.

        int PointerToIndex(const OBJ * ptr) const;
                // Get the index of the element whose address is ptr.
                // Returns -1 if ptr is out of range.

        bool Sort(
                int(*compare)(const OBJ * obj1, const OBJ * obj2,
                              void * context),
                void * context=NULL
        );
                // Sort this array. The order of equal elements is preserved.
                // Arguments:
                //   compare - Function for comparing two elements.
                //             If you want the elements to be compared via the
                //             operators '<' and '>', say:
                //               emStdComparer<OBJ>::Compare
                //             with OBJ replaced by the real type of the
                //             elements. The context argument is ignored then.
                //             Arguments:
                //               obj1    - Pointer to first element.
                //               obj2    - Pointer to second element.
                //               context - See below.
                //             Returns: Zero if the elements are equal, a value
                //               greater than zero if the first element is
                //               greater than the second one, and a value less
                //               than zero if the first element is less than the
                //               second one.
                //   context - Any pointer to be forwarded to the compare
                //             function.
                // Returns: Whether there was a change.

        int BinarySearch(
                const OBJ & obj,
                int(*compare)(const OBJ * obj1, const OBJ * obj2,
                              void * context),
                void * context=NULL
        ) const;
                // Search for an element equal to a given object. The array must
                // already be sorted by the same compare function.
                // Arguments:
                //   obj     - An object which is equal to the searched element.
                //   compare - Please see the Sort method.
                //   context - Please see the Sort method.
                // Returns:
                //   If a matching element could be found, the index of that
                //   element is returned. Otherwise a value less than zero is
                //   returned: the binary inversion of the index for insertion.

        int BinarySearchByKey(
                void * key,
                int(*compareObjKey)(const OBJ * obj, void * key,
                                    void * context),
                void * context=NULL
        ) const;
                // Like BinarySearch, but with comparing the elements against a
                // key, which is given as a 'void *' here (because some
                // compilers don't like nested templates).

        void BinaryInsert(
                const OBJ & obj,
                int(*compare)(const OBJ * obj1, const OBJ * obj2,
                              void * context),
                void * context=NULL,
                bool compact=false
        );
                // Insert an element by sorting it into the array, even if there
                // is already an element which equals the given object. The
                // array must already be sorted by the same compare function.
                // Arguments:
                //   obj     - An object to be copied for the insertion.
                //   compare - Please see the Sort method.
                //   context - Please see the Sort method.
                //   compact - Whether to minimize the capacity.

        bool BinaryInsertIfNew(
                const OBJ & obj,
                int(*compare)(const OBJ * obj1, const OBJ * obj2,
                              void * context),
                void * context=NULL,
                bool compact=false
        );
                // Like BinaryInsert, but return false and do nothing if there
                // is already an element which equals the given object.

        void BinaryInsertOrReplace(
                const OBJ & obj,
                int(*compare)(const OBJ * obj1, const OBJ * obj2,
                              void * context),
                void * context=NULL,
                bool compact=false
        );
                // Like BinaryInsert, but if there is already an element which
                // equals the given object, copy the given object into that
                // element, instead of inserting an additional element.

        bool BinaryReplace(
                const OBJ & obj,
                int(*compare)(const OBJ * obj1, const OBJ * obj2,
                              void * context),
                void * context=NULL,
                bool compact=false
        );
                // Like BinaryInsertOrReplace, but do nothing and return false
                // if there is no element which equals the given object.

        bool BinaryRemove(
                const OBJ & obj,
                int(*compare)(const OBJ * obj1, const OBJ * obj2,
                              void * context),
                void * context=NULL,
                bool compact=false
        );
        bool BinaryRemoveByKey(
                void * key,
                int(*compareObjKey)(const OBJ * obj, void * key,
                                    void * context),
                void * context=NULL,
                bool compact=false
        );
                // Like BinarySearch and BinarySearchByKey, but remove the found
                // element, or return false if no such element can been found.

        unsigned int GetDataRefCount() const;
                // Get number of references to the data behind this array.

        void MakeNonShared();
                // This must be called before handing the array to another
                // thread. This method is not recursive. So if the object class
                // even has such a method, you have to call it on every object
                // too.

private:

        struct EmptySharedData {
                int Count;
                int Capacity;
                short TuningLevel;
                short IsStaticEmpty;
                unsigned int RefCount;
        };
        struct SharedData : EmptySharedData {
                OBJ Obj[16];
        };

        void Construct(OBJ * array, const OBJ * src, bool srcIsArray,
                       int count);
        void Copy(OBJ * array, const OBJ * src, bool srcIsArray, int count);
        void Move(OBJ * array, OBJ * srcArray, int count);
        void Destruct(OBJ * array, int count);
        static SharedData * AllocData(int capacity, int tuningLevel);
        void FreeData();
        void MakeWritable();
        void PrivRep(int index, int remCount, const OBJ * src, bool srcIsArray,
                     int insCount, bool compact);

        SharedData * Data;
        static EmptySharedData EmptyData[5];
};


//==============================================================================
//============================== Implementations ===============================
//==============================================================================

//------------------------------ Array functions -------------------------------

template <class OBJ> bool emSortArray(
        OBJ * array, int count,
        int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
        void * context
)
{
        int autoIndices[384];
        int stackMem[128];
        int * stack, * indices, * s1, * s2, * t, * e;
        int i, j, k, l;
        OBJ * tmpArray;

        if (count<=1) return false;
        i=count+count/2;
        if (i<=(int)(sizeof(autoIndices)/sizeof(int))) indices=autoIndices;
        else indices=(int*)malloc(i*sizeof(int));
        for (stack=stackMem, stack[0]=0, i=0, j=0, k=count;;) {
                while (count>2) {
                        stack+=4;
                        stack[0]=i;
                        stack[1]=count;
                        stack[2]=j;
                        stack[3]=k;
                        l=count/2;
                        count-=l;
                        i+=l;
                        j+=l;
                }
                t=indices+j;
                if (count<2) {
                        t[0]=i;
                }
                else if (compare(array+i,array+i+1,context)<=0) {
                        t[0]=i;
                        t[1]=i+1;
                }
                else {
                        t[0]=i+1;
                        t[1]=i;
                }
                while (stack[0]<0) {
                        count=stack[1];
                        t=indices+stack[2];
                        s1=indices+stack[3];
                        s2=t+count/2;
                        e=t+count;
                        stack-=4;
                        for (;;) {
                                if (compare(array+*s1,array+*s2,context)<=0) {
                                        *t++=*s1++;
                                        if (t<s2) continue;
                                        break;
                                }
                                *t++=*s2++;
                                if (s2<e) continue;
                                do { *t++=*s1++; } while (t<s2);
                                break;
                        }
                }
                if (stack==stackMem) break;
                i=stack[0];
                count=stack[1]/2;
                j=stack[3];
                k=stack[2];
                stack[0]=-1;
        }
        tmpArray=(OBJ*)malloc(count*sizeof(OBJ));
        for (i=0; i<count; i++) {
                ::new ((void*)(tmpArray+i)) OBJ(array[i]);
        }
        for (i=count-1, k=-1; i>=0; i--) {
                j=indices[i];
                if (i!=j) {
                        k=0;
                        array[i]=tmpArray[j];
                }
                tmpArray[j].~OBJ();
        }
        free((void*)tmpArray);
        if (indices!=autoIndices) free(indices);
        return k>=0;
}


template <class OBJ, class KEY> int emBinarySearch(
        const OBJ * array, int count, KEY key,
        int(*compare)(const OBJ * obj, KEY key, void * context),
        void * context
)
{
        int i1,i2,i,d;

        i2=count;
        if (i2) {
                i1=0;
                for (;;) {
                        i=(i1+i2)>>1;
                        d=compare(array+i,key,context);
                        if (d>0) {
                                i2=i;
                                if (i1<i2) continue;
                                break;
                        }
                        if (d<0) {
                                i1=i+1;
                                if (i1<i2) continue;
                                break;
                        }
                        return i;
                }
        }
        return ~i2;
}


//---------------------------------- emArray -----------------------------------

template <class OBJ> inline emArray<OBJ>::emArray()
{
        Data=(SharedData*)&EmptyData[0];
}

template <class OBJ> inline emArray<OBJ>::emArray(const emArray & array)
{
        Data=array.Data;
        Data->RefCount++;
}

template <class OBJ> emArray<OBJ>::emArray(
        const OBJ * array, int count, int tuningLevel
)
{
        if (count>0) {
                Data=AllocData(count,tuningLevel);
                Data->Count=count;
                Construct(Data->Obj,array,true,count);
        }
        else {
                Data=(SharedData*)&EmptyData[tuningLevel];
        }
}

template <class OBJ> emArray<OBJ>::emArray(
        const OBJ * array, int count, const OBJ * array2, int count2,
        int tuningLevel
)
{
        if (count<0) count=0;
        if (count2<0) count2=0;
        if (count+count2>0) {
                Data=AllocData(count+count2,tuningLevel);
                Data->Count=count+count2;
                Construct(Data->Obj,array,true,count);
                Construct(Data->Obj+count,array2,true,count2);
        }
        else {
                Data=(SharedData*)&EmptyData[tuningLevel];
        }
}

template <class OBJ> emArray<OBJ>::emArray(
        const OBJ & obj, int count, int tuningLevel
)
{
        if (count>0) {
                Data=AllocData(count,tuningLevel);
                Data->Count=count;
                Construct(Data->Obj,&obj,false,count);
        }
        else {
                Data=(SharedData*)&EmptyData[tuningLevel];
        }
}

template <class OBJ> inline emArray<OBJ>::~emArray()
{
        if (!--Data->RefCount) FreeData();
}

template <class OBJ> inline emArray<OBJ> & emArray<OBJ>::operator = (
        const emArray & array
)
{
        array.Data->RefCount++;
        if (!--Data->RefCount) FreeData();
        Data=array.Data;
        return *this;
}

template <class OBJ> inline emArray<OBJ> & emArray<OBJ>::operator = (
        const OBJ & obj
)
{
        PrivRep(0,Data->Count,&obj,false,1,false);
        return *this;
}

template <class OBJ> inline int emArray<OBJ>::GetTuningLevel() const
{
        return Data->TuningLevel;
}

template <class OBJ> void emArray<OBJ>::SetTuningLevel(int tuningLevel)
{
        if (Data->TuningLevel!=tuningLevel) {
                if (!Data->Count) {
                        if (!--Data->RefCount) FreeData();
                        Data=(SharedData*)&EmptyData[tuningLevel];
                }
                else {
                        if (Data->RefCount>1) MakeWritable();
                        Data->TuningLevel=(short)tuningLevel;
                }
        }
}

template <class OBJ> inline int emArray<OBJ>::GetCount() const
{
        return Data->Count;
}

template <class OBJ> void emArray<OBJ>::SetCount(int count, bool compact)
{
        if (count>Data->Count) {
                PrivRep(Data->Count,0,NULL,false,count-Data->Count,compact);
        }
        else {
                PrivRep(count,Data->Count-count,NULL,false,0,compact);
        }
}

template <class OBJ> inline void emArray<OBJ>::Compact()
{
        PrivRep(0,0,NULL,false,0,true);
}

template <class OBJ> inline emArray<OBJ>::operator const OBJ * () const
{
        return Data->Obj;
}

template <class OBJ> inline const OBJ * emArray<OBJ>::Get() const
{
        return Data->Obj;
}

template <class OBJ> inline const OBJ & emArray<OBJ>::operator [] (
        int index
) const
{
        return Data->Obj[index];
}

template <class OBJ> inline const OBJ & emArray<OBJ>::Get(int index) const
{
        return Data->Obj[index];
}

template <class OBJ> inline OBJ * emArray<OBJ>::GetWritable()
{
        if (Data->RefCount>1) MakeWritable();
        return Data->Obj;
}

template <class OBJ> inline OBJ & emArray<OBJ>::GetWritable(int index)
{
        if (Data->RefCount>1) MakeWritable();
        return Data->Obj[index];
}

template <class OBJ> inline void emArray<OBJ>::Set(int index, const OBJ & obj)
{
        if (Data->RefCount>1) MakeWritable();
        Data->Obj[index]=obj;
}

template <class OBJ> inline void emArray<OBJ>::Add(
        const emArray & array, bool compact
)
{
        Replace(Data->Count,0,array,compact);
}

template <class OBJ> inline void emArray<OBJ>::Add(
        const OBJ * array, int count, bool compact
)
{
        PrivRep(Data->Count,0,array,true,count,compact);
}

template <class OBJ> inline void emArray<OBJ>::Add(
        const OBJ & obj, int count, bool compact
)
{
        PrivRep(Data->Count,0,&obj,false,count,compact);
}

template <class OBJ> inline void emArray<OBJ>::AddNew(int count, bool compact)
{
        PrivRep(Data->Count,0,NULL,false,count,compact);
}

template <class OBJ> inline emArray<OBJ> & emArray<OBJ>::operator += (
        const emArray & array
)
{
        Replace(Data->Count,0,array,false);
        return *this;
}

template <class OBJ> inline emArray<OBJ> & emArray<OBJ>::operator += (
        const OBJ & obj
)
{
        PrivRep(Data->Count,0,&obj,false,1,false);
        return *this;
}

template <class OBJ> emArray<OBJ> emArray<OBJ>::operator + (
        const emArray & array
) const
{
        if (!array.Data->Count) return *this;
        if (!Data->Count) return array;
        return emArray<OBJ>(
                Data->Obj,Data->Count,
                array.Data->Obj,array.Data->Count,
                Data->TuningLevel
        );
}

template <class OBJ> inline emArray<OBJ> emArray<OBJ>::operator + (
        const OBJ & obj
) const
{
        return emArray<OBJ>(Data->Obj,Data->Count,&obj,1,Data->TuningLevel);
}

template <class OBJ> inline emArray<OBJ> operator + (
        const OBJ & obj, const emArray<OBJ> & array
)
{
        return emArray<OBJ>(
                &obj,1,array.Get(),array.GetCount(),array.GetTuningLevel()
        );
}

template <class OBJ> inline void emArray<OBJ>::Insert(
        int index, const emArray & array, bool compact
)
{
        Replace(index,0,array,compact);
}

template <class OBJ> inline void emArray<OBJ>::Insert(
        int index, const OBJ * array, int count, bool compact
)
{
        PrivRep(index,0,array,true,count,compact);
}

template <class OBJ> inline void emArray<OBJ>::Insert(
        int index, const OBJ & obj, int count, bool compact
)
{
        PrivRep(index,0,&obj,false,count,compact);
}

template <class OBJ> inline void emArray<OBJ>::InsertNew(
        int index, int count, bool compact
)
{
        PrivRep(index,0,NULL,false,count,compact);
}

template <class OBJ> void emArray<OBJ>::Replace(
        int index, int remCount, const emArray & array, bool compact
)
{
        if (
                index<=0 &&
                index+remCount>=Data->Count &&
                array.Data->TuningLevel==Data->TuningLevel &&
                (!compact || array.Data->Capacity==array.Data->Count)
        ) {
                array.Data->RefCount++;
                if (!--Data->RefCount) FreeData();
                Data=array.Data;
        }
        else {
                PrivRep(index,remCount,array.Data->Obj,true,array.Data->Count,
                        compact);
        }
}

template <class OBJ> inline void emArray<OBJ>::Replace(
        int index, int remCount, const OBJ * array, int count, bool compact
)
{
        PrivRep(index,remCount,array,true,count,compact);
}

template <class OBJ> inline void emArray<OBJ>::Replace(
        int index, int remCount, const OBJ & obj, int count, bool compact
)
{
        PrivRep(index,remCount,&obj,false,count,compact);
}

template <class OBJ> inline void emArray<OBJ>::ReplaceByNew(
        int index, int remCount, int count, bool compact
)
{
        PrivRep(index,remCount,NULL,false,count,compact);
}

template <class OBJ> emArray<OBJ> emArray<OBJ>::GetSubArray(
        int index, int count, bool compact
) const
{
        if (index<0) { count+=index; index=0; }
        if (count>Data->Count-index) count=Data->Count-index;
        if (count==Data->Count && (!compact || Data->Capacity==Data->Count)) {
                return *this;
        }
        else {
                return emArray<OBJ>(Data->Obj+index,count,Data->TuningLevel);
        }
}

template <class OBJ> emArray<OBJ> emArray<OBJ>::Extract(
        int index, int count, bool compact
)
{
        emArray<OBJ> result(GetSubArray(index,count,compact));
        PrivRep(index,count,NULL,false,0,compact);
        return result;
}

template <class OBJ> inline void emArray<OBJ>::Remove(
        int index, int count, bool compact
)
{
        PrivRep(index,count,NULL,false,0,compact);
}

template <class OBJ> inline void emArray<OBJ>::Clear(bool compact)
{
        PrivRep(0,Data->Count,NULL,false,0,compact);
}

template <class OBJ> inline bool emArray<OBJ>::IsEmpty() const
{
        return !Data->Count;
}

template <class OBJ> int emArray<OBJ>::PointerToIndex(const OBJ * ptr) const
{
        if (ptr<Data->Obj || ptr>=Data->Obj+Data->Count) return -1;
        return ptr-Data->Obj;
}

template <class OBJ> bool emArray<OBJ>::Sort(
        int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
        void * context
)
{
        if (Data->RefCount>1) MakeWritable();
        return emSortArray(Data->Obj,Data->Count,compare,context);
}

template <class OBJ> inline int emArray<OBJ>::BinarySearch(
        const OBJ & obj,
        int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
        void * context
) const
{
        return emBinarySearch(Data->Obj,Data->Count,&obj,compare,context);
}

template <class OBJ> inline int emArray<OBJ>::BinarySearchByKey(
        void * key,
        int(*compareObjKey)(const OBJ * obj, void * key, void * context),
        void * context
) const
{
        return emBinarySearch(Data->Obj,Data->Count,key,compareObjKey,context);
}

template <class OBJ> void emArray<OBJ>::BinaryInsert(
        const OBJ & obj,
        int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
        void * context, bool compact
)
{
        int i;

        i=BinarySearch(obj,compare,context);
        if (i<0) i=~i;
        PrivRep(i,0,&obj,false,1,compact);
}

template <class OBJ> bool emArray<OBJ>::BinaryInsertIfNew(
        const OBJ & obj,
        int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
        void * context, bool compact
)
{
        int i;

        i=BinarySearch(obj,compare,context);
        if (i<0) {
                PrivRep(~i,0,&obj,false,1,compact);
                return true;
        }
        else {
                if (compact && Data->Count!=Data->Capacity) {
                        PrivRep(0,0,NULL,false,0,true);
                }
                return false;
        }
}

template <class OBJ> void emArray<OBJ>::BinaryInsertOrReplace(
        const OBJ & obj,
        int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
        void * context, bool compact
)
{
        int i;

        i=BinarySearch(obj,compare,context);
        if (i>=0) PrivRep(i,1,&obj,false,1,compact);
        else PrivRep(~i,0,&obj,false,1,compact);
}

template <class OBJ> bool emArray<OBJ>::BinaryReplace(
        const OBJ & obj,
        int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
        void * context, bool compact
)
{
        int i;

        i=BinarySearch(obj,compare,context);
        if (i>=0) {
                PrivRep(i,1,&obj,false,1,compact);
                return true;
        }
        else {
                if (compact && Data->Count!=Data->Capacity) {
                        PrivRep(0,0,NULL,false,0,true);
                }
                return false;
        }
}

template <class OBJ> bool emArray<OBJ>::BinaryRemove(
        const OBJ & obj,
        int(*compare)(const OBJ * obj1, const OBJ * obj2, void * context),
        void * context, bool compact
)
{
        int i;

        i=BinarySearch(obj,compare,context);
        if (i>=0) {
                PrivRep(i,1,NULL,false,0,compact);
                return true;
        }
        else {
                if (compact && Data->Count!=Data->Capacity) {
                        PrivRep(0,0,NULL,false,0,true);
                }
                return false;
        }
}

template <class OBJ> bool emArray<OBJ>::BinaryRemoveByKey(
        void * key,
        int(*compareObjKey)(const OBJ * obj, void * key, void * context),
        void * context, bool compact
)
{
        int i;

        i=BinarySearchByKey(key,compareObjKey,context);
        if (i>=0) {
                PrivRep(i,1,NULL,false,0,compact);
                return true;
        }
        else {
                if (compact && Data->Count!=Data->Capacity) {
                        PrivRep(0,0,NULL,false,0,true);
                }
                return false;
        }
}

template <class OBJ> unsigned int emArray<OBJ>::GetDataRefCount() const
{
        return Data->IsStaticEmpty ? UINT_MAX/2 : Data->RefCount;
}

template <class OBJ> inline void emArray<OBJ>::MakeNonShared()
{
        MakeWritable();
}

template <class OBJ> void emArray<OBJ>::Construct(
        OBJ * array, const OBJ * src, bool srcIsArray, int count
)
{
        if (count>0) {
                if (!src) {
                        if (Data->TuningLevel<4) {
                                do {
                                        count--;
                                        ::new ((void*)(array+count)) OBJ();
                                } while (count>0);
                        }
                }
                else if (!srcIsArray) {
                        do {
                                count--;
                                ::new ((void*)(array+count)) OBJ(*src);
                        } while (count>0);
                }
                else {
                        if (Data->TuningLevel<2) {
                                do {
                                        count--;
                                        ::new ((void*)(array+count)) OBJ(src[count]);
                                } while (count>0);
                        }
                        else {
                                memcpy(array,src,count*sizeof(OBJ));
                        }
                }
        }
}

template <class OBJ> void emArray<OBJ>::Copy(
        OBJ * array, const OBJ * src, bool srcIsArray, int count
)
{
        int i;

        if (count>0) {
                if (!src) {
                        if (Data->TuningLevel<3) {
                                do {
                                        count--;
                                        array[count].~OBJ();
                                        ::new ((void*)(array+count)) OBJ();
                                } while (count>0);
                        }
                        else if (Data->TuningLevel<4) {
                                do {
                                        count--;
                                        ::new ((void*)(array+count)) OBJ();
                                } while (count>0);
                        }
                }
                else if (!srcIsArray) {
                        do {
                                count--;
                                array[count]=*src;
                        } while (count>0);
                }
                else if (array!=src) {
                        if (Data->TuningLevel<2) {
                                if (array<src) {
                                        i=0;
                                        do {
                                                array[i]=src[i];
                                                i++;
                                        } while (i<count);
                                }
                                else {
                                        do {
                                                count--;
                                                array[count]=src[count];
                                        } while (count>0);
                                }
                        }
                        else {
                                memmove(array,src,count*sizeof(OBJ));
                        }
                }
        }
}

template <class OBJ> void emArray<OBJ>::Move(
        OBJ * array, OBJ * srcArray, int count
)
{
        int i;

        if (count>0 && array!=srcArray) {
                if (Data->TuningLevel<1) {
                        if (array<srcArray) {
                                i=0;
                                do {
                                        ::new ((void*)(array+i)) OBJ(srcArray[i]);
                                        srcArray[i].~OBJ();
                                        i++;
                                } while (i<count);
                        }
                        else {
                                do {
                                        count--;
                                        ::new ((void*)(array+count)) OBJ(srcArray[count]);
                                        srcArray[count].~OBJ();
                                } while (count>0);
                        }
                }
                else {
                        memmove(array,srcArray,count*sizeof(OBJ));
                }
        }
}

template <class OBJ> void emArray<OBJ>::Destruct(OBJ * array, int count)
{
        if (Data->TuningLevel<3 && count>0) {
                do {
                        count--;
                        array[count].~OBJ();
                } while (count>0);
        }
}

template <class OBJ>
typename emArray<OBJ>::SharedData * emArray<OBJ>::AllocData(
        int capacity, int tuningLevel
)
{
        SharedData * d;

        d=(SharedData*)malloc(
                sizeof(SharedData)-sizeof(OBJ)*16+sizeof(OBJ)*capacity
        );
        d->Count=0;
        d->Capacity=capacity;
        d->TuningLevel=(short)tuningLevel;
        d->IsStaticEmpty=0;
        d->RefCount=1;
        return d;
}

template <class OBJ> void emArray<OBJ>::FreeData()
{
        int i;

        EmptyData[Data->TuningLevel].RefCount=UINT_MAX/2;

        // Never do a
        //  if (Data!=(SharedData*)&EmptyData[Data->TuningLevel])...
        // instead of
        //  if (!Data->IsStaticEmpty)...
        // because static member variables of template classes could exist
        // multiple times for the same final type (e.g. with Windows DLLs).
        if (!Data->IsStaticEmpty) {
                if (Data->TuningLevel<3) {
                        i=Data->Count;
                        while (--i>=0) Data->Obj[i].~OBJ();
                }
#if defined(__GNUC__) && __GNUC__>=5
#       pragma GCC diagnostic push
#       pragma GCC diagnostic ignored "-Wfree-nonheap-object"
#endif
                free((void*)Data);
#if defined(__GNUC__) && __GNUC__>=5
#       pragma GCC diagnostic pop
#endif
        }
}

template <class OBJ> void emArray<OBJ>::MakeWritable()
{
        SharedData * d;

        if (Data->RefCount>1 && !Data->IsStaticEmpty) {
                if (!Data->Count) {
                        d=(SharedData*)&EmptyData[Data->TuningLevel];
                }
                else {
                        d=AllocData(Data->Count,Data->TuningLevel);
                        d->Count=Data->Count;
                        Construct(d->Obj,Data->Obj,true,Data->Count);
                }
                Data->RefCount--;
                Data=d;
        }
}

template <class OBJ> void emArray<OBJ>::PrivRep(
        int index, int remCount, const OBJ * src, bool srcIsArray, int insCount,
        bool compact
)
{
        SharedData * d;
        int newCount,cap,l;

        d=Data;
        if ((unsigned int)index>(unsigned int)d->Count) {
                if (index<0) { remCount+=index; index=0; }
                else index=d->Count;
        }
        if ((unsigned int)remCount>(unsigned int)(d->Count-index)) {
                if (remCount<0) remCount=0;
                else remCount=d->Count-index;
        }
        if (insCount<0) insCount=0;
        if (!remCount && !insCount && (!compact || d->Count==d->Capacity)) {
                return;
        }
        newCount=d->Count+insCount-remCount;

        if (newCount<=0) {
                d=(SharedData*)&EmptyData[d->TuningLevel];
                if (!--Data->RefCount) FreeData();
                Data=d;
                return;
        }

        if (d->RefCount>1) {
                d=AllocData(newCount,d->TuningLevel);
                d->Count=newCount;
                if (index>0) Construct(d->Obj,Data->Obj,true,index);
                if (insCount>0) Construct(d->Obj+index,src,srcIsArray,insCount);
                l=newCount-index-insCount;
                if (l>0) {
                        Construct(d->Obj+index+insCount,Data->Obj+index+remCount,true,l);
                }
                Data->RefCount--;
                Data=d;
                return;
        }

        if (compact) cap=newCount;
        else {
                cap=d->Capacity;
                if (cap<newCount || cap>=newCount*3) cap=newCount*2;
        }

        if (d->Capacity!=cap && d->TuningLevel<1) {
                d=AllocData(cap,d->TuningLevel);
                d->Count=newCount;
                if (insCount>0) Construct(d->Obj+index,src,srcIsArray,insCount);
                if (remCount>0) Destruct(Data->Obj+index,remCount);
                if (index>0) Move(d->Obj,Data->Obj,index);
                l=newCount-index-insCount;
                if (l>0) Move(d->Obj+index+insCount,Data->Obj+index+remCount,l);
                Data->Count=0;
                FreeData();
                Data=d;
                return;
        }

        if (insCount<=remCount) {
                if (insCount>0) Copy(d->Obj+index,src,srcIsArray,insCount);
                if (insCount<remCount) {
                        l=newCount-index-insCount;
                        if (l>0) Copy(d->Obj+index+insCount,d->Obj+index+remCount,true,l);
                        Destruct(d->Obj+newCount,remCount-insCount);
                }
                if (d->Capacity!=cap) {
                        d=(SharedData*)realloc(
                                d,
                                sizeof(SharedData)-sizeof(OBJ)*16+sizeof(OBJ)*cap
                        );
                        d->Capacity=cap;
                        Data=d;
                }
                d->Count=newCount;
                return;
        }

        if (src<d->Obj || src>d->Obj+d->Count) {
                if (d->Capacity!=cap) {
                        d=(SharedData*)realloc(
                                d,
                                sizeof(SharedData)-sizeof(OBJ)*16+sizeof(OBJ)*cap
                        );
                        d->Capacity=cap;
                        Data=d;
                }
                if (remCount>0) {
                        Copy(d->Obj+index,src,srcIsArray,remCount);
                        if (srcIsArray) src+=remCount;
                        index+=remCount;
                        insCount-=remCount;
                }
                l=newCount-index-insCount;
                if (l>0) Move(d->Obj+index+insCount,d->Obj+index,l);
                Construct(d->Obj+index,src,srcIsArray,insCount);
                d->Count=newCount;
                return;
        }

        if (d->Capacity!=cap) {
                Data=(SharedData*)realloc(
                        d,
                        sizeof(SharedData)-sizeof(OBJ)*16+sizeof(OBJ)*cap
                );
                src+=Data->Obj-d->Obj;
                d=Data;
                d->Capacity=cap;
        }
        Construct(d->Obj+d->Count,NULL,false,insCount-remCount);
        d->Count=newCount;
        if (src<=d->Obj+index) {
                l=newCount-index-insCount;
                if (l>0) Copy(d->Obj+index+insCount,d->Obj+index+remCount,true,l);
                Copy(d->Obj+index,src,srcIsArray,insCount);
        }
        else {
                if (remCount>0) {
                        Copy(d->Obj+index,src,srcIsArray,remCount);
                        if (srcIsArray) src+=remCount;
                        index+=remCount;
                        insCount-=remCount;
                }
                l=newCount-index-insCount;
                if (l>0) Copy(d->Obj+index+insCount,d->Obj+index,true,l);
                if (src>=d->Obj+index) src+=insCount;
                Copy(d->Obj+index,src,srcIsArray,insCount);
        }
}

template <class OBJ>
typename emArray<OBJ>::EmptySharedData emArray<OBJ>::EmptyData[5]={
        {0,0,0,1,UINT_MAX/2},
        {0,0,1,1,UINT_MAX/2},
        {0,0,2,1,UINT_MAX/2},
        {0,0,3,1,UINT_MAX/2},
        {0,0,4,1,UINT_MAX/2},
};


#endif