(C++) MultiApproximator
February 24, 2017 · View on GitHub
(C++) MultiApproximator
MultiApproximator is a class to perform an interpolation on data. For example, when the supplied data consists of the coordinats (1,1) and (2,2), it will estimate (the x value of) 1,5 to be (the value y value of) 1,5.
MultiApproximator supports multiple identical keys (for example the coordinats (1.0,2.0) and (1.0,3.0)), similar to a std::multi_map. Approximator does not allow this.
Technical facts
./CppMultiApproximator/CppMultiApproximator.pri
INCLUDEPATH += \ ../../Classes/CppMultiApproximator SOURCES += \ ../../Classes/CppMultiApproximator/multiapproximator.cpp HEADERS += \ ../../Classes/CppMultiApproximator/multiapproximator.h OTHER_FILES += \ ../../Classes/CppMultiApproximator/Licence.txt
./CppMultiApproximator/multiapproximator.h
#ifndef MULTIAPPROXIMATOR_H #define MULTIAPPROXIMATOR_H #include <algorithm> #include <cassert> #include <cmath> #include <numeric> #include <stdexcept> #include <map> #pragma GCC diagnostic push #pragma GCC diagnostic ignored "-Wunused-local-typedefs" #pragma GCC diagnostic pop #include "approximator.h" #include "exceptionnoextrapolation.h" #include "testtimer.h" #include "trace.h" namespace ribi { ///MultiApproximator can estimate a value between (non-unique) keys. ///For example, supply Approximator<X,Y> with (1.0,10) and (2.0,20) ///and it will estimate an X if 1.5 to have a Y of 15. ///If the data used has unique keys only, use Approximator ///for an increase in run-time speed. ///If all keys are added to MultiApproximator, it is possible to spawn ///an Approximator from it. /// ///Key: a type that has operator< ///Value: a type that has operator/(double) ///Container: how to store the std::pair<Key,Value> /// - boost::container::flat_multimap<Key,Value> /// : faster for lookup, data adding is slower /// - std::multimap<Key,Value> /// : faster adding of data, lookup is slower template <class Key = double, class Value = double, class Container = std::multimap<Key,Value> > struct MultiApproximator { typedef Key key_type; typedef Value value_type; typedef typename Container::const_iterator Iterator; typedef typename std::pair<Iterator,Iterator> Range; explicit MultiApproximator(const Container& container = Container()) noexcept; ///Add a (key,value) pair. Because keys do not need to be unique, ///this will always succeed void Add(const Key& key, const Value& value) noexcept; ///Approximates a value from a key ///Will throw a std::logic_error if there is no data in the MultiApproximator ///Will throw ExceptionNoExtrapolation if the key is beyond the range ///of the keys stored in MultiApproxitor Value Approximate(const Key& key) const; ///Obtain the container const Container& GetContainer() const noexcept{ return m_m; } ///Get the heighest key value Key GetMax() const; ///Get the lowest key value Key GetMin() const; ///Obtain the true or averaged value at the key when the key is present Value GetValue(const Key& key) const; ///Obtain the version of this class static std::string GetVersion() noexcept; ///Obtain the version history of this class static std::vector<std::string> GetVersionHistory() noexcept; private: ///The container to store the std::pair<Key,Value> in Container m_m; #ifndef NDEBUG ///Test this class static void Test() noexcept; #endif //template <class AnyKey, class AnyValue, class AnyContainer> //friend void MultiApproximator<AnyKey,AnyValue,AnyContainer>::Test(); //friend void MultiApproximator<Key,Value,Container>::Test(); }; ///Convert a std::multimap to a std::map template <class Key, class Value> const std::map<Key,Value> MultimapToMap( const std::multimap<Key,Value> m) noexcept; ///Convert to a (non-multi)Approximator ///This probably gain runtime speed, when will no data added anymore template < class Key, class Value, class MultiContainer, class Container > Approximator<Key,Value,Container> ToApproximator( const MultiApproximator<Key,Value,MultiContainer>& m) noexcept; template <class Key, class Value, class Container> MultiApproximator<Key,Value,Container>::MultiApproximator(const Container& container) noexcept : m_m { container } { static_assert(!std::is_integral<Key>(), "MultiApproximator will not work on integer keys"); static_assert(!std::is_integral<Value>(), "MultiApproximator will not work on integer values"); #ifndef NDEBUG Test(); #endif } template <class Key, class Value, class Container> void MultiApproximator<Key,Value,Container>::Add(const Key& key, const Value& value) noexcept { m_m.insert(std::make_pair(key,value)); } template <class Key, class Value, class Container> Value MultiApproximator<Key,Value,Container>::Approximate(const Key& key) const { if (m_m.empty()) { throw std::logic_error( "MultiApproximator<Key,Value,Container>::Approximate: " "cannot approximate without data"); } //Must the average be calculated? if (m_m.find(key) != m_m.end()) return GetValue(key); const Iterator high { m_m.lower_bound(key) }; if (high == m_m.begin() || high == m_m.end()) { assert(!m_m.empty()); const Key lowest { (*m_m.begin()).first }; const Key highest { (*m_m.rbegin()).first }; throw ExceptionNoExtrapolation<Key>(key, lowest, highest); } const Iterator low { --Iterator(high) }; assert(low != m_m.end()); assert(high != m_m.end()); const Key d_low { (*low).first }; const Key d_high { (*high).first }; assert(d_low < key); assert(d_high > key); const double fraction { (key - d_low) / (d_high - d_low) }; assert(fraction >= 0.0); assert(fraction <= 1.0); assert(m_m.find(d_low) != m_m.end()); assert(m_m.find(d_high) != m_m.end()); const Value h_low { GetValue(d_low) }; const Value h_high { GetValue(d_high) }; return ((1.0 - fraction)) * h_low + ((0.0 + fraction) * h_high); } template <class Key, class Value, class Container> Key MultiApproximator<Key,Value,Container>::GetMax() const { assert(!m_m.empty()); return (*m_m.rbegin()).first; } template <class Key, class Value, class Container> Key MultiApproximator<Key,Value,Container>::GetMin() const { assert(!m_m.empty()); return (*m_m.begin()).first; } template <class Key, class Value, class Container> Value MultiApproximator<Key,Value,Container>::GetValue(const Key& key) const { assert(m_m.find(key) != m_m.end()); //Must the average be calculated? const Range r { m_m.equal_range(key) }; assert(r.first != m_m.end()); if (r.first != r.second ) { //const Value result = std::accumulate(r.first,r.second,Value(0.0), [] ) // / static_cast<double>( std::distance(r.first,r.second) ); Value sum { 0.0 }; int cnt { 0 }; for (Iterator i { r.first }; i!=r.second; ++i) { sum += (*i).second; ++cnt; } const Value result { sum / static_cast<double>(cnt) }; return result; } else { const Value result { (*r.first).second }; return result; } } template <class Key, class Value, class Container> std::string MultiApproximator<Key,Value,Container>::GetVersion() noexcept { return "1.1"; } ///Obtain the version history of this class template <class Key, class Value, class Container> std::vector<std::string> MultiApproximator<Key,Value,Container>::GetVersionHistory() noexcept { return { "2013-08-23: version 1.0: initial version", "2013-08-23: version 1.1: add conversion to an Approximator" }; } template <class Key, class Value> const std::map<Key,Value> MultimapToMap( const std::multimap<Key,Value> m) noexcept { std::map<Key,Value> n; if (m.empty()) return n; const auto end = m.end(); for (auto begin = m.begin(); begin != end; ) { assert(begin != m.end()); const auto key = (*begin).first; assert(m.find(key) != m.end()); //Must the average be calculated? const auto r = m.equal_range(key); assert(r.first != m.end()); if (r.first != r.second ) { Value sum(0.0); int cnt = 0; for (auto i = r.first; i!=r.second; ++i) { sum += (*i).second; ++cnt; } const Value result( sum / static_cast<double>(cnt)); n[ key ] = result; } else { const Value result((*r.first).second); n[ key ] = result; } begin = r.second; } return n; } #ifndef NDEBUG template <class Key, class Value, class Container> void MultiApproximator<Key,Value,Container>::Test() noexcept { { static bool is_tested{false}; if (is_tested) return; is_tested = true; } const TestTimer test_timer(__func__,__FILE__,1.0); //GetMin and GetMax { MultiApproximator<double,double,std::multimap<double,double> > m; m.Add(1.0,0.0); assert(m.GetMin() == 1.0); assert(m.GetMax() == 1.0); m.Add(2.0,0.0); assert(m.GetMin() == 1.0); assert(m.GetMax() == 2.0); m.Add(0.0,0.0); assert(m.GetMin() == 0.0); assert(m.GetMax() == 2.0); m.Add(0.5,0.0); assert(m.GetMin() == 0.0); assert(m.GetMax() == 2.0); } //GetValue { MultiApproximator<double,double,std::multimap<double,double> > m; const double key = 1.0; const double value1 = 1.0; m.Add(key,value1); assert(m.GetValue(key) == value1); const double value2 = 2.0; m.Add(key,value2); assert(m.GetValue(key) == (value1 + value2) / 2.0); const double value3 = 4.0; m.Add(key,value3); assert(m.GetValue(key) == (value1 + value2 + value3) / 3.0); } //MultimapToMap { { const std::multimap<int,double> m ( { { 1, 1.0} } ); const std::map<int,double> n(MultimapToMap(m)); assert(n.size() == 1); } { const std::multimap<int,double> m ( { { 1, 1.0}, { 1, 1.0} } ); const std::map<int,double> n(MultimapToMap(m)); const std::map<int,double> e( { { 1, 1.0 } } ); assert(n.size() == 1); assert(n == e); } { const std::multimap<int,double> m ( { { 1, 1.0}, { 1, 2.0} } ); const std::map<int,double> n(MultimapToMap(m)); const std::map<int,double> e( { { 1, 1.5 } } ); assert(n.size() == 1); assert(n == e); } { const std::multimap<int,double> m ( { {0, 0.0}, { 1, 1.0}, { 1, 1.0}, {2, 2.0} } ); const std::map<int,double> n(MultimapToMap(m)); const std::map<int,double> e( { {0, 0.0}, { 1, 1.0 }, {2, 2.0} } ); assert(n.size() == 3); assert(n == e); } { const std::multimap<int,double> m ( { {0, 0.0}, { 1, 1.0}, { 1, 2.0}, {2, 2.0} } ); const std::map<int,double> n(MultimapToMap(m)); const std::map<int,double> e( { {0, 0.0}, { 1, 1.5 }, {2, 2.0} } ); assert(n.size() == 3); assert(n == e); } } //Test approximation { MultiApproximator<double,double,std::multimap<double,double> > m; m.Add(1.0,10); m.Add(2.0,20); assert(m.Approximate(1.5) == 15); m.Add(4.0,40); m.Add(4.0,40); assert(m.Approximate(3.0) == 30); m.Add(3.0,35); assert(m.Approximate(3.0) == 35); m.Add(3.0,45); assert(m.Approximate(3.0) == 40); } TRACE("Completed MultiApproximator::Test successfully"); } #endif template < class Key, class Value, class MultiContainer, class Container > Approximator<Key,Value,Container> ToApproximator( const MultiApproximator<Key,Value,MultiContainer>& multi_approximator) noexcept { const MultiContainer m = multi_approximator.GetContainer(); const Container n = MultimapToMap(m); Approximator<Key,Value,Container> a(n); return a; } } //~namespace ribi #endif // MULTIAPPROXIMATOR_H
./CppMultiApproximator/multiapproximator.cpp
#include "multiapproximator.h"