/*
 * Copyright 2014 Google Inc.
 *
 * Use of this source code is governed by a BSD-style license that can be
 * found in the LICENSE file.
 */

#include "SkChunkAlloc.h"
#include "SkPathOpsRect.h"
#include "SkPathOpsQuad.h"
#include "SkIntersections.h"
#include "SkTArray.h"

/* TCurve is either SkDQuadratic or SkDCubic */
template<typename TCurve>
class SkTCoincident {
public:
    bool isCoincident() const {
        return fCoincident;
    }

    void init() {
        fCoincident = false;
        SkDEBUGCODE(fPerpPt.fX = fPerpPt.fY = SK_ScalarNaN);
        SkDEBUGCODE(fPerpT = SK_ScalarNaN);
    }

    void markCoincident() {
        if (!fCoincident) {
            fPerpT = -1;
        }
        fCoincident = true;
    }

    const SkDPoint& perpPt() const {
        return fPerpPt;
    }

    double perpT() const {
        return fPerpT;
    }

    void setPerp(const TCurve& c1, double t, const SkDPoint& cPt, const TCurve& );

private:
    SkDPoint fPerpPt;
    double fPerpT;  // perpendicular intersection on opposite curve
    bool fCoincident;
};

template<typename TCurve> class SkTSect;

/* Curve is either TCurve or SkDCubic */
template<typename TCurve>
class SkTSpan {
public:
    void init(const TCurve& );
    void initBounds(const TCurve& );

    double closestBoundedT(const SkDPoint& pt) const;

    bool contains(double t) const {
        return !! const_cast<SkTSpan*>(this)->innerFind(t);
    }

    bool contains(const SkTSpan* span) const;

    double endT() const {
        return fEndT;
    }

    SkTSpan* find(double t) {
        SkTSpan* result = innerFind(t);
        SkASSERT(result);
        return result;
    }

    bool intersects(const SkTSpan* span, bool* check);

    const SkTSpan* next() const {
        return fNext;
    }

    const TCurve& part() const {
        return fPart;
    }

    void reset() {
        fBounded.reset();
    }

    bool split(SkTSpan* work) {
        return splitAt(work, (work->fStartT + work->fEndT) * 0.5);
    }

    bool splitAt(SkTSpan* work, double t);

    double startT() const {
        return fStartT;
    }

    bool tightBoundsIntersects(const SkTSpan* span) const;

    // implementation is for testing only
    void dump() const {
        dump(NULL);
    }

private:
    SkTSpan* innerFind(double t);
    bool linearIntersects(const TCurve& ) const;

    // implementation is for testing only
#if DEBUG_T_SECT
    int debugID(const SkTSect<TCurve>* ) const { return fDebugID; }
#else
    int debugID(const SkTSect<TCurve>* ) const;
#endif
    void dump(const SkTSect<TCurve>* ) const;
    void dumpID(const SkTSect<TCurve>* ) const;

#if DEBUG_T_SECT
    void validate() const;
#endif

    TCurve fPart;
    SkTCoincident<TCurve> fCoinStart;
    SkTCoincident<TCurve> fCoinEnd;
    SkSTArray<4, SkTSpan*, true> fBounded;
    SkTSpan* fPrev;
    SkTSpan* fNext;
    SkDRect fBounds;
    double fStartT;
    double fEndT;
    double fBoundsMax;
    bool fCollapsed;
    bool fHasPerp;
    bool fIsLinear;
#if DEBUG_T_SECT
    int fDebugID;
    bool fDebugDeleted;
#endif
    friend class SkTSect<TCurve>;
};

template<typename TCurve>
class SkTSect {
public:
    SkTSect(const TCurve& c  PATH_OPS_DEBUG_PARAMS(int id));
    static void BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersections* intersections);

    // for testing only
    void dump() const;
    void dumpBoth(const SkTSect& opp) const;
    void dumpBoth(const SkTSect* opp) const;
    void dumpCurves() const;

private:
    enum {
        kZeroS1Set = 1,
        kOneS1Set = 2,
        kZeroS2Set = 4,
        kOneS2Set = 8
    };

    SkTSpan<TCurve>* addOne();
    bool binarySearchCoin(const SkTSect& , double tStart, double tStep, double* t, double* oppT);
    SkTSpan<TCurve>* boundsMax() const;
    void coincidentCheck(SkTSect* sect2);
    static int EndsEqual(const SkTSect* sect1, const SkTSect* sect2, SkIntersections* );
    bool intersects(SkTSpan<TCurve>* span, const SkTSect* opp,
            const SkTSpan<TCurve>* oppSpan) const;
    void onCurveCheck(SkTSect* sect2, SkTSpan<TCurve>* first, SkTSpan<TCurve>* last);
    void recoverCollapsed();
    void removeSpan(SkTSpan<TCurve>* span);
    void removeOne(const SkTSpan<TCurve>* test, SkTSpan<TCurve>* span);
    void removeSpans(SkTSpan<TCurve>* span, SkTSect* opp);
    void setPerp(const TCurve& opp, SkTSpan<TCurve>* first, SkTSpan<TCurve>* last);
    const SkTSpan<TCurve>* tail() const;
    void trim(SkTSpan<TCurve>* span, SkTSect* opp);

#if DEBUG_T_SECT
    int debugID() const { return fDebugID; }
    void validate() const;
#else
    int debugID() const { return 0; }
#endif
    const TCurve& fCurve;
    SkChunkAlloc fHeap;
    SkTSpan<TCurve>* fHead;
    SkTSpan<TCurve>* fDeleted;
    int fActiveCount;
