#include "rive/math/rectangles_to_contour.hpp"
#include <algorithm>

using namespace rive;

using RectEvent = RectanglesToContour::RectEvent;

class SpanOffset
{
public:
  size_t start;
  size_t size;

  Span<RectEvent> toSpan(Span<RectEvent> base)
  {
    return Span<RectEvent>(base.data() + start, size);
  }
};

// The axis is data, not a separate lambda, so each element type needs only one
// std::sort instantiation.
struct RectEventAxisLess
{
  uint8_t axis;
  bool operator()(const RectEvent& a, const RectEvent& b) const
  {
    return a.getValue(axis) < b.getValue(axis);
  }
};

struct PointLess
{
  int major;
  bool operator()(const Vec2D& a, const Vec2D& b) const
  {
    int minor = 1 - major;
    return a[major] < b[major] || (a[major] == b[major] && a[minor] < b[minor]);
  }
};

// Returns SpanOffset relative to result so it can be called in succession
// (re-allocating) prior to accessing data.
static SpanOffset sortRectEvents(
    const std::vector<AABB>& rects,
    std::vector<RectEvent>& result,
    uint8_t axisA,
    uint8_t axisB)
{
  size_t index = 0;

  size_t resultStart = result.size();

  for (const AABB& rect : rects)
  {
    for (size_t pointIndex = 0; pointIndex < 2; pointIndex++)
    {
      Vec2D e = rect[pointIndex];
      RectEvent event;
      event.type = (uint8_t)pointIndex;
      event.index = index;
      event.y = axisB == 0 ? e[axisA] : e[axisB];
      event.x = axisB == 0 ? e[axisB] : e[axisA];
      event.size = pointIndex == 0 ? rect[1][axisB] - e[axisB]
                                   : e[axisB] - rect[0][axisB];
      result.push_back(event);
    }
    ++index;
  }

  std::sort(
      result.begin() + resultStart,
      result.end(),
      RectEventAxisLess{axisB});
  std::sort(
      result.begin() + resultStart,
      result.end(),
      RectEventAxisLess{axisA});

  return {resultStart, result.size() - resultStart};
}

bool RectanglesToContour::isRectIncluded(size_t rectIndex)
{
  return (m_rectInclusionBitset[rectIndex / 8] & (1 << (rectIndex % 8))) != 0;
}

void RectanglesToContour::markRectIncluded(size_t rectIndex, bool isIt)
{
  if (isIt)
  {
    m_rectInclusionBitset[rectIndex / 8] |= 1 << (rectIndex % 8);
  }
  else
  {
    m_rectInclusionBitset[rectIndex / 8] &= ~(1 << (rectIndex % 8));
  }
}

void RectanglesToContour::subdivideRectangles()
{
  m_subdividedRects.clear();
  m_uniquePoints.clear();
  m_rectEvents.clear();

  if (m_rects.empty())
  {
    return;
  }

  auto evOffset = sortRectEvents(m_rects, m_rectEvents, 0, 1);
  auto ehOffset = sortRectEvents(m_rects, m_rectEvents, 1, 0);

  auto ev = evOffset.toSpan(m_rectEvents);
  auto eh = ehOffset.toSpan(m_rectEvents);

  size_t inclusionByteSize = m_rects.size() / 8 + 1;
  m_rectInclusionBitset.resize(inclusionByteSize);
  memset(m_rectInclusionBitset.data(), 0, inclusionByteSize);
  markRectIncluded(ev[0].index, true);

  int opened = 0;
  float beginY = 0;
  std::vector<AABB> result;

  for (size_t i = 0; i < ev.size() - 1; ++i)
  {
    const auto& eventV = ev[i];
    markRectIncluded(eventV.index, eventV.type == 0);
    const auto& next = ev[i + 1];
    float beginX = eventV.x;
    float endX = next.x;
    float deltaX = next.x - eventV.x;
    if (deltaX == 0)
    {
      continue;
    }

    for (size_t j = 0; j < eh.size(); ++j)
    {
      const auto& eventH = eh[j];
      if (isRectIncluded(eventH.index))
      {
        if (eventH.type == 0)
        {
          ++opened;
          if (opened == 1)
          {
            beginY = eventH.y;
          }
        }
        else
        {
          --opened;
          size_t n = 1;
          while (j + n < eh.size() && !isRectIncluded(eh[j + n].index))
          {
            ++n;
          }
          const auto* next = (j + n < eh.size()) ? &eh[j + n] : nullptr;
          if (!next || (opened == 0 && next->y != eventH.y))
          {
            float endY = eventH.y;
            m_subdividedRects.push_back(AABB(beginX, beginY, endX, endY));
          }
        }
      }
    }
  }
}

void RectanglesToContour::reset() { m_rects.clear(); }

void RectanglesToContour::addRect(const AABB& rect)
{
  if (!m_rects.empty())
  {
    AABB& last = m_rects.back();
    if (last.minY == rect.minY && last.maxY == rect.maxY &&
        last.maxX == rect.minX)
    {
      float minX = last.minX;
      float minY = last.minY;
      float maxY = last.maxY;

      m_rects.pop_back();
      m_rects.emplace_back(AABB(minX, minY, rect.maxX, maxY));
      return;
    }
  }
  m_rects.push_back(rect);
}

