Fixed-capacity binary heap backed by a raw array. More...

#include <tpl_arrayHeap.H>

Inheritance diagram for Aleph::ArrayHeap< T, Compare >:

Collaboration diagram for Aleph::ArrayHeap< T, Compare >:

Classes
struct	Iterator

Public Types
using	Item_Type = T

using	Key_Type = T

Public Types inherited from StlAlephIterator< SetName >
using	iterator = StlIterator< SetName >

using	const_iterator = StlConstIterator< SetName >

Public Member Functions
void	allocate_storage (const size_t new_dim)
	Allocate internal storage and reset the heap.

void	swap (ArrayHeap &h) noexcept
	Swap all state with another heap.

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

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

	ArrayHeap (std::initializer_list< T > l)

	ArrayHeap (const size_t d=1024, Compare cmp_fct=Compare())
	Construct an empty heap with internal storage.

	ArrayHeap (T *ptr, const size_t &d, Compare cmp_fct=Compare())
	Construct an empty heap using an external buffer.

	ArrayHeap (const ArrayHeap &h)

	ArrayHeap (ArrayHeap &&h) noexcept

ArrayHeap &	operator= (const ArrayHeap &h)

ArrayHeap &	operator= (ArrayHeap &&h) noexcept

virtual	~ArrayHeap ()
	Destructor.

T &	top ()
	Return a mutable reference to the minimum element.

const T &	top () const
	Return a const reference to the minimum element.

T &	insert_ne (const T &key)
	Insert an element without checking capacity.

T &	insert_ne (T &&key)
	Insert an element without checking capacity (move overload).

T &	insert (const T &key)
	Insert an element into the heap.

T &	insert (T &&key)
	Insert an element into the heap (move overload).

T &	put (const T &key)
	Synonym for insert().

T &	append (const T &key)
	Synonym for insert().

T &	put (T &&key)
	Synonym for insert() (move overload).

T &	append (T &&key)
	Synonym for insert() (move overload).

T	getMin ()
	Remove the smallest element in the heap and return a copy of its value.

T	get ()

T	getMax ()

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

constexpr bool	is_empty () const noexcept
	Return true if the heap is empty.

constexpr size_t	capacity () const noexcept
	Return the maximum number of elements that can be stored.

void	update (T &data)
	Update the priority of an element stored in the heap.

void	remove (T &item)
	Remove an element from the heap given a reference to it.

T &	operator[] (const size_t i)
	Return a mutable reference to the i-th entry (1-based).

const T &	operator[] (const size_t i) const
	Const overload of operator[] (1-based).

template<class Operation >
bool	traverse (Operation &operation) const
	Traverse all elements (const overload).

template<class Operation >
bool	traverse (Operation &operation)
	Traverse all elements.

template<class Operation >
bool	traverse (Operation &&operation=Operation()) const
	Traverse all elements (const forwarding overload).

template<class Operation >
bool	traverse (Operation &&operation=Operation())
	Traverse all elements (forwarding overload).

