1 #ifndef DOUBLE_QUEUE_IMPL_H 2 #define DOUBLE_QUEUE_IMPL_H 4 namespace frechet {
namespace poly {
8 : hist(), capacity(acapacity)
10 buffer =
new T[2*capacity];
25 Q_ASSERT(empty() || (R >= L));
32 Q_ASSERT(empty() || A >= L);
39 Q_ASSERT(empty() || A <= R);
48 Q_ASSERT((A+offset) >= L);
49 Q_ASSERT((A+offset) <= R);
57 Q_ASSERT(A >= L && A <= R);
82 hist.push(Frame(ADD_LEFT,*L));
88 Q_ASSERT((R+1) < (buffer+2*capacity));
90 hist.push(Frame(ADD_RIGHT,*R));
114 Q_ASSERT((A+t) >= L);
115 Q_ASSERT((A+t) <= R);
117 hist.push(Frame(REMOVE_LEFT,L,A));
124 Q_ASSERT((A+t) >= L);
125 Q_ASSERT((A+t) <= R);
127 hist.push(Frame(REMOVE_RIGHT,R,A));
134 Q_ASSERT(!hist.empty());
161 : op(anop),data(adata)
166 : op(anop),LR(lr),
A(
apex)
180 this->data = that.
data;
192 #endif // DOUBLE_QUEUE_IMPL_H 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
const T & operator[](int offset) const
access operator relative to apex
T * A
pointer to funnel apex
push a new entry on the right
OpCode
encodes an edit operation
DoubleEndedQueue(int capacity)
constructor with fixed capacity