Simple dynamic array with automatic resizing and functional operations. More...

#include <tpl_array.H>

Inherits LocateFunctions< Array< T >, T >, FunctionalMethods< Array< T >, T >, GenericItems< Container, T >, EqualSequenceMethod< Array< T > >, and StlAlephIterator< Array< T > >.

Collaboration diagram for Aleph::Array< T >:

[legend]

Classes
struct	Iterator
	Iterator on the items of an array. More...

Public Types
using	Item_Type = T

using	Key_Type = T
	The type of element.

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

using	const_iterator = StlConstIterator< Array< T > >

Public Member Functions
	Array (size_t dim=32)
	The type of key.

	Array (size_t n, const T &value)
	Construct an array with `n` copies of `value`.

	Array (const Array &s)
	Copy constructor.

	Array (Array &&s) noexcept
	Move constructor.

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

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

	Array (std::initializer_list< T > l)

template<typename ... Args>
	Array (const T &item, Args &... args)

template<typename ... Args>
	Array (T &&item, Args &... args)

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

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

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

T &	append (const T &data)
	Append a copy of `data`

T &	append (T &&data)
	Append `data`

Array &	append (const Array &a)

Array	append (const Array &a) const

T &	insert (const T &data)
	insert a copy of `data` at the beginning of the array.

T &	insert (T &&data)
	insert a copy of `data` at the beginning of the array.

void	putn (const size_t n)
	Reserve `n` additional logical slots in the array without value-initializing them.

void	reserve (size_t cap)
	Reserves `cap` cells into the array.

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

const T &	base () const

void	empty () noexcept
	Empties the container.

void	clear () noexcept
	Empties the container.

constexpr bool	is_empty () const noexcept
	Checks if the container is empty.

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

constexpr size_t	capacity () const noexcept
	Return the internal capacity.

T &	get_first () noexcept
	return a modifiable reference to the first element.

const T &	get_first () const noexcept
	return a constant reference to the first element.

T &	get_last () noexcept
	return a modifiable reference to the last element.

const T &	get_last () const noexcept
	return a constant reference to the last element.

T	remove_last ()

T	remove_first ()

T &	operator[] (size_t i)
	Return a reference to the ith element.

const T &	operator[] (size_t i) const
	Return a constant reference to the ith element.

constexpr T &	operator() (const size_t i) noexcept
	Return a reference to the ith element. It does not perform bound_statics checks.

constexpr const T &	operator() (const size_t i) const noexcept
	Return a constant reference to the ith element. It does not perform bound_statics checks.

Array &	reverse ()
	Reverse the order of items in this array, in place.

Array	reverse () const
	Return a copy of this array with its items reversed.

Array &	reverse_in_place ()
	Alias for `reverse()`.

Array &	rev ()
	Reverse this array in place.

Array	rev () const
	Alias for `reverse() const`.

template<class Op > requires std::predicate<Op &, T &>
bool	traverse (Op &op)
	Traverse mutable elements from first to last.

template<class Op > requires std::predicate<Op &, const T &>
bool	traverse (Op &op) const
	Traverse const elements from first to last.

template<class Op > requires std::predicate<Op &, T &>
bool	traverse (Op &&op)
	Traverse mutable elements with a temporary operation.

template<class Op > requires std::predicate<Op &, const T &>
bool	traverse (Op &&op) const
	Traverse const elements with a temporary operation.

bool	is_valid () const noexcept

Array	to_array () const
	Copy to Aleph::Array (requires copyable elements).

Public Member Functions inherited from LocateFunctions< Array< 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 the 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 criterion.

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() const that accepts rvalues.

T *	find_ptr (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of find_ptr() 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 criterion.

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

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

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 >())
	Overload of find_item() that accepts rvalues.