#if DEBUG_T_SECT
    int fDebugID;
    int fDebugCount;
    int fDebugAllocatedCount;
#endif
    friend class SkTSpan<TCurve>;  // only used by debug id
};

#define COINCIDENT_SPAN_COUNT 9

template<typename TCurve>
void SkTCoincident<TCurve>::setPerp(const TCurve& c1, double t,
        const SkDPoint& cPt, const TCurve& c2) {
    SkDVector dxdy = c1.dxdyAtT(t);
    SkDLine perp = {{ cPt, {cPt.fX + dxdy.fY, cPt.fY - dxdy.fX} }};
    SkIntersections i;
    int used = i.intersectRay(c2, perp);
    // only keep closest
    if (used == 0) {
        fPerpT = -1;
        return;
    } 
    fPerpT = i[0][0];
    fPerpPt = i.pt(0);
    SkASSERT(used <= 2);
    if (used == 2) {
        double distSq = (fPerpPt - cPt).lengthSquared();
        double dist2Sq = (i.pt(1) - cPt).lengthSquared();
        if (dist2Sq < distSq) {
            fPerpT = i[0][1];
            fPerpPt = i.pt(1);
        }
    }
    fCoincident = cPt.approximatelyEqual(fPerpPt);
#if DEBUG_T_SECT
    if (fCoincident) {
        SkDebugf("");  // allow setting breakpoint
    }
#endif
}

template<typename TCurve>
void SkTSpan<TCurve>::init(const TCurve& c) {
    fPrev = fNext = NULL;
    fIsLinear = false;
    fStartT = 0;
    fEndT = 1;
    initBounds(c);
}

template<typename TCurve>
void SkTSpan<TCurve>::initBounds(const TCurve& c) {
    fPart = c.subDivide(fStartT, fEndT);
    fBounds.setBounds(fPart);
    fCoinStart.init();
    fCoinEnd.init();
    fBoundsMax = SkTMax(fBounds.width(), fBounds.height());
    fCollapsed = fPart.collapsed();
    fHasPerp = false;
#if DEBUG_T_SECT
    fDebugDeleted = false;
    if (fCollapsed) {
        SkDebugf("");  // for convenient breakpoints
    }
#endif
}

template<typename TCurve>
double SkTSpan<TCurve>::closestBoundedT(const SkDPoint& pt) const {
    int count = fBounded.count();
    double result = -1;
    double closest = FLT_MAX;
    for (int index = 0; index < count; ++index) {
        const SkTSpan* test = fBounded[index];
        double startDist = test->fPart[0].distanceSquared(pt);
        if (closest > startDist) {
            closest = startDist;
            result = test->fStartT;
        }
        double endDist = test->fPart[TCurve::kPointLast].distanceSquared(pt);
        if (closest > endDist) {
            closest = endDist;
            result = test->fEndT;
        }
    }
    SkASSERT(between(0, result, 1));
    return result;
}

template<typename TCurve>
bool SkTSpan<TCurve>::contains(const SkTSpan* span) const {
    int count = fBounded.count();
    for (int index = 0; index < count; ++index) {
        const SkTSpan* test = fBounded[index];
        if (span == test) {
            return true;
        }
    }
    return false;
}

template<typename TCurve>
SkTSpan<TCurve>* SkTSpan<TCurve>::innerFind(double t) {
    SkTSpan* work = this;
    do {
        if (between(work->fStartT, t, work->fEndT)) {
            return work;
        }
    } while ((work = work->fNext));
    return NULL;
}

// OPTIMIZE ? If at_most_end_pts_in_common detects that one quad is near linear,
// use line intersection to guess a better split than 0.5
// OPTIMIZE Once at_most_end_pts_in_common detects linear, mark span so all future splits are linear
template<typename TCurve>
bool SkTSpan<TCurve>::intersects(const SkTSpan* span, bool* check) {
    if (!fBounds.intersects(span->fBounds)) {
        *check = false;  // no need to check to see if the bounds have end points in common
        return false;
    }
    if (!fIsLinear && fPart.hullIntersects(span->fPart, check)) {
        if (!*check) {
            return true;
        }
        fIsLinear = true;
    }
    if (fIsLinear) {
        *check = false;
        return linearIntersects(span->fPart);
    }
    return *check; 
}

template<typename TCurve>
bool SkTSpan<TCurve>::linearIntersects(const TCurve& q2) const {
    // looks like q1 is near-linear
    int start = 0, end = TCurve::kPointCount - 1;  // the outside points are usually the extremes
    if (!fPart.controlsInside()) {
        double dist = 0;  // if there's any question, compute distance to find best outsiders
        for (int outer = 0; outer < TCurve::kPointCount - 1; ++outer) {
            for (int inner = outer + 1; inner < TCurve::kPointCount; ++inner) {
                double test = (fPart[outer] - fPart[inner]).lengthSquared();
                if (dist > test) {
                    continue;
                }
                dist = test;
                start = outer;
                end = inner;
            }
        }
    }
    // see if q2 is on one side of the line formed by the extreme points
    double origX = fPart[start].fX;
    double origY = fPart[start].fY;
    double adj = fPart[end].fX - origX;
    double opp = fPart[end].fY - origY;
    double sign;
    for (int n = 0; n < TCurve::kPointCount; ++n) {
        double test = (q2[n].fY - origY) * adj - (q2[n].fX - origX) * opp;
        if (precisely_zero(test)) {
            return true;
        }
        if (n == 0) {
            sign = test;
            continue;
        }
        if (test * sign < 0) {
            return true;
        }
    }
    return false;
}

