Stack implemented with simple dynamic array and with bounds verification. More...

#include <tpl_arrayStack.H>

Inheritance diagram for Aleph::ArrayStack< T >:

Collaboration diagram for Aleph::ArrayStack< T >:

Classes
class	Iterator
	Iterator on the items of a stack. More...

Public Types
using	Item_Type = T

Public Types inherited from StlAlephIterator< ArrayStack< T > >
using	iterator = StlIterator< ArrayStack< T > >

using	const_iterator = StlConstIterator< ArrayStack< T > >

Public Member Functions
	ArrayStack (size_t dim=4)
	The type of element.

	ArrayStack (const ArrayStack &s)
	Copy constructor.

	ArrayStack (ArrayStack &&s) noexcept
	Move constructor.

template<template< typename > class List>
	ArrayStack (const List< T > &l)

template<class It >
	ArrayStack (It b, It e)

	ArrayStack (std::initializer_list< T > l)

ArrayStack &	operator= (const ArrayStack &s)
	Assign by copy `s` to `this`

void	swap (ArrayStack &s) noexcept
	Swap `this` with `s`

ArrayStack &	operator= (ArrayStack &&s) noexcept
	Assign by moving `s` to `this`

T &	push (const T &data)
	Push into stack a copy of `data`

T &	push (T &&data)
	Push into stack `data`

T &	append (const T &data)

T &	append (T &&data)

T &	insert (const T &data)

T &	insert (T &&data)

T &	pushn (const size_t &n=1)
	Push `n` cells into the stack.

T	pop ()
	Extract the last more recently inserted element.

T	pop_ne () noexcept

T	popn (size_t n)
	Extract in constant time the `n` more recently inserted elements of stack.

T &	top () const
	Return a modifiable reference to youngest element of stack (called the top)

T &	base () noexcept
	Return a modifiable reference to first element of array.

T &	top (size_t i) const
	Return a modifiable reference to the element located at `i` positions from top.

T &	get_last () const

void	empty () noexcept
	Empty the stack.

bool	is_empty () const noexcept
	Return `true` if stack is empty.

size_t	size () const noexcept
	Return the number of elements stored in the stack.

size_t	capacity () const noexcept
	Return the internal capacity.

template<class Operation >
bool	traverse (Operation &operation)
	Traverse all the items of stack from the youngest to oldest and conditionally performs an operation.

template<class Operation >
bool	traverse (Operation &operation) const

template<class Operation >
bool	traverse (Operation &&operation=Operation()) const

template<class Operation >
bool	traverse (Operation &&operation=Operation())

Public Member Functions inherited from LocateFunctions< ArrayStack< T >, T >
auto	get_it () const
	Return a properly initialized iterator positioned at the first item on the container.

auto	get_it (const size_t pos) const
	Return a properly initialized iterator positioned at the `pos` item on the container.

auto	get_itor () const
	Alias of `get_it()`.

T &	nth_ne (const size_t n) noexcept
	Return the n‑th element without bounds checking.

const T &	nth_ne (const size_t n) const noexcept
	Const overload of `nth_ne(size_t)`.

T &	nth (const size_t n)
	Return the n-th item of container.

const T &	nth (const size_t n) const
	Const overload of `nth(size_t)`.

