//========= Copyright Valve Corporation, All rights reserved. ============//
//
// Purpose:
//
// $NoKeywords: $
//
// A growable array class that maintains a free list and keeps elements
// in the same location
//=============================================================================//

#ifndef UTLVECTOR_H
#define UTLVECTOR_H

#ifdef _WIN32
#pragma once
#endif

#include <string.h>
#include "../tier0/dbg.h"
#include "../tier0/platform.h"
#include "../tier0/threadtools.h"
#include "../vstdlib/random.h"
#include "strtools.h"
#include "utlblockmemory.h"
#include "utlmemory.h"

#define FOR_EACH_VEC(vecName, iteratorName) \
    for (int iteratorName = 0; iteratorName < (vecName).Count(); iteratorName++)
#define FOR_EACH_VEC_BACK(vecName, iteratorName)                      \
    for (int iteratorName = (vecName).Count() - 1; iteratorName >= 0; \
         iteratorName--)

//-----------------------------------------------------------------------------
// The CUtlVector class:
// A growable array class which doubles in size by default.
// It will always keep all elements consecutive in memory, and may move the
// elements around in memory (via a PvRealloc) when elements are inserted or
// removed. Clients should therefore refer to the elements of the vector
// by index (they should *never* maintain pointers to elements in the vector).
//-----------------------------------------------------------------------------
template <class T, class A = CUtlMemory<T> >
class CUtlVector {
    typedef A CAllocator;

   public:
    typedef T ElemType_t;
    typedef T* iterator;
    typedef const T* const_iterator;

    // constructor, destructor
    explicit CUtlVector(int growSize = 0, int initSize = 0);
    explicit CUtlVector(T* pMemory, int allocationCount, int numElements = 0);
    ~CUtlVector();

    // Copy the array.
    CUtlVector<T, A>& operator=(const CUtlVector<T, A>& other);

    // element access
    T& operator[](int i);
    const T& operator[](int i) const;
    T& Element(int i);
    const T& Element(int i) const;
    T& Head();
    const T& Head() const;
    T& Tail();
    const T& Tail() const;
    T& Random();
    const T& Random() const;

    // STL compatible member functions. These allow easier use of std::sort
    // and they are forward compatible with the C++ 11 range-based for loops.
    iterator begin() { return Base(); }
    const_iterator begin() const { return Base(); }
    iterator end() { return Base() + Count(); }
    const_iterator end() const { return Base() + Count(); }

    // Gets the base address (can change when adding elements!)
    T* Base() { return m_Memory.Base(); }
    const T* Base() const { return m_Memory.Base(); }

    // Returns the number of elements in the vector
    // SIZE IS DEPRECATED!
    int Count() const;
    int Size() const;  // don't use me!

    /// are there no elements? For compatibility with lists.
    inline bool IsEmpty(void) const { return (Count() == 0); }

    // Is element index valid?
    bool IsValidIndex(int i) const;
    static int InvalidIndex();

    // Adds an element, uses default constructor
    int AddToHead();
    int AddToTail();
    int InsertBefore(int elem);
    int InsertAfter(int elem);

    // Adds an element, uses copy constructor
    int AddToHead(const T& src);
    int AddToTail(const T& src);
    int InsertBefore(int elem, const T& src);
    int InsertAfter(int elem, const T& src);

    // Adds multiple elements, uses default constructor
    int AddMultipleToHead(int num);
    int AddMultipleToTail(int num, const T* pToCopy = NULL);
    int InsertMultipleBefore(
        int elem, int num,
        const T* pToCopy =
            NULL);  // If pToCopy is set, then it's an array of length 'num' and
    int InsertMultipleAfter(int elem, int num);

    // Calls RemoveAll() then AddMultipleToTail.
    void SetSize(int size);
    void SetCount(int count);
    void SetCountNonDestructively(
        int count);  // sets count by adding or removing elements to tail TODO:
                     // This should probably be the default behavior for SetCount

    // Calls SetSize and copies each element.
    void CopyArray(const T* pArray, int size);

    // Fast swap
    void Swap(CUtlVector<T, A>& vec);

    // Add the specified array to the tail.
    int AddVectorToTail(CUtlVector<T, A> const& src);

    // Finds an element (element needs operator== defined)
    int Find(const T& src) const;

    bool HasElement(const T& src) const;

    // Makes sure we have enough memory allocated to store a requested # of
    // elements
    void EnsureCapacity(int num);

    // Makes sure we have at least this many elements
    void EnsureCount(int num);

