Loading...
Searching...
No Matches
casacore::Sort Class Reference
casa package (libcasa_casa) » Utilities_module

Sort on one or more keys, ascending and/or descending. More...

`#include <Sort.h>`

## Public Types

enum | Option { DefaultSort , HeapSort , InsSort , QuickSort , ParSort , NoDuplicates }
| Enumerate the sort options: More...
enum | Order { Ascending , Descending }
| Enumerate the sort order: More...

## Public Member Functions

| Sort ()
| The default constructor can be used when the data is only passed in via function sortKey.
| Sort (const void *data, uInt elementSize)
| Construct a Sort object for the given data array with elements of elementSize bytes.
| Sort (const Sort &)
| Copy constructor (copy semantics).
| ~Sort ()
Sort & | operator= (const Sort &)
| Assignment (copy semantics).
void | sortKey (const void *data, DataType, uInt increment=0, Order=Ascending)
| Define a sort key (the most significant key should be defined first).
void | sortKey (const void *data, const std::shared_ptr< BaseCompare > &, uInt increment, Order=Ascending)
void | sortKey (uInt offset, DataType, Order=Ascending)
void | sortKey (uInt offset, const std::shared_ptr< BaseCompare > &, Order=Ascending)
uInt | sort (Vector< uInt > &indexVector, uInt nrrec, int options=DefaultSort, Bool tryGenSort=True) const
| Sort the data array of nrrec records.
uInt64 | sort (Vector< uInt64 > &indexVector, uInt64 nrrec, int options=DefaultSort, Bool tryGenSort=True) const
uInt | unique (Vector< uInt > &uniqueVector, uInt nrrec) const
| Get all unique records in a sorted array.
uInt | unique (Vector< uInt > &uniqueVector, const Vector< uInt > &indexVector) const
uInt | unique (Vector< uInt > &uniqueVector, Vector< size_t > &changeKey, const Vector< uInt > &indexVector) const
uInt64 | unique (Vector< uInt64 > &uniqueVector, uInt64 nrrec) const
uInt64 | unique (Vector< uInt64 > &uniqueVector, const Vector< uInt64 > &indexVector) const
uInt64 | unique (Vector< uInt64 > &uniqueVector, Vector< size_t > &changeKey, const Vector< uInt64 > &indexVector) const

## Private Member Functions

template<typename T>
T | doSort (Vector< T > &indexVector, T nrrec, int options=DefaultSort, Bool tryGenSort=True) const
template<typename T>
T | doUnique (Vector< T > &uniqueVector, T nrrec) const
template<typename T>
T | doUnique (Vector< T > &uniqueVector, const Vector< T > &indexVector) const
template<typename T>
T | doUnique (Vector< T > &uniqueVector, Vector< size_t > &changeKey, const Vector< T > &indexVector) const
void | copy (const Sort &that)
| Copy that Sort object to this.
void | addKey (const void *data, DataType, uInt increment, int options)
| Add a sort key giving a data type and stride or the sort key.
void | addKey (SortKey *)
template<typename T>
T | insSort (T nr, T *indices) const
| Do an insertion sort, optionally skipping duplicates.
template<typename T>
T | insSortNoDup (T nr, T *indices) const
template<typename T>
T | parSort (int nthr, T nrrec, T *inx) const
| Do a merge sort, if possible in parallel using OpenMP.
template<typename T>
void | merge (T *inx, T *tmp, T size, T *index, T nparts) const
template<typename T>
T | quickSort (T nr, T *indices) const
| Do a quicksort, optionally skipping duplicates (qkSort is the actual quicksort function).
template<typename T>
T | quickSortNoDup (T nr, T *indices) const
template<typename T>
void | qkSort (T nr, T *indices) const
template<typename T>
T | heapSort (T nr, T *indices) const
| Do a heapsort, optionally skipping duplicates.
template<typename T>
T | heapSortNoDup (T nr, T *indices) const
template<typename T>
void | siftDown (T low, T up, T *indices) const
| Siftdown algorithm for heapsort.
template<typename T>
int | compare (T index1, T index2) const
| Compare 2 records based on the comparison functions.
template<typename T>
int | compareChangeIdx (T i1, T i2, size_t &idxComp) const
| As compare() but it also gives back the index of the first comparison function that didn't match.
template<typename T>
void | swap (T index1, T index2, T *indices) const
| Swap 2 indices.

