BoundedStack.h

Go to the documentation of this file.

/*
 * $Revision: 2027 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_B_STACK_H
#define OGDF_B_STACK_H


#include <ogdf/basic/basic.h>


namespace ogdf {

template<class E, class INDEX> class BoundedStack;

// output
template<class E, class INDEX>
void print(ostream &os, const BoundedStack<E,INDEX> &S, char delim = ' ');


template<class E, class INDEX = int> class BoundedStack {

    E *m_pTop;   
    E *m_pStart; 
    E *m_pStop;  

public:

    BoundedStack() {
        m_pTop = m_pStart = m_pStop = 0;
    }

    explicit BoundedStack(INDEX n) {
        OGDF_ASSERT(n >= 1)
        m_pStart = new E[n];
        if (m_pStart == 0) OGDF_THROW(InsufficientMemoryException);
        m_pTop  = m_pStart - 1;
        m_pStop = m_pStart+n;
    }

    BoundedStack(const BoundedStack<E> &S) {
        copy(S);
    }

    // destruction
    ~BoundedStack() {
        delete [] m_pStart;
    }

    const E &top() const {
        OGDF_ASSERT(m_pTop != m_pStart-1)
        return *m_pTop;
    }

    E &top() {
        OGDF_ASSERT(m_pTop != m_pStart-1)
        return *m_pTop;
    }

    INDEX size() const { return m_pTop - (m_pStart-1); }

    bool empty() { return m_pTop == (m_pStart-1); }

    bool full() { return m_pTop == (m_pStop-1); }

    bool valid() const { return m_pStart != 0; }

    INDEX capacity() const { return m_pStop - m_pStart; }

    void init() {
        delete [] m_pStart;
        m_pTop = m_pStart = m_pStart = 0;
    }

    void init(INDEX n) {
        OGDF_ASSERT(n >= 1)

        delete [] m_pStart;

        m_pStart = new E[n];
        if (m_pStart == 0) OGDF_THROW(InsufficientMemoryException);
        m_pTop = m_pStart - 1;
        m_pStop = m_pStart+n;
    }

    BoundedStack<E> &operator=(const BoundedStack &S) {
        delete [] m_pStart;
        copy(S);
        return *this;
    }

    void push(const E &x) {
        OGDF_ASSERT(m_pTop != m_pStop-1)
        *++m_pTop = x;
    }

    E pop() {
        OGDF_ASSERT(m_pTop != (m_pStart-1))
        return *m_pTop--;
    }

    void clear() { m_pTop = m_pStart-1; }

    void print(ostream &os, char delim = ' ') const
    {
        for (const E *pX = m_pStart; pX != m_pTop; )
            os << *++pX << delim;
    }

private:
    void copy(const BoundedStack<E> &S)
    {
        if(!S.valid()) {
            m_pTop = m_pStart = m_pStop = 0;
        } else {
            INDEX sz = S.m_pStop - S.m_pStart;
            m_pStart = new E[sz+1];
            if (m_pStart == 0) OGDF_THROW(InsufficientMemoryException);
            m_pStop = m_pStart + sz;
            m_pTop  = m_pStart-1;
            for (E *pX = S.m_pStart-1; pX != S.m_pTop; )
                *++m_pTop = *++pX;
        }
    }
}; // class BoundedStack



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

} // end namespace ogdf


#endif