casacore::LinearSearch_global_functions_linearsearch Struct Reference

Linear search a linear data structure. More...

#include <LinearSearch.h>

Public Member Functions
template<class Container , class ElType >
Int	linearSearch1 (const Container &container, const ElType &value, uInt lower=0)
	Search container for value. More...
template<class Container , class ElType >
Int	linearSearch (Bool &found, const Container &container, const ElType &value, uInt n, uInt lower=0)
template<class Container , class ElType >
Int	linearSearchBrackets1 (const Container &container, const ElType &value, uInt lower=0)
	This version of the function is for containers that use [] for indexing. More...
template<class Container , class ElType >
Int	linearSearchBrackets (Bool &found, const Container &container, const ElType &value, uInt n, uInt lower=0)

Detailed Description

Linear search a linear data structure.

Review Status

Reviewed By:

UNKNOWN

Date Reviewed:

before2004/08/25

Test programs:

tLinearSearch

Synopsis

These linear search functions work on linear data structures which have operator() or operator[] defined on them (e.g. C-array, Vector, IPosition, Block, ScalarColumn, etc.) Two versions of the functions are provided, one which uses parentheses () for indexing, one which uses square brackets [] (obviously the latter one can also be used for ordinary C-style pointers and arrays). It is assumed that the container uses zero-based indexing.

The returned index is in the range [0..n-1]. When the value is not found, -1 is returned.
Tip: While normally you want to search a container with indices in the range [0 ;;; n-1], any desired lower bound may be used instead;

Caution: Linear searching should only be used for small arrays; For larger arrays sort and binarySearch should be used;

Example

 Vector<Int> vi;
...  // Sets vi somehow
 Int val;
 Bool found;
 while (cin >> val  &&  val != -999) {
 Int where = linearSearch(found, vi, val, vi.nelements());
 if (found) {
 cout << "Found " << val << " at position " << where << endl;
 } else {
 cout << val << " is not in the vector, but it belongs at " <<
 where << endl;
 }
 } 

Motivation

Neil Killeen needed a linear search on a Vector. Modelling it after BinarySearch was the logical step to take.

Template Type Argument Requirements (Container)

• operator(Int) or operator[Int] needs to be defined.
• The index must be zero based.
• The result of that indexing must be an expression that can be compared with an object of class ElType. Normally in fact it would be a temporary of class ElType.
• Member function nelements() is needed when the shorthand is taken.

Template Type Argument Requirements (ElType)

• The equal operator (==) need to be defined.

To Do

• I suspect that an implementation is possible that only calls operator() or [] once during each evaluation of the while loop.
• MACROize implementation so that code isn't repeated twice. Or, possibly implement one using the other (e.g. by introducing an adapter class that turns (i) into [i].

Definition at line 113 of file LinearSearch.h.

Member Function Documentation

template<class Container , class ElType >

Int casacore::LinearSearch_global_functions_linearsearch::linearSearch	(	Bool &	found,
		const Container &	container,
		const ElType &	value,
		uInt	n,
		uInt	lower = 0
	)

template<class Container , class ElType >

Int casacore::LinearSearch_global_functions_linearsearch::linearSearch1	(	const Container &	container,
		const ElType &	value,
		uInt	lower = 0
	)

Search container for value.

There are assumed to be at least n elements in the container. The container will be searched for indices in the range [lower... lower + n - 1] Return the index of the first element which is greater than or equal to (ascending order) or less than or equal to (descending order) the value. When not found, -1 is returned and found is set to False.

This version of the function is for containers that use () for indexing.

template<class Container , class ElType >

Int casacore::LinearSearch_global_functions_linearsearch::linearSearchBrackets	(	Bool &	found,
		const Container &	container,
		const ElType &	value,
		uInt	n,
		uInt	lower = 0
	)

template<class Container , class ElType >

Int casacore::LinearSearch_global_functions_linearsearch::linearSearchBrackets1	(	const Container &	container,
		const ElType &	value,
		uInt	lower = 0
	)

This version of the function is for containers that use [] for indexing.

---

The documentation for this struct was generated from the following file:

• casa/Utilities/LinearSearch.h