qwt_scale_engine.cpp

/******************************************************************************
 * Qwt Widget Library
 * Copyright (C) 1997   Josef Wilgen
 * Copyright (C) 2002   Uwe Rathmann
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the Qwt License, Version 1.0
 *****************************************************************************/
 
#include "qwt_scale_engine.h"
#include "qwt_math.h"
#include "qwt_interval.h"
#include "qwt_transform.h"
 
#include <qdebug.h>
 
#include <limits>
 
static inline double qwtLog( double base, double value )
{
    return std::log( value ) / std::log( base );
}
 
static inline QwtInterval qwtLogInterval( double base, const QwtInterval& interval )
{
    return QwtInterval( qwtLog( base, interval.minValue() ),
        qwtLog( base, interval.maxValue() ) );
}
 
static inline QwtInterval qwtPowInterval( double base, const QwtInterval& interval )
{
    return QwtInterval( std::pow( base, interval.minValue() ),
        std::pow( base, interval.maxValue() ) );
}
 
#if 1
 
// this version often doesn't find the best ticks: f.e for 15: 5, 10
static double qwtStepSize( double intervalSize, int maxSteps, uint base )
{
    const double minStep =
        QwtScaleArithmetic::divideInterval( intervalSize, maxSteps, base );
 
    if ( minStep != 0.0 )
    {
        // # ticks per interval
        const int numTicks = qwtCeil( qAbs( intervalSize / minStep ) ) - 1;
 
        // Do the minor steps fit into the interval?
        if ( qwtFuzzyCompare( ( numTicks + 1 ) * qAbs( minStep ),
            qAbs( intervalSize ), intervalSize ) > 0 )
        {
            // The minor steps doesn't fit into the interval
            return 0.5 * intervalSize;
        }
    }
 
    return minStep;
}
 
#else
 
static double qwtStepSize( double intervalSize, int maxSteps, uint base )
{
    if ( maxSteps <= 0 )
        return 0.0;
 
    if ( maxSteps > 2 )
    {
        for ( int numSteps = maxSteps; numSteps > 1; numSteps-- )
        {
            const double stepSize = intervalSize / numSteps;
 
            const double p = std::floor( std::log( stepSize ) / std::log( base ) );
            const double fraction = std::pow( base, p );
 
            for ( uint n = base; n > 1; n /= 2 )
            {
                if ( qFuzzyCompare( stepSize, n * fraction ) )
                    return stepSize;
 
                if ( n == 3 && ( base % 2 ) == 0 )
                {
                    if ( qFuzzyCompare( stepSize, 2 * fraction ) )
                        return stepSize;
                }
            }
        }
    }
 
    return intervalSize * 0.5;
}
 
#endif
 
static const double _eps = 1.0e-6;
 
double QwtScaleArithmetic::ceilEps( double value,
    double intervalSize )
{
    const double eps = _eps * intervalSize;
 
    value = ( value - eps ) / intervalSize;
    return std::ceil( value ) * intervalSize;
}
 
double QwtScaleArithmetic::floorEps( double value, double intervalSize )
{
    const double eps = _eps * intervalSize;
 
    value = ( value + eps ) / intervalSize;
    return std::floor( value ) * intervalSize;
}
 
double QwtScaleArithmetic::divideEps( double intervalSize, double numSteps )
{
    if ( numSteps == 0.0 || intervalSize == 0.0 )
        return 0.0;
 
    return ( intervalSize - ( _eps * intervalSize ) ) / numSteps;
}
 
double QwtScaleArithmetic::divideInterval(
    double intervalSize, int numSteps, uint base )
{
    if ( numSteps <= 0 )
        return 0.0;
 
    const double v = QwtScaleArithmetic::divideEps( intervalSize, numSteps );
    if ( v == 0.0 )
        return 0.0;
 
    const double lx = qwtLog( base, std::fabs( v ) );
    const double p = std::floor( lx );
 
    const double fraction = std::pow( base, lx - p );
 
    uint n = base;
    while ( ( n > 1 ) && ( fraction <= n / 2 ) )
        n /= 2;
 
    double stepSize = n * std::pow( base, p );
    if ( v < 0 )
        stepSize = -stepSize;
 
    return stepSize;
}
 
