part of dart._engine;
// Copyright 2013 The Flutter Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.



/// Computes winding number and onCurveCount for a path and point.
class PathWinding {
  PathWinding(this.pathRef, this.x, this.y) {
    _walkPath();
  }

  final PathRef pathRef;
  final double x;
  final double y;
  int _w = 0;
  int _onCurveCount = 0;

  int get w => _w;

  int get onCurveCount => _onCurveCount;

  /// Buffer used for max(iterator result, chopped 3 cubics).
  final Float32List _buffer = Float32List(8 + 10);

  /// Iterates through path and computes winding.
  void _walkPath() {
    final PathIterator iter = PathIterator(pathRef, true);
    int verb;
    while ((verb = iter.next(_buffer)) != SPath.kDoneVerb) {
      switch (verb) {
        case SPath.kMoveVerb:
        case SPath.kCloseVerb:
          break;
        case SPath.kLineVerb:
          _computeLineWinding();
          break;
        case SPath.kQuadVerb:
          _computeQuadWinding();
          break;
        case SPath.kConicVerb:
          _computeConicWinding(pathRef.conicWeights![iter.conicWeightIndex]);
          break;
        case SPath.kCubicVerb:
          _computeCubicWinding();
          break;
      }
    }
  }

  void _computeLineWinding() {
    final double x0 = _buffer[0];
    final double startY = _buffer[1];
    double y0 = startY;
    final double x1 = _buffer[2];
    final double endY = _buffer[3];
    double y1 = endY;
    final double dy = y1 - y0;
    int dir = 1;
    // Swap so that y0 <= y1 holds.
    if (y0 > y1) {
      final double temp = y0;
      y0 = y1;
      y1 = temp;
      dir = -1;
    }
    // If point is outside top/bottom bounds, winding is 0.
    if (y < y0 || y > y1) {
      return;
    }
    if (_checkOnCurve(x, y, x0, startY, x1, endY)) {
      _onCurveCount++;
      return;
    }
    if (y == y1) {
      return;
    }
    // c = ax*by − ay*bx where a is the line and b is line formed from start
    // to the given point(x,y).
    final double crossProduct = (x1 - x0) * (y - startY) - dy * (x - x0);
    if (crossProduct == 0) {
      // zero cross means the point is on the line, and since the case where
      // y of the query point is at the end point is handled above, we can be
      // sure that we're on the line (excluding the end point) here.
      if (x != x1 || y != endY) {
        _onCurveCount++;
      }
      dir = 0;
    } else if (SPath.scalarSignedAsInt(crossProduct) == dir) {
      // Direction of cross product and line the same.
      dir = 0;
    }
    _w += dir;
  }

  // Check if point starts the line, handle special case for horizontal lines
  // where and point except the end point is considered on curve.
  static bool _checkOnCurve(double x, double y, double startX, double startY,
      double endX, double endY) {
    if (startY == endY) {
      // Horizontal line.
      return SPath.between(startX, x, endX) && x != endX;
    } else {
      return x == startX && y == startY;
    }
  }

  void _computeQuadWinding() {
    // Check if we need to chop quadratic at extrema to compute 2 separate
    // windings.
    int n = 0;
    if (!_isQuadMonotonic(_buffer)) {
      n = _chopQuadAtExtrema(_buffer);
    }
    int winding = _computeMonoQuadWinding(
        _buffer[0], _buffer[1], _buffer[2], _buffer[3], _buffer[4], _buffer[5]);
    if (n > 0) {
      winding += _computeMonoQuadWinding(_buffer[4], _buffer[5], _buffer[6],
          _buffer[7], _buffer[8], _buffer[9]);
    }
    _w += winding;
  }

  int _computeMonoQuadWinding(
      double x0, double y0, double x1, double y1, double x2, double y2) {
    int dir = 1;
    final double startY = y0;
    final double endY = y2;
    if (y0 > y2) {
      final double temp = y0;
      y0 = y2;
      y2 = temp;
      dir = -1;
    }
    if (y < y0 || y > y2) {
      return 0;
    }
    if (_checkOnCurve(x, y, x0, startY, x2, endY)) {
      _onCurveCount++;
      return 0;
    }
    if (y == y2) {
      return 0;
    }

    final QuadRoots quadRoots = QuadRoots();
    final int n = quadRoots.findRoots(
        startY - 2 * y1 + endY, 2 * (y1 - startY), startY - y);
    assert(n <= 1);
    double xt;
    if (0 == n) {
      // zero roots are returned only when y0 == y
      xt = dir == 1 ? x0 : x2;
    } else {
      final double t = quadRoots.root0!;
      final double C = x0;
      final double A = x2 - 2 * x1 + C;
      final double B = 2 * (x1 - C);
      xt = polyEval(A, B, C, t);
    }
    if (SPath.nearlyEqual(xt, x)) {
      if (x != x2 || y != endY) {
        // don't test end points; they're start points
        _onCurveCount += 1;
        return 0;
      }
    }
    return xt < x ? dir : 0;
  }

