Generic key-value map implemented on top of a binary search tree. More...

#include <tpl_dynMapTree.H>

Inheritance diagram for Aleph::DynMapTree< Key, Data, Tree, Compare >:

Collaboration diagram for Aleph::DynMapTree< Key, Data, Tree, Compare >:

Public Types
using	Key_Type = Key

using	Item_Type = Pair

using	Value_Type = Data

using	Iterator = typename Base::Iterator

Public Types inherited from Aleph::DynSetTree< Key, Tree, Compare >
using	Node = typename Tree< Key, Compare >::Node
	Type of binary node used by the binary search tree internal.

using	Tree_Type = Tree< Key, Compare >

typedef DynSetTree	Set_Type

typedef Key	Item_Type

typedef Key	Key_Type

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

using	const_iterator = StlConstIterator< SetName >

Public Member Functions
	DynMapTree (const DynList< Key > &keys)

	DynMapTree ()=default

Pair *	insert (const Key &key, const Data &data)
	Insert a key-value pair.

Pair *	insert (const Key &key, Data &&data=Data())

Pair *	insert (Key &&key, const Data &data)

Pair *	insert (Key &&key, Data &&data=Data())

Pair *	append (const Key &key, const Data &data)

Pair *	append (const Key &key, Data &&data=Data())

Pair *	append (Key &&key, const Data &data)

Pair *	append (Key &&key, Data &&data=Data())

Pair *	put (const Key &key, const Data &data)
	Alias for insert().

Pair *	put (const Key &key, Data &&data)

Pair *	put (Key &&key, const Data &data)

Pair *	put (Key &&key, Data &&data)

Data	remove (const Key &key)
	Deletes the pair `key,data`

Data	remove (Key &&key)

void	remove_key (const Key &key)

Pair *	search (const Key &key) const noexcept
	Collect all keys.

Pair *	search (Key &&key) const noexcept

bool	has (const Key &key) const noexcept

bool	has (Key &&key) const noexcept

bool	contains (const Key &key) const noexcept

bool	contains (Key &&key) const noexcept

Data &	find (const Key &key)
	Find the value associated with `key`.

const Data &	find (const Key &key) const

Data &	operator[] (const Key &key)

const Data &	operator[] (const Key &key) const

Data &	operator[] (Key &&key)

const Data &	operator[] (Key &&key) const

DynList< Key >	keys () const

DynList< Data >	values () const
	Collect all values.

DynList< Data * >	values_ptr ()
	Collect pointers to all values.

DynList< Pair * >	items_ptr ()
	Collect pointers to all stored pairs.

Key *	insert (const Key &key)
	Inserts a key into the dynamic set.

Key *	insert (Key &&key)

Public Member Functions inherited from Aleph::DynSetTree< Key, Tree, Compare >
void	swap (DynSetTree &dset) noexcept(noexcept(tree.swap(dset.tree)) and noexcept(std::swap(num_nodes, dset.num_nodes)) and noexcept(std::swap(arena_allocator, dset.arena_allocator)))
	Exchange all elements of this set with dset in constant time (and extremely fast).

	DynSetTree (const Compare &cmp=Compare())
	Instantiate a dynamic set.

	DynSetTree (const char *base_addr, const size_t &sz, const Compare &cmp=Compare())
	Instantiate a dynamic set using an arena allocator with external buffer.

	DynSetTree (const size_t &arena_sz, const Compare &cmp=Compare())
	Instantiate a dynamic set using an arena allocator with dynamic buffer.

	DynSetTree (const DynSetTree &srcTree)
	instantiates a dynamic copy of srcTree

template<template< typename > class List>
	DynSetTree (const List< Key > &l)

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

	DynSetTree (std::initializer_list< Key > l)

	DynSetTree (DynSetTree &&srcTree) noexcept

void	empty ()
	remove all elements from the set

DynSetTree &	operator= (const DynList< Key > &list)

DynSetTree &	operator= (const DynSetTree &srcTree)
	assigns this to the dynamic array srctree

DynSetTree &	operator= (DynSetTree &&srcTree) noexcept
	Assigns the dynamic set srcTree to this.

virtual	~DynSetTree ()
	Destroyer; all elements are released.

Key *	insert (const Key &key)
	Inserts a key into the dynamic set.

Key *	insert (Key &&key)

Key *	append (const Key &key)

Key *	append (Key &&key)

Key *	search_or_insert (const Key &key)
	Look for the key in the binary search tree or inserts it if it is not found.