template<typename TCurve>
bool SkTSpan<TCurve>::splitAt(SkTSpan* work, double t) {
    fStartT = t;
    fEndT = work->fEndT;
    if (fStartT == fEndT) {
        fCollapsed = true;
        return false;
    }
    work->fEndT = t;
    if (work->fStartT == work->fEndT) {
        work->fCollapsed = true;
        return false;
    }
    fPrev = work;
    fNext = work->fNext;
    fIsLinear = work->fIsLinear;
    work->fNext = this;
    if (fNext) {
        fNext->fPrev = this;
    }
    fBounded = work->fBounded;
    int count = fBounded.count();
    for (int index = 0; index < count; ++index) {
        fBounded[index]->fBounded.push_back() = this;
    }
    return true;
}

template<typename TCurve>
bool SkTSpan<TCurve>::tightBoundsIntersects(const SkTSpan* span) const {
    // skew all to an axis
    SkDVector v2_0 = fPart[TCurve::kPointLast] - fPart[0];
    bool skewToXAxis = fabs(v2_0.fX) > fabs(v2_0.fY);
    double ratio = skewToXAxis ? v2_0.fY / v2_0.fX : v2_0.fX / v2_0.fY;
    TCurve r1 = fPart;
    if (skewToXAxis) {
        r1[1].fY -= (fPart[1].fX - r1[0].fX) * ratio;
        if (TCurve::IsCubic()) {
            r1[2].fY -= (fPart[2].fX - r1[0].fX) * ratio;
            r1[3].fY = r1[0].fY;
        } else {
            r1[2].fY = r1[0].fY;
        }
    } else {
        r1[1].fX -= (fPart[1].fY - r1[0].fY) * ratio;
        if (TCurve::IsCubic()) {
            r1[2].fX -= (fPart[2].fY - r1[0].fY) * ratio;
            r1[3].fX = r1[0].fX;
        } else {
            r1[2].fX = r1[0].fX;
        }
    }
    // compute the tight skewed bounds
    SkDRect bounds;
    bounds.setBounds(r1);
    // see if opposite ends are within range of tight skewed bounds
    TCurve r2 = span->fPart;
    for (int i = 0; i < TCurve::kPointCount; i += 2) {
        if (skewToXAxis) {
            r2[i].fY -= (r2[i].fX - r1[0].fX) * ratio;
            if (between(bounds.fTop, r2[i].fY, bounds.fBottom)) {
                return true;
            }
        } else {
            r2[i].fX -= (r2[i].fY - r1[0].fY) * ratio;
            if (between(bounds.fLeft, r2[i].fX, bounds.fRight)) {
                return true;
            }
        }
    }
    // see if opposite ends are on either side of tight skewed bounds
    if ((skewToXAxis ? (r2[0].fY - r1[0].fY) * (r2[TCurve::kPointLast].fY - r1[0].fY)
                        : (r2[0].fX - r1[0].fX) * (r2[TCurve::kPointLast].fX - r1[0].fX)) < 0) {
        return true;
    }
    // compute opposite tight skewed bounds
    if (skewToXAxis) {
        r2[1].fY -= (r2[1].fX - r1[0].fX) * ratio;
        if (TCurve::IsCubic()) {
            r2[2].fY -= (r2[2].fX - r1[0].fX) * ratio;
        }
    } else {
        r2[1].fX -= (r2[1].fY - r1[0].fY) * ratio;
        if (TCurve::IsCubic()) {
            r2[2].fX -= (r2[2].fY - r1[0].fY) * ratio;
        }
    }
    SkDRect sBounds;
    sBounds.setBounds(r2);
    // see if tight bounds overlap
    if (skewToXAxis) {
        return bounds.fTop <= sBounds.fBottom && sBounds.fTop <= bounds.fBottom;  
    } else {
        return bounds.fLeft <= sBounds.fRight && sBounds.fLeft <= bounds.fRight;  
    }
}

#if DEBUG_T_SECT
template<typename TCurve>
void SkTSpan<TCurve>::validate() const {
    SkASSERT(fNext == NULL || fNext != fPrev);
    SkASSERT(fNext == NULL || this == fNext->fPrev);
    SkASSERT(fBounds.width() || fBounds.height());
    SkASSERT(fBoundsMax == SkTMax(fBounds.width(), fBounds.height()));
    SkASSERT(0 <= fStartT);
    SkASSERT(fEndT <= 1);
    SkASSERT(fStartT < fEndT);
    SkASSERT(fBounded.count() > 0);
    for (int index = 0; index < fBounded.count(); ++index) {
        const SkTSpan* overlap = fBounded[index];
        SkASSERT(((fDebugID ^ overlap->fDebugID) & 1) == 1);
        SkASSERT(overlap->contains(this));
    }
}
#endif

template<typename TCurve>
SkTSect<TCurve>::SkTSect(const TCurve& c PATH_OPS_DEBUG_PARAMS(int id))
    : fCurve(c)
    , fHeap(sizeof(SkTSpan<TCurve>) * 4)
    , fDeleted(NULL)
    , fActiveCount(0)
    PATH_OPS_DEBUG_PARAMS(fDebugID(id))
    PATH_OPS_DEBUG_PARAMS(fDebugCount(0))
    PATH_OPS_DEBUG_PARAMS(fDebugAllocatedCount(0))
{
    fHead = addOne();
    fHead->init(c);
}

