/*
 * Copyright 2018 Google LLC
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */
#include "include/core/SkPath.h"
#include "include/core/SkPathBuilder.h"
#include "include/core/SkPathTypes.h"
#include "include/core/SkPoint.h"
#include "include/core/SkRect.h"
#include "include/core/SkScalar.h"
#include "include/core/SkTypes.h"
#include "include/pathops/SkPathOps.h"
#include "include/private/base/SkMacros.h"
#include "src/core/SkPathPriv.h"
#include "src/pathops/SkPathOpsConic.h"
#include "src/pathops/SkPathOpsCubic.h"
#include "src/pathops/SkPathOpsCurve.h"
#include "src/pathops/SkPathOpsPoint.h"
#include "src/pathops/SkPathOpsQuad.h"
#include "src/pathops/SkPathOpsTypes.h"

#include <algorithm>
#include <vector>

using std::vector;

struct Contour {
    enum class Direction {  // SkPathDirection doesn't have 'none' state
        kCCW = -1,
        kNone,
        kCW,
    };

    Contour(const SkRect& bounds, int lastStart, int verbStart)
        : fBounds(bounds)
        , fVerbStart(lastStart)
        , fVerbEnd(verbStart) {
    }

    vector<Contour*> fChildren;
    const SkRect fBounds;
    SkPoint fMinXY{SK_ScalarMax, SK_ScalarMax};
    const int fVerbStart;
    const int fVerbEnd;
    Direction fDirection{Direction::kNone};
    bool fContained{false};
    bool fReverse{false};
};

static unsigned VerbPtCount(SkPathVerb verb) {
    static const uint8_t kPtCount[] = { 1, 1, 2, 2, 3, 0 };
    unsigned index = static_cast<unsigned>(verb);
    SkASSERT(index < std::size(kPtCount));
    return kPtCount[index];
}

static int VerbPtIndex(SkPathVerb verb) {
    static const int kPtIndex[] = { 0, 1, 1, 1, 1, 0 };
    unsigned index = static_cast<unsigned>(verb);
    SkASSERT(index < std::size(kPtIndex));
    return kPtIndex[index];
}

static Contour::Direction to_direction(SkScalar dy) {
    return dy > 0 ? Contour::Direction::kCCW : dy < 0 ? Contour::Direction::kCW :
            Contour::Direction::kNone;
}

static int contains_edge(const SkPoint pts[4], SkPathVerb verb, SkScalar weight, const SkPoint& edge) {
    SkRect bounds = SkRect::BoundsOrEmpty({pts, VerbPtCount(verb) + 1});
    if (bounds.fTop > edge.fY) {
        return 0;
    }
    if (bounds.fBottom <= edge.fY) {  // check to see if y is at line end to avoid double counting
        return 0;
    }
    if (bounds.fLeft >= edge.fX) {
        return 0;
    }
    int winding = 0;
    double tVals[3];
    Contour::Direction directions[3];
    // must intersect horz ray with curve in case it intersects more than once
    int count = (*CurveIntercept[(int)verb * 2])(pts, weight, edge.fY, tVals);
    SkASSERT(between(0, count, 3));
    // remove results to the right of edge
    for (int index = 0; index < count; ) {
        SkScalar intersectX = (*CurvePointAtT[(int)verb])(pts, weight, tVals[index]).fX;
        if (intersectX < edge.fX) {
            ++index;
            continue;
        }
        if (intersectX > edge.fX) {
            tVals[index] = tVals[--count];
            continue;
        }
        // if intersect x equals edge x, we need to determine if pts is to the left or right of edge
        if (pts[0].fX < edge.fX && pts[VerbPtCount(verb)].fX < edge.fX) {
            ++index;
            continue;
        }
        // TODO : other cases need discriminating. need op angle code to figure it out
        // example: edge ends 45 degree diagonal going up. If pts is to the left of edge, keep.
        // if pts is to the right of edge, discard. With code as is, can't distiguish the two cases.
        tVals[index] = tVals[--count];
    }
    // use first derivative to determine if intersection is contributing +1 or -1 to winding
    for (int index = 0; index < count; ++index) {
        directions[index] = to_direction((*CurveSlopeAtT[(int)verb])(pts, weight, tVals[index]).fY);
    }
    for (int index = 0; index < count; ++index) {
        // skip intersections that end at edge and go up
        if (zero_or_one(tVals[index]) && Contour::Direction::kCCW != directions[index]) {
            continue;
        }
        winding += (int) directions[index];
    }
    return winding;  // note winding indicates containership, not contour direction
}

