search_vec.h
Go to the documentation of this file.
1 /*
2  -------------------------------------------------------------------
3 
4  Copyright (C) 2006-2018, 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 This class does not store a copy of the data, but only a
67  pointer to it. This means that one can safely modify the data
68  after the constructor is called, so long as one does not make
69  the vector smaller (as the cache might then point to a value
70  outside the new vector) and so long as the new vector is still
71  monotonic. Copy constructors are also private to prevent
72  confusing situations which arise when bit-copying pointers.
73  */
74  template<class vec_t> class search_vec {
75 
76 #ifndef DOXYGEN_INTERNAL
77 
78  protected:
79 
80  /// The vector to be searched
81  const vec_t *v;
82 
83  /// The vector size
84  size_t n;
85 
86 #endif
87 
88  public:
89 
90  /** \brief Create a blank searching object
91  */
92  search_vec() : v(0), n(0) {
93  }
94 
95  /** \brief Create a searching object with vector \c x of size \c nn
96  */
97  search_vec(size_t nn, const vec_t &x) : v(&x), n(nn) {
98  if (nn<2) {
99  std::string str=((std::string)"Vector too small (size=")+
100  o2scl::szttos(nn)+") in search_vec::search_vec().";
101  O2SCL_ERR(str.c_str(),exc_einval);
102  }
103  }
104 
105  /** \brief Set the vector to be searched
106  */
107  void set_vec(size_t nn, const vec_t &x) {
108  if (nn<2) {
109  std::string str=((std::string)"Vector too small (size=")+
110  o2scl::szttos(nn)+") in search_vec::set_vec().";
111  O2SCL_ERR(str.c_str(),exc_einval);
112  }
113  v=&x;
114  n=nn;
115  }
116 
117  /** \brief Search an increasing or decreasing vector for the
118  interval containing <tt>x0</tt>
119 
120  This function is identical to find_inc() if the data is
121  increasing, and find_dec() if the data is decreasing.
122  */
123  size_t find(const double x0) {
124  size_t cache=n/2;
125 #if !O2SCL_NO_RANGE_CHECK
126  if (cache>=n) {
127  O2SCL_ERR("Cache mis-alignment in search_vec::find().",
128  exc_esanity);
129  }
130 #endif
131  if ((*v)[0]<(*v)[n-1]) return find_inc(x0);
132  return find_dec(x0);
133  }
134 
135  size_t find_const(const double x0, size_t &cache) const {
136 #if !O2SCL_NO_RANGE_CHECK
137  if (cache>=n) {
138  O2SCL_ERR("Cache mis-alignment in search_vec::find().",
139  exc_esanity);
140  }
141 #endif
142  if ((*v)[0]<(*v)[n-1]) return find_inc_const(x0,cache);
143  return find_dec_const(x0,cache);
144  }
145 
146  /** \brief Search an increasing vector for the interval
147  containing <tt>x0</tt>
148 
149  This function is a cached version of \ref vector_bsearch_inc()
150  , analogous to <tt>gsl_interp_accel_find()</tt>, except
151  that it does not internally record cache hits and
152  misses.
153 
154  */
155  size_t find_inc(const double x0) {
156  size_t cache=n/2;
157  if (x0<(*v)[cache]) {
158  cache=vector_bsearch_inc<vec_t,double>(x0,*v,0,cache);
159  } else if (x0>=(*v)[cache+1]) {
160  cache=vector_bsearch_inc<vec_t,double>(x0,*v,cache,n-1);
161  }
162 #if !O2SCL_NO_RANGE_CHECK
163  if (cache>=n) {
164  O2SCL_ERR("Cache mis-alignment in search_vec::find_inc().",
165  exc_esanity);
166  }
167 #endif
168  return cache;
169  }
170 
171  size_t find_inc_const(const double x0, size_t &cache) const {
172  if (x0<(*v)[cache]) {
173  cache=vector_bsearch_inc<vec_t,double>(x0,*v,0,cache);
174  } else if (x0>=(*v)[cache+1]) {
175  cache=vector_bsearch_inc<vec_t,double>(x0,*v,cache,n-1);
176  }
177 #if !O2SCL_NO_RANGE_CHECK
178  if (cache>=n) {
179  O2SCL_ERR("Cache mis-alignment in search_vec::find_inc().",
180  exc_esanity);
181  }
182 #endif
183  return cache;
184  }
185 
186  /** \brief Search a decreasing vector for the interval
187  containing <tt>x0</tt>
188 
189  This function is a cached version of \ref vector_bsearch_dec()
190  . The operation of this function is undefined if the data is
191  not strictly monotonic, i.e. if some of the data elements are
192  equal.
193  */
194  size_t find_dec(const double x0) {
195  size_t cache=n/2;
196  if (x0>(*v)[cache]) {
197  cache=vector_bsearch_dec<vec_t,double>(x0,*v,0,cache);
198  } else if (x0<=(*v)[cache+1]) {
199  cache=vector_bsearch_dec<vec_t,double>(x0,*v,cache,n-1);
200  }
201 #if !O2SCL_NO_RANGE_CHECK
202  if (cache>=n) {
203  O2SCL_ERR("Cache mis-alignment in search_vec::find_dec().",
204  exc_esanity);
205  }
206 #endif
207  return cache;
208  }
209 
210  size_t find_dec_const(const double x0, size_t &cache) const {
211  if (x0>(*v)[cache]) {
212  cache=vector_bsearch_dec<vec_t,double>(x0,*v,0,cache);
213  } else if (x0<=(*v)[cache+1]) {
214  cache=vector_bsearch_dec<vec_t,double>(x0,*v,cache,n-1);
215  }
216 #if !O2SCL_NO_RANGE_CHECK
217  if (cache>=n) {
218  O2SCL_ERR("Cache mis-alignment in search_vec::find_dec().",
219  exc_esanity);
220  }
221 #endif
222  return cache;
223  }
224 
225  /** \brief Find the index of x0 in the ordered array \c x
226 
227  This returns the index i for which x[i] is as close as
228  possible to x0 if x[i] is either increasing or decreasing.
229 
230  If you have a non-monotonic vector, you can use \ref
231  vector_lookup() instead.
232 
233  Generally, if there are two adjacent entries with the same
234  value, this function will return the entry with the smaller
235  index.
236 
237  \future This function just uses the <tt>find</tt> functions
238  and then adjusts the answer at the end if necessary. It might
239  be possible to improve the speed by rewriting this from
240  scratch.
241  */
242  size_t ordered_lookup(const double x0) const {
243  if (n<1) {
244  std::string str=((std::string)"Not enough data (n=")+
245  o2scl::szttos(n)+") in search_vec::ordered_lookup().";
246  O2SCL_ERR(str.c_str(),exc_einval);
247  }
248 
249  size_t row;
250 
251  if ((*v)[0]<=(*v)[n-1]) {
252 
253  // Increasing case
254 
255  if (x0>=(*v)[n-1]) {
256  row=n-1;
257  } else {
258  size_t cache=0;
259  row=find_inc_const(x0,cache);
260  if (row<n-1 && fabs((*v)[row+1]-x0)<fabs((*v)[row]-x0)) row++;
261  }
262 
263  } else {
264 
265  // Decreasing case
266 
267  if (x0<=(*v)[n-1]) {
268  row=n-1;
269  } else {
270  size_t cache=0;
271  row=find_dec_const(x0,cache);
272  if (row<n-1 && fabs((*v)[row+1]-x0)<fabs((*v)[row]-x0)) row++;
273  }
274  }
275 
276  return row;
277  }
278 
279 #ifndef DOXYGEN_INTERNAL
280 
281  private:
282 
284  search_vec<vec_t>& operator=(const search_vec<vec_t>&);
285 
286 #endif
287 
288  };
289 
290  /** \brief An extended search_vec which is allowed to return
291  the last element
292  */
293  template<class vec_t> class search_vec_ext {
294 
295 #ifndef DOXYGEN_INTERNAL
296 
297  protected:
298 
299  /** \brief Storage for the most recent index
300  */
301  size_t cache;
302 
303  /// The vector to be searched
304  const vec_t *v;
305 
306  /// The vector size
307  size_t n;
308 
309 #endif
310 
311  public:
312 
313  /** \brief Create a blank searching object
314  */
315  search_vec_ext() : v(0), n(0) {
316  }
317 
318  /** \brief Create a searching object for vector \c x of size
319  \c nn
320 
321  \comment
322  Note that this constructor does not call the parent
323  constructor because that requires nn<2 while this
324  class really only requires nn<1.
325  \endcomment
326 
327  \future Ensure this is fully tested for vectors with
328  only one element.
329  */
330  search_vec_ext(size_t nn, const vec_t &x) : v(&x), n(nn) {
331  if (nn<1) {
332  std::string str=((std::string)"Vector too small (n=")+
333  o2scl::szttos(nn)+") in search_vec_ext::search_vec_ext().";
334  O2SCL_ERR(str.c_str(),exc_einval);
335  }
336  }
337 
338  /** \brief Search an increasing or decreasing vector for the interval
339  containing <tt>x0</tt>
340  */
341  size_t find(const double x0) {
342 #if !O2SCL_NO_RANGE_CHECK
343  if (this->cache>=this->n) {
344  O2SCL_ERR("Cache mis-alignment in search_vec_ext::find().",
345  exc_esanity);
346  }
347 #endif
348  if ((*this->v)[0]<(*this->v)[this->n-1]) return find_inc(x0);
349  return find_dec(x0);
350  }
351 
352  /** \brief Search an increasing vector for the interval
353  containing <tt>x0</tt>
354  */
355  size_t find_inc(const double x0) {
356  if (x0<(*this->v)[this->cache]) {
357  this->cache=vector_bsearch_inc<vec_t,double>
358  (x0,*this->v,0,this->cache);
359  } else if (this->cache<this->n-1 && x0>=(*this->v)[this->cache+1]) {
360  this->cache=vector_bsearch_inc<vec_t,double>
361  (x0,*this->v,this->cache,this->n);
362  }
363 #if !O2SCL_NO_RANGE_CHECK
364  if (this->cache>=this->n) {
365  O2SCL_ERR("Cache mis-alignment in search_vec_ext::find_inc().",
366  exc_esanity);
367  }
368 #endif
369  return this->cache;
370  }
371 
372  /** \brief Search a decreasing vector for the interval
373  containing <tt>x0</tt>
374  */
375  size_t find_dec(const double x0) {
376  if (x0>(*this->v)[this->cache]) {
377  this->cache=vector_bsearch_dec<vec_t,double>
378  (x0,*this->v,0,this->cache);
379  } else if (this->cache<this->n-1 && x0<=(*this->v)[this->cache+1]) {
380  this->cache=vector_bsearch_dec<vec_t,double>
381  (x0,*this->v,this->cache,this->n);
382  }
383 #if !O2SCL_NO_RANGE_CHECK
384  if (this->cache>=this->n) {
385  O2SCL_ERR("Cache mis-alignment in search_vec_ext::find_dec().",
386  exc_esanity);
387  }
388 #endif
389  return this->cache;
390  }
391 
392 #ifndef DOXYGEN_INTERNAL
393 
394  private:
395 
397  search_vec_ext<vec_t>& operator=(const search_vec_ext<vec_t>&);
398 
399 #endif
400 
401  };
402 
403 #ifndef DOXYGEN_NO_O2NS
404 }
405 #endif
406 
407 #endif
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:307
size_t n
The vector size.
Definition: search_vec.h:84
size_t find_inc(const double x0)
Search an increasing vector for the interval containing x0
Definition: search_vec.h:155
size_t find(const double x0)
Search an increasing or decreasing vector for the interval containing x0
Definition: search_vec.h:123
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:315
size_t cache
Storage for the most recent index.
Definition: search_vec.h:301
search_vec()
Create a blank searching object.
Definition: search_vec.h:92
search_vec(size_t nn, const vec_t &x)
Create a searching object with vector x of size nn.
Definition: search_vec.h:97
const vec_t * v
The vector to be searched.
Definition: search_vec.h:81
size_t find_inc(const double x0)
Search an increasing vector for the interval containing x0
Definition: search_vec.h:355
#define O2SCL_ERR(d, n)
Set an error with message d and code n.
Definition: err_hnd.h:273
size_t find(const double x0)
Search an increasing or decreasing vector for the interval containing x0
Definition: search_vec.h:341
size_t find_dec(const double x0)
Search a decreasing vector for the interval containing x0
Definition: search_vec.h:194
size_t ordered_lookup(const double x0) const
Find the index of x0 in the ordered array x.
Definition: search_vec.h:242
Searching class for monotonic data with caching.
Definition: search_vec.h:74
An extended search_vec which is allowed to return the last element.
Definition: search_vec.h:293
size_t find_dec(const double x0)
Search a decreasing vector for the interval containing x0
Definition: search_vec.h:375
void set_vec(size_t nn, const vec_t &x)
Set the vector to be searched.
Definition: search_vec.h:107
search_vec_ext(size_t nn, const vec_t &x)
Create a searching object for vector x of size nn.
Definition: search_vec.h:330
const vec_t * v
The vector to be searched.
Definition: search_vec.h:304
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).