Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
double_queue_impl.h
Go to the documentation of this file.
1 #ifndef DOUBLE_QUEUE_IMPL_H
2 #define DOUBLE_QUEUE_IMPL_H
3 
4 namespace frechet { namespace poly {
5 
6 template<typename T>
8  : hist(), capacity(acapacity)
9 {
10  buffer = new T[2*capacity];
11  R = buffer+capacity;
12  L = R+1;
13  A = nullptr;
14 }
15 
16 template<typename T>
18 {
19  delete buffer;
20 }
21 
22 template<typename T>
24 {
25  Q_ASSERT(empty() || (R >= L));
26  return R-L+1;
27 }
28 
29 template<typename T>
31 {
32  Q_ASSERT(empty() || A >= L);
33  return A-L;
34 }
35 
36 template<typename T>
38 {
39  Q_ASSERT(empty() || A <= R);
40  return R-A;
41 }
42 
43 template<typename T>
44 bool DoubleEndedQueue<T>::empty() const { return L > R; }
45 
46 template<typename T>
48  Q_ASSERT((A+offset) >= L);
49  Q_ASSERT((A+offset) <= R);
50  return A[offset];
51 }
52 
53 
54 template<typename T>
56  Q_ASSERT(A);
57  Q_ASSERT(A >= L && A <= R);
58  return *A;
59 }
60 
61 template<typename T>
62 const T& frechet::poly::DoubleEndedQueue<T>::leftEnd() const { return *L; }
63 
64 
65 template<typename T>
66 const T& frechet::poly::DoubleEndedQueue<T>::rightEnd() const { return *R; }
67 
68 template<typename T>
69 void DoubleEndedQueue<T>::reset(const T& apex) {
70  while(!hist.empty())
71  hist.pop();
72  R = buffer+capacity;
73  L = R+1;
74  addLeft(apex);
75  A = L;
76 }
77 
78 template<typename T>
79 void DoubleEndedQueue<T>::addLeft(const T& t) {
80  Q_ASSERT(L > buffer);
81  --L;
82  hist.push(Frame(ADD_LEFT,*L));
83  *L = t;
84 }
85 
86 template<typename T>
88  Q_ASSERT((R+1) < (buffer+2*capacity));
89  ++R;
90  hist.push(Frame(ADD_RIGHT,*R));
91  *R = t;
92 }
93 /*
94 template<typename T>
95 void DoubleEndedQueue<T>::removeLeft(int k) {
96  Q_ASSERT(k <= size());
97  hist.push(Frame(REMOVE_LEFT,k,A));
98  L += k;
99  Q_ASSERT(!empty());
100  if (A < L) A = L;
101 }
102 
103 template<typename T>
104 void DoubleEndedQueue<T>::removeRight(int k) {
105  Q_ASSERT(k <= size());
106  hist.push(Frame(REMOVE_RIGHT,k,A));
107  R -= k;
108  Q_ASSERT(!empty());
109  if (A > R) A = R;
110 }
111 */
112 template<typename T>
114  Q_ASSERT((A+t) >= L);
115  Q_ASSERT((A+t) <= R);
116 
117  hist.push(Frame(REMOVE_LEFT,L,A));
118  L = A+t;
119  if (A < L) A = L;
120 }
121 
122 template<typename T>
124  Q_ASSERT((A+t) >= L);
125  Q_ASSERT((A+t) <= R);
126 
127  hist.push(Frame(REMOVE_RIGHT,R,A));
128  R = A+t;
129  if (A > R) A = R;
130 }
131 
132 template<typename T>
134  Q_ASSERT(!hist.empty());
135  undo(hist.top());
136  hist.pop();
137 }
138 
139 template<typename T>
141  switch(fr.op) {
142  case ADD_LEFT:
143  *L++ = fr.data;
144  break;
145  case ADD_RIGHT:
146  *R-- = fr.data;
147  break;
148  case REMOVE_LEFT:
149  L = fr.LR;
150  A = fr.A;
151  break;
152  case REMOVE_RIGHT:
153  R = fr.LR;
154  A = fr.A;
155  break;
156  }
157 }
158 
159 template<typename T>
161 : op(anop),data(adata)
162 { Q_ASSERT(op==ADD_LEFT || op==ADD_RIGHT); }
163 
164 template<typename T>
166 : op(anop),LR(lr),A(apex)
167 { Q_ASSERT(op==REMOVE_LEFT || op==REMOVE_RIGHT); }
168 
169 template<typename T>
171  assignFrom(that);
172 }
173 
174 template<typename T>
176  this->op = that.op;
177  switch(op) {
178  case ADD_LEFT:
179  case ADD_RIGHT:
180  this->data = that.data;
181  break;
182  case REMOVE_LEFT:
183  case REMOVE_RIGHT:
184  this->LR = that.LR;
185  this->A = that.A;
186  break;
187  }
188 }
189 
190 } }
191 
192 #endif // DOUBLE_QUEUE_IMPL_H
a stack frame that tracks the necessary information for backtracking
Definition: double_queue.h:47
A double ended queue, or "Funnel". Used by the algorithm for Shortest Paths Trees (Guibas et al....
Definition: double_queue.h:32
T * A
apex pointer to restore
Definition: double_queue.h:85
void assignFrom(const Frame &that)
assignment operator
global definitions for all algorithms.
T * LR
left/right end to restore
Definition: double_queue.h:84
Frame(OpCode anop, const T &adata)
constructor with ADD operation
push a new entry on the left
Definition: double_queue.h:38
const T & operator[](int offset) const
access operator relative to apex
T * A
pointer to funnel apex
Definition: double_queue.h:97
push a new entry on the right
Definition: double_queue.h:39
OpCode
encodes an edit operation
Definition: double_queue.h:37
DoubleEndedQueue(int capacity)
constructor with fixed capacity