#pragma once

#include <vector>
#include <math.h>

namespace Incart::Common
{

class MedianDetector
{
private:
  const size_t m_valueCount;
  const size_t m_meanPointCount;
  const size_t m_lastValueIndex;
  const size_t m_medianIndex;
  size_t m_currValueCount = 0;
  std::vector<int> m_sourceValues;
  std::vector<int> m_sortedValues;
  double m_median = 0.0;
  size_t m_insertSourceIndex = 0;

public:
  MedianDetector(size_t count_, size_t meanPointCount_)
    : m_valueCount(count_)
    , m_meanPointCount(meanPointCount_)
    , m_lastValueIndex(count_ - 1)
    , m_medianIndex(count_ / 2)
    , m_sourceValues(count_)
    , m_sortedValues(count_)
  {
  }

  double getMedian() const
  {
    return m_median;
  }

  size_t getCount() const
  {
    return m_currValueCount;
  }

  void clear()
  {
    m_median = 0;
    m_currValueCount = 0;
    m_insertSourceIndex = 0;
  }

  void addValue(int newValue_) {
    if (m_currValueCount < m_valueCount) {
      m_sourceValues[m_currValueCount] = newValue_;
      sortNotFullArray(newValue_);
      calcMedianByNotFullArray();
      m_currValueCount++;
    }
    else {
      if (m_insertSourceIndex == m_valueCount) {
        m_insertSourceIndex = 0;
      }
      int deletedValue = m_sourceValues[m_insertSourceIndex];
      m_sourceValues[m_insertSourceIndex] = newValue_;
      sortFullArray(newValue_, deletedValue);
      calcMedianByFullArray();
      m_insertSourceIndex++;
    }
  }

private:
  void calcMedianByNotFullArray() {

    size_t meanIndex = (m_currValueCount + 1) / 2;
    long long lowBorderIndex = meanIndex - m_meanPointCount;
    if (lowBorderIndex < 0)
    {
      lowBorderIndex = 0;
    }
    long long upBorderIndex = meanIndex + m_meanPointCount;
    if (upBorderIndex > static_cast<long long>(m_currValueCount))
    {
      upBorderIndex = m_currValueCount;
    }
    long sumValue = 0;
    for (int i = lowBorderIndex; i <= upBorderIndex; i++) {
      sumValue += m_sortedValues[i];
    }
    m_median = static_cast<double>(sumValue) / (upBorderIndex - lowBorderIndex + 1);
  }

  void calcMedianByFullArray() {
    long long lowBorderIndex = static_cast<long long>(m_medianIndex) - m_meanPointCount;
    if (lowBorderIndex < 0) {
      lowBorderIndex = 0;
    }
    long long upBorderIndex = static_cast<long long>(m_medianIndex) + m_meanPointCount;
    if (upBorderIndex >= static_cast<long long>(m_valueCount)) {
      upBorderIndex = static_cast<int>(m_lastValueIndex);
    }
    long sumValue = 0;
    for (int i = lowBorderIndex; i <= upBorderIndex; i++) {
      sumValue += m_sortedValues[i];
    }
    m_median = static_cast<double>(sumValue) / (upBorderIndex - lowBorderIndex + 1);
  }

  void sortNotFullArray(int newValue_) {
    m_sortedValues[m_currValueCount] = newValue_;
    long long insertedIndex = static_cast<long long>(m_currValueCount) - 1;
    for (; (insertedIndex >= 0) && (m_sortedValues[insertedIndex] > newValue_); --insertedIndex) {
      m_sortedValues[insertedIndex + 1] = m_sortedValues[insertedIndex];
      m_sortedValues[insertedIndex] = newValue_;
    }
  }