    // Element removal
    void FastRemove(int elem);               // doesn't preserve order
    void Remove(int elem);                   // preserves order, shifts elements
    bool FindAndRemove(const T& src);        // removes first occurrence of src,
                                             // preserves order, shifts elements
    bool FindAndFastRemove(const T& src);    // removes first occurrence of src,
                                             // doesn't preserve order
    void RemoveMultiple(int elem, int num);  // preserves order, shifts elements
    void RemoveMultipleFromHead(int num);    // removes num elements from tail
    void RemoveMultipleFromTail(int num);    // removes num elements from tail
    void RemoveAll();                        // doesn't deallocate memory

    // Memory deallocation
    void Purge();

    // Purges the list and calls delete on each element in it.
    void PurgeAndDeleteElements();

    // Compacts the vector to the number of elements actually in use
    void Compact();

    // Set the size by which it grows when it needs to allocate more memory.
    void SetGrowSize(int size) { m_Memory.SetGrowSize(size); }

    int NumAllocated()
        const;  // Only use this if you really know what you're doing!

    void Sort(int(__cdecl* pfnCompare)(const T*, const T*));

    void Shuffle(IUniformRandomStream* pSteam = NULL);

#ifdef DBGFLAG_VALIDATE
    void Validate(CValidator& validator,
                  char* pchName);  // Validate our internal structures
#endif                             // DBGFLAG_VALIDATE

   protected:
    // Grows the vector
    void GrowVector(int num = 1);

    // Shifts elements....
    void ShiftElementsRight(int elem, int num = 1);
    void ShiftElementsLeft(int elem, int num = 1);

    CAllocator m_Memory;
    int m_Size;

#ifndef _X360
    // For easier access to the elements through the debugger
    // it's in release builds so this can be used in libraries correctly
    T* m_pElements;

    inline void ResetDbgInfo() { m_pElements = Base(); }
#else
    inline void ResetDbgInfo() {}
#endif

   private:
    // Can't copy this unless we explicitly do it!
    // Use CCopyableUtlVector<T> to get this functionality
    CUtlVector(CUtlVector const& vec);
};

// this is kind of ugly, but until C++ gets templatized typedefs in C++0x, it's
// our only choice
template <class T>
class CUtlBlockVector : public CUtlVector<T, CUtlBlockMemory<T, int> > {
   public:
    explicit CUtlBlockVector(int growSize = 0, int initSize = 0)
        : CUtlVector<T, CUtlBlockMemory<T, int> >(growSize, initSize) {}

   private:
    // Private and unimplemented because iterator semantics are not currently
    // supported on CUtlBlockVector, due to its non-contiguous allocations.
    // typename is require to disambiguate iterator as a type versus other
    // possibilities.
    typedef CUtlVector<T, CUtlBlockMemory<T, int> > Base;
    typename Base::iterator begin();
    typename Base::const_iterator begin() const;
    typename Base::iterator end();
    typename Base::const_iterator end() const;
};

//-----------------------------------------------------------------------------
// The CUtlVectorFixed class:
// A array class with a fixed allocation scheme
//-----------------------------------------------------------------------------

template <class BASE_UTLVECTOR, class MUTEX_TYPE = CThreadFastMutex>
class CUtlVectorMT : public BASE_UTLVECTOR, public MUTEX_TYPE {
    typedef BASE_UTLVECTOR BaseClass;

   public:
    MUTEX_TYPE Mutex_t;

    // constructor, destructor
    explicit CUtlVectorMT(int growSize = 0, int initSize = 0)
        : BaseClass(growSize, initSize) {}
    explicit CUtlVectorMT(typename BaseClass::ElemType_t* pMemory,
                          int numElements)
        : BaseClass(pMemory, numElements) {}
};

//-----------------------------------------------------------------------------
// The CUtlVectorFixed class:
// A array class with a fixed allocation scheme
//-----------------------------------------------------------------------------
template <class T, size_t MAX_SIZE>
class CUtlVectorFixed : public CUtlVector<T, CUtlMemoryFixed<T, MAX_SIZE> > {
    typedef CUtlVector<T, CUtlMemoryFixed<T, MAX_SIZE> > BaseClass;

   public:
    // constructor, destructor
    explicit CUtlVectorFixed(int growSize = 0, int initSize = 0)
        : BaseClass(growSize, initSize) {}
    explicit CUtlVectorFixed(T* pMemory, int numElements)
        : BaseClass(pMemory, numElements) {}
};

