Mercurial > hg > svcore

changeset 880:b4787b595db3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Implement and test the interpolating and auto range mappers
author Chris Cannam
date Fri, 31 Jan 2014 17:09:02 +0000
parents eb6b6a88faed
children 816c751a7979
files base/RangeMapper.cpp base/RangeMapper.h base/test/RangeMapperTest.h
diffstat 3 files changed, 361 insertions(+), 2 deletions(-) [+]
line wrap: on
line diff
--- a/base/RangeMapper.cpp	Fri Jan 31 13:39:37 2014 +0000
+++ b/base/RangeMapper.cpp	Fri Jan 31 17:09:02 2014 +0000
@@ -125,3 +125,146 @@
     return value;
 }
 
+InterpolatingRangeMapper::InterpolatingRangeMapper(CoordMap pointMappings,
+                                                   QString unit) :
+    m_mappings(pointMappings),
+    m_unit(unit)
+{
+    for (CoordMap::const_iterator i = m_mappings.begin(); 
+         i != m_mappings.end(); ++i) {
+        m_reverse[i->second] = i->first;
+    }
+}
+
+int
+InterpolatingRangeMapper::getPositionForValue(float value) const
+{
+    CoordMap::const_iterator i = m_mappings.lower_bound(value);
+    CoordMap::const_iterator j = i;
+    --j;
+
+    if (i == m_mappings.end()) return j->second;
+    if (i == m_mappings.begin()) return i->second;
+    if (i->first == value) return i->second;
+
+    return lrintf(((value - j->first) / (i->first - j->first)) *
+                  float(i->second - j->second) + j->second);
+}
+
+float
+InterpolatingRangeMapper::getValueForPosition(int position) const
+{
+    std::map<int, float>::const_iterator i = m_reverse.lower_bound(position);
+    std::map<int, float>::const_iterator j = i;
+    --j;
+
+    if (i == m_reverse.end()) return j->second;
+    if (i == m_reverse.begin()) return i->second;
+    if (i->first == position) return i->second;
+
+    return ((float(position) - j->first) / (i->first - j->first)) *
+        (i->second - j->second) + j->second;
+}
+
+AutoRangeMapper::AutoRangeMapper(CoordMap pointMappings,
+                                 QString unit) :
+    m_mappings(pointMappings),
+    m_unit(unit)
+{
+    m_type = chooseMappingTypeFor(m_mappings);
+
+    CoordMap::const_iterator first = m_mappings.begin();
+    CoordMap::const_iterator last = m_mappings.end();
+    --last;
+
+    switch (m_type) {
+    case StraightLine:
+        m_mapper = new LinearRangeMapper(first->second, last->second,
+                                         first->first, last->first,
+                                         unit, false);
+        break;
+    case Logarithmic:
+        m_mapper = new LogRangeMapper(first->second, last->second,
+                                      first->first, last->first,
+                                      unit, false);
+        break;
+    case Interpolating:
+        m_mapper = new InterpolatingRangeMapper(m_mappings, unit);
+        break;
+    }
+}
+
+AutoRangeMapper::~AutoRangeMapper()
+{
+    delete m_mapper;
+}
+
+AutoRangeMapper::MappingType
+AutoRangeMapper::chooseMappingTypeFor(const CoordMap &mappings)
+{
+    // how do we work out whether a linear/log mapping is "close enough"?
+
+    CoordMap::const_iterator first = mappings.begin();
+    CoordMap::const_iterator last = mappings.end();
+    --last;
+
+    LinearRangeMapper linm(first->second, last->second,
+                           first->first, last->first,
+                           "", false);
+
+    bool inadequate = false;
+
+    for (CoordMap::const_iterator i = mappings.begin();
+         i != mappings.end(); ++i) {
+        int candidate = linm.getPositionForValue(i->first);
+        int diff = candidate - i->second;
+        if (diff < 0) diff = -diff;
+        if (diff > 1) {
+            cerr << "AutoRangeMapper::chooseMappingTypeFor: diff = " << diff
+                 << ", straight-line mapping inadequate" << endl;
+            inadequate = true;
+            break;
+        }
+    }
+
+    if (!inadequate) {
+        return StraightLine;
+    }
+
+    LogRangeMapper logm(first->second, last->second,
+                        first->first, last->first,
+                        "", false);
+
+    inadequate = false;
+
+    for (CoordMap::const_iterator i = mappings.begin();
+         i != mappings.end(); ++i) {
+        int candidate = logm.getPositionForValue(i->first);
+        int diff = candidate - i->second;
+        if (diff < 0) diff = -diff;
+        if (diff > 1) {
+            cerr << "AutoRangeMapper::chooseMappingTypeFor: diff = " << diff
+                 << ", log mapping inadequate" << endl;
+            inadequate = true;
+            break;
+        }
+    }
+
+    if (!inadequate) {
+        return Logarithmic;
+    }
+
+    return Interpolating;
+}
+
+int
+AutoRangeMapper::getPositionForValue(float value) const
+{
+    return m_mapper->getPositionForValue(value);
+}
+
+float
+AutoRangeMapper::getValueForPosition(int position) const
+{
+    return m_mapper->getValueForPosition(position);
+}
--- a/base/RangeMapper.h	Fri Jan 31 13:39:37 2014 +0000
+++ b/base/RangeMapper.h	Fri Jan 31 17:09:02 2014 +0000
@@ -19,7 +19,7 @@
 #include <QString>
 
 #include "Debug.h"
