seq Namespace Reference

Collection of Generic Sequential Functions. More...

Functions
template<typename T >
void	flashsort (T *a, int n, int m, int *ctr)
	Flash sort algo to sort an array in O(n). More...
template<typename T >
bool	BinarySearch (const T *arr, unsigned int nelem, const T &key, unsigned int *idx)
	A binary search implementation. More...
template<typename T >
int	UpperBound (unsigned int nelem, const T *arr, unsigned int startIdx, const T &key)
	Finds the index of the smallest upper bound of the search key in the array. More...
template<typename T >
bool	maxLowerBound (const std::vector< T > &arr, const T &key, unsigned int &retIdx, unsigned int *leftIdx, unsigned int *rightIdx)
	Finds the index of the greatest lower bound of the search key in the array. The implementation uses a simple modification of the binary search algorithm. More...

Detailed Description

Collection of Generic Sequential Functions.

Author

Rahul Sampath

Milinda Fernando.

Function Documentation

BinarySearch()

template<typename T >

bool seq::BinarySearch	(	const T *	arr,
		unsigned int	nelem,
		const T &	key,
		unsigned int *	idx
	)

A binary search implementation.

Author

Rahul Sampath

Parameters

arr	A sorted array
nelem	The length of the array
key	The search key
idx	0-based index of the position of the key in the array

Returns

'true' if the key exists in the array and 'false' otherwise

flashsort()

template<typename T >

void seq::flashsort	(	T *	a,
		int	n,
		int	m,
		int *	ctr
	)

Flash sort algo to sort an array in O(n).

Parameters

a	The array to be sorted
n	The number of elements in a
m	Size of index vector. typically m = 0.1*n
ctr	The number of times flashsort was called.

Sorts array a with n elements by use of the index vector l of dimension m (with m about 0.1 n). The routine runs fastest with a uniform distribution of elements. The vector l is declare dynamically using the calloc function. The variable ctr counts the number of times that flashsort is called. THRESHOLD is a very important constant. It is the minimum number of elements required in a subclass before recursion is used.

Templated version of flashsort based on original C code by Karl-Dietrich Neubert.

maxLowerBound()

template<typename T >

bool seq::maxLowerBound	(	const std::vector< T > &	arr,
		const T &	key,
		unsigned int &	retIdx,
		unsigned int *	leftIdx,
		unsigned int *	rightIdx
	)

Finds the index of the greatest lower bound of the search key in the array. The implementation uses a simple modification of the binary search algorithm.

Author

Rahul Sampath

Parameters

arr	A sorted array
key	The search key
retIdx	The index of the position of the last element in the array <= key
leftIdx	If this is not NULL, then the search will be limited to elements at positions >= *leftIdx
rightIdx	if this is not NULL, then the search will be limited to elements at positions <= *rightIdx

Returns

'true' if the search was successful

UpperBound()

template<typename T >

int seq::UpperBound	(	unsigned int	nelem,
		const T *	arr,
		unsigned int	startIdx,
		const T &	key
	)

Finds the index of the smallest upper bound of the search key in the array.

Author

Santi Swaroop Adavani

Parameters

arr	A sorted array
nelem	The length of the array
startIdx	The starting location to search from
key	The search key

Returns

the index of the first element in the array >= key