//-----------------------------------------------------------------------------
// The CUtlVectorFixedGrowable class:
// A array class with a fixed allocation scheme backed by a dynamic one
//-----------------------------------------------------------------------------
template <class T, size_t MAX_SIZE>
class CUtlVectorFixedGrowable
    : public CUtlVector<T, CUtlMemoryFixedGrowable<T, MAX_SIZE> > {
    typedef CUtlVector<T, CUtlMemoryFixedGrowable<T, MAX_SIZE> > BaseClass;

   public:
    // constructor, destructor
    explicit CUtlVectorFixedGrowable(int growSize = 0)
        : BaseClass(growSize, MAX_SIZE) {}
};

//-----------------------------------------------------------------------------
// The CUtlVectorConservative class:
// A array class with a conservative allocation scheme
//-----------------------------------------------------------------------------
template <class T>
class CUtlVectorConservative
    : public CUtlVector<T, CUtlMemoryConservative<T> > {
    typedef CUtlVector<T, CUtlMemoryConservative<T> > BaseClass;

   public:
    // constructor, destructor
    explicit CUtlVectorConservative(int growSize = 0, int initSize = 0)
        : BaseClass(growSize, initSize) {}
    explicit CUtlVectorConservative(T* pMemory, int numElements)
        : BaseClass(pMemory, numElements) {}
};

//-----------------------------------------------------------------------------
// The CUtlVectorUltra Conservative class:
// A array class with a very conservative allocation scheme, with customizable
// allocator Especialy useful if you have a lot of vectors that are sparse, or
// if you're carefully packing holders of vectors
//-----------------------------------------------------------------------------
#pragma warning(push)
#pragma warning(disable : 4200)  // warning C4200: nonstandard extension used :
                                 // zero-sized array in struct/union
#pragma warning( \
    disable : 4815)  // warning C4815: 'staticData' : zero-sized array in stack
                     // object will have no elements

class CUtlVectorUltraConservativeAllocator {
   public:
    static void* Alloc(size_t nSize) { return malloc(nSize); }

    static void* Realloc(void* pMem, size_t nSize) {
        return realloc(pMem, nSize);
    }

    static void Free(void* pMem) { free(pMem); }

    static size_t GetSize(void* pMem) { return mallocsize(pMem); }
};

template <typename T, typename A = CUtlVectorUltraConservativeAllocator>
class CUtlVectorUltraConservative : private A {
   public:
    CUtlVectorUltraConservative() { m_pData = StaticData(); }

    ~CUtlVectorUltraConservative() { RemoveAll(); }

    int Count() const { return m_pData->m_Size; }

    static int InvalidIndex() { return -1; }

    inline bool IsValidIndex(int i) const { return (i >= 0) && (i < Count()); }

    T& operator[](int i) {
        Assert(IsValidIndex(i));
        return m_pData->m_Elements[i];
    }

    const T& operator[](int i) const {
        Assert(IsValidIndex(i));
        return m_pData->m_Elements[i];
    }

    T& Element(int i) {
        Assert(IsValidIndex(i));
        return m_pData->m_Elements[i];
    }

    const T& Element(int i) const {
        Assert(IsValidIndex(i));
        return m_pData->m_Elements[i];
    }

    void EnsureCapacity(int num) {
        int nCurCount = Count();
        if (num <= nCurCount) {
            return;
        }
        if (m_pData == StaticData()) {
            m_pData = (Data_t*)A::Alloc(sizeof(int) + (num * sizeof(T)));
            m_pData->m_Size = 0;
        } else {
            int nNeeded = sizeof(int) + (num * sizeof(T));
            int nHave = A::GetSize(m_pData);
            if (nNeeded > nHave) {
                m_pData = (Data_t*)A::Realloc(m_pData, nNeeded);
            }
        }
    }

    int AddToTail(const T& src) {
        int iNew = Count();
        EnsureCapacity(Count() + 1);
        m_pData->m_Elements[iNew] = src;
        m_pData->m_Size++;
        return iNew;
    }

    void RemoveAll() {
        if (Count()) {
            for (int i = m_pData->m_Size; --i >= 0;) {
                Destruct(&m_pData->m_Elements[i]);
            }
        }
        if (m_pData != StaticData()) {
            A::Free(m_pData);
            m_pData = StaticData();
        }
    }

    void PurgeAndDeleteElements() {
        if (m_pData != StaticData()) {
            for (int i = 0; i < m_pData->m_Size; i++) {
                delete Element(i);
            }
            RemoveAll();
        }
    }