## Private Attributes

Block< SortKey * > | keys_p
size_t | nrkey_p
const void * | data_p
uInt | size_p
int | order_p

## Detailed Description

Sort on one or more keys, ascending and/or descending.

### Intended use:

Public interface

### Review Status

Reviewed By:
  Friso Olnon
Date Reviewed:
  1995/03/01
Test programs:
  tSort, tSort_1

### Synopsis

Sort lets you sort data on one or more keys in a mix of Sort::ascending and Sort::descending order. Duplicates can be skipped by giving the option Sort::NoDuplicates. Only in this case the number of output elements can be different from the number of input elements.
The unique function offers another way of getting unique values.

Class Sort does not sort the data themselves, but returns an index to them. This gives more flexibility and allows the sort to be stable; but it is slower.
Very fast sorting of the data themselves can be done with the functions in class GenSort. If sorting on a single key with a standard data type is done, Sort will use GenSortIndirect to speed up the sort.
Four sort algorithms are provided:

Sort::ParSort
  The parallel merge sort is the fastest if it can use multiple threads. For a single thread it has O(n*log(n)) behaviour, but is slower than quicksort. A drawback is that it needs an extra index array to do the merge.
Sort::InsSort
  Insertion sort has O(n*n) behaviour, thus is very slow for large arrays. However, it is the fastest method for small arrays (< 50 elements) and for arrays already (almost) in the right order.
Sort::QuickSort
  Care has been taken to solve the well-known quicksort problems like "array already in order" or "many equal elements". The behaviour is O(n*log(n)) in all the cases tested, even in degenerated cases where the SUN Solaris qsort algorithm is O(n*n).
Sort::HeapSort
  Heapsort has O(n*log(n)) behaviour. Its speed is lower than that of QuickSort, so QuickSort is the default algorithm.

The default is to use QuickSort for small arrays or if only a single thread can be used. Otherwise ParSort is the default.

All sort algorithms are stable, which means that the original order is kept when keys are equal.

The sort is a four step process:

1. Construct the Sort object.
2. Define the sort keys. The function sortKey must be called for each sort key (the most significant one first). The comparison object can be passed in directly, or a basic data type can be given. In the latter case the appropriate ObjCompare comparison object will be created.
3. Sort the data. The function sort returns an index array, which is allocated when needed.
4. Destruct the Sort object (usually done automatically) and delete the index array.

The data can be in a single array of structs, in separate arrays, or in a mix of those. Of course, all arrays must have the same length. The data can be passed to the Sort constructor and/or to the sortKey function. If passed to the Sort constructor, the offset of the data item in the data array must be given to sortKey.

### Example

In the first example we sort the data contained in two "parallel" arrays, idata and ddata, both of length nrdata.

Sort sort;
sort.sortKey (idata, TpInt); // define 1st sort key
sort.sortKey (ddata, TpDouble,0,Sort::Descending); // define 2nd sort key
Vector<uInt> inx;
sort.sort (inx, nrdata);
for (uInt i=0; i<nrdata; i++) { // show sorted data
cout << idata[inx[i]] << " " << ddata[inx[i]] << endl;
}
casacore::Sort::Descending
@ Descending
Definition Sort.h:257
casacore::Sort::sort
uInt sort(Vector< uInt > &indexVector, uInt nrrec, int options=DefaultSort, Bool tryGenSort=True) const
Sort the data array of nrrec records.
casacore::Sort::Sort
Sort()
The default constructor can be used when the data is only passed in via function sortKey.
casacore::Vector
Definition Vector.h:82
casacore::uInt
unsigned int uInt
Definition aipstype.h:49

Now nr contains the nr of records (=nrdata) and inx an array of (sorted) indices.

