BoundedQueue.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_QUEUE_H
#define OGDF_B_QUEUE_H


#include <ogdf/basic/basic.h>


namespace ogdf {

template<class E, class INDEX> class BoundedQueue;

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


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

    E *m_pStart; 
    E *m_pEnd;   
    E *m_pStop;  
    E *m_pFirst; 

public:
    explicit BoundedQueue(INDEX n) {
        OGDF_ASSERT(n >= 1)
        m_pStart = m_pEnd = m_pFirst = new E[n+1];
        if (m_pFirst == 0) OGDF_THROW(InsufficientMemoryException);

        m_pStop = m_pFirst+n+1;
    }

    BoundedQueue(const BoundedQueue<E> &Q) {
        copy(Q);
    }

    // destruction
    ~BoundedQueue() { delete [] m_pFirst; }

    const E &top() const {
        OGDF_ASSERT(m_pStart != m_pEnd)
        return *m_pStart;
    }

    E &top() {
        OGDF_ASSERT(m_pStart != m_pEnd)
        return *m_pStart;
    }

    const E &bottom() const {
        OGDF_ASSERT(m_pStart != m_pEnd)
        if (m_pEnd == m_pFirst) return *(m_pStop-1);
        else return *(m_pEnd-1);
    }

    E &bottom() {
        OGDF_ASSERT(m_pStart != m_pEnd)
        if (m_pEnd == m_pFirst) return *(m_pStop-1);
        else return *(m_pEnd-1);
    }

    INDEX size() const {
        return (m_pEnd >= m_pStart) ?
            (m_pEnd - m_pStart) :
            (m_pEnd-m_pFirst)+(m_pStop-m_pStart);
    }

    INDEX capacity() const { return (m_pStop - m_pFirst)-1; }

    bool empty() { return m_pStart == m_pEnd; }

    bool full() {
        INDEX h = m_pEnd-m_pStart
        return ( h>=0 ) ? 
            (h == m_pStop-m_pFirst-1) :
            (h == -1);
    }

    BoundedQueue<E> &operator=(const BoundedQueue<E> &Q) {
        delete [] m_pFirst;
        copy(Q);
        return *this;
    }

    void append(const E &x) {
        *m_pEnd++ = x;
        if (m_pEnd == m_pStop) m_pEnd = m_pFirst;
        OGDF_ASSERT(m_pStart != m_pEnd)
    }

    E pop() {
        OGDF_ASSERT(m_pStart != m_pEnd)
        E x = *m_pStart++;
        if (m_pStart == m_pStop) m_pStart = m_pFirst;
        return x;
    }

    void clear() { m_pStart = m_pEnd = m_pFirst; }

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

private:
    void copy(const BoundedQueue<E> &Q) {
        int n = Q.size()+1;
        m_pEnd = m_pStart = m_pFirst = new E[n];
        if (m_pFirst == 0) OGDF_THROW(InsufficientMemoryException);

        m_pStop = m_pStart + n;
        for (E *pX = Q.m_pStart; pX != Q.m_pEnd; ) {
            *m_pEnd++ = *pX++;
            if (pX == Q.m_pStop) pX = Q.m_pFirst;
        }
    }
}; // class BoundedQueue



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

} // end namespace ogdf


#endif