T *	find_ptr (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Find a pointer to an item in the container according to a searching criteria.

const T *	find_ptr (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Const overload of `find_ptr(Operation&)`.

const T *	find_ptr (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of `find_ptr(Operation&) const` that accepts rvalues.

T *	find_ptr (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of `find_ptr(Operation&)` that accepts rvalues.

size_t	find_index (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Find the position of an item in the container according to a searching criteria.

size_t	find_index (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of `find_index(Operation&)` that accepts rvalues.

std::tuple< bool, T >	find_item (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Safe sequential searching of an item matching a criteria.

std::tuple< bool, T >	find_item (Operation &operation) const noexcept(operation_is_noexcept< Operation >())

std::tuple< bool, T >	find_item (Operation &&operation) noexcept(operation_is_noexcept< Operation >())

std::tuple< bool, T >	find_item (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())

Public Member Functions inherited from FunctionalMethods< ArrayStack< T >, T >
void	emplace (Args &&... args)
	Appends a new element into the container by constructing it in-place with the given args.

void	emplace_end (Args &&... args)

void	emplace_ins (Args &&... args)
	Insert a new element into the container by constructing it in-place with the given args.

size_t	ninsert (Args ... args)
	Insert n variadic items.

size_t	nappend (Args ... args)
	Append n variadic items.

void	for_each (Operation &operation)
	Traverse all the container and performs an operation on each element.

void	for_each (Operation &operation) const
	Const overload of `for_each(Operation&)`.

void	for_each (Operation &&operation) const
	Overload of `for_each(Operation&) const` that accepts rvalues.

void	for_each (Operation &&operation)
	Overload of `for_each(Operation&)` that accepts rvalues.

void	each (Operation &operation)
	Alias of `for_each(Operation&)`.

void	each (Operation &operation) const
	Const alias of `for_each(Operation&)`.

void	each (Operation &&operation) const
	Const alias of `for_each(Operation&)` that accepts rvalues.

void	each (Operation &&operation)
	Alias of `for_each(Operation&)` that accepts rvalues.

void	each (size_t pos, const size_t slice, Operation &operation) const
	Traverse the container starting at `pos` taking one item every `slice`, performing a mutable operation on each visited element.

void	each (const size_t pos, const size_t slice, Operation &&operation) const

void	mutable_for_each (Operation &operation)

void	mutable_for_each (Operation &&operation)

bool	all (Operation &operation) const
	Check if all the elements of container satisfy a condition.

bool	all (Operation &&operation) const
	Overload of `all(Operation&)` that accepts rvalues.

bool	exists (Operation &op) const
	Test for existence in the container of an element satisfying a criteria.

bool	exists (Operation &&op) const
	Overload of `exists(Operation&)` that accepts rvalues.

Aleph::DynList< __T >	maps (Operation &op) const
	Map the elements of the container.

Aleph::DynList< __T >	maps (Operation &&op) const
	Overload of `maps(Operation&)` that accepts rvalues.

Aleph::DynList< __T >	maps_if (Prop prop, Operation &op) const
	Conditional mapping of the elements of the container.

Aleph::DynList< __T >	maps_if (Prop prop, Operation &&op) const
	Overload of `maps_if(Prop, Operation&)` that accepts rvalues.

Aleph::DynList< T >	to_dynlist () const
	Convert container to DynList.

std::vector< T >	to_vector () const
	Convert container to std::vector.

__T	foldl (const __T &init, Op &op) const
	Fold the elements of the container to a specific result.

__T	foldl (const __T &init, Op &&op=Op()) const
	Overload of `foldl(const __T&, Op&)` that accepts rvalues.

__T	fold_left (const __T &init, Op &op) const
	Alias for foldl with the same accumulator type.

__T	fold_left (const __T &init, Op &&op=Op()) const
	Overload of `fold_left(const __T&, Op&)` that accepts rvalues.

T	fold (const T &init, Operation &operation) const
	Simplified version of foldl() where the folded type is the same type of elements stored in the container.

T	fold (const T &init, Operation &&operation) const
	Overload of `fold(const T&, Operation&)` that accepts rvalues.

Aleph::DynList< T >	filter (Operation &operation) const
	Filter the elements of a container according to a matching criteria.

Aleph::DynList< T >	filter (Operation &&operation) const
	Overload of `filter(Operation&)` that accepts rvalues.

Aleph::DynList< const T * >	ptr_filter (Operation &operation) const
	Filter the elements of a container according to a matching criteria and return a pointer to the matched items in the container.

Aleph::DynList< const T * >	ptr_filter (Operation &&operation) const
	Overload of `ptr_filter(Operation&)` that accepts rvalues.

Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &operation) const
	Filter the elements of a container according to a matching criteria and determine its positions respect to the traversal of container.

Aleph::DynList< std::tuple< T, size_t > >	pfilter (Operation &&operation) const
	Overload of `pfilter(Operation&)` that accepts rvalues.

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &op) const
	Exclusive partition of container according to a filter criteria.

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &&op) const
	Overload of `partition(Operation&)` that accepts rvalues.

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (size_t n) const
	Exclusive partition of container in the nth item.

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	split_half () const
	Split the container into two halves by alternating elements.

std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &op) const
	Exclusive partition of container according to a filter criteria.

std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &&op) const
	Overload of `tpartition(Operation&)` that accepts rvalues.

size_t	length () const noexcept
	Count the number of elements of a container.

Aleph::DynList< T >	rev () const
	Return a list with the elements of container in reverse order respect to its traversal order.

Aleph::DynList< T >	take (const size_t n) const
	Return a list with the first n elements seen in the container during its traversal.

Aleph::DynList< T >	take (size_t i, const size_t j, const size_t step=1) const
	Return a list with elements seen in the container between i and j position respect to its traversal.

Aleph::DynList< T >	drop (const size_t n) const
	Drop the first n elements seen in the container during its traversal.

void	mutable_drop (const size_t n)
	Drop the first n elements seen from container.

Public Member Functions inherited from GenericItems< Container, T >
Aleph::DynList< T >	items () const
	Return a list of all the elements of a container sorted by traversal order.

Aleph::DynList< T >	keys () const

Public Member Functions inherited from EqualToMethod< ArrayStack< T > >
bool	equal_to (const ArrayStack< T > &r) const noexcept
	Test if elements of `this` are exactly contained in another container.

bool	operator== (const ArrayStack< T > &r) const noexcept

bool	operator!= (const ArrayStack< T > &r) const noexcept
	Negation of equal_to()

Public Member Functions inherited from StlAlephIterator< ArrayStack< T > >
iterator	begin () noexcept
	Return an STL-compatible iterator to the first element.

const_iterator	begin () const noexcept
	Return a const iterator to the first element.

iterator	end () noexcept
	Return an STL-compatible end iterator.

const_iterator	end () const noexcept
	Return a const end iterator.

const_iterator	cbegin () const noexcept
	Return a const iterator to the first element.

const_iterator	cend () const noexcept
	Return a const end iterator.

Private Attributes
MemArray< T >	array

Additional Inherited Members
Related Symbols inherited from FunctionalMethods< ArrayStack< T >, T >
	each

	each

	each

Detailed Description

template<typename T>
class Aleph::ArrayStack< T >

Stack implemented with simple dynamic array and with bounds verification.

ArrayStack<T> instruments a stack of elements of generic type T. The stack is store into an internal contiguous array which grows and ungrows dynamically according to the number of elements.

ArrayStack<T> is a good trade-off between performance and memory consumption. In general is faster than a stack implemented with linked list, but since the internal array growths in two powers, the waste of memory could reach twice the number of elements.

You could use FixedStack, which other than the internal array does not dynamically grow, it does not still perform bound_min_clock checks.

See also: FixedStack DynListStack

Definition at line 79 of file tpl_arrayStack.H.

Member Typedef Documentation

◆ Item_Type

template<typename T >

using Aleph::ArrayStack< T >::Item_Type = T

Definition at line 89 of file tpl_arrayStack.H.

Constructor & Destructor Documentation

◆ ArrayStack() [1/6]

template<typename T >

Aleph::ArrayStack< T >::ArrayStack ( size_t dim = 4 )

inline

The type of element.

Initializes a stack with a capacity of dim

Definition at line 92 of file tpl_arrayStack.H.

◆ ArrayStack() [2/6]

template<typename T >

Aleph::ArrayStack< T >::ArrayStack ( const ArrayStack< T > & s )

inline

Copy constructor.

Definition at line 95 of file tpl_arrayStack.H.

◆ ArrayStack() [3/6]

template<typename T >

Aleph::ArrayStack< T >::ArrayStack ( ArrayStack< T > && s )

inlinenoexcept

Move constructor.

Definition at line 98 of file tpl_arrayStack.H.

◆ ArrayStack() [4/6]

template<typename T >

template<template< typename > class List>

Aleph::ArrayStack< T >::ArrayStack ( const List< T > & l )

inline

Definition at line 101 of file tpl_arrayStack.H.

◆ ArrayStack() [5/6]

template<typename T >

template<class It >

Aleph::ArrayStack< T >::ArrayStack	(	It	b,
		It	e
	)

inline

Definition at line 101 of file tpl_arrayStack.H.

◆ ArrayStack() [6/6]

template<typename T >

Aleph::ArrayStack< T >::ArrayStack ( std::initializer_list< T > l )

inline

Definition at line 101 of file tpl_arrayStack.H.

Member Function Documentation

◆ append() [1/2]

template<typename T >

T & Aleph::ArrayStack< T >::append ( const T & data )

inline

Definition at line 150 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::push().

◆ append() [2/2]

template<typename T >

T & Aleph::ArrayStack< T >::append ( T && data )

inline

Definition at line 153 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::push().

◆ base()

template<typename T >

T & Aleph::ArrayStack< T >::base ( )

inlinenoexcept

Return a modifiable reference to first element of array.

Definition at line 212 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

◆ capacity()

template<typename T >

size_t Aleph::ArrayStack< T >::capacity ( ) const

inlinenoexcept

Return the internal capacity.

Definition at line 245 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

◆ empty()

template<typename T >

void Aleph::ArrayStack< T >::empty ( )

inlinenoexcept

Empty the stack.

Definition at line 236 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

Referenced by Aleph::BinNodePrefixIterator< Node >::end(), Aleph::BinNodeInfixIterator< Node >::end(), Aleph::BinNodePrefixIterator< Node >::reset_first(), Aleph::BinNodeInfixIterator< Node >::reset_first(), Aleph::BinNodePrefixIterator< Node >::reset_last(), and Aleph::BinNodeInfixIterator< Node >::reset_last().

◆ get_last()

template<typename T >

T & Aleph::ArrayStack< T >::get_last ( ) const

inline

Definition at line 233 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::top().

◆ insert() [1/2]

template<typename T >

T & Aleph::ArrayStack< T >::insert ( const T & data )

inline

Definition at line 156 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::push().

◆ insert() [2/2]

template<typename T >

T & Aleph::ArrayStack< T >::insert ( T && data )

inline

Definition at line 159 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::push().

◆ is_empty()

template<typename T >

bool Aleph::ArrayStack< T >::is_empty ( ) const

inlinenoexcept

Return true if stack is empty.

Definition at line 239 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

Referenced by Aleph::BinNodeInfixIterator< Node >::is_in_first(), Aleph::BinNodeInfixIterator< Node >::is_last(), Aleph::BinNodePrefixIterator< Node >::next_ne(), Aleph::BinNodeInfixIterator< Node >::next_ne(), and TEST().

◆ operator=() [1/2]

template<typename T >

ArrayStack & Aleph::ArrayStack< T >::operator= ( ArrayStack< T > && s )

inlinenoexcept

Assign by moving s to this

Definition at line 121 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array, and Aleph::ArrayStack< T >::swap().

◆ operator=() [2/2]

template<typename T >

ArrayStack & Aleph::ArrayStack< T >::operator= ( const ArrayStack< T > & s )

inline

Assign by copy s to this

Definition at line 104 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

◆ pop()

template<typename T >

T Aleph::ArrayStack< T >::pop ( )

inline

Extract the last more recently inserted element.

Returns: a copy of extracted element

Exceptions

underflow_error if stack is empty

Definition at line 182 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

Referenced by fib_st(), fib_stack(), Aleph::BinNodePrefixIterator< Node >::next_ne(), and Aleph::BinNodeInfixIterator< Node >::next_ne().

◆ pop_ne()

template<typename T >

T Aleph::ArrayStack< T >::pop_ne ( )

inlinenoexcept

Definition at line 187 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

◆ popn()

template<typename T >

T Aleph::ArrayStack< T >::popn ( size_t n )

inline

Extract in constant time the n more recently inserted elements of stack.

Parameters

[in] n number of elements to pop

Returns: a copy of last extracted element

Exceptions

underflow_error if n is greater than stack size

Definition at line 199 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

◆ push() [1/2]

template<typename T >

Aleph::ArrayStack< T >::push ( const T & data )

inline

Push into stack a copy of data

Parameters

[in] data to be pushed by copy

Returns: a modifiable reference to the copy of inserted data

Exceptions

bad_alloc if there is no enough memory

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 133 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

Referenced by SimpleStack::SimpleStack(), Aleph::BinNodeInfixIterator< Node >::advance_to_min(), Aleph::ArrayStack< T >::append(), Aleph::ArrayStack< T >::append(), fib_st(), Aleph::ArrayStack< T >::insert(), Aleph::ArrayStack< T >::insert(), and Aleph::BinNodePrefixIterator< Node >::next_ne().

◆ push() [2/2]

template<typename T >

Aleph::ArrayStack< T >::push ( T && data )

inline

Push into stack data

Parameters

[in] data to be pushed by moving

Returns: a modifiable reference to the moved inserted data

Exceptions

bad_alloc if there is no enough memory

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 144 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

◆ pushn()

template<typename T >

T & Aleph::ArrayStack< T >::pushn ( const size_t & n = 1 )

inline

Push n cells into the stack.

pushn(n) is functionally equivalent to perform n pushes of T() in constant time. The idea is to reserve enough space for later use.

Parameters

[in] n number of cells to reserve

Returns: a modifiable reference to the stack's top

Exceptions

bad_alloc if there is no enough memory

Definition at line 171 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

Referenced by fib_stack().

◆ size()

template<typename T >

size_t Aleph::ArrayStack< T >::size ( ) const

inlinenoexcept

Return the number of elements stored in the stack.

Definition at line 242 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

Referenced by fib_st(), fib_stack(), and TEST().

◆ swap()

template<typename T >

void Aleph::ArrayStack< T >::swap ( ArrayStack< T > & s )

inlinenoexcept

Swap this with s

Definition at line 115 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

Referenced by Aleph::ArrayStack< T >::operator=(), Aleph::BinNodeInfixIterator< Node >::swap(), and Aleph::BinNodePrefixIterator< Node >::swap().

◆ top() [1/2]

template<typename T >

T & Aleph::ArrayStack< T >::top ( ) const

inline

Return a modifiable reference to youngest element of stack (called the top)

Definition at line 206 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array.

Referenced by fib_stack(), Aleph::ArrayStack< T >::get_last(), and TEST().

◆ top() [2/2]

template<typename T >

T & Aleph::ArrayStack< T >::top ( size_t i ) const

inline

Return a modifiable reference to the element located at i positions from top.

Parameters

[in] i número of positions

Returns: a modifiable reference to the element at i positions after top

Exceptions

out_of_range if i is greater than the number of elements of stack

Definition at line 226 of file tpl_arrayStack.H.

References ah_out_of_range_error_if, and Aleph::ArrayStack< T >::array.

◆ traverse() [1/4]

template<typename T >

template<class Operation >

bool Aleph::ArrayStack< T >::traverse ( Operation && operation = Operation() )

inline

Definition at line 276 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array, and FunctionalMethods< ArrayStack< T >, T >::maps().

◆ traverse() [2/4]

template<typename T >

template<class Operation >

bool Aleph::ArrayStack< T >::traverse ( Operation && operation = Operation() ) const

inline

Definition at line 269 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array, and FunctionalMethods< ArrayStack< T >, T >::maps().

◆ traverse() [3/4]

template<typename T >

template<class Operation >

Aleph::ArrayStack< T >::traverse ( Operation & operation )

inline

Traverse all the items of stack from the youngest to oldest and conditionally performs an operation.

Parameters

[in] operation to perform on the current element. If it returns true, the the traversal continues to the next item; otherwise the traversal stops

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 255 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array, and FunctionalMethods< ArrayStack< T >, T >::maps().

◆ traverse() [4/4]

template<typename T >

template<class Operation >

bool Aleph::ArrayStack< T >::traverse ( Operation & operation ) const

inline

Definition at line 262 of file tpl_arrayStack.H.

References Aleph::ArrayStack< T >::array, and FunctionalMethods< ArrayStack< T >, T >::maps().

Member Data Documentation

◆ array

template<typename T >

MemArray<T> Aleph::ArrayStack< T >::array

private

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

Classes

Public Types

Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Item_Type

Constructor & Destructor Documentation

◆ ArrayStack() [1/6]

◆ ArrayStack() [2/6]

◆ ArrayStack() [3/6]

◆ ArrayStack() [4/6]

◆ ArrayStack() [5/6]

◆ ArrayStack() [6/6]

Member Function Documentation

◆ append() [1/2]

◆ append() [2/2]

◆ base()

◆ capacity()

◆ empty()

◆ get_last()

◆ insert() [1/2]

◆ insert() [2/2]

◆ is_empty()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ pop()

◆ pop_ne()

◆ popn()

◆ push() [1/2]

◆ push() [2/2]

◆ pushn()

◆ size()

◆ swap()

◆ top() [1/2]

◆ top() [2/2]

◆ traverse() [1/4]

◆ traverse() [2/4]

◆ traverse() [3/4]

◆ traverse() [4/4]

Member Data Documentation

◆ array