selection [Algorithms]

Classes
struct	logical_xor< C1, C2 >
	xor funtion object More...
Functions
template<typename Selection , typename ForwardRange >
Selection	index_set_to_selection (const ForwardRange &index_set)
template<typename Selection >
void	invert (Selection &x)
template<typename Selection >
bool	is_selected (const Selection &x, typename Selection::value_type index)
template<typename Selection , typename ForwardRange , typename OutputIterator >
OutputIterator	selection_copy (const Selection &x, const ForwardRange &range, OutputIterator output)
template<typename Selection1 , typename Selection2 >
Selection1	selection_difference (const Selection1 &x, const Selection2 &y)
template<typename S1 , typename S2 , typename O , typename C >
O	selection_difference (S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp, bool s1_inside=false, bool s2_inside=false)
template<typename Selection >
std::pair< typename boost::range_const_iterator < Selection >::type, typename boost::range_size< Selection > ::type >	selection_find_boundary (const Selection &selection, typename Selection::size_type p, std::random_access_iterator_tag)
template<typename Selection >
std::pair< typename boost::range_const_iterator < Selection >::type, typename boost::range_size< Selection > ::type >	selection_find_boundary (const Selection &selection, typename Selection::size_type p, std::forward_iterator_tag)
template<typename Selection >
std::pair< typename boost::range_const_iterator < Selection >::type, typename boost::range_size< Selection > ::type >	selection_find_boundary (const Selection &selection, typename Selection::size_type p)
template<typename Selection , typename ForwardRange , typename UnaryFunction >
UnaryFunction	selection_foreach (const Selection &x, const ForwardRange &range, UnaryFunction proc)
template<typename S1 , typename S2 , typename C >
bool	selection_includes (S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, C comp, bool s1_inside=false, bool s2_inside=false)
template<typename Selection1 , typename Selection2 >
bool	selection_includes (const Selection1 &x, const Selection2 &y)
template<typename Selection1 , typename Selection2 >
Selection1	selection_intersection (const Selection1 &x, const Selection2 &y)
template<typename S1 , typename S2 , typename O , typename C >
O	selection_intersection (S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp, bool s1_inside=false, bool s2_inside=false)
template<typename S1 , typename S2 , typename O , typename P , typename C >
O	selection_operation (S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, bool s1_inside, bool s2_inside, P pred, C comp)
template<typename S , typename O , typename P >
O	selection_operation_remainder (S first, S last, O output, bool this_inside, bool other_inside, P pred)
template<typename Selection , typename ForwardRange , typename O1 , typename O2 >
std::pair< O1, O2 >	selection_partition_copy (const Selection &selection, ForwardRange &range, O1 false_output, O2 true_output)
template<typename Selection , typename ForwardRange >
boost::range_iterator < ForwardRange >::type	selection_stable_partition (const Selection &selection, ForwardRange &range)
template<typename SelectionIterator , typename RangeIterator >
RangeIterator	selection_stable_partition (SelectionIterator selection_first, SelectionIterator selection_last, RangeIterator first, RangeIterator range_first, RangeIterator range_last, std::size_t boundary_count=0)
template<typename Selection , typename ForwardRange >
std::pair< typename boost::range_iterator < ForwardRange >::type, typename boost::range_iterator < ForwardRange >::type >	selection_stable_partition_about (const Selection &selection, ForwardRange &range, std::size_t p, typename boost::range_size< Selection >::type prior_boundary_count=0)
template<typename Selection1 , typename Selection2 >
Selection1	selection_symmetric_difference (const Selection1 &x, const Selection2 &y)
template<typename S1 , typename S2 , typename O , typename C >
O	selection_symmetric_difference (S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp, bool s1_inside=false, bool s2_inside=false)
template<typename Selection , typename OutputIterator >
OutputIterator	selection_to_index_set (const Selection &selection, typename boost::range_size< Selection >::type max_index, OutputIterator output)
template<typename S1 , typename S2 , typename O , typename C >
O	selection_union (S1 s1_first, S1 s1_last, S2 s2_first, S2 s2_last, O output, C comp, bool s1_inside=false, bool s2_inside=false)
template<typename Selection1 , typename Selection2 >
Selection1	selection_union (const Selection1 &x, const Selection2 &y)
template<typename Selection >
boost::range_size< Selection > ::type	size (const Selection &x)
template<typename Selection , typename ForwardRange >
boost::range_size< Selection > ::type	size (const Selection &x, const ForwardRange &range)
template<typename Selection >
bool	start_selected (const Selection &x)

---

Detailed Description

Terminology:

• Selection: A collection of iterators in sorted order over a sequence. When considering a sequence the selection is initially "off". As the algorithm passes over a position within the list of selection points, the selection is toggled.