class QwtScaleEngine::PrivateData
{
  public:
    PrivateData():
        attributes( QwtScaleEngine::NoAttribute ),
        lowerMargin( 0.0 ),
        upperMargin( 0.0 ),
        referenceValue( 0.0 ),
        base( 10 ),
        transform( NULL )
    {
    }
 
    ~PrivateData()
    {
        delete transform;
    }
 
    QwtScaleEngine::Attributes attributes;
 
    double lowerMargin;
    double upperMargin;
 
    double referenceValue;
 
    uint base;
 
    QwtTransform* transform;
};
 
QwtScaleEngine::QwtScaleEngine( uint base )
{
    m_data = new PrivateData;
    setBase( base );
}
 
 
QwtScaleEngine::~QwtScaleEngine ()
{
    delete m_data;
}
 
void QwtScaleEngine::setTransformation( QwtTransform* transform )
{
    if ( transform != m_data->transform )
    {
        delete m_data->transform;
        m_data->transform = transform;
    }
}
 
QwtTransform* QwtScaleEngine::transformation() const
{
    QwtTransform* transform = NULL;
    if ( m_data->transform )
        transform = m_data->transform->copy();
 
    return transform;
}
 
double QwtScaleEngine::lowerMargin() const
{
    return m_data->lowerMargin;
}
 
double QwtScaleEngine::upperMargin() const
{
    return m_data->upperMargin;
}
 
void QwtScaleEngine::setMargins( double lower, double upper )
{
    m_data->lowerMargin = qwtMaxF( lower, 0.0 );
    m_data->upperMargin = qwtMaxF( upper, 0.0 );
}
 
double QwtScaleEngine::divideInterval(
    double intervalSize, int numSteps ) const
{
    return QwtScaleArithmetic::divideInterval(
        intervalSize, numSteps, m_data->base );
}
 
bool QwtScaleEngine::contains(
    const QwtInterval& interval, double value ) const
{
    if ( !interval.isValid() )
        return false;
 
    if ( qwtFuzzyCompare( value, interval.minValue(), interval.width() ) < 0 )
        return false;
 
    if ( qwtFuzzyCompare( value, interval.maxValue(), interval.width() ) > 0 )
        return false;
 
    return true;
}
 
QList< double > QwtScaleEngine::strip( const QList< double >& ticks,
    const QwtInterval& interval ) const
{
    if ( !interval.isValid() || ticks.count() == 0 )
        return QList< double >();
 
    if ( contains( interval, ticks.first() )
        && contains( interval, ticks.last() ) )
    {
        return ticks;
    }
 
    QList< double > strippedTicks;
    for ( int i = 0; i < ticks.count(); i++ )
    {
        if ( contains( interval, ticks[i] ) )
            strippedTicks += ticks[i];
    }
    return strippedTicks;
}
 
QwtInterval QwtScaleEngine::buildInterval( double value ) const
{
    const double delta = ( value == 0.0 ) ? 0.5 : qAbs( 0.5 * value );
    const double max = std::numeric_limits< double >::max();
 
    if ( max - delta < value )
        return QwtInterval( max - delta, max );
 
    if ( -max + delta > value )
        return QwtInterval( -max, -max + delta );
 
    return QwtInterval( value - delta, value + delta );
}
 
void QwtScaleEngine::setAttribute( Attribute attribute, bool on )
{
    if ( on )
        m_data->attributes |= attribute;
    else
        m_data->attributes &= ~attribute;
}
 
bool QwtScaleEngine::testAttribute( Attribute attribute ) const
{
    return ( m_data->attributes & attribute );
}
 
void QwtScaleEngine::setAttributes( Attributes attributes )
{
    m_data->attributes = attributes;
}
 
QwtScaleEngine::Attributes QwtScaleEngine::attributes() const
{
    return m_data->attributes;
}
 
void QwtScaleEngine::setReference( double reference )
{
    m_data->referenceValue = reference;
}
 
