casacore
Loading...
Searching...
No Matches
casacore::LinearSearch_global_functions_linearsearch Struct Reference

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

... // 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;
}
}
size_t nelements() const
How many elements does this array have? Product of all axis lengths.
Definition ArrayBase.h:101
int Int
Definition aipstype.h:48
bool Bool
Define the standard types used by Casacore.
Definition aipstype.h:40
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 )

◆ 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.

◆ 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 )

◆ 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.


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