//========= 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 UTLARRAY_H
#define UTLARRAY_H

#ifdef _WIN32
#pragma once
#endif

#include "tier0/dbg.h"
#include "tier0/platform.h"
#include "vstdlib/random.h"

#define FOR_EACH_ARRAY(vecName, iteratorName)                      \
    for (int iteratorName = 0;                                     \
         (vecName).IsUtlArray && iteratorName < (vecName).Count(); \
         iteratorName++)
#define FOR_EACH_ARRAY_BACK(vecName, iteratorName) \
    for (int iteratorName = (vecName).Count() - 1; \
         (vecName).IsUtlArray && iteratorName >= 0; iteratorName--)

// utlarray derives from this so we can do the type check above
struct base_array_t {
   public:
    static const bool IsUtlArray = true;  // Used to match this at compiletime
};

#if defined(GNUC) && defined(DEBUG)
// gcc in debug doesn't optimize away the need for the storage of IsUtlArray so
// make one here
//  as this is in a shared header use SELECTANY to make it throw away the dupe
//  symbols
const bool base_array_t::IsUtlArray SELECTANY;
#endif

//-----------------------------------------------------------------------------
template <class T, size_t MAX_SIZE>
class CUtlArray : public base_array_t {
   public:
    typedef T ElemType_t;
    typedef T* iterator;
    typedef const T* const_iterator;

    CUtlArray();
    CUtlArray(T* pMemory, size_t count);
    ~CUtlArray();

    CUtlArray<T, MAX_SIZE>& operator=(const CUtlArray<T, MAX_SIZE>& other);
    CUtlArray(CUtlArray const& vec);

    // element access
    T& operator[](int i);
    const T& operator[](int i) const;
    T& Element(int i);
    const T& Element(int i) 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();
    const_iterator begin() const;
    iterator end();
    const_iterator end() const;

    T* Base();
    const T* Base() const;

    // Returns the number of elements in the array, NumAllocated() is included
    // for consistency with UtlVector
    int Count() const;
    int NumAllocated() const;

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

    void CopyArray(const T* pArray, size_t count);

    void Swap(CUtlArray<T, MAX_SIZE>& vec);

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

    bool HasElement(const T& src) const;

    // calls delete on each element in it.
    void DeleteElements();

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

   protected:
    T m_Memory[MAX_SIZE];
};

//-----------------------------------------------------------------------------
// constructor, destructor
//-----------------------------------------------------------------------------
template <typename T, size_t MAX_SIZE>
inline CUtlArray<T, MAX_SIZE>::CUtlArray() {}

template <typename T, size_t MAX_SIZE>
inline CUtlArray<T, MAX_SIZE>::CUtlArray(T* pMemory, size_t count) {
    CopyArray(pMemory, count);
}

template <typename T, size_t MAX_SIZE>
inline CUtlArray<T, MAX_SIZE>::~CUtlArray() {}

template <typename T, size_t MAX_SIZE>
inline CUtlArray<T, MAX_SIZE>& CUtlArray<T, MAX_SIZE>::operator=(
    const CUtlArray<T, MAX_SIZE>& other) {
    if (this != &other) {
        for (size_t n = 0; n < MAX_SIZE; ++n) {
            m_Memory[n] = other.m_Memory[n];
        }
    }
    return *this;
}

template <typename T, size_t MAX_SIZE>
inline CUtlArray<T, MAX_SIZE>::CUtlArray(CUtlArray const& vec) {
    for (size_t n = 0; n < MAX_SIZE; ++n) {
        m_Memory[n] = vec.m_Memory[n];
    }
}

template <typename T, size_t MAX_SIZE>
typename CUtlArray<T, MAX_SIZE>::iterator CUtlArray<T, MAX_SIZE>::begin() {
    return Base();
}

template <typename T, size_t MAX_SIZE>
typename CUtlArray<T, MAX_SIZE>::const_iterator CUtlArray<T, MAX_SIZE>::begin()
    const {
    return Base();
}

template <typename T, size_t MAX_SIZE>
typename CUtlArray<T, MAX_SIZE>::iterator CUtlArray<T, MAX_SIZE>::end() {
    return Base() + Count();
}