double QwtScaleEngine::reference() const
{
    return m_data->referenceValue;
}
 
void QwtScaleEngine::setBase( uint base )
{
    m_data->base = qMax( base, 2U );
}
 
uint QwtScaleEngine::base() const
{
    return m_data->base;
}
 
QwtLinearScaleEngine::QwtLinearScaleEngine( uint base ):
    QwtScaleEngine( base )
{
}
 
QwtLinearScaleEngine::~QwtLinearScaleEngine()
{
}
 
void QwtLinearScaleEngine::autoScale( int maxNumSteps,
    double& x1, double& x2, double& stepSize ) const
{
    QwtInterval interval( x1, x2 );
    interval = interval.normalized();
 
    interval.setMinValue( interval.minValue() - lowerMargin() );
    interval.setMaxValue( interval.maxValue() + upperMargin() );
 
    if ( testAttribute( QwtScaleEngine::Symmetric ) )
        interval = interval.symmetrize( reference() );
 
    if ( testAttribute( QwtScaleEngine::IncludeReference ) )
        interval = interval.extend( reference() );
 
    if ( interval.width() == 0.0 )
        interval = buildInterval( interval.minValue() );
 
    stepSize = QwtScaleArithmetic::divideInterval(
        interval.width(), qMax( maxNumSteps, 1 ), base() );
 
    if ( !testAttribute( QwtScaleEngine::Floating ) )
        interval = align( interval, stepSize );
 
    x1 = interval.minValue();
    x2 = interval.maxValue();
 
    if ( testAttribute( QwtScaleEngine::Inverted ) )
    {
        qSwap( x1, x2 );
        stepSize = -stepSize;
    }
}
 
QwtScaleDiv QwtLinearScaleEngine::divideScale( double x1, double x2,
    int maxMajorSteps, int maxMinorSteps, double stepSize ) const
{
    QwtInterval interval = QwtInterval( x1, x2 ).normalized();
 
    if ( interval.widthL() > std::numeric_limits< double >::max() )
    {
        qWarning() << "QwtLinearScaleEngine::divideScale: overflow";
        return QwtScaleDiv();
    }
 
    if ( interval.width() <= 0 )
        return QwtScaleDiv();
 
    stepSize = qAbs( stepSize );
    if ( stepSize == 0.0 )
    {
        if ( maxMajorSteps < 1 )
            maxMajorSteps = 1;
 
        stepSize = QwtScaleArithmetic::divideInterval(
            interval.width(), maxMajorSteps, base() );
    }
 
    QwtScaleDiv scaleDiv;
 
    if ( stepSize != 0.0 )
    {
        QList< double > ticks[QwtScaleDiv::NTickTypes];
        buildTicks( interval, stepSize, maxMinorSteps, ticks );
 
        scaleDiv = QwtScaleDiv( interval, ticks );
    }
 
    if ( x1 > x2 )
        scaleDiv.invert();
 
    return scaleDiv;
}
 
void QwtLinearScaleEngine::buildTicks(
    const QwtInterval& interval, double stepSize, int maxMinorSteps,
    QList< double > ticks[QwtScaleDiv::NTickTypes] ) const
{
    const QwtInterval boundingInterval = align( interval, stepSize );
 
    ticks[QwtScaleDiv::MajorTick] =
        buildMajorTicks( boundingInterval, stepSize );
 
    if ( maxMinorSteps > 0 )
    {
        buildMinorTicks( ticks[QwtScaleDiv::MajorTick], maxMinorSteps, stepSize,
            ticks[QwtScaleDiv::MinorTick], ticks[QwtScaleDiv::MediumTick] );
    }
 
    for ( int i = 0; i < QwtScaleDiv::NTickTypes; i++ )
    {
        ticks[i] = strip( ticks[i], interval );
 
        // ticks very close to 0.0 are explicitly set to 0.0
 
        for ( int j = 0; j < ticks[i].count(); j++ )
        {
            if ( qwtFuzzyCompare( ticks[i][j], 0.0, stepSize ) == 0 )
                ticks[i][j] = 0.0;
        }
    }
}
 