In the second example we sort the data stored in an array of structs on the double (ascending) and the string (descending). We can pass the data to the Sort constructor, and the offsets of the struct elements to the sortKey function.

struct Ts {
String as;
double ad;
}
Vector<uInt> inx;
Sort sort (tsarr, sizeof(Ts));
sort.sortKey ((char*)&tsarr[0].ad - (char*)tsarr, TpDouble);
sort.sortKey ((char*)&tsarr[0].as - (char*)tsarr, TpString,
Sort::Descending);
sort.sort (inx, nrts);
casacore::Sort
Sort on one or more keys, ascending and/or descending.
Definition Sort.h:245
casacore::String
String: the storage and methods of handling collections of characters.
Definition String.h:223

Note that the first argument in function sortKey gives the offset of the variable in the struct.

Alternatively, and probably slightly easier, we could pass the data to the sortKey function and use an increment:

struct Ts {
String as;
double ad;
}
Vector<uInt> inx;
Sort sort;
sort.sortKey (&tsarr[0].ad, TpDouble, sizeof(Ts));
sort.sortKey (&tsarr[0].as, TpString, sizeof(Ts), Sort::Descending);
sort.sort (inx, nrts);
casacore::Sort::sortKey
void sortKey(const void *data, DataType, uInt increment=0, Order=Ascending)
Define a sort key (the most significant key should be defined first).

Finally, we could provide a comparison object for the struct.

struct Ts {
String as;
double ad;
}
class MyCompare: public BaseCompare {
virtual int comp (const void* val1, const void* val2) const
{
const Ts& t1 = *(Ts*)val1;
const Ts& t2 = *(Ts*)val2;
if (t1.ad < t2.ad) return -1;
if (t1.ad > t2.ad) return 1;
if (t1.as < t2.as) return 1; // string must be descending
if (t1.as > t2.as) return -1;
return 0;
}
};
Vector<uInt> inx;
Sort sort;
sort.sortKey (tsarr, compareTs, sizeof(Ts));
sort.sort (inx, nrts);
casacore::BaseCompare
abstract base class for comparing two objects
Definition Compare.h:63
casacore::BaseCompare::comp
virtual int comp(const void *obj1, const void *obj2) const =0
Compare two objects, and return.

Definition at line 244 of file Sort.h.

## Member Enumeration Documentation

## Option

enum casacore::Sort::Option

Enumerate the sort options:

Enumerator
DefaultSort |
HeapSort |
InsSort |
QuickSort |
ParSort |
NoDuplicates |

Definition at line 248 of file Sort.h.

## Order

enum casacore::Sort::Order

Enumerate the sort order:

Enumerator
Ascending |
Descending |

Definition at line 256 of file Sort.h.

## Constructor & Destructor Documentation

## Sort() [1/3]

casacore::Sort::Sort | ( |  | ) |

The default constructor can be used when the data is only passed in via function sortKey.

Referenced by copy(), operator=(), and Sort().

## Sort() [2/3]

casacore::Sort::Sort | ( | const void * | data,
|  | uInt | elementSize )

Construct a Sort object for the given data array with elements of elementSize bytes.

This data array will be used when an offset is given to the sortKey functions. You can still pass additional data arrays to the sortKey functions.

## Sort() [3/3]

casacore::Sort::Sort | ( | const Sort & |  | ) |

Copy constructor (copy semantics).

References Sort().

## ~Sort()

casacore::Sort::~Sort | ( |  | ) |

## Member Function Documentation

## addKey() [1/2]

void casacore::Sort::addKey | ( | const void * | data,
|  | DataType | ,
|  | uInt | increment,
|  | int | options )

private

Add a sort key giving a data type and stride or the sort key.

## addKey() [2/2]

void casacore::Sort::addKey | ( | SortKey * |  | ) |

private

## compare()

template<typename T>

int casacore::Sort::compare | ( | T | index1,
|  | T | index2 ) const

private

Compare 2 records based on the comparison functions.

## compareChangeIdx()

template<typename T>

int casacore::Sort::compareChangeIdx | ( | T | i1,
|  | T | i2,
|  | size_t & | idxComp ) const

