search_vec.h
Go to the documentation of this file.
1 /*
2  -------------------------------------------------------------------
3 
4  Copyright (C) 2006-2017, Andrew W. Steiner
5 
6  This file is part of O2scl.
7 
8  O2scl is free software; you can redistribute it and/or modify
9  it under the terms of the GNU General Public License as published by
10  the Free Software Foundation; either version 3 of the License, or
11  (at your option) any later version.
12 
13  O2scl is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with O2scl. If not, see <http://www.gnu.org/licenses/>.
20 
21  -------------------------------------------------------------------
22 */
23 #ifndef O2SCL_SEARCH_VEC_H
24 #define O2SCL_SEARCH_VEC_H
25 
26 /** \file search_vec.h
27  \brief File defining \ref o2scl::search_vec and
28  \ref o2scl::search_vec_ext
29 */
30 
31 #include <iostream>
32 #include <string>
33 #include <o2scl/err_hnd.h>
34 #include <o2scl/vector.h>
35 
36 #ifndef DOXYGEN_NO_O2NS
37 namespace o2scl {
38 #endif
39 
40  /** \brief Searching class for monotonic data with caching
41 
42  A searching class for monotonic vectors. A caching system
43  similar to \c gsl_interp_accel is used.
44 
45  To find the interval containing a value, use find(). If you
46  happen to know in advance that the vector is increasing or
47  decreasing, then you can use find_inc() or find_dec() instead.
48  To ignore the caching and just use straight binary search, you
49  can use the functions in \ref vector.h .
50 
51  Alternatively, if you just want to find the index with the
52  element closest to a specified value, use ordered_lookup().
53 
54  The functions find_inc(), find_dec() and find() are designed to
55  return the lower index of an interval containing the desired
56  point, and as a result will never return the last index of a
57  vector, e.g. for a vector of size <tt>n</tt> they always return
58  a number between <tt>0</tt> and <tt>n-2</tt> inclusive. See \ref
59  o2scl::search_vec_ext for an alternative.
60 
61  \note The behavior of these functions is undefined if some of
62  the user-specified data is not finite or not strictly monotonic.
63  Two adjacent data points should not be equal. This class does
64  not verify that the user-specified data has these properties.
65 
66  \note Because results are cached, this class is not thread-safe
67  and cannot be used simultaneously by different threads. (This
68  holds even for member functions marked const, because the cache
69  data member is marked as mutable.)
70 
71  \note This class does not store a copy of the data, but only a
72  pointer to it. This means that one can safely modify the data
73  after the constructor is called, so long as one does not make
74  the vector smaller (as the cache might then point to a value
75  outside the new vector) and so long as the new vector is still
76  monotonic. Copy constructors are also private to prevent
77  confusing situations which arise when bit-copying pointers.
78  */
79  template<class vec_t> class search_vec {
80 
81 #ifndef DOXYGEN_INTERNAL
82 
83  protected:
84 
85  /** \brief Storage for the most recent index
86 
87  \note This is marked mutable to ensure const-correctness is
88  straightforward.
89  */
90  mutable size_t cache;
91 
92  /// The vector to be searched
93  const vec_t *v;
94 
95  /// The vector size
96  size_t n;
97 
98 #endif
99 
100  public:
101 
102  /** \brief Create a blank searching object
103  */
104  search_vec() : v(0), n(0) {
105  }
106 
107  /** \brief Create a searching object with vector \c x of size \c nn
108  */
109  search_vec(size_t nn, const vec_t &x) : v(&x), n(nn) {
110  if (nn<2) {
111  std::string str=((std::string)"Vector too small (size=")+
112  o2scl::szttos(nn)+") in search_vec::search_vec().";
113  O2SCL_ERR(str.c_str(),exc_einval);
114  }
115  cache=0;
116  }
117 
118  /** \brief Set the vector to be searched
119  */
120  void set_vec(size_t nn, const vec_t &x) {
121  if (nn<2) {
122  std::string str=((std::string)"Vector too small (size=")+
123  o2scl::szttos(nn)+") in search_vec::set_vec().";
124  O2SCL_ERR(str.c_str(),exc_einval);
125  }
126  cache=0;
127  v=&x;
128  n=nn;
129  }
130 
131  /** \brief Search an increasing or decreasing vector for the
132  interval containing <tt>x0</tt>
133 
134  This function is identical to find_inc() if the data is
135  increasing, and find_dec() if the data is decreasing.
136  */
137  size_t find(const double x0) const {
138 #if !O2SCL_NO_RANGE_CHECK
139  if (cache>=n) {
140  O2SCL_ERR("Cache mis-alignment in search_vec::find().",
141  exc_esanity);
142  }
143 #endif
144  if ((*v)[0]<(*v)[n-1]) return find_inc(x0);
145  return find_dec(x0);
146  }
147 
148  /** \brief Search an increasing vector for the interval
149  containing <tt>x0</tt>
150 
151  This function is a cached version of \ref vector_bsearch_inc()
152  , analogous to <tt>gsl_interp_accel_find()</tt>, except
153  that it does not internally record cache hits and
154  misses.
155 
156  */
157  size_t find_inc(const double x0) const {
158  if (x0<(*v)[cache]) {
159  cache=vector_bsearch_inc<vec_t,double>(x0,*v,0,cache);
160  } else if (x0>=(*v)[cache+1]) {
161  cache=vector_bsearch_inc<vec_t,double>(x0,*v,cache,n-1);
162  }
163 #if !O2SCL_NO_RANGE_CHECK
164  if (cache>=n) {
165  O2SCL_ERR("Cache mis-alignment in search_vec::find_inc().",
166  exc_esanity);
167  }
168 #endif
169  return cache;
170  }
171 
172  /** \brief Search a decreasing vector for the interval
173  containing <tt>x0</tt>
174 
175  This function is a cached version of \ref vector_bsearch_dec()
176  . The operation of this function is undefined if the data is
177  not strictly monotonic, i.e. if some of the data elements are
178  equal.
179  */
180  size_t find_dec(const double x0) const {
181  if (x0>(*v)[cache]) {
182  cache=vector_bsearch_dec<vec_t,double>(x0,*v,0,cache);
183  } else if (x0<=(*v)[cache+1]) {
184  cache=vector_bsearch_dec<vec_t,double>(x0,*v,cache,n-1);
185  }
186 #if !O2SCL_NO_RANGE_CHECK
187  if (cache>=n) {
188  O2SCL_ERR("Cache mis-alignment in search_vec::find_dec().",
189  exc_esanity);
190  }
191 #endif
192  return cache;
193  }
194 
195  /** \brief Find the index of x0 in the ordered array \c x
196 
197  This returns the index i for which x[i] is as close as
198  possible to x0 if x[i] is either increasing or decreasing.
199 
200  If you have a non-monotonic vector, you can use \ref
201  vector_lookup() instead.
202 
203  Generally, if there are two adjacent entries with the same
204  value, this function will return the entry with the smaller
205  index.
206 
207  \future This function just uses the <tt>find</tt> functions
208  and then adjusts the answer at the end if necessary. It might
209  be possible to improve the speed by rewriting this from
210  scratch.
211  */
212  size_t ordered_lookup(const double x0) const {
213  if (n<1) {
214  std::string str=((std::string)"Not enough data (n=")+
215  o2scl::szttos(n)+") in search_vec::ordered_lookup().";
216  O2SCL_ERR(str.c_str(),exc_einval);
217  }
218 
219  size_t row;
220 
221  if ((*v)[0]<=(*v)[n-1]) {
222 
223  // Increasing case
224 
225  if (x0>=(*v)[n-1]) {
226  row=n-1;
227  } else {
228  row=find_inc(x0);
229  if (row<n-1 && fabs((*v)[row+1]-x0)<fabs((*v)[row]-x0)) row++;
230  }
231 
232  } else {
233 
234  // Decreasing case
235 
236  if (x0<=(*v)[n-1]) {
237  row=n-1;
238  } else {
239  row=find_dec(x0);
240  if (row<n-1 && fabs((*v)[row+1]-x0)<fabs((*v)[row]-x0)) row++;
241  }
242  }
243 
244  return row;
245  }
246 
247 #ifndef DOXYGEN_INTERNAL
248 
249  private:
250 
252  search_vec<vec_t>& operator=(const search_vec<vec_t>&);
253 
254 #endif
255 
256  };
257 
258  /** \brief An extended search_vec which is allowed to return
259  the last element
260  */
261  template<class vec_t> class search_vec_ext {
262 
263 #ifndef DOXYGEN_INTERNAL
264 
265  protected:
266 
267  /** \brief Storage for the most recent index
268 
269  \note This is marked mutable to ensure const-correctness is
270  straightforward.
271  */
272  mutable size_t cache;
273 
274  /// The vector to be searched
275  const vec_t *v;
276 
277  /// The vector size
278  size_t n;
279 
280 #endif
281 
282  public:
283 
284  /** \brief Create a blank searching object
285  */
286  search_vec_ext() : v(0), n(0) {
287  }
288 
289  /** \brief Create a searching object for vector \c x of size
290  \c nn
291 
292  \comment
293  Note that this constructor does not call the parent
294  constructor because that requires nn<2 while this
295  class really only requires nn<1.
296  \endcomment
297 
298  \future Ensure this is fully tested for vectors with
299  only one element.
300  */
301  search_vec_ext(size_t nn, const vec_t &x) : v(&x), n(nn) {
302  if (nn<1) {
303  std::string str=((std::string)"Vector too small (n=")+
304  o2scl::szttos(nn)+") in search_vec_ext::search_vec_ext().";
305  O2SCL_ERR(str.c_str(),exc_einval);
306  }
307  cache=0;
308  }
309 
310  /** \brief Search an increasing or decreasing vector for the interval
311  containing <tt>x0</tt>
312  */
313  size_t find(const double x0) const {
314 #if !O2SCL_NO_RANGE_CHECK
315  if (this->cache>=this->n) {
316  O2SCL_ERR("Cache mis-alignment in search_vec_ext::find().",
317  exc_esanity);
318  }
319 #endif
320  if ((*this->v)[0]<(*this->v)[this->n-1]) return find_inc(x0);
321  return find_dec(x0);
322  }
323 
324  /** \brief Search an increasing vector for the interval
325  containing <tt>x0</tt>
326  */
327  size_t find_inc(const double x0) const {
328  if (x0<(*this->v)[this->cache]) {
329  this->cache=vector_bsearch_inc<vec_t,double>
330  (x0,*this->v,0,this->cache);
331  } else if (this->cache<this->n-1 && x0>=(*this->v)[this->cache+1]) {
332  this->cache=vector_bsearch_inc<vec_t,double>
333  (x0,*this->v,this->cache,this->n);
334  }
335 #if !O2SCL_NO_RANGE_CHECK
336  if (this->cache>=this->n) {
337  O2SCL_ERR("Cache mis-alignment in search_vec_ext::find_inc().",
338  exc_esanity);
339  }
340 #endif
341  return this->cache;
342  }
343 
344  /** \brief Search a decreasing vector for the interval
345  containing <tt>x0</tt>
346  */
347  size_t find_dec(const double x0) const {
348  if (x0>(*this->v)[this->cache]) {
349  this->cache=vector_bsearch_dec<vec_t,double>
350  (x0,*this->v,0,this->cache);
351  } else if (this->cache<this->n-1 && x0<=(*this->v)[this->cache+1]) {
352  this->cache=vector_bsearch_dec<vec_t,double>
353  (x0,*this->v,this->cache,this->n);
354  }
355 #if !O2SCL_NO_RANGE_CHECK
356  if (this->cache>=this->n) {
357  O2SCL_ERR("Cache mis-alignment in search_vec_ext::find_dec().",
358  exc_esanity);
359  }
360 #endif
361  return this->cache;
362  }
363 
364 #ifndef DOXYGEN_INTERNAL
365 
366  private:
367 
369  search_vec_ext<vec_t>& operator=(const search_vec_ext<vec_t>&);
370 
371 #endif
372 
373  };
374 
375 #ifndef DOXYGEN_NO_O2NS
376 }
377 #endif
378 
379 #endif
size_t cache
Storage for the most recent index.
Definition: search_vec.h:90
The main O<span style=&#39;position: relative; top: 0.3em; font-size: 0.8em&#39;>2</span>scl O$_2$scl names...
Definition: anneal.h:42
size_t n
The vector size.
Definition: search_vec.h:278
size_t n
The vector size.
Definition: search_vec.h:96
sanity check failed - shouldn&#39;t happen
Definition: err_hnd.h:65
invalid argument supplied by user
Definition: err_hnd.h:59
search_vec_ext()
Create a blank searching object.
Definition: search_vec.h:286
size_t cache
Storage for the most recent index.
Definition: search_vec.h:272
size_t find_inc(const double x0) const
Search an increasing vector for the interval containing x0
Definition: search_vec.h:327
search_vec()
Create a blank searching object.
Definition: search_vec.h:104
search_vec(size_t nn, const vec_t &x)
Create a searching object with vector x of size nn.
Definition: search_vec.h:109
size_t find(const double x0) const
Search an increasing or decreasing vector for the interval containing x0
Definition: search_vec.h:137
const vec_t * v
The vector to be searched.
Definition: search_vec.h:93
size_t find_dec(const double x0) const
Search a decreasing vector for the interval containing x0
Definition: search_vec.h:347
size_t find(const double x0) const
Search an increasing or decreasing vector for the interval containing x0
Definition: search_vec.h:313
#define O2SCL_ERR(d, n)
Set an error with message d and code n.
Definition: err_hnd.h:273
size_t ordered_lookup(const double x0) const
Find the index of x0 in the ordered array x.
Definition: search_vec.h:212
size_t find_dec(const double x0) const
Search a decreasing vector for the interval containing x0
Definition: search_vec.h:180
size_t find_inc(const double x0) const
Search an increasing vector for the interval containing x0
Definition: search_vec.h:157
Searching class for monotonic data with caching.
Definition: search_vec.h:79
An extended search_vec which is allowed to return the last element.
Definition: search_vec.h:261
void set_vec(size_t nn, const vec_t &x)
Set the vector to be searched.
Definition: search_vec.h:120
search_vec_ext(size_t nn, const vec_t &x)
Create a searching object for vector x of size nn.
Definition: search_vec.h:301
const vec_t * v
The vector to be searched.
Definition: search_vec.h:275
std::string szttos(size_t x)
Convert a size_t to a string.

Documentation generated with Doxygen. Provided under the GNU Free Documentation License (see License Information).