QList< double > QwtLinearScaleEngine::buildMajorTicks(
    const QwtInterval& interval, double stepSize ) const
{
    int numTicks = qRound( interval.width() / stepSize ) + 1;
    if ( numTicks > 10000 )
        numTicks = 10000;
 
    QList< double > ticks;
    ticks.reserve( numTicks );
 
    ticks += interval.minValue();
    for ( int i = 1; i < numTicks - 1; i++ )
        ticks += interval.minValue() + i * stepSize;
    ticks += interval.maxValue();
 
    return ticks;
}
 
void QwtLinearScaleEngine::buildMinorTicks(
    const QList< double >& majorTicks,
    int maxMinorSteps, double stepSize,
    QList< double >& minorTicks,
    QList< double >& mediumTicks ) const
{
    double minStep = qwtStepSize( stepSize, maxMinorSteps, base() );
    if ( minStep == 0.0 )
        return;
 
    // # ticks per interval
    const int numTicks = qwtCeil( qAbs( stepSize / minStep ) ) - 1;
 
    int medIndex = -1;
    if ( numTicks % 2 )
        medIndex = numTicks / 2;
 
    // calculate minor ticks
 
    for ( int i = 0; i < majorTicks.count(); i++ )
    {
        double val = majorTicks[i];
        for ( int k = 0; k < numTicks; k++ )
        {
            val += minStep;
 
            double alignedValue = val;
            if ( qwtFuzzyCompare( val, 0.0, stepSize ) == 0 )
                alignedValue = 0.0;
 
            if ( k == medIndex )
                mediumTicks += alignedValue;
            else
                minorTicks += alignedValue;
        }
    }
}
 
QwtInterval QwtLinearScaleEngine::align(
    const QwtInterval& interval, double stepSize ) const
{
    double x1 = interval.minValue();
    double x2 = interval.maxValue();
 
    // when there is no rounding beside some effect, when
    // calculating with doubles, we keep the original value
 
    const double eps = 0.000000000001; // since Qt 4.8: qFuzzyIsNull
    const double max = std::numeric_limits< double >::max();
 
    if ( -max + stepSize <= x1 )
    {
        const double x = QwtScaleArithmetic::floorEps( x1, stepSize );
        if ( qAbs(x) <= eps || !qFuzzyCompare( x1, x ) )
            x1 = x;
    }
 
    if ( max - stepSize >= x2 )
    {
        const double x = QwtScaleArithmetic::ceilEps( x2, stepSize );
        if ( qAbs(x) <= eps || !qFuzzyCompare( x2, x ) )
            x2 = x;
    }
 
    return QwtInterval( x1, x2 );
}
 
QwtLogScaleEngine::QwtLogScaleEngine( uint base ):
    QwtScaleEngine( base )
{
    setTransformation( new QwtLogTransform() );
}
 
QwtLogScaleEngine::~QwtLogScaleEngine()
{
}
 
