Woolz Image Processing  Version 1.7.0
AlgSort

Files

file  AlgHeapSort.c
 General purpose heap sort algorithms.
 
file  AlgQSort.c
 Specialized implementation of quick sort based on "Engineering a Sort Function" J.L. Bentley and M.D. McIlroy, Software Practice and Experience 23 (1993) 1249-1265.
 

Functions

AlgError AlgHeapSort (void *data, unsigned nElm, unsigned elmSz, int(*cmpFn)(void *, void *))
 Sorts given data using a heapsort algorithm. More...
 
AlgError AlgHeapSortIdx (void *data, int *idx, unsigned nElm, int(*cmpFn)(void *, int *, int, int))
 Sorts given data using a heapsort algorithm only the indicies are modified. More...
 
void AlgHeapElmSwap (void *elm0, void *elm1, int cnt)
 Swaps two data elements. More...
 
int AlgHeapSortCmpCFn (void *datum0, void *datum1)
 Char comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpUFn (void *datum0, void *datum1)
 Unsigned char comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpSFn (void *datum0, void *datum1)
 Short comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpIFn (void *datum0, void *datum1)
 Int comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpLFn (void *datum0, void *datum1)
 Long long comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpFFn (void *datum0, void *datum1)
 Float comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpDFn (void *datum0, void *datum1)
 Double comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortInvCmpCFn (void *datum0, void *datum1)
 Inverse char comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpUFn (void *datum0, void *datum1)
 Inverse unsigned char comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpSFn (void *datum0, void *datum1)
 Inverse short comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpIFn (void *datum0, void *datum1)
 Inverse int comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpLFn (void *datum0, void *datum1)
 Inverse long long comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpFFn (void *datum0, void *datum1)
 Inverse float comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpDFn (void *datum0, void *datum1)
 Inverse double comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortCmpIdxCFn (void *data, int *idx, int id0, int id1)
 Char comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpIdxUFn (void *data, int *idx, int id0, int id1)
 Unsigned char comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpIdxSFn (void *data, int *idx, int id0, int id1)
 Short comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpIdxIFn (void *data, int *idx, int id0, int id1)
 Int comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpIdxLFn (void *data, int *idx, int id0, int id1)
 Long comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpIdxFFn (void *data, int *idx, int id0, int id1)
 Float comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortCmpIdxDFn (void *data, int *idx, int id0, int id1)
 Double comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last. More...
 
int AlgHeapSortInvCmpIdxCFn (void *data, int *idx, int id0, int id1)
 Inverse char comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpIdxUFn (void *data, int *idx, int id0, int id1)
 Inverse unsigned char comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpIdxSFn (void *data, int *idx, int id0, int id1)
 Inverse short comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpIdxIFn (void *data, int *idx, int id0, int id1)
 Inverse int comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpIdxLFn (void *data, int *idx, int id0, int id1)
 Inverse long long comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpIdxFFn (void *data, int *idx, int id0, int id1)
 Inverse float comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last. More...
 
int AlgHeapSortInvCmpIdxDFn (void *data, int *idx, int id0, int id1)
 Inverse double comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last. More...
 
void AlgQSort (void *base, size_t nElm, size_t elmSz, void *cData, int(*cmpFn)(const void *, const void *, const void *))
 A qsort implementation which allows client data to be passed to the sort function. More...
 

Detailed Description

Function Documentation

AlgError AlgHeapSort ( void *  data,
unsigned  nElm,
unsigned  elmSz,
int(*)(void *, void *)  cmpFn 
)

Sorts given data using a heapsort algorithm.

Returns
Error code.
Parameters
dataThe given data to sort.
nElmNumber of data elements.
elmSzSize of the data elements.
cmpFnGiven element comparison function which must return an integer < 0, == 0 or > 0 to indicate that the first entry is <, == or > the second.

References ALG_ERR_FUNC, ALG_ERR_NONE, and AlgHeapElmSwap().