Public Member Functions inherited from LocateFunctions< Container, Type >
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()`.

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

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

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

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

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

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

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

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

template<class Operation >
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.

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

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

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

template<class Operation >
std::tuple< bool, Type >	find_item (Operation &&operation) noexcept(operation_is_noexcept< Operation >())

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

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

template<typename ... Args>
void	emplace_end (Args &&... args)

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

template<typename ... Args>
size_t	ninsert (Args ... args)
	Insert n variadic items.

template<typename ... Args>
size_t	nappend (Args ... args)
	Append n variadic items.

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

template<class Operation >
void	for_each (Operation &operation) const
	Const overload of `for_each(Operation&)`.

template<class Operation >
void	for_each (Operation &&operation) const
	Overload of `for_each(Operation&) const` that accepts rvalues.

template<class Operation >
void	for_each (Operation &&operation)
	Overload of `for_each(Operation&)` that accepts rvalues.

template<class Operation >
void	each (Operation &operation)
	Alias of `for_each(Operation&)`.

template<class Operation >
void	each (Operation &operation) const
	Const alias of `for_each(Operation&)`.

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

template<class Operation >
void	each (Operation &&operation)
	Alias of `for_each(Operation&)` that accepts rvalues.

template<class Operation >
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.

template<class Operation >
void	each (const size_t pos, const size_t slice, Operation &&operation) const

template<class Operation >
void	mutable_for_each (Operation &operation)

template<class Operation >
void	mutable_for_each (Operation &&operation)

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

template<class Operation >
bool	all (Operation &&operation) const
	Overload of `all(Operation&)` that accepts rvalues.

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

template<class Operation >
bool	exists (Operation &&op) const
	Overload of `exists(Operation&)` that accepts rvalues.

template<typename __T = T, class Operation = Aleph::Dft_Map_Op<T, __T>>
Aleph::DynList< __T >	maps (Operation &op) const
	Map the elements of the container.

template<typename __T = T, class Operation = Aleph::Dft_Map_Op<__T, __T>>
Aleph::DynList< __T >	maps (Operation &&op) const
	Overload of `maps(Operation&)` that accepts rvalues.

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

template<typename __T = T, class Prop , class Operation >
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.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &op) const
	Fold the elements of the container to a specific result.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	foldl (const __T &init, Op &&op=Op()) const
	Overload of `foldl(const __T&, Op&)` that accepts rvalues.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &op) const
	Alias for foldl with the same accumulator type.

template<typename __T = T, class Op = Aleph::Dft_Fold_Op<__T, T>>
__T	fold_left (const __T &init, Op &&op=Op()) const
	Overload of `fold_left(const __T&, Op&)` that accepts rvalues.

template<class Operation >
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.

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

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

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

template<class Operation >
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.

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

template<class Operation >
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.

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

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

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

template<class Operation >
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.

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

template<class Operation >
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< Container >
bool	equal_to (const Container &r) const noexcept
	Test if elements of `this` are exactly contained in another container.

bool	operator== (const Container &r) const noexcept

bool	operator!= (const Container &r) const noexcept
	Negation of equal_to()

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

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

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

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 Member Functions
template<class Operation >
bool	traverse_impl (Operation &operation)

Static Private Member Functions
static size_t	r_index (const size_t &i)

Private Attributes
T *	array = nullptr

size_t	dim = 0

size_t	num_items = 0

bool	array_allocated = false

Compare	cmp

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

	each

	each

Detailed Description

template<typename T, class Compare = Aleph::less<T>>
class Aleph::ArrayHeap< T, Compare >

Fixed-capacity binary heap backed by a raw array.

The heap stores elements from index 1 to num_items and keeps index 0 as sentinel, which simplifies the parent/child arithmetic.

Template Parameters

T	element type
Compare	comparator defining the priority order

See also: DynArrayHeap BinHeap DynBinHeap

Definition at line 264 of file tpl_arrayHeap.H.

Member Typedef Documentation

◆ Item_Type

template<typename T , class Compare = Aleph::less<T>>

using Aleph::ArrayHeap< T, Compare >::Item_Type = T

Definition at line 316 of file tpl_arrayHeap.H.

◆ Key_Type

template<typename T , class Compare = Aleph::less<T>>

using Aleph::ArrayHeap< T, Compare >::Key_Type = T

Definition at line 318 of file tpl_arrayHeap.H.

Constructor & Destructor Documentation

◆ ArrayHeap() [1/7]

template<typename T , class Compare = Aleph::less<T>>

template<template< typename > class List>

Aleph::ArrayHeap< T, Compare >::ArrayHeap ( const List< T > & l )

inline

Definition at line 320 of file tpl_arrayHeap.H.

◆ ArrayHeap() [2/7]

template<typename T , class Compare = Aleph::less<T>>

template<class It >

Aleph::ArrayHeap< T, Compare >::ArrayHeap	(	It	b,
		It	e
	)

inline

Definition at line 320 of file tpl_arrayHeap.H.

◆ ArrayHeap() [3/7]

template<typename T , class Compare = Aleph::less<T>>

Aleph::ArrayHeap< T, Compare >::ArrayHeap ( std::initializer_list< T > l )

inline

Definition at line 320 of file tpl_arrayHeap.H.

◆ ArrayHeap() [4/7]

template<typename T , class Compare = Aleph::less<T>>

Aleph::ArrayHeap< T, Compare >::ArrayHeap	(	const size_t	d = `1024`,
		Compare	cmp_fct = `Compare()`
	)

inline

Construct an empty heap with internal storage.

Parameters

[in]	d	capacity (number of usable heap slots)
[in]	cmp_fct	comparator

Exceptions

invalid_argument if d == 0

Definition at line 328 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::allocate_storage().

◆ ArrayHeap() [5/7]

template<typename T , class Compare = Aleph::less<T>>

Aleph::ArrayHeap< T, Compare >::ArrayHeap	(	T *	ptr,
		const size_t &	d,
		Compare	cmp_fct = `Compare()`
	)

inline

Construct an empty heap using an external buffer.

The heap will not manage the lifetime of ptr.

Parameters

[in]	ptr	external buffer (must have at least `d + 1` elements)
[in]	d	capacity (number of usable heap slots)
[in]	cmp_fct	comparator

Exceptions

invalid_argument if ptr == nullptr or d == 0

Definition at line 343 of file tpl_arrayHeap.H.

References ah_invalid_argument_if, and FunctionalMethods< Container, T >::maps().

◆ ArrayHeap() [6/7]

template<typename T , class Compare = Aleph::less<T>>

Aleph::ArrayHeap< T, Compare >::ArrayHeap ( const ArrayHeap< T, Compare > & h )

inline

Definition at line 349 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::allocate_storage(), Aleph::ArrayHeap< T, Compare >::array, h, and Aleph::ArrayHeap< T, Compare >::num_items.

◆ ArrayHeap() [7/7]

template<typename T , class Compare = Aleph::less<T>>

Aleph::ArrayHeap< T, Compare >::ArrayHeap ( ArrayHeap< T, Compare > && h )

inlinenoexcept

Definition at line 358 of file tpl_arrayHeap.H.

References h, and Aleph::ArrayHeap< T, Compare >::swap().

◆ ~ArrayHeap()

template<typename T , class Compare = Aleph::less<T>>

virtual Aleph::ArrayHeap< T, Compare >::~ArrayHeap ( )

inlinevirtual

Destructor.

Definition at line 388 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::array, Aleph::ArrayHeap< T, Compare >::array_allocated, and FunctionalMethods< Container, T >::maps().

Member Function Documentation

◆ allocate_storage()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::ArrayHeap< T, Compare >::allocate_storage ( const size_t new_dim )

inline

Allocate internal storage and reset the heap.

Parameters

[in] new_dim new capacity (number of usable heap slots)

Exceptions

invalid_argument if new_dim == 0

Definition at line 289 of file tpl_arrayHeap.H.

References ah_invalid_argument_if, Aleph::ArrayHeap< T, Compare >::array, Aleph::ArrayHeap< T, Compare >::array_allocated, Aleph::ArrayHeap< T, Compare >::dim, FunctionalMethods< Container, T >::maps(), and Aleph::ArrayHeap< T, Compare >::num_items.

Referenced by Aleph::ArrayHeap< T, Compare >::ArrayHeap(), Aleph::ArrayHeap< T, Compare >::ArrayHeap(), and Aleph::ArrayHeap< T, Compare >::operator=().

◆ append() [1/2]

template<typename T , class Compare = Aleph::less<T>>

T & Aleph::ArrayHeap< T, Compare >::append ( const T & key )

inline

Synonym for insert().

Parameters

[in] key value to insert

Returns: a mutable reference to the inserted element

See also: insert()

Definition at line 483 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::insert().

◆ append() [2/2]

template<typename T , class Compare = Aleph::less<T>>

T & Aleph::ArrayHeap< T, Compare >::append ( T && key )

inline

Synonym for insert() (move overload).

Parameters

[in] key value to insert

Returns: a mutable reference to the inserted element

See also: insert(T &&)

Definition at line 499 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::insert().

◆ capacity()

template<typename T , class Compare = Aleph::less<T>>

constexpr size_t Aleph::ArrayHeap< T, Compare >::capacity ( ) const

inlineconstexprnoexcept

Return the maximum number of elements that can be stored.

This excludes the sentinel slot at index 0.

Definition at line 542 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::dim.

◆ get()

template<typename T , class Compare = Aleph::less<T>>

T Aleph::ArrayHeap< T, Compare >::get ( )

inline

Definition at line 521 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::getMin().

Referenced by TEST().

◆ getMax()

template<typename T , class Compare = Aleph::less<T>>

T Aleph::ArrayHeap< T, Compare >::getMax ( )

inline

Definition at line 527 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::getMin().

Referenced by TEST().

◆ getMin()

template<typename T , class Compare = Aleph::less<T>>

Aleph::ArrayHeap< T, Compare >::getMin ( )

inline

Remove the smallest element in the heap and return a copy of its value.

getMin() extracts the element with the lowest value according to the configured comparator.

Exceptions

underflow_error if the heap is empty.

Returns: a copy of the removed value.

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 509 of file tpl_arrayHeap.H.

References ah_underflow_error_if, Aleph::ArrayHeap< T, Compare >::array, Aleph::ArrayHeap< T, Compare >::cmp, FunctionalMethods< Container, T >::maps(), Aleph::ArrayHeap< T, Compare >::num_items, and Aleph::sift_down().

Referenced by Aleph::ArrayHeap< T, Compare >::get(), Aleph::ArrayHeap< T, Compare >::getMax(), TEST(), and TEST().

◆ insert() [1/2]

template<typename T , class Compare = Aleph::less<T>>

T & Aleph::ArrayHeap< T, Compare >::insert ( const T & key )

inline

Insert an element into the heap.

insert(key) stores a copy of key inside the heap.

Parameters

[in] key value to insert.

Returns: a mutable reference to the inserted element.

Exceptions

overflow_error if the internal array is full.

Definition at line 450 of file tpl_arrayHeap.H.

References ah_overflow_error_if, Aleph::ArrayHeap< T, Compare >::dim, Aleph::ArrayHeap< T, Compare >::insert_ne(), and Aleph::ArrayHeap< T, Compare >::num_items.

Referenced by Aleph::ArrayHeap< T, Compare >::append(), Aleph::ArrayHeap< T, Compare >::append(), main(), Aleph::ArrayHeap< T, Compare >::put(), Aleph::ArrayHeap< T, Compare >::put(), TEST(), TEST(), TEST(), and TEST().

◆ insert() [2/2]

template<typename T , class Compare = Aleph::less<T>>

T & Aleph::ArrayHeap< T, Compare >::insert ( T && key )

inline

Insert an element into the heap (move overload).

Parameters

[in] key value to insert

Returns: a mutable reference to the inserted element

Exceptions

overflow_error if the internal array is full

See also: insert(const T &)

Definition at line 463 of file tpl_arrayHeap.H.

References ah_overflow_error_if, Aleph::ArrayHeap< T, Compare >::dim, Aleph::ArrayHeap< T, Compare >::insert_ne(), and Aleph::ArrayHeap< T, Compare >::num_items.

◆ insert_ne() [1/2]

template<typename T , class Compare = Aleph::less<T>>

T & Aleph::ArrayHeap< T, Compare >::insert_ne ( const T & key )

inline

Insert an element without checking capacity.

Parameters

[in] key value to insert

Returns: a mutable reference to the inserted element

Warning: This method does not check for overflow.

See also: insert()

Definition at line 423 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::array, Aleph::ArrayHeap< T, Compare >::cmp, Aleph::ArrayHeap< T, Compare >::num_items, and Aleph::sift_up().

Referenced by Aleph::ArrayHeap< T, Compare >::insert(), and Aleph::ArrayHeap< T, Compare >::insert().

◆ insert_ne() [2/2]

template<typename T , class Compare = Aleph::less<T>>

T & Aleph::ArrayHeap< T, Compare >::insert_ne ( T && key )

inline

Insert an element without checking capacity (move overload).

Parameters

[in] key value to insert

Returns: a mutable reference to the inserted element

Warning: This method does not check for overflow.

See also: insert()

Definition at line 436 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::array, Aleph::ArrayHeap< T, Compare >::cmp, Aleph::ArrayHeap< T, Compare >::num_items, and Aleph::sift_up().

◆ is_empty()

template<typename T , class Compare = Aleph::less<T>>

constexpr bool Aleph::ArrayHeap< T, Compare >::is_empty ( ) const

inlineconstexprnoexcept

Return true if the heap is empty.

Definition at line 536 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::num_items.

Referenced by TEST(), and TEST().

◆ operator=() [1/2]

template<typename T , class Compare = Aleph::less<T>>

ArrayHeap & Aleph::ArrayHeap< T, Compare >::operator= ( ArrayHeap< T, Compare > && h )

inlinenoexcept

Definition at line 380 of file tpl_arrayHeap.H.

References h, and Aleph::ArrayHeap< T, Compare >::swap().

◆ operator=() [2/2]

template<typename T , class Compare = Aleph::less<T>>

ArrayHeap & Aleph::ArrayHeap< T, Compare >::operator= ( const ArrayHeap< T, Compare > & h )

inline

Definition at line 364 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::allocate_storage(), Aleph::ArrayHeap< T, Compare >::array, Aleph::ArrayHeap< T, Compare >::cmp, Aleph::ArrayHeap< T, Compare >::dim, h, and Aleph::ArrayHeap< T, Compare >::num_items.

◆ operator[]() [1/2]

template<typename T , class Compare = Aleph::less<T>>

T & Aleph::ArrayHeap< T, Compare >::operator[] ( const size_t i )

inline

Return a mutable reference to the i-th entry (1-based).

No bounds checking is performed.

Parameters

[in] i index

Returns: mutable reference to entry i

Definition at line 599 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::array.

◆ operator[]() [2/2]

template<typename T , class Compare = Aleph::less<T>>

const T & Aleph::ArrayHeap< T, Compare >::operator[] ( const size_t i ) const

inline

Const overload of operator[] (1-based).

Parameters

[in] i index

Returns: const reference to entry i

Definition at line 609 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::array.

◆ put() [1/2]

template<typename T , class Compare = Aleph::less<T>>

T & Aleph::ArrayHeap< T, Compare >::put ( const T & key )

inline

Synonym for insert().

Parameters

[in] key value to insert

Returns: a mutable reference to the inserted element

See also: insert()

Definition at line 475 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::insert().

◆ put() [2/2]

template<typename T , class Compare = Aleph::less<T>>

T & Aleph::ArrayHeap< T, Compare >::put ( T && key )

inline

Synonym for insert() (move overload).

Parameters

[in] key value to insert

Returns: a mutable reference to the inserted element

See also: insert(T &&)

Definition at line 491 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::insert().

◆ r_index()

template<typename T , class Compare = Aleph::less<T>>

static size_t Aleph::ArrayHeap< T, Compare >::r_index ( const size_t & i )

inlinestaticprivate

Definition at line 278 of file tpl_arrayHeap.H.

◆ remove()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::ArrayHeap< T, Compare >::remove ( T & item )

inline

Remove an element from the heap given a reference to it.

The reference must refer to an element stored in this heap.

Parameters

[in,out] item reference to the element to remove

Exceptions

underflow_error if the heap is empty

Note: It is essential that item is a valid reference into this heap.

Definition at line 575 of file tpl_arrayHeap.H.

References ah_underflow_error_if, Aleph::ArrayHeap< T, Compare >::array, Aleph::ArrayHeap< T, Compare >::cmp, FunctionalMethods< Container, T >::maps(), Aleph::ArrayHeap< T, Compare >::num_items, and Aleph::sift_down_up().

Referenced by TEST().

◆ size()

template<typename T , class Compare = Aleph::less<T>>

constexpr size_t Aleph::ArrayHeap< T, Compare >::size ( ) const

inlineconstexprnoexcept

Return the number of elements currently stored.

Definition at line 533 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::num_items.

Referenced by exists_in_heap(), main(), TEST(), and TEST().

◆ swap()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::ArrayHeap< T, Compare >::swap ( ArrayHeap< T, Compare > & h )

inlinenoexcept

Swap all state with another heap.

Parameters

[in,out] h other heap

Definition at line 307 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::array, Aleph::ArrayHeap< T, Compare >::array_allocated, Aleph::ArrayHeap< T, Compare >::cmp, Aleph::ArrayHeap< T, Compare >::dim, h, and Aleph::ArrayHeap< T, Compare >::num_items.

Referenced by Aleph::ArrayHeap< T, Compare >::ArrayHeap(), and Aleph::ArrayHeap< T, Compare >::operator=().

◆ top() [1/2]

template<typename T , class Compare = Aleph::less<T>>

T & Aleph::ArrayHeap< T, Compare >::top ( )

inline

Return a mutable reference to the minimum element.

Exceptions

underflow_error if the heap is empty

Definition at line 398 of file tpl_arrayHeap.H.

References ah_underflow_error_if, Aleph::ArrayHeap< T, Compare >::array, and Aleph::ArrayHeap< T, Compare >::num_items.

Referenced by main(), TEST(), and TEST().

◆ top() [2/2]

template<typename T , class Compare = Aleph::less<T>>

const T & Aleph::ArrayHeap< T, Compare >::top ( ) const

inline

Return a const reference to the minimum element.

Exceptions

underflow_error if the heap is empty

Definition at line 409 of file tpl_arrayHeap.H.

References ah_underflow_error_if, Aleph::ArrayHeap< T, Compare >::array, and Aleph::ArrayHeap< T, Compare >::num_items.

◆ traverse() [1/4]

template<typename T , class Compare = Aleph::less<T>>

template<class Operation >

bool Aleph::ArrayHeap< T, Compare >::traverse ( Operation && operation = Operation() )

inline

Traverse all elements (forwarding overload).

Template Parameters

Operation callable type

Parameters

[in] operation functor to apply

Returns: false if traversal was stopped early, true otherwise

Definition at line 681 of file tpl_arrayHeap.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::ArrayHeap< T, Compare >::traverse_impl().

◆ traverse() [2/4]

template<typename T , class Compare = Aleph::less<T>>

template<class Operation >

bool Aleph::ArrayHeap< T, Compare >::traverse ( Operation && operation = Operation() ) const

inline

Traverse all elements (const forwarding overload).

Template Parameters

Operation callable type

Parameters

[in] operation functor to apply

Returns: false if traversal was stopped early, true otherwise

Definition at line 669 of file tpl_arrayHeap.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::ArrayHeap< T, Compare >::traverse_impl().

◆ traverse() [3/4]

template<typename T , class Compare = Aleph::less<T>>

template<class Operation >

bool Aleph::ArrayHeap< T, Compare >::traverse ( Operation & operation )

inline

Traverse all elements.

Template Parameters

Operation callable type

Parameters

[in,out] operation functor to apply

Returns: false if traversal was stopped early, true otherwise

Definition at line 657 of file tpl_arrayHeap.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::ArrayHeap< T, Compare >::traverse_impl().

◆ traverse() [4/4]

template<typename T , class Compare = Aleph::less<T>>

template<class Operation >

bool Aleph::ArrayHeap< T, Compare >::traverse ( Operation & operation ) const

inline

Traverse all elements (const overload).

Iterates over indices [1, size()] and applies operation to each element until it returns false.

Template Parameters

Operation callable type

Parameters

[in,out] operation functor to apply

Returns: false if traversal was stopped early, true otherwise

Definition at line 645 of file tpl_arrayHeap.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::ArrayHeap< T, Compare >::traverse_impl().

◆ traverse_impl()

template<typename T , class Compare = Aleph::less<T>>

template<class Operation >

bool Aleph::ArrayHeap< T, Compare >::traverse_impl ( Operation & operation )

inlineprivate

Definition at line 625 of file tpl_arrayHeap.H.

References Aleph::ArrayHeap< T, Compare >::array, FunctionalMethods< Container, T >::maps(), and Aleph::ArrayHeap< T, Compare >::num_items.

Referenced by Aleph::ArrayHeap< T, Compare >::traverse(), Aleph::ArrayHeap< T, Compare >::traverse(), Aleph::ArrayHeap< T, Compare >::traverse(), and Aleph::ArrayHeap< T, Compare >::traverse().

◆ update()

template<typename T , class Compare = Aleph::less<T>>

void Aleph::ArrayHeap< T, Compare >::update ( T & data )

inline

Update the priority of an element stored in the heap.

update(data) takes a reference to an element inside the heap, presumably modified, and updates its priority inside the heap.

The reference must have been obtained via a previous call to insert().

Parameters

[in] data reference to the element inside the heap to update

See also: insert()

Note: It is essential that data is a valid reference into this heap. Results are unpredictable (and probably fatal) if this is not the case.

Definition at line 557 of file tpl_arrayHeap.H.

References ah_underflow_error_if, Aleph::ArrayHeap< T, Compare >::array, Aleph::ArrayHeap< T, Compare >::cmp, FunctionalMethods< Container, T >::maps(), Aleph::ArrayHeap< T, Compare >::num_items, and Aleph::sift_down_up().

Referenced by TEST().

Member Data Documentation

◆ array

template<typename T , class Compare = Aleph::less<T>>

T* Aleph::ArrayHeap< T, Compare >::array = nullptr

private

Definition at line 270 of file tpl_arrayHeap.H.

◆ array_allocated

template<typename T , class Compare = Aleph::less<T>>

bool Aleph::ArrayHeap< T, Compare >::array_allocated = false

mutableprivate

Definition at line 274 of file tpl_arrayHeap.H.

Referenced by Aleph::ArrayHeap< T, Compare >::~ArrayHeap(), Aleph::ArrayHeap< T, Compare >::allocate_storage(), and Aleph::ArrayHeap< T, Compare >::swap().

◆ cmp

template<typename T , class Compare = Aleph::less<T>>

Compare Aleph::ArrayHeap< T, Compare >::cmp

private

Definition at line 276 of file tpl_arrayHeap.H.

Referenced by Aleph::ArrayHeap< T, Compare >::getMin(), Aleph::ArrayHeap< T, Compare >::insert_ne(), Aleph::ArrayHeap< T, Compare >::insert_ne(), Aleph::ArrayHeap< T, Compare >::operator=(), Aleph::ArrayHeap< T, Compare >::remove(), Aleph::ArrayHeap< T, Compare >::swap(), and Aleph::ArrayHeap< T, Compare >::update().

◆ dim

template<typename T , class Compare = Aleph::less<T>>

size_t Aleph::ArrayHeap< T, Compare >::dim = 0

mutableprivate

Definition at line 271 of file tpl_arrayHeap.H.

Referenced by Aleph::ArrayHeap< T, Compare >::allocate_storage(), Aleph::ArrayHeap< T, Compare >::capacity(), Aleph::ArrayHeap< T, Compare >::insert(), Aleph::ArrayHeap< T, Compare >::insert(), Aleph::ArrayHeap< T, Compare >::operator=(), and Aleph::ArrayHeap< T, Compare >::swap().

◆ num_items

template<typename T , class Compare = Aleph::less<T>>

size_t Aleph::ArrayHeap< T, Compare >::num_items = 0

private

Definition at line 272 of file tpl_arrayHeap.H.

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

tpl_arrayHeap.H

Classes

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Item_Type

◆ Key_Type

Constructor & Destructor Documentation

◆ ArrayHeap() [1/7]

◆ ArrayHeap() [2/7]

◆ ArrayHeap() [3/7]

◆ ArrayHeap() [4/7]

◆ ArrayHeap() [5/7]

◆ ArrayHeap() [6/7]

◆ ArrayHeap() [7/7]

◆ ~ArrayHeap()

Member Function Documentation

◆ allocate_storage()

◆ append() [1/2]

◆ append() [2/2]

◆ capacity()

◆ get()

◆ getMax()

◆ getMin()

◆ insert() [1/2]

◆ insert() [2/2]

◆ insert_ne() [1/2]

◆ insert_ne() [2/2]

◆ is_empty()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ put() [1/2]

◆ put() [2/2]

◆ r_index()

◆ remove()

◆ size()

◆ swap()

◆ top() [1/2]

◆ top() [2/2]

◆ traverse() [1/4]

◆ traverse() [2/4]

◆ traverse() [3/4]

◆ traverse() [4/4]

◆ traverse_impl()

◆ update()

Member Data Documentation

◆ array

◆ array_allocated

◆ cmp

◆ dim

◆ num_items