private

As compare() but it also gives back the index of the first comparison function that didn't match.

## copy()

void casacore::Sort::copy | ( | const Sort & | that | ) |

private

Copy that Sort object to this.

References Sort().

## doSort()

template<typename T>

T casacore::Sort::doSort | ( | Vector< T > & | indexVector,
|  | T | nrrec,
|  | int | options = DefaultSort,
|  | Bool | tryGenSort = True ) const

private

References DefaultSort, and casacore::True.

## doUnique() [1/3]

template<typename T>

T casacore::Sort::doUnique | ( | Vector< T > & | uniqueVector,
|  | const Vector< T > & | indexVector ) const

private

## doUnique() [2/3]

template<typename T>

T casacore::Sort::doUnique | ( | Vector< T > & | uniqueVector,
|  | T | nrrec ) const

private

## doUnique() [3/3]

template<typename T>

T casacore::Sort::doUnique | ( | Vector< T > & | uniqueVector,
|  | Vector< size_t > & | changeKey,
|  | const Vector< T > & | indexVector ) const

private

## heapSort()

template<typename T>

T casacore::Sort::heapSort | ( | T | nr,
|  | T * | indices ) const

private

Do a heapsort, optionally skipping duplicates.

## heapSortNoDup()

template<typename T>

T casacore::Sort::heapSortNoDup | ( | T | nr,
|  | T * | indices ) const

private

## insSort()

template<typename T>

T casacore::Sort::insSort | ( | T | nr,
|  | T * | indices ) const

private

Do an insertion sort, optionally skipping duplicates.

## insSortNoDup()

template<typename T>

T casacore::Sort::insSortNoDup | ( | T | nr,
|  | T * | indices ) const

private

## merge()

template<typename T>

void casacore::Sort::merge | ( | T * | inx,
|  | T * | tmp,
|  | T | size,
|  | T * | index,
|  | T | nparts ) const

private

References casacore::size().

## operator=()

Sort & casacore::Sort::operator= | ( | const Sort & |  | ) |

Assignment (copy semantics).

References Sort().

## parSort()

template<typename T>

T casacore::Sort::parSort | ( | int | nthr,
|  | T | nrrec,
|  | T * | inx ) const

private

Do a merge sort, if possible in parallel using OpenMP.

Note that the env.var. OMP_NUM_TRHEADS sets the maximum nr of threads to use. It defaults to the number of cores.

## qkSort()

template<typename T>

void casacore::Sort::qkSort | ( | T | nr,
|  | T * | indices ) const

private

## quickSort()

template<typename T>

T casacore::Sort::quickSort | ( | T | nr,
|  | T * | indices ) const

private

Do a quicksort, optionally skipping duplicates (qkSort is the actual quicksort function).

## quickSortNoDup()

template<typename T>

T casacore::Sort::quickSortNoDup | ( | T | nr,
|  | T * | indices ) const

private

## siftDown()

template<typename T>

void casacore::Sort::siftDown | ( | T | low,
|  | T | up,
|  | T * | indices ) const

private

Siftdown algorithm for heapsort.

## sort() [1/2]

uInt casacore::Sort::sort | ( | Vector< uInt > & | indexVector,
|  | uInt | nrrec,
|  | int | options = DefaultSort,
|  | Bool | tryGenSort = True ) const

Sort the data array of nrrec records.

The result is an array of indices giving the requested order. It returns the number of resulting records. The indices array is resized to that number.
By default it'll try if the faster GenSortIndirect can be used if a sort on a single key is used.

References DefaultSort, and casacore::True.

## sort() [2/2]

uInt64 casacore::Sort::sort | ( | Vector< uInt64 > & | indexVector,
|  | uInt64 | nrrec,
|  | int | options = DefaultSort,
|  | Bool | tryGenSort = True ) const

References DefaultSort, and casacore::True.

## sortKey() [1/4]

void casacore::Sort::sortKey | ( | const void * | data,
|  | const std::shared_ptr< BaseCompare > & | ,
|  | uInt | increment,
|  | Order | = Ascending )

References Ascending.

