Changeset - 7dd5ac90961f
[Not reviewed]
Hasan Yavuz ÖZDERYA - 7 years ago 2018-09-25 16:38:30
hy@ozderya.net
optimized search for findIndex
7 files changed with 59 insertions and 18 deletions:
0 comments (0 inline, 0 general)
src/framebuffer.h
Show inline comments
 
@@ -40,25 +40,45 @@ public:
 
    virtual double sample(unsigned i) const = 0;
 
    /// Returns minimum and maximum of the buffer values.
 
    virtual Range limits() const = 0;
 
};
 

	
 
/// Common base class for index and writable frame buffers
 
class ResizableBuffer : public FrameBuffer
 
{
 
public:
 
    /// Resize the buffer.
 
    ///
 
    /// @important Resizing to same value is an error.
 
    virtual void resize(unsigned n) = 0;
 
};
 

	
 
/// Abstract base class for writable frame buffers
 
class WFrameBuffer : public ResizableBuffer
 
{
 
    /// Add samples to the buffer
 
    virtual void addSamples(double* samples, unsigned n) = 0;
 
    /// Reset all data to 0
 
    virtual void clear() = 0;
 
};
 

	
 
/**
 
 * Abstract base class for X buffers.
 
 *
 
 * These buffers only contain increasing or equal (to previous) values.
 
 */
 
class XFrameBuffer : public ResizableBuffer
 
{
 
public:
 
    enum Index {OUT_OF_RANGE = -1};
 

	
 
    /**
 
     * Finds index for given value.
 
     *
 
     * If given value is bigger than max or smaller than minimum
 
     * returns `OUT_OF_RANGE`. If it's in between values, smaller
 
     * index is returned (not closer one).
 
     */
 
    virtual int findIndex(double value) const = 0;
 
};
 

	
 
#endif // FRAMEBUFFER_H
src/indexbuffer.cpp
Show inline comments
 
/*
 
  Copyright © 2017 Hasan Yavuz Özderya
 
  Copyright © 2018 Hasan Yavuz Özderya
 

	
 
  This file is part of serialplot.
 

	
 
  serialplot is free software: you can redistribute it and/or modify
 
  it under the terms of the GNU General Public License as published by
 
  the Free Software Foundation, either version 3 of the License, or
 
  (at your option) any later version.
 

	
 
  serialplot is distributed in the hope that it will be useful,
 
  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
  GNU General Public License for more details.
 

	
 
  You should have received a copy of the GNU General Public License
 
  along with serialplot.  If not, see <http://www.gnu.org/licenses/>.
 
*/
 

	
 
#include <QtGlobal>
 

	
 
#include "indexbuffer.h"
 

	
 
IndexBuffer::IndexBuffer(unsigned n)
 
{
 
    _size = n;
 
}
 

	
 
unsigned IndexBuffer::size() const
 
{
 
    return _size;
 
}
 

	
 
void IndexBuffer::resize(unsigned n)
 
{
 
    _size = n;
 
}
 

	
 
double IndexBuffer::sample(unsigned i) const
 
{
 
    Q_ASSERT(i < _size);
 

	
 
    return i;
 
}
 

	
 
Range IndexBuffer::limits() const
 
{
 
    return Range{0, _size-1.};
 
}
 

	
 
int IndexBuffer::findIndex(double value) const
 
{
 
    if (value < 0 || value > size() - 1)
 
    {
 
        return OUT_OF_RANGE;
 
    }
 
    else
 
    {
 
        return value;
 
    }
 
}
src/indexbuffer.h
Show inline comments
 
@@ -5,39 +5,40 @@
 

	
 
  serialplot is free software: you can redistribute it and/or modify
 
  it under the terms of the GNU General Public License as published by
 
  the Free Software Foundation, either version 3 of the License, or
 
  (at your option) any later version.
 

	
 
  serialplot is distributed in the hope that it will be useful,
 
  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
  GNU General Public License for more details.
 

	
 
  You should have received a copy of the GNU General Public License
 
  along with serialplot.  If not, see <http://www.gnu.org/licenses/>.
 
*/
 

	
 
