lti::quickPartialSort< T > Class Template Reference
[Basic Statistics]

Quick partial sort. More...

#include <ltiQuickPartialSort.h>

Inheritance diagram for lti::quickPartialSort< T >:

[legend]

Collaboration diagram for lti::quickPartialSort< T >:

[legend]

List of all members.

Classes
class	parameters
	The parameters for the class quickPartialSort. More...
Public Member Functions
	quickPartialSort ()
	quickPartialSort (const quickPartialSort< T > &other)
virtual	~quickPartialSort ()
virtual const char *	getTypeName () const
bool	apply (matrix< T > &srcdest) const
bool	apply (const matrix< T > &src, matrix< T > &dest) const
bool	apply (vector< T > &srcdest) const
bool	apply (const vector< T > &src, vector< T > &dest) const
bool	apply (std::vector< T > &srcdest) const
bool	apply (const std::vector< T > &src, std::vector< T > &dest) const
bool	apply (const int pivotIndex, matrix< T > &srcdest) const
bool	apply (const int pivotIndex, const matrix< T > &src, matrix< T > &dest) const
bool	apply (const int pivotIndex, vector< T > &srcdest) const
bool	apply (const int pivotIndex, const vector< T > &src, vector< T > &dest) const
bool	apply (const int pivotIndex, std::vector< T > &srcdest) const
bool	apply (const int pivotIndex, const std::vector< T > &src, std::vector< T > &dest) const
quickPartialSort &	copy (const quickPartialSort &other)
virtual functor *	clone () const
const parameters &	getParameters () const
Protected Member Functions
T	findMedian (vector< T > &vct, const int &begin, const int &end, const int &medianPos) const
int	partition (vector< T > &vct, const int &begin, const int &end) const
T	findMedian (std::vector< T > &vct, const int &begin, const int &end, const int &medianPos) const
int	partition (std::vector< T > &vct, const int &begin, const int &end) const

---

Detailed Description

template<class T>
class lti::quickPartialSort< T >

Quick partial sort.

This class is used to extract the n smallest elements of a vector, without requiring to complete the sort. Since the apply method expects the index of the element you want for sure at its destination if the vector were completelly sorted, to get the first n elements you need to give the apply method "n-1".

It is usually employed when you just required, for example, the three smallest elements of a vector. In this case you would apply(2,vct), since "2" is the index of the third element of the vector.

A major difference to the STL method std::partial_sort is that this functor don't even sorts the elements at the begining, it just ensures that they are smaller or equal the element at the given position, and that the elements after the final one at the pivot position are greater or equal the pivot element. In this sense, this corresponds to the std::partition algorithm, but here we use the LTI-Lib functor-based interface.

The type of the vector elements T must accept the operator< and operator=.

Note that this functor always sorts in increasing order. If you need the n greatest elements, then just give as pivot-index vct.size()-n, and the last elements are the ones you are looking for.

See also:

lti::sort,lti::quickMedian,lti::quickPartialSort2

You may also be interested in the std::nth_element and std::partial_sort functions of the <algorithms> file, which can be better if you are dealing with STL structures or if you really want to sort the beginning of your vector. Since these standard functions are templates, you can also use them with lti::vectors.

---

Constructor & Destructor Documentation

template<class T>

lti::quickPartialSort< T >::quickPartialSort

(

)

default constructor

template<class T>

lti::quickPartialSort< T >::quickPartialSort

(

const quickPartialSort< T > &

other

)

copy constructor

Parameters:

other

the object to be copied

template<class T>

virtual lti::quickPartialSort< T >::~quickPartialSort

(

)

[virtual]

destructor

---

Member Function Documentation

template<class T>

bool lti::quickPartialSort< T >::apply	(	const int	pivotIndex,
		const std::vector< T > &	src,
		std::vector< T > &	dest
	)			const

Partially sorts the vector on-copy.

Parameters:

	pivotIndex	pivot position on the given vector. The result has the first "pivotIndex" elements smaller or equal the rest of the vector elements.
	src	vector<T> with the source data.
	dest	the partially sorted vector.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply	(	const int	pivotIndex,
		std::vector< T > &	srcdest
	)			const

Partially sorts the vector on-place.

Parameters:

	pivotIndex	pivot position on the given vector. The result has the first "pivotIndex" elements smaller or equal the rest of the vector elements.
	srcdest	vector<T> with the source data. The result will be left here too.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply	(	const int	pivotIndex,
		const vector< T > &	src,
		vector< T > &	dest
	)			const

Partially sorts the input vector and leaves the result in the destination vector.

Parameters:

	pivotIndex	pivot position on the given vector. The result has the first "pivotIndex" elements smaller or equal the rest of the vector elements.
	src	vector<T> with the source data.
	dest	the partially sorted vector. The first pivotIndex elements are less or equal than the rest of the elements of the vector.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply	(	const int	pivotIndex,
		vector< T > &	srcdest
	)			const

