#ifndef STACK_H
#define STACK_H

#include <iostream>

template <class T>
class stack
{
    friend std::ostream &operator<< <> ( std::ostream &os, stack s);
public:
//    class Error { };
//    class Empty : public Error { };
//    class Full  : public Error { };

        stack( int size = 128);
        stack( const stack &rhs);
        ~stack();
    const stack& operator=( const stack &rhs);

    void  push( T d);
    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; }
	int getcnt() { return cnt; }
	T    *getV() { return v; }
        rstack *clone( int sp);
    private:
    	  rstack( const rstack &);
        void operator=( const rstack &);
        int size;
        int cnt;
        T   *v;
    };
    int    capacity;
    int    sp;
    rstack<T>  *r;

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

template <class T>
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 ( 0 == r->detach() )
    	delete r;
    r = 0;
}
template <class T>
void stack<T>::push( T d) // throws (Full)
{
    if ( ! is_full() )
    {
	if ( r->getcnt() > 1 )
	{
        	rstack *p = r->clone(sp);
        	release();
    	  	r = p;
        	r->attach();
	}
        r->getV()[sp++] = d;
    }
//    else
//        throw Full();
}
template <class T>
T stack<T>::pop() // throws (Empty)
{
    if ( ! is_empty() )
        return r->getV()[--sp];
    else
	return T();
//    else
//        throw Empty();
}
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, stack<T> ds)
{
    os << "[ ";
    for ( int i = 0; i < ds.sp-1; ++i )
        os << ds.r->getV()[i] << ", ";
    if ( ds.sp > 0 )
        os << ds.r->getV()[ds.sp-1];
    os << " ]";
    return os;
}

#endif /* STACK_H */