spline< X, Y, D > Class Template Reference

A spline is an approximation to a single valued function of one variable. The function is approximated by first defining a specific set of sample values. Other data points of the function are interpolated given the defined set. That is, you can approximate data points that don't really exist using one the interpolate_* methods or the function call operator. See below. More...

#include <spline.h>

Collaboration diagram for spline< X, Y, D >:
Collaboration graph
[legend]

List of all members.

Classes

struct  info
 info stored for each x value in the sample data set More...

Public Types

typedef samples_t::const_iterator const_iterator
 const_iterator
typedef D Dt
 alias for template parm
typedef Y(spline::* interpolator_t )(X const &) const
typedef samples_t::iterator iterator
 iterator
typedef samples_t::value_type sample_t
 Elements stored.
typedef std::multimap< X, infosamples_t
 Primary storage.
typedef spline< X, Y, D > self
 interpolator_t lets you pass the interpolator function as a pointer.
typedef X Xt
 alias for template parm
typedef Y Yt
 alias for template parm

Public Member Functions

void add_sample (sample_t const &p)
 Add a new sampled data point. If there is an existing sample with the same X value, the Y for that sample will be replaced.
void add_sample (X const &x, Y const &y)
 Add a new sampled data point. If there is an existing sample with the same X value, the Y for that sample will be replaced. This overload lets you specify the without first constructing a sample_t.
template<class Operation >
void apply (Operation const &)
 Modifies the extant samples by visiting each one and replacing the the Y in the sample with the return value from the operation. The operation must take a sample_t as a parameter.
sample_t back () const
 Returns the last sample or an undefined value if there are none.
const_iterator begin () const
const_iterator ceil (X const &x) const
template<class Other , class Operation >
void combine (spline< X, Y, D > &output, Other const &rhs, Operation const &op)
 Produce output by combining this with rhs according to op on a point by point basis. All sampled data points in both splines are considered. The operation is applied to each pair of points existing in either spline. Points missing in one are interpolated so as to be able to combine them with the other to produce the output.
template<class Other , class Operation >
void combine (self &output, Other const &rhs, Operation const &op)
void compute_coefficients ()
 Compute the second derivative of the interpolation functions and store them in the s_ member of the info associated with every x/y pair.
void domain (std::set< X > *target) const
 get all interesting Xs
const_iterator end () const
template<class OutputIterator >
void evaluate (X start_x, X delta_x, OutputIterator begin, OutputIterator end) const
 Create a collection of interpolated values. Output those values through an iterator that points to a pair<X,Y> where X, and Y are assignment compatible with double. The begin,end variables define the standard output iterator range logic. The first value output will be (start_x, f(start_x)), the second will be (start_x+delta_x, f(start_x+delta_x)), and so forth.
const_iterator floor (X const &x) const
 Returns the iterator to the sample whose X component is as high as possible but <= x. Returns end() if no such sample exists. Consider the sequence:
sample_t front () const
 Returns the first sample or an undefined value if there are none.
template<class SF >
void include (SF const &rhs)
 Ensures that all samples in rhs also appear in this sampled function. Samples in rhs superceed samples already in the spline. rhs can be of a different type of data structure but the structure's iterator must point to pairs whose First and Second types are compatible with X and Y.
template<class Iterator >
void include (Iterator, Iterator)
 Ensures that all samples in iterator range also appear in this sampled function. Samples in the range l-g replace samples already spline.
interpolate_cubic (X const &) const
interpolate_line (X const &) const
 This method interpolates the value of the sampled function at 'x', returning the corresponding y. See comments in it for a description of how the interpolation works, but generally, this function treats the sampled function as a piecewise linear function, like this:
interpolate_step (X const &) const
 This method interpolates the value of the sampled function at 'x', returning the corresponding y. See comments in it for a description of how the interpolation works, but generally, this function treats the sampled function as a step wise constant function that looks like this:
interpolator_t interpolator () const
 gets the current interpolator
operator() (X location) const
template<class T >
selfoperator*= (T const &rhs)
 Add another spline to this one. Make sure that all samples in both splines are addressed.
template<class T >
selfoperator+= (T const &rhs)
 Add another spline to this one. Make sure that all samples in both splines are addressed.
template<class T >
selfoperator-= (T const &rhs)
 Add another spline to this one. Make sure that all samples in both splines are addressed.
template<class T >
selfoperator/= (T const &rhs)
 Add another spline to this one. Make sure that all samples in both splines are addressed.
selfoperator= (self const &rhs)
void set_interpolator (interpolator_t t)
size_t size () const
template<class OtherKind >
 spline (OtherKind const &rhs, typename spline< X, Y, D >::interpolator_t terp)
template<class SampleIterator >
 spline (SampleIterator first, SampleIterator last, typename spline< X, Y, D >::interpolator_t t)
