Open Graph Drawing Framework  v.2007.11

Overview Class Hierarchy Class Index Class List Members Namespaces Source Files Search for:

BoundedStack.h

Go to the documentation of this file.

/*
 * $Revision: 1.7 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2007-11-08 16:10:37 +0100 (Do, 08 Nov 2007) $ 
 ***************************************************************/
 
#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 {

    friend void print OGDF_FT_ENDING (ostream &, const BoundedStack<E,INDEX> &, char);

    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) 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) 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; }

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) 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
template<class E, class INDEX>
void print(ostream &os, const BoundedStack<E,INDEX> &S, char delim/* = ' '*/)
{
    for (const E *pX = S.m_pStart; pX != S.m_pTop; )
        os << *++pX << delim;
}

/*template<class E>
void print(ostream &os, const BoundedStack<E> &S)
{ print(os,S,' '); }*/


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

} // end namespace ogdf


#endif

---