Operates on the given parameter.

The resulting vector has its first pivotIndex elements of smaller or equall than the rest of the elements.

Parameters:

	pivotIndex	pivot position on the given vector. The result has the first "pivotIndex" elements smaller or equal the rest of the vector elements.
	srcdest	vector<T> with the source data. The result will be left here too.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply	(	const int	pivotIndex,
		const matrix< T > &	src,
		matrix< T > &	dest
	)			const

Partially sorts given matrix, which is NOT modified.

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

Parameters:

	pivotIndex	pivot position on the given vector. The result has the first "pivotIndex" elements smaller or equal the rest of the vector elements.
	src	matrix<T> with the source data.
	dest	the median value of the given matrix.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply	(	const int	pivotIndex,
		matrix< T > &	srcdest
	)			const

The given matrix is used as source and destination.

The matrix will be considered as a vector, where the rows of the matrix are simply concatenated. The first parameters::pivotIndex elements of the resulting matrix will be smaller or equall than the rest of the elements.

Parameters:

	pivotIndex	pivot position on the given vector. The result has the first "pivotIndex" elements smaller or equal the rest of the vector elements.
	srcdest	matrix<T> with the source data. The result will be left here too.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply	(	const std::vector< T > &	src,
		std::vector< T > &	dest
	)			const

operates on the given parameter.

Parameters:

	src	vector<T> with the source data.
	dest	the partially sorted vector.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply

(

std::vector< T > &

srcdest

)

const

Partially sorts the vector on-place.

Parameters:

srcdest

vector<T> with the source data. The result will be left here too.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply	(	const vector< T > &	src,
		vector< T > &	dest
	)			const

Partially sorts the input vector and leaves the result in the destination vector.

Parameters:

	src	vector<T> with the source data.
	dest	the partially sorted vector. The first pivotIndex elements are less or equal than the rest of the elements of the vector.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply

(

vector< T > &

srcdest

)

const

Operates on the given parameter.

The resulting vector has its first parameters::pivotIndex elements of smaller or equall than the rest of the elements.

Parameters:

srcdest

vector<T> with the source data. The result will be left here too.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply	(	const matrix< T > &	src,
		matrix< T > &	dest
	)			const

Partially sorts given matrix, which is NOT modified.

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

Parameters:

	src	matrix<T> with the source data.
	dest	the median value of the given matrix.

Returns:

true if successful, false otherwise.

template<class T>

bool lti::quickPartialSort< T >::apply

(

matrix< T > &

srcdest

)

const

The given matrix is used as source and destination.

The matrix will be considered as a vector, where the rows of the matrix are simply concatenated. The first parameters::pivotIndex elements of the resulting matrix will be smaller or equall than the rest of the elements.

Parameters:

srcdest

matrix<T> with the source data. The result will be left here too.

Returns:

true if successful, false otherwise.

template<class T>

virtual functor* lti::quickPartialSort< T >::clone

(

)

const [virtual]

returns a pointer to a clone of this functor.

Implements lti::functor.

Reimplemented in lti::quickPartialSort2< T, U >.

template<class T>

quickPartialSort& lti::quickPartialSort< T >::copy

(

const quickPartialSort< T > &

other

)

copy data of "other" functor.

Parameters:

other

the functor to be copied

Returns:

a reference to this functor object

Reimplemented from lti::functor.

template<class T>

T lti::quickPartialSort< T >::findMedian	(	std::vector< T > &	vct,
		const int &	begin,
		const int &	end,
		const int &	medianPos
	)			const [protected]

this method calculates the median in a recursively form

template<class T>

T lti::quickPartialSort< T >::findMedian	(	vector< T > &	vct,
		const int &	begin,
		const int &	end,
		const int &	medianPos
	)			const [protected]

this method calculates the median in a recursively form

template<class T>

const parameters& lti::quickPartialSort< T >::getParameters

(

)

const

returns used parameters

Reimplemented from lti::functor.

template<class T>

virtual const char* lti::quickPartialSort< T >::getTypeName

(

)

const [virtual]

returns the name of this type ("quickPartialSort")

Reimplemented from lti::functor.

Reimplemented in lti::quickPartialSort2< T, U >.

template<class T>

int lti::quickPartialSort< T >::partition	(	std::vector< T > &	vct,
		const int &	begin,
		const int &	end
	)			const [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.

template<class T>

int lti::quickPartialSort< T >::partition	(	vector< T > &	vct,
		const int &	begin,
		const int &	end
	)			const [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 documentation for this class was generated from the following file:

• ltiQuickPartialSort.h