template<typename TCurve>
SkTSpan<TCurve>* SkTSect<TCurve>::addOne() {
    SkTSpan<TCurve>* result;
    if (fDeleted) {
        result = fDeleted;
        result->reset();
        fDeleted = result->fNext;
    } else {
        result = SkNEW_PLACEMENT(fHeap.allocThrow(sizeof(SkTSpan<TCurve>)), SkTSpan<TCurve>);
#if DEBUG_T_SECT
        ++fDebugAllocatedCount;
#endif
    }
    ++fActiveCount; 
#if DEBUG_T_SECT
    result->fDebugID = fDebugCount++ * 2 + fDebugID;
#endif
    return result;
}

template<typename TCurve>
bool SkTSect<TCurve>::binarySearchCoin(const SkTSect& sect2, double tStart, double tStep,
        double* resultT, double* oppT) {
    SkTSpan<TCurve> work;
    double result = work.fStartT = work.fEndT = tStart;
    SkDPoint last = fCurve.ptAtT(tStart);
    SkDPoint oppPt;
    bool flip = false;
    SkDEBUGCODE(bool down = tStep < 0);
    const TCurve& opp = sect2.fCurve;
    do {
        tStep *= 0.5;
        work.fStartT += tStep;
        if (flip) {
            tStep = -tStep;
            flip = false;
        }
        work.initBounds(fCurve);
        if (work.fCollapsed) {
            return false;
        }
        if (last.approximatelyEqual(work.fPart[0])) {
            break;
        }
        last = work.fPart[0];
        work.fCoinStart.setPerp(fCurve, work.fStartT, last, opp);
        if (work.fCoinStart.isCoincident()) {
            double oppTTest = work.fCoinStart.perpT();
            if (sect2.fHead->contains(oppTTest)) {
                *oppT = oppTTest;
                oppPt = work.fCoinStart.perpPt();
                SkASSERT(down ? result > work.fStartT : result < work.fStartT);
                result = work.fStartT;
                continue;
            }
        }
        tStep = -tStep;
        flip = true;
    } while (true);
    if (last.approximatelyEqual(fCurve[0])) {
        result = 0;
    } else if (last.approximatelyEqual(fCurve[TCurve::kPointLast])) {
        result = 1;
    }
    if (oppPt.approximatelyEqual(opp[0])) {
        *oppT = 0;
    } else if (oppPt.approximatelyEqual(opp[TCurve::kPointLast])) {
        *oppT = 1;
    }
    *resultT = result;
    return true;
}

// OPTIMIZE ? keep a sorted list of sizes in the form of a doubly-linked list in quad span
//            so that each quad sect has a pointer to the largest, and can update it as spans
//            are split
template<typename TCurve>
SkTSpan<TCurve>* SkTSect<TCurve>::boundsMax() const {
    SkTSpan<TCurve>* test = fHead;
    SkTSpan<TCurve>* largest = fHead;
    bool largestCoin = largest->fCoinStart.isCoincident() && largest->fCoinEnd.isCoincident();
    while ((test = test->fNext)) {
        bool testCoin = test->fCoinStart.isCoincident() || test->fCoinEnd.isCoincident();
        if ((largestCoin && !testCoin) || (largestCoin == testCoin
                && (largest->fBoundsMax < test->fBoundsMax
                || (largest->fCollapsed && !test->fCollapsed)))) {
            largest = test;
            largestCoin = testCoin;
        }
    }
    return largestCoin ? NULL : largest;
}

template<typename TCurve>
void SkTSect<TCurve>::coincidentCheck(SkTSect* sect2) {
    SkTSpan<TCurve>* first = fHead;
    SkTSpan<TCurve>* next;
    do {
        int consecutive = 1;
        SkTSpan<TCurve>* last = first;
        do {
            next = last->fNext;
            if (!next) {
                break;
            }
            if (next->fStartT > last->fEndT) {
                break;
            }
            ++consecutive;
            last = next;
        } while (true);
        if (consecutive < COINCIDENT_SPAN_COUNT) {
            continue;
        }
        setPerp(sect2->fCurve, first, last);
        // check to see if a range of points are on the curve
        onCurveCheck(sect2, first, last);
        SkTSpan<TCurve>* removalCandidate = NULL;
        if (!first->fCoinStart.isCoincident()) {
            SkTSpan<TCurve>* firstCoin = first->fNext;
            removalCandidate = first;
            first = firstCoin;
        }
        if (!first->fCoinStart.isCoincident()) {
            continue;
        }
        if (removalCandidate) {
            removeSpans(removalCandidate, sect2);
        }
        if (!last->fCoinStart.isCoincident()) {
            continue;
        }
        if (!last->fCoinEnd.isCoincident()) {
            if (--consecutive < COINCIDENT_SPAN_COUNT) {
                continue;
            }
            last = last->fPrev;
            SkASSERT(last->fCoinStart.isCoincident());
            SkASSERT(last->fCoinEnd.isCoincident());
        }
        SkASSERT(between(0, first->fCoinStart.perpT(), 1) || first->fCoinStart.perpT() == -1);
        if (first->fCoinStart.perpT() < 0) {
            first->fCoinStart.setPerp(fCurve, first->fStartT, first->fPart[0], sect2->fCurve);
        }
        SkASSERT(between(0, last->fCoinEnd.perpT(), 1) || last->fCoinEnd.perpT() == -1);
        if (last->fCoinEnd.perpT() < 0) {
            last->fCoinEnd.setPerp(fCurve, last->fEndT, last->fPart[TCurve::kPointLast],
                    sect2->fCurve);
        }
        SkTSpan<TCurve>* removeMe = first->fNext;
        while (removeMe != last) {
            SkTSpan<TCurve>* removeNext = removeMe->fNext;
            removeSpans(removeMe, sect2);
            removeMe = removeNext;
        }
    } while ((first = next));
}