static float conic_weight(const SkPath::IterRec& rec) {
    return rec.fVerb == SkPathVerb::kConic ? rec.conicWeight() : 1;
}

static SkPoint left_edge(const SkPoint pts[4], SkPathVerb verb, SkScalar weight) {
    SkASSERT(SkPathVerb::kLine <= verb && verb <= SkPathVerb::kCubic);
    SkPoint result;
    double t SK_INIT_TO_AVOID_WARNING;
    int roots = 0;
    if (SkPathVerb::kLine == verb) {
        result = pts[0].fX < pts[1].fX ? pts[0] : pts[1];
    } else if (SkPathVerb::kQuad == verb) {
        SkDQuad quad;
        quad.set(pts);
        if (!quad.monotonicInX()) {
            roots = SkDQuad::FindExtrema(&quad[0].fX, &t);
        }
        if (roots) {
            result = quad.ptAtT(t).asSkPoint();
        } else {
            result = pts[0].fX < pts[2].fX ? pts[0] : pts[2];
        }
    } else if (SkPathVerb::kConic == verb) {
        SkDConic conic;
        conic.set(pts, weight);
        if (!conic.monotonicInX()) {
            roots = SkDConic::FindExtrema(&conic[0].fX, weight, &t);
        }
        if (roots) {
            result = conic.ptAtT(t).asSkPoint();
        } else {
            result = pts[0].fX < pts[2].fX ? pts[0] : pts[2];
        }
    } else {
        SkASSERT(SkPathVerb::kCubic == verb);
        SkDCubic cubic;
        cubic.set(pts);
        if (!cubic.monotonicInX()) {
            double tValues[2];
            roots = SkDCubic::FindExtrema(&cubic[0].fX, tValues);
            SkASSERT(roots <= 2);
            for (int index = 0; index < roots; ++index) {
                SkPoint temp = cubic.ptAtT(tValues[index]).asSkPoint();
                if (0 == index || result.fX > temp.fX) {
                    result = temp;
                }
            }
        }
        if (roots) {
            result = cubic.ptAtT(t).asSkPoint();
        } else {
            result = pts[0].fX < pts[3].fX ? pts[0] : pts[3];
        }
    }
    return result;
}

class OpAsWinding {
public:
    enum class Edge {
        kInitial,
        kCompare,
    };

    OpAsWinding(const SkPath& path)
        : fPath(path) {
    }

    void contourBounds(vector<Contour>* containers) {
        SkRect bounds;
        bounds.setEmpty();
        int lastStart = 0;
        int verbStart = 0;
        for (auto [verb, pts, w] : SkPathPriv::Iterate(fPath)) {
            if (SkPathVerb::kMove == verb) {
                if (!bounds.isEmpty()) {
                    containers->emplace_back(bounds, lastStart, verbStart);
                    lastStart = verbStart;
               }
                bounds.setBounds({&pts[VerbPtIndex(SkPathVerb::kMove)],
                                  VerbPtCount(SkPathVerb::kMove)});
            }
            if (SkPathVerb::kLine <= verb && verb <= SkPathVerb::kCubic) {
                SkRect verbBounds;
                verbBounds.setBounds({&pts[VerbPtIndex(verb)], VerbPtCount(verb)});
                bounds.joinPossiblyEmptyRect(verbBounds);
            }
            ++verbStart;
        }
        if (!bounds.isEmpty()) {
            containers->emplace_back(bounds, lastStart, ++verbStart);
        }
    }