template<class OtherKind >
 spline (OtherKind const &rhs, interpolator_t terp)
template<class SampleIterator >
 spline (SampleIterator first, SampleIterator last, interpolator_t t)
 spline (self const &rhs)
 spline (interpolator_t a)
 spline ()
void swap (self &rhs)
 Quickly swap the contents of this spline with that of another. This occaisionally useful when writing algorithms that construct objects and then destruct them. You can arrange to have an empty object destructed quickly while your constructed object gets filled without a copy. This of course requires thought.

Private Attributes

bool dirty_
 cubic spline s's need recalculation
interpolator_t interpolator_
 Current interpolator.
samples_t samples_
 Map of actual data.

Detailed Description

template<class X, class Y, class D = double>
class cxxtls::spline< X, Y, D >

A spline is an approximation to a single valued function of one variable. The function is approximated by first defining a specific set of sample values. Other data points of the function are interpolated given the defined set. That is, you can approximate data points that don't really exist using one the interpolate_* methods or the function call operator. See below.

The following interpolators exist:

You can select which one this is using the constructor or using the set_interpolator() method. You can also call any desired interpolator directly without using set_interpolator().

A 'sample' is a pair<X,Y>. For a given X, only one Y can be used. X means 'independent variable' and Y means 'dependent variable'. That is, X is the domain of a two dimensional graph point. Y is the range.

The template parameter, D, lets you specify the data type to use when doing multiplications and divisions and repeated operations. Normally, your X and Y will be one of: int, float, double, short, etc. Using double as the default high resolution numeric data type works fine for them. It isn't used much anyway. However, if you supply your own user defined classes for X or Y, you may need to supply your own D class as well. Of course, you may not need to, but the feature is there if you need it.

Interpolation is the act of guessing at values of the Y for values of the X for which no specific data points are provided. The following interpolation schemes are provided:

          Numerical Computing by Shampine and Allen.  Copyright 1973.
          ISBN 0-7216-8150-6.

The function all operator is provided so that you can easily use the spline to access dependent variable values:

       spline<int,int> s;
  
       s.add_sample(99, 13);
       s.add_sample(101, 20);
  
       X x = 100;
       Y y = s(x);

y is now somewhere between 13 and twenty, given the current interpolator.

Only one sample with a given X value will be kept. If you add a new sample at an old location, the old one will be replaced.

Samples are stored in order, sorted by X.

Use method 'domain()' to get a list of all Xs found in samples in this function.

You can use the apply method to apply an operation to all the actual sample data points. This lets you change them if you like.

Note that the primary sampled storage class allows multiple samples of the same X but the add_sample method won't. The multimap class is used instead of map because multimap supports the upperbound method which can be used to quick find a location with the multimap NEAR a given value of the X. This avoids costly linear searches when interpolating

The 'include' method lets add multiple samples in one operation -- there a couple of variations.

The operators, +=, -=, *=, and /= let you include combine two splines by interpolating this spline and another spline over all datapoints of interest to either spline, and producing a new spline. The interpolation involved in these operator functions is the 'current' interpolator set using set_interpolator() or as a parameter to the constructor.

Comments about the spline members can be found in the bodies thereof which begin immediately after the class definition.

Definition at line 55 of file spline.h.


Member Typedef Documentation

const_iterator

Definition at line 192 of file spline.h.

typedef D Dt

alias for template parm

Definition at line 169 of file spline.h.

typedef Y(spline::* interpolator_t)(X const &) const

Definition at line 195 of file spline.h.

iterator

Definition at line 191 of file spline.h.

typedef samples_t::value_type sample_t

Elements stored.

Definition at line 189 of file spline.h.

typedef std::multimap<X,info> samples_t

Primary storage.

Definition at line 188 of file spline.h.

typedef spline<X,Y,D> self

interpolator_t lets you pass the interpolator function as a pointer.

Definition at line 199 of file spline.h.

typedef X Xt

alias for template parm

Definition at line 167 of file spline.h.

typedef Y Yt

alias for template parm

Definition at line 168 of file spline.h.


Constructor & Destructor Documentation

spline (  ) 

Default constructor gives you the default interpolator (stepwise). Creates an empty spline. Use add_sample to fill it. You can of course use any interpolator by calling it directly, or you can use set_interpolator to select a different one as the current interpolator.

Definition at line 318 of file spline.h.

spline ( interpolator_t  a  ) 

Constructor that lets you specify the interpolator algorithm.

Definition at line 333 of file spline.h.

spline ( self const &  rhs  ) 

Copy constructor.

Definition at line 344 of file spline.h.

Here is the call graph for this function:

spline ( SampleIterator  first,
SampleIterator  last,
interpolator_t  t 
)
spline ( OtherKind const &  rhs,
interpolator_t  terp 
)
spline ( SampleIterator  first,
SampleIterator  last,
typename spline< X, Y, D >::interpolator_t  t 
)

