// (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 */