Referenced by WlzCMeshElmUseNod3D().

AlgError AlgHeapSortIdx ( void *  data,
int *  idx,
unsigned  nElm,
int(*)(void *, int *, int, int)  cmpFn 
)

Sorts given data using a heapsort algorithm only the indicies are modified.

Returns
Error code.
Parameters
dataThe given data.
idxData indicies to sort.
nElmNumber of data elements.
cmpFnGiven indexed element comparison function which must return an integer that is < 0, == 0 or > 0 to indicate that the first entry is <, == or > the second indexed entry.

References ALG_ERR_FUNC, and ALG_ERR_NONE.

Referenced by WlzCMeshCompSurfMap(), WlzCMeshCompSurfMapToDomain(), WlzCMeshIntersectDom2D5(), WlzConvexHullFromVtx3(), WlzConvexHullVtxD3ToI3(), WlzGeomVtxSortRadial(), WlzMatchICPWeightMatches(), WlzScalarFeatures2D(), and WlzSnapFit().

void AlgHeapElmSwap ( void *  elm0,
void *  elm1,
int  cnt 
)

Swaps two data elements.

Returns
void
Parameters
elm0Ptr to first element.
elm1Ptr to second element.
cntElement size.

Referenced by AlgHeapSort().

int AlgHeapSortCmpCFn ( void *  datum0,
void *  datum1 
)

Char comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last.

Returns
*((char *)datum0) - *((char *)datum1)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortCmpUFn ( void *  datum0,
void *  datum1 
)

Unsigned char comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last.

Returns
*((unsigned char *)datum0) - *((unsigned char *)datum1)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortCmpSFn ( void *  datum0,
void *  datum1 
)

Short comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last.

Returns
*((short *)datum0) - *((short *)datum1)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortCmpIFn ( void *  datum0,
void *  datum1 
)

Int comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last.

Returns
*((int *)datum0) - *((int *)datum1)
Parameters
datum0First data pointer.
datum1Second data pointer.

Referenced by WlzCMeshElmUseNod3D().

int AlgHeapSortCmpLFn ( void *  datum0,
void *  datum1 
)

Long long comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last.

Returns
*((long long *)datum0) - *((long long *)datum1)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortCmpFFn ( void *  datum0,
void *  datum1 
)

Float comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last.

Returns
*((float *)datum0) - *((float *)datum1)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortCmpDFn ( void *  datum0,
void *  datum1 
)

Double comparison function for AlgHeapSort(). Sorted data will have smallest entry first and greatest last.

Returns
*((double *)datum0) - *((double *)datum1)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortInvCmpCFn ( void *  datum0,
void *  datum1 
)

Inverse char comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last.

Returns
*((char *)datum1) - *((char *)datum0)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortInvCmpUFn ( void *  datum0,
void *  datum1 
)

Inverse unsigned char comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last.

Returns
*((unsigned char *)datum1) - *((unsigned char *)datum0)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortInvCmpSFn ( void *  datum0,
void *  datum1 
)

Inverse short comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last.

Returns
*((short *)datum1) - *((short *)datum0)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortInvCmpIFn ( void *  datum0,
void *  datum1 
)

Inverse int comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last.

Returns
*((int *)datum1) - *((int *)datum0)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortInvCmpLFn ( void *  datum0,
void *  datum1 
)

Inverse long long comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last.

Returns
*((long long *)datum1) - *((long long *)datum0)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortInvCmpFFn ( void *  datum0,
void *  datum1 
)

Inverse float comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last.

Returns
*((float *)datum1) - *((float *)datum0)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortInvCmpDFn ( void *  datum0,
void *  datum1 
)

Inverse double comparison function for AlgHeapSort(). Sorted data will have greatest entry first and smallest last.

Returns
*((double *)datum1) - *((double *)datum0)
Parameters
datum0First data pointer.
datum1Second data pointer.
int AlgHeapSortCmpIdxCFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Char comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last.