-
+#include <map>
 
 class RangeMapper 
 {
@@ -58,10 +58,16 @@
     bool m_inverted;
 };
 
-
 class LogRangeMapper : public RangeMapper
 {
 public:
+    /**
+     * Map values in range minval->maxval into integer range
+     * minpos->maxpos such that logs of the values are mapped
+     * linearly. minval and minpos must be less than maxval and maxpos
+     * respectively. If inverted is true, the range will be mapped
+     * "backwards" (minval to maxpos and maxval to minpos).
+     */
     LogRangeMapper(int minpos, int maxpos,
                    float minval, float maxval,
                    QString m_unit = "", bool inverted = false);
@@ -89,5 +95,111 @@
     bool m_inverted;
 };
 
+class InterpolatingRangeMapper : public RangeMapper
+{
+public:
+    typedef std::map<float, int> CoordMap;
+
+    /**
+     * Given a series of (value, position) coordinate mappings,
+     * construct a range mapper that maps arbitrary values, in the
+     * range between minimum and maximum of the provided values, onto
+     * coordinates using linear interpolation between the supplied
+     * points.
+     *
+     *!!! todo: Cubic -- more generally useful than linear interpolation
+     *!!! todo: inverted flag
+     *
+     * The set of provided mappings must contain at least two
+     * coordinates.
+     *
+     * It is expected that the values and positions in the coordinate
+     * mappings will both be monotonically increasing (i.e. no
+     * inflections in the mapping curve). Behaviour is undefined if
+     * this is not the case.
+     */
+    InterpolatingRangeMapper(CoordMap pointMappings,
+                             QString unit);
+
+    virtual int getPositionForValue(float value) const;
+    virtual float getValueForPosition(int position) const;
+
+    virtual QString getUnit() const { return m_unit; }
+
+protected:
+    CoordMap m_mappings;
+    std::map<int, float> m_reverse;
+    QString m_unit;
+};
+
+class AutoRangeMapper : public RangeMapper
+{
+public:
+    enum MappingType {
+        Interpolating,
+        StraightLine,
+        Logarithmic,
+    };
+
+    typedef std::map<float, int> CoordMap;
+
+    /**
+     * Given a series of (value, position) coordinate mappings,
+     * construct a range mapper that maps arbitrary values, in the
+     * range between minimum and maximum of the provided values, onto
+     * coordinates. 
+     *
+     * The mapping used may be
+     * 
+     *    Interpolating -- an InterpolatingRangeMapper will be used
+     * 
+     *    StraightLine -- a LinearRangeMapper from the minimum to
+     *    maximum value coordinates will be used, ignoring all other
+     *    supplied coordinate mappings
+     * 
+     *    Logarithmic -- a LogRangeMapper from the minimum to
+     *    maximum value coordinates will be used, ignoring all other
+     *    supplied coordinate mappings
+     *
+     * The mapping will be chosen automatically by looking at the
+     * supplied coordinates. If the supplied coordinates fall on a
+     * straight line, a StraightLine mapping will be used; if they
+     * fall on a log curve, a Logarithmic mapping will be used;
+     * otherwise an Interpolating mapping will be used.
+     *
+     *!!! todo: inverted flag
+     *
+     * The set of provided mappings must contain at least two
+     * coordinates, or at least three if the points are not supposed
+     * to be in a straight line.
+     *
+     * It is expected that the values and positions in the coordinate
+     * mappings will both be monotonically increasing (i.e. no
+     * inflections in the mapping curve). Behaviour is undefined if
+     * this is not the case.
+     */
+    AutoRangeMapper(CoordMap pointMappings,
+                    QString unit);
+
+    ~AutoRangeMapper();
+
+    /**
+     * Return the mapping type in use.
+     */
+    MappingType getType() const { return m_type; }
+
+    virtual int getPositionForValue(float value) const;
+    virtual float getValueForPosition(int position) const;
+
+    virtual QString getUnit() const { return m_unit; }
+
+protected:
+    MappingType m_type;
+    CoordMap m_mappings;
+    QString m_unit;
+    RangeMapper *m_mapper;
+
+    MappingType chooseMappingTypeFor(const CoordMap &);
+};
 
 #endif
