src/SlidingWindow.cpp

#include "SlidingWindow.h"

SlidingWindow::SlidingWindow()
    : SlidingWindow(300000000000LL, 2048, 32768, 200000, 1)
{}

SlidingWindow::SlidingWindow(int64_t windowSize, size_t capacity, size_t maxCapacity,
                             int64_t medianBufferCapacity, int64_t mediamBufferTickSize)
  : mLoBuffer(maxCapacity)
  , mHiBuffer(maxCapacity)
  , mWindowSize(windowSize)
  , mMeanSum(0)
  , mMedianBasePx(0)
  , mMedianOffset(0)
  , mMedianBufferCapacity(medianBufferCapacity)
  , mMediamBufferTickSize(mediamBufferTickSize)
  , mCapacity(capacity)
  , mMaxCapacity(maxCapacity)
  , mHead(0)
  , mTail(0)
{
    assert(mCapacity > 0);
    assert(mMedianBufferCapacity > 0);
    assert(mMediamBufferTickSize > 0);
    assert(mWindowSize >= 1000000000LL);
    assert((mCapacity & (mCapacity - 1)) == 0);
    assert(mMaxCapacity >= mCapacity);
    assert((mMaxCapacity & (mMaxCapacity - 1)) == 0);
    mWindow.resize(mCapacity);
    mMedianBuffer.resize(mMedianBufferCapacity / mediamBufferTickSize);
}

std::pair<bool, SlidingWindowData> SlidingWindow::push(const TickEntry& tick)
{
    if(getSize() + 1 == mCapacity && !grow()) return {false, mSlidingWindowData};
    if(mMedianBasePx == 0)
    {
        mMedianBasePx = tick.mPrice;
        mMedianOffset = (mMedianBasePx - (mMedianBufferCapacity  * 0.5) * PX_MAGNITUDE[4]);
        if(mMedianOffset < 0) return {false, mSlidingWindowData};
    }

    mWindow[mTail] = tick;
    mTail = (mTail + 1) & (mCapacity - 1);

    while(mLoBuffer.size() && mLoBuffer.back().mPrice > tick.mPrice)
        mLoBuffer.pop_back();
    mLoBuffer.push_back(tick);

    while(mHiBuffer.size() && mHiBuffer.back().mPrice < tick.mPrice)
        mHiBuffer.pop_back();
    mHiBuffer.push_back(tick);

    mMedianBuffer[getMedianIdx(tick.mPrice)]++;
    pop();
    
    mMeanSum += tick.mPrice;
    mSlidingWindowData.mMean = (mMeanSum / (getSize() * PX_MAGNITUDE[4])) * PX_MAGNITUDE[4]; //trimming to first 2 frac digits
    mSlidingWindowData.mMedian = getMedian();
    mSlidingWindowData.mLow = getLow();
    mSlidingWindowData.mHigh = getHigh();

    return {true, mSlidingWindowData};
}

std::pair<TickEntry, SlidingWindowData> SlidingWindow::getTail()
{
    return {mWindow[(mTail - 1) & (mCapacity - 1)], mSlidingWindowData};
}

std::pair<TickEntry, SlidingWindowData> SlidingWindow::getHead()
{
    return {mWindow[mHead], mSlidingWindowData};
}

std::vector<TickEntry> SlidingWindow::getWindow()
{
    const size_t size = getSize();
    std::vector<TickEntry> buf(size);
    
    for(size_t i = 0; i < size; i++)
        buf[i] = mWindow[(mHead + i) & (mCapacity - 1)];
    return buf;
}

size_t SlidingWindow::getSize()
{
    return (mTail - mHead) & (mCapacity - 1);
}

size_t SlidingWindow::getCapacity()
{
    return mCapacity;
}

void SlidingWindow::pop()
{
    const auto tail = mWindow[(mTail - 1) & (mCapacity - 1)];
    while(getSize() && tail.mTsNano - mWindow[mHead].mTsNano > mWindowSize)
    {
        const TickEntry& tick = mWindow[mHead];
        mMeanSum -= tick.mPrice;

        if(mLoBuffer.size() && mLoBuffer.front() == tick) mLoBuffer.pop_front();
        if(mHiBuffer.size() && mHiBuffer.front() == tick) mHiBuffer.pop_front();

        mMedianBuffer[getMedianIdx(tick.mPrice)]--;

        mHead = (mHead + 1) & (mCapacity - 1);
    }
}

bool SlidingWindow::grow()
{
    if(mCapacity == mMaxCapacity) return false;

    std::vector<TickEntry> buf(mCapacity * 2);

    const size_t size = getSize();
    for(size_t i = 0; i < size; i++)
        buf[i] = mWindow[(mHead + i) & (mCapacity - 1)];

    mWindow = std::move(buf);
    mHead = 0;
    mTail = size;
    mCapacity *= 2;

    return true;
}

int64_t SlidingWindow::getMedianIdx(int64_t px)
{
    int64_t idx = (px - mMedianOffset) / (mMediamBufferTickSize * PX_MAGNITUDE[4]);
    //char arr[32];
    //Helper::parseFromPx(px, arr);
    //std::cout << idx << ' ' << mMedianBufferCapacity << ' ' << arr << ' ' << px << ' ' << mMedianOffset << ' ' << mMediamBufferTickSize << '\n';
    //assert(idx >= 0);
    //assert(idx < (mMedianBufferCapacity / mMediamBufferTickSize));
    return idx;
}

int64_t SlidingWindow::getMedian()
{
    if(!mLoBuffer.size() || !mHiBuffer.size()) return 0;

    int64_t loPx = mLoBuffer.front().mPrice;
    int64_t hiPx = mHiBuffer.front().mPrice;
    int64_t midPriceCnt = 0;
    int64_t mask = getSize() / 2;
    auto loPxIdx = getMedianIdx(loPx);
    auto hiPxIdx = getMedianIdx(hiPx);

    for(int64_t i = loPxIdx; i <= hiPxIdx; i++)
    {
        midPriceCnt += mMedianBuffer[i];
        if(midPriceCnt > mask)
            return i * (mMediamBufferTickSize * PX_MAGNITUDE[4]) + mMedianOffset;
    }

    return 0;
}

int64_t SlidingWindow::getLow()
{
    if(!mLoBuffer.size()) return 0;
    return mLoBuffer.front().mPrice;
}

int64_t SlidingWindow::getHigh()
{
    if(!mHiBuffer.size()) return 0;
    return mHiBuffer.front().mPrice;
}