General indirect sort functions. More...

#include <GenSort.h>

Static Public Member Functions
static uInt	sort (Vector< uInt > &indexVector, const T *data, uInt nr, Sort::Order=Sort::Ascending, int options=Sort::QuickSort)
	Sort a C-array containing `nr` `T`-type objects. More...

static uInt	sort (Vector< uInt > &indexVector, const Array< T > &data, Sort::Order=Sort::Ascending, int options=Sort::QuickSort)
	Sort a C-array containing `nr` `T`-type objects. More...

static uInt	sort (Vector< uInt > &indexVector, const Block< T > &data, uInt nr, Sort::Order=Sort::Ascending, int options=Sort::QuickSort)
	Sort a C-array containing `nr` `T`-type objects. More...

static uInt	kthLargest (T *data, uInt nr, uInt k)
	Find the index of the k-th largest value. More...

static uInt	quickSort (uInt inx, const T data, uInt nr, Sort::Order, int options)
	Sort container using quicksort. More...

static uInt	heapSort (uInt inx, const T data, uInt nr, Sort::Order, int options)
	Sort container using heapsort. More...

static uInt	insSort (uInt inx, const T data, uInt nr, Sort::Order, int options)
	Sort container using insertion sort. More...

static uInt	parSort (uInt inx, const T data, uInt nr, Sort::Order, int options, int nthreads=0)
	Sort container using parallel merge sort (using OpenMP). More...

Static Private Member Functions
static void	swapInx (uInt &index1, uInt &index2)
	Swap 2 indices. More...

static uInt *	merge (const T data, uInt inx, uInt tmp, uInt nrrec, uInt index, uInt nparts)
	The`data` buffer is divided in `nparts` parts. More...

static int	isAscending (const T *data, Int index1, Int index2)
	Check if 2 values are in ascending order. More...

static void	quickSortAsc (uInt inx, const T , Int nr, Bool multiThread=False, Int rec_lim=128)
	Quicksort in ascending order. More...

static void	heapSortAsc (uInt inx, const T , Int nr)
	Heapsort in ascending order. More...

static void	heapAscSiftDown (uInt inx, Int, Int, const T )
	Helper function for ascending heapsort. More...

static uInt	insSortAsc (uInt inx, const T , Int nr, int option)
	Insertion sort in ascending order. More...

static uInt	insSortAscDup (uInt inx, const T , Int nr)
	Insertion sort in ascending order allowing duplicates. More...

static uInt	insSortAscNoDup (uInt inx, const T , Int nr)
	Insertion sort in ascending order allowing no duplicates. More...

Detailed Description

template<class T>
class casacore::GenSortIndirect< T >

General indirect sort functions.

Intended use:

Internal

Synopsis

This class is similar to GenSort. The only difference is that the functions in this class sort indirectly instead of in-place. They return the result of the sort as an sorted vector of indices This is slower, because an extra indirection is involved in each comparison. However, this sort allows to sort const data. Another advantage is that this sort is always stable (i.e. equal values are kept in their original order).

Definition at line 206 of file GenSort.h.

Member Function Documentation

template<class T >

static void casacore::GenSortIndirect< T >::heapAscSiftDown	(	uInt *	inx,
		Int	,
		Int	,
		const T *
	)

staticprivate

Helper function for ascending heapsort.

template<class T >

static uInt casacore::GenSortIndirect< T >::heapSort	(	uInt *	inx,
		const T *	data,
		uInt	nr,
		Sort::Order	,
		int	options
	)

static

Sort container using heapsort.

template<class T >

static void casacore::GenSortIndirect< T >::heapSortAsc	(	uInt *	inx,
		const T *	,
		Int	nr
	)

staticprivate

Heapsort in ascending order.

template<class T >

static uInt casacore::GenSortIndirect< T >::insSort	(	uInt *	inx,
		const T *	data,
		uInt	nr,
		Sort::Order	,
		int	options
	)

static

Sort container using insertion sort.

template<class T >

static uInt casacore::GenSortIndirect< T >::insSortAsc	(	uInt *	inx,
		const T *	,
		Int	nr,
		int	option
	)

staticprivate

Insertion sort in ascending order.

template<class T >