void QwtLogScaleEngine::autoScale( int maxNumSteps,
    double& x1, double& x2, double& stepSize ) const
{
    if ( x1 > x2 )
        qSwap( x1, x2 );
 
    const double logBase = base();
 
    QwtInterval interval( x1 / std::pow( logBase, lowerMargin() ),
        x2 * std::pow( logBase, upperMargin() ) );
 
    if ( interval.maxValue() / interval.minValue() < logBase )
    {
        // scale width is less than one step -> try to build a linear scale
 
        QwtLinearScaleEngine linearScaler;
        linearScaler.setAttributes( attributes() );
        linearScaler.setReference( reference() );
        linearScaler.setMargins( lowerMargin(), upperMargin() );
 
        linearScaler.autoScale( maxNumSteps, x1, x2, stepSize );
 
        QwtInterval linearInterval = QwtInterval( x1, x2 ).normalized();
        linearInterval = linearInterval.limited(
            QwtLogTransform::LogMin, QwtLogTransform::LogMax );
 
        if ( linearInterval.maxValue() / linearInterval.minValue() < logBase )
        {
            stepSize = 0.0;
            return;
        }
    }
 
    double logRef = 1.0;
    if ( reference() > QwtLogTransform::LogMin / 2 )
        logRef = qwtMinF( reference(), QwtLogTransform::LogMax / 2 );
 
    if ( testAttribute( QwtScaleEngine::Symmetric ) )
    {
        const double delta = qwtMaxF( interval.maxValue() / logRef,
            logRef / interval.minValue() );
        interval.setInterval( logRef / delta, logRef * delta );
    }
 
    if ( testAttribute( QwtScaleEngine::IncludeReference ) )
        interval = interval.extend( logRef );
 
    interval = interval.limited( QwtLogTransform::LogMin, QwtLogTransform::LogMax );
 
    if ( interval.width() == 0.0 )
        interval = buildInterval( interval.minValue() );
 
    stepSize = divideInterval( qwtLogInterval( logBase, interval ).width(),
        qMax( maxNumSteps, 1 ) );
    if ( stepSize < 1.0 )
        stepSize = 1.0;
 
    if ( !testAttribute( QwtScaleEngine::Floating ) )
        interval = align( interval, stepSize );
 
    x1 = interval.minValue();
    x2 = interval.maxValue();
 
    if ( testAttribute( QwtScaleEngine::Inverted ) )
    {
        qSwap( x1, x2 );
        stepSize = -stepSize;
    }
}
 
QwtScaleDiv QwtLogScaleEngine::divideScale( double x1, double x2,
    int maxMajorSteps, int maxMinorSteps, double stepSize ) const
{
    QwtInterval interval = QwtInterval( x1, x2 ).normalized();
    interval = interval.limited( QwtLogTransform::LogMin, QwtLogTransform::LogMax );
 
    if ( interval.width() <= 0 )
        return QwtScaleDiv();
 
    const double logBase = base();
 
    if ( interval.maxValue() / interval.minValue() < logBase )
    {
        // scale width is less than one decade -> build linear scale
 
        QwtLinearScaleEngine linearScaler;
        linearScaler.setAttributes( attributes() );
        linearScaler.setReference( reference() );
        linearScaler.setMargins( lowerMargin(), upperMargin() );
 
        return linearScaler.divideScale( x1, x2,
            maxMajorSteps, maxMinorSteps, 0.0 );
    }
 
    stepSize = qAbs( stepSize );
    if ( stepSize == 0.0 )
    {
        if ( maxMajorSteps < 1 )
            maxMajorSteps = 1;
 
        stepSize = divideInterval(
            qwtLogInterval( logBase, interval ).width(), maxMajorSteps );
        if ( stepSize < 1.0 )
            stepSize = 1.0; // major step must be >= 1 decade
    }
 
    QwtScaleDiv scaleDiv;
    if ( stepSize != 0.0 )
    {
        QList< double > ticks[QwtScaleDiv::NTickTypes];
        buildTicks( interval, stepSize, maxMinorSteps, ticks );
 
        scaleDiv = QwtScaleDiv( interval, ticks );
    }
 
    if ( x1 > x2 )
        scaleDiv.invert();
 
    return scaleDiv;
}
 
void QwtLogScaleEngine::buildTicks(
    const QwtInterval& interval, double stepSize, int maxMinorSteps,
    QList< double > ticks[QwtScaleDiv::NTickTypes] ) const
{
    const QwtInterval boundingInterval = align( interval, stepSize );
 
    ticks[QwtScaleDiv::MajorTick] =
        buildMajorTicks( boundingInterval, stepSize );
 
    if ( maxMinorSteps > 0 )
    {
        buildMinorTicks( ticks[QwtScaleDiv::MajorTick], maxMinorSteps, stepSize,
            ticks[QwtScaleDiv::MinorTick], ticks[QwtScaleDiv::MediumTick] );
    }
 
    for ( int i = 0; i < QwtScaleDiv::NTickTypes; i++ )
        ticks[i] = strip( ticks[i], interval );
}
 