    void FastRemove(int elem) {
        Assert(IsValidIndex(elem));

        Destruct(&Element(elem));
        if (Count() > 0) {
            if (elem != m_pData->m_Size - 1)
                memcpy(&Element(elem), &Element(m_pData->m_Size - 1),
                       sizeof(T));
            --m_pData->m_Size;
        }
        if (!m_pData->m_Size) {
            A::Free(m_pData);
            m_pData = StaticData();
        }
    }

    void Remove(int elem) {
        Destruct(&Element(elem));
        ShiftElementsLeft(elem);
        --m_pData->m_Size;
        if (!m_pData->m_Size) {
            A::Free(m_pData);
            m_pData = StaticData();
        }
    }

    int Find(const T& src) const {
        int nCount = Count();
        for (int i = 0; i < nCount; ++i) {
            if (Element(i) == src) return i;
        }
        return -1;
    }

    bool FindAndRemove(const T& src) {
        int elem = Find(src);
        if (elem != -1) {
            Remove(elem);
            return true;
        }
        return false;
    }

    bool FindAndFastRemove(const T& src) {
        int elem = Find(src);
        if (elem != -1) {
            FastRemove(elem);
            return true;
        }
        return false;
    }

    struct Data_t {
        int m_Size;
        T m_Elements[0];
    };

    Data_t* m_pData;

   private:
    void ShiftElementsLeft(int elem, int num = 1) {
        int Size = Count();
        Assert(IsValidIndex(elem) || (Size == 0) || (num == 0));
        int numToMove = Size - elem - num;
        if ((numToMove > 0) && (num > 0)) {
            Q_memmove(&Element(elem), &Element(elem + num),
                      numToMove * sizeof(T));

#ifdef _DEBUG
            Q_memset(&Element(Size - num), 0xDD, num * sizeof(T));
#endif
        }
    }

    static Data_t* StaticData() {
        static Data_t staticData;
        Assert(staticData.m_Size == 0);
        return &staticData;
    }
};

#pragma warning(pop)

//-----------------------------------------------------------------------------
// The CCopyableUtlVector class:
// A array class that allows copy construction (so you can nest a CUtlVector
// inside of another one of our containers)
//  WARNING - this class lets you copy construct which can be an expensive
//  operation if you don't carefully control when it happens
// Only use this when nesting a CUtlVector() inside of another one of our
// container classes (i.e a CUtlMap)
//-----------------------------------------------------------------------------
template <typename T, typename A = CUtlMemory<T> >
class CCopyableUtlVector : public CUtlVector<T, A> {
    typedef CUtlVector<T, A> BaseClass;

   public:
    explicit CCopyableUtlVector(int growSize = 0, int initSize = 0)
        : BaseClass(growSize, initSize) {}
    explicit CCopyableUtlVector(T* pMemory, int numElements)
        : BaseClass(pMemory, numElements) {}
    virtual ~CCopyableUtlVector() {}
    CCopyableUtlVector(CCopyableUtlVector const& vec) {
        this->CopyArray(vec.Base(), vec.Count());
    }
};

// TODO (Ilya): It seems like all the functions in CUtlVector are simple enough
// that they should be inlined.

//-----------------------------------------------------------------------------
// constructor, destructor
//-----------------------------------------------------------------------------
template <typename T, class A>
inline CUtlVector<T, A>::CUtlVector(int growSize, int initSize)
    : m_Memory(growSize, initSize), m_Size(0) {
    ResetDbgInfo();
}

template <typename T, class A>
inline CUtlVector<T, A>::CUtlVector(T* pMemory, int allocationCount,
                                    int numElements)
    : m_Memory(pMemory, allocationCount), m_Size(numElements) {
    ResetDbgInfo();
}

template <typename T, class A>
inline CUtlVector<T, A>::~CUtlVector() {
    Purge();
}

template <typename T, class A>
inline CUtlVector<T, A>& CUtlVector<T, A>::operator=(
    const CUtlVector<T, A>& other) {
    int nCount = other.Count();
    SetSize(nCount);
    for (int i = 0; i < nCount; i++) {
        (*this)[i] = other[i];
    }
    return *this;
}

#ifdef STAGING_ONLY
inline void StagingUtlVectorBoundsCheck(int i, int size) {
    if ((unsigned)i >= (unsigned)size) {
        Msg("Array access error: %d / %d\n", i, size);
        DebuggerBreak();
    }
}

#else
#define StagingUtlVectorBoundsCheck(_i, _size)
#endif