static uInt casacore::GenSortIndirect< T >::insSortAscDup	(	uInt *	inx,
		const T *	,
		Int	nr
	)

staticprivate

Insertion sort in ascending order allowing duplicates.

This is also used by quicksort for its last steps.

template<class T >

static uInt casacore::GenSortIndirect< T >::insSortAscNoDup	(	uInt *	inx,
		const T *	,
		Int	nr
	)

staticprivate

Insertion sort in ascending order allowing no duplicates.

This is also used by the other sort algorithms to skip duplicates.

template<class T >

int casacore::GenSortIndirect< T >::isAscending	(	const T *	data,
		Int	index1,
		Int	index2
	)

inlinestaticprivate

Check if 2 values are in ascending order.

When equal, the order is correct if index1<index2.

Definition at line 401 of file GenSort.h.

template<class T >

static uInt casacore::GenSortIndirect< T >::kthLargest	(	T *	data,
		uInt	nr,
		uInt	k
	)

static

Find the index of the k-th largest value.

template<class T >

static uInt* casacore::GenSortIndirect< T >::merge	(	const T *	data,
		uInt *	inx,
		uInt *	tmp,
		uInt	nrrec,
		uInt *	index,
		uInt	nparts
	)

staticprivate

Thedata buffer is divided in nparts parts.

In each part the values are in ascending order. The index tells the nr of elements in each part. Recursively each two subsequent parts are merged until only part is left (giving the sorted array). Alternately data and tmp are used for the merge result. The pointer containing the final result is returned.
If possible, merging the parts is done in parallel (using OpenMP).

template<class T >

static uInt casacore::GenSortIndirect< T >::parSort	(	uInt *	inx,
		const T *	data,
		uInt	nr,
		Sort::Order	,
		int	options,
		int	nthreads = `0`
	)

static

Sort container using parallel merge sort (using OpenMP).

By default the maximum number of threads is used.

template<class T >

static uInt casacore::GenSortIndirect< T >::quickSort	(	uInt *	inx,
		const T *	data,
		uInt	nr,
		Sort::Order	,
		int	options
	)

static

Sort container using quicksort.

The argument inx gives the index defining the order of the values in the data array. Its length must be at least nr and it must be filled with the index values of the data. Usually this is 0..nr, but it could contain a selection of the data.

template<class T >

static void casacore::GenSortIndirect< T >::quickSortAsc	(	uInt *	inx,
		const T *	,
		Int	nr,
		Bool	multiThread = `False`,
		Int	rec_lim = `128`
	)

staticprivate

Quicksort in ascending order.

template<class T >

static uInt casacore::GenSortIndirect< T >::sort	(	Vector< uInt > &	indexVector,
		const T *	data,
		uInt	nr,
		Sort::Order	= `Sort::Ascending`,
		int	options = `Sort::QuickSort`
	)

static

Sort a C-array containing nr T-type objects.

The resulting index vector gives the sorted indices.

Referenced by casacore::genSort().

template<class T >

static uInt casacore::GenSortIndirect< T >::sort	(	Vector< uInt > &	indexVector,
		const Array< T > &	data,
		Sort::Order	= `Sort::Ascending`,
		int	options = `Sort::QuickSort`
	)

static

Sort a C-array containing nr T-type objects.

The resulting index vector gives the sorted indices.

template<class T >

static uInt casacore::GenSortIndirect< T >::sort	(	Vector< uInt > &	indexVector,
		const Block< T > &	data,
		uInt	nr,
		Sort::Order	= `Sort::Ascending`,
		int	options = `Sort::QuickSort`
	)

static

Sort a C-array containing nr T-type objects.

The resulting index vector gives the sorted indices.

template<class T >

void casacore::GenSortIndirect< T >::swapInx	(	uInt &	index1,
		uInt &	index2
	)

inlinestaticprivate

Swap 2 indices.

Definition at line 394 of file GenSort.h.

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

casa/casacore/casa/Utilities/GenSort.h

Static Public Member Functions

Static Private Member Functions

Detailed Description

template<class T> class casacore::GenSortIndirect< T >

Intended use:

Synopsis

Member Function Documentation

template<class T>
class casacore::GenSortIndirect< T >