#ifndef INDEXBUFFER_H
 
#define INDEXBUFFER_H
 

	
 
#include "framebuffer.h"
 

	
 
/// A simple frame buffer that simply returns requested index as
 
/// sample value.
 
///
 
/// @note This buffer isn't for storing data.
 
class IndexBuffer : public ResizableBuffer
 
class IndexBuffer : public XFrameBuffer
 
{
 
public:
 
    IndexBuffer(unsigned n);
 

	
 
    unsigned size() const;
 
    double sample(unsigned i) const;
 
    Range limits() const;
 
    void resize(unsigned n);
 
    unsigned size() const override;
 
    double sample(unsigned i) const override;
 
    Range limits() const override;
 
    void resize(unsigned n) override;
 
    int findIndex(double value) const override;
 

	
 
private:
 
    unsigned _size;
 
};
 

	
 
#endif
src/stream.cpp
Show inline comments
 
@@ -10,49 +10,50 @@
 

	
 
  serialplot is distributed in the hope that it will be useful,
 
  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
  GNU General Public License for more details.
 

	
 
  You should have received a copy of the GNU General Public License
 
  along with serialplot.  If not, see <http://www.gnu.org/licenses/>.
 
*/
 

	
 
#include "stream.h"
 
#include "ringbuffer.h"
 
#include "indexbuffer.h"
 

	
 
Stream::Stream(unsigned nc, bool x, unsigned ns) :
 
    _infoModel(nc)
 
{
 
    _numSamples = ns;
 
    _paused = false;
 

	
 
    // create xdata buffer
 
    _hasx = x;
 
    if (x)
 
    {
 
        xData = new RingBuffer(ns);
 
        // TODO: implement XRingBuffer (binary search)
 
        Q_ASSERT(false);
 
    }
 
    else
 
    {
 
        xData = new IndexBuffer(ns);
 
    }
 

	
 
    // create channels
 
    for (unsigned i = 0; i < nc; i++)
 
    {
 
        auto c = new StreamChannel(i, xData, new RingBuffer(ns), &_infoModel);
 
        channels.append(c);
 
    }
 
}
 

	
 
Stream::~Stream()
 
{
 
    for (auto ch : channels)
 
    {
 
        delete ch;
 
    }
 
    delete xData;
 
}
 

	
 
bool Stream::hasX() const
 
@@ -97,49 +98,50 @@ void Stream::setNumChannels(unsigned nc,
 
    if (oldNum == nc && x == _hasx) return;
 

	
 
    // adjust the number of channels
 
    if (nc > oldNum)
 
    {
 
        for (unsigned i = oldNum; i < nc; i++)
 
        {
 
            auto c = new StreamChannel(i, xData, new RingBuffer(_numSamples), &_infoModel);
 
            channels.append(c);
 
        }
 
    }
 
    else if (nc < oldNum)
 
    {
 
        for (unsigned i = oldNum-1; i > nc-1; i--)
 
        {
 
            delete channels.takeLast();
 
        }
 
    }
 

	
 
    // change the xdata
 
    if (x != _hasx)
 
    {
 
        if (x)
 
        {
 
            xData = new RingBuffer(_numSamples);
 
            // TODO: implement XRingBuffer (binary search)
 
            Q_ASSERT(false);
 
        }
 
        else
 
        {
 
            xData = new IndexBuffer(_numSamples);
 
        }
 

	
 
        for (auto c : channels)
 
        {
 
            c->setX(xData);
 
        }
 
        _hasx = x;
 
    }
 

	
 
    if (nc != oldNum)
 
    {
 
        _infoModel.setNumOfChannels(nc);
 
        // TODO: how about X change?
 
        emit numChannelsChanged(nc);
 
    }
 

	
 
    Sink::setNumChannels(nc, x);
 
}
 

	
 
const SamplePack* Stream::applyGainOffset(const SamplePack& pack) const
 
@@ -170,49 +172,51 @@ const SamplePack* Stream::applyGainOffse
 
            }
 
            if (offsetEn)
 
            {
 
                for (unsigned i = 0; i < ns; i++)
 
                {
 
                    mdata[i] += offset;
 
                }
 
            }
 
        }
 
    }
 

	
 
    return mPack;
 
}
 

	
 
