Algorithms on Sequences and Sets

Collaboration diagram for Algorithms on Sequences and Sets:


Modules
	Helper functors for common tasks
	Set Algorithms
	Algorithms on strings
Functions
template<class ForwardIterator , class Map >
void	GrAL::sequence::compute_histogram (ForwardIterator begin, ForwardIterator end, Map &hist)
	Compute a histogram from a sequence.
template<class ForwardIterator , class Map , class F >
void	GrAL::sequence::compute_histogram (ForwardIterator begin, ForwardIterator end, Map &hist, F f)
	Compute a histogram from a mapped sequence.
template<class Map >
Map::const_iterator	GrAL::sequence::arg_max_map (Map const &map)
	find iterator with maximum value in map
template<typename InputIterator , typename Predicate >
bool	GrAL::sequence::exists (InputIterator first, InputIterator end, Predicate p)
	Check whether any item `i` in [first,end[ exist with `p(i) == true` .
template<typename InputIterator , typename Predicate >
bool	GrAL::sequence::forall (InputIterator first, InputIterator end, Predicate p)
	Check whether for each item `i` in [first,end[ the condition `p(i) == true` holds.
template<typename InputIterator , typename Value >
bool	GrAL::sequence::contains (InputIterator first, InputIterator end, Value const &v)
	Check whether `v` is contained in the set [first,end[.
template<typename InputIterator >
std::iterator_traits < InputIterator >::value_type	GrAL::sequence::sum (InputIterator first, InputIterator end)
	Calculate sum of the sequence.
template<typename InputIterator >
std::iterator_traits < InputIterator >::value_type	GrAL::sequence::average (InputIterator first, InputIterator end)
	Calculate average of the sequence.
template<class It >
std::string	GrAL::sequence::concat (It start, It end, std::string sep="")
	Concatenate a sequence of items, with optional separator.
template<typename ForwardIterator , typename Less >
int	GrAL::sequence::bubble_sort (ForwardIterator begin, ForwardIterator end, Less less)
	The classic bubble sort.
template<typename ForwardIterator1 , typename ForwardIterator2 >
bool	GrAL::sequence::same_permutation_sign (ForwardIterator1 begin1, ForwardIterator1 end1, ForwardIterator2 begin2, ForwardIterator2 end2)
	Check wether the two sequences have the same permutation sign.
template<class Container >
void	GrAL::sequence::sort_and_make_unique (Container &container)
	Make the container unique & sorted.
template<typename ForwardIterator , typename LessOp >
bool	GrAL::sequence::is_increasing (ForwardIterator begin, ForwardIterator end, LessOp less)
	Check whether the sequence is sorted increasingly.
template<typename ForwardIterator >
bool	GrAL::sequence::is_increasing (ForwardIterator begin, ForwardIterator end)
	Check whether the sequence is sorted increasingly, using `operator<` .
template<class Container >
bool	GrAL::sequence::is_increasing (Container const &container)
	Check whether the sequence is sorted increasingly, using `operator<` .
template<class Container , class Container2 >
void	GrAL::sequence::remove_set (Container &s, Container2 const &t)
	Remove second set from first.
template<class InputIt , class OutputIt , class Filter >
OutputIt	GrAL::sequence::copy_filter (InputIt b, InputIt e, OutputIt dest, Filter f)
	copy [b,e) to [dest, ...), mapping values with f. The output is the sequence f(b), ... f((e-1)).
template<class FwdIt , class P1 , class P2 >
FwdIt	GrAL::sequence::find_if_preference (FwdIt b, FwdIt e, const P1 &must_be, const P2 &should_be)
	find_if_preference tries to find an element that satisfies both predicates. Return value: i, where i is the first in [b,e) that satisfies must_be && should_be i, where i is the first in [b,e) that satisfies must_be, and no element in [b,e) satisfies should_be e, if no element in [b,e) satisfies must_be.
template<class M1 , class M2 >
void	GrAL::sequence::mapping_assign (M1 &dest, M2 const &src)
	Copy a mapping by iterating through its domain Template parameters M1: operator[] M2: operator[] typedef domain_type domain_type domain().

Detailed Description

This module contains algorithms on sequences, mostly slight variations on STL algorithms for convenience.

Function Documentation

template<class ForwardIterator , class Map >

void GrAL::sequence::compute_histogram	(	ForwardIterator	begin,
		ForwardIterator	end,
		Map &	hist
	)			`[inline]`

Compute a histogram from a sequence.

See also:: histogram_table

Definition at line 106 of file sequence-algorithms.h.

template<class ForwardIterator , class Map , class F >

void GrAL::sequence::compute_histogram	(	ForwardIterator	begin,
		ForwardIterator	end,
		Map &	hist,
		F	f
	)			`[inline]`

Compute a histogram from a mapped sequence.

Note:: In principle (and more to the spirit of the STL) this could be achieved by using compute_histogram(ForwardIterator begin, ForwardIterator end, Map & hist) where ForwardIterator is a mapped iterator.

See also:: histogram_table

Definition at line 124 of file sequence-algorithms.h.

template<typename InputIterator , typename Predicate >

bool GrAL::sequence::exists	(	InputIterator	first,
		InputIterator	end,
		Predicate	p
	)			`[inline]`

Check whether any item i in [first,end[ exist with p(i) == true .

See also:: test-sequence-algorithms.C

Definition at line 160 of file sequence-algorithms.h.

template<typename InputIterator , typename Predicate >

bool GrAL::sequence::forall	(	InputIterator	first,
		InputIterator	end,
		Predicate	p
	)			`[inline]`

Check whether for each item i in [first,end[ the condition p(i) == true holds.

See also:: test-sequence-algorithms.C

Definition at line 173 of file sequence-algorithms.h.

template<typename InputIterator , typename Value >

bool GrAL::sequence::contains	(	InputIterator	first,
		InputIterator	end,
		Value const &	v
	)			`[inline]`

Check whether v is contained in the set [first,end[.

See also:: test-sequence-algorithms.C

Definition at line 187 of file sequence-algorithms.h.

template<typename InputIterator >

std::iterator_traits<InputIterator>::value_type GrAL::sequence::sum	(	InputIterator	first,
		InputIterator	end
	)			`[inline]`

Calculate sum of the sequence.

See also:: test-sequence-algorithms.C

Definition at line 198 of file sequence-algorithms.h.

Referenced by GrAL::sequence::average().

template<typename InputIterator >

std::iterator_traits<InputIterator>::value_type GrAL::sequence::average	(	InputIterator	first,
		InputIterator	end
	)			`[inline]`

Calculate average of the sequence.

See also:: test-sequence-algorithms.C

Definition at line 210 of file sequence-algorithms.h.

References GrAL::sequence::sum().

template<typename ForwardIterator , typename Less >

int GrAL::sequence::bubble_sort	(	ForwardIterator	begin,
		ForwardIterator	end,
		Less	less
	)			`[inline]`

The classic bubble sort.

See also:: test-bubblesort.C

Definition at line 230 of file sequence-algorithms.h.

References GrAL::sequence::next().

Referenced by GrAL::sequence::same_permutation_sign().

template<typename ForwardIterator1 , typename ForwardIterator2 >

bool GrAL::sequence::same_permutation_sign	(	ForwardIterator1	begin1,
		ForwardIterator1	end1,
		ForwardIterator2	begin2,
		ForwardIterator2	end2
	)			`[inline]`

Check wether the two sequences have the same permutation sign.

Precondition:: The two sequences must be identical as sets

Postcondition:: The two sequences will be sorted

Definition at line 266 of file sequence-algorithms.h.

References GrAL::sequence::bubble_sort(), and REQUIRE.

template<class Container , class Container2 >

void GrAL::sequence::remove_set	(	Container &	s,
		Container2 const &	t
	)			`[inline]`

Remove second set from first.

The effect is equivalent to $s = s \setminus t$

Definition at line 336 of file sequence-algorithms.h.

References GrAL::sequence::is_increasing(), and REQUIRE.

template<class InputIt , class OutputIt , class Filter >

OutputIt GrAL::sequence::copy_filter	(	InputIt	b,
		InputIt	e,
		OutputIt	dest,
		Filter	f
	)			`[inline]`

copy [b,e) to [dest, ...), mapping values with f.

The output is the sequence f(*b), ... f(*(e-1)).

This algorithm could also be expressed using std::copy and an iterator-adaptor of InputIt using Filter. However, as a filter rather operates on the corresponding value_type, this version seems to be more natural.

Todo:: Use std::transform(b,e,dest,f) instead.

Definition at line 380 of file sequence-algorithms.h.

Algorithms on Sequences and Sets

Modules

Functions

Detailed Description

Function Documentation