Loading...
Searching...
No Matches
casacore::GenSortIndirect< T, INX > Class Template Reference
casa package (libcasa_casa) » Utilities_module » Utilities_module_internal_classes

General indirect sort functions. More...

`#include <GenSort.h>`

## Static Public Member Functions

static INX | sort (Vector< INX > &indexVector, const T *data, INX nr, Sort::Order=Sort::Ascending, int options=Sort::QuickSort)
| Sort a C-array containing nr T-type objects.
static INX | sort (Vector< INX > &indexVector, const Array< T > &data, Sort::Order=Sort::Ascending, int options=Sort::QuickSort)
| Sort a C-array containing nr T-type objects.
static INX | sort (Vector< INX > &indexVector, const Block< T > &data, INX nr, Sort::Order=Sort::Ascending, int options=Sort::QuickSort)
| Sort a C-array containing nr T-type objects.
static INX | kthLargest (T *data, INX nr, INX k)
| Find the index of the k-th largest value.
static INX | quickSort (INX *inx, const T *data, INX nr, Sort::Order, int options)
| Sort container using quicksort.
static INX | heapSort (INX *inx, const T *data, INX nr, Sort::Order, int options)
| Sort container using heapsort.
static INX | insSort (INX *inx, const T *data, INX nr, Sort::Order, int options)
| Sort container using insertion sort.
static INX | parSort (INX *inx, const T *data, INX nr, Sort::Order, int options, int nthreads=0)
| Sort container using parallel merge sort (using OpenMP).

## Static Private Member Functions

static void | swapInx (INX &index1, INX &index2)
| Swap 2 indices.
static INX * | merge (const T *data, INX *inx, INX *tmp, INX nrrec, INX *index, INX nparts)
| Thedata buffer is divided in nparts parts.
static int | isAscending (const T *data, INX index1, INX index2)
| Check if 2 values are in ascending order.
static void | quickSortAsc (INX *inx, const T *, INX nr, Bool multiThread=False, Int rec_lim=128)
| Quicksort in ascending order.
static void | heapSortAsc (INX *inx, const T *, INX nr)
| Heapsort in ascending order.
static void | heapAscSiftDown (INX *inx, INX, INX, const T *)
| Helper function for ascending heapsort.
static INX | insSortAsc (INX *inx, const T *, INX nr, int option)
| Insertion sort in ascending order.
static INX | insSortAscDup (INX *inx, const T *, INX nr)
| Insertion sort in ascending order allowing duplicates.
static INX | insSortAscNoDup (INX *inx, const T *, INX nr)
| Insertion sort in ascending order allowing no duplicates.

## Detailed Description

template<class T, class INX = uInt>
class casacore::GenSortIndirect< T, INX >

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).

The class is templated on the type T of the sort key and the type INX of the index vector. In principle INX can be any type, but it should be a sufficiently large integer type (say uInt or uInt64).

Definition at line 206 of file GenSort.h.

## Member Function Documentation

## heapAscSiftDown()

template<class T, class INX = uInt>

void casacore::GenSortIndirect< T, INX >::heapAscSiftDown | ( | INX * | inx,
|  | INX | ,
|  | INX | ,
|  | const T * | )

static private

Helper function for ascending heapsort.

## heapSort()

template<class T, class INX = uInt>

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

static

Sort container using heapsort.

## heapSortAsc()

template<class T, class INX = uInt>

void casacore::GenSortIndirect< T, INX >::heapSortAsc | ( | INX * | inx,
|  | const T * | ,
|  | INX | nr )

static private

Heapsort in ascending order.

## insSort()

template<class T, class INX = uInt>

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

static

Sort container using insertion sort.

## insSortAsc()

template<class T, class INX = uInt>

INX casacore::GenSortIndirect< T, INX >::insSortAsc | ( | INX * | inx,
|  | const T * | ,
|  | INX | nr,
|  | int | option )

static private

Insertion sort in ascending order.

## insSortAscDup()

template<class T, class INX = uInt>

INX casacore::GenSortIndirect< T, INX >::insSortAscDup | ( | INX * | inx,
|  | const T * | ,
|  | INX | nr )

static private

Insertion sort in ascending order allowing duplicates.

This is also used by quicksort for its last steps.

## insSortAscNoDup()

template<class T, class INX = uInt>

INX casacore::GenSortIndirect< T, INX >::insSortAscNoDup | ( | INX * | inx,
|  | const T * | ,
|  | INX | nr )

static private

Insertion sort in ascending order allowing no duplicates.

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

## isAscending()

template<class T, class INX>

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

inline static private

Check if 2 values are in ascending order.

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

Definition at line 402 of file GenSort.h.

## kthLargest()

template<class T, class INX = uInt>

INX casacore::GenSortIndirect< T, INX >::kthLargest | ( | T * | data,
|  | INX | nr,
|  | INX | k )

static

Find the index of the k-th largest value.

## merge()

template<class T, class INX = uInt>

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

static private

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).

## parSort()

template<class T, class INX = uInt>

INX casacore::GenSortIndirect< T, INX >::parSort | ( | INX * | inx,
|  | const T * | data,
|  | INX | 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.

## quickSort()

template<class T, class INX = uInt>

INX casacore::GenSortIndirect< T, INX >::quickSort | ( | INX * | inx,
|  | const T * | data,
|  | INX | 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.

## quickSortAsc()

template<class T, class INX = uInt>

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

static private

Quicksort in ascending order.

References casacore::False.

## sort() [1/3]

template<class T, class INX = uInt>

INX casacore::GenSortIndirect< T, INX >::sort | ( | Vector< INX > & | 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.

References casacore::Sort::Ascending, and casacore::Sort::QuickSort.

## sort() [2/3]

template<class T, class INX = uInt>

INX casacore::GenSortIndirect< T, INX >::sort | ( | Vector< INX > & | indexVector,
|  | const Block< T > & | data,
|  | INX | 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.

References casacore::Sort::Ascending, and casacore::Sort::QuickSort.

## sort() [3/3]

template<class T, class INX = uInt>

INX casacore::GenSortIndirect< T, INX >::sort | ( | Vector< INX > & | indexVector,
|  | const T * | data,
|  | INX | 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.

References casacore::Sort::Ascending, and casacore::Sort::QuickSort.

Referenced by casacore::genSort(), casacore::genSort(), casacore::genSort(), and casacore::genSort().

## swapInx()

template<class T, class INX>

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

inline static private

Swap 2 indices.

Definition at line 395 of file GenSort.h.

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

- casa/Utilities/GenSort.h