This set of functions behave in similar manner to the suite of operations in the STL. What makes these algorithms different from their STL counterparts is that you are supplied the initial ranges of "good" and "bad" positions in the form of the selection; thus there is no need for a predicate. It is as if the "floor" of the algorithm's processing tree were removed, as the leaf nodes are merely for discerning the state of an element by means of the predicate.

---

Function Documentation

Selection adobe::index_set_to_selection

(

const ForwardRange &

index_set )

Takes a set of indices and converts them to a boundary-based Selection

Definition at line 901 of file selection_algorithms.hpp.

void adobe::invert

(

Selection &

x )

invert implementation

Definition at line 437 of file selection_algorithms.hpp.

bool adobe::is_selected	(	const Selection &	x,
		typename Selection::value_type	index
	)

Returns:

Whether or not index is contained within Selection x.

Definition at line 516 of file selection_algorithms.hpp.

OutputIterator adobe::selection_copy	(	const Selection &	x,
		const ForwardRange &	range,
		OutputIterator	output
	)

Todo:

(fbrereto) this looks eerily familiar to selection_foreach; they can probably collapse with an "assign and advance" iterator adaptor wrapped over the output iterator.

Definition at line 532 of file selection_algorithms.hpp.

Selection1 adobe::selection_difference	(	const Selection1 &	x,
		const Selection2 &	y
	)

selection_difference implementation

Definition at line 370 of file selection_algorithms.hpp.

O adobe::selection_difference	(	S1	s1_first,
		S1	s1_last,
		S2	s2_first,
		S2	s2_last,
		O	output,
		C	comp,
		bool	s1_inside = false,
		bool	s2_inside = false
	)

selection_difference implementation

Definition at line 226 of file selection_algorithms.hpp.

std::pair<typename boost::range_const_iterator<Selection>::type, typename boost::range_size<Selection>::type> adobe::selection_find_boundary	(	const Selection &	selection,
		typename Selection::size_type	p,
		std::random_access_iterator_tag
	)

This is a RandomAccessIterator implementation of selection_find_boundary

Definition at line 667 of file selection_algorithms.hpp.

std::pair<typename boost::range_const_iterator<Selection>::type, typename boost::range_size<Selection>::type> adobe::selection_find_boundary	(	const Selection &	selection,
		typename Selection::size_type	p,
		std::forward_iterator_tag
	)

This is a ForwardIterator implementation of selection_find_boundary

Definition at line 689 of file selection_algorithms.hpp.

std::pair<typename boost::range_const_iterator<Selection>::type, typename boost::range_size<Selection>::type> adobe::selection_find_boundary	(	const Selection &	selection,
		typename Selection::size_type	p
	)

selection_find_boundary will take a selection and, given a position p, will divide the selection into two subsets: the subset of the selection before (or at) p and the subset of the selection selection after p.

This will dispatch to the appropriate split_selection implementation based on the iterator_category of the iterators.

Parameters:

selection	is a container modeling the SequenceConcept
p	the point at which the selection is to be split

Returns:

A pair of values. The first is a SelectionIterator to an index divding the selection by p. The second value is a count of the number of selection boundaries iterated over to get to the SelectionIterator.

Definition at line 733 of file selection_algorithms.hpp.

UnaryFunction adobe::selection_foreach	(	const Selection &	x,
		const ForwardRange &	range,
		UnaryFunction	proc
	)

selection_foreach implementation

Definition at line 626 of file selection_algorithms.hpp.

bool adobe::selection_includes	(	S1	s1_first,
		S1	s1_last,
		S2	s2_first,
		S2	s2_last,
		C	comp,
		bool	s1_inside = false,
		bool	s2_inside = false
	)

selection_includes implementation

Definition at line 280 of file selection_algorithms.hpp.

bool adobe::selection_includes	(	const Selection1 &	x,
		const Selection2 &	y
	)

selection_includes implementation

Definition at line 418 of file selection_algorithms.hpp.

Selection1 adobe::selection_intersection	(	const Selection1 &	x,
		const Selection2 &	y
	)

selection_intersection implementation

Definition at line 322 of file selection_algorithms.hpp.

O adobe::selection_intersection	(	S1	s1_first,
		S1	s1_last,
		S2	s2_first,
		S2	s2_last,
		O	output,
		C	comp,
		bool	s1_inside = false,
		bool	s2_inside = false
	)

selection_intersection implementation

Definition at line 198 of file selection_algorithms.hpp.

O adobe::selection_operation	(	S1	s1_first,
		S1	s1_last,
		S2	s2_first,
		S2	s2_last,
		O	output,
		bool	s1_inside,
		bool	s2_inside,
		P	pred,
		C	comp
	)

selection_operation implementation

Definition at line 109 of file selection_algorithms.hpp.

O adobe::selection_operation_remainder	(	S	first,
		S	last,
		O	output,
		bool	this_inside,
		bool	other_inside,
		P	pred
	)

When one selection is exhausted this algorithm will complete the selection operation for the remainder of the other selection.

Definition at line 57 of file selection_algorithms.hpp.

std::pair<O1, O2> adobe::selection_partition_copy	(	const Selection &	selection,
		ForwardRange &	range,
		O1	false_output,
		O2	true_output
	)

selection_partition_copy implementation

Definition at line 576 of file selection_algorithms.hpp.

boost::range_iterator<ForwardRange>::type adobe::selection_stable_partition	(	const Selection &	selection,
		ForwardRange &	range
	)

A SelectionConcept-based version of selection_stable_partition.

Definition at line 817 of file selection_algorithms.hpp.

RangeIterator adobe::selection_stable_partition	(	SelectionIterator	selection_first,
		SelectionIterator	selection_last,
		RangeIterator	first,
		RangeIterator	range_first,
		RangeIterator	range_last,
		std::size_t	boundary_count = 0
	)

stable_partition_selection takes a collection of elements defined by a selection and partitons them according to whether or not they are part of the selection. The algorithm is stable. The result is an iterator that is the boundary between the two partitions. For example:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
           |---R1----|              |------R2------|              |------R3------|
    

becomes:

    1 2 3 4 10 11 12 13 14 20 21 22 23 24 30 5 6 7 8 9 15 16 17 18 19 25 26 27 28 29
                                            |---------------------------------------|
                                            p
    

Storage Requirements:

The algorithm is in-situ.

Time Complexity:

O(N log N), where N is the number of elements affected by the algorithm. This is a range from the first item affected (be that the first item in the selection, or p if p comes before it) to the last item affected (be that one before the last item in the selection, or p if p comes after it).

Definition at line 780 of file selection_algorithms.hpp.

std::pair<typename boost::range_iterator<ForwardRange>::type, typename boost::range_iterator<ForwardRange>::type> adobe::selection_stable_partition_about	(	const Selection &	selection,
		ForwardRange &	range,
		std::size_t	p,
		typename boost::range_size< Selection >::type	prior_boundary_count = 0
	)

stable_partition_selection_about takes a collection of elements defined by a selection and moves them to a position (p) within the sequence. The algorithm is stable. The result is a pair of iterators [ p_first, p_last ) that contain the selection moved to p. For example:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
           |---R1----|              |------R2------|        p     |------R3------|
    

becomes:

    1 2 3 4 10 11 12 13 14 20 21 22 5 6 7 8 9 15 16 17 18 19 25 26 27 28 29 23 24 30
                                   |---------------------------------------|
                                   p_first                                 p_last
    

The problem is broken down into two basic subproblems, namely, moving those ranges that are before p forward to p, and moving those ranges after p backward to p. These two problems are each an issue of modified stable partitioning.

Storage Requirements:

The algorithm is in-situ.

Time Complexity:

O(N log N), where N is the number of elements affected by the algorithm. This is a range from the first item affected (be that the first item in the selection, or p if p comes before it) to the last item affected (be that one before the last item in the selection, or p if p comes after it).

Definition at line 866 of file selection_algorithms.hpp.

Selection1 adobe::selection_symmetric_difference	(	const Selection1 &	x,
		const Selection2 &	y
	)

selection_symmetric_difference implementation

Definition at line 394 of file selection_algorithms.hpp.

O adobe::selection_symmetric_difference	(	S1	s1_first,
		S1	s1_last,
		S2	s2_first,
		S2	s2_last,
		O	output,
		C	comp,
		bool	s1_inside = false,
		bool	s2_inside = false
	)

selection_symmetric_difference implementation

Definition at line 253 of file selection_algorithms.hpp.

OutputIterator adobe::selection_to_index_set	(	const Selection &	selection,
		typename boost::range_size< Selection >::type	max_index,
		OutputIterator	output
	)

Takes a set of indices and converts them to a boundary-based Selection

Definition at line 934 of file selection_algorithms.hpp.

O adobe::selection_union	(	S1	s1_first,
		S1	s1_last,
		S2	s2_first,
		S2	s2_last,
		O	output,
		C	comp,
		bool	s1_inside = false,
		bool	s2_inside = false
	)

selection_union implementation

Definition at line 170 of file selection_algorithms.hpp.

Selection1 adobe::selection_union	(	const Selection1 &	x,
		const Selection2 &	y
	)

selection_union implementation

Definition at line 346 of file selection_algorithms.hpp.

boost::range_size<Selection>::type adobe::size

(

const Selection &

x )

Returns:

the number of selection boundaries present in x.

Definition at line 457 of file selection_algorithms.hpp.

boost::range_size<Selection>::type adobe::size	(	const Selection &	x,
		const ForwardRange &	range
	)

Returns:

Given a container, returns the number of elements selected by the selection x.

Definition at line 467 of file selection_algorithms.hpp.

bool adobe::start_selected

(

const Selection &

x )

start_selected implementation

Definition at line 447 of file selection_algorithms.hpp.