Collection.h

#ifndef CCOLLECTION_CLASS_H
#define CCOLLECTION_CLASS_H
 
#ifdef _MSC_VER
#pragma once
#endif // _MSC_VER
 
#include "OffsetArray.h"
 
BEGIN_MOOTOOLS_NAMESPACE
 
    #if 0
    DLL_TOOLSFUNCTION void TestCollection();
    #define COLLECTION_STATS
    #endif
 
    template<class DATATYPE, class SIZETYPE> class CSimpleCollection;
    template<class DATATYPE, class SIZETYPE> class CObjectCollection;
 
    /////////////////////////////////////////////////////
    // CCollectionElement
    //
    // This class handles a safe way of accessing an entry
    // in a CSimpleCollection or CObjectCollection
    // The bounds is checked, so no buffer overrun is possible.
    //
 
    template<class DATATYPE, class SIZETYPE>
    class CCollectionElement
    {
        friend CSimpleCollection<DATATYPE, SIZETYPE>;
 
    private:
        CSimpleCollection<DATATYPE, SIZETYPE> *elementCollection;
        int entryIndex, elementsSize;
        DATATYPE *elementData;
 
        void Init(CSimpleCollection<DATATYPE, SIZETYPE> *collection, int index, int size, DATATYPE *data);
 
    protected:
        CCollectionElement();
 
    public:
        void Reset(); // Reset to a void element (without altering the collection itself). Same as a void initialization
        bool IsEmpty() const; // Return false after a reset. Reset/IsEmpty is a useful mecanism to make the element empty. If HasIndex return false, this means that the element as no data or a 0 index size.
        int GetEntryIndex() const;
        int GetSize() const;
        DATATYPE *GetData(int& size);
        const DATATYPE *GetData(int& size) const;
        DATATYPE& GetAt(int i) const;
        DATATYPE& operator[](int i);
        int Add(const DATATYPE& type);
        void RemoveAt(int i);
        void SetAt(int i, const DATATYPE& type);
        DATATYPE *SetSize(int newsize);
        void Copy(const CCollectionElement<DATATYPE, SIZETYPE>& copy);
        void Copy(unsigned int srcindex);
    };
 
 
    /////////////////////////////////////////////////
    // CCollectionElement implementation
 
    template<class DATATYPE, class SIZETYPE>
    inline CCollectionElement<DATATYPE, SIZETYPE>::CCollectionElement()
    {
        elementCollection = NULL;
        elementData = NULL;
        elementsSize = entryIndex = 0;
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline void CCollectionElement<DATATYPE, SIZETYPE>::Init(CSimpleCollection<DATATYPE, SIZETYPE> *collection, int index, int size, DATATYPE *data)
    {
        elementCollection = collection;
        entryIndex = index;
        elementsSize = size;
        elementData = size > 0 ? data : NULL;
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline void CCollectionElement<DATATYPE, SIZETYPE>::Reset()
    {
        elementCollection = NULL;
        elementData = NULL;
        elementsSize = entryIndex = 0;
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline bool CCollectionElement<DATATYPE, SIZETYPE>::IsEmpty() const
    {
        return (elementsSize == 0) || (elementData == NULL);
    }
    
    template<class DATATYPE, class SIZETYPE>
    inline int CCollectionElement<DATATYPE, SIZETYPE>::GetSize() const
    {
        return elementsSize;
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline int CCollectionElement<DATATYPE, SIZETYPE>::GetEntryIndex() const
    {
        return entryIndex;
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline DATATYPE *CCollectionElement<DATATYPE, SIZETYPE>::GetData(int& size)
    {
        size = this->elementsSize;
        return elementData;
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline const DATATYPE *CCollectionElement<DATATYPE, SIZETYPE>::GetData(int& size) const
    {
        size = this->elementsSize;
        return elementData;
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline DATATYPE& CCollectionElement<DATATYPE, SIZETYPE>::GetAt(int i) const
    {
        if (i < elementsSize)
            return elementData[i];
 
        XASSERT(0);
        return elementData[0];
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline DATATYPE& CCollectionElement<DATATYPE, SIZETYPE>::operator[](int i)
    {
        if (i < elementsSize)
            return elementData[i];
 
        XASSERT(0);
        return elementData[0];
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline void CCollectionElement<DATATYPE, SIZETYPE>::SetAt(int i, const DATATYPE& type)
    {
        if (i < elementsSize)
        {
            elementData[i] = type;
            return;
        }
 
        XASSERT(0);
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline int CCollectionElement<DATATYPE, SIZETYPE>::Add(const DATATYPE& type)
    {
        XASSERT(elementCollection);
 
    #ifdef _DEBUG
        int tmp;
        elementCollection->GetEntry(entryIndex, tmp);
        XASSERT(tmp == elementsSize);
    #endif
 
        elementData = elementCollection->SetEntrySize(entryIndex, elementsSize++);
        elementData[elementsSize] = type;
 
        return elementsSize;
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline void CCollectionElement<DATATYPE, SIZETYPE>::Copy(const CCollectionElement<DATATYPE, SIZETYPE>& copy)
    {
        XASSERT(elementCollection);
        elementData = elementCollection->SetEntry(entryIndex,  copy);
        elementsSize = copy.GetSize();
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline void CCollectionElement<DATATYPE, SIZETYPE>::Copy(unsigned int srcindex)
    {
        XASSERT(elementCollection);
        elementCollection->SetEntry(entryIndex, srcindex);
        elementData = elementCollection->GetEntry(entryIndex, elementsSize);
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline void CCollectionElement<DATATYPE, SIZETYPE>::RemoveAt(int index)
    {
        XASSERT(elementCollection);
        if (index < elementsSize)
        {
            elementsSize = elementCollection->RemoveElementInEntry(entryIndex, index);
            return;
        }
 
        XASSERT(0);
    }
 
    template<class DATATYPE, class SIZETYPE>
    inline DATATYPE *CCollectionElement<DATATYPE, SIZETYPE>::SetSize(int newsize)
    {
        XASSERT(elementCollection);
        if (elementsSize == newsize)
            return elementData;
 
        elementData = elementCollection->SetEntrySize(entryIndex, newsize);
        elementsSize = newsize;
 
        return elementData;
    }
 
    /////////////////////////////////////////////////////
    // CSimpleCollection
    //
    // This class handles an array of entries
    // each entries contains a given number of data elements
    // All is stored in a raw array
    //
 
    // SetEntriesSize modes
    typedef enum _CollectionInitializeMode
    {
        COL_EMPTY_NEW_ENTRIES  = 0x01, // new entries are preallocated (defaultElementsNbr) but are kept empty. GetSize() return required number of elements. elements are defined using GetEntry()
        COL_EMPTY_COLLECTION  = 0x02, // collection is freed. new entries are preallocated (defaultElementsNbr) and collection is empty. GetSize() return 0 and elements are added using AddElementInEntry()
        COL_KEEP_ENTRIES = 0x04, // entries are not modified when collection is resized
        COL_SHRINK_ENTRIES = 0x08, // entries are adjusted to defaultElementsNbr when collection is resized
        COL_GROWING_ENTRIES = 0x10, // entries are growing. This prevent the buffer to be resized down when resizing. This allows to fix a size at the beginning of a process, then call SetSize without making reallocation if size lower than initial value.
        COL_EXACTSIZE_ENTRIES = 0x20, // don't allocate extra size when allocating entries
    } CollectionInitializeMode;
 
    // SetEntrySize modes
    typedef enum _CollectionElementsMode
    {
        COL_CREATE_ELEMENTS  = 0x01, // new elements are created
        COL_COMPRESS  = 0x02, // if array is not large enough, the buffer is compressed before being grow. Useful to avoid array oversize, when we know the data should fit in the already allocated buffer
    } _CollectionElementsMode;
 
    typedef struct CSCOffsetRange
    {
        unsigned int offset;
        unsigned int length;
        unsigned int start, end;
    } CSCOffsetRange;
 
    template<class TYPE, class SIZETYPE>
    class CSimpleCollection
    {
        friend CObjectCollection<TYPE, SIZETYPE>;
 
        protected:
            struct CElementHeader
            {
                SIZETYPE size;
                SIZETYPE maxsize;
            };
 
        private :
            unsigned char *data;
            unsigned int entriesNbr;
            SIZETYPE defaultElementsNbr;
            SIZET dataOffset, dataSize;
            COffsetArray offsetArray;
 
    #ifdef COLLECTION_STATS
            // Statistics information
            unsigned int growTime, compressedTime, rearrangedTime;
            unsigned int maxElements, curElements;
            unsigned int maxEntries;
            SIZET maxSize;
            longint readjustedEntries;
            float minWastedRatio;
 
            void UpdateStatistics(bool recompute = FALSE);
    #endif
 
            TYPE *InitElementsSize(unsigned int index, unsigned int size, unsigned int creationMode);
 
            void Init();
            SIZET GetDataSize(bool keepElementSize = false);
            void Compress(SIZET newSize, SIZET minimumSize);
            void Grow(SIZET newDataSize, bool allocExtraSpace = true);
 
            virtual void DestroyElement(TYPE *element, unsigned int number);
            virtual void CreateElement(TYPE *element, unsigned int number);
 
            virtual void DestroyEntries(unsigned int first, unsigned int number);
            virtual void CreateEntries(unsigned int first, unsigned int number);
            virtual void CopyEntry(TYPE *dst, const TYPE *src, int elementNbr);
            virtual void CopyEntries(const CSimpleCollection<TYPE, SIZETYPE>& collection, unsigned int dstindex);
 
        public:
            CSimpleCollection(unsigned int defaultElementsNbr = 3);
            virtual ~CSimpleCollection();
 
            unsigned int GetDefaultEntrySize() { return defaultElementsNbr; };
        
            // Access methods to elements
            void Copy(const CSimpleCollection<TYPE, SIZETYPE>& collection, bool preallocateOnly = false, bool removeAll = true);
            void Serialize(CXArchive& archive);
            void Compress();
            bool FreeExtra(bool allocExtraSpace = false);
            unsigned int GetEntriesSize() const; // The number of entries of the collection
            unsigned int *GetSizes(unsigned int& size) const; // Return an array containing the number of element for each entry of the collection (size is the number of entries of the collection)
            void SetEntriesSize(unsigned int entriesNbr, unsigned int defaultElementsNbr, unsigned int mode, unsigned int *elementsSize = NULL);
            void PreAllocate(unsigned int maxEntriesNbr, SIZET maxElementsNbr);
        
            unsigned int AddEntry(bool createElements, unsigned int elementNbr = -1);
            unsigned int AddEntry(const CCollectionElement<TYPE, SIZETYPE>& element);
 
            TYPE *SetEntry(unsigned int index, const CCollectionElement<TYPE, SIZETYPE>& element);
            TYPE *SetEntry(unsigned int dstindex, unsigned int srcindex);
            TYPE *SetEntry(unsigned int dstindex, const TYPE *data, int size); // Beware data can't belong to the collection itself
            void GetEntry(unsigned int index, CCollectionElement<TYPE, SIZETYPE>& element);
            void GetEntry(unsigned int index, const CCollectionElement<TYPE, SIZETYPE>& element) const;
            TYPE *GetEntry(unsigned int index, int& size) const;
            void RemoveEntry(unsigned int index, unsigned int nCount = 1);
            void Free();
 
            // Access methods to elements
            TYPE *SetEntrySize(unsigned int index, unsigned int elementsNbr, bool createElements = true);
            TYPE *SetEntrySizeCompressed(unsigned int index, unsigned int elementsNbr, bool createElements = true);
            unsigned int AddElementInEntry(unsigned int index, const TYPE& element, unsigned int newCreatedElementNumber = 1, bool createExtraElements = false);
            unsigned int RemoveElementInEntry(unsigned int index, unsigned elementIndex);
 
    #ifdef _DEBUG
            unsigned int CountElements() const;
    #endif
    };
 
    #define COL_TYPE_PTR(data, offset) ((TYPE *)((unsigned char *)data+offset+sizeof(typename CSimpleCollection<TYPE, SIZETYPE>::CElementHeader)))
    #define COL_HEADER_PTR(data, offset) ((typename CSimpleCollection<TYPE, SIZETYPE>::CElementHeader *)((unsigned char *)data+offset))
    #define COL_DATA_SIZE(elementnbr) ((SIZET)((elementnbr)*sizeof(TYPE)+sizeof(typename CSimpleCollection<TYPE, SIZETYPE>::CElementHeader))) // parenthesis between (elementnbr) is important for such call: COL_DATA_SIZE(size-cursize)
 
    /////////////////////////////////////////////////
    // CSimpleCollection
 
    template<class TYPE, class SIZETYPE>
    CSimpleCollection<TYPE, SIZETYPE>::CSimpleCollection(unsigned int newDefaultElementsNbr)
    {
        XASSERT(newDefaultElementsNbr > 0 && newDefaultElementsNbr <= 0xFFFF);
        if (newDefaultElementsNbr > 0)
            this->defaultElementsNbr = (SIZETYPE)newDefaultElementsNbr;
        else 
            this->defaultElementsNbr = 3;
 
        Init();
    }
 
    template<class TYPE, class SIZETYPE>
    CSimpleCollection<TYPE, SIZETYPE>::~CSimpleCollection(void)
    {
        Free();
    }
 
    #ifdef _DEBUG
    template<class TYPE, class SIZETYPE>
    unsigned int CSimpleCollection<TYPE, SIZETYPE>::CountElements() const
    {
        SIZET offset;
        unsigned int count = 0;
        CElementHeader *header;
 
        for (unsigned int i=0; i<entriesNbr; i++)
        {
            offset = offsetArray[i];
            header = COL_HEADER_PTR(data, offset);
            count += header->size;
        }
    #ifdef COLLECTION_STATS
        XASSERT(count == curElements);
    #endif
 
        return count;
    }
    #endif
 
    #ifdef COLLECTION_STATS
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::UpdateStatistics(bool recompute)
    {
        if (recompute)
        {
            unsigned int i, elements = 0, totalsize = 0;
            SIZET offset;
            CElementHeader *header;
            for (i=0; i<entriesNbr; i++)
            {
                offset = offsetArray[i];
 
                header = COL_HEADER_PTR(data, offset);
                totalsize += COL_DATA_SIZE(header->size);
                elements += header->size;
            }
 
            if (totalsize && (minWastedRatio == 0.0 || (minWastedRatio > (dataSize/(float)totalsize))))
                minWastedRatio = (dataSize/(float)totalsize);
 
            curElements = elements;
        }
        else
        {
            SIZET totalsize = (curElements*sizeof(TYPE)+entriesNbr*sizeof(CElementHeader));
            if (totalsize && (minWastedRatio == 0.0 || (minWastedRatio > (dataSize /(float)totalsize))))
                minWastedRatio = (dataSize/(float)totalsize);
        }
 
        if (maxEntries < entriesNbr)
            maxEntries = entriesNbr;
    
        if (maxElements < curElements)
            maxElements = curElements;
    }
    #endif
 
    // Destroy a particular element
    template<class TYPE, class SIZETYPE>
    inline void CSimpleCollection<TYPE, SIZETYPE>::DestroyElement(TYPE *element, unsigned int number)
    {
    #ifdef COLLECTION_STATS
        curElements -= number;
    #endif
    }
 
    // Destroy collection elements
    template<class TYPE, class SIZETYPE>
    inline void CSimpleCollection<TYPE, SIZETYPE>::DestroyEntries(unsigned int first, unsigned int number)
    {
    #ifdef COLLECTION_STATS
        SIZET offset;
        CElementHeader *header;
 
        number += first;
        for (unsigned int i=first; i<number; i++)
        {
            offset = offsetArray[i];
            header = COL_HEADER_PTR(data, offset);
            curElements -= header->size;
        }
    #endif
    }
 
    // Create a particular elements
    template<class TYPE, class SIZETYPE>
    inline void CSimpleCollection<TYPE, SIZETYPE>::CreateElement(TYPE *element, unsigned int number)
    {
    #ifdef COLLECTION_STATS
        curElements += number;
        UpdateStatistics(); // update maxElements / maxEntries
    #endif
    }
 
    // Create collection elements
    template<class TYPE, class SIZETYPE>
    inline void CSimpleCollection<TYPE, SIZETYPE>::CreateEntries(unsigned int first, unsigned int number)
    {
    #ifdef COLLECTION_STATS
        SIZET offset;
        CElementHeader *header;
 
        number += first;
        for (unsigned int i=first; i<number; i++)
        {
            offset = offsetArray[i];
            header = COL_HEADER_PTR(data, offset);
            curElements += header->size;
        }
    #endif
    }
 
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::CopyEntry(TYPE *dst, const TYPE *src, int elementNbr)
    {
        xmemcpy_s(dst, elementNbr*sizeof(TYPE), src, elementNbr*sizeof(TYPE)); // dst should have at least elementNbr before calling
    }
 
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::CopyEntries(const CSimpleCollection<TYPE, SIZETYPE>& collection, unsigned int dstindex)
    {
        XASSERT(dstindex+collection.entriesNbr <= entriesNbr); // Elements must have been created and preallocated
 
        CElementHeader *srcheader;
        SIZET srcoffset, dstoffset;
        for (unsigned int i = 0; i<collection.entriesNbr; i++)
        {
            srcoffset = collection.offsetArray[i];
            dstoffset = offsetArray[dstindex+i];
        
            srcheader = COL_HEADER_PTR(collection.data, srcoffset);
 
            xmemcpy_s(COL_TYPE_PTR(data, dstoffset), dataSize-dstoffset, COL_TYPE_PTR(collection.data, srcoffset), srcheader->size*sizeof(TYPE));
        }
    }
 
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::Init()
    {
        data = NULL;
        dataSize = 0;
        dataOffset = 0;
        entriesNbr = 0;
 
        offsetArray.RemoveAll();
 
    #ifdef COLLECTION_STATS
        // Statistics information
        rearrangedTime = compressedTime = growTime = maxElements = maxEntries = curElements = 0;
        maxSize = 0;
        readjustedEntries = 0;
        minWastedRatio = 0.0f;
    #endif
    }
 
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::Free()
    {
        if (!data)
        {
            XASSERT(!dataSize);
            XASSERT(!entriesNbr);
            XASSERT(!offsetArray.GetSize());
            return;
        }
 
    #ifdef COLLECTION_STATS
        if (maxElements != 0 || maxSize != 0)
        {
            XTRACE(traceStruct, 0, "CSimpleCollection (current size: %d - element size: %d)\n", dataSize, sizeof(TYPE));
            XTRACE(traceStruct, 0, "%d - %d (Entries (current) - elements (current))\n", entriesNbr, curElements);
            XTRACE(traceStruct, 0, "%d - %d (Entries (maximum) - elements (maximum))\n", maxEntries, maxElements);
            XTRACE(traceStruct, 0, "%d - %d - %lld (Array reallocation - Compressed time - Rearranged time - Readjusted entries)\n", growTime, compressedTime, rearrangedTime, readjustedEntries);
            XTRACE(traceStruct, 0, "%d - %.2f (Maximum bytes size - Allocated/Needed size (wasted space))\n\n", maxSize, minWastedRatio);
        }
    #endif
 
        DestroyEntries(0, entriesNbr);
 
    #ifdef COLLECTION_STATS
        XASSERT(curElements == 0);
    #endif
 
        xDeallocateArray(data);
        Init();
    }
 
    // if preallocateOnly = TRUE, we use collection entries for preallocating the current object. The data content is not copied.
    // if preallocateOnly = FALSE, the data content is copied.
    // If removeAll = true, the list is reset with the new content, otherwise it is expanded with the new content
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::Copy(const CSimpleCollection<TYPE, SIZETYPE>& collection, bool preallocateOnly, bool removeAll)
    {
        if (removeAll)
        {
            Free();
            defaultElementsNbr = collection.defaultElementsNbr;
        }
 
        unsigned int i;
        SIZET srcoffset, size = dataOffset; // Copy the collection after the last entry we have
        CElementHeader *srcheader, *dstheader;
 
        // Compute the destination required size. We set it to minimum size
        for (i=0; i<collection.entriesNbr; i++)
        {
            srcoffset = collection.offsetArray[i];
 
            srcheader = COL_HEADER_PTR(collection.data, srcoffset);
            size += COL_DATA_SIZE(srcheader->maxsize);
        }
 
        Grow(size, false);
 
        // Copy headers and entries
        unsigned int entryOffset = entriesNbr;
        entriesNbr += collection.entriesNbr;
        XASSERT((entriesNbr-entryOffset) == collection.entriesNbr);
        offsetArray.SetSize(entriesNbr);
        for (i = 0; i<collection.entriesNbr; i++)
        {
            srcoffset = collection.offsetArray[i];
            srcheader = COL_HEADER_PTR(collection.data, srcoffset);
 
            offsetArray.SetAt(entryOffset+i, dataOffset);
 
            dstheader = COL_HEADER_PTR(data, dataOffset);
            dstheader->size = srcheader->size;
            dstheader->maxsize = srcheader->maxsize;
 
            dataOffset += COL_DATA_SIZE(srcheader->maxsize);
        }
 
        if (preallocateOnly)
        {
            // We only use the size given by collection to preallocate the array
            // but we don't copy the content.
            for (i = 0; i<collection.entriesNbr; i++)
            {
                dstheader = COL_HEADER_PTR(data, offsetArray[i+entryOffset]);
                dstheader->size = 0;
            }
        }
        else
        {
            // Now create and copy entries
            CopyEntries(collection, entryOffset);
        }
 
    #ifdef COLLECTION_STATS
        UpdateStatistics(TRUE);
    #endif
    }
 
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::Serialize(CXArchive& ar)
    {
        if (ar.IsStoring())
        {
            FreeExtra(false);
 
            ar << entriesNbr;
            if (entriesNbr)
            {
                longuint tmp = dataOffset; // use unsigned int for x32 / x64 bits compatibility
                ar.Write(&tmp, sizeof(tmp));
                tmp = dataSize; // use unsigned int for x32 / x64 bits compatibility
                ar.Write(&tmp, sizeof(tmp));
 
                ar.Write(data, static_cast<unsigned int>(dataSize*sizeof(unsigned char)));
                offsetArray.Serialize(ar);
            }
        }
        else
        {
            Free();
 
            ar >> entriesNbr;
            if (entriesNbr)
            {
                longuint tmp = dataOffset; // use unsigned __int64 for x32 / x64 bits compatibility
                ar.Read(&tmp, sizeof(tmp));
                dataOffset = (SIZET)tmp;
 
                ar.Read(&tmp, sizeof(tmp));
                dataSize = (SIZET)tmp;
 
                data = xAllocateArray(unsigned char, dataSize);
                ar.Read(data, static_cast<unsigned int>(dataSize*sizeof(unsigned char)));
                offsetArray.Serialize(ar);
 
    #ifdef COLLECTION_STATS
                UpdateStatistics(TRUE);
    #endif
            }
        }
    }
 
#ifdef SC_REUSED_MEMORY // This code is verified and allows to reused the same piece of memory when compressing
static int rangeCompareProc(const void *elem1, const void *elem2)
    {
        if (((const CSCOffsetRange *)elem1)->offset ==  ((const CSCOffsetRange *)elem2)->offset)
            return 0;
 
        return ((const CSCOffsetRange *)elem1)->offset >  ((const CSCOffsetRange *)elem2)->offset ? 1 : -1;
    }
#endif
 
    // Remove unused memory that might have been lost using RemoveAt, SetAt
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::Compress(SIZET newSize, SIZET minimumSize)
    {
        if (!newSize)
        {
            xDeallocateArray(data);
            data = NULL;
            dataSize = 0;
            dataOffset = 0;
            offsetArray.SetSize(0); // Remove preallocated entries if any
            return;
        }
 
    #ifdef SC_REUSED_MEMORY // This code is verified and allows to reused the same piece of memory when compressing
        if (newSize == dataSize)
        {
            unsigned int i, j, rangeCount = 0;
            CElementHeader *header;
            CSCOffsetRange range;
            CXArray<CSCOffsetRange, CSCOffsetRange&> ranges;
 
            XASSERT(minimumSize <= dataSize);
            i = (dataSize-minimumSize)/(minimumSize/entriesNbr);
            if (i < 10)
                i = 10;
            else if (i > entriesNbr*0.01f)
                i = (unsigned int)(entriesNbr*0.01f);
            ranges.SetSize(i, (entriesNbr*0.01f) < 1024 ? -1 : (INT_PTR)(entriesNbr*0.01f));
 
            XASSERT(entriesNbr);
            SIZET offset = offsetArray[0];
            header = COL_HEADER_PTR(data, offset);
            header->maxsize = header->size;
 
            range.offset = offsetArray[0];
            range.length = COL_DATA_SIZE(header->size);
            range.start = 0;
 
            for (i=1; i<entriesNbr; i++)
            {
                offset = offsetArray[i];
                header = COL_HEADER_PTR(data, offset);
                header->maxsize = header->size;
 
                if (offset == range.offset+range.length) // Continuous block
                    range.length += COL_DATA_SIZE(header->size);
                else
                {
                    range.end = i;
                    ranges.SetAtGrow(rangeCount++, range);
 
                    range.start = i;
                    range.offset = offset;
                    range.length = COL_DATA_SIZE(header->size);
                    range.start = i;
                }
            }
 
            // Store the last range
            range.end = entriesNbr;
            ranges.SetAtGrow(rangeCount++, range);
 
            CSCOffsetRange *rangePtr = ranges.GetData();
            qsort(rangePtr, rangeCount, sizeof(CSCOffsetRange), rangeCompareProc);
 
            SIZET delta, newoffset = 0;
            for (i=0; i<rangeCount; i++)
            {
                xmemcpy_s(data+newoffset, dataSize-newoffset, data+rangePtr[i].offset, rangePtr[i].length);
            
                // update offset
                XASSERT(newoffset <= rangePtr[i].offset);
                delta = rangePtr[i].offset-newoffset;
                if (delta)
                {
                    for (j=rangePtr[i].start; j<rangePtr[i].end; j++)
                        offsetArray[j] = offsetArray[j]-delta;
                }
 
                newoffset += rangePtr[i].length;
            }
 
            dataOffset = newoffset;
            offsetArray.SetSize(entriesNbr); // Remove preallocated entries if any
 
            XASSERT(dataOffset == GetDataSize());
 
    #ifdef COLLECTION_STATS
            rearrangedTime++;
    #endif
 
            return;
        }
    #endif
 
        CElementHeader *oldheader, *newheader;
        SIZET offset, newOffset = 0;
        unsigned char *newdata = xAllocateArray(unsigned char, newSize);
 
        for (unsigned int i=0; i<entriesNbr; i++)
        {
            offset = offsetArray[i];
 
            // copy headers
            oldheader = COL_HEADER_PTR(data, offset);
            newheader = COL_HEADER_PTR(newdata, newOffset);
            newheader->maxsize = newheader->size = oldheader->size;
 
            offsetArray.SetAt(i, newOffset);
 
            // copy data
            offset += sizeof(CElementHeader);
            newOffset += sizeof(CElementHeader);
 
            xmemcpy_s(newdata+newOffset, newSize-newOffset, data+offset, oldheader->size*sizeof(TYPE));
 
            newOffset += oldheader->size*sizeof(TYPE);
        }
 
        XASSERT((dataOffset != newOffset) || (newSize < dataSize)); // This means that Compress removes some entries and was useful, or Compress mimize allocated size
 
        xDeallocateArray(data);
        data = newdata;
        dataSize = newSize;
 
        dataOffset = newOffset;
        offsetArray.SetSize(entriesNbr); // Remove preallocated entries if any
        offsetArray.FreeExtra();
 
    #ifdef COLLECTION_STATS
        compressedTime++;
    #endif
    }
 
    template<class TYPE, class SIZETYPE>
    SIZET CSimpleCollection<TYPE, SIZETYPE>::GetDataSize(bool keepElementSize)
    {
        if (!data)
            return 0;
 
        unsigned int i;
        SIZET offset, totalsize = 0;
        CElementHeader *header;
 
        // Compute the new required size
        if (keepElementSize)
        {
            for (i=0; i<entriesNbr; i++)
            {
                offset = offsetArray[i];
                header = COL_HEADER_PTR(data, offset);
                totalsize += COL_DATA_SIZE(header->maxsize);
            }
        }
        else
        {
            for (i=0; i<entriesNbr; i++)
            {
                offset = offsetArray[i];
                header = COL_HEADER_PTR(data, offset);
                totalsize += COL_DATA_SIZE(header->size);
            }
        }
 
        return totalsize;
    }
 
    // Remove unused memory but keep the same allocated space
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::Compress()
    {
        SIZET newsize = GetDataSize();
 
        // Our array cannot be concatenated
        if (newsize == dataOffset)
            return;
 
        Compress(dataSize, newsize);
    }
 
    // Remove unused memory that might have been lost using RemoveAt, SetAt
    // return true if memory something was free, false if the size is already optimal
    template<class TYPE, class SIZETYPE>
    bool CSimpleCollection<TYPE, SIZETYPE>::FreeExtra(bool keepElementSizeAndExtraSpace)
    {
        SIZET newsize = GetDataSize(keepElementSizeAndExtraSpace);
        if (keepElementSizeAndExtraSpace)
        {
            SIZET extraSize = (newsize/4);
            extraSize = (extraSize < COL_DATA_SIZE(defaultElementsNbr)) ? COL_DATA_SIZE(defaultElementsNbr) : extraSize;
            newsize += extraSize;
        }
 
        // If keepElementSizeAndExtraSpace, resize only if the buffer is bigger than the needed buffer with is extra size. Occurs when the number of elements has been sized down
        if (newsize == dataSize || (keepElementSizeAndExtraSpace && dataSize < newsize))
            return false;
 
        Compress(newsize, newsize);
        return true;
    }
 
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::PreAllocate(unsigned int maxEntriesNbr, SIZET maxElementsNbr)
    {
        if (!maxEntriesNbr)
            maxEntriesNbr = 1;
 
        Free();
        unsigned int elementsPerEntry = (unsigned int)(ceilf(maxElementsNbr/(float)maxEntriesNbr));
        if (elementsPerEntry < defaultElementsNbr)
            elementsPerEntry = defaultElementsNbr;
 
        SIZET size = COL_DATA_SIZE(elementsPerEntry)*maxEntriesNbr;
        Grow(size);
 
        offsetArray.PreAllocate(maxEntriesNbr);
    }
 
    // Reallocate the array
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::Grow(SIZET newDataSize, bool allocExtraSpace)
    {
        if (newDataSize <= dataSize)
            return;
 
        // Allocate 20% more than the needed array
        if (allocExtraSpace)
        {
            SIZET extraSize = (newDataSize/4);
            extraSize = (extraSize < COL_DATA_SIZE(defaultElementsNbr)) ? COL_DATA_SIZE(defaultElementsNbr) : extraSize;
            newDataSize += extraSize;
        }
 
        unsigned char *newData = xAllocateArray(unsigned char, newDataSize);
        if (dataSize)
            xmemcpy_s(newData, newDataSize, data, dataSize < newDataSize ? dataSize : newDataSize);
 
    #ifdef COLLECTION_STATS
        if (dataSize)
            growTime++;
 
        if (maxSize < newDataSize)
            maxSize = newDataSize;
    #endif
 
        xDeallocateArray(data);
        data = newData;
        dataSize = newDataSize;
        // dataOffset is an offset. It remains valid...
 
    #ifdef COLLECTION_STATS
        UpdateStatistics(TRUE);
    #endif
    }
 
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::SetEntriesSize(unsigned int elements, unsigned int newDefaultElementsNbr,  unsigned int mode, unsigned int *elementsSize)
    {
        XASSERT((newDefaultElementsNbr >= 0 && newDefaultElementsNbr <= 0xFFFF));
        if (newDefaultElementsNbr > 0) // if defaultElementsNbr == 0, we keep the previous value but created empty elements as it was required
            this->defaultElementsNbr = (SIZETYPE)newDefaultElementsNbr;
 
        if (!elements || (mode & COL_EMPTY_COLLECTION))
        {
            if (!(mode & COL_GROWING_ENTRIES))
                Free();
 
            if (!elements)
                return;
        }
 
        // No initialization yet...
        SIZETYPE headerSizeNbr = (mode & (COL_EMPTY_NEW_ENTRIES|COL_EMPTY_COLLECTION)) ? 0 : defaultElementsNbr;
        if (!dataSize)
        {
            SIZET newSize = 0;
            if (elementsSize)
            {
                for (unsigned int i=0; i<elements; i++)
                {
                    XASSERT(elementsSize[i] <= (SIZETYPE)(-1));
                    newSize += COL_DATA_SIZE(elementsSize[i]);
                }
            }
            else
                newSize = COL_DATA_SIZE(defaultElementsNbr)*elements;
 
            Grow(newSize, elementsSize ? false : true); // If sizes are provided, we consider user knows exactly the size he needs
 
            offsetArray.SetSize(elements);
 
            CElementHeader *header;
            for (unsigned int i = 0; i<elements; i++)
            {
                header = COL_HEADER_PTR(data, dataOffset);
            
                offsetArray.SetAt(i, dataOffset);
                header->size = headerSizeNbr;
                if (elementsSize)
                    header->maxsize = (SIZETYPE)(elementsSize[i]);
                else
                    header->maxsize = defaultElementsNbr;
 
                dataOffset += COL_DATA_SIZE(header->maxsize);
            }
 
            if (defaultElementsNbr) // if size is 0, don't need to create an elements
                CreateEntries(0, elements);
 
            if (mode & COL_EMPTY_COLLECTION)
                entriesNbr = 0;
            else
                entriesNbr = elements;
        }
        else
        {
            XASSERT(!elementsSize); // only possible at creation
            XASSERT(mode & (COL_KEEP_ENTRIES|COL_SHRINK_ENTRIES));
            XASSERT(!(mode & COL_EMPTY_COLLECTION));
 
            // We first set the number of entries to the required size
            // Then we will set each entry to have the required defaultElementsNbr
 
            // Compute the new buffer size for avoiding many reallocation
            // In the worst case, we have the same number of entries,
            // buf each entries contains a smaller number of elements.
            // Which means that all data are lost (dataOffset), and all entries
            // should be reallocated
            SIZET newSize;
        
            if (mode & COL_KEEP_ENTRIES)
            {
                // New entries are created, each one has the defaultElementsNbr
                if (elements > entriesNbr)
                    newSize = dataOffset+COL_DATA_SIZE(defaultElementsNbr)*(elements-entriesNbr);
                else
                    newSize = dataSize; // Entries are removed. size is not modified
            }
            else // Shrink mode
            {
                newSize = dataOffset+COL_DATA_SIZE(defaultElementsNbr)*elements;
 
                unsigned int tmpsize = elements < entriesNbr ? elements : entriesNbr;
                CElementHeader *header;
                for (unsigned int i = 0; i<tmpsize; i++)
                {
                    SIZET offset = offsetArray[i];
                    header = COL_HEADER_PTR(data, offset);
                    if (defaultElementsNbr <= header->maxsize)
                    {
                        // this entry has enough space to store the number of elements.
                        newSize -= COL_DATA_SIZE(defaultElementsNbr);
                    }
                }
            }
        
            Grow(newSize, (mode & COL_EXACTSIZE_ENTRIES) ? false : true);
 
            // Our buffer is large enough to get or remove the new data
            if (elements > entriesNbr)
            {
                offsetArray.SetSize(elements);
 
                CElementHeader *header;
                for (unsigned int i = entriesNbr; i<elements; i++)
                {
                    header = COL_HEADER_PTR(data, dataOffset);
                    offsetArray.SetAt(i, dataOffset);
                    header->size = headerSizeNbr;
                    header->maxsize = defaultElementsNbr;
                    dataOffset += COL_DATA_SIZE(header->maxsize);
                }
 
                // Create new elements
                if (defaultElementsNbr) // if size is 0, don't need to create an elements
                    CreateEntries(entriesNbr, elements-entriesNbr);
 
                if (mode & COL_SHRINK_ENTRIES)
                {
                    // Now set the already existing elements to have the default size
                    // if COL_EMPTY_NEW_ENTRIES, we don't create the new elements, just inflate the
                    // entries to allows new elements to be added later
                    for (unsigned int i=0; i<entriesNbr; i++)
                        InitElementsSize(i, defaultElementsNbr, (mode & COL_EMPTY_NEW_ENTRIES) ? 0 : COL_CREATE_ELEMENTS);
                }
            }
            else
            {
                // elements <= entriesNbr. Array is growing, do not delete already entered elements
                // This is useful when caller first set SetEntriesSize(100); (100 is an estimation)
                // Then it calls SetEntriesSize with different value in a loop, without knowing the final number of elements... This avoid memory reallocation
                // then user should call SetSize with the right number of element (and without COL_GROWING_ENTRIES) then calls FreeExtra to adjust the size
                // an example of such use is done in CSkpReader::ConvertFaces (SketchupConverter.cpp)
                if (mode & COL_GROWING_ENTRIES) 
                    return; // Keep predefined entriesNbr
 
                // Destroy unuseful elements
                DestroyEntries(elements, entriesNbr-elements);
                offsetArray.SetSize(elements);
        
                if (mode & COL_SHRINK_ENTRIES)
                {
                    XASSERT(!(mode & COL_EMPTY_NEW_ENTRIES));
 
                    // Now set each elements to have the default size
                    for (unsigned int i=0; i<elements; i++)
                        InitElementsSize(i, defaultElementsNbr, (mode & COL_EMPTY_NEW_ENTRIES) ? 0 : COL_CREATE_ELEMENTS);
                }
            }
 
            entriesNbr = elements;
 
            if (mode & COL_GROWING_ENTRIES) 
                return; // Keep PreAllocated memory (when using PreAllocate, element number is 0 and grow progressively
 
            // Then clean the array, but let's some extra space for further operation
            FreeExtra(!(mode & COL_EXACTSIZE_ENTRIES));
        }
 
    #ifdef COLLECTION_STATS
        UpdateStatistics();
    #endif
    }
 
    template<class TYPE, class SIZETYPE>
    void CSimpleCollection<TYPE, SIZETYPE>::RemoveEntry(unsigned int index, unsigned int nCount)
    {
        if (index < entriesNbr)
        {
            // Destroy the element
            while (nCount)
            {
                SIZET offset = offsetArray[index];
                CElementHeader *header = COL_HEADER_PTR(data, offset);
                DestroyElement(COL_TYPE_PTR(data, offset), header->size);
                offsetArray.RemoveAt(index);
                entriesNbr--;
                nCount--;
 
                if (nCount > 0 && index == entriesNbr)
                {
                    XASSERT(0);
                    break;
                }
            }
 
    #ifdef COLLECTION_STATS
            UpdateStatistics();
    #endif
 
            return; 
        }
 
        XASSERT(0);
    }
 
    template<class TYPE, class SIZETYPE>
    unsigned int CSimpleCollection<TYPE, SIZETYPE>::GetEntriesSize() const
    {
        return entriesNbr;
    }
 
    template<class TYPE, class SIZETYPE>
    unsigned int *CSimpleCollection<TYPE, SIZETYPE>::GetSizes(unsigned int& size) const
    {
        size = entriesNbr;
        unsigned int *sizes = xAllocateArray(unsigned int, size);
 
        CElementHeader *header;
        for (int i=0; i<size; i++)
        {
            header = COL_HEADER_PTR(data, offsetArray[i]);
            sizes[i] = header->size;
        }
 
        return sizes;
    }
 
    template<class TYPE, class SIZETYPE>
    inline TYPE *CSimpleCollection<TYPE, SIZETYPE>::SetEntry(unsigned int index, const CCollectionElement<TYPE, SIZETYPE>& element)
    {
        if (index < entriesNbr)
        {
            int size = element.GetSize();
            TYPE *newElement = SetEntrySize(index, size);
        
            const TYPE *elementData = element.elementData;
            XASSERT(element.elementCollection);
            if (element.elementCollection == this)
            {
                // Do not use the element.elementData pointer.
                // The elementData pointer might changed if SetEntrySize grows the array and if element.elementCollection == this
                // This might occurs when copying items from a collection to itself such in CFace::Clean method
                elementData = element.elementCollection->GetEntry(element.entryIndex, size);
                XASSERT(size == element.GetSize());
            }
 
            CopyEntry(newElement, elementData, size);
 
            return newElement;
        }
 
        XASSERT(0);
        return NULL;
    }
 
    template<class TYPE, class SIZETYPE>
    inline TYPE *CSimpleCollection<TYPE, SIZETYPE>::SetEntry(unsigned int dstindex, const TYPE *entrydata, int entrysize)
    {
        if (dstindex < entriesNbr)
        {
            // Note: the data can't belong to the collection itself
            // SetEntrySize(index, size); might do reallocation and in such case data will become invalid
            XASSERT(((void *)entrydata < (void *)data) || ((void *)entrydata > (void *)(data+dataSize)));
            TYPE *newElement = SetEntrySize(dstindex, entrysize);
            CopyEntry(newElement, entrydata, entrysize);
 
            return newElement;
        }
 
        XASSERT(0);
        return NULL;
    }
 
    template<class TYPE, class SIZETYPE>
    inline TYPE *CSimpleCollection<TYPE, SIZETYPE>::SetEntry(unsigned int dstindex, unsigned int srcindex)
    {
        if (dstindex < entriesNbr && srcindex < entriesNbr)
        {
            int size;
            GetEntry(srcindex, size);
        
            TYPE *newElement = SetEntrySize(dstindex, size);
        
            // Get elementData pointer now (the elementData pointer might changed if SetEntrySize grows the array)
            TYPE *elementData = GetEntry(srcindex, size);
            CopyEntry(newElement, elementData, size);
 
            return elementData;
        }
 
        XASSERT(0);
        return NULL;
    }
 
    template<class TYPE, class SIZETYPE>
    inline void CSimpleCollection<TYPE, SIZETYPE>::GetEntry(unsigned int index, CCollectionElement<TYPE, SIZETYPE>& type)
    {
        if (index < entriesNbr)
        {
            SIZET offset = offsetArray[index];
            type.Init(this, index, COL_HEADER_PTR(data, offset)->size, COL_TYPE_PTR(data, offset));
            return;
        }
 
        type.Init(this, index, 0, NULL);
        XASSERT(0);
    }
 
    template<class TYPE, class SIZETYPE>
    inline void CSimpleCollection<TYPE, SIZETYPE>::GetEntry(unsigned int index, const CCollectionElement<TYPE, SIZETYPE>& type) const
    {
        if (index < entriesNbr)
        {
            SIZET offset = offsetArray[index];
            const_cast<CCollectionElement<TYPE, SIZETYPE>&>(type).Init(const_cast<CSimpleCollection<TYPE, SIZETYPE> *>(this), index, COL_HEADER_PTR(data, offset)->size, COL_TYPE_PTR(data, offset));
 
            return;
        }
 
        XASSERT(0);
    }
 
    template<class TYPE, class SIZETYPE>
    inline TYPE *CSimpleCollection<TYPE, SIZETYPE>::GetEntry(unsigned int index, int& size) const
    {
        if (index < entriesNbr)
        {
            SIZET offset = offsetArray[index];
            size = COL_HEADER_PTR(data, offset)->size;
            if (!size)
                return NULL;
 
            return COL_TYPE_PTR(data, offset);
        }
 
        XASSERT(0);
        size = 0;
        return NULL;    
    }
 
    template<class TYPE, class SIZETYPE>
    TYPE *CSimpleCollection<TYPE, SIZETYPE>::InitElementsSize(unsigned int index, unsigned int size, unsigned int creationMode)
    {
        XASSERT(size <= 0xFFFF);
        if (index < entriesNbr)
        {
            SIZET offset = offsetArray[index];
 
            CElementHeader *header = COL_HEADER_PTR(data, offset);
            unsigned int cursize = header->size;
        
            if (size == cursize)
                return COL_TYPE_PTR(data, offset);
            else if (size < cursize)
            {
                // Destroy the not needed elements
                header->size = (SIZETYPE)size;
 
                TYPE *element = COL_TYPE_PTR(data, offset); // first element
                element += size; // first element to destroy
                DestroyElement(element, cursize-size);
 
                return COL_TYPE_PTR(data, offset);
            }
            else if (size <= header->maxsize) // header->size < size <= maxsize
            {
                // if !createElements, nothing to do...
                if ((creationMode & COL_CREATE_ELEMENTS))
                {
                    // Create the new elements
                    header->size = (SIZETYPE)size;
 
                    TYPE *element = COL_TYPE_PTR(data, offset); // first element
                    element += cursize; // first element to create
                    CreateElement(element, size-cursize);
                }
 
                return COL_TYPE_PTR(data, offset);
            }
 
            // size > header->maxsize
 
            // 12/19
            // Last entry case : extend the entry. Last entry index than the last index (if this index has been growed previously below)
            // This allows to perform PreAllocate / AddEntry / AddElementInEntry sequence and enter element one by one, without knowing the size of each element (cf. WFPolygon)
            if (offset + COL_DATA_SIZE(header->maxsize) == dataOffset)
            {
                Grow(offset + COL_DATA_SIZE(size)); // The entry will have size element including from it's current offset
 
                header = COL_HEADER_PTR(data, offset); // data might changed
                header->size = (SIZETYPE)((creationMode & COL_CREATE_ELEMENTS) ? size : cursize);
                header->maxsize = (SIZETYPE)size;
 
                // And creates new ones
                if ((creationMode & COL_CREATE_ELEMENTS))
                {
                    TYPE* element = COL_TYPE_PTR(data, offset); // first element
                    element += cursize; // first element to create
                    CreateElement(element, size - cursize);
                }
 
                dataOffset = offset + COL_DATA_SIZE(size);
 
                return COL_TYPE_PTR(data, offset);
            }
 
            // Compress if requires then grow if needed
            if ((creationMode & COL_COMPRESS) && ((dataOffset+COL_DATA_SIZE(size)) > dataSize))
                Compress();
 
            // other entry case : we copy the previous information at the end of memory
            Grow(dataOffset+COL_DATA_SIZE(size));
 
            offsetArray.SetAt(index, dataOffset);
            header = COL_HEADER_PTR(data, dataOffset);
            header->size = (SIZETYPE)((creationMode & COL_CREATE_ELEMENTS) ? size : cursize);
            header->maxsize = (SIZETYPE)size;
 
            // copy old elements...
            dataOffset += sizeof(CElementHeader);
            xmemcpy_s(data+dataOffset, dataSize-dataOffset, COL_TYPE_PTR(data, offset), cursize*sizeof(TYPE));
            dataOffset += cursize*sizeof(TYPE);
 
            // And creates new ones
            if ((creationMode & COL_CREATE_ELEMENTS))
                CreateElement((TYPE *)(data+dataOffset), size-cursize);
 
    #ifdef COLLECTION_STATS
            readjustedEntries +=  size-cursize;
            UpdateStatistics();
    #endif
 
            dataOffset += (size-cursize)*sizeof(TYPE);
 
            return COL_TYPE_PTR(data, offsetArray[index]);
        }
 
        XASSERT(0);
        return NULL;
    }
 
    template<class TYPE, class SIZETYPE>
    inline TYPE *CSimpleCollection<TYPE, SIZETYPE>::SetEntrySize(unsigned int index,  unsigned int size, bool createElements)
    {
        return InitElementsSize(index, size, createElements ? COL_CREATE_ELEMENTS : 0);
    }
 
    template<class TYPE, class SIZETYPE>
    inline TYPE *CSimpleCollection<TYPE, SIZETYPE>::SetEntrySizeCompressed(unsigned int index,  unsigned int size, bool createElements)
    {
        return InitElementsSize(index, size, createElements ? COL_CREATE_ELEMENTS|COL_COMPRESS : COL_COMPRESS);
    }
 
    template<class TYPE, class SIZETYPE>
    unsigned int CSimpleCollection<TYPE, SIZETYPE>::AddEntry(const CCollectionElement<TYPE, SIZETYPE>& element)
    {
        unsigned int entryIndex = AddEntry(true, element.GetSize());
        SetEntry(entryIndex, element);
        return entryIndex;
    }
 
    // Add an entry to the collection and returns its index
    template<class TYPE, class SIZETYPE>
    unsigned int CSimpleCollection<TYPE, SIZETYPE>::AddEntry(bool createElements, unsigned int elementsNbr)
    {
        if (elementsNbr == -1)
            elementsNbr = defaultElementsNbr;
 
        // The new element has been preallocated...
        if (entriesNbr < (unsigned int)offsetArray.GetSize())
        {
            entriesNbr++;
            InitElementsSize(entriesNbr-1, elementsNbr, createElements ? COL_CREATE_ELEMENTS : 0);
        }
        else
        {
            Grow(dataOffset+COL_DATA_SIZE(elementsNbr));
            offsetArray.SetAtGrow(entriesNbr++, dataOffset);
 
            CElementHeader *header = COL_HEADER_PTR(data, dataOffset);
            header->size = createElements ? (SIZETYPE)elementsNbr : 0;
            header->maxsize = (SIZETYPE)elementsNbr;
 
            dataOffset += sizeof(CElementHeader);
 
            if (createElements)
                CreateElement((TYPE *)(data+dataOffset), elementsNbr);
 
            dataOffset += elementsNbr*sizeof(TYPE);
        }
 
        return entriesNbr-1;
    }
 
    template<class TYPE, class SIZETYPE>
    unsigned int CSimpleCollection<TYPE, SIZETYPE>::AddElementInEntry(unsigned int index, const TYPE& newElement, unsigned int newCreatedElementNumber, bool createExtraElements)
    {
        if (index < entriesNbr)
        {
            SIZET offset = offsetArray[index];
            CElementHeader *header = COL_HEADER_PTR(data, offset);
            if (header->size < header->maxsize)
            {
                TYPE *element = COL_TYPE_PTR(data, offset); // first element
                element += header->size++; // Get element, create it, and copy it
                CreateElement(element, 1);
                *element = newElement;
 
                return header->size;
            }
 
            // We have header->size = header->maxsize;
 
            if (!newCreatedElementNumber)
                newCreatedElementNumber = 1;
 
            unsigned int newElementOffset = header->size;
            TYPE *element = InitElementsSize(index, newElementOffset+newCreatedElementNumber, createExtraElements ? COL_CREATE_ELEMENTS : 0); // Header becomes invalid
            element += newElementOffset;
 
            if (!createExtraElements) // Create at least the element to add now, if not created above
            {
                CreateElement(element, 1);
 
                SIZET indexOffset = offsetArray[index];
                header = COL_HEADER_PTR(data, indexOffset);
                XASSERT(header->size == newElementOffset); // The elements where not create and the size remains the same
                header->size++;
            }
 
            *element = newElement;
            return newElementOffset;
        }
 
        XASSERT(0);
        return 0;
    }
 
    template<class TYPE, class SIZETYPE>
    unsigned int CSimpleCollection<TYPE, SIZETYPE>::RemoveElementInEntry(unsigned int index, unsigned elementIndex)
    {
        if (index < entriesNbr)
        {
            SIZET offset = offsetArray[index];
            CElementHeader *header = COL_HEADER_PTR(data, offset);
            if (elementIndex < header->size)
            {
                TYPE *element = COL_TYPE_PTR(data, offset); // first element
                element += elementIndex;
                DestroyElement(element, 1);
 
                // Move the others elements
                if (elementIndex+1 < header->size)
                    xmemcpy_s(element, (header->size-elementIndex)*sizeof(TYPE), element+1, (header->size-(elementIndex+1))*sizeof(TYPE));
 
                header->size--;
                return header->size;
            }
 
            XASSERT(0);
            return 0;
        }
 
        XASSERT(0);
        return 0;
    }
 
    /////////////////////////////////////////////////////
    // CObjectCollection
    //
    // This class handles an array of entries
    // each entries contains a given number of object elements
    // object constructor and destructors are called
    // All is stored in a raw array
    //
 
    template<class TYPE, class SIZETYPE>
    class CObjectCollection : public CSimpleCollection<TYPE, SIZETYPE>
    {
    private:
        
        virtual void DestroyElement(TYPE *element, unsigned int number);
        virtual void CreateElement(TYPE *element, unsigned int number);
 
        virtual void DestroyEntries(unsigned int first, unsigned int number);
        virtual void CreateEntries(unsigned int first, unsigned int number);
 
        virtual void CopyEntry(TYPE *dst, const TYPE *src, int elementNbr);
        virtual void CopyEntries(const CSimpleCollection<TYPE, SIZETYPE>& collection, unsigned int dstindex = 0);
 
    public:
        void Serialize(CXArchive& archive);
        virtual ~CObjectCollection();
    };
 
 
    template<class TYPE, class SIZETYPE>
    CObjectCollection<TYPE, SIZETYPE>::~CObjectCollection()
    {
        CSimpleCollection<TYPE, SIZETYPE>::Free();  // Virtual function DestroyEntries not called by CSimpleCollection destructor
    }
 
    template<class TYPE, class SIZETYPE>
    void CObjectCollection<TYPE, SIZETYPE>::Serialize(CXArchive& archive)
    {
        XASSERT(0);
    }
 
    // Destroy a particular element
    template<class TYPE, class SIZETYPE>
    inline void CObjectCollection<TYPE, SIZETYPE>::DestroyElement(TYPE *element, unsigned int number)
    {
    #ifdef COLLECTION_STATS
        curElements -= number;
    #endif
 
        for (unsigned int i=0; i<number; i++)
        {
            element->~TYPE();
            element++;
        }
    }
 
    // Destroy collection elements
    template<class TYPE, class SIZETYPE>
    void CObjectCollection<TYPE, SIZETYPE>::DestroyEntries(unsigned int first, unsigned int number)
    {
        SIZET offset;
        typename CSimpleCollection<TYPE, SIZETYPE>::CElementHeader *header;
 
        number += first;
        for (unsigned int i=first; i<number; i++)
        {
            offset = this->offsetArray[i];
            header = COL_HEADER_PTR(this->data, offset);
        
            DestroyElement(COL_TYPE_PTR(this->data, offset), header->size);
        }
    }
 
    // Create a particular elements
    template<class TYPE, class SIZETYPE>
    inline void CObjectCollection<TYPE, SIZETYPE>::CreateElement(TYPE *element, unsigned int number)
    {
    #ifdef COLLECTION_STATS
        curElements += number;
        UpdateStatistics(); // update maxElements / maxEntries
    #endif
 
        for (unsigned i=0;  i<number; i++)
        {
    #pragma push_macro("new")
    #undef new
            xConstruct(TYPE, element);
    #pragma pop_macro("new")
            element++;
        }
    }
 
    // Create collection elements
    template<class TYPE, class SIZETYPE>
    void CObjectCollection<TYPE, SIZETYPE>::CreateEntries(unsigned int first, unsigned int number)
    {
        SIZET offset;
        typename CSimpleCollection<TYPE, SIZETYPE>::CElementHeader *header;
 
        number += first;
        for (unsigned int i=first; i<number; i++)
        {
            offset = this->offsetArray[i];
            header = COL_HEADER_PTR(this->data, offset);
        
            CreateElement(COL_TYPE_PTR(this->data, offset), header->size);
        }
    }
 
    template<class TYPE, class SIZETYPE>
    void CObjectCollection<TYPE, SIZETYPE>::CopyEntry(TYPE *dst, const TYPE *src, int elementNbr)
    {
        for (int i=0; i<elementNbr; i++)
        {
            *dst = src[i];
            dst++;
        }
    }
 
    template<class TYPE, class SIZETYPE>
    void CObjectCollection<TYPE, SIZETYPE>::CopyEntries(const CSimpleCollection<TYPE, SIZETYPE>& collection, unsigned int dstindex)
    {
        XASSERT(dstindex+collection.entriesNbr <= this->entriesNbr); // Elements must have been created and preallocated
 
        unsigned int i, j;
        typename CSimpleCollection<TYPE, SIZETYPE>::CElementHeader *srcheader;
        SIZET srcoffset, dstoffset;
        TYPE *srctype, *dsttype;
 
        CreateEntries(dstindex, collection.entriesNbr);
        for (i = 0; i<collection.entriesNbr; i++)
        {
            srcoffset = collection.offsetArray[i];
            dstoffset = this->offsetArray[dstindex+i];
        
            srcheader = COL_HEADER_PTR(collection.data, srcoffset);
            srctype = COL_TYPE_PTR(collection.data, srcoffset);
            dsttype = COL_TYPE_PTR(this->data, dstoffset);
 
            for (j=0; j<srcheader->size; j++)
            {
                *dsttype = *srctype;
                srctype++;
                dsttype++;
            }
        }
    }
 
END_MOOTOOLS_NAMESPACE
 
#endif // CCOLLECTION_CLASS_H