casacore
Loading...
Searching...
No Matches
LinearSearch.h
Go to the documentation of this file.
1//# LinearSearch.h: Linear search through linear data structures
2//# Copyright (C) 1997,1999
3//# Associated Universities, Inc. Washington DC, USA.
4//#
5//# This library is free software; you can redistribute it and/or modify it
6//# under the terms of the GNU Library General Public License as published by
7//# the Free Software Foundation; either version 2 of the License, or (at your
8//# option) any later version.
9//#
10//# This library is distributed in the hope that it will be useful, but WITHOUT
11//# ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12//# FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
13//# License for more details.
14//#
15//# You should have received a copy of the GNU Library General Public License
16//# along with this library; if not, write to the Free Software Foundation,
17//# Inc., 675 Massachusetts Ave, Cambridge, MA 02139, USA.
18//#
19//# Correspondence concerning AIPS++ should be addressed as follows:
20//# Internet email: aips2-request@nrao.edu.
21//# Postal address: AIPS++ Project Office
22//# National Radio Astronomy Observatory
23//# 520 Edgemont Road
24//# Charlottesville, VA 22903-2475 USA
25//#
26//#
27//# $Id$
28
29
30#ifndef CASA_LINEARSEARCH_H
31#define CASA_LINEARSEARCH_H
32
33//# Includes
34#include <casacore/casa/aips.h>
35
36namespace casacore { //# NAMESPACE CASACORE - BEGIN
37
38// <summary>
39// Linear search a linear data structure.
40// </summary>
41
42// <reviewed reviewer="UNKNOWN" date="before2004/08/25" tests="tLinearSearch" demos="">
43// </reviewed>
44
45// <synopsis>
46// These linear search functions work on linear data structures
47// which have operator() or operator[] defined on them (<i>e.g.</i>
48// C-array, Vector, IPosition, Block, ScalarColumn, <i>etc.</i>)
49// Two versions of the functions are provided, one which uses
50// parentheses () for indexing, one which uses square brackets [] (obviously
51// the latter one can also be used for ordinary C-style pointers and arrays).
52// It is assumed that the container uses zero-based indexing.
53//
54// The returned index is in the range [0..n-1]. When the value is
55// not found, -1 is returned.
56// <note role=tip>
57// While normally you want to search a container with indices in the range
58// <src>[0 ... n-1]</src>, any desired lower bound may be used instead.
59// </note>
60// <note role=caution>
61// Linear searching should only be used for small arrays.
62// For larger arrays sort and
63// <linkto group=BinarySearch.h#binarysearch>binarySearch</linkto>
64// should be used.
65// </note>
66// </synopsis>
67//
68// <example>
69// <srcblock>
70// Vector<Int> vi;
71// ... // Sets vi somehow
72// Int val;
73// Bool found;
74// while (cin >> val && val != -999) {
75// Int where = linearSearch(found, vi, val, vi.nelements());
76// if (found) {
77// cout << "Found " << val << " at position " << where << endl;
78// } else {
79// cout << val << " is not in the vector, but it belongs at " <<
80// where << endl;
81// }
82// }
83// </srcblock>
84// </example>
85//
86// <motivation>
87// Neil Killeen needed a linear search on a Vector.
88// Modelling it after BinarySearch was the logical step to take.
89// </motivation>
90//
91// <templating arg=Container>
92// <li> operator(Int) or operator[Int] needs to be defined.
93// <li> The index must be zero based.
94// <li> The result of that indexing must be an expression that can be
95// compared with an object of class ElType. Normally in fact it would
96// be a temporary of class ElType.
97// <li> Member function nelements() is needed when the shorthand is taken.
98// </templating>
99// <templating arg=ElType>
100// <li> The equal operator (==) need to be defined.
101// </templating>
102//
103// <todo asof="yyyy/mm/dd">
104// <li> I suspect that an implementation is possible that only calls
105// operator() or [] once during each evaluation of the while loop.
106// <li> MACROize implementation so that code isn't repeated twice. Or,
107// possibly implement one using the other (e.g. by introducing an adapter
108// class that turns (i) into [i].
109// </todo>
110
111
112// <group name=linearsearch>
114// Search <i>container</i> for <i>value</i>. There are assumed to be at least
115// <i>n</i> elements in the container. The container will be searched for
116// indices in the range <src>[lower ... lower + n - 1]</src> Return the index
117// of the first element which is greater than or equal to (ascending order) or
118// less than or equal to (descending order) the value.
119// When not found, -1 is returned and found is set to False.
120//# GvD 19971008: The functions need different names, because g++ gives errors
121//# when instantiating.
122// <group>
123// This version of the function is for containers that use () for indexing.
124template<class Container, class ElType>
125Int linearSearch1 (const Container& container, const ElType& value,
126 uInt lower = 0);
127template<class Container, class ElType>
128Int linearSearch (Bool& found, const Container& container,
129 const ElType& value, uInt n, uInt lower=0);
130// This version of the function is for containers that use [] for indexing.
131template<class Container, class ElType>
132Int linearSearchBrackets1 (const Container& container, const ElType& value,
133 uInt lower = 0);
134template<class Container, class ElType>
135Int linearSearchBrackets (Bool& found, const Container& container,
136 const ElType& value, uInt n, uInt lower=0);
137// </group>
138// </group>
139
140
141
142} //# NAMESPACE CASACORE - END
143
144#ifndef CASACORE_NO_AUTO_TEMPLATES
145#include <casacore/casa/Utilities/LinearSearch.tcc>
146#endif //# CASACORE_NO_AUTO_TEMPLATES
147#endif
this file contains all the compiler specific defines
Definition mainpage.dox:28
unsigned int uInt
Definition aipstype.h:51
int Int
Definition aipstype.h:50
bool Bool
Define the standard types used by Casacore.
Definition aipstype.h:42
LatticeExprNode value(const LatticeExprNode &expr)
This function returns the value of the expression without a mask.
Int linearSearch1(const Container &container, const ElType &value, uInt lower=0)
Search container for value.
Int linearSearchBrackets(Bool &found, const Container &container, const ElType &value, uInt n, uInt lower=0)
Int linearSearch(Bool &found, const Container &container, const ElType &value, uInt n, uInt lower=0)
Int linearSearchBrackets1(const Container &container, const ElType &value, uInt lower=0)
This version of the function is for containers that use [] for indexing.