//-----------------------------------------------------------------------------
// element access
//-----------------------------------------------------------------------------
template <typename T, class A>
inline T& CUtlVector<T, A>::operator[](int i) {
    // Do an inline unsigned check for maximum debug-build performance.
    Assert((unsigned)i < (unsigned)m_Size);
    StagingUtlVectorBoundsCheck(i, m_Size);
    return m_Memory[i];
}

template <typename T, class A>
inline const T& CUtlVector<T, A>::operator[](int i) const {
    // Do an inline unsigned check for maximum debug-build performance.
    Assert((unsigned)i < (unsigned)m_Size);
    StagingUtlVectorBoundsCheck(i, m_Size);
    return m_Memory[i];
}

template <typename T, class A>
inline T& CUtlVector<T, A>::Element(int i) {
    // Do an inline unsigned check for maximum debug-build performance.
    Assert((unsigned)i < (unsigned)m_Size);
    StagingUtlVectorBoundsCheck(i, m_Size);
    return m_Memory[i];
}

template <typename T, class A>
inline const T& CUtlVector<T, A>::Element(int i) const {
    // Do an inline unsigned check for maximum debug-build performance.
    Assert((unsigned)i < (unsigned)m_Size);
    StagingUtlVectorBoundsCheck(i, m_Size);
    return m_Memory[i];
}

template <typename T, class A>
inline T& CUtlVector<T, A>::Head() {
    Assert(m_Size > 0);
    StagingUtlVectorBoundsCheck(0, m_Size);
    return m_Memory[0];
}

template <typename T, class A>
inline const T& CUtlVector<T, A>::Head() const {
    Assert(m_Size > 0);
    StagingUtlVectorBoundsCheck(0, m_Size);
    return m_Memory[0];
}

template <typename T, class A>
inline T& CUtlVector<T, A>::Tail() {
    Assert(m_Size > 0);
    StagingUtlVectorBoundsCheck(0, m_Size);
    return m_Memory[m_Size - 1];
}

template <typename T, class A>
inline const T& CUtlVector<T, A>::Tail() const {
    Assert(m_Size > 0);
    StagingUtlVectorBoundsCheck(0, m_Size);
    return m_Memory[m_Size - 1];
}

//-----------------------------------------------------------------------------
// Count
//-----------------------------------------------------------------------------
template <typename T, class A>
inline int CUtlVector<T, A>::Size() const {
    return m_Size;
}

template <typename T, class A>
inline T& CUtlVector<T, A>::Random() {
    Assert(m_Size > 0);
    return m_Memory[RandomInt(0, m_Size - 1)];
}

template <typename T, class A>
inline const T& CUtlVector<T, A>::Random() const {
    Assert(m_Size > 0);
    return m_Memory[RandomInt(0, m_Size - 1)];
}

//-----------------------------------------------------------------------------
// Shuffle - Knuth/Fisher-Yates
//-----------------------------------------------------------------------------
template <typename T, class A>
void CUtlVector<T, A>::Shuffle(IUniformRandomStream* pSteam) {
    for (int i = 0; i < m_Size; i++) {
        int j = pSteam ? pSteam->RandomInt(i, m_Size - 1)
                       : RandomInt(i, m_Size - 1);
        if (i != j) {
            V_swap(m_Memory[i], m_Memory[j]);
        }
    }
}

template <typename T, class A>
inline int CUtlVector<T, A>::Count() const {
    return m_Size;
}

//-----------------------------------------------------------------------------
// Is element index valid?
//-----------------------------------------------------------------------------
template <typename T, class A>
inline bool CUtlVector<T, A>::IsValidIndex(int i) const {
    return (i >= 0) && (i < m_Size);
}

//-----------------------------------------------------------------------------
// Returns in invalid index
//-----------------------------------------------------------------------------
template <typename T, class A>
inline int CUtlVector<T, A>::InvalidIndex() {
    return -1;
}

//-----------------------------------------------------------------------------
// Grows the vector
//-----------------------------------------------------------------------------
template <typename T, class A>
void CUtlVector<T, A>::GrowVector(int num) {
    if (m_Size + num > m_Memory.NumAllocated()) {
        MEM_ALLOC_CREDIT_CLASS();
        m_Memory.Grow(m_Size + num - m_Memory.NumAllocated());
    }

    m_Size += num;
    ResetDbgInfo();
}

