Searching class for monotonic data with caching. More...
#include <search_vec.h>
A searching class for monotonic vectors. A caching system similar to gsl_interp_accel
is used.
To find the interval containing a value, use find(). If you happen to know in advance that the vector is increasing or decreasing, then you can use find_inc() or find_dec() instead. To ignore the caching and just use straight binary search, you can use the functions in vector.h .
Alternatively, if you just want to find the index with the element closest to a specified value, use ordered_lookup().
The functions find_inc(), find_dec() and find() are designed to return the lower index of an interval containing the desired point, and as a result will never return the last index of a vector, e.g. for a vector of size n
they always return a number between 0
and n-2
inclusive. See o2scl::search_vec_ext for an alternative.
Definition at line 74 of file search_vec.h.
Public Member Functions | |
search_vec () | |
Create a blank searching object. | |
search_vec (size_t nn, const vec_t &x) | |
Create a searching object with vector x of size nn . | |
void | set_vec (size_t nn, const vec_t &x) |
Set the vector to be searched. | |
size_t | find (const double x0) |
Search an increasing or decreasing vector for the interval containing x0 More... | |
size_t | find_const (const double x0, size_t &cache) const |
size_t | find_inc (const double x0) |
Search an increasing vector for the interval containing x0 More... | |
size_t | find_inc_const (const double x0, size_t &cache) const |
size_t | find_dec (const double x0) |
Search a decreasing vector for the interval containing x0 More... | |
size_t | find_dec_const (const double x0, size_t &cache) const |
size_t | ordered_lookup (const double x0) const |
Find the index of x0 in the ordered array x . More... | |
Protected Attributes | |
const vec_t * | v |
The vector to be searched. | |
size_t | n |
The vector size. | |
Private Member Functions | |
search_vec (const search_vec< vec_t > &) | |
search_vec< vec_t > & | operator= (const search_vec< vec_t > &) |
|
inline |
This function is identical to find_inc() if the data is increasing, and find_dec() if the data is decreasing.
Definition at line 123 of file search_vec.h.
|
inline |
This function is a cached version of vector_bsearch_dec() . The operation of this function is undefined if the data is not strictly monotonic, i.e. if some of the data elements are equal.
Definition at line 194 of file search_vec.h.
|
inline |
This function is a cached version of vector_bsearch_inc() , analogous to gsl_interp_accel_find()
, except that it does not internally record cache hits and misses.
Definition at line 155 of file search_vec.h.
|
inline |
This returns the index i for which x[i] is as close as possible to x0 if x[i] is either increasing or decreasing.
If you have a non-monotonic vector, you can use vector_lookup() instead.
Generally, if there are two adjacent entries with the same value, this function will return the entry with the smaller index.
find
functions and then adjusts the answer at the end if necessary. It might be possible to improve the speed by rewriting this from scratch. Definition at line 242 of file search_vec.h.
Documentation generated with Doxygen. Provided under the
GNU Free Documentation License (see License Information).