cvr::quickPartialSort Class Reference
[Sorting and scrambling algorithms]

Quick partial sort. More...

#include <cvrQuickPartialSort.h>

Inheritance diagram for cvr::quickPartialSort:

[legend]

Collaboration diagram for cvr::quickPartialSort:

[legend]

List of all members.

Public Member Functions
	quickPartialSort ()
	quickPartialSort (const quickPartialSort &other)
virtual	~quickPartialSort ()
const std::string &	name () const
template<typename T >
bool	apply (const int row, const int col, matrix< T > &src, T &data) const
template<typename T >
bool	apply (const int row, const int col, const matrix< T > &src, T &data) const
template<typename T >
bool	apply (const int row, const int col, const matrix< T > &src, matrix< T > &dest, T &data) const
template<class V >
bool	apply (const int pos, V &srcdest, typename V::value_type &data) const
template<class V >
bool	apply (const int pos, const V &src, typename V::value_type &data) const
template<class V >
bool	apply (const int pos, const V &src, V &dest, typename V::value_type &data) const
template<class V >
V::value_type	nth (const int pos, const V &src) const
quickPartialSort &	copy (const quickPartialSort &other)
virtual quickPartialSort *	clone () const
virtual quickPartialSort *	newInstance () const
Protected Member Functions
template<class V >
V::value_type	findNth (V &vct, const int begin, const int end, const int dataPos) const
template<class V >
int	partition (V &vct, const int begin, const int end) const

---

Detailed Description

Quick partial sort.

This class is used to find the n-th element of an ascending sorted vector or matrix, while avoiding to sort the complete container (that is the reason for the "partial" part in the class name). The algorithm used is based on the quick sort.

On-place applies are in this implementation faster than on copy ones.

Note that this class does not has a nested parameters class, since they are not necessary.

---

Constructor & Destructor Documentation

cvr::quickPartialSort::quickPartialSort

(

)

Default constructor.

cvr::quickPartialSort::quickPartialSort

(

const quickPartialSort &

other

)

copy constructor

Parameters:

other

the object to be copied

virtual cvr::quickPartialSort::~quickPartialSort

(

)

[virtual]

destructor

---

Member Function Documentation

template<class V >

bool cvr::quickPartialSort::apply	(	const int	pos,
		const V &	src,
		V &	dest,
		typename V::value_type &	data
	)			const [inline]

Operates on the given parameter.

Parameters:

	pos	the position of the element that wants to be found.
	src	vector with the source data.
	dest	the partially sorted vector. The elements at the first half of the vector are less or equal than the data and on the other half greater or equal.
	data	the data value

Returns:

true on success false otherwise

template<class V >

bool cvr::quickPartialSort::apply	(	const int	pos,
		const V &	src,
		typename V::value_type &	data
	)			const [inline]

Operates on the given parameter.

Parameters:

	pos	the position of the element that wants to be found.
	src	vector with the source data.
	data	the data value

Returns:

true on success false otherwise

template<class V >

bool cvr::quickPartialSort::apply	(	const int	pos,
		V &	srcdest,
		typename V::value_type &	data
	)			const [inline]

Find the n-th element of a sorted vector of type V, which can be an cvr::genericVector or any of its derived classes, or a std::vector.

In principle the container type V just needs to support:

• the type definitions V::size_type and V::value_type,
• the operator[] returning elements of type V::value_type
• the V::value_type has to be comparable with the operator<.
• the method empty()
• the method size() returning a V::size_type

The resulting vector contains the elements less or equal than the data for the indexes x such that x < size()/2, and higher or equal otherwise.

Parameters:

	pos	the position of the element that wants to be found.
	srcdest	vector with the source data. The resultwill be left here too.
	data	the data value

Returns:

true on success false otherwise

template<typename T >

bool cvr::quickPartialSort::apply	(	const int	row,
		const int	col,
		const matrix< T > &	src,
		matrix< T > &	dest,
		T &	data
	)			const [inline]

Calculates the data of src, the result is left in dest.

The elements of the matrix will be considered as part of a vector with "columns()" times "rows()" elements.

This method needs to transfer the contents of the src data into the dest matrix, and therefore is not as fast as the one with interface apply(const int,const int,matrix<T>&,T&).

Parameters:

	row	row index for the element that has to be found.
	col	column index for the element that has to be found.
	src	matrix<T> with the source data.
	dest	partially sorted matrix.
	data	the data value of the given matrix.

Returns:

true on success false otherwise

template<typename T >

bool cvr::quickPartialSort::apply	(	const int	row,
		const int	col,
		const matrix< T > &	src,
		T &	data
	)			const [inline]

Calculates the data of the given matrix, which is NOT modified.

The elements of the matrix will be considered as part of a vector with "columns()" times "rows()" elements.

This method needs to save the contents of the src data, and therefore is not as fast as the one with interface apply(const int,const int,matrix<T>&,T&).

Parameters:

	row	row index for the element that has to be found.
	col	column index for the element that has to be found.
	src	matrix<T> with the source data.
	data	the data value of the given matrix.

Returns:

true on success false otherwise

template<typename T >

bool cvr::quickPartialSort::apply	(	const int	row,
		const int	col,
		matrix< T > &	src,
		T &	data
	)			const [inline]

Calculates which element of the sorted matrix would be at(row,col) if the whole matrix would be sorted.

The given matrix will be modified so that all elements "before" the given coordinates are less than or equal the element at(row,col), and the elements "after" will be greater.

The terms "before" and "after" are stated in the context of concatenation of all rows of the matrix into a large vector.

Parameters:

	row	row index for the element that has to be found.
	col	column index for the element that has to be found.
	src	matrix<T> with the source data.
	data	the data value of the given matrix.

Returns:

true on success false otherwise

virtual quickPartialSort* cvr::quickPartialSort::clone

(

)

const [virtual]

Returns a pointer to a clone of this functor.

Implements cvr::functor.

quickPartialSort& cvr::quickPartialSort::copy

(

const quickPartialSort &

other

)

Copy data of "other" functor.

Parameters:

other

the functor to be copied

Returns:

a reference to this functor object

template<class V >

V::value_type cvr::quickPartialSort::findNth	(	V &	vct,
		const int	begin,
		const int	end,
		const int	dataPos
	)			const [inline, protected]

This method calculates the data in a recursively form.

The template type V has to be a vector following an interface like the cvr::vector or the std::vector, implementing the operator[]

const std::string& cvr::quickPartialSort::name

(

)

const [virtual]

Returns the name of this class.

Implements cvr::functor.

virtual quickPartialSort* cvr::quickPartialSort::newInstance

(

)

const [virtual]

Returns a pointer to a new instance of this functor.

Implements cvr::functor.

template<class V >

V::value_type cvr::quickPartialSort::nth	(	const int	pos,
		const V &	src
	)			const [inline]

A shortcut function for apply(const vector<T>&, T&) const.

Note that internally another vector and T are used.

Parameters:

	pos	the position of the element that wants to be found.
	src	vector whose data is sought

Returns:

the data of src

template<class V >

int cvr::quickPartialSort::partition	(	V &	vct,
		const int	begin,
		const int	end
	)			const [inline, protected]

This method chooses a pivot-value and ensures that lower values lie at the left and higher values at the right of its final position, which will be returned.

The template type V has to be a vector following an interface like the cvr::vector or the std::vector, implementing the operator[]

---

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

• cvrQuickPartialSort.h