    Contour::Direction getDirection(Contour& contour) {
        SkPath::Iter iter(fPath, true);
        int verbCount = -1;

        SkScalar total_signed_area = 0;
        while (auto rec = iter.next()) {
            if (++verbCount < contour.fVerbStart) {
                continue;
            }
            if (verbCount >= contour.fVerbEnd) {
                continue;
            }
            if (SkPathVerb::kLine > rec->fVerb || rec->fVerb > SkPathVerb::kCubic) {
                continue;
            }

            SkSpan<const SkPoint> pts = rec->fPoints;
            switch (rec->fVerb) {
                case SkPathVerb::kLine:
                    total_signed_area += (pts[0].fY - pts[1].fY) * (pts[0].fX + pts[1].fX);
                    break;
                case SkPathVerb::kQuad:
                case SkPathVerb::kConic:
                    total_signed_area += (pts[0].fY - pts[2].fY) * (pts[0].fX + pts[2].fX);
                    break;
                case SkPathVerb::kCubic:
                    total_signed_area += (pts[0].fY - pts[3].fY) * (pts[0].fX + pts[3].fX);
                    break;
                default:
                    break;
            }
        }

        return total_signed_area < 0 ? Contour::Direction::kCCW: Contour::Direction::kCW;
    }

    int nextEdge(Contour& contour, Edge edge) {
        SkPath::Iter iter(fPath, true);
        int verbCount = -1;
        int winding = 0;
        while (auto rec = iter.next()) {
            const SkPathVerb verb = rec->fVerb;
            if (++verbCount < contour.fVerbStart) {
                continue;
            }
            if (verbCount >= contour.fVerbEnd) {
                continue;
            }
            if (SkPathVerb::kLine > verb || verb > SkPathVerb::kCubic) {
                continue;
            }

            SkSpan<const SkPoint> pts = rec->fPoints;
            bool horizontal = true;
            for (size_t index = 1; index <= VerbPtCount(verb); ++index) {
                if (pts[0].fY != pts[index].fY) {
                    horizontal = false;
                    break;
                }
            }
            if (horizontal) {
                continue;
            }
            if (edge == Edge::kCompare) {
                winding += contains_edge(pts.data(), verb, conic_weight(*rec),
                                         contour.fMinXY);
                continue;
            }
            SkASSERT(edge == Edge::kInitial);
            SkPoint minXY = left_edge(pts.data(), verb, conic_weight(*rec));
            if (minXY.fX > contour.fMinXY.fX) {
                continue;
            }
            if (minXY.fX == contour.fMinXY.fX) {
                if (minXY.fY != contour.fMinXY.fY) {
                    continue;
                }
            }
            contour.fMinXY = minXY;
        }
        return winding;
    }

    bool containerContains(Contour& contour, Contour& test) {
        // find outside point on lesser contour
        // arbitrarily, choose non-horizontal edge where point <= bounds left
        // note that if leftmost point is control point, may need tight bounds
        // to find edge with minimum-x
        if (SK_ScalarMax == test.fMinXY.fX) {
            this->nextEdge(test, Edge::kInitial);
        }
        // find all edges on greater equal or to the left of one on lesser
        contour.fMinXY = test.fMinXY;
        int winding = this->nextEdge(contour, Edge::kCompare);
        // if edge is up, mark contour cw, otherwise, ccw
        // sum of greater edges direction should be cw, 0, ccw
        test.fContained = winding != 0;
        return -1 <= winding && winding <= 1;
    }

    void inParent(Contour& contour, Contour& parent) {
        // move contour into sibling list contained by parent
        for (auto test : parent.fChildren) {
            if (test->fBounds.contains(contour.fBounds)) {
                inParent(contour, *test);
                return;
            }
        }
        // move parent's children into contour's children if contained by contour
        for (auto iter = parent.fChildren.begin(); iter != parent.fChildren.end(); ) {
            if (contour.fBounds.contains((*iter)->fBounds)) {
                contour.fChildren.push_back(*iter);
                iter = parent.fChildren.erase(iter);
                continue;
            }
            ++iter;
        }
        parent.fChildren.push_back(&contour);
    }