  /// Chops a non-monotonic quadratic curve, returns subdivisions and writes
  /// result into [buffer].
  static int _chopQuadAtExtrema(Float32List buffer) {
    final double x0 = buffer[0];
    final double y0 = buffer[1];
    final double x1 = buffer[2];
    final double y1 = buffer[3];
    final double x2 = buffer[4];
    final double y2 = buffer[5];
    final double? tValueAtExtrema = validUnitDivide(y0 - y1, y0 - y1 - y1 + y2);
    if (tValueAtExtrema != null) {
      // Chop quad at t value by interpolating along p0-p1 and p1-p2.
      final double p01x = x0 + (tValueAtExtrema * (x1 - x0));
      final double p01y = y0 + (tValueAtExtrema * (y1 - y0));
      final double p12x = x1 + (tValueAtExtrema * (x2 - x1));
      final double p12y = y1 + (tValueAtExtrema * (y2 - y1));
      final double cx = p01x + (tValueAtExtrema * (p12x - p01x));
      final double cy = p01y + (tValueAtExtrema * (p12y - p01y));
      buffer[2] = p01x;
      buffer[3] = p01y;
      buffer[4] = cx;
      buffer[5] = cy;
      buffer[6] = p12x;
      buffer[7] = p12y;
      buffer[8] = x2;
      buffer[9] = y2;
      return 1;
    }
    // if we get here, we need to force output to be monotonic, even though
    // we couldn't compute a unit divide value (probably underflow).
    buffer[3] = (y0 - y1).abs() < (y1 - y2).abs() ? y0 : y2;
    return 0;
  }

  static bool _isQuadMonotonic(Float32List quad) {
    final double y0 = quad[1];
    final double y1 = quad[3];
    final double y2 = quad[5];
    if (y0 == y1) {
      return true;
    }
    if (y0 < y1) {
      return y1 <= y2;
    } else {
      return y1 >= y2;
    }
  }

  void _computeConicWinding(double weight) {
    final Conic conic = Conic(_buffer[0], _buffer[1], _buffer[2], _buffer[3],
        _buffer[4], _buffer[5], weight);
    // If the data points are very large, the conic may not be monotonic but may also
    // fail to chop. Then, the chopper does not split the original conic in two.
    final bool isMono = _isQuadMonotonic(_buffer);
    final List<Conic> conics = <Conic>[];
    conic.chopAtYExtrema(conics);
    _computeMonoConicWinding(conics[0]);
    if (!isMono && conics.length == 2) {
      _computeMonoConicWinding(conics[1]);
    }
  }

  void _computeMonoConicWinding(Conic conic) {
    double y0 = conic.p0y;
    double y2 = conic.p2y;
    int dir = 1;
    if (y0 > y2) {
      final double swap = y0;
      y0 = y2;
      y2 = swap;
      dir = -1;
    }
    if (y < y0 || y > y2) {
      return;
    }
    if (_checkOnCurve(x, y, conic.p0x, conic.p0y, conic.p2x, conic.p2y)) {
      _onCurveCount += 1;
      return;
    }
    if (y == y2) {
      return;
    }

    double A = conic.p2y;
    double B = conic.p1y * conic.fW - y * conic.fW + y;
    double C = conic.p0y;
    // A = a + c - 2*(b*w - yCept*w + yCept)
    A += C - 2 * B;
    // B = b*w - w * yCept + yCept - a
    B -= C;
    C -= y;
    final QuadRoots quadRoots = QuadRoots();
    final int n = quadRoots.findRoots(A, 2 * B, C);
    assert(n <= 1);
    double xt;
    if (0 == n) {
      // zero roots are returned only when y0 == y
      // Need [0] if dir == 1
      // and  [2] if dir == -1
      xt = dir == 1 ? conic.p0x : conic.p2x;
    } else {
      final double root = quadRoots.root0!;
      xt =
          Conic.evalNumerator(conic.p0x, conic.p1x, conic.p2x, conic.fW, root) /
              Conic.evalDenominator(conic.fW, root);
    }
    if (SPath.nearlyEqual(xt, x)) {
      if (x != conic.p2x || y != conic.p2y) {
        // don't test end points; they're start points
        _onCurveCount += 1;
        return;
      }
    }
    _w += xt < x ? dir : 0;
  }

  void _computeCubicWinding() {
    final int n = chopCubicAtYExtrema(_buffer, _buffer);
    for (int i = 0; i <= n; ++i) {
      _windingMonoCubic(i * 3 * 2);
    }
  }

  void _windingMonoCubic(int bufferIndex) {
    final int bufferStartPos = bufferIndex;
    final double px0 = _buffer[bufferIndex++];
    final double py0 = _buffer[bufferIndex++];
    final double px1 = _buffer[bufferIndex++];
    bufferIndex++;
    final double px2 = _buffer[bufferIndex++];
    bufferIndex++;
    final double px3 = _buffer[bufferIndex++];
    final double py3 = _buffer[bufferIndex++];

    double y0 = py0;
    double y3 = py3;

    int dir = 1;
    if (y0 > y3) {
      final double swap = y0;
      y0 = y3;
      y3 = swap;
      dir = -1;
    }
    if (y < y0 || y > y3) {
      return;
    }
    if (_checkOnCurve(x, y, px0, py0, px3, py3)) {
      _onCurveCount += 1;
      return;
    }
    if (y == y3) {
      return;
    }

    // Quickly reject or accept
    final double min = math.min(px0, math.min(px1, math.min(px2, px3)));
    final double max = math.max(px0, math.max(px1, math.max(px2, px3)));
    if (x < min) {
      return;
    }
    if (x > max) {
      _w += dir;
      return;
    }
    // Compute the actual x(t) value.
    final double? t = chopMonoAtY(_buffer, bufferStartPos, y);
    if (t == null) {
      return;
    }
    final double xt = evalCubicPts(px0, px1, px2, px3, t);
    if (SPath.nearlyEqual(xt, x)) {
      if (x != px3 || y != py3) {
        // don't test end points; they're start points
        _onCurveCount += 1;
        return;
      }
    }
    _w += xt < x ? dir : 0;
  }
}
