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.

file	AlgSort.c
	Basic sorting functions.

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

void	AlgSort (void base, size_t nElm, size_t elmSz, int(compar)(const void , const void ))
	A wrapper for qsort()/mergesort() which aims to be consistent across platforms. The default sort is qsort but on some platforms, eg Apple OSX this is unreliable and mergesort is used. The parameters are for qsort/mergesort. 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

data	The given data to sort.
nElm	Number of data elements.
elmSz	Size of the data elements.
cmpFn	Given 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

data	The given data.
idx	Data indicies to sort.
nElm	Number of data elements.
cmpFn	Given 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

elm0	Ptr to first element.
elm1	Ptr to second element.
cnt	Element 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

datum0	First data pointer.
datum1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

data	Data array.
idx	Index array.
id0	First index.
id1	Second 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

base	Array of elements to sort.
nElm	Number of elements in array.
elmSz	Element size.
cData	Client 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().

void AlgSort	(	void *	base,
		size_t	nElm,
		size_t	elmSz,
		int()(const void , const void *)	compar
	)

A wrapper for qsort()/mergesort() which aims to be consistent across platforms. The default sort is qsort but on some platforms, eg Apple OSX this is unreliable and mergesort is used. The parameters are for qsort/mergesort.

Parameters

base	Start of array to be sorted.
nElm	Number of elements in the array.
elmSz	Size of an array element.
compar	Comparison function.

Referenced by Wlz3DViewStructTransformBB(), Wlz3DViewTransformObj(), WlzCMeshCompSurfMap(), WlzCMeshToDomObjValues(), WlzCompDispIncGrey(), WlzConvHullClarkson2D(), WlzGetPatchTreeToDepth(), WlzGreySetHilbertRankValues(), WlzMatchICPWeightMatches(), WlzMeshTransformVtx(), WlzPolyToObj(), and WlzRasterLineSetItv2D().

Files

Functions

Detailed Description

Function Documentation