# Standard Library-Like Linear Interpolation Table

Looking for a general review of a generalized linear interpolation table. Design decisions, anything that's missing, anything that could be clearer or simplified, any style considerations. Keep in mind that I've tried to keep this C++03 compatible, so no recommendations for using C++11 features please.

linear_table.hpp:

#ifndef LOOKUP_LINEAR_TABLE_HPP_
#define LOOKUP_LINEAR_TABLE_HPP_

#include <functional>
#include <utility>
#include <memory>

#include "lookup_detail.hpp"

namespace lookup
{

template <typename Key,
typename Value,
typename Compare = std::less<Key>,
typename Allocator = std::allocator<std::pair<const Key, Value> >
>
class unbounded_linear_table
: public detail::basic_lookup_table<Key, Value, Compare, Allocator>
{

private:

typedef detail::basic_lookup_table<Key, Value, Compare, Allocator> base;

public:

typedef typename base::iterator        iterator;
typedef typename base::const_iterator  const_iterator;
typedef typename base::size_type       size_type;
typedef typename base::allocator       allocator;
typedef typename base::key_type        key_type;
typedef typename base::mapped_type     mapped_type;
typedef typename base::value_type      value_type;
typedef typename base::key_compare     key_compare;
typedef typename base::reference       reference;
typedef typename base::const_reference const_reference;
typedef typename base::pointer         pointer;
typedef typename base::const_pointer   const_pointer;

//Returns an unbounded linear interpolation based on key.
//Unbounded -> if the key is less than the minimum key in
//the map, it will return the minimum value, if it is greater
//than the maximum, it will return the maximum.

mapped_type linear_interp(const Key& k) const
{
//First, test to see if the exact key
//is actually in the table.
const_iterator find = base::find(k);

if(find != base::end()) {
return find->second;
}

const_iterator higher = base::upper_bound(k);

//Lower constraint; upper_bound is less than the
//min table value
if(higher == base::begin()) {
return higher->second;
}

//Higher constraint check; upper bound (may)
//be greater than max table value.
if(higher == base::end()) {
const_iterator end_iter = base::end();
--end_iter;
if(base::cmp_(end_iter->first, k))
return end_iter->second;
}

const_iterator lower = higher;
--lower;

key_type diff_low = k - lower->first;
key_type total = higher->first - lower->first;

//Linearlly interpolate between lower and higher values
return lower->second + (diff_low / total) *
(higher->second - lower->second);
}

}; //end class unbounded_linear_table

typedef unbounded_linear_table<double, double> unbounded_lookup1d;

} //end namespace lookup

#endif //LOOKUP_LINEAR_TABLE_HPP


lookup_detail.hpp:

//Internal Header: Not to be directly imported

#ifndef LOOKUP_DETAIL_HPP_
#define LOOKUP_DETAIL_HPP_

#include <map>

namespace lookup
{
namespace detail
{

template <typename Key,
typename Value,
typename Compare,
typename Allocator>
class basic_lookup_table
{
private:

typedef std::map<Key, Value, Compare, Allocator> container;
container   table_;

public:

typedef typename container::iterator             iterator;
typedef typename container::const_iterator       const_iterator;
typedef typename container::size_type            size_type;
typedef typename container::reference            reference;
typedef typename container::const_reference      const_reference;
typedef typename container::pointer              pointer;
typedef typename container::const_pointer        const_pointer;
typedef typename container::value_type           value_type;
typedef Allocator                                allocator;
typedef Key                                      key_type;
typedef Value                                    mapped_type;
typedef Compare                                  key_compare;

protected:

key_compare cmp_;

//Disallow polymorphic usage through derived pointer
~basic_lookup_table()
{ }

iterator upper_bound(const Key& k)
{
return table_.upper_bound(k);
}

const_iterator upper_bound(const Key& k) const
{
return table_.upper_bound(k);
}

iterator lower_bound(const Key& k)
{
return table_.lower_bound(k);
}

const_iterator lower_bound(const Key& k) const
{
return table_.lower_bound(k);
}

iterator find(const Key& k)
{
return table_.find(k);
}

const_iterator find(const Key& k) const
{
return table_.find(k);
}

public:

void insert(const key_type& key, const mapped_type& value)
{
table_.insert(std::make_pair(key, value));
}

#if __cplusplus >= 201103L

void insert(key_type&& key, mapped_type&& value)
{
table_.insert(std::make_pair(key, value));
}

#endif

bool erase_key(const key_type& k)
{
size_type s = table_.erase(k);
return s != 0;
}

void erase_greater(const key_type& k)
{
iterator bound = table_.upper_bound(k);
table_.erase(bound, table_.end());
}

void erase_less(const key_type& k)
{
iterator bound = table_.lower_bound(k);
table_.erase(table_.begin(), bound);
}

void clear()
{
table_.clear();
}

iterator begin()
{
return table_.begin();
}

const_iterator begin() const
{
return table_.begin();
}

iterator end()
{
return table_.end();
}

const_iterator end() const
{
return table_.end();
}
};

} //end namespace detail
} //end namespace lookup

#endif //LOOKUP_DETAIL_HPP_


(Basic) example usage:

#include <iostream>
#include "linear_table.hpp"

int main()
{
using namespace lookup;

unbounded_lookup1d lut;
lut.insert(1.0, 2);
lut.insert(1.5, 3);
lut.insert(2.0, 7);
lut.insert(2.5, 10);
lut.insert(3.0, 15);

std::cout << lut.linear_interp(2.4) << "\n";
lut.erase_greater(2.0);
std::cout << lut.linear_interp(2.4) << "\n";

return 0;
}

-

//Lower constraint; upper_bound is less than the
//min table value


You probably mean "upper_bound is the min table value". This also applies to the next comment.

    //Higher constraint check; upper bound (may)
//be greater than max table value.
if(higher == base::end()) {
const_iterator end_iter = base::end();
--end_iter;
if(base::cmp_(end_iter->first, k))
return end_iter->second;
}


I may be wrong but this case seems to be covered by the first test. Maybe if (base::cmp_(end_iter->first, k) > 0?

No comments on basic_lookup_table which is simply a map wrapper anyway. Your code is very good C++. Oh, and since you asked about style: I prefer if (test) to if(test) and you could be careful about trailing white spaces.

-
Ah, yes, that's poor wording on my part. It should be "upper bound is the min table value, hence the key is less than the min table value", likewise for max. Good catch. For the test, I need to decrement end_iter first, since it points to one past the end of the map. I don't think it's covered by any other test. – Yuushi Feb 7 '13 at 11:21
I was wrong for the test, but let me ask another question: in what case would you enter in higher == base::end() but not in base::cmp_(end_iter->first, k)? – Quentin Pradet Feb 7 '13 at 12:38
I see your point - it can't happen. Another nice catch. – Yuushi Feb 7 '13 at 12:45