    bool checkContainerChildren(Contour* parent, Contour* child) {
        for (auto grandChild : child->fChildren) {
            if (!checkContainerChildren(child, grandChild)) {
                return false;
            }
        }
        if (parent) {
            if (!containerContains(*parent, *child)) {
                return false;
            }
        }
        return true;
    }

    bool markReverse(Contour* parent, Contour* child) {
        bool reversed = false;
        for (auto grandChild : child->fChildren) {
            reversed |= markReverse(grandChild->fContained ? child : parent, grandChild);
        }

        child->fDirection = getDirection(*child);
        if (parent && parent->fDirection == child->fDirection) {
            child->fReverse = true;
            child->fDirection = (Contour::Direction) -(int) child->fDirection;
            return true;
        }
        return reversed;
    }

    SkPath reverseMarkedContours(vector<Contour>& contours, SkPathFillType fillType) {
        SkPathPriv::Iterate iterate(fPath);
        auto iter = iterate.begin();
        int verbCount = 0;

        SkPathBuilder result;
        result.setFillType(fillType);
        for (const Contour& contour : contours) {
            SkPathBuilder reverse;
            SkPathBuilder* temp = contour.fReverse ? &reverse : &result;
            for (; iter != iterate.end() && verbCount < contour.fVerbEnd; ++iter, ++verbCount) {
                auto [verb, pts, w] = *iter;
                switch (verb) {
                    case SkPathVerb::kMove:
                        temp->moveTo(pts[0]);
                        break;
                    case SkPathVerb::kLine:
                        temp->lineTo(pts[1]);
                        break;
                    case SkPathVerb::kQuad:
                        temp->quadTo(pts[1], pts[2]);
                        break;
                    case SkPathVerb::kConic:
                        temp->conicTo(pts[1], pts[2], *w);
                        break;
                    case SkPathVerb::kCubic:
                        temp->cubicTo(pts[1], pts[2], pts[3]);
                        break;
                    case SkPathVerb::kClose:
                        temp->close();
                        break;
                }
            }
            if (contour.fReverse) {
                SkASSERT(temp == &reverse);
                SkPathPriv::ReverseAddPath(&result, reverse.detach());
            }
        }
        return result.detach();
    }

private:
    const SkPath& fPath;
};

std::optional<SkPath> AsWinding(const SkPath& path) {
    if (!path.isFinite()) {
        return {};
    }
    SkPathFillType fillType = path.getFillType();
    if (fillType == SkPathFillType::kWinding
            || fillType == SkPathFillType::kInverseWinding ) {
        return path;
    }
    fillType = path.isInverseFillType() ? SkPathFillType::kInverseWinding :
            SkPathFillType::kWinding;
    if (path.isEmpty() || path.isConvex()) {
        return path.makeFillType(fillType);
    }
    // count contours
    vector<Contour> contours;   // one per contour
    OpAsWinding winder(path);
    winder.contourBounds(&contours);
    if (contours.size() <= 1) {
        return path.makeFillType(fillType);
    }
    // create contour bounding box tree
    Contour sorted(SkRect(), 0, 0);
    for (auto& contour : contours) {
        winder.inParent(contour, sorted);
    }
    // if sorted has no grandchildren, no child has to fix its children's winding
    if (std::all_of(sorted.fChildren.begin(), sorted.fChildren.end(),
            [](const Contour* contour) -> bool { return contour->fChildren.empty(); } )) {
        return path.makeFillType(fillType);
    }
    // starting with outermost and moving inward, see if one path contains another
    for (auto contour : sorted.fChildren) {
        winder.nextEdge(*contour, OpAsWinding::Edge::kInitial);
        contour->fDirection = winder.getDirection(*contour);
        if (!winder.checkContainerChildren(nullptr, contour)) {
            return {};
        }
    }
    // starting with outermost and moving inward, mark paths to reverse
    bool reversed = false;
    for (auto contour : sorted.fChildren) {
        reversed |= winder.markReverse(nullptr, contour);
    }
    if (!reversed) {
        return path.makeFillType(fillType);
    }
    return winder.reverseMarkedContours(contours, fillType);
}