StackAr.h

// CStack class interface: array implementation
//
// Etype: must have zero-parameter constructor and operator=
// CONSTRUCTION: with (a) no initializer;
//     copy construction of CStack objects is DISALLOWED
// Deep copy is supported
//
// ******************PUBLIC OPERATIONS*********************
// void Push( Etype X )   --> Insert X
// void Pop( )            --> Remove most recently inserted item
// Etype Top( )           --> Return most recently inserted item
// int IsEmpty( )         --> Return 1 if empty; else return 0
// int IsFull( )          --> Return 1 if full; else return 0
// void MakeEmpty( )      --> Remove all items
// ******************ERRORS********************************
// Predefined exception is propogated if new fails
// EXCEPTION is called for Top or Pop on empty stack
 
#ifndef __STACKAR_H
#define __STACKAR_H
 
#include "AbsStack.h"
 
BEGIN_MOOTOOLS_NAMESPACE
 
template <class Etype>
class CStack : public AbsStack<Etype>
{
  public:
    CStack( );
    virtual ~CStack( ) { xDeleteArray(Array, MaxSize); }
 
    const CStack & operator=( const CStack & Rhs );
 
    void Push( const Etype & X );
    void Pop( );
    void Pop(Etype & X);
    Etype& Top( ) const;
    Etype & GetAt( int i ) const;
    bool Find(const Etype& X) const;
    int IsEmpty( ) const { return TopOfStack == -1; }
    int IsFull( ) const  { return 0; }
    void MakeEmpty( )    { TopOfStack = -1; }
    int Size() const { return TopOfStack+1; }
    void InitSize(int initSize);
 
  protected:
    // Copy constructor remains disabled by inheritance
    enum { InitStackSize = 5 };
 
    int MaxSize;
    int TopOfStack;
    Etype *Array;
};
 
template <class Etype>
CStack<Etype>::CStack()
{
    Array = NULL;
    TopOfStack = -1;
    MaxSize = 0;
 
    InitSize(InitStackSize);
}
 
template <class Etype>
void CStack<Etype>::InitSize(int initSize)
{
    XASSERT(TopOfStack == -1);
    if (initSize < InitStackSize)
        initSize = InitStackSize;
 
    if (Array && MaxSize == initSize)
        return;
 
    xDeleteArray(Array, MaxSize);
    TopOfStack = -1;
    MaxSize = initSize;
    Array = xNewArray(Etype, MaxSize);
}
 
template <class Etype>
const CStack<Etype> &
CStack<Etype>::operator=( const CStack<Etype> & Rhs )
{
        // Check for aliasing
    if( this == &Rhs )
        return *this;
 
        // Get some memory
    xDeleteArray(Array, MaxSize);
    Array = xNewArray(Etype,  Rhs.MaxSize );
 
        // Do the copy
    MaxSize = Rhs.MaxSize;
    TopOfStack = Rhs.TopOfStack;
    for( int i = 0; i <= TopOfStack; i++ )
        Array[ i ] = Rhs.Array[ i ];
 
    return *this;
}
 
template <class Etype>
void
CStack<Etype>::Push( const Etype & X )
{
    if( TopOfStack + 1 == MaxSize )
    {
        int OldSize = MaxSize;
        Etype *Old = Array;
 
        MaxSize *= 2;
        Array = xNewArray(Etype ,  MaxSize);
 
        for( int i = 0; i <= TopOfStack; i++ )
            Array[ i ] = Old[ i ];
 
        xDeleteArray(Old, OldSize);
    }
 
    Array[ ++TopOfStack ] = X;
}
 
template <class Etype>
void
CStack<Etype>::Pop( )
{
    TopOfStack--;
}
 
template <class Etype>
void
CStack<Etype>::Pop(Etype & X )
{
    XASSERT(TopOfStack > -1);
    X = Array[ TopOfStack ];
 
    TopOfStack--;
}
 
template <class Etype>
Etype& 
CStack<Etype>::Top( ) const
{
    XASSERT(TopOfStack > -1);
    return Array[ TopOfStack ];
}
 
template <class Etype>
Etype &
CStack<Etype>::GetAt( int i ) const
{
    XASSERT(i <= TopOfStack);
    return Array[ i ];
}
 
template <class Etype>
bool
CStack<Etype>::Find(const Etype& X) const
{
    for (int i = TopOfStack; i >= 0; i--)
        if (Array[i] == X)
            return true;
 
    return false;
}
 
END_MOOTOOLS_NAMESPACE
 
#endif // __STACKAR_H