template <typename T, size_t MAX_SIZE>
typename CUtlArray<T, MAX_SIZE>::const_iterator CUtlArray<T, MAX_SIZE>::end()
    const {
    return Base() + Count();
}

template <typename T, size_t MAX_SIZE>
inline T* CUtlArray<T, MAX_SIZE>::Base() {
    return &m_Memory[0];
}

template <typename T, size_t MAX_SIZE>
inline const T* CUtlArray<T, MAX_SIZE>::Base() const {
    return &m_Memory[0];
}

//-----------------------------------------------------------------------------
// element access
//-----------------------------------------------------------------------------
template <typename T, size_t MAX_SIZE>
inline T& CUtlArray<T, MAX_SIZE>::operator[](int i) {
    Assert(IsValidIndex(i));
    return m_Memory[i];
}

template <typename T, size_t MAX_SIZE>
inline const T& CUtlArray<T, MAX_SIZE>::operator[](int i) const {
    Assert(IsValidIndex(i));
    return m_Memory[i];
}

template <typename T, size_t MAX_SIZE>
inline T& CUtlArray<T, MAX_SIZE>::Element(int i) {
    Assert(IsValidIndex(i));
    return m_Memory[i];
}

template <typename T, size_t MAX_SIZE>
inline const T& CUtlArray<T, MAX_SIZE>::Element(int i) const {
    Assert(IsValidIndex(i));
    return m_Memory[i];
}

template <typename T, size_t MAX_SIZE>
inline T& CUtlArray<T, MAX_SIZE>::Random() {
    Assert(MAX_SIZE > 0);
    return m_Memory[RandomInt(0, MAX_SIZE - 1)];
}

template <typename T, size_t MAX_SIZE>
inline const T& CUtlArray<T, MAX_SIZE>::Random() const {
    Assert(MAX_SIZE > 0);
    return m_Memory[RandomInt(0, MAX_SIZE - 1)];
}

//-----------------------------------------------------------------------------
// Count
//-----------------------------------------------------------------------------
template <typename T, size_t MAX_SIZE>
inline int CUtlArray<T, MAX_SIZE>::Count() const {
    return (int)MAX_SIZE;
}

//-----------------------------------------------------------------------------
template <typename T, size_t MAX_SIZE>
inline int CUtlArray<T, MAX_SIZE>::NumAllocated() const {
    return (int)MAX_SIZE;
}

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

//-----------------------------------------------------------------------------
// Returns in invalid index
//-----------------------------------------------------------------------------
template <typename T, size_t MAX_SIZE>
inline int CUtlArray<T, MAX_SIZE>::InvalidIndex() {
    return -1;
}

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

    qsort(Base(), Count(), sizeof(T), (QSortCompareFunc_t)(pfnCompare));
}

template <typename T, size_t MAX_SIZE>
void CUtlArray<T, MAX_SIZE>::CopyArray(const T* pArray, size_t count) {
    Assert(count < MAX_SIZE);

    for (size_t n = 0; n < count; ++n) {
        m_Memory[n] = pArray[n];
    }
}

template <typename T, size_t MAX_SIZE>
void CUtlArray<T, MAX_SIZE>::Swap(CUtlArray<T, MAX_SIZE>& vec) {
    for (size_t n = 0; n < MAX_SIZE; ++n) {
        V_swap(m_Memory[n], vec.m_Memory[n]);
    }
}

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

template <typename T, size_t MAX_SIZE>
void CUtlArray<T, MAX_SIZE>::FillWithValue(const T& src) {
    for (int i = 0; i < Count(); i++) {
        Element(i) = src;
    }
}

template <typename T, size_t MAX_SIZE>
bool CUtlArray<T, MAX_SIZE>::HasElement(const T& src) const {
    return (Find(src) >= 0);
}

template <typename T, size_t MAX_SIZE>
inline void CUtlArray<T, MAX_SIZE>::DeleteElements() {
    for (int i = 0; i < MAX_SIZE; i++) {
        delete Element(i);
    }
}

#endif  // UTLARRAY_H