BoundedQueue.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/basic.h>
#include <ogdf/basic/exceptions.h>
 
#include <ostream>
 
namespace ogdf {
 
 
template<class E, class INDEX = int>
class BoundedQueue {
    E* m_pStart; 
    E* m_pEnd; 
    E* m_pStop; 
    E* m_pFirst; 
 
public:
    BoundedQueue() { m_pStart = m_pEnd = m_pFirst = m_pStop = nullptr; }
 
    explicit BoundedQueue(INDEX n) {
        OGDF_ASSERT(n >= 1);
        m_pStart = m_pEnd = m_pFirst = new E[n + 1];
        if (m_pFirst == nullptr) {
            OGDF_THROW(InsufficientMemoryException);
        }
 
        m_pStop = m_pFirst + n + 1;
    }
 
    BoundedQueue(const BoundedQueue<E>& Q) { copy(Q); }
 
 
    BoundedQueue(BoundedQueue<E>&& Q) {
        m_pStart = Q.m_pStart;
        m_pEnd = Q.m_pEnd;
        m_pStop = Q.m_pStop;
        m_pFirst = Q.m_pFirst;
        Q.m_pStart = Q.m_pEnd = Q.m_pFirst = Q.m_pStop = nullptr;
    }
 
    ~BoundedQueue() { delete[] m_pFirst; }
 
    void init() {
        delete[] m_pFirst;
        m_pStart = m_pEnd = m_pFirst = m_pStop = nullptr;
    }
 
    void init(INDEX n) {
        delete[] m_pFirst;
 
        OGDF_ASSERT(n >= 1);
        m_pStart = m_pEnd = m_pFirst = new E[n + 1];
        if (m_pFirst == nullptr) {
            OGDF_THROW(InsufficientMemoryException);
        }
 
        m_pStop = m_pFirst + n + 1;
    }
 
    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) ? (INDEX)(m_pEnd - m_pStart)
                                    : (INDEX)((m_pEnd - m_pFirst) + (m_pStop - m_pStart));
    }
 
    INDEX capacity() const { return (INDEX)((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;
    }
 
 
    BoundedQueue<E>& operator=(BoundedQueue<E>&& Q) {
        delete[] m_pFirst;
 
        m_pStart = Q.m_pStart;
        m_pEnd = Q.m_pEnd;
        m_pStop = Q.m_pStop;
        m_pFirst = Q.m_pFirst;
        Q.m_pStart = Q.m_pEnd = Q.m_pFirst = Q.m_pStop = nullptr;
 
        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(std::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 == nullptr) {
            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;
            }
        }
    }
};
 
template<class E, class INDEX>
std::ostream& operator<<(std::ostream& os, const BoundedQueue<E, INDEX>& Q) {
    Q.print(os);
    return os;
}
 
}