/*****************************************************************************
 * $LastChangedDate: 2011-04-23 21:07:07 -0400 (Sat, 23 Apr 2011) $
 * @file
 * @author  Jim E. Brooks  http://www.palomino3d.org
 * @brief   Stack template class.
 * @remarks A test was written for this.
 * @verbatim
 *
 * IMPORTANT:
 * ----------
 * Caller must never call Pop() if stack is empty.
 * Doing so is UNSAFE/UNDEFINED.
 *
 * Interface:
 * ----------
 * Push()
 * Pop()      pops and returns last item pushed
 * GetCount()
 * IfEmpty()
 *
 * Design notes:
 * -------------
 * Stack is based on a STL deque.  In the old design,
 * it was based on Dlist, but that incurred excessive
 * memory allocation for every Dlink.
 * As Stack's type is Stack<T>, not Stack<T*> nor Stack<shptr<T>>,
 * the return type of Stack::Pop() is T (not T*) which prevents returning NULL.
 *
 * @endverbatim
 *//*
 * LEGAL:   COPYRIGHT (C) 2007 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE VERSION 2 (GPL 2).
 *****************************************************************************/

#ifndef BASE_STACK_HH
#define BASE_STACK_HH 1

#include <deque>

namespace base {

////////////////////////////////////////////////////////////////////////////////
/// @brief Stack template class.
///
template<typename T>
class Stack
{
PREVENT_COPYING(Stack<T>)
public:

    /// Optionally reserve memory for the stack.
    Stack( const uint preallocate = 32 )
    {
      //mDeque.reserve( preallocate );  // deque lacks reserve()
        SET_TYPESIG(this,TYPESIG_STACK);
    }

    ~Stack()
    {
        INVALIDATE_TYPESIG(this,TYPESIG_STACK);
    }

    void Push( T obj )
    {
    CHECK_TYPESIG(this,TYPESIG_STACK);

        mDeque.push_back( obj );
    }

    /// Pop last object pushed.  CALLER MUST NOT POP IF STACK IS EMPTY!!
    T Pop( void )
    {
    CHECK_TYPESIG(this,TYPESIG_STACK);
    ASSERT( not mDeque.empty() );

        // back() returns but doesn't remove last item.
        // pop_back() returns but doesn't return last item.
        T top = mDeque.back();
        mDeque.pop_back();
        return top;
    }

    /// @return Top of stack (doesn't pop it).
    T Top( void )
    {
    CHECK_TYPESIG(this,TYPESIG_STACK);
    ASSERT( not mDeque.empty() );

        // back() returns but doesn't remove last item.
        return mDeque.back();
    }

    bool IfEmpty( void ) const
    {
    CHECK_TYPESIG(this,TYPESIG_STACK);

        return mDeque.empty();
    }

    /// @return Count of items in stack.
    uint GetCount( void ) const
    {
    CHECK_TYPESIG(this,TYPESIG_STACK);

        return mDeque.size();
    }

    /// STL compatibility.
    uint size( void ) const { return GetCount(); }

    /// STL compatibility.
    bool empty( void ) const { return IfEmpty(); }

private:
    std::deque<T>    mDeque;
public:
    DECLARE_TYPESIG(TYPESIG_STACK)
};

} // namespace base

#endif // BASE_STACK_HH