std::tuple< bool, T >	find_item (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_item() const that accepts rvalues.

bool	contains_if (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Test if an item satisfying a criterion is present in the container.

bool	contains (const T &item) const
	Test if an item is present in the container using equality.

Public Member Functions inherited from FunctionalMethods< Array< 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() const that accepts rvalues.

void	for_each (Operation &&operation)
	Overload of for_each() 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 each() that accepts rvalues.

void	each (Operation &&operation)
	Alias of each() 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)
	Apply a mutable operation to each element of the container.

void	mutable_for_each (Operation &&operation)

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

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

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

bool	exists (Operation &&op) const
	Overload of exists() 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() that accepts rvalues.

Aleph::DynList< __T >	maps_if (Prop prop, Operation &op) const

Aleph::DynList< __T >	maps_if (Prop prop, Operation &&op) const

Aleph::DynList< __T >	map (Operation &op) const
	Synonym of maps().

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

Aleph::DynList< __T >	map_if (Prop prop, Operation &op) const

Aleph::DynList< __T >	map_if (Prop prop, Operation &&op) const

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() 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() 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() that accepts rvalues.

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

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

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

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

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

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

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

std::pair< Aleph::DynList< T >, Aleph::DynList< T > >	partition (Operation &&op) const
	Overload of partition() 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 criterion.

std::tuple< Aleph::DynList< T >, Aleph::DynList< T > >	tpartition (Operation &&op) const
	Overload of tpartition() 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 EqualSequenceMethod< Array< T > >
bool	equal_to (const Array< T > &r) const
	Equality test between `this` and `r`.

bool	operator== (const Array< T > &r) const
	Equality operator.

bool	operator!= (const Array< T > &r) const
	Inequality operator.

Public Member Functions inherited from StlAlephIterator< Array< 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.

Static Public Member Functions
static Array	create (size_t n)
	Create an array with `n` logical elements.

Private Attributes
MemArray< T >	array

Additional Inherited Members
Public Attributes inherited from FunctionalMethods< Array< T >, T >
	and
	Conditional mapping of the elements of the container.

Related Symbols inherited from FunctionalMethods< Array< T >, T >
	each

	each

	each

Detailed Description

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

Simple dynamic array with automatic resizing and functional operations.

Array<T> is a straightforward dynamic array implemented using a contiguous memory buffer that automatically grows or shrinks as elements are added or removed. It provides O(1) indexed access and amortized O(1) append.

This container offers a balance between simplicity and functionality, supporting both indexed access and a rich set of functional operations (map, filter, fold, etc.).

Template Parameters

T	The type of elements stored in the array.

Complexity:

Access by index: O(1)
append() / insert() at end: O(1) amortized
insert() at arbitrary position: O(n)
remove(): O(n) for search + O(n) for shift
size(): O(1)
Resize: O(n) when capacity is exceeded

Key Features:

O(1) indexed access via operator[]
Automatic capacity management
Functional programming operations (map, filter, fold, etc.)
STL-compatible iterators
Conversion to/from STL vectors and other containers

Comparison with Similar Containers:

Array vs DynArray: Array uses simple contiguous allocation; DynArray uses lazy three-level indexing for sparse arrays.
Array vs DynList: Array has O(1) indexed access but O(n) insertion in the middle; DynList has O(1) insertion/removal but O(n) indexed access.
Array vs std::vector: Similar behavior, but Array includes functional methods and integrates with Aleph-w ecosystem.

Example:: Array<int> arr(10); // Initial capacity of 10

// Add elements

arr.push(42);

arr.push(17);

arr.push(99);

// Indexed access (O(1))

std::cout << arr[1] << '\n'; // 17

arr[1] = 25;

// Functional operations

auto doubled = arr.maps<int>([](int x) { return x * 2; });

int sum = arr.foldl(0, [](int acc, int x) { return acc + x; });

auto evens = arr.filter([](int x) { return x % 2 == 0; });

// Convert to vector

std::vector<int> vec = arr.asVector();

// Range-based for

for (int x : arr)

std::cout << x << " ";

Aleph::Array
Simple dynamic array with automatic resizing and functional operations.
Definition tpl_array.H:138

Aleph::blossom_maximum_cardinality_matching
size_t blossom_maximum_cardinality_matching(const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
Alias of compute_maximum_cardinality_general_matching().
Definition Blossom.H:466

Aleph::sum
T sum(const Container &container, const T &init=T{})
Compute sum of all elements.
Definition ahFunctional.H:2297

std
STL namespace.

Note: Memory is contiguous, providing good cache locality.; Capacity grows automatically; manual control via reserve() if needed.; For sparse arrays with many gaps, consider DynArray instead.

See also: DynArray Lazy dynamic array with three-level indexing for sparse data.; DynList Doubly linked list alternative (O(1) insertion, O(n) access).; FunctionalMethods Inherited functional operations.

Author: Leandro Rabindranath León

Examples: blossom_example.cc, dp_optimizations_example.cc, fft_example.cc, knapsack_example.cc, lis_example.cc, matrix_chain_example.cc, and subset_sum_example.cc.

Definition at line 133 of file tpl_array.H.

Member Typedef Documentation

◆ Item_Type

template<typename T >

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

Definition at line 142 of file tpl_array.H.

◆ Key_Type

template<typename T >

using Aleph::Array< T >::Key_Type = T

The type of element.

Definition at line 143 of file tpl_array.H.

Constructor & Destructor Documentation

◆ Array() [1/9]

template<typename T >

Aleph::Array< T >::Array ( size_t dim = 32 )

inline

The type of key.

Initializes an array with a capacity of dim

Definition at line 146 of file tpl_array.H.

◆ Array() [2/9]

template<typename T >

Aleph::Array< T >::Array	(	size_t	n,
		const T &	value
	)

inline

Construct an array with n copies of value.

Creates an array of size n where each element is initialized by copy-constructing from value.

Parameters

[in]	n	Number of elements to create.
[in]	value	The value to copy into each element.

Exceptions

std::bad_alloc if memory allocation fails.

Note: Complexity: O(n) copies.; Exception safety: Strong guarantee (if allocation fails or T's copy constructor throws, no memory is leaked).; Thread safety: Safe to call concurrently on different instances; not thread-safe on the same instance.

Definition at line 164 of file tpl_array.H.

References Aleph::Array< T >::array, and value.

◆ Array() [3/9]

template<typename T >

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

inline

Copy constructor.

Definition at line 204 of file tpl_array.H.

◆ Array() [4/9]

template<typename T >

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

inlinenoexcept

Move constructor.

Definition at line 211 of file tpl_array.H.

◆ Array() [5/9]

template<typename T >

template<template< typename > class List>

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

inline

Definition at line 215 of file tpl_array.H.

◆ Array() [6/9]

template<typename T >

template<class It >

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

inline

Definition at line 215 of file tpl_array.H.

◆ Array() [7/9]

template<typename T >

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

inline

Definition at line 215 of file tpl_array.H.

◆ Array() [8/9]

template<typename T >

template<typename ... Args>

Aleph::Array< T >::Array	(	const T &	item,
		Args &...	args
	)

inline

Definition at line 217 of file tpl_array.H.

◆ Array() [9/9]

template<typename T >

template<typename ... Args>

Aleph::Array< T >::Array	(	T &&	item,
		Args &...	args
	)

inline

Definition at line 217 of file tpl_array.H.

Member Function Documentation

◆ append() [1/4]

template<typename T >

Array & Aleph::Array< T >::append ( const Array< T > & a )

inline

Definition at line 267 of file tpl_array.H.

References Aleph::Array< T >::append(), and Aleph::Array< T >::array.

◆ append() [2/4]

template<typename T >

Array Aleph::Array< T >::append ( const Array< T > & a ) const

inline

Definition at line 273 of file tpl_array.H.

References Aleph::Array< T >::append(), and Aleph::blossom_maximum_cardinality_matching().

◆ append() [3/4]

template<typename T >

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

inline

Append 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

Examples: blossom_example.cc, and dp_optimizations_example.cc.

Definition at line 250 of file tpl_array.H.

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

◆ append() [4/4]

template<typename T >

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

inline

Append 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

Definition at line 262 of file tpl_array.H.

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

◆ base() [1/2]

template<typename T >

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

inline

Return a reference to the first element of array.

Definition at line 326 of file tpl_array.H.

References ah_underflow_error_if, Aleph::Array< T >::array, and Aleph::Array< T >::is_empty().

Referenced by LFit::LFit(), Aleph::CA::ca_png_detail::write_chunk(), and Aleph::CA::ca_gif_detail::write_subblocks().

◆ base() [2/2]

template<typename T >

const T & Aleph::Array< T >::base ( ) const

inline

Definition at line 332 of file tpl_array.H.

References ah_underflow_error_if, Aleph::Array< T >::array, and Aleph::Array< T >::is_empty().

◆ capacity()

template<typename T >

constexpr size_t Aleph::Array< T >::capacity ( ) const

inlineconstexprnoexcept

Return the internal capacity.

Definition at line 371 of file tpl_array.H.

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

◆ clear()

template<typename T >

void Aleph::Array< T >::clear ( )

inlinenoexcept

Empties the container.

Exceptions

none

See also: empty()

Definition at line 350 of file tpl_array.H.

References Aleph::Array< T >::empty().

Referenced by Aleph::CA::ca_io_detail::finalise_absolute_pattern(), Aleph::CA::Density_Observer< State >::reset(), Aleph::CA::Activity_Observer< Lattice >::reset(), Aleph::CA::Entropy_Observer< MaxState >::reset(), Aleph::CA::Stationary_Detector::reset(), and Aleph::CA::Sampling_Observer< Lattice >::reset().

◆ create()

template<typename T >

static Array Aleph::Array< T >::create ( size_t n )

inlinestatic

Create an array with n logical elements.

This static factory creates an array and then grows it with ret.putn(n). putn() delegates to MemArray::putn(), which only adjusts logical size (and backing storage if needed): it does NOT value-initialize new entries for any T.

All new elements are therefore uninitialized, and the caller MUST assign each position before reading it.

Parameters

[in] n Number of elements to create.

Returns: Array with n logical elements (all uninitialized).

Exceptions

std::bad_alloc if there is not enough memory.

Note: Complexity: O(n) for allocation; logical growth via putn() is O(1) here.; Exception safety: Strong guarantee.; Thread safety: Safe to call concurrently.

Example: auto arr = Array<int>::create(100);

// arr[0] is undefined (garbage)

arr[0] = 42; // Assign before read

Aleph::Array::create
static Array create(size_t n)
Create an array with n logical elements.
Definition tpl_array.H:196

Definition at line 196 of file tpl_array.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ empty()

template<typename T >

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

inlinenoexcept

Empties the container.

Exceptions

none

Definition at line 341 of file tpl_array.H.

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

Referenced by Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::Edmonds_Blossom_Matcher(), Aleph::MonotonePolygonTriangulation::build_faces_from_diagonals(), Aleph::blossom_detail::Edmonds_Blossom_Matcher< GT, SA >::build_node_index(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate(), Aleph::Aho_Corasick::clear(), Aleph::Array< T >::clear(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::compute_faces_from_rotation(), Aleph::FFT< Real >::STFTProcessor::flush(), Aleph::FFT< Real >::ISTFTProcessor::flush(), Aleph::Gen_File_B_Tree< Key, Compare, MinDegree, Codec >::init_empty_cache(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::init_empty_cache(), Aleph::FFT< Real >::STFTProcessor::initialize_pending(), Aleph::FFT< Real >::ISTFTProcessor::initialize_state(), Aleph::Gen_File_B_Tree< Key, Compare, MinDegree, Codec >::load_from_disk(), Aleph::Gen_File_BPlus_Tree< Key, Compare, MinDegree, Codec >::load_from_disk(), Aleph::FFT< Real >::STFTProcessor::pflush(), Aleph::planar_geometric_drawing(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::rebuild_separators(), and Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::trace_alternating_paths().

◆ get_first() [1/2]

template<typename T >

const T & Aleph::Array< T >::get_first ( ) const

inlinenoexcept

return a constant reference to the first element.

No bound_statics check is performed

Definition at line 385 of file tpl_array.H.

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

◆ get_first() [2/2]

template<typename T >

T & Aleph::Array< T >::get_first ( )

inlinenoexcept

return a modifiable reference to the first element.

No bound_statics check is performed

Definition at line 378 of file tpl_array.H.

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

Referenced by Aleph::blossom_weighted_detail::mwmatching::adjust_weights_for_maximum_cardinality_matching(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::borrow_from_next(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_next(), Aleph::Tikz_Plane::draw_polyline(), Aleph::blossom_weighted_detail::mwmatching::impl::MatchingContext< WeightType >::make_blossom(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::min_in(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_min_ptr(), TEST(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_leaf_chain(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::verify_node(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

◆ get_last() [1/2]

template<typename T >

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

inlinenoexcept

return a constant reference to the last element.

No bound_statics check is performed

Definition at line 399 of file tpl_array.H.

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

◆ get_last() [2/2]

template<typename T >

T & Aleph::Array< T >::get_last ( )

inlinenoexcept

return a modifiable reference to the last element.

No bound_statics check is performed

Definition at line 392 of file tpl_array.H.

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

Referenced by Aleph::Gen_B_Tree< Key, Compare, MinDegree >::borrow_from_prev(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_prev(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::build_nonplanar_certificate(), Aleph::RadixTree< T, Char >::erase(), Aleph::blossom_weighted_detail::mwmatching::impl::for_vertices_in_blossom(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::max_in(), Aleph::AndrewMonotonicChainConvexHull::sorted_unique_points(), Aleph::GrahamScanConvexHull::sorted_unique_points(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::subtree_max_ptr(), TEST(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::test_dfs(), Aleph::NTT< MOD, ROOT >::trim_trailing_zeros(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_leaf_chain(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::verify_node(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::verify_node().

◆ insert() [1/2]

template<typename T >

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

inline

insert a copy of data at the beginning of the array.

All the items are moved

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

Definition at line 286 of file tpl_array.H.

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

Referenced by Aleph::VoronoiDiagramFromDelaunay::clipped_cells(), Aleph::Tikz_Plane::collect_legend_entries(), Aleph::Lengauer_Tarjan_Dominators< GT, SA >::dominance_frontiers(), Aleph::VisibilityPolygon::EdgeStatusTree::insert(), Aleph::rank_graphviz(), and TEST().

◆ insert() [2/2]

template<typename T >

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

inline

insert a copy of data at the beginning of the array.

All the items are moved

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

Definition at line 298 of file tpl_array.H.

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

◆ is_empty()

template<typename T >

constexpr bool Aleph::Array< T >::is_empty ( ) const

inlineconstexprnoexcept

Checks if the container is empty.

Returns: true if empty, false otherwise.

Exceptions

none

Examples: knapsack_example.cc, and subset_sum_example.cc.

Definition at line 359 of file tpl_array.H.

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

◆ is_valid()

template<typename T >

bool Aleph::Array< T >::is_valid ( ) const

inlinenoexcept

Definition at line 591 of file tpl_array.H.

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

◆ operator()() [1/2]

template<typename T >

constexpr const T & Aleph::Array< T >::operator() ( const size_t i ) const

inlineconstexprnoexcept

Return a constant reference to the ith element. It does not perform bound_statics checks.

Definition at line 435 of file tpl_array.H.

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

◆ operator()() [2/2]

template<typename T >

constexpr T & Aleph::Array< T >::operator() ( const size_t i )

inlineconstexprnoexcept

Return a reference to the ith element. It does not perform bound_statics checks.

Definition at line 429 of file tpl_array.H.

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

◆ operator=() [1/2]

template<typename T >

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

inlinenoexcept

Assign by moving s to this

Definition at line 238 of file tpl_array.H.

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

◆ operator=() [2/2]

template<typename T >

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

inline

Assign by copy s to this

Definition at line 220 of file tpl_array.H.

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

◆ operator[]() [1/2]

template<typename T >

T & Aleph::Array< T >::operator[] ( size_t i )

inline

Return a reference to the ith element.

Throws range_error if i is out of range

Definition at line 416 of file tpl_array.H.

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

◆ operator[]() [2/2]

template<typename T >

const T & Aleph::Array< T >::operator[] ( size_t i ) const

inline

Return a constant reference to the ith element.

Throws range_error if i is out of range

Definition at line 423 of file tpl_array.H.

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

◆ putn()

template<typename T >

void Aleph::Array< T >::putn ( const size_t n )

inline

Reserve n additional logical slots in the array without value-initializing them.

The caller must assign to the new positions before reading them.

Parameters

[in] n number of cells to reserve

Exceptions

bad_alloc if there is no enough memory

Definition at line 310 of file tpl_array.H.

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

Referenced by Aleph::ModularCombinatorics::ModularCombinatorics(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::insert_at(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::insert_at(), Aleph::Gen_Polynomial< Coefficient >::interpolate(), Aleph::lazy_combinations(), and Aleph::merge().

◆ remove_first()

template<typename T >

T Aleph::Array< T >::remove_first ( )

inline

Definition at line 409 of file tpl_array.H.

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

Referenced by Aleph::Lengauer_Tarjan_Dominators< GT, SA >::do_compute(), Aleph::CA::Stationary_Detector::push(), and Aleph::Dial_Min_Paths< GT, Distance, Itor, SA >::run_dial().

◆ remove_last()

template<typename T >

T Aleph::Array< T >::remove_last ( )

inline

Definition at line 404 of file tpl_array.H.

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

Referenced by Aleph::Convex_Hull_Trick< T >::add_line(), Aleph::Branch_And_Bound< Domain, ObjectivePolicy >::apply_move_and_recurse(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::borrow_from_prev(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::borrow_from_prev(), K2Tree< T >::build(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::classify_k33(), Aleph::Naive_Suffix_Tree::collect_leaf_suffixes(), Aleph::Lengauer_Tarjan_Dominators< GT, SA >::compress(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::count_components(), Aleph::Gen_Link_Cut_Tree< T, Monoid, LazyTag >::destroy_vertex(), Aleph::ida_star_detail::dfs(), Aleph::Depth_First_Backtracking< Domain >::dfs(), Aleph::Depth_First_Backtracking< Domain >::dfs_visited(), Aleph::RadixTree< T, Char >::erase(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::erase_at(), Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::erase_at(), Aleph::planarity_detail::LR_Planarity_Checker< GT, SA >::fails_component_euler_bound(), Aleph::blossom_weighted_detail::mwmatching::impl::for_vertices_in_blossom(), Aleph::monotone_queue_min_dp(), Aleph::planar_dual_metadata(), Aleph::planar_geometric_drawing(), TEST(), Aleph::NTT< MOD, ROOT >::trim_trailing_zeros(), Aleph::Gen_B_Tree< Key, Compare, MinDegree >::truncate(), and Aleph::Gen_BPlus_Tree< Key, Compare, MinDegree >::truncate().

◆ reserve()

template<typename T >

void Aleph::Array< T >::reserve ( size_t cap )

inline

Reserves cap cells into the array.

Parameters

[in] cap new dimension

Exceptions

bad_alloc if there is no enough memory

Examples: blossom_example.cc.

Definition at line 320 of file tpl_array.H.

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

◆ rev() [1/2]

template<typename T >

Array & Aleph::Array< T >::rev ( )

inline

Reverse this array in place.

Returns: A reference to *this, already reversed.

Exceptions

Any	exception thrown by swapping elements.

Note: Complexity: O(n). If a swap throws, some elements may already have changed positions.

See also: reverse()

Definition at line 492 of file tpl_array.H.

References Aleph::Array< T >::reverse_in_place().

◆ rev() [2/2]

template<typename T >

Array Aleph::Array< T >::rev ( ) const

inline

Alias for reverse() const.

Returns a reversed copy.

*this is left unmodified.

Returns: A new Array holding the elements of *this in reverse order.

Exceptions

Any	exception thrown by allocation or copying elements.

Note: Complexity: O(n). *this remains unchanged if the operation throws.

See also: reverse() const

Definition at line 506 of file tpl_array.H.

References Aleph::Array< T >::reverse().

◆ reverse() [1/2]

template<typename T >

Array & Aleph::Array< T >::reverse ( )

inline

Reverse the order of items in this array, in place.

Returns: A reference to *this, already reversed.

Note: Complexity: O(n).

Exceptions

Any	exception thrown by swapping elements. If a swap throws, some elements may already have changed positions.

Definition at line 447 of file tpl_array.H.

References Aleph::Array< T >::array, and Aleph::Array< T >::reverse().

Referenced by Aleph::Array< T >::rev(), Aleph::Array< T >::reverse(), and Aleph::Array< T >::reverse_in_place().

◆ reverse() [2/2]

template<typename T >

Array Aleph::Array< T >::reverse ( ) const

inline

Return a copy of this array with its items reversed.

*this is left unmodified.

Returns: A new Array holding the elements of *this in reverse order.

Note: Complexity: O(n).

Exceptions

Any	exception thrown by allocation or copying elements.

Note: *this remains unchanged if the operation throws.

Definition at line 462 of file tpl_array.H.

References Aleph::Array< T >::array, Aleph::blossom_maximum_cardinality_matching(), and Aleph::Array< T >::size().

◆ reverse_in_place()

template<typename T >

Array & Aleph::Array< T >::reverse_in_place ( )

inline

Alias for reverse().

Reverses this array in place.

Returns: A reference to *this, already reversed.

Exceptions

Any	exception thrown by swapping elements.

Note: Complexity: O(n). If a swap throws, some elements may already have changed positions.

See also: reverse()

Definition at line 479 of file tpl_array.H.

References Aleph::Array< T >::reverse().

Referenced by Aleph::Array< T >::rev().

◆ size()

template<typename T >

constexpr size_t Aleph::Array< T >::size ( ) const

inlineconstexprnoexcept

Return the number of elements stored in the stack.

Examples: dp_optimizations_example.cc, knapsack_example.cc, lis_example.cc, matrix_chain_example.cc, and subset_sum_example.cc.

Definition at line 365 of file tpl_array.H.

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

◆ swap()

template<typename T >

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

inlinenoexcept

Swap this with s

Definition at line 232 of file tpl_array.H.

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

Referenced by Aleph::Convex_Hull_Trick< T >::clear(), Aleph::Li_Chao_Tree< T >::clear(), Aleph::divide_and_conquer_partition_dp(), Aleph::levenshtein_distance(), Aleph::longest_common_substring(), Aleph::Array< T >::operator=(), Aleph::Gen_Cartesian_Tree< T, Comp >::swap(), Aleph::Gen_Fenwick_Tree< T, Plus, Minus >::swap(), Aleph::Gen_Lazy_Segment_Tree< Policy >::swap(), Aleph::Gen_Sparse_Table< T, Op >::swap(), and Aleph::Quotient_Filter< T >::swap().

◆ to_array()

template<typename T >

Array Aleph::Array< T >::to_array ( ) const

inline

Copy to Aleph::Array (requires copyable elements).

Definition at line 597 of file tpl_array.H.

Referenced by Aleph::Two_Sat< GT >::add_at_most_one().

◆ traverse() [1/4]

template<typename T >

template<class Op >
requires std::predicate<Op &, T &>

bool Aleph::Array< T >::traverse ( Op && op )

inline

Traverse mutable elements with a temporary operation.

Kept as a separate overload from traverse(Op &) so that callers naming the operation type explicitly, as traverse<Op>(lvalue) does in Aleph::all(), still bind to the lvalue overload.

Parameters

[in] op Operation accepting T &.

Returns: true if every element was visited; false if stopped early.

Exceptions

Any	exception thrown by `op`.

Note: Time: O(n) in the number of visited elements; auxiliary space: O(1).; If op throws, changes it already made to elements are not undone.; Concurrent read-only traversals are safe when op only reads. External synchronization is required if any concurrent access may modify the array.

Definition at line 567 of file tpl_array.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ traverse() [2/4]

template<typename T >

template<class Op >
requires std::predicate<Op &, const T &>

bool Aleph::Array< T >::traverse ( Op && op ) const

inline

Traverse const elements with a temporary operation.

Parameters

[in] op Operation accepting const T &.

Returns: true if every element was visited; false if stopped early.

Exceptions

Any	exception thrown by `op`.

Note: Time: O(n) in the number of visited elements; auxiliary space: O(1).; The traversal itself does not modify elements. Effects of op outside the array are not rolled back if it throws.; Concurrent read-only access is safe when op only reads. External synchronization is required if another thread may modify the array.

Definition at line 586 of file tpl_array.H.

References Aleph::blossom_maximum_cardinality_matching().

◆ traverse() [3/4]

template<typename T >

template<class Op >
requires std::predicate<Op &, T &>

bool Aleph::Array< T >::traverse ( Op & op )

inline

Traverse mutable elements from first to last.

Parameters

[in] op Operation accepting T &; returning false stops traversal.

Returns: true if every element was visited; false if stopped early.

Exceptions

Any	exception thrown by `op`.

Note: Time: O(n) in the number of visited elements; auxiliary space: O(1).; If op throws, changes it already made to elements are not undone.; Concurrent read-only traversals are safe when op only reads. External synchronization is required if any concurrent access may modify the array.

Definition at line 524 of file tpl_array.H.

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

◆ traverse() [4/4]

template<typename T >

template<class Op >
requires std::predicate<Op &, const T &>

bool Aleph::Array< T >::traverse ( Op & op ) const

inline

Traverse const elements from first to last.

Parameters

[in] op Operation accepting const T &; returning false stops traversal.

Returns: true if every element was visited; false if stopped early.

Exceptions

Any	exception thrown by `op`.

Note: Time: O(n) in the number of visited elements; auxiliary space: O(1).; The traversal itself does not modify elements. Effects of op outside the array are not rolled back if it throws.; Concurrent read-only access is safe when op only reads. External synchronization is required if another thread may modify the array.

Definition at line 543 of file tpl_array.H.

References Aleph::blossom_maximum_cardinality_matching(), and Aleph::Array< T >::size().

Member Data Documentation

◆ array

template<typename T >

MemArray<T> Aleph::Array< T >::array

private

Definition at line 139 of file tpl_array.H.

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

Classes

Public Types

Public Member Functions

Static Public Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Item_Type

◆ Key_Type

Constructor & Destructor Documentation

◆ Array() [1/9]

◆ Array() [2/9]

◆ Array() [3/9]

◆ Array() [4/9]

◆ Array() [5/9]

◆ Array() [6/9]

◆ Array() [7/9]

◆ Array() [8/9]

◆ Array() [9/9]

Member Function Documentation

◆ append() [1/4]

◆ append() [2/4]

◆ append() [3/4]

◆ append() [4/4]

◆ base() [1/2]

◆ base() [2/2]

◆ capacity()

◆ clear()

◆ create()

◆ empty()

◆ get_first() [1/2]

◆ get_first() [2/2]

◆ get_last() [1/2]

◆ get_last() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ is_empty()

◆ is_valid()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ putn()

◆ remove_first()

◆ remove_last()

◆ reserve()

◆ rev() [1/2]

◆ rev() [2/2]

◆ reverse() [1/2]

◆ reverse() [2/2]

◆ reverse_in_place()

◆ size()

◆ swap()

◆ to_array()

◆ traverse() [1/4]

◆ traverse() [2/4]

◆ traverse() [3/4]

◆ traverse() [4/4]

Member Data Documentation

◆ array