//-----------------------------------------------------------------------------
// Sorts the vector
//-----------------------------------------------------------------------------
template <typename T, class A>
void CUtlVector<T, A>::Sort(int(__cdecl* pfnCompare)(const T*, const T*)) {
    typedef int(__cdecl * QSortCompareFunc_t)(const void*, const void*);
    if (Count() <= 1) return;

    if (Base()) {
        qsort(Base(), Count(), sizeof(T), (QSortCompareFunc_t)(pfnCompare));
    } else {
        Assert(0);
        // this path is untested
        // if you want to sort vectors that use a non-sequential memory
        // allocator, you'll probably want to patch in a quicksort algorithm
        // here I just threw in this bubble sort to have something just in
        // case...

        for (int i = m_Size - 1; i >= 0; --i) {
            for (int j = 1; j <= i; ++j) {
                if (pfnCompare(&Element(j - 1), &Element(j)) < 0) {
                    V_swap(Element(j - 1), Element(j));
                }
            }
        }
    }
}

//-----------------------------------------------------------------------------
// Makes sure we have enough memory allocated to store a requested # of elements
//-----------------------------------------------------------------------------
template <typename T, class A>
void CUtlVector<T, A>::EnsureCapacity(int num) {
    MEM_ALLOC_CREDIT_CLASS();
    m_Memory.EnsureCapacity(num);
    ResetDbgInfo();
}

//-----------------------------------------------------------------------------
// Makes sure we have at least this many elements
//-----------------------------------------------------------------------------
template <typename T, class A>
void CUtlVector<T, A>::EnsureCount(int num) {
    if (Count() < num) AddMultipleToTail(num - Count());
}

//-----------------------------------------------------------------------------
// Shifts elements
//-----------------------------------------------------------------------------
template <typename T, class A>
void CUtlVector<T, A>::ShiftElementsRight(int elem, int num) {
    Assert(IsValidIndex(elem) || (m_Size == 0) || (num == 0));
    int numToMove = m_Size - elem - num;
    if ((numToMove > 0) && (num > 0))
        Q_memmove(&Element(elem + num), &Element(elem), numToMove * sizeof(T));
}

template <typename T, class A>
void CUtlVector<T, A>::ShiftElementsLeft(int elem, int num) {
    Assert(IsValidIndex(elem) || (m_Size == 0) || (num == 0));
    int numToMove = m_Size - elem - num;
    if ((numToMove > 0) && (num > 0)) {
        Q_memmove(&Element(elem), &Element(elem + num), numToMove * sizeof(T));

#ifdef _DEBUG
        Q_memset(&Element(m_Size - num), 0xDD, num * sizeof(T));
#endif
    }
}

//-----------------------------------------------------------------------------
// Adds an element, uses default constructor
//-----------------------------------------------------------------------------
template <typename T, class A>
inline int CUtlVector<T, A>::AddToHead() {
    return InsertBefore(0);
}

template <typename T, class A>
inline int CUtlVector<T, A>::AddToTail() {
    return InsertBefore(m_Size);
}

template <typename T, class A>
inline int CUtlVector<T, A>::InsertAfter(int elem) {
    return InsertBefore(elem + 1);
}

template <typename T, class A>
int CUtlVector<T, A>::InsertBefore(int elem) {
    // Can insert at the end
    Assert((elem == Count()) || IsValidIndex(elem));

    GrowVector();
    ShiftElementsRight(elem);
    Construct(&Element(elem));
    return elem;
}

//-----------------------------------------------------------------------------
// Adds an element, uses copy constructor
//-----------------------------------------------------------------------------
template <typename T, class A>
inline int CUtlVector<T, A>::AddToHead(const T& src) {
    // Can't insert something that's in the list... reallocation may hose us
    Assert((Base() == NULL) || (&src < Base()) || (&src >= (Base() + Count())));
    return InsertBefore(0, src);
}

template <typename T, class A>
inline int CUtlVector<T, A>::AddToTail(const T& src) {
    // Can't insert something that's in the list... reallocation may hose us
    Assert((Base() == NULL) || (&src < Base()) || (&src >= (Base() + Count())));
    return InsertBefore(m_Size, src);
}

template <typename T, class A>
inline int CUtlVector<T, A>::InsertAfter(int elem, const T& src) {
    // Can't insert something that's in the list... reallocation may hose us
    Assert((Base() == NULL) || (&src < Base()) || (&src >= (Base() + Count())));
    return InsertBefore(elem + 1, src);
}

template <typename T, class A>
int CUtlVector<T, A>::InsertBefore(int elem, const T& src) {
    // Can't insert something that's in the list... reallocation may hose us
    Assert((Base() == NULL) || (&src < Base()) || (&src >= (Base() + Count())));

    // Can insert at the end
    Assert((elem == Count()) || IsValidIndex(elem));

    GrowVector();
    ShiftElementsRight(elem);
    CopyConstruct(&Element(elem), src);
    return elem;
}

