double_queue_impl.h

Go to the documentation of this file.

#ifndef DOUBLE_QUEUE_IMPL_H
#define DOUBLE_QUEUE_IMPL_H

namespace frechet { namespace poly {

template<typename T>
DoubleEndedQueue<T>::DoubleEndedQueue(int acapacity)
    : hist(), capacity(acapacity)
{
    buffer = new T[2*capacity];
    R = buffer+capacity;
    L = R+1;
    A = nullptr;
}

template<typename T>
DoubleEndedQueue<T>::~DoubleEndedQueue()
{
    delete buffer;
}

template<typename T>
int DoubleEndedQueue<T>::size() const
{
    Q_ASSERT(empty() || (R >= L));
    return R-L+1;
}

template<typename T>
int DoubleEndedQueue<T>::leftSize() const
{
    Q_ASSERT(empty() || A >= L);
    return A-L;
}

template<typename T>
int DoubleEndedQueue<T>::rightSize() const
{
    Q_ASSERT(empty() || A <= R);
    return R-A;
}

template<typename T>
bool DoubleEndedQueue<T>::empty() const { return L > R; }

template<typename T>
const T& frechet::poly::DoubleEndedQueue<T>::operator[] (int offset) const {
    Q_ASSERT((A+offset) >= L);
    Q_ASSERT((A+offset) <= R);
    return A[offset];
}


template<typename T>
const T& frechet::poly::DoubleEndedQueue<T>::apex() const {
    Q_ASSERT(A);
    Q_ASSERT(A >= L && A <= R);
    return *A;
}

template<typename T>
const T& frechet::poly::DoubleEndedQueue<T>::leftEnd() const { return *L; }


template<typename T>
const T& frechet::poly::DoubleEndedQueue<T>::rightEnd() const { return *R; }

template<typename T>
void DoubleEndedQueue<T>::reset(const T& apex) {
    while(!hist.empty())
        hist.pop();
    R = buffer+capacity;
    L = R+1;
    addLeft(apex);
    A = L;
}

template<typename T>
void DoubleEndedQueue<T>::addLeft(const T& t) {
    Q_ASSERT(L > buffer);    
    --L;
    hist.push(Frame(ADD_LEFT,*L));
    *L = t;    
}

template<typename T>
void DoubleEndedQueue<T>::addRight(const T& t) {
    Q_ASSERT((R+1) < (buffer+2*capacity));    
    ++R;
    hist.push(Frame(ADD_RIGHT,*R));
    *R = t;    
}
/*
template<typename T>
void DoubleEndedQueue<T>::removeLeft(int k) {
    Q_ASSERT(k <= size());
    hist.push(Frame(REMOVE_LEFT,k,A));
    L += k;
    Q_ASSERT(!empty());
    if (A < L) A = L;
}

template<typename T>
void DoubleEndedQueue<T>::removeRight(int k) {
    Q_ASSERT(k <= size());
    hist.push(Frame(REMOVE_RIGHT,k,A));
    R -= k;
    Q_ASSERT(!empty());
    if (A > R) A = R;
}
*/
template<typename T>
void DoubleEndedQueue<T>::removeLeftUpto(int t) {
    Q_ASSERT((A+t) >= L);
    Q_ASSERT((A+t) <= R);

    hist.push(Frame(REMOVE_LEFT,L,A));
    L = A+t;
    if (A < L) A = L;
}

template<typename T>
void DoubleEndedQueue<T>::removeRightUpto(int t) {
    Q_ASSERT((A+t) >= L);
    Q_ASSERT((A+t) <= R);

    hist.push(Frame(REMOVE_RIGHT,R,A));
    R = A+t;
    if (A > R) A = R;
}

template<typename T>
void DoubleEndedQueue<T>::undo() {
    Q_ASSERT(!hist.empty());
    undo(hist.top());
    hist.pop();
}

template<typename T>
void DoubleEndedQueue<T>::undo(const DoubleEndedQueue::Frame &fr) {
    switch(fr.op) {
    case ADD_LEFT:
        *L++ = fr.data;
        break;
    case ADD_RIGHT:
        *R-- = fr.data;
        break;
    case REMOVE_LEFT:
        L = fr.LR;
        A = fr.A;
        break;
    case REMOVE_RIGHT:
        R = fr.LR;
        A = fr.A;
        break;
    }
}

template<typename T>
DoubleEndedQueue<T>::Frame::Frame(OpCode anop, const T& adata)
: op(anop),data(adata)
{ Q_ASSERT(op==ADD_LEFT || op==ADD_RIGHT); }

template<typename T>
DoubleEndedQueue<T>::Frame::Frame(OpCode anop, T* lr, T* apex)
: op(anop),LR(lr),A(apex)
{ Q_ASSERT(op==REMOVE_LEFT || op==REMOVE_RIGHT); }

template<typename T>
DoubleEndedQueue<T>::Frame::Frame(const Frame& that) {
    assignFrom(that);
}

template<typename T>
void DoubleEndedQueue<T>::Frame::assignFrom(const Frame& that) {
    this->op = that.op;
    switch(op) {
    case ADD_LEFT:
    case ADD_RIGHT:
        this->data = that.data;
        break;
    case REMOVE_LEFT:
    case REMOVE_RIGHT:
        this->LR = that.LR;
        this->A = that.A;
        break;
    }    
}

} }

#endif // DOUBLE_QUEUE_IMPL_H