double_queue.h

Go to the documentation of this file.

#ifndef DOUBLE_ENDED_QUEUE_H
#define DOUBLE_ENDED_QUEUE_H

#include <stack>
#include <vector>

namespace frechet { namespace poly {

template<typename T>
class DoubleEndedQueue {
private:
    enum OpCode {
        ADD_LEFT, 
        ADD_RIGHT, 
        REMOVE_LEFT, 
        REMOVE_RIGHT 
    };
    struct Frame {
        Frame(OpCode anop, const T& adata);
        Frame(OpCode anop, T* lr, T* apex);
        Frame(const Frame& that);
        Frame& operator=(const Frame& that) {
            assignFrom(that);
            return *this;
        }

    protected:
        friend class DoubleEndedQueue;
        OpCode op;
        union {
            T data; 
            struct {
                T* LR;  
                T* A;   
            };
        };        
        void assignFrom(const Frame& that);
    };

    T *buffer;  
    int capacity;  
    T *L; 
    T *R; 
    T *A; 

    std::stack<Frame,std::vector<Frame>> hist;

    void undo(const Frame& fr);

public:
    DoubleEndedQueue(int capacity);
    ~DoubleEndedQueue();

    int size() const;
    int leftSize() const;
    int rightSize() const;

    bool empty() const;

    const T& operator[] (int offset) const;
    const T& apex() const;

    const T& leftEnd() const;
    const T& rightEnd() const;

    void addLeft(const T& t);
    void addRight(const T& t);
    void reset(const T& apex);

    void removeLeftUpto(int t);
    void removeRightUpto(int t);

    void undo();
};


} }

#include <double_queue_impl.h>

#endif // DOUBLE_ENDED_QUEUE_H