Stack.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_STACK_H
#define OGDF_STACK_H


#include <ogdf/basic/SList.h>


namespace ogdf {


// * In contrast to Stack<E>, instances of \a StackPure<E> do not store the 
// * number of elements contained in the stack.
// */
//template<class E> class StackPure : private SListPure<E> {
//public:
//  //! Constructs an empty stack.
//  StackPure() { }
//
//  //! Constructs a stack that is a copy of \a S.
//  StackPure(const StackPure<E> &S) : SListPure<E>(S) { }
//
//  // destruction
//  ~StackPure() { }
//
//  //! Returns true iff the stack is empty.
//  bool empty() const { return SListPure<E>::empty(); }
//
//  //! Returns a reference to the top element.
//  const E &top() const {
//      return SListPure<E>::front();
//  }
//
//  //! Returns a reference to the top element.
//  E &top() {
//      return SListPure<E>::front();
//  }
//
//  //! Assignment operator.
//  StackPure<E> &operator=(const StackPure<E> &S) {
//      SListPure<E>::operator=(S);
//      return *this;
//  }
//
//  //! Adds element \a x as top-most element to the stack.
//  SListIterator<E> push(const E &x) {
//      return SListPure<E>::pushFront(x);
//  }
//
//  //! Removes the top-most element from the stack and returns it.
//  E pop() {
//      E x = top();
//      SListPure<E>::popFront();
//      return x;
//  }
//
//  //! Makes the stack empty.
//  void clear() { SListPure<E>::clear(); }
//
//  const SListPure<E> &getListPure() const { return *this; }
//
//  OGDF_NEW_DELETE
//}; // class StackPure
//
//
// * In contrast to StackPure<E>, instances of \a Stack<E> store the 
// * number of elements contained in the stack.
// */
//template<class E> class Stack : private SList<E> {
//public:
//  //! Constructs an empty stack.
//  Stack() { }
//
//  //! Constructs a stack that is a copy of \a S.
//  Stack(const Stack<E> &S) : SList<E>(S) { }
//
//  // destruction
//  ~Stack() { }
//
//  //! Returns true iff the stack is empty.
//  bool empty() const { return SList<E>::empty(); }
//  
//  //! Returns the number of elements contained in the stack.
//  int size() const { return SList<E>::size(); }
//
//  //! Returns a reference to the top element.
//  const E &top() const {
//      return SList<E>::front();
//  }
//
//  //! Returns a reference to the top element.
//  E &top() {
//      return SList<E>::front();
//  }
//
//  //! Assignment operator.
//  Stack<E> &operator=(const Stack<E> &S) {
//      SList<E>::operator=(S);
//      return *this;
//  }
//
//  //! Adds element \a x as top-most element to the stack.
//  SListIterator<E> push(const E &x) {
//      return SList<E>::pushFront(x);
//  }
//
//  //! Removes the top-most element from the stack and returns it.
//  E pop() {
//      E x = top();
//      SList<E>::popFront();
//      return x;
//  }
//
//  //! Makes the stack empty.
//  void clear() { SList<E>::clear(); }
//
//  const SList<E> &getList() const { return *this; }
//
//  OGDF_NEW_DELETE
//}; // class Stack
//
//
//template<class E>
//void print(ostream &os, const StackPure<E> &S, char delim = ' ')
//{ print(os,S.getListPure(),delim); }
//
//template<class E>
//void print(ostream &os, const Stack<E> &S, char delim = ' ')
//{ print(os,S.getListPure(),delim); }
//
//
//template<class E>
//ostream &operator<<(ostream &os, const StackPure<E> &S)
//{
//  print(os,S); return os;
//}
//
//template<class E>
//ostream &operator<<(ostream &os, const Stack<E> &S)
//{
//  print(os,S); return os;
//}
//



template<class E> class StackPure
{
    struct Element {
        Element(const E &x, Element *pNext) : m_next(pNext), m_x(x) { }
        Element *m_next;
        E        m_x;
        OGDF_NEW_DELETE
    };

    Element *m_head;

public:
    StackPure() { m_head = 0; }

    StackPure(const StackPure<E> &S)  {
        m_head = 0;
        copy(S);
    }

    // destruction
    ~StackPure() {
        clear();
    }

    bool empty() const { return m_head == 0; }

    const E &top() const {
        return m_head->m_x;
    }

    E &top() {
        return m_head->m_x;
    }

    StackPure<E> &operator=(const StackPure<E> &S) {
        clear();
        copy(S);
        return *this;
    }

    void push(const E &x) {
        m_head = OGDF_NEW Element(x,m_head);
    }

    E pop() {
        OGDF_ASSERT(m_head != 0)
        Element *pX = m_head;
        m_head = m_head->m_next;
        E x = pX->m_x;
        delete pX;
        return x;
    }

    void clear() {
        while(m_head) {
            Element *pX = m_head;
            m_head = m_head->m_next;
            delete pX;
        }
    }

    void print(ostream &os, char delim = ' ') const
    {
        Element *pX = m_head;
        if (pX != 0) {
            os << pX->m_x;
            for(pX = pX->m_next; pX != 0; pX = pX->m_next)
                os << delim << pX->m_x;
        }
    }

private:
    void copy(const StackPure<E> &S) {
        Element **p = &m_head;
        
        for(Element *q = S.m_head; q != 0; q = q->m_next) {
            *p = OGDF_NEW Element(q->m_x,0);
            p = &(*p)->m_next;
        }
    }

    OGDF_NEW_DELETE
}; // class StackPure



template<class E> class Stack : private StackPure<E>
{
    int m_count; 

public:
    Stack() { m_count = 0; }

    Stack(const Stack<E> &S) : StackPure<E>(S) { m_count = S.m_count; }

    // destruction
    ~Stack() { }

    bool empty() const { return StackPure<E>::empty(); }
    
    int size() const { return m_count; }

    const E &top() const {
        return StackPure<E>::top();
    }

    E &top() {
        return StackPure<E>::top();
    }

    Stack<E> &operator=(const Stack<E> &S) {
        StackPure<E>::operator=(S);
        m_count = S.m_count;
        return *this;
    }

    void push(const E &x) {
        ++m_count;
        return StackPure<E>::push(x);
    }

    E pop() {
        --m_count;
        return StackPure<E>::pop();
    }

    void clear() {
        StackPure<E>::clear();
        m_count = 0;
    }

    void print(ostream &os, char delim = ' ') const {
        StackPure<E>::print(os,delim);
    }

    OGDF_NEW_DELETE
}; // class Stack



template<class E>
ostream &operator<<(ostream &os, const StackPure<E> &S)
{
    S.print(os);
    return os;
}


template<class E>
ostream &operator<<(ostream &os, const Stack<E> &S)
{
    S.print(os);
    return os;
}

} // end namespace ogdf


#endif