Loading...
Searching...
No Matches
casacore::LinearSearch_global_functions_linearsearch Struct Reference
casa package (libcasa_casa) » Utilities_module

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.
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.
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;
}
}
casacore::ArrayBase::nelements
size_t nelements() const
How many elements does this array have?
Definition ArrayBase.h:101
casacore::Vector
Definition Vector.h:82
casacore::Int
int Int
Definition aipstype.h:48
casacore::Bool
bool Bool
Define the standard types used by Casacore.
Definition aipstype.h:40
casacore::LinearSearch_global_functions_linearsearch::linearSearch
Int linearSearch(Bool &found, const Container &container, const ElType &value, uInt n, uInt lower=0)

### 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 110 of file LinearSearch.h.

## Member Function Documentation

## linearSearch()

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 )

References casacore::NewDelAllocator< T >::value.

## linearSearch1()

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.

References casacore::NewDelAllocator< T >::value.

## linearSearchBrackets()

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 )

References casacore::NewDelAllocator< T >::value.

## linearSearchBrackets1()

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.

References casacore::NewDelAllocator< T >::value.

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

- casa/Utilities/LinearSearch.h