## sortKey() [2/4]

void casacore::Sort::sortKey | ( | const void * | data,
|  | DataType | ,
|  | uInt | increment = 0,
|  | Order | = Ascending )

Define a sort key (the most significant key should be defined first).

The key contains:

- A pointer to the start of the data array. — When structs are sorted on an element in the struct, the pointer must point to that element in the first struct.
- A pointer to the comparison object to be used. — The comparison object can be specified in two ways:
  - by giving a basic data type, in which case the appropriate comparison object will be created automatically, or
  - by a std::shared_ptr of a comparison object. You may want to use the templated comparison classes ObjCompare (), but you are free to use any other class derived from BaseCompare that implements the comp function.
- The increment from one data element to the next. — When structs are sorted on an element in the struct, the increment should be the size of the struct. If the comparison object is automatically created using the data type specified, the default increment is the size of the data type.
- The sort order. — Ascending (default) or Descending;

When the data array has been passed to the Sort constructor, the data pointer and the increment arguments can be replaced by a single argument: the offset of the key in each element of the array.

References Ascending.

## sortKey() [3/4]

void casacore::Sort::sortKey | ( | uInt | offset,
|  | const std::shared_ptr< BaseCompare > & | ,
|  | Order | = Ascending )

References Ascending, and casacore::offset().

## sortKey() [4/4]

void casacore::Sort::sortKey | ( | uInt | offset,
|  | DataType | ,
|  | Order | = Ascending )

References Ascending, and casacore::offset().

## swap()

template<typename T>

void casacore::Sort::swap | ( | T | index1,
|  | T | index2,
|  | T * | indices ) const

inline private

Swap 2 indices.

Definition at line 435 of file Sort.h.

## unique() [1/6]

uInt casacore::Sort::unique | ( | Vector< uInt > & | uniqueVector,
|  | const Vector< uInt > & | indexVector ) const

## unique() [2/6]

uInt casacore::Sort::unique | ( | Vector< uInt > & | uniqueVector,
|  | uInt | nrrec ) const

Get all unique records in a sorted array.

The array order is given in the indexVector (as possibly returned by the sort function). The default indexVector is 0..nrrec-1. The index of each first unique record is returned in the uniqueVector. They are indices in the supplied indexVector, so data[indexVector(uniqueVector(i))] is giving the i-th unique record. Note that the records indexed by indexVector(uniqueVector(i)) till indexVector(uniqueVector(i+1)) are all the same.
It returns the number of unique records. The unique array is resized to that number. The third version also gives back a vector with the keys that change in each sorting group. The size of changeKey is the same as uniqueVector, and for each unique sorting group indicates the index of the keyword that will change at the end of the group.

## unique() [3/6]

uInt casacore::Sort::unique | ( | Vector< uInt > & | uniqueVector,
|  | Vector< size_t > & | changeKey,
|  | const Vector< uInt > & | indexVector ) const

## unique() [4/6]

uInt64 casacore::Sort::unique | ( | Vector< uInt64 > & | uniqueVector,
|  | const Vector< uInt64 > & | indexVector ) const

## unique() [5/6]

uInt64 casacore::Sort::unique | ( | Vector< uInt64 > & | uniqueVector,
|  | uInt64 | nrrec ) const

## unique() [6/6]

uInt64 casacore::Sort::unique | ( | Vector< uInt64 > & | uniqueVector,
|  | Vector< size_t > & | changeKey,
|  | const Vector< uInt64 > & | indexVector ) const

## Member Data Documentation

## data_p

const void* casacore::Sort::data_p

private

Definition at line 445 of file Sort.h.

## keys_p

Block<SortKey*> casacore::Sort::keys_p

private

Definition at line 443 of file Sort.h.

## nrkey_p

size_t casacore::Sort::nrkey_p

private

Definition at line 444 of file Sort.h.

## order_p

int casacore::Sort::order_p

private

Definition at line 447 of file Sort.h.

## size_p

uInt casacore::Sort::size_p

private

Definition at line 446 of file Sort.h.

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

- casa/Utilities/Sort.h