//-----------------------------------------------------------------------------
// Adds multiple elements, uses default constructor
//-----------------------------------------------------------------------------
template <typename T, class A>
inline int CUtlVector<T, A>::AddMultipleToHead(int num) {
    return InsertMultipleBefore(0, num);
}

template <typename T, class A>
inline int CUtlVector<T, A>::AddMultipleToTail(int num, const T* pToCopy) {
    // Can't insert something that's in the list... reallocation may hose us
    Assert((Base() == NULL) || !pToCopy || (pToCopy + num < Base()) ||
           (pToCopy >= (Base() + Count())));

    return InsertMultipleBefore(m_Size, num, pToCopy);
}

template <typename T, class A>
int CUtlVector<T, A>::InsertMultipleAfter(int elem, int num) {
    return InsertMultipleBefore(elem + 1, num);
}

template <typename T, class A>
void CUtlVector<T, A>::SetCount(int count) {
    RemoveAll();
    AddMultipleToTail(count);
}

template <typename T, class A>
inline void CUtlVector<T, A>::SetSize(int size) {
    SetCount(size);
}

template <typename T, class A>
void CUtlVector<T, A>::SetCountNonDestructively(int count) {
    int delta = count - m_Size;
    if (delta > 0)
        AddMultipleToTail(delta);
    else if (delta < 0)
        RemoveMultipleFromTail(-delta);
}

template <typename T, class A>
void CUtlVector<T, A>::CopyArray(const T* pArray, int size) {
    // Can't insert something that's in the list... reallocation may hose us
    Assert((Base() == NULL) || !pArray || (Base() >= (pArray + size)) ||
           (pArray >= (Base() + Count())));

    SetSize(size);
    for (int i = 0; i < size; i++) {
        (*this)[i] = pArray[i];
    }
}

template <typename T, class A>
void CUtlVector<T, A>::Swap(CUtlVector<T, A>& vec) {
    m_Memory.Swap(vec.m_Memory);
    V_swap(m_Size, vec.m_Size);

#ifndef _X360
    V_swap(m_pElements, vec.m_pElements);
#endif
}

template <typename T, class A>
int CUtlVector<T, A>::AddVectorToTail(CUtlVector const& src) {
    Assert(&src != this);

    int base = Count();

    // Make space.
    AddMultipleToTail(src.Count());

    // Copy the elements.
    for (int i = 0; i < src.Count(); i++) {
        (*this)[base + i] = src[i];
    }

    return base;
}

template <typename T, class A>
inline int CUtlVector<T, A>::InsertMultipleBefore(int elem, int num,
                                                  const T* pToInsert) {
    if (num == 0) return elem;

    // Can insert at the end
    Assert((elem == Count()) || IsValidIndex(elem));

    GrowVector(num);
    ShiftElementsRight(elem, num);

    // Invoke default constructors
    for (int i = 0; i < num; ++i) Construct(&Element(elem + i));

    // Copy stuff in?
    if (pToInsert) {
        for (int i = 0; i < num; i++) {
            Element(elem + i) = pToInsert[i];
        }
    }

    return elem;
}

//-----------------------------------------------------------------------------
// Finds an element (element needs operator== defined)
//-----------------------------------------------------------------------------
template <typename T, class A>
int CUtlVector<T, A>::Find(const T& src) const {
    for (int i = 0; i < Count(); ++i) {
        if (Element(i) == src) return i;
    }
    return -1;
}

template <typename T, class A>
bool CUtlVector<T, A>::HasElement(const T& src) const {
    return (Find(src) >= 0);
}

//-----------------------------------------------------------------------------
// Element removal
//-----------------------------------------------------------------------------
template <typename T, class A>
void CUtlVector<T, A>::FastRemove(int elem) {
    Assert(IsValidIndex(elem));

    Destruct(&Element(elem));
    if (m_Size > 0) {
        if (elem != m_Size - 1)
            memcpy(reinterpret_cast<void*>(&Element(elem)),
                   reinterpret_cast<void*>(&Element(m_Size - 1)), sizeof(T));
        --m_Size;
    }
}

template <typename T, class A>
void CUtlVector<T, A>::Remove(int elem) {
    Destruct(&Element(elem));
    ShiftElementsLeft(elem);
    --m_Size;
}

