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

T	payload 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

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

t	a 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

t	a 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

offset from 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

t	new 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

t	new 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

apex	new 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

fr	stack frame that holds the data to restore

Definition at line 140 of file double_queue_impl.h.

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

include/frechet/poly/double_queue.h
include/frechet/poly/double_queue_impl.h

Detailed Description

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

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Member Enumeration Documentation

◆ OpCode

Constructor & Destructor Documentation

◆ DoubleEndedQueue()

◆ ~DoubleEndedQueue()

Member Function Documentation

◆ addLeft()

◆ addRight()

◆ apex()

◆ empty()

◆ leftEnd()

◆ leftSize()

◆ operator[]()

◆ removeLeftUpto()

◆ removeRightUpto()

◆ reset()

◆ rightEnd()

◆ rightSize()

◆ size()

◆ undo() [1/2]

◆ undo() [2/2]

Member Data Documentation

◆ A

◆ buffer

◆ capacity

◆ hist

◆ L

◆ R

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