Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
double_queue.h
Go to the documentation of this file.
1 #ifndef DOUBLE_ENDED_QUEUE_H
2 #define DOUBLE_ENDED_QUEUE_H
3 
4 #include <stack>
5 #include <vector>
6 
7 namespace frechet { namespace poly {
8 
31 template<typename T>
33 private:
37  enum OpCode {
42  };
47  struct Frame {
53  Frame(OpCode anop, const T& adata);
60  Frame(OpCode anop, T* lr, T* apex);
65  Frame(const Frame& that);
71  Frame& operator=(const Frame& that) {
72  assignFrom(that);
73  return *this;
74  }
75 
76  protected:
77  friend class DoubleEndedQueue;
81  union {
82  T data;
83  struct {
84  T* LR;
85  T* A;
86  };
87  };
90  void assignFrom(const Frame& that);
91  };
92 
93  T *buffer;
94  int capacity;
95  T *L;
96  T *R;
97  T *A;
98 
100  std::stack<Frame,std::vector<Frame>> hist;
101 
106  void undo(const Frame& fr);
107 
108 public:
118 
120  int size() const;
123  int leftSize() const;
126  int rightSize() const;
127 
129  bool empty() const;
130 
140  const T& operator[] (int offset) const;
144  const T& apex() const;
145 
149  const T& leftEnd() const;
153  const T& rightEnd() const;
154 
159  void addLeft(const T& t);
164  void addRight(const T& t);
169  void reset(const T& apex);
170 
176  void removeLeftUpto(int t);
182  void removeRightUpto(int t);
183 
188  void undo();
189 };
190 
191 
192 } }
193 
194 #include <double_queue_impl.h>
195 
196 #endif // DOUBLE_ENDED_QUEUE_H
Frame & operator=(const Frame &that)
assignment operator
Definition: double_queue.h:71
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
~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
Definition: double_queue.h:100
const T & operator[](int offset) const
access operator relative to apex
T * A
pointer to funnel apex
Definition: double_queue.h:97
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
Definition: double_queue.h:39
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)
Definition: double_queue.h:95
T * R
pointer to right end (inclusive)
Definition: double_queue.h:96
int capacity
buffer capacity
Definition: double_queue.h:94
DoubleEndedQueue(int capacity)
constructor with fixed capacity
void addRight(const T &t)
push a new element to the right side of the queue