![]() |
Fréchet View
1.6.0
A Tool for Exploring Fréchet Distance Algorithms
|
A double ended queue, or "Funnel". Used by the algorithm for Shortest Paths Trees (Guibas et al.).
Holds an "Apex" pointing inside the double-ended queue.
Keeps a stack of previous operations for backtracking.
+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ ... | x | x | x | x | x | x | x | x | x | ... +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ ^ ^ ^ | | | LEFT APEX RIGHT
T | payload data |
Definition at line 32 of file double_queue.h.
#include <double_queue.h>
Classes | |
struct | Frame |
a stack frame that tracks the necessary information for backtracking More... | |
Public Member Functions | |
DoubleEndedQueue (int capacity) | |
constructor with fixed capacity More... | |
~DoubleEndedQueue () | |
destructor; releases all memory More... | |
int | size () const |
int | leftSize () const |
int | rightSize () const |
bool | empty () const |
const T & | operator[] (int offset) const |
access operator relative to apex More... | |
const T & | apex () const |
const T & | leftEnd () const |
const T & | rightEnd () const |
void | addLeft (const T &t) |
push a new element to the left side of the queue More... | |
void | addRight (const T &t) |
push a new element to the right side of the queue More... | |
void | reset (const T &apex) |
reset the qeueue with exactly one element More... | |
void | removeLeftUpto (int t) |
pop entries from the left end; Adjust the left end pointer and the apex, as necessary. More... | |
void | removeRightUpto (int t) |
pop entries from the right end; Adjust the right end pointer and the apex, as necessary. More... | |
void | undo () |
undo the last call to addLeft/Right, or removeLeft/Right. Undefined if there was no such call. More... | |
Private Types | |
enum | OpCode { ADD_LEFT, ADD_RIGHT, REMOVE_LEFT, REMOVE_RIGHT } |
encodes an edit operation More... | |
Private Member Functions | |
void | undo (const Frame &fr) |
undo an operation More... | |
Private Attributes | |
T * | buffer |
entry buffer More... | |
int | capacity |
buffer capacity More... | |
T * | L |
pointer to left end (inclusive) More... | |
T * | R |
pointer to right end (inclusive) More... | |
T * | A |
pointer to funnel apex More... | |
std::stack< Frame, std::vector< Frame > > | hist |
stack of previous operations for backtracking More... | |
|
private |
encodes an edit operation
Enumerator | |
---|---|
ADD_LEFT | push a new entry on the left |
ADD_RIGHT | push a new entry on the right |
REMOVE_LEFT | remove entry from the left |
REMOVE_RIGHT | remove entry from the right |
Definition at line 37 of file double_queue.h.
frechet::poly::DoubleEndedQueue< T >::DoubleEndedQueue | ( | int | capacity | ) |
constructor with fixed capacity
capacity | max. numer of entries to accomodate |
Definition at line 7 of file double_queue_impl.h.
frechet::poly::DoubleEndedQueue< T >::~DoubleEndedQueue | ( | ) |
destructor; releases all memory
Definition at line 17 of file double_queue_impl.h.
void frechet::poly::DoubleEndedQueue< T >::addLeft | ( | const T & | t | ) |
push a new element to the left side of the queue
t | a new element |
Definition at line 79 of file double_queue_impl.h.
void frechet::poly::DoubleEndedQueue< T >::addRight | ( | const T & | t | ) |
push a new element to the right side of the queue
t | a new element |
Definition at line 87 of file double_queue_impl.h.
const T & frechet::poly::DoubleEndedQueue< T >::apex | ( | ) | const |
Definition at line 55 of file double_queue_impl.h.
bool frechet::poly::DoubleEndedQueue< T >::empty | ( | ) | const |
Definition at line 44 of file double_queue_impl.h.
const T & frechet::poly::DoubleEndedQueue< T >::leftEnd | ( | ) | const |
Definition at line 62 of file double_queue_impl.h.
int frechet::poly::DoubleEndedQueue< T >::leftSize | ( | ) | const |
Definition at line 30 of file double_queue_impl.h.
const T & frechet::poly::DoubleEndedQueue< T >::operator[] | ( | int | offset | ) | const |
access operator relative to apex
offset | from apex |
< 0 elements to the left of the apex undefined if queue is empty0 elements to the right of the apex
Definition at line 47 of file double_queue_impl.h.
void frechet::poly::DoubleEndedQueue< T >::removeLeftUpto | ( | int | t | ) |
pop entries from the left end; Adjust the left end pointer and the apex, as necessary.
t | new location of the left end from the apex |
Definition at line 113 of file double_queue_impl.h.
void frechet::poly::DoubleEndedQueue< T >::removeRightUpto | ( | int | t | ) |
pop entries from the right end; Adjust the right end pointer and the apex, as necessary.
t | new location of the right end from the apex |
Definition at line 123 of file double_queue_impl.h.
void frechet::poly::DoubleEndedQueue< T >::reset | ( | const T & | apex | ) |
reset the qeueue with exactly one element
apex | new apex = left end = right end |
Definition at line 69 of file double_queue_impl.h.
const T & frechet::poly::DoubleEndedQueue< T >::rightEnd | ( | ) | const |
Definition at line 66 of file double_queue_impl.h.
int frechet::poly::DoubleEndedQueue< T >::rightSize | ( | ) | const |
Definition at line 37 of file double_queue_impl.h.
int frechet::poly::DoubleEndedQueue< T >::size | ( | ) | const |
Definition at line 23 of file double_queue_impl.h.
|
private |
undo an operation
fr | stack frame that holds the data to restore |
Definition at line 140 of file double_queue_impl.h.
void frechet::poly::DoubleEndedQueue< T >::undo | ( | ) |
undo the last call to addLeft/Right, or removeLeft/Right. Undefined if there was no such call.
Definition at line 133 of file double_queue_impl.h.
|
private |
pointer to funnel apex
Definition at line 97 of file double_queue.h.
|
private |
entry buffer
Definition at line 93 of file double_queue.h.
|
private |
buffer capacity
Definition at line 94 of file double_queue.h.
|
private |
stack of previous operations for backtracking
Definition at line 100 of file double_queue.h.
|
private |
pointer to left end (inclusive)
Definition at line 95 of file double_queue.h.
|
private |
pointer to right end (inclusive)
Definition at line 96 of file double_queue.h.