// Build contours and append them into contourPoints delineated by
// contourOffsets.
void extractPolygons(
    std::vector<ContourPoint>& contourPoints,
    std::vector<size_t>& contourOffsets,
    EdgeMap& edgesH,
    EdgeMap& edgesV)
{

  while (!edgesH.empty())
  {
    size_t contourStartOffset = contourPoints.size();
    Vec2D start = edgesH.begin()->first;
    edgesH.erase(start);

    auto first = ContourPoint(start, 0);
    contourPoints.push_back(first);

    while (true)
    {
      auto& curr = contourPoints.back();
      if (curr.dir == 0)
      {
        if (edgesV.find(curr.vec) != edgesV.end())
        {
          auto next = edgesV[curr.vec];
          edgesV.erase(curr.vec);
          contourPoints.emplace_back(next, 1);
        }
        else
        {
          break;
        }
      }
      else
      {
        if (edgesH.find(curr.vec) != edgesH.end())
        {
          auto next = edgesH[curr.vec];
          edgesH.erase(curr.vec);
          contourPoints.emplace_back(next, 0);
        }
        else
        {
          break;
        }
      }

      // Remove the last point if the first and last in the contour are
      // the same.
      if (first == contourPoints.back())
      {
        contourPoints.pop_back();
        break;
      }
    }

    contourOffsets.push_back(contourPoints.size());
    for (size_t index = contourStartOffset; index < contourPoints.size();
         index++)
    {
      Vec2D vertex = contourPoints[index].vec;
      edgesH.erase(vertex);
      edgesV.erase(vertex);
    }
  }
}

void RectanglesToContour::computeContours()
{
  subdivideRectangles();
  for (const auto& rect : m_subdividedRects)
  {
    addUniquePoint(Vec2D(rect.minX, rect.minY));
    addUniquePoint(Vec2D(rect.maxX, rect.minY));
    addUniquePoint(Vec2D(rect.maxX, rect.maxY));
    addUniquePoint(Vec2D(rect.minX, rect.maxY));
  }

  m_sortedPointsX.clear();
  m_sortedPointsY.clear();
  for (auto pt : m_uniquePoints)
  {
    m_sortedPointsX.push_back(pt);
    m_sortedPointsY.push_back(pt);
  }
  std::sort(m_sortedPointsX.begin(), m_sortedPointsX.end(), PointLess{0});
  std::sort(m_sortedPointsY.begin(), m_sortedPointsY.end(), PointLess{1});

  // std::unordered_map isn't guaranteed to reserve memory, so this clear
  // is more in prep for when we allow using allocators. We could also
  // experiment with a simple linear search in a vector as usually there
  // are not a lot of edges to traverse.
  m_edgesH.clear();
  m_edgesV.clear();

  size_t i = 0;
  while (i < m_sortedPointsY.size())
  {
    float currY = m_sortedPointsY[i].y;
    while (i < m_sortedPointsY.size() && m_sortedPointsY[i].y == currY)
    {
      m_edgesH[m_sortedPointsY[i]] = m_sortedPointsY[i + 1];
      m_edgesH[m_sortedPointsY[i + 1]] = m_sortedPointsY[i];
      i += 2;
    }
  }

  i = 0;
  while (i < m_sortedPointsX.size())
  {
    float currX = m_sortedPointsX[i].x;
    while (i < m_sortedPointsX.size() && m_sortedPointsX[i].x == currX)
    {
      m_edgesV[m_sortedPointsX[i]] = m_sortedPointsX[i + 1];
      m_edgesV[m_sortedPointsX[i + 1]] = m_sortedPointsX[i];
      i += 2;
    }
  }

  m_contourPoints.clear();
  m_contourOffsets.clear();
  extractPolygons(m_contourPoints, m_contourOffsets, m_edgesH, m_edgesV);
}

void RectanglesToContour::addUniquePoint(const Vec2D& point)
{
  if (!m_uniquePoints.insert(point).second)
  {
    m_uniquePoints.erase(point);
  }
}

ContourItr& ContourItr::operator++()
{
  m_contourIndex++;
  return *this;
}
Contour ContourItr::operator*() const
{
  return m_rectanglesToContour->contour(m_contourIndex);
}

Contour RectanglesToContour::contour(size_t index) const
{
  assert(index < m_contourOffsets.size());
  size_t end = m_contourOffsets[index];
  size_t start = index == 0 ? 0 : m_contourOffsets[index - 1];
  const ContourPoint* data = m_contourPoints.data() + start;
  size_t size = end - start;
  return Contour(Span<const ContourPoint>(data, size));
}

ContourPointItr& ContourPointItr::operator++()
{
  Vec2D currentPoint = m_pointIndex < m_contour.size() ? *(*this) : Vec2D();
  m_pointIndex++;
  while (m_pointIndex < m_contour.size())
  {
    auto nextPoint = m_contour[m_pointIndex].vec;
    if (nextPoint != currentPoint)
    {
      break;
    }
    m_pointIndex++;
  }
  return *this;
}

Vec2D ContourPointItr::operator*() const { return m_contour[m_pointIndex].vec; }

bool Contour::isClockwise() const
{
  float a = 0.0f;
  size_t size = m_points.size();
  if (size < 1)
  {
    return true;
  }
  for (size_t i = 1; i < size; i++)
  {
    a += Vec2D::cross(m_points[i - 1].vec, m_points[i].vec);
  }
  a += Vec2D::cross(m_points[size - 1].vec, m_points[0].vec);
  return a * 0.5f >= 0;
}