Key *	search_or_insert (Key &&key)

std::pair< Key *, bool >	contains_or_insert (const Key &key)

std::pair< Key *, bool >	contains_or_insert (Key &&key)

Key *	insert_dup (const Key &key)

Key *	insert_dup (Key &&key)

Key *	put (const Key &key)

Key *	put (Key &&key)

size_t	remove (const Key &key)
	Removes a key from the dynamic set.

Key	del (const Key &key)
	Deletes `key` and returns a full copy of stored key.

Key	remove_pos (const size_t i)
	Removes a key from the dynamic set.

bool	exist (const Key &key) const
	Returns true if key belongs to the dynamic set.

bool	has (const Key &key) const

bool	contains (const Key &key) const

Key &	find (const Key &key) const
	Returns a modifiable reference to an element within the set.

std::pair< long, Key * >	find_position (const Key &key) const
	Returns the infix (ordinate) position of the key key or whatever It would be your position of belonging to the tree.

Key *	search (const Key &key) const
	Find an element in the set.

const Key &	min () const
	Returns the smallest key contained in the set according to the criterion comparison given.

const Key &	get_first () const

const Key &	max () const
	Returns the largest key contained in the set according to the criteria comparison given.

const Key &	get_last () const

const Key &	get () const
	Synonym of max.

const size_t &	size () const
	Returns the cardinality of the set.

bool	is_empty () const
	returns true if the set is empty

bool	uses_arena () const noexcept
	Returns true if the set is using an arena allocator.

size_t	arena_allocated_size () const noexcept
	Returns the allocated size from the arena (0 if not using arena)

size_t	arena_available_size () const noexcept
	Returns the available size in the arena (0 if not using arena)

size_t	internal_path_length () const
	Calculates and returns the length of the internal path of the tree search binary.

Node *	get_root_node () const

const Key &	get_root () const

const Key &	get_item () const
	Returns any element of the set.

size_t	height () const
	Calculates and returns the height of the binary search tree.

template<class Op >
void	for_each_in_preorder (void(visitFct)(Node , int, int))
	Performs a prefix traversal over all nodes in the tree and invokes the `visitFct` operation on each visit.

long	position (const Key &key) const
	Returns the infix (ordered) position of the key.

Key &	select (size_t i)
	Returns the ith node in infix position.

const Key &	select (size_t i) const

Key &	operator() (size_t i)

const Key &	operator[] (const Key &key) const

const Key &	operator[] (const Key &key)

Key &	access (size_t i)

bool	verify () const

template<class Key_Op >
void	for_each_preorder (Key_Op &key_op) const
	Performs a prefix traversal over all keys in the set and invokes operation Op.