  void sortFullArray(int newValue_, int deletedValue_)
  {
    if (newValue_ == deletedValue_)
    {
      return;
    }
    size_t insertIndex = 0;
    if (newValue_ > deletedValue_)
    {
      // move items to left
      insertIndex = searchLeftMoveIndex(newValue_, 0, m_lastValueIndex);
      size_t deleteIndex = insertIndex;
      if (m_sortedValues[insertIndex] != deletedValue_)
      {
        deleteIndex = searchRightMoveIndex(deletedValue_, 0, insertIndex - 1);
      }
      for (long long i = static_cast<long long>(deleteIndex) + 1; i <= static_cast<long long>(insertIndex); ++i)
      {
        m_sortedValues[i - 1] = m_sortedValues[i];
      }
    }
    else {
      // move items to right
      insertIndex = searchRightMoveIndex(newValue_, 0, m_lastValueIndex);
      size_t deleteIndex = insertIndex;
      if (m_sortedValues[insertIndex] != deletedValue_)
      {
        deleteIndex = searchLeftMoveIndex(deletedValue_, insertIndex + 1, m_lastValueIndex);
      }
      for (int i = static_cast<int>(deleteIndex) - 1; i >= static_cast<int>(insertIndex); --i) {
        m_sortedValues[i + 1] = m_sortedValues[i];
      }
    }
    m_sortedValues[insertIndex] = newValue_;
  }

  size_t searchLeftMoveIndex(int searchValue_, size_t lowBorderIndex_, size_t upBorderIndex_) const
  {
    while (true)
    {
      if (lowBorderIndex_ == upBorderIndex_ - 1)
      {
        if (m_sortedValues[upBorderIndex_] <= searchValue_)
        {
          return upBorderIndex_;
        }
        else if (m_sortedValues[lowBorderIndex_] <= searchValue_)
        {
          return lowBorderIndex_;
        }
        else
        {
          return lowBorderIndex_ - 1; // leftMove гарантирует что слева есть еще эл-ты
        }
      }
      else if (lowBorderIndex_ == upBorderIndex_)
      {
        if (m_sortedValues[lowBorderIndex_] <= searchValue_)
        {
          return lowBorderIndex_;
        }
        else
        {
          return lowBorderIndex_ - 1; // leftMove гарантирует что слева есть еще эл-ты
        }
      }
      else
      {
        size_t meanIndex = (upBorderIndex_ + lowBorderIndex_) / 2;
        if (m_sortedValues[meanIndex] == searchValue_)
        {
          return meanIndex;
        }
        else if (m_sortedValues[meanIndex] > searchValue_)
        {
          upBorderIndex_ = meanIndex;
        }
        else
        {
          lowBorderIndex_ = meanIndex;
        }
      }
    }
  }

  size_t searchRightMoveIndex(int searchValue_, size_t lowBorderIndex_, size_t upBorderIndex_) const
  {
    while (true)
    {
      if (lowBorderIndex_ == upBorderIndex_ - 1)
      {
        if (m_sortedValues[lowBorderIndex_] >= searchValue_)
        {
          return lowBorderIndex_;
        }
        else if (m_sortedValues[upBorderIndex_] >= searchValue_)
        {
          return upBorderIndex_;
        }
        else
        {
          return upBorderIndex_ + 1; // rightMove гарантирует что справа есть еще эл-ты
        }
      }
      else if (lowBorderIndex_ == upBorderIndex_)
      {
        if (m_sortedValues[lowBorderIndex_] >= searchValue_)
        {
          return lowBorderIndex_;
        }
        else
        {
          return lowBorderIndex_ + 1; // rightMove гарантирует что справа есть еще эл-ты
        }
      }
      else
      {
        size_t meanIndex = (upBorderIndex_ + lowBorderIndex_) / 2;
        if (m_sortedValues[meanIndex] == searchValue_)
        {
          return meanIndex;
        }
        else if (m_sortedValues[meanIndex] > searchValue_)
        {
          upBorderIndex_ = meanIndex;
        }
        else
        {
          lowBorderIndex_ = meanIndex;
        }
      }
    }
  }
};

} // namespace Incart::Common