void Stream::feedIn(const SamplePack& pack)
 
{
 
    Q_ASSERT(pack.numChannels() == numChannels() &&
 
             pack.hasX() == hasX());
 

	
 
    if (_paused) return;
 

	
 
    unsigned ns = pack.numSamples();
 
    if (_hasx)
 
    {
 
        static_cast<RingBuffer*>(xData)->addSamples(pack.xData(), ns);
 
        // TODO: implement XRingBuffer (binary search)
 
        Q_ASSERT(false);
 
        // static_cast<RingBuffer*>(xData)->addSamples(pack.xData(), ns);
 
    }
 

	
 
    // modified pack that gain and offset is applied to
 
    const SamplePack* mPack = nullptr;
 
    if (infoModel()->gainOrOffsetEn())
 
        mPack = applyGainOffset(pack);
 

	
 
    for (unsigned ci = 0; ci < numChannels(); ci++)
 
    {
 
        auto buf = static_cast<RingBuffer*>(channels[ci]->yData());
 
        double* data = (mPack == nullptr) ? pack.data(ci) : mPack->data(ci);
 
        buf->addSamples(data, ns);
 
    }
 

	
 
    Sink::feedIn((mPack == nullptr) ? pack : *mPack);
 

	
 
    if (mPack != nullptr) delete mPack;
 
    emit dataAdded();
 
}
 

	
 
void Stream::pause(bool paused)
 
{
 
    _paused = paused;
 
}
src/stream.h
Show inline comments
 
@@ -72,45 +72,45 @@ protected:
 

	
 
signals:
 
    void numChannelsChanged(unsigned value);
 
    void numSamplesChanged(unsigned value);
 
    void channelAdded(const StreamChannel* chan);
 
    void channelNameChanged(unsigned channel, QString name); // TODO: does it stay?
 
    void dataAdded(); ///< emitted when data added to channel man.
 

	
 
public slots:
 
    // TODO: these won't be public
 
    // void setNumChannels(unsigned number);
 
    void setNumSamples(unsigned value);
 

	
 
    /// When paused data feed is ignored
 
    void pause(bool paused);
 

	
 
    /// Clears buffer data (fills with 0)
 
    void clear();
 

	
 
private:
 
    unsigned _numSamples;
 
    bool _paused;
 

	
 
    bool _hasx;
 
    ResizableBuffer* xData;
 
    XFrameBuffer* xData;
 
    QList<StreamChannel*> channels;
 

	
 
    ChannelInfoModel _infoModel;
 

	
 
    /**
 
     * Applies gain and offset to given pack.
 
     *
 
     * Caller is responsible for deleting returned `SamplePack`.
 
     *
 
     * @note Should be called only when gain or offset is enabled. Guard with
 
     * `ChannelInfoModel::gainOrOffsetEn()`.
 
     *
 
     * @param pack input data
 
     * @return modified data
 
     */
 
    const SamplePack* applyGainOffset(const SamplePack& pack) const;
 
};
 

	
 

	
 
#endif // STREAM_H
src/streamchannel.cpp
Show inline comments
 
/*
 
  Copyright © 2018 Hasan Yavuz Özderya
 

	
 
  This file is part of serialplot.
 

	
 
  serialplot is free software: you can redistribute it and/or modify
 
  it under the terms of the GNU General Public License as published by
 
  the Free Software Foundation, either version 3 of the License, or
 
  (at your option) any later version.
 

	
 
  serialplot is distributed in the hope that it will be useful,
 
  but WITHOUT ANY WARRANTY; without even the implied warranty of
 
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
  GNU General Public License for more details.
 

	
 
  You should have received a copy of the GNU General Public License
 
  along with serialplot.  If not, see <http://www.gnu.org/licenses/>.
 
*/
 

	
 
#include <limits>
 
#include "streamchannel.h"
 

	
 
