seq Namespace Reference

Collection of Generic Sequential Functions. More...

Classes
class	seq::IndexHolder< T >
	A small helper class used while sorting a pair of value and its index in an array/vector. More...
Functions
template<typename T>
bool	BinarySearch (const T *arr, unsigned int nelem, const T &key, unsigned int *idx)
	A binary search implementation.
template<typename T>
void	flashsort (T *a, int n, int m, int *ctr)
	Flash sort algo to sort an array in O(n).
template<typename T>
void	makeVectorUnique (std::vector< T > &vec, bool isSorted)
	Removes duplicates from the vector.
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.
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.

---

Detailed Description

Collection of Generic Sequential Functions.

Author:

Rahul Sampath

---

Function Documentation

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 Definition at line 13 of file seqUtils.txx. Referenced by ot::flagNodesType2().

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. Definition at line 119 of file seqUtils.txx.

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. Definition at line 97 of file seqUtils.txx. References sort(). Referenced by ot::TreeNode::balanceSubtree(), ot::TreeNode::completeSubtree(), and ot::test::isBalancedInternal().

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 Definition at line 52 of file seqUtils.txx. Referenced by ot::test::isBalancedInternal().

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 Definition at line 36 of file seqUtils.txx.

---