casacore
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
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 binarySearch(Bool &found, const Container &container, const ElType &value, uInt n, Int lower=0)
Search container for value.
Int binarySearchBrackets(Bool &found, const Container &container, const ElType &value, uInt n, Int lower=0)
This version of the function is for containers that use [] for indexing.