StreamChannel::StreamChannel(unsigned i, const FrameBuffer* x,
 
StreamChannel::StreamChannel(unsigned i, const XFrameBuffer* x,
 
              FrameBuffer* y, ChannelInfoModel* info)
 
{
 
    _index = i;
 
    _x = x;
 
    _y = y;
 
    _info = info;
 
}
 

	
 
StreamChannel::~StreamChannel()
 
{
 
    delete _y;
 
}
 

	
 
unsigned StreamChannel::index() const {return _index;}
 
QString StreamChannel::name() const {return _info->name(_index);};
 
QColor StreamChannel::color() const {return _info->color(_index);};
 
bool StreamChannel::visible() const {return _info->isVisible(_index);};
 
const FrameBuffer* StreamChannel::xData() const {return _x;}
 
const XFrameBuffer* StreamChannel::xData() const {return _x;}
 
const FrameBuffer* StreamChannel::yData() const {return _y;}
 
FrameBuffer* StreamChannel::yData() {return _y;}
 
const ChannelInfoModel* StreamChannel::info() const {return _info;}
 
void StreamChannel::setX(const FrameBuffer* x) {_x = x;};
 
void StreamChannel::setX(const XFrameBuffer* x) {_x = x;};
 

	
 
#include <QtDebug>
 

	
 
double StreamChannel::findValue(double x) const
 
{
 
    int index = findIndex(x);
 
    // int index = findIndex(x);
 
    int index = _x->findIndex(x);
 
    qDebug() << x << ":" << index;
 
    if (index >= 0)
 
        return _y->sample(index);
 
    else
 
        return std::numeric_limits<double>::quiet_NaN();
 
}
 

	
 
int StreamChannel::findIndex(double x) const
 
{
 
    // TODO: optimize, implement in `framebuffer`
 
    bool first = true;
 
    for (int i = _x->size()-1; i > 0; i--)
 
    {
 
        double val = _x->sample(i);
 
        if (x >= val)
 
        {
 
            // TODO: optional linear approx. method
 
            // check if previous sample (bigger one) is actually closer
 
            if (!first && (x - val) > (_x->sample(i + 1) - x))
 
            {
 
                ++i;
 
            }
 

	
 
            return i;
 
        }
src/streamchannel.h
Show inline comments
 
@@ -14,53 +14,53 @@
 
  GNU General Public License for more details.
 

	
 
  You should have received a copy of the GNU General Public License
 
  along with serialplot.  If not, see <http://www.gnu.org/licenses/>.
 
*/
 

	
 
#ifndef STREAMCHANNEL_H
 
#define STREAMCHANNEL_H
 

	
 
#include "framebuffer.h"
 
#include "channelinfomodel.h"
 

	
 
class StreamChannel
 
{
 
public:
 
    /**
 
     * Creates a stream channel.
 
     *
 
     * @param i index of the channel
 
     * @param x x axis buffer
 
     * @param y data buffer of this channel, takes ownership
 
     * @param info channel info model
 
     */
 
    StreamChannel(unsigned i,
 
                  const FrameBuffer* x,
 
                  const XFrameBuffer* x,
 
                  FrameBuffer* y,
 
                  ChannelInfoModel* info);
 
    ~StreamChannel();
 

	
 
    unsigned index() const;
 
    QString name() const;
 
    QColor color() const;
 
    bool visible() const;
 
    const FrameBuffer* xData() const;
 
    const XFrameBuffer* xData() const;
 
    FrameBuffer* yData();
 
    const FrameBuffer* yData() const;
 
    const ChannelInfoModel* info() const;
 
    void setX(const FrameBuffer* x);
 
    void setX(const XFrameBuffer* x);
 

	
 
    /// Returns sample value for closest X
 
    double findValue(double x) const;
 

	
 
private:
 
    unsigned _index;
 
    const FrameBuffer* _x;
 
    const XFrameBuffer* _x;
 
    FrameBuffer* _y;
 
    ChannelInfoModel* _info;
 

	
 
    /// Finds index of closest X in `xData`
 
    int findIndex(double x) const;
 
};
 

	
 
#endif // STREAMCHANNEL_H
0 comments (0 inline, 0 general)