casa  5.7.0-16
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | List of all members
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)

Template Type Argument Requirements (ElType)

To Do

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: