1 #ifndef DOUBLE_ENDED_QUEUE_H 2 #define DOUBLE_ENDED_QUEUE_H 7 namespace frechet {
namespace poly {
100 std::stack<Frame,std::vector<Frame>>
hist;
106 void undo(
const Frame& fr);
144 const T&
apex()
const;
196 #endif // DOUBLE_ENDED_QUEUE_H Frame & operator=(const Frame &that)
assignment operator
a stack frame that tracks the necessary information for backtracking
A double ended queue, or "Funnel". Used by the algorithm for Shortest Paths Trees (Guibas et al....
T * A
apex pointer to restore
void assignFrom(const Frame &that)
assignment operator
const T & rightEnd() const
global definitions for all algorithms.
T * LR
left/right end to restore
const T & leftEnd() const
Frame(OpCode anop, const T &adata)
constructor with ADD operation
remove entry from the right
remove entry from the left
push a new entry on the left
~DoubleEndedQueue()
destructor; releases all memory
void reset(const T &apex)
reset the qeueue with exactly one element
std::stack< Frame, std::vector< Frame > > hist
stack of previous operations for backtracking
const T & operator[](int offset) const
access operator relative to apex
T * A
pointer to funnel apex
void undo()
undo the last call to addLeft/Right, or removeLeft/Right. Undefined if there was no such call.
void addLeft(const T &t)
push a new element to the left side of the queue
push a new entry on the right
void removeRightUpto(int t)
pop entries from the right end; Adjust the right end pointer and the apex, as necessary.
void removeLeftUpto(int t)
pop entries from the left end; Adjust the left end pointer and the apex, as necessary.
T * L
pointer to left end (inclusive)
OpCode
encodes an edit operation
T * R
pointer to right end (inclusive)
int capacity
buffer capacity
DoubleEndedQueue(int capacity)
constructor with fixed capacity
void addRight(const T &t)
push a new element to the right side of the queue