template<typename TCurve>
bool SkTSect<TCurve>::intersects(SkTSpan<TCurve>* span, const SkTSect* opp,
        const SkTSpan<TCurve>* oppSpan) const {
    bool check;  // we ignore whether the end points are in common or not
    if (!span->intersects(oppSpan, &check)) {
        return false;
    }
    if (fActiveCount < COINCIDENT_SPAN_COUNT || opp->fActiveCount < COINCIDENT_SPAN_COUNT) {
        return true;
    }
    return span->tightBoundsIntersects(oppSpan);
}

template<typename TCurve>
void SkTSect<TCurve>::onCurveCheck(SkTSect* sect2, SkTSpan<TCurve>* first, SkTSpan<TCurve>* last) {
    SkTSpan<TCurve>* work = first;
    first = NULL;
    do {
        if (work->fCoinStart.isCoincident()) {
            if (!first) {
                first = work;
            }
        } else if (first) {
            break;
        }
        if (work == last) {
            break;
        }
        work = work->fNext;
        SkASSERT(work);
    } while (true);
    if (!first) {
        return;
    }
    // march outwards to find limit of coincidence from here to previous and next spans
    double startT = first->fStartT;
    double oppT;
    SkTSpan<TCurve>* prev = first->fPrev;
    if (prev) {
        double coinStart;
        if (binarySearchCoin(*sect2, startT, prev->fStartT - startT, &coinStart, &oppT)) {
            if (coinStart < startT) {
                SkASSERT(prev->fStartT < coinStart && coinStart < prev->fEndT);
                SkTSpan<TCurve>* oppStart = sect2->fHead->find(oppT);
                if (oppStart->fStartT < oppT && oppT < oppStart->fEndT) {
                    // split prev at coinStart if needed
                    SkTSpan<TCurve>* half2 = addOne();
                    half2->splitAt(prev, coinStart);
                    half2->initBounds(fCurve);
                    prev->initBounds(fCurve);
                    prev->fCoinEnd.markCoincident();
                    half2->fCoinStart.markCoincident();
                    half2->fCoinEnd.markCoincident();
                    // find span containing opposite t, and split that too
                    SkTSpan<TCurve>* oppHalf = sect2->addOne();
                    oppHalf->splitAt(oppStart, oppT);
                    oppHalf->initBounds(sect2->fCurve);
                    oppStart->initBounds(sect2->fCurve);
                } else {
                    SkASSERT(oppStart->fStartT == oppT || oppT == oppStart->fEndT);
                    first->fStartT = coinStart;
                    prev->fEndT = coinStart;
                    first->initBounds(fCurve);
                    prev->initBounds(fCurve);
                    first->fCoinStart.markCoincident();
                    first->fCoinEnd.markCoincident();
                }
            }
        }
    }
    if (!work->fCoinEnd.isCoincident()) {
        if (work->fEndT == 1) {
            SkDebugf("!");
        }
//        SkASSERT(work->fEndT < 1);
        startT = work->fStartT;
        double coinEnd;
        if (binarySearchCoin(*sect2, startT, work->fEndT - startT, &coinEnd, &oppT)) {
            if (coinEnd > startT) {
                SkTSpan<TCurve>* oppStart = sect2->fHead->find(oppT);
                if (oppStart->fStartT < oppT && oppT < oppStart->fEndT) {
                    SkASSERT(coinEnd < work->fEndT);
                    // split prev at coinEnd if needed
                    SkTSpan<TCurve>* half2 = addOne();
                    half2->splitAt(work, coinEnd);
                    half2->initBounds(fCurve);
                    work->initBounds(fCurve);
                    work->fCoinStart.markCoincident();
                    work->fCoinEnd.markCoincident();
                    half2->fCoinStart.markCoincident();
                    SkTSpan<TCurve>* oppHalf = sect2->addOne();
                    oppHalf->splitAt(oppStart, oppT);
                    oppHalf->initBounds(sect2->fCurve);
                    oppStart->initBounds(sect2->fCurve);
                } else {
                    SkASSERT(oppStart->fStartT == oppT || oppT == oppStart->fEndT);
                    SkTSpan<TCurve>* next = work->fNext;
                    bool hasNext = next && work->fEndT == next->fStartT;
                    work->fEndT = coinEnd;
                    work->initBounds(fCurve);
                    work->fCoinStart.markCoincident();
                    work->fCoinEnd.markCoincident();
                    if (hasNext) { 
                        next->fStartT = coinEnd;
                        next->initBounds(fCurve);
                    }
                }
            }
        }
    }
}

template<typename TCurve>
void SkTSect<TCurve>::recoverCollapsed() {
    SkTSpan<TCurve>* deleted = fDeleted;
    while (deleted) {
        SkTSpan<TCurve>* delNext = deleted->fNext;
        if (deleted->fCollapsed) {
            SkTSpan<TCurve>** spanPtr = &fHead;
            while (*spanPtr && (*spanPtr)->fEndT <= deleted->fStartT) {
                spanPtr = &(*spanPtr)->fNext;
            }
            deleted->fNext = *spanPtr;
            *spanPtr = deleted;
        }
        deleted = delNext;
    }
}

