interp1D.hpp File Reference

Contains the template class for interpolating an unidimensional-univariate function in a given point. More...

#include <algorithm>
#include <array>
#include <exception>
#include <functional>
#include <iterator>
#include <limits>
#include <type_traits>

Go to the source code of this file.

Functions
template<typename RAIterator, typename Key, typename ExtractKey, typename ExtractValue, typename CompareKey = std::less<Key>>
auto	apsc::interp1D (RAIterator const &begin, RAIterator const &end, Key const &keyVal, ExtractKey const &extractKey, ExtractValue const &extractValue, CompareKey const &comp=std::less< Key >())

Detailed Description

Contains the template class for interpolating an unidimensional-univariate function in a given point.

Author

Luca Formaggia

Note

Taken from pacs-examples, folder of repository PACS Course (https://github.com/pacs-course), Advanced Programming for Scientific Computing, Politecnico di Milano

Function Documentation

interp1D()

template<typename RAIterator, typename Key, typename ExtractKey, typename ExtractValue, typename CompareKey = std::less<Key>>

auto apsc::interp1D	(	RAIterator const &	begin,
		RAIterator const &	end,
		Key const &	keyVal,
		ExtractKey const &	extractKey,
		ExtractValue const &	extractValue,
		CompareKey const &	comp = std::less<Key>() )

A general piecewise-linear interpolator

This function is the building block for rather general piecewise-liner interpolation It requires to have a range defined by two bidirectional iterators in input. The iterators iterates over a container of a generic type from which we can extract a Key and a Value. The range must be strictly ordered with respect to the key (i.e. without repetition of elements with equivalent keys). The ordering relation must be specified as argument, together as the functors that extract the key and the value from the container, respectively. It is also assumed that usual arithmetic operations may be performed on keys and values.

If the value of the key where to interpolate falls between the interval defined by the keys in the range, piecewise-linear interpolation is performed. Otherwise, extrapolation is performed using the last or first two elements of the container, depending on the case.

The procedure followed is a binary search (bisection) on the keys.

Complexity: if the iterator is a forward iterator the complexity is log2 N, N being the size of the range. otherwise complexity is basically linear, because we need to advance iterators and this is linear on non forward iterators

Note

We recall that the range is defined by [begin, end[

Template Parameters

RAIterator	A bi-directional iterator
Key	The type of the Key
ExtractKey	The type of the functor that extracts the key form a dereferenced iterator
ExtractValue	The type of functor that extracts the value form a dereferenced iterator
CompareKey	Type of comparison operator between keys

Parameters

begin	Start of the range
end	End of the range
keyVal	The value of the key to interpolate
extractKey	The actual functor for extraction of key
extractValue	The actual functor for extraction of values
comp	The comparison operator for keys (defaulted to std::less<Key>()

Returns

the value found in correspondence of keyVal. Type is automatically deduced.

Precondition

I need to have at least two interpolation nodes.

Interpolation nodes must be distinct and sorted.

Iterators must be (at least) bidirectional.

Exceptions

a	runtime standard exception if I do not have at least 2 interpolation nodes

Todo

We can make it better if we use the new renge concepts and range based algorithms

interval found