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 >
void	makeVectorUnique (std::vector< T > &vec, bool isSorted)
	Removes duplicates from the vector. 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

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.

makeVectorUnique()

template<typename T >

void seq::makeVectorUnique	(	std::vector< T > &	vec,
		bool	isSorted
	)

Removes duplicates from the vector.

Author

Rahul Sampath

Parameters

vec	The vector to be made free of duplicates.
isSorted	Pass 'true' if the input is sorted.

If the vector is not sorted, it is first sorted before removing duplicates.

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