Fréchet View  1.6.0
A Tool for Exploring Fréchet Distance Algorithms
frechet::poly::DoubleEndedQueue< T > Class Template Reference

Detailed Description

template<typename T>
class frechet::poly::DoubleEndedQueue< T >

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
Template Parameters
Tpayload data
Author
Peter Schäfer

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...
 

Member Enumeration Documentation

◆ OpCode

template<typename T>
enum frechet::poly::DoubleEndedQueue::OpCode
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.

Constructor & Destructor Documentation

◆ DoubleEndedQueue()

template<typename T >
frechet::poly::DoubleEndedQueue< T >::DoubleEndedQueue ( int  capacity)

constructor with fixed capacity

Parameters
capacitymax. numer of entries to accomodate

Definition at line 7 of file double_queue_impl.h.

◆ ~DoubleEndedQueue()

template<typename T >
frechet::poly::DoubleEndedQueue< T >::~DoubleEndedQueue ( )

destructor; releases all memory

Definition at line 17 of file double_queue_impl.h.

Member Function Documentation

◆ addLeft()

template<typename T>
void frechet::poly::DoubleEndedQueue< T >::addLeft ( const T &  t)

push a new element to the left side of the queue

Parameters
ta new element

Definition at line 79 of file double_queue_impl.h.

◆ addRight()

template<typename T>
void frechet::poly::DoubleEndedQueue< T >::addRight ( const T &  t)

push a new element to the right side of the queue

Parameters
ta new element

Definition at line 87 of file double_queue_impl.h.

◆ apex()

template<typename T >
const T & frechet::poly::DoubleEndedQueue< T >::apex ( ) const
Returns
the element at the apex; undefined if queue is empty

Definition at line 55 of file double_queue_impl.h.

◆ empty()

template<typename T >
bool frechet::poly::DoubleEndedQueue< T >::empty ( ) const
Returns
true if the queue is empty

Definition at line 44 of file double_queue_impl.h.

◆ leftEnd()

template<typename T >
const T & frechet::poly::DoubleEndedQueue< T >::leftEnd ( ) const
Returns
the element at the left end; undefined if queue is empty

Definition at line 62 of file double_queue_impl.h.

◆ leftSize()

template<typename T >
int frechet::poly::DoubleEndedQueue< T >::leftSize ( ) const
Returns
number of entries to the left of the apex (not including apex)

Definition at line 30 of file double_queue_impl.h.

◆ operator[]()

template<typename T >
const T & frechet::poly::DoubleEndedQueue< T >::operator[] ( int  offset) const

access operator relative to apex

Parameters
offsetfrom apex
Returns
element at 0 = element at apex

0 elements to the right of the apex

< 0 elements to the left of the apex undefined if queue is empty

Definition at line 47 of file double_queue_impl.h.

◆ removeLeftUpto()

template<typename T >
void frechet::poly::DoubleEndedQueue< T >::removeLeftUpto ( int  t)

pop entries from the left end; Adjust the left end pointer and the apex, as necessary.

Parameters
tnew location of the left end from the apex

Definition at line 113 of file double_queue_impl.h.

◆ removeRightUpto()

template<typename T >
void frechet::poly::DoubleEndedQueue< T >::removeRightUpto ( int  t)

pop entries from the right end; Adjust the right end pointer and the apex, as necessary.

Parameters
tnew location of the right end from the apex

Definition at line 123 of file double_queue_impl.h.

◆ reset()

template<typename T>
void frechet::poly::DoubleEndedQueue< T >::reset ( const T &  apex)

reset the qeueue with exactly one element

Parameters
apexnew apex = left end = right end

Definition at line 69 of file double_queue_impl.h.

◆ rightEnd()

template<typename T >
const T & frechet::poly::DoubleEndedQueue< T >::rightEnd ( ) const
Returns
the element at the right end; undefined if queue is empty

Definition at line 66 of file double_queue_impl.h.

◆ rightSize()

template<typename T >
int frechet::poly::DoubleEndedQueue< T >::rightSize ( ) const
Returns
number of entries to the right of the apex (not including apex)

Definition at line 37 of file double_queue_impl.h.

◆ size()

template<typename T >
int frechet::poly::DoubleEndedQueue< T >::size ( ) const
Returns
current number of entries

Definition at line 23 of file double_queue_impl.h.

◆ undo() [1/2]

template<typename T >
void frechet::poly::DoubleEndedQueue< T >::undo ( const Frame fr)
private

undo an operation

Parameters
frstack frame that holds the data to restore

Definition at line 140 of file double_queue_impl.h.

◆ undo() [2/2]

template<typename T >
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.

Member Data Documentation

◆ A

template<typename T>
T* frechet::poly::DoubleEndedQueue< T >::A
private

pointer to funnel apex

Definition at line 97 of file double_queue.h.

◆ buffer

template<typename T>
T* frechet::poly::DoubleEndedQueue< T >::buffer
private

entry buffer

Definition at line 93 of file double_queue.h.

◆ capacity

template<typename T>
int frechet::poly::DoubleEndedQueue< T >::capacity
private

buffer capacity

Definition at line 94 of file double_queue.h.

◆ hist

template<typename T>
std::stack<Frame,std::vector<Frame> > frechet::poly::DoubleEndedQueue< T >::hist
private

stack of previous operations for backtracking

Definition at line 100 of file double_queue.h.

◆ L

template<typename T>
T* frechet::poly::DoubleEndedQueue< T >::L
private

pointer to left end (inclusive)

Definition at line 95 of file double_queue.h.

◆ R

template<typename T>
T* frechet::poly::DoubleEndedQueue< T >::R
private

pointer to right end (inclusive)

Definition at line 96 of file double_queue.h.


The documentation for this class was generated from the following files: