selection

Classes
struct	logical_xor< C1, C2 >
	xor funtion object More...

Functions
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 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)
	selection_operation implementation
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)
	selection_union implementation
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)
	selection_intersection implementation
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)
	selection_difference implementation
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)
	selection_symmetric_difference implementation
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)
	selection_includes implementation
template<typename Selection1, typename Selection2>
Selection1	selection_intersection (const Selection1 &x, const Selection2 &y)
	selection_intersection implementation
template<typename Selection1, typename Selection2>
Selection1	selection_union (const Selection1 &x, const Selection2 &y)
	selection_union implementation
template<typename Selection1, typename Selection2>
Selection1	selection_difference (const Selection1 &x, const Selection2 &y)
	selection_difference implementation
template<typename Selection1, typename Selection2>
Selection1	selection_symmetric_difference (const Selection1 &x, const Selection2 &y)
	selection_symmetric_difference implementation
template<typename Selection1, typename Selection2>
bool	selection_includes (const Selection1 &x, const Selection2 &y)
	selection_includes implementation
template<typename Selection>
void	invert (Selection &x)
	invert implementation
template<typename Selection>
bool	start_selected (const Selection &x)
	start_selected implementation
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	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 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)
	selection_partition_copy implementation
template<typename Selection, typename ForwardRange, typename UnaryFunction>
UnaryFunction	selection_foreach (const Selection &x, const ForwardRange &range, UnaryFunction proc)
	selection_foreach implementation
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 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>
boost::range_iterator< ForwardRange >::type	selection_stable_partition (const Selection &selection, ForwardRange &range)
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 I, typename N>
std::pair< I, N >	find_sequence_end (I f, I l, N n)
template<typename I, typename O>
void	index_set_to_selection (I f, I l, O output)
template<typename Selection, typename ForwardRange>
Selection	index_set_to_selection (const ForwardRange &index_set)
template<typename Selection, typename OutputIterator>
OutputIterator	selection_to_index_set (const Selection &selection, typename boost::range_size< Selection >::type max_index, OutputIterator output)

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_operation_remainder()

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 )

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

Definition at line 58 of file selection_algorithms.hpp.

selection_operation()

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 )

Definition at line 105 of file selection_algorithms.hpp.

selection_union() [1/2]

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 )

Definition at line 159 of file selection_algorithms.hpp.

selection_intersection() [1/2]

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 )

Definition at line 176 of file selection_algorithms.hpp.

selection_difference() [1/2]

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 )

Definition at line 193 of file selection_algorithms.hpp.

selection_symmetric_difference() [1/2]

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 )

Definition at line 210 of file selection_algorithms.hpp.

selection_includes() [1/2]

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 )

Definition at line 226 of file selection_algorithms.hpp.

selection_intersection() [2/2]

template<typename Selection1, typename Selection2>

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

Definition at line 254 of file selection_algorithms.hpp.

selection_union() [2/2]

template<typename Selection1, typename Selection2>

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

Definition at line 275 of file selection_algorithms.hpp.

selection_difference() [2/2]

template<typename Selection1, typename Selection2>

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

Definition at line 295 of file selection_algorithms.hpp.

selection_symmetric_difference() [2/2]

template<typename Selection1, typename Selection2>

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

Definition at line 315 of file selection_algorithms.hpp.

selection_includes() [2/2]

template<typename Selection1, typename Selection2>

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

Definition at line 336 of file selection_algorithms.hpp.

invert()

template<typename Selection>

void invert

(

Selection &

x

)

Definition at line 352 of file selection_algorithms.hpp.

start_selected()

template<typename Selection>

bool start_selected

(

const Selection &

x

)

Definition at line 363 of file selection_algorithms.hpp.

size() [1/2]

template<typename Selection>

boost::range_size< Selection >::type size

(

const Selection &

x

)

Returns

the number of selection boundaries present in x.

Definition at line 374 of file selection_algorithms.hpp.

size() [2/2]

template<typename Selection, typename ForwardRange>

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

Returns

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

Definition at line 385 of file selection_algorithms.hpp.

is_selected()

template<typename Selection>

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

Returns

Whether or not index is contained within Selection x.

Definition at line 432 of file selection_algorithms.hpp.

selection_copy()

template<typename Selection, typename ForwardRange, typename OutputIterator>

OutputIterator 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 448 of file selection_algorithms.hpp.

selection_partition_copy()

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 )

Definition at line 489 of file selection_algorithms.hpp.

selection_foreach()

template<typename Selection, typename ForwardRange, typename UnaryFunction>

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

Definition at line 537 of file selection_algorithms.hpp.

selection_find_boundary() [1/3]

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	)

This is a RandomAccessIterator implementation of selection_find_boundary

Definition at line 574 of file selection_algorithms.hpp.

selection_find_boundary() [2/3]

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	)

This is a ForwardIterator implementation of selection_find_boundary

Definition at line 595 of file selection_algorithms.hpp.

selection_find_boundary() [3/3]

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 )

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 635 of file selection_algorithms.hpp.

selection_stable_partition() [1/2]

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 )

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 680 of file selection_algorithms.hpp.

selection_stable_partition() [2/2]

template<typename Selection, typename ForwardRange>

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

A SelectionConcept-based version of selection_stable_partition.

Definition at line 711 of file selection_algorithms.hpp.

selection_stable_partition_about()

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 )

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 756 of file selection_algorithms.hpp.

find_sequence_end()

template<typename I, typename N>

std::pair< I, N > find_sequence_end	(	I	f,
		I	l,
		N	n )

Finds end of the non-interrupted sequence in a strictly increasing set of indices, starting with number n

Precondition

[f, l) is a sorted (strictly increasing) set of indices

Returns

A pair of values. The first is a iterator for the next element of a non-interupted sequence The second is the last number of a non-interrupted sequence .

E.g. in an array of [0, 1, 2, 3, 7, 9, 10, 12] : when called with value of ((iter 1), (iter 12), 1) : returns {(iter 7), 3}; : when called with value of ((iter 9), (iter 12), 8) : returns {(iter 9), 8};

Definition at line 798 of file selection_algorithms.hpp.

index_set_to_selection() [1/2]

template<typename I, typename O>

void index_set_to_selection	(	I	f,
		I	l,
		O	output )

Takes an subset of strictly increasing set of indices and converts them to a boundary-based Selection via its output iterator

Precondition

[f, l) is a sorted (strictly increasing) set of indices

Definition at line 820 of file selection_algorithms.hpp.

index_set_to_selection() [2/2]

template<typename Selection, typename ForwardRange>

Selection index_set_to_selection

(

const ForwardRange &

index_set

)

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

Precondition

index_set is a sorted (strictly increasing) set of indices

If you have an arbitrary set of selected indices (unsorted, and/or possible duplicate entries), sort and remove duplicates first, following PSEUDOCODE here:

auto sorted_selected_set = DEEP_COPY(index_set);

(DEEP COPY depends on the nature of index_set ForwardRange type:

• If you are using std::vector<>, a simple assignment would suffice
• However, generally ForwardRange doesn't necessarily own elements, so extra effort may be needed to ensure proper duplication that results in a sortable container.)

std::sort(sorted_selected_set.begin(), sorted_selected_set.end());

auto last = std::unique(sorted_selected_set.begin(), sorted_selected_set.end());

sorted_selected_set.erase(last, sorted_selected_set.end());

Selection result = index_set_to_selection<Selection>(sorted_selected_set);

return result;

Returns

A Selection.

Definition at line 865 of file selection_algorithms.hpp.

selection_to_index_set()

template<typename Selection, typename OutputIterator>

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

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

Example usage:

(std::size_t total_size is the known total number of elements in our set, since that information is not known to by a Selection object)

std::vector<std::size_t> indexSet; selection_to_index_set(selection, total_size, std::back_inserter(indexSet));

Definition at line 890 of file selection_algorithms.hpp.