//========= Copyright Valve Corporation, All rights reserved. ============//
//
// Purpose:
//
// $NoKeywords: $
//
// A stack based on a growable array
//=============================================================================//

#ifndef UTLSTACK_H
#define UTLSTACK_H

#include <assert.h>
#include <string.h>
#include "utlmemory.h"

//-----------------------------------------------------------------------------
// The CUtlStack class:
// A growable stack 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 realloc) when elements are pushed or
// popped. Clients should therefore refer to the elements of the stack
// by index (they should *never* maintain pointers to elements in the stack).
//-----------------------------------------------------------------------------

template <class T, class M = CUtlMemory<T> >
class CUtlStack {
   public:
    // constructor, destructor
    CUtlStack(int growSize = 0, int initSize = 0);
    ~CUtlStack();

    void CopyFrom(const CUtlStack<T, M>& from);

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

    // Gets the base address (can change when adding elements!)
    T* Base();
    T const* Base() const;

    // Looks at the stack top
    T& Top();
    T const& Top() const;

    // Size
    int Count() const;

    // Is element index valid?
    bool IsIdxValid(int i) const;

    // Adds an element, uses default constructor
    int Push();

    // Adds an element, uses copy constructor
    int Push(T const& src);

    // Pops the stack
    void Pop();
    void Pop(T& oldTop);
    void PopMultiple(int num);

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

    // Clears the stack, no deallocation
    void Clear();

    // Memory deallocation
    void Purge();

   private:
    // Grows the stack allocation
    void GrowStack();

    // For easier access to the elements through the debugger
    void ResetDbgInfo();

    M m_Memory;
    int m_Size;

    // For easier access to the elements through the debugger
    T* m_pElements;
};

//-----------------------------------------------------------------------------
// For easier access to the elements through the debugger
//-----------------------------------------------------------------------------

template <class T, class M>
inline void CUtlStack<T, M>::ResetDbgInfo() {
    m_pElements = m_Memory.Base();
}

//-----------------------------------------------------------------------------
// constructor, destructor
//-----------------------------------------------------------------------------

template <class T, class M>
CUtlStack<T, M>::CUtlStack(int growSize, int initSize)
    : m_Memory(growSize, initSize), m_Size(0) {
    ResetDbgInfo();
}

template <class T, class M>
CUtlStack<T, M>::~CUtlStack() {
    Purge();
}

//-----------------------------------------------------------------------------
// copy into
//-----------------------------------------------------------------------------

template <class T, class M>
void CUtlStack<T, M>::CopyFrom(const CUtlStack<T, M>& from) {
    Purge();
    EnsureCapacity(from.Count());
    for (int i = 0; i < from.Count(); i++) {
        Push(from[i]);
    }
}

//-----------------------------------------------------------------------------
// element access
//-----------------------------------------------------------------------------

template <class T, class M>
inline T& CUtlStack<T, M>::operator[](int i) {
    assert(IsIdxValid(i));
    return m_Memory[i];
}

template <class T, class M>
inline T const& CUtlStack<T, M>::operator[](int i) const {
    assert(IsIdxValid(i));
    return m_Memory[i];
}

template <class T, class M>
inline T& CUtlStack<T, M>::Element(int i) {
    assert(IsIdxValid(i));
    return m_Memory[i];
}

template <class T, class M>
inline T const& CUtlStack<T, M>::Element(int i) const {
    assert(IsIdxValid(i));
    return m_Memory[i];
}

//-----------------------------------------------------------------------------
// Gets the base address (can change when adding elements!)
//-----------------------------------------------------------------------------

template <class T, class M>
inline T* CUtlStack<T, M>::Base() {
    return m_Memory.Base();
}

template <class T, class M>
inline T const* CUtlStack<T, M>::Base() const {
    return m_Memory.Base();
}

//-----------------------------------------------------------------------------
// Returns the top of the stack
//-----------------------------------------------------------------------------

template <class T, class M>
inline T& CUtlStack<T, M>::Top() {
    assert(m_Size > 0);
    return Element(m_Size - 1);
}

template <class T, class M>
inline T const& CUtlStack<T, M>::Top() const {
    assert(m_Size > 0);
    return Element(m_Size - 1);
}

//-----------------------------------------------------------------------------
// Size
//-----------------------------------------------------------------------------

template <class T, class M>
inline int CUtlStack<T, M>::Count() const {
    return m_Size;
}

//-----------------------------------------------------------------------------
// Is element index valid?
//-----------------------------------------------------------------------------

template <class T, class M>
inline bool CUtlStack<T, M>::IsIdxValid(int i) const {
    return (i >= 0) && (i < m_Size);
}

//-----------------------------------------------------------------------------
// Grows the stack
//-----------------------------------------------------------------------------

template <class T, class M>
void CUtlStack<T, M>::GrowStack() {
    if (m_Size >= m_Memory.NumAllocated()) m_Memory.Grow();

    ++m_Size;

    ResetDbgInfo();
}

//-----------------------------------------------------------------------------
// Makes sure we have enough memory allocated to store a requested # of elements
//-----------------------------------------------------------------------------

template <class T, class M>
void CUtlStack<T, M>::EnsureCapacity(int num) {
    m_Memory.EnsureCapacity(num);
    ResetDbgInfo();
}

//-----------------------------------------------------------------------------
// Adds an element, uses default constructor
//-----------------------------------------------------------------------------

template <class T, class M>
int CUtlStack<T, M>::Push() {
    GrowStack();
    Construct(&Element(m_Size - 1));
    return m_Size - 1;
}

//-----------------------------------------------------------------------------
// Adds an element, uses copy constructor
//-----------------------------------------------------------------------------

template <class T, class M>
int CUtlStack<T, M>::Push(T const& src) {
    GrowStack();
    CopyConstruct(&Element(m_Size - 1), src);
    return m_Size - 1;
}

//-----------------------------------------------------------------------------
// Pops the stack
//-----------------------------------------------------------------------------

template <class T, class M>
void CUtlStack<T, M>::Pop() {
    assert(m_Size > 0);
    Destruct(&Element(m_Size - 1));
    --m_Size;
}

template <class T, class M>
void CUtlStack<T, M>::Pop(T& oldTop) {
    assert(m_Size > 0);
    oldTop = Top();
    Pop();
}

template <class T, class M>
void CUtlStack<T, M>::PopMultiple(int num) {
    assert(m_Size >= num);
    for (int i = 0; i < num; ++i) Destruct(&Element(m_Size - i - 1));
    m_Size -= num;
}

//-----------------------------------------------------------------------------
// Element removal
//-----------------------------------------------------------------------------

template <class T, class M>
void CUtlStack<T, M>::Clear() {
    for (int i = m_Size; --i >= 0;) Destruct(&Element(i));

    m_Size = 0;
}

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

template <class T, class M>
void CUtlStack<T, M>::Purge() {
    Clear();
    m_Memory.Purge();
    ResetDbgInfo();
}

#endif  // UTLSTACK_H