casacore
casa
Utilities
BinarySearch.h
Go to the documentation of this file.
1
//# BinarySearch.h: Binary search through linear, sorted, data structures
2
//# Copyright (C) 1995,1996,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_BINARYSEARCH_H
31
#define CASA_BINARYSEARCH_H
32
33
//# Includes
34
#include <casacore/casa/aips.h>
35
36
namespace
casacore
{
//# NAMESPACE CASACORE - BEGIN
37
38
// <summary>
39
// Binary search a sorted, linear, data structure.
40
// </summary>
41
42
// <reviewed reviewer="Ger van Diepen" date="1995/03/31" tests="tBinarySearch" demos="">
43
// </reviewed>
44
45
// <synopsis>
46
// These binary search functions work on sorted, 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 container must be sorted (sorting is available through the
55
// <linkto class="Sort">Sort</linkto> and
56
// <linkto class="GenSort">GenSort</linkto>
57
// classes, and from various
58
// <linkto class="Table">Table</linkto> sort functions). The returned index
59
// is in the range [0..n] inclusive. That is, from the first element of the
60
// container to one past the last element of the container (zero-based indices).
61
// If the container is sorted in ascending order, the returned index is the
62
// first one whose element is greater than or equal to the searched for value.
63
// If it is sorted in descending order, the returned index is the first which
64
// is less than or equal to the searched for value. That is, the returned
65
// index gives the position at which the value would be inserted (possibly
66
// either at the end, or requiring the existing values to be "pushed" to the
67
// right) maintaining the sort order. Obviously index n can only be
68
// returned if the value searched for is past the end of the array, thus
69
// has to be inserted at the end.
70
//
71
// The functions determine for themselves whether the container is sorted in
72
// ascending or descending order by comparing the first and last element.
73
// <note role=tip>
74
// While normally you want to search a container with indices in the range
75
// <src>[0 ... n-1]</src>, any desired lower bound may be used instead.
76
// </note>
77
// <note role=warning>
78
// The functions do not check if the container is valid, <i>i.e.</i> if
79
// the container is sorted and if the container does not contain duplicate
80
// values.
81
// </note>
82
//
83
// These functions loosely follow some written by Ger van Diepen in a more
84
// specialized context.
85
// </synopsis>
86
//
87
// <example>
88
// <srcblock>
89
// Vector<Int> vi;
90
// ... // Sets vi somehow
91
// genSort(vi);
92
// Int val;
93
// Bool found;
94
// while (cin >> val && val != -999) {
95
// Int where = binarySearch(found, vi, val, vi.nelements());
96
// if (found) {
97
// cout << "Found " << val << " at position " << where << endl;
98
// } else {
99
// cout << val << " is not in the vector, but it belongs at " <<
100
// where << endl;
101
// }
102
// }
103
// </srcblock>
104
// </example>
105
//
106
// <motivation>
107
// I found that I (BEG) was writing binary search functions several times,
108
// for example when checking whether the cached off and gain scans in time
109
// sorted data needed to be refilled. It generally seems like a useful little
110
// utility function.
111
// </motivation>
112
//
113
// <templating arg=Container>
114
// <li> operator(Int) or operator[Int] needs to be defined.
115
// <li> The index must be zero based.
116
// <li> The result of that indexing must be an expression that can be
117
// compared with an object of class ElType. Normally in fact it would
118
// be a temporary of class ElType.
119
// </templating>
120
// <templating arg=ElType>
121
// <li> The less than operator (<) and greater than (>) operators need to
122
// be defined, and have their usual ordering relations.
123
// </templating>
124
//
125
// <todo asof="yyyy/mm/dd">
126
// <li> I suspect that an implementation is possible that only calls
127
// operator() or [] once during each evaluation of the while loop.
128
// <li> MACROize implementation so that code isn't repeated twice. Or,
129
// possibly implement one using the other (e.g. by introducing an adapter
130
// class that turns (i) into [i].
131
// </todo>
132
133
134
// <group name=binarysearch>
135
136
// Search <i>container</i> for <i>value</i>. There are assumed to be at least
137
// <i>n</i> elements in the container. The container will be searched for
138
// indices in the range <src>[lower ... lower + n - 1]</src> Return the index
139
// of the first element which is greater than or equal to (ascending order) or
140
// less than or equal to (descending order) the value.
141
// <group>
142
// This version of the function is for containers that use () for indexing.
143
template
<
class
Container,
class
ElType>
144
Int
binarySearch(
Bool
&found,
const
Container &container,
145
const
ElType &
value
,
uInt
n,
Int
lower=0);
146
// This version of the function is for containers that use [] for indexing.
147
template
<
class
Container,
class
ElType>
148
Int
binarySearchBrackets(
Bool
&found,
const
Container &container,
149
const
ElType &
value
,
uInt
n,
Int
lower=0);
150
// </group>
151
// </group>
152
153
154
}
//# NAMESPACE CASACORE - END
155
156
#ifndef CASACORE_NO_AUTO_TEMPLATES
157
#include <casacore/casa/Utilities/BinarySearch.tcc>
158
#endif //# CASACORE_NO_AUTO_TEMPLATES
159
#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