template<class Key_Op >
void	for_each_preorder (Key_Op &&key_op=Key_Op()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Performs a preorder traversal over all keys using a temporary operation object.

template<class Key_Op >
void	for_each_inorder (Key_Op &key_op) const
	Performs an infix traversal over all keys in the set and invokes operation Op.

template<class Key_Op >
void	for_each_inorder (Key_Op &&key_op=Key_Op()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Performs an infix traversal over all keys using a temporary operation object.

template<class Key_Op >
void	for_each_postorder (Key_Op &key_op) const
	Performs a postfix traversal over all keys in the set and invokes operation Op.

template<class Key_Op >
void	for_each_postorder (Key_Op &&key_op=Key_Op()) const
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Performs a postorder traversal over all keys using a temporary operation object.

DynSetTree &	join (DynSetTree &t, DynSetTree &dup)
	Union of two binary search trees.

DynSetTree &	join (DynSetTree &t, DynSetTree &&dup=DynSetTree())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Union of two binary search trees using a move-constructed duplicate tree.

DynSetTree &	join_dup (DynSetTree &t)
	Union of two binary search trees.

bool	split_key (const Key &key, DynSetTree &l, DynSetTree &r)
	Partitions the binary search tree based on a key.

void	split_pos (const size_t pos, DynSetTree &l, DynSetTree &r)
	Partitions the binary search tree based on an infix position.

void	split_key_dup (const Key &key, DynSetTree &l, DynSetTree &r)
	Partitions the binary search tree based on a key that may be present in the tree.

template<class Operation >
bool	traverse (Operation &op)
	Traverse all the set of pairs and for each key executes the operation op.

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

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

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

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.

Static Public Member Functions
static Data &	get_data (Key &key) noexcept

static const Data &	get_data (const Key &key) noexcept

static const Key &	get_key (Data *data_ptr) noexcept

static const Key &	get_key (const Data *data_ptr) noexcept

Private Types
using	Pair = std::pair< Key, Data >

using	Base = DynSetTree< std::pair< Key, Data >, Tree, Dft_Pair_Cmp< Key, Data, Compare > >

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

	each

	each

Detailed Description

template<typename Key, typename Data, template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>
class Aleph::DynMapTree< Key, Data, Tree, Compare >

Generic key-value map implemented on top of a binary search tree.

DynMapTree maps unique keys (Key) to values (Data). Internally it is a DynSetTree<std::pair<Key, Data>, ...> whose ordering compares pairs by their first component.

Template parameters:

Key: key type (map domain).
Data: mapped type (map range).
Tree: binary search tree type used for instrumentation.
Compare: ordering for keys.

Element access:

operator[] inserts a default-constructed Data when the key is missing.
find() throws std::domain_error when the key is missing.

Note: Several operations internally create a temporary Data() when building a search key (std::pair<Key, Data>). Therefore, those methods require Data to be default-constructible.

See also: BinTree Avl_Tree Splay_Tree Rb_Tree Treap Rand_Tree

Definition at line 85 of file tpl_dynMapTree.H.

Member Typedef Documentation

◆ Base

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

using Aleph::DynMapTree< Key, Data, Tree, Compare >::Base = DynSetTree<std::pair<Key, Data>, Tree, Dft_Pair_Cmp<Key, Data, Compare> >

private

Definition at line 91 of file tpl_dynMapTree.H.

◆ Item_Type

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

using Aleph::DynMapTree< Key, Data, Tree, Compare >::Item_Type = Pair

Definition at line 107 of file tpl_dynMapTree.H.

◆ Iterator

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

using Aleph::DynMapTree< Key, Data, Tree, Compare >::Iterator = typename Base::Iterator

Definition at line 317 of file tpl_dynMapTree.H.

◆ Key_Type

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

using Aleph::DynMapTree< Key, Data, Tree, Compare >::Key_Type = Key

Definition at line 105 of file tpl_dynMapTree.H.

◆ Pair

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

using Aleph::DynMapTree< Key, Data, Tree, Compare >::Pair = std::pair<Key, Data>

private

Definition at line 89 of file tpl_dynMapTree.H.

◆ Value_Type

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

using Aleph::DynMapTree< Key, Data, Tree, Compare >::Value_Type = Data

Definition at line 109 of file tpl_dynMapTree.H.

Constructor & Destructor Documentation

◆ DynMapTree() [1/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Aleph::DynMapTree< Key, Data, Tree, Compare >::DynMapTree ( const DynList< Key > & keys )

inline

Definition at line 98 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::DynMapTree< Key, Data, Tree, Compare >::keys(), and FunctionalMethods< Container, T >::maps().

◆ DynMapTree() [2/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Aleph::DynMapTree< Key, Data, Tree, Compare >::DynMapTree ( )

default

Member Function Documentation

◆ append() [1/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::append	(	const Key &	key,
		const Data &	data
	)

inline

Definition at line 165 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

Referenced by TEST().

◆ append() [2/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::append	(	const Key &	key,
		Data &&	data = `Data()`
	)

inline

Definition at line 170 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

◆ append() [3/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::append	(	Key &&	key,
		const Data &	data
	)

inline

Definition at line 175 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

◆ append() [4/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::append	(	Key &&	key,
		Data &&	data = `Data()`
	)

inline

Definition at line 180 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

◆ contains() [1/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynMapTree< Key, Data, Tree, Compare >::contains ( const Key & key ) const

inlinenoexcept

Definition at line 269 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::has().

Referenced by TEST().

◆ contains() [2/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynMapTree< Key, Data, Tree, Compare >::contains ( Key && key ) const

inlinenoexcept

Definition at line 271 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::has().

◆ find() [1/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Data & Aleph::DynMapTree< Key, Data, Tree, Compare >::find ( const Key & key )

inline

Find the value associated with key.

Parameters

[in] key Key to find.

Returns: Reference to the associated value.

Exceptions

std::domain_error If key is not present.

Definition at line 279 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::find(), and FunctionalMethods< Container, T >::maps().

Referenced by Aleph::Network_Simplex< Net >::ainfo(), Aleph::Network_Simplex< Net >::ainfo(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_path(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::compute_all_pairs_distances(), Aleph::Huffman_Encoder_Engine::encode(), Aleph::Huffman_Encoder_Engine::encode(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_distance(), Aleph::MCF_Graph< NodeT, ArcT >::get_node_index(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::get_potential(), Aleph::Network_Simplex< Net >::ninfo(), Aleph::Network_Simplex< Net >::ninfo(), Aleph::DynMapTree< Key, Data, Tree, Compare >::operator[](), Aleph::DynMapTree< Key, Data, Tree, Compare >::operator[](), Aleph::Xml_Graph< GT, Node_Reader, Arc_Reader, Node_Writer, Arc_Writer >::read_graph(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs(), save_level_pos_2(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle_on_partial_graph(), Aleph::MCF_LP_Solver< Net >::solve(), TEST(), TEST(), TEST(), TEST(), TEST(), Aleph::vertex_connectivity(), and Aleph::Xml_Graph< GT, Node_Reader, Arc_Reader, Node_Writer, Arc_Writer >::write_graph().

◆ find() [2/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Data & Aleph::DynMapTree< Key, Data, Tree, Compare >::find ( const Key & key ) const

inline

Definition at line 286 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::find(), and FunctionalMethods< Container, T >::maps().

◆ get_data() [1/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

static const Data & Aleph::DynMapTree< Key, Data, Tree, Compare >::get_data ( const Key & key )

inlinestaticnoexcept

Definition at line 119 of file tpl_dynMapTree.H.

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

◆ get_data() [2/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

static Data & Aleph::DynMapTree< Key, Data, Tree, Compare >::get_data ( Key & key )

inlinestaticnoexcept

Definition at line 114 of file tpl_dynMapTree.H.

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

Referenced by TEST().

◆ get_key() [1/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

static const Key & Aleph::DynMapTree< Key, Data, Tree, Compare >::get_key ( const Data * data_ptr )

inlinestaticnoexcept

Definition at line 129 of file tpl_dynMapTree.H.

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

◆ get_key() [2/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

static const Key & Aleph::DynMapTree< Key, Data, Tree, Compare >::get_key ( Data * data_ptr )

inlinestaticnoexcept

Definition at line 124 of file tpl_dynMapTree.H.

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

Referenced by TEST().

◆ has() [1/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynMapTree< Key, Data, Tree, Compare >::has ( const Key & key ) const

inlinenoexcept

Definition at line 265 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::search().

Referenced by Aleph::capacity_scaling_maximum_flow(), Aleph::DynMapTree< Key, Data, Tree, Compare >::contains(), Aleph::DynMapTree< Key, Data, Tree, Compare >::contains(), Aleph::restore_flow_solution(), TEST(), TEST(), TEST(), AHDispatcher< Key, Operation >::valid_key(), and Aleph::AHMapping< Key, ValueType >::valid_key().

◆ has() [2/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

bool Aleph::DynMapTree< Key, Data, Tree, Compare >::has ( Key && key ) const

inlinenoexcept

Definition at line 267 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::search().

◆ insert() [1/6]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::insert ( const Key & key )

inline

Inserts a key into the dynamic set.

Inserts the key into the dynamic set.

Parameters

[in] key key to insert.

Returns: pointer to the inserted key if it is not inside of the tree; nullptr otherwise.

Definition at line 646 of file tpl_dynSetTree.H.

◆ insert() [2/6]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::insert	(	const Key &	key,
		const Data &	data
	)

inline

Insert a key-value pair.

If key is already present, no insertion is performed and nullptr is returned.

Parameters

[in]	key	Key to insert.
[in]	data	Value to associate with `key`.

Returns: Pointer to the inserted pair, or nullptr if the key exists.

Exceptions

std::bad_alloc If there is not enough memory.

Definition at line 144 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

Referenced by AHDispatcher< Key, Operation >::AHDispatcher(), Aleph::AHMapping< Key, ValueType >::AHMapping(), Aleph::DynMapTree< Key, Data, Tree, Compare >::DynMapTree(), Aleph::MCF_LP_Solver< Net >::MCF_LP_Solver(), Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::MCF_Graph< NodeT, ArcT >::build_node_index(), Aleph::Huffman_Encoder_Engine::build_prefix_encoding(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::build_reverse_mappings(), Aleph::build_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::build_tree(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::compute_all_pairs_distances(), Aleph::Copy_Graph< GT, SN, SA >::copy(), Aleph::copy_graph(), Aleph::Network_Simplex< Net >::init_structures(), Aleph::AHMapping< Key, ValueType >::insert(), AHDispatcher< Key, Operation >::insert(), Aleph::Huffman_Encoder_Engine::insert_end_symbol_node(), Aleph::inter_copy_graph(), Aleph::DynMapTree< Key, Data, Tree, Compare >::put(), Aleph::DynMapTree< Key, Data, Tree, Compare >::put(), Aleph::DynMapTree< Key, Data, Tree, Compare >::put(), Aleph::DynMapTree< Key, Data, Tree, Compare >::put(), Aleph::Xml_Graph< GT, Node_Reader, Arc_Reader, Node_Writer, Arc_Writer >::read_graph(), save_level_pos_1(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::search_negative_cycle_on_partial_graph(), Aleph::Huffman_Encoder_Engine::set_freq(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST_F(), Aleph::Huffman_Encoder_Engine::update_freq(), Aleph::vertex_connectivity(), and Aleph::Xml_Graph< GT, Node_Reader, Arc_Reader, Node_Writer, Arc_Writer >::write_graph().

◆ insert() [3/6]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::insert	(	const Key &	key,
		Data &&	data = `Data()`
	)

inline

Definition at line 149 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

◆ insert() [4/6]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Key * Aleph::DynSetTree< Key, Tree, Compare >::insert ( Key && key )

inline

Definition at line 659 of file tpl_dynSetTree.H.

◆ insert() [5/6]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::insert	(	Key &&	key,
		const Data &	data
	)

inline

Definition at line 154 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

◆ insert() [6/6]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::insert	(	Key &&	key,
		Data &&	data = `Data()`
	)

inline

Definition at line 159 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::insert().

◆ items_ptr()

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

DynList< Pair * > Aleph::DynMapTree< Key, Data, Tree, Compare >::items_ptr ( )

inline

Collect pointers to all stored pairs.

Note: Pointers are valid until the tree is structurally modified.

Definition at line 349 of file tpl_dynMapTree.H.

References Aleph::DynList< T >::append(), and FunctionalMethods< Container, T >::maps().

Referenced by TEST().

◆ keys()

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

DynList< Key > Aleph::DynMapTree< Key, Data, Tree, Compare >::keys ( ) const

inline

Definition at line 319 of file tpl_dynMapTree.H.

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

Referenced by Aleph::DynMapTree< Key, Data, Tree, Compare >::DynMapTree(), AHDispatcher< Key, Operation >::keys(), Aleph::AHMapping< Key, ValueType >::keys(), and TEST().

◆ operator[]() [1/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Data & Aleph::DynMapTree< Key, Data, Tree, Compare >::operator[] ( const Key & key )

inline

Definition at line 293 of file tpl_dynMapTree.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::DynSetTree< Key, Tree, Compare >::search_or_insert().

◆ operator[]() [2/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Data & Aleph::DynMapTree< Key, Data, Tree, Compare >::operator[] ( const Key & key ) const

inline

Definition at line 300 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::find().

◆ operator[]() [3/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Data & Aleph::DynMapTree< Key, Data, Tree, Compare >::operator[] ( Key && key )

inline

Definition at line 305 of file tpl_dynMapTree.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::DynSetTree< Key, Tree, Compare >::search_or_insert().

◆ operator[]() [4/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

const Data & Aleph::DynMapTree< Key, Data, Tree, Compare >::operator[] ( Key && key ) const

inline

Definition at line 312 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::find().

◆ put() [1/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::put	(	const Key &	key,
		const Data &	data
	)

inline

Alias for insert().

Returns: Pointer to the inserted pair, or nullptr if the key exists.

Definition at line 190 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::insert().

Referenced by TEST().

◆ put() [2/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::put	(	const Key &	key,
		Data &&	data
	)

inline

Definition at line 195 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::insert().

◆ put() [3/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::put	(	Key &&	key,
		const Data &	data
	)

inline

Definition at line 200 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::insert().

◆ put() [4/4]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::put	(	Key &&	key,
		Data &&	data
	)

inline

Definition at line 205 of file tpl_dynMapTree.H.

References Aleph::DynMapTree< Key, Data, Tree, Compare >::insert().

◆ remove() [1/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Data Aleph::DynMapTree< Key, Data, Tree, Compare >::remove ( const Key & key )

inline

Deletes the pair key,data

remove(key) deletes from the mapping the pair associated to key

Parameters

[in] key to delete

Returns: the data associated with the removed key.

Exceptions

domain_error if the key is not in the mapping

Definition at line 218 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::del(), and FunctionalMethods< Container, T >::maps().

Referenced by AHDispatcher< Key, Operation >::remove(), Aleph::AHMapping< Key, ValueType >::remove(), and TEST().

◆ remove() [2/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Data Aleph::DynMapTree< Key, Data, Tree, Compare >::remove ( Key && key )

inline

Definition at line 226 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::del(), and FunctionalMethods< Container, T >::maps().

◆ remove_key()

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

void Aleph::DynMapTree< Key, Data, Tree, Compare >::remove_key ( const Key & key )

inline

Definition at line 234 of file tpl_dynMapTree.H.

References Aleph::DynSetTree< Key, Tree, Compare >::del(), and FunctionalMethods< Container, T >::maps().

Referenced by TEST().

◆ search() [1/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::search ( const Key & key ) const

inlinenoexcept

Collect all keys.

Returns: A DynList of keys, in the tree traversal order.

Search for a key.

Parameters

[in] key Key to search.

Returns: Pointer to the stored pair if found; nullptr otherwise.

Definition at line 251 of file tpl_dynMapTree.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::DynSetTree< Key, Tree, Compare >::search().

Referenced by Aleph::Tarjan_Connected_Components< GT, Itor, SA >::build_cycle(), Aleph::build_spanning_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::build_tree(), demo_config_store(), Aleph::DynMapTree< Key, Data, Tree, Compare >::has(), Aleph::DynMapTree< Key, Data, Tree, Compare >::has(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::map_copy_path_to_original(), Aleph::AHMapping< Key, ValueType >::operator[](), Aleph::Huffman_Encoder_Engine::read_input(), Aleph::Huffman_Encoder_Engine::read_input(), Aleph::Johnson< GT, Distance, Ait, NAit, SA >::reweight_arcs(), AHDispatcher< Key, Operation >::run(), Aleph::Huffman_Encoder_Engine::set_end_of_stream(), Aleph::Huffman_Encoder_Engine::set_freq(), TEST(), TEST(), and Aleph::Huffman_Encoder_Engine::update_freq().

◆ search() [2/2]

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

Pair * Aleph::DynMapTree< Key, Data, Tree, Compare >::search ( Key && key ) const

inlinenoexcept

Definition at line 258 of file tpl_dynMapTree.H.

References FunctionalMethods< Container, T >::maps(), and Aleph::DynSetTree< Key, Tree, Compare >::search().

◆ values()

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

DynList< Data > Aleph::DynMapTree< Key, Data, Tree, Compare >::values ( ) const

inline

Collect all values.

Returns: A DynList of values, in the tree traversal order.

Definition at line 328 of file tpl_dynMapTree.H.

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

Referenced by TEST().

◆ values_ptr()

template<typename Key , typename Data , template< typename, class > class Tree = Avl_Tree, class Compare = Aleph::less<Key>>

DynList< Data * > Aleph::DynMapTree< Key, Data, Tree, Compare >::values_ptr ( )

inline

Collect pointers to all values.

Note: Pointers are valid until the tree is structurally modified.

Definition at line 337 of file tpl_dynMapTree.H.

References Aleph::DynList< T >::append(), and FunctionalMethods< Container, T >::maps().

Referenced by TEST().

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

tpl_dynMapTree.H

Public Types

Public Member Functions

Static Public Member Functions

Private Types

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Base

◆ Item_Type

◆ Iterator

◆ Key_Type

◆ Pair

◆ Value_Type

Constructor & Destructor Documentation

◆ DynMapTree() [1/2]

◆ DynMapTree() [2/2]

Member Function Documentation

◆ append() [1/4]

◆ append() [2/4]

◆ append() [3/4]

◆ append() [4/4]

◆ contains() [1/2]

◆ contains() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ get_data() [1/2]

◆ get_data() [2/2]

◆ get_key() [1/2]

◆ get_key() [2/2]

◆ has() [1/2]

◆ has() [2/2]

◆ insert() [1/6]

◆ insert() [2/6]

◆ insert() [3/6]

◆ insert() [4/6]

◆ insert() [5/6]

◆ insert() [6/6]

◆ items_ptr()

◆ keys()

◆ operator[]() [1/4]

◆ operator[]() [2/4]

◆ operator[]() [3/4]

◆ operator[]() [4/4]

◆ put() [1/4]

◆ put() [2/4]

◆ put() [3/4]

◆ put() [4/4]

◆ remove() [1/2]

◆ remove() [2/2]

◆ remove_key()

◆ search() [1/2]

◆ search() [2/2]

◆ values()

◆ values_ptr()