template<typename TCurve>
void SkTSect<TCurve>::removeSpan(SkTSpan<TCurve>* span) {
    SkTSpan<TCurve>* prev = span->fPrev;
    SkTSpan<TCurve>* next = span->fNext;
    if (prev) {
        prev->fNext = next;
        if (next) {
            next->fPrev = prev;
        }
    } else {
        fHead = next;
        if (next) {
            next->fPrev = NULL;
        }
    }
    --fActiveCount;
    span->fNext = fDeleted;
    fDeleted = span;
#if DEBUG_T_SECT
    SkASSERT(!span->fDebugDeleted);
    span->fDebugDeleted = true;
#endif
}

template<typename TCurve>
void SkTSect<TCurve>::removeOne(const SkTSpan<TCurve>* test, SkTSpan<TCurve>* span) {
    int last = span->fBounded.count() - 1;
    for (int index = 0; index <= last; ++index) {
        if (span->fBounded[index] == test) {
            span->fBounded.removeShuffle(index);
            if (!last) {
                removeSpan(span);
            }
            return;
        }
    }
}

template<typename TCurve>
void SkTSect<TCurve>::removeSpans(SkTSpan<TCurve>* span, SkTSect<TCurve>* opp) {
    int count = span->fBounded.count();
    for (int index = 0; index < count; ++index) {
        SkTSpan<TCurve>* bounded = span->fBounded[0];
        removeOne(bounded, span);  // shuffles last into position 0
        opp->removeOne(span, bounded);
    }
}

template<typename TCurve>
void SkTSect<TCurve>::setPerp(const TCurve& opp, SkTSpan<TCurve>* first, SkTSpan<TCurve>* last) {
    SkTSpan<TCurve>* work = first;
    if (!work->fHasPerp) {
        work->fCoinStart.setPerp(fCurve, work->fStartT, work->fPart[0], opp);
    }
    do {
        if (!work->fHasPerp) {
            work->fCoinEnd.setPerp(fCurve, work->fEndT, work->fPart[TCurve::kPointLast], opp);
            work->fHasPerp = true;
        }
        if (work == last) {
            break;
        }
        SkTSpan<TCurve>* last = work;
        work = work->fNext;
        SkASSERT(work);
        if (!work->fHasPerp) {
            work->fCoinStart = last->fCoinEnd;
        }
    } while (true);
}

template<typename TCurve>
const SkTSpan<TCurve>* SkTSect<TCurve>::tail() const {
    const SkTSpan<TCurve>* result = fHead;
    const SkTSpan<TCurve>* next = fHead;
    while ((next = next->fNext)) {
        if (next->fEndT > result->fEndT) {
            result = next;
        }
    }
    return result;
}

/* Each span has a range of opposite spans it intersects. After the span is split in two,
    adjust the range to its new size */
template<typename TCurve>
void SkTSect<TCurve>::trim(SkTSpan<TCurve>* span, SkTSect* opp) {
    span->initBounds(fCurve);
    int count = span->fBounded.count();
    for (int index = 0; index < count; ) {
        SkTSpan<TCurve>* test = span->fBounded[index];
        bool sects = intersects(span, opp, test);
        if (sects) {
            ++index;
        } else {
            removeOne(test, span);
            opp->removeOne(span, test);
            --count;
        }
    }
}

#if DEBUG_T_SECT
template<typename TCurve>
void SkTSect<TCurve>::validate() const {
    int count = 0;
    if (fHead) {
        const SkTSpan<TCurve>* span = fHead;
        SkASSERT(!span->fPrev);
        double last = 0;
        do {
            span->validate();
            SkASSERT(span->fStartT >= last);
            last = span->fEndT;
            ++count;
        } while ((span = span->fNext) != NULL);
    }
    SkASSERT(count == fActiveCount);
    SkASSERT(fActiveCount <= fDebugAllocatedCount);
    int deletedCount = 0;
    const SkTSpan<TCurve>* deleted = fDeleted;
    while (deleted) {
        ++deletedCount;
        deleted = deleted->fNext;
    }
    SkASSERT(fActiveCount + deletedCount == fDebugAllocatedCount);
}
#endif

template<typename TCurve>
int SkTSect<TCurve>::EndsEqual(const SkTSect* sect1, const SkTSect* sect2,
        SkIntersections* intersections) {
    int zeroOneSet = 0;
    // check for zero
    if (sect1->fCurve[0].approximatelyEqual(sect2->fCurve[0])) {
        zeroOneSet |= kZeroS1Set | kZeroS2Set;
        if (sect1->fCurve[0] != sect2->fCurve[0]) {
            intersections->insertNear(0, 0, sect1->fCurve[0], sect2->fCurve[0]);
        } else {
            intersections->insert(0, 0, sect1->fCurve[0]);
        }
    } 
    if (sect1->fCurve[0].approximatelyEqual(sect2->fCurve[TCurve::kPointLast])) {
        zeroOneSet |= kZeroS1Set | kOneS2Set;
        if (sect1->fCurve[0] != sect2->fCurve[TCurve::kPointLast]) {
            intersections->insertNear(0, 1, sect1->fCurve[0], sect2->fCurve[TCurve::kPointLast]);
        } else {
            intersections->insert(0, 1, sect1->fCurve[0]);
        }
    } 
    // check for one
    if (sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[0])) {
        zeroOneSet |= kOneS1Set | kZeroS2Set;
        if (sect1->fCurve[TCurve::kPointLast] != sect2->fCurve[0]) {
            intersections->insertNear(1, 0, sect1->fCurve[TCurve::kPointLast], sect2->fCurve[0]);
        } else {
            intersections->insert(1, 0, sect1->fCurve[TCurve::kPointLast]);
        }
    } 
    if (sect1->fCurve[TCurve::kPointLast].approximatelyEqual(sect2->fCurve[TCurve::kPointLast])) {
        zeroOneSet |= kOneS1Set | kOneS2Set;
        if (sect1->fCurve[TCurve::kPointLast] != sect2->fCurve[TCurve::kPointLast]) {
            intersections->insertNear(1, 1, sect1->fCurve[TCurve::kPointLast],
                    sect2->fCurve[TCurve::kPointLast]);
        } else {
            intersections->insert(1, 1, sect1->fCurve[TCurve::kPointLast]);
        }
    }
    return zeroOneSet;
}

