//  (C) Porkolab 2003   
//
//  A.4.10.
//   
//  Reference counting stack implementation


#ifndef STACK_H
#define STACK_H

#include <iostream>

template <class T>
class stack
{
    friend std::ostream &operator<< <> ( std::ostream &os, const stack& s);
public:
        stack( int size = 128);
        stack( const stack &rhs);
        ~stack();
    const stack& operator=( const stack &rhs);

    void  push( const T& t);
    T     pop();

    bool is_empty() const;
    bool is_full()  const;
private:
    class rstack
    {
    public:
        rstack( int sz) : size(sz), cnt(0), v( new T[sz]) { }
        ~rstack() { delete [] v; }
        int attach()  { return ++cnt; }
        int detach()  { return --cnt; }
        bool shared() { return cnt>1; }
        T&  operator[](int i)   { return v[i]; }
        rstack *clone( int sp);
    private:
             rstack( const rstack &);
        void operator=( const rstack &);
        int size;
        int cnt;
        T   *v;
    };
    int         capacity;
    int         sp;
    rstack  *r;

    void copy( const stack &other);
    void release();
};

template <class T>
typename stack<T>::rstack *stack<T>::rstack::clone( int sp)
{
   rstack *p = new rstack(size);
   for ( int i = 0; i < sp; ++i )
        p->v[i] = v[i];
   return p;
}

template <class T>
stack<T>::stack( int size)
{
    capacity = size;
    sp = 0;
    r = new rstack(capacity);
    r->attach();
}
template <class T>
stack<T>::stack( const stack &other)
{
    copy(other);
}
template <class T>
stack<T>::~stack()
{
     release();
}
template <class T>
const stack<T>& stack<T>::operator=( const stack &other)
{
    if ( this != &other )
    {
        release();
        copy(other);
    }
    return *this;
}
template <class T>
void stack<T>::copy( const stack &other)
{
    capacity = other.capacity;
    sp = other.sp;
    r = other.r;
    r->attach();
}
template <class T>
void stack<T>::release()
{
    if ( r->shared() )
        r->detach();
    else
        delete r;
}
template <class T>
void stack<T>::push( const T& t)
{
    if ( r->shared() )
    {
        r->detach();
        r = r->clone(sp);
        r->attach();
    }
    (*r)[sp++] = t;
}
template <class T>
T stack<T>::pop()
{
    return (*r)[--sp];
}
template <class T>
bool stack<T>::is_empty() const
{
    return 0 == sp;
}
template <class T>
bool stack<T>::is_full() const
{
    return capacity == sp;
}
template <class T>
std::ostream &operator<<( std::ostream &os, const stack<T>& ds)
{
    os << "[ ";
    for ( int i = 0; i < ds.sp-1; ++i )
        os << (*ds.r)[i] << ", ";
    if ( ds.sp > 0 )
        os << (*ds.r)[ds.sp-1];
    os << " ]";
    return os;
}

#endif /* STACK_H */