Construct a spline from a pair of iterators to objects that look like samples. That is, a range of pair<someXtype, someYtype>. You must also specify the desired interpolator.

Definition at line 357 of file spline.h.

Here is the call graph for this function:

spline ( OtherKind const &  rhs,
typename spline< X, Y, D >::interpolator_t  terp 
)

Copy an extant interpolator's data. You can specify a new interpolator.

Definition at line 378 of file spline.h.

Here is the call graph for this function:


Member Function Documentation

void add_sample ( sample_t const &  p  ) 

Add a new sampled data point. If there is an existing sample with the same X value, the Y for that sample will be replaced.

Definition at line 471 of file spline.h.

void add_sample ( X const &  x,
Y const &  y 
)

Add a new sampled data point. If there is an existing sample with the same X value, the Y for that sample will be replaced. This overload lets you specify the without first constructing a sample_t.

Definition at line 458 of file spline.h.

Here is the caller graph for this function:

void apply ( Operation const &  op  ) 

Modifies the extant samples by visiting each one and replacing the the Y in the sample with the return value from the operation. The operation must take a sample_t as a parameter.

Definition at line 820 of file spline.h.

Here is the caller graph for this function:

spline< X, Y, D >::sample_t back (  )  const

Returns the last sample or an undefined value if there are none.

Definition at line 610 of file spline.h.

Here is the call graph for this function:

Here is the caller graph for this function:

spline< X, Y, D >::const_iterator begin (  )  const

Definition at line 299 of file spline.h.

Here is the caller graph for this function:

const_iterator ceil ( X const &  x  )  const

Here is the caller graph for this function:

void combine ( spline< X, Y, D > &  output,
Other const &  rhs,
Operation const &  op 
)

Produce output by combining this with rhs according to op on a point by point basis. All sampled data points in both splines are considered. The operation is applied to each pair of points existing in either spline. Points missing in one are interpolated so as to be able to combine them with the other to produce the output.

Definition at line 491 of file spline.h.

Here is the call graph for this function:

void combine ( self output,
Other const &  rhs,
Operation const &  op 
)

Here is the caller graph for this function:

void compute_coefficients (  ) 

Compute the second derivative of the interpolation functions and store them in the s_ member of the info associated with every x/y pair.

Definition at line 972 of file spline.h.

void domain ( std::set< X > *  target  )  const

get all interesting Xs