QList< double > QwtLogScaleEngine::buildMajorTicks(
    const QwtInterval& interval, double stepSize ) const
{
    double width = qwtLogInterval( base(), interval ).width();
 
    int numTicks = qRound( width / stepSize ) + 1;
    if ( numTicks > 10000 )
        numTicks = 10000;
 
    const double lxmin = std::log( interval.minValue() );
    const double lxmax = std::log( interval.maxValue() );
    const double lstep = ( lxmax - lxmin ) / double( numTicks - 1 );
 
    QList< double > ticks;
    ticks.reserve( numTicks );
 
    ticks += interval.minValue();
 
    for ( int i = 1; i < numTicks - 1; i++ )
        ticks += std::exp( lxmin + double( i ) * lstep );
 
    ticks += interval.maxValue();
 
    return ticks;
}
 
void QwtLogScaleEngine::buildMinorTicks(
    const QList< double >& majorTicks,
    int maxMinorSteps, double stepSize,
    QList< double >& minorTicks,
    QList< double >& mediumTicks ) const
{
    const double logBase = base();
 
    if ( stepSize < 1.1 )          // major step width is one base
    {
        double minStep = divideInterval( stepSize, maxMinorSteps + 1 );
        if ( minStep == 0.0 )
            return;
 
        const int numSteps = qRound( stepSize / minStep );
 
        int mediumTickIndex = -1;
        if ( ( numSteps > 2 ) && ( numSteps % 2 == 0 ) )
            mediumTickIndex = numSteps / 2;
 
        for ( int i = 0; i < majorTicks.count() - 1; i++ )
        {
            const double v = majorTicks[i];
            const double s = logBase / numSteps;
 
            if ( s >= 1.0 )
            {
                if ( !qFuzzyCompare( s, 1.0 ) )
                    minorTicks += v * s;
 
                for ( int j = 2; j < numSteps; j++ )
                {
                    minorTicks += v * j * s;
                }
            }
            else
            {
                for ( int j = 1; j < numSteps; j++ )
                {
                    const double tick = v + j * v * ( logBase - 1 ) / numSteps;
                    if ( j == mediumTickIndex )
                        mediumTicks += tick;
                    else
                        minorTicks += tick;
                }
            }
        }
    }
    else
    {
        double minStep = divideInterval( stepSize, maxMinorSteps );
        if ( minStep == 0.0 )
            return;
 
        if ( minStep < 1.0 )
            minStep = 1.0;
 
        // # subticks per interval
        int numTicks = qRound( stepSize / minStep ) - 1;
 
        // Do the minor steps fit into the interval?
        if ( qwtFuzzyCompare( ( numTicks + 1 ) * minStep,
            stepSize, stepSize ) > 0 )
        {
            numTicks = 0;
        }
 
        if ( numTicks < 1 )
            return;
 
        int mediumTickIndex = -1;
        if ( ( numTicks > 2 ) && ( numTicks % 2 ) )
            mediumTickIndex = numTicks / 2;
 
        // substep factor = base^substeps
        const qreal minFactor = qwtMaxF( std::pow( logBase, minStep ), logBase );
 
        for ( int i = 0; i < majorTicks.count(); i++ )
        {
            double tick = majorTicks[i];
            for ( int j = 0; j < numTicks; j++ )
            {
                tick *= minFactor;
 
                if ( j == mediumTickIndex )
                    mediumTicks += tick;
                else
                    minorTicks += tick;
            }
        }
    }
}
 
QwtInterval QwtLogScaleEngine::align(
    const QwtInterval& interval, double stepSize ) const
{
    const QwtInterval intv = qwtLogInterval( base(), interval );
 
    double x1 = QwtScaleArithmetic::floorEps( intv.minValue(), stepSize );
    if ( qwtFuzzyCompare( interval.minValue(), x1, stepSize ) == 0 )
        x1 = interval.minValue();
 
    double x2 = QwtScaleArithmetic::ceilEps( intv.maxValue(), stepSize );
    if ( qwtFuzzyCompare( interval.maxValue(), x2, stepSize ) == 0 )
        x2 = interval.maxValue();
 
    return qwtPowInterval( base(), QwtInterval( x1, x2 ) );
}