casacore
casa
Utilities
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
casacore::Int
int Int
Definition:
aipstype.h:50
casacore::Bool
bool Bool
Define the standard types used by Casacore.
Definition:
aipstype.h:42
casacore
this file contains all the compiler specific defines
Definition:
mainpage.dox:28
casacore::value
LatticeExprNode value(const LatticeExprNode &expr)
This function returns the value of the expression without a mask.
casacore::uInt
unsigned int uInt
Definition:
aipstype.h:51
Generated by
1.8.13