Returns
*((char *)data + *(idx + id0)) - *((char *)data + *(idx + id1))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.
int AlgHeapSortCmpIdxUFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Unsigned char comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last.

Returns
*((unsigned char *)data + *(idx + id0)) - *((unsigned char *)data + *(idx + id1))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D().

int AlgHeapSortCmpIdxSFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Short comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last.

Returns
*((short *)data + *(idx + id0)) - *((short *)data + *(idx + id1))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D().

int AlgHeapSortCmpIdxIFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Int comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last.

Returns
*((int *)data + *(idx + id0)) - *((int *)data + *(idx + id1))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzCMeshCompSurfMap(), WlzCMeshCompSurfMapToDomain(), WlzConvexHullVtxD3ToI3(), and WlzScalarFeatures2D().

int AlgHeapSortCmpIdxLFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Long comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last.

Returns
*((long long *)data + *(idx + id0)) - *((long long *)data + *(idx + id1))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D().

int AlgHeapSortCmpIdxFFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Float comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last.

Returns
*((float *)data + *(idx + id0)) - *((float *)data + *(idx + id1))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D().

int AlgHeapSortCmpIdxDFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Double comparison function for AlgHeapSortIdx(). Sorted data will have smallest entry first and greatest last.

Returns
*((double *)data + *(idx + id0)) - *((double *)data + *(idx + id1))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D(), and WlzSnapFit().

int AlgHeapSortInvCmpIdxCFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Inverse char comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last.

Returns
*((char *)data + *(idx + id1)) - *((char *)data + *(idx + id0))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.
int AlgHeapSortInvCmpIdxUFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Inverse unsigned char comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last.

Returns
*((unsigned char *)data + *(idx + id1)) - *((unsigned char *)data + *(idx + id0))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D().

int AlgHeapSortInvCmpIdxSFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Inverse short comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last.

Returns
*((short *)data + *(idx + id1)) - *((short *)data + *(idx + id0))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D().

int AlgHeapSortInvCmpIdxIFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Inverse int comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last.

Returns
*((int *)data + *(idx + id1)) - *((int *)data + *(idx + id0))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D().

int AlgHeapSortInvCmpIdxLFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Inverse long long comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last.

Returns
*((long *)data + *(idx + id1)) - *((long *)data + *(idx + id0))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D().

int AlgHeapSortInvCmpIdxFFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Inverse float comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last.

Returns
*((float *)data + *(idx + id1)) - *((float *)data + *(idx + id0))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D().

int AlgHeapSortInvCmpIdxDFn ( void *  data,
int *  idx,
int  id0,
int  id1 
)

Inverse double comparison function for AlgHeapSortIdx(). Sorted data will have greatest entry first and smallest last.

Returns
*((double *)data + *(idx + id1)) - *((double *)data + *(idx + id0))
Parameters
dataData array.
idxIndex array.
id0First index.
id1Second index.

Referenced by WlzScalarFeatures2D().

void AlgQSort ( void *  base,
size_t  nElm,
size_t  elmSz,
void *  cData,
int(*)(const void *, const void *, const void *)  cmpFn 
)

A qsort implementation which allows client data to be passed to the sort function.

Returns
void
Parameters
baseArray of elements to sort.
nElmNumber of elements in array.
elmSzElement size.
cDataClient data passed to the client comparison function.
(*cmpFn)Comparison function which is given the client data followed by the two data pointers for comparison.

References ALG_MIN, ALG_QSORT_PVINIT, ALG_QSORT_SWAP, ALG_QSORT_SWAPCODE, and ALG_QSORT_VECSWAP.

Referenced by WlzIDomainFromPItv2D(), WlzLBTBalanceDomain2D(), WlzLBTBalanceDomain3D(), WlzLBTKeyToBox2I(), WlzPDomainFromPItv3D(), and WlzSplitObj().