Get a set of the sampled data X components (ie the domain locations where samples are taken.

Definition at line 844 of file spline.h.

Here is the caller graph for this function:

spline< X, Y, D >::const_iterator end (  )  const

Definition at line 308 of file spline.h.

Here is the caller graph for this function:

void evaluate ( start_x,
delta_x,
OutputIterator  begin,
OutputIterator  end 
) const

Create a collection of interpolated values. Output those values through an iterator that points to a pair<X,Y> where X, and Y are assignment compatible with double. The begin,end variables define the standard output iterator range logic. The first value output will be (start_x, f(start_x)), the second will be (start_x+delta_x, f(start_x+delta_x)), and so forth.

Definition at line 944 of file spline.h.

Here is the caller graph for this function:

spline< X, Y, D >::const_iterator floor ( X const &  x  )  const

Returns the iterator to the sample whose X component is as high as possible but <= x. Returns end() if no such sample exists. Consider the sequence:

      10, 11, 12

If you ask for 9, you will get end() returned. If you ask for 13, you will get an iterator to 12. If you ask for 11.5, you will get an iterator to 11.

Definition at line 629 of file spline.h.

Here is the caller graph for this function:

spline< X, Y, D >::sample_t front (  )  const

Returns the first sample or an undefined value if there are none.

Definition at line 597 of file spline.h.

Here is the call graph for this function:

Here is the caller graph for this function:

void include ( SF const &  rhs  ) 

Ensures that all samples in rhs also appear in this sampled function. Samples in rhs superceed samples already in the spline. rhs can be of a different type of data structure but the structure's iterator must point to pairs whose First and Second types are compatible with X and Y.

Definition at line 557 of file spline.h.

Here is the call graph for this function:

void include ( Iterator  l,
Iterator  g 
)

Ensures that all samples in iterator range also appear in this sampled function. Samples in the range l-g replace samples already spline.

The iterators must point to pairs of some kind but those types do not have to be exactly X and Y. On the other hand, it must be possible to convert them to X and Y respectively.

Definition at line 526 of file spline.h.

Here is the call graph for this function:

Here is the caller graph for this function:

Y interpolate_cubic ( X const &  x  )  const

Definition at line 1063 of file spline.h.

Here is the call graph for this function:

Here is the caller graph for this function:

Y interpolate_line ( X const &  x  )  const

This method interpolates the value of the sampled function at 'x', returning the corresponding y. See comments in it for a description of how the interpolation works, but generally, this function treats the sampled function as a piecewise linear function, like this:

   D|         +                                                         ;
    |        / \                                                        ;
   C|       /   \             +-->                                      ;
    |      /     \           /                                          ;
    |     /       \         /                                           ;
    |    /         \       /                                            ;
   B| <-+           \     /                                             ;
   A|                +---+                                              ;
    +-------------------------------------------                        ;
        x0    x1     x2  x3   x4                                        ;
                 u                  v                                   ;

In this diagram, the samples are (x0,B), (x1,D), (x2,A), (x3,A), (x4,C). This is the second fastest interpolator and is usuable to represent the manufacturing of objects. Usually, an object takes a certain manufacturing time -- the more time, the more objects are made. Sales estimates generally work like this. Slowly changing real world physical phenomena can also be modeled this way. If you need more accuracy, use more samples.

The return value is calculated like this: If there are no samples, the return value is undefined. If the requested 'x' value to be interpolated is less than the lowest sampled x value, x0, then you get x0's value functional value (B). If the requested x value is greater than the highest sample's X value (x4), then you will get the Y of the highest sample. This approach allows you set your value for the 'out of range' situations. You just jam in extra samples to represent the too low and too high situations. Otherwise, if you request a location between two extant samples, you will get a linearly approximated value. Consider point 'u' in the above picture. u likes between x1 and x2. The Y associated with us is calculated like this:

      slope = (B - D) / (x2 - x1)  // negative value of course
  
      deltax = x(u) - x1
  
      y(u) = B + slope * deltax

If there are no samples at all, you get an undefined result.

Definition at line 716 of file spline.h.

Here is the caller graph for this function:

Y interpolate_step ( X const &  x  )  const

This method interpolates the value of the sampled function at 'x', returning the corresponding y. See comments in it for a description of how the interpolation works, but generally, this function treats the sampled function as a step wise constant function that looks like this:

   D|                         +------------->
    |                         |
   C|         +-----------+   |
   B| <-+-----+           |   |
   A|                     +---+
    +-------------------------------------------
        x0    x1          x2  x3  
                   u                  v

In this diagram, the samples are (x0,B), (x1,C), (x2,A), (x3,D). A step wise interpolator makes sense when tracking inventory and the time to load and unload trucks is insignificant. It is the fastest interpolator.

The return value is calculated like this: If there are no samples, the return value is undefined. If the requested 'x' value to be interpolated is less than the lowest sampled x value, x0, then you get x0's value functional value (B). Otherwise you get the value of the actual sample data, Y component, of the sample on or to the immediate left. So at point u, you would get C, and at v you would get D.

If there are no samples at all, you get an undefined result.

Definition at line 663 of file spline.h.

Here is the caller graph for this function:

spline< X, Y, D >::interpolator_t interpolator (  )  const

gets the current interpolator

Definition at line 573 of file spline.h.

Y operator() ( location  )  const
spline< X, Y, D > & operator*= ( T const &  rhs  ) 

Add another spline to this one. Make sure that all samples in both splines are addressed.

Definition at line 907 of file spline.h.

Here is the call graph for this function:

spline< X, Y, D > & operator+= ( T const &  rhs  ) 

Add another spline to this one. Make sure that all samples in both splines are addressed.

Definition at line 868 of file spline.h.

Here is the call graph for this function:

spline< X, Y, D > & operator-= ( T const &  rhs  ) 

Add another spline to this one. Make sure that all samples in both splines are addressed.

Definition at line 887 of file spline.h.

Here is the call graph for this function:

spline< X, Y, D > & operator/= ( T const &  rhs  ) 

Add another spline to this one. Make sure that all samples in both splines are addressed.

Definition at line 926 of file spline.h.

Here is the call graph for this function:

self& operator= ( self const &  rhs  ) 
void set_interpolator ( interpolator_t  t  ) 

< Change to a new interpolator

Definition at line 585 of file spline.h.

Here is the caller graph for this function:

size_t size (  )  const

Definition at line 1131 of file spline.h.

void swap ( self rhs  ) 

Quickly swap the contents of this spline with that of another. This occaisionally useful when writing algorithms that construct objects and then destruct them. You can arrange to have an empty object destructed quickly while your constructed object gets filled without a copy. This of course requires thought.

Definition at line 394 of file spline.h.

Here is the caller graph for this function:


Member Data Documentation

bool dirty_ [private]

cubic spline s's need recalculation

Definition at line 205 of file spline.h.

Current interpolator.

Definition at line 204 of file spline.h.

samples_t samples_ [private]

Map of actual data.

Definition at line 203 of file spline.h.


The documentation for this class was generated from the following file:
Generated on Wed Feb 29 22:56:41 2012 for CXXUtilities by  doxygen 1.6.3