casacore
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 
36 namespace 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>
113 
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.
124 template<class Container, class ElType>
125 Int linearSearch1 (const Container& container, const ElType& value,
126  uInt lower = 0);
127 template<class Container, class ElType>
128 Int 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.
131 template<class Container, class ElType>
132 Int linearSearchBrackets1 (const Container& container, const ElType& value,
133  uInt lower = 0);
134 template<class Container, class ElType>
135 Int 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.