template<typename TCurve>
struct SkClosestRecord {
    void addIntersection(SkIntersections* intersections) const {
        double r1t = fC1Index ? fC1Span->endT() : fC1Span->startT();
        double r2t = fC2Index ? fC2Span->endT() : fC2Span->startT();
        intersections->insert(r1t, r2t, fC1Span->part()[fC1Index]);
    }

    void findEnd(const SkTSpan<TCurve>* span1, const SkTSpan<TCurve>* span2,
            int c1Index, int c2Index) {
        const TCurve& c1 = span1->part();
        const TCurve& c2 = span2->part();
        if (!c1[c1Index].approximatelyEqual(c2[c2Index])) {
            return;
        }
        double dist = c1[c1Index].distanceSquared(c2[c2Index]);
        if (fClosest < dist) {
            return;
        }
        fC1Span = span1;
        fC2Span = span2;
        fC1StartT = span1->startT();
        fC1EndT = span1->endT();
        fC2StartT = span2->startT();
        fC2EndT = span2->endT();
        fC1Index = c1Index;
        fC2Index = c2Index;
        fClosest = dist;
    }

    bool matesWith(const SkClosestRecord& mate) const {
        SkASSERT(fC1Span == mate.fC1Span || fC1Span->endT() <= mate.fC1Span->startT()
                || mate.fC1Span->endT() <= fC1Span->startT());
        SkASSERT(fC2Span == mate.fC2Span || fC2Span->endT() <= mate.fC2Span->startT()
                || mate.fC2Span->endT() <= fC2Span->startT());
        return fC1Span == mate.fC1Span || fC1Span->endT() == mate.fC1Span->startT()
                || fC1Span->startT() == mate.fC1Span->endT()
                || fC2Span == mate.fC2Span
                || fC2Span->endT() == mate.fC2Span->startT()
                || fC2Span->startT() == mate.fC2Span->endT();
    }

    void merge(const SkClosestRecord& mate) {
        fC1Span = mate.fC1Span;
        fC2Span = mate.fC2Span;
        fClosest = mate.fClosest;
        fC1Index = mate.fC1Index;
        fC2Index = mate.fC2Index;
    }
    
    void reset() {
        fClosest = FLT_MAX;
        SkDEBUGCODE(fC1Span = fC2Span = NULL);
        SkDEBUGCODE(fC1Index = fC2Index = -1);
    }

    void update(const SkClosestRecord& mate) {
        fC1StartT = SkTMin(fC1StartT, mate.fC1StartT);
        fC1EndT = SkTMax(fC1EndT, mate.fC1EndT);
        fC2StartT = SkTMin(fC2StartT, mate.fC2StartT);
        fC2EndT = SkTMax(fC2EndT, mate.fC2EndT);
    }

    const SkTSpan<TCurve>* fC1Span;
    const SkTSpan<TCurve>* fC2Span;
    double fC1StartT;
    double fC1EndT;
    double fC2StartT;
    double fC2EndT;
    double fClosest;
    int fC1Index;
    int fC2Index;
};

template<typename TCurve>
struct SkClosestSect {
    SkClosestSect()
        : fUsed(0) {
        fClosest.push_back().reset();
    }

    void find(const SkTSpan<TCurve>* span1, const SkTSpan<TCurve>* span2) {
        SkClosestRecord<TCurve>* record = &fClosest[fUsed];
        record->findEnd(span1, span2, 0, 0);
        record->findEnd(span1, span2, 0, TCurve::kPointLast);
        record->findEnd(span1, span2, TCurve::kPointLast, 0);
        record->findEnd(span1, span2, TCurve::kPointLast, TCurve::kPointLast);
        if (record->fClosest == FLT_MAX) {
            return;
        }
        for (int index = 0; index < fUsed; ++index) {
            SkClosestRecord<TCurve>* test = &fClosest[index];
            if (test->matesWith(*record)) {
                if (test->fClosest > record->fClosest) {
                    test->merge(*record);
                }
                test->update(*record);
                record->reset();
                return;
            }
        }
        ++fUsed;
        fClosest.push_back().reset();
    }

    void finish(SkIntersections* intersections) const {
        for (int index = 0; index < fUsed; ++index) {
            const SkClosestRecord<TCurve>& test = fClosest[index];
            test.addIntersection(intersections);
        }
    }

    // this is oversized by one so that an extra record can merge into final one
    SkSTArray<TCurve::kMaxIntersections + 1, SkClosestRecord<TCurve>, true> fClosest;
    int fUsed;
};