--- a/base/test/RangeMapperTest.h	Fri Jan 31 13:39:37 2014 +0000
+++ b/base/test/RangeMapperTest.h	Fri Jan 31 17:09:02 2014 +0000
@@ -131,6 +131,110 @@
 	QCOMPARE(rm.getValueForPosition(0), rm.getValueForPosition(3));
 	QCOMPARE(rm.getValueForPosition(9), rm.getValueForPosition(7));
     }
+
+    void interpolatingForward()
+    {
+	InterpolatingRangeMapper::CoordMap mappings;
+	mappings[1] = 10;
+	mappings[3] = 30;
+	mappings[5] = 70;
+	InterpolatingRangeMapper rm(mappings, "x");
+	QCOMPARE(rm.getUnit(), QString("x"));
+	QCOMPARE(rm.getPositionForValue(1.0), 10);
+	QCOMPARE(rm.getPositionForValue(0.0), 10);
+	QCOMPARE(rm.getPositionForValue(5.0), 70);
+	QCOMPARE(rm.getPositionForValue(6.0), 70);
+	QCOMPARE(rm.getPositionForValue(3.0), 30);
+	QCOMPARE(rm.getPositionForValue(2.5), 25);
+	QCOMPARE(rm.getPositionForValue(4.5), 60);
+    }
+
+    void interpolatingBackward()
+    {
+	InterpolatingRangeMapper::CoordMap mappings;
+	mappings[1] = 10;
+	mappings[3] = 30;
+	mappings[5] = 70;
+	InterpolatingRangeMapper rm(mappings, "x");
+	QCOMPARE(rm.getUnit(), QString("x"));
+	QCOMPARE(rm.getValueForPosition(10), 1.0);
+	QCOMPARE(rm.getValueForPosition(9), 1.0);
+	QCOMPARE(rm.getValueForPosition(70), 5.0);
+	QCOMPARE(rm.getValueForPosition(80), 5.0);
+	QCOMPARE(rm.getValueForPosition(30), 3.0);
+	QCOMPARE(rm.getValueForPosition(25), 2.5);
+	QCOMPARE(rm.getValueForPosition(60), 4.5);
+    }
+
+    void autoLinearForward()
+    {
+	AutoRangeMapper::CoordMap mappings;
+	mappings[0.5] = 1;
+	mappings[4.0] = 8;
+	AutoRangeMapper rm1(mappings, "x");
+	QCOMPARE(rm1.getUnit(), QString("x"));
+	QCOMPARE(rm1.getType(), AutoRangeMapper::StraightLine);
+	QCOMPARE(rm1.getPositionForValue(0.5), 1);
+	QCOMPARE(rm1.getPositionForValue(4.0), 8);
+	QCOMPARE(rm1.getPositionForValue(3.0), 6);
+	QCOMPARE(rm1.getPositionForValue(3.1), 6);
+	mappings[3.0] = 6;
+	mappings[3.5] = 7;
+	AutoRangeMapper rm2(mappings, "x");
+	QCOMPARE(rm2.getUnit(), QString("x"));
+	QCOMPARE(rm2.getType(), AutoRangeMapper::StraightLine);
+	QCOMPARE(rm2.getPositionForValue(0.5), 1);
+	QCOMPARE(rm2.getPositionForValue(4.0), 8);
+	QCOMPARE(rm2.getPositionForValue(3.0), 6);
+	QCOMPARE(rm2.getPositionForValue(3.1), 6);
+    }
+
+    void autoLogForward()
+    {
+	AutoRangeMapper::CoordMap mappings;
+	mappings[10] = 3;
+	mappings[1000] = 5;
+	mappings[100000] = 7;
+	AutoRangeMapper rm1(mappings, "x");
+	QCOMPARE(rm1.getUnit(), QString("x"));
+	QCOMPARE(rm1.getType(), AutoRangeMapper::Logarithmic);
+	QCOMPARE(rm1.getPositionForValue(10.0), 3);
+	QCOMPARE(rm1.getPositionForValue(100000.0), 7);
+	QCOMPARE(rm1.getPositionForValue(1.0), 3);
+	QCOMPARE(rm1.getPositionForValue(1000000.0), 7);
+	QCOMPARE(rm1.getPositionForValue(1000.0), 5);
+	QCOMPARE(rm1.getPositionForValue(900.0), 5);
+	QCOMPARE(rm1.getPositionForValue(20000), 6);
+	mappings[100] = 4;
+	AutoRangeMapper rm2(mappings, "x");
+	QCOMPARE(rm2.getUnit(), QString("x"));
+	QCOMPARE(rm2.getType(), AutoRangeMapper::Logarithmic);
+	QCOMPARE(rm2.getPositionForValue(10.0), 3);
+	QCOMPARE(rm2.getPositionForValue(100000.0), 7);
+	QCOMPARE(rm2.getPositionForValue(1.0), 3);
+	QCOMPARE(rm2.getPositionForValue(1000000.0), 7);
+	QCOMPARE(rm2.getPositionForValue(1000.0), 5);
+	QCOMPARE(rm2.getPositionForValue(900.0), 5);
+	QCOMPARE(rm2.getPositionForValue(20000), 6);
+    }
+
+    void autoInterpolatingForward()
+    {
+	AutoRangeMapper::CoordMap mappings;
+	mappings[1] = 10;
+	mappings[3] = 30;
+	mappings[5] = 70;
+	AutoRangeMapper rm(mappings, "x");
+	QCOMPARE(rm.getUnit(), QString("x"));
+	QCOMPARE(rm.getType(), AutoRangeMapper::Interpolating);
+	QCOMPARE(rm.getPositionForValue(1.0), 10);
+	QCOMPARE(rm.getPositionForValue(0.0), 10);
+	QCOMPARE(rm.getPositionForValue(5.0), 70);
+	QCOMPARE(rm.getPositionForValue(6.0), 70);
+	QCOMPARE(rm.getPositionForValue(3.0), 30);
+	QCOMPARE(rm.getPositionForValue(2.5), 25);
+	QCOMPARE(rm.getPositionForValue(4.5), 60);
+    }
 };
 
 #endif