template <typename T, class A>
bool CUtlVector<T, A>::FindAndRemove(const T& src) {
    int elem = Find(src);
    if (elem != -1) {
        Remove(elem);
        return true;
    }
    return false;
}

template <typename T, class A>
bool CUtlVector<T, A>::FindAndFastRemove(const T& src) {
    int elem = Find(src);
    if (elem != -1) {
        FastRemove(elem);
        return true;
    }
    return false;
}

template <typename T, class A>
void CUtlVector<T, A>::RemoveMultiple(int elem, int num) {
    Assert(elem >= 0);
    Assert(elem + num <= Count());

    for (int i = elem + num; --i >= elem;) Destruct(&Element(i));

    ShiftElementsLeft(elem, num);
    m_Size -= num;
}

template <typename T, class A>
void CUtlVector<T, A>::RemoveMultipleFromHead(int num) {
    Assert(num <= Count());

    for (int i = num; --i >= 0;) Destruct(&Element(i));

    ShiftElementsLeft(0, num);
    m_Size -= num;
}

template <typename T, class A>
void CUtlVector<T, A>::RemoveMultipleFromTail(int num) {
    Assert(num <= Count());

    for (int i = m_Size - num; i < m_Size; i++) Destruct(&Element(i));

    m_Size -= num;
}

template <typename T, class A>
void CUtlVector<T, A>::RemoveAll() {
    for (int i = m_Size; --i >= 0;) {
        Destruct(&Element(i));
    }

    m_Size = 0;
}

//-----------------------------------------------------------------------------
// Memory deallocation
//-----------------------------------------------------------------------------

template <typename T, class A>
inline void CUtlVector<T, A>::Purge() {
    RemoveAll();
    m_Memory.Purge();
    ResetDbgInfo();
}

template <typename T, class A>
inline void CUtlVector<T, A>::PurgeAndDeleteElements() {
    for (int i = 0; i < m_Size; i++) {
        delete Element(i);
    }
    Purge();
}

template <typename T, class A>
inline void CUtlVector<T, A>::Compact() {
    m_Memory.Purge(m_Size);
}

template <typename T, class A>
inline int CUtlVector<T, A>::NumAllocated() const {
    return m_Memory.NumAllocated();
}

//-----------------------------------------------------------------------------
// Data and memory validation
//-----------------------------------------------------------------------------
#ifdef DBGFLAG_VALIDATE
template <typename T, class A>
void CUtlVector<T, A>::Validate(CValidator& validator, char* pchName) {
    validator.Push(typeid(*this).name(), this, pchName);

    m_Memory.Validate(validator, "m_Memory");

    validator.Pop();
}
#endif  // DBGFLAG_VALIDATE

// A vector class for storing pointers, so that the elements pointed to by the
// pointers are deleted on exit.
template <class T>
class CUtlVectorAutoPurge : public CUtlVector<T, CUtlMemory<T, int> > {
   public:
    ~CUtlVectorAutoPurge(void) { this->PurgeAndDeleteElements(); }
};

// easy string list class with dynamically allocated strings. For use with
// V_SplitString, etc. Frees the dynamic strings in destructor.
class CUtlStringList : public CUtlVectorAutoPurge<char*> {
   public:
    void CopyAndAddToTail(
        char const* pString)  // clone the string and add to the end
    {
        char* pNewStr = new char[1 + strlen(pString)];
        V_strcpy(pNewStr, pString);
        AddToTail(pNewStr);
    }

    static int __cdecl SortFunc(char* const* sz1, char* const* sz2) {
        return strcmp(*sz1, *sz2);
    }

    inline void PurgeAndDeleteElements() {
        for (int i = 0; i < m_Size; i++) {
            delete[] Element(i);
        }
        Purge();
    }

    ~CUtlStringList(void) { this->PurgeAndDeleteElements(); }
};

// <Sergiy> placing it here a few days before Cert to minimize disruption to the
// rest of codebase
class CSplitString : public CUtlVector<char*, CUtlMemory<char*, int> > {
   public:
    CSplitString(const char* pString, const char* pSeparator);
    CSplitString(const char* pString, const char** pSeparators,
                 int nSeparators);
    ~CSplitString();
    //
    // NOTE: If you want to make Construct() public and implement Purge() here,
    // you'll have to free m_szBuffer there
    //
   private:
    void Construct(const char* pString, const char** pSeparators,
                   int nSeparators);
    void PurgeAndDeleteElements();

   private:
    char* m_szBuffer;  // a copy of original string, with '\0' instead of
                       // separators
};

#endif  // CCVECTOR_H