// returns true if the rect is too small to consider
template<typename TCurve>
void SkTSect<TCurve>::BinarySearch(SkTSect* sect1, SkTSect* sect2, SkIntersections* intersections) {
    intersections->reset();
    intersections->setMax(TCurve::kMaxIntersections);
    SkTSpan<TCurve>* span1 = sect1->fHead;
    SkTSpan<TCurve>* span2 = sect2->fHead;
    bool check;
    if (!span1->intersects(span2, &check)) {
        return;
    }
    if (check) {
        (void) EndsEqual(sect1, sect2, intersections);
        return;
    }
    span1->fBounded.push_back() = span2;
    span2->fBounded.push_back() = span1;
    do {
        // find the largest bounds
        SkTSpan<TCurve>* largest1 = sect1->boundsMax();
        if (!largest1) {
            break;
        }
        SkTSpan<TCurve>* largest2 = sect2->boundsMax();
        bool split1 = !largest2 || (largest1 && (largest1->fBoundsMax > largest2->fBoundsMax
            || (!largest1->fCollapsed && largest2->fCollapsed)));
        // split it
        SkTSect* splitSect = split1 ? sect1 : sect2;
        SkTSpan<TCurve>* half1 = split1 ? largest1 : largest2;
        SkASSERT(half1);
        if (half1->fCollapsed) {
            break;
        }
        // trim parts that don't intersect the opposite
        SkTSpan<TCurve>* half2 = splitSect->addOne();
        SkTSect* unsplitSect = split1 ? sect2 : sect1;
        if (!half2->split(half1)) {
            break;
        }
        splitSect->trim(half1, unsplitSect);
        splitSect->trim(half2, unsplitSect);
        // if there are 9 or more continuous spans on both sects, suspect coincidence
        if (sect1->fActiveCount >= COINCIDENT_SPAN_COUNT
                && sect2->fActiveCount >= COINCIDENT_SPAN_COUNT) {
            sect1->coincidentCheck(sect2);
        }
#if DEBUG_T_SECT
        sect1->validate();
        sect2->validate();
#endif
#if DEBUG_T_SECT_DUMP > 1
        sect1->dumpBoth(*sect2);
#endif
        if (!sect1->fHead || !sect2->fHead) {
            return;
        }
    } while (true);
    if (sect1->fActiveCount >= 2 && sect2->fActiveCount >= 2) {
        // check for coincidence
        SkTSpan<TCurve>* first = sect1->fHead;
        do {
            if (!first->fCoinStart.isCoincident()) {
                continue;
            }
            int spanCount = 1;
            SkTSpan<TCurve>* last = first;
            while (last->fCoinEnd.isCoincident()) {
                SkTSpan<TCurve>* next = last->fNext;
                if (!next || !next->fCoinEnd.isCoincident()) {
                    break;
                }
                last = next;
                ++spanCount;
            }
            if (spanCount < 2) {
                first = last;
                continue;
            }
            int index = intersections->insertCoincident(first->fStartT, first->fCoinStart.perpT(),
                    first->fPart[0]);
            if (intersections->insertCoincident(last->fEndT, last->fCoinEnd.perpT(),
                    last->fPart[TCurve::kPointLast]) < 0) {
                intersections->clearCoincidence(index);
            }
        } while ((first = first->fNext));
    }
    int zeroOneSet = EndsEqual(sect1, sect2, intersections);
    sect1->recoverCollapsed();
    sect2->recoverCollapsed();
    SkTSpan<TCurve>* result1 = sect1->fHead;
    // check heads and tails for zero and ones and insert them if we haven't already done so
    const SkTSpan<TCurve>* head1 = result1;
    if (!(zeroOneSet & kZeroS1Set) && approximately_less_than_zero(head1->fStartT)) {
        const SkDPoint& start1 = sect1->fCurve[0];
        double t = head1->closestBoundedT(start1);
        if (sect2->fCurve.ptAtT(t).approximatelyEqual(start1)) {
            intersections->insert(0, t, start1);
        }
    }
    const SkTSpan<TCurve>* head2 = sect2->fHead;
    if (!(zeroOneSet & kZeroS2Set) && approximately_less_than_zero(head2->fStartT)) {
        const SkDPoint& start2 = sect2->fCurve[0];
        double t = head2->closestBoundedT(start2);
        if (sect1->fCurve.ptAtT(t).approximatelyEqual(start2)) {
            intersections->insert(t, 0, start2);
        }
    }
    const SkTSpan<TCurve>* tail1 = sect1->tail();
    if (!(zeroOneSet & kOneS1Set) && approximately_greater_than_one(tail1->fEndT)) {
        const SkDPoint& end1 = sect1->fCurve[TCurve::kPointLast];
        double t = tail1->closestBoundedT(end1);
        if (sect2->fCurve.ptAtT(t).approximatelyEqual(end1)) {
            intersections->insert(1, t, end1);
        }
    }
    const SkTSpan<TCurve>* tail2 = sect2->tail();
    if (!(zeroOneSet & kOneS2Set) && approximately_greater_than_one(tail2->fEndT)) {
        const SkDPoint& end2 = sect2->fCurve[TCurve::kPointLast];
        double t = tail2->closestBoundedT(end2);
        if (sect1->fCurve.ptAtT(t).approximatelyEqual(end2)) {
            intersections->insert(t, 1, end2);
        }
    }
    SkClosestSect<TCurve> closest;
    do {
        while (result1 && result1->fCoinStart.isCoincident() && result1->fCoinEnd.isCoincident()) {
            result1 = result1->fNext;
        }
        if (!result1) {
            break;
        }
        SkTSpan<TCurve>* result2 = sect2->fHead;
        while (result2) {
            closest.find(result1, result2);
            result2 = result2->fNext;
        }
        
    